# Getting probabilities over 1 in positive and unlabeled learning

I have a question regarding PU-Learning, which deals with learning from positive-labeled (no labeled negative examples) and positive/negative-unlabeled data.

Particularly, my question is about the paper Learning classifiers from only Positive and Unlabeled data. This paper converts a non-traditional classifier $g(x)$ which is learned from labeled/unlabeled datasets and outputs the probability of an example of being labeled, into a traditional classifier $f(x)$ which outputs the probability of an example to be positive. I have implemented the first proposed approach (section 2, "learning a traditional classifier from nontraditional input"). However, the probability $f(x)=g(x)/p(s=1|y=1)$ becomes greater than 1 for several examples (this should not be greater than 1, since it is a probability)

For learning the non-traditional classifier $g(x)$, I am using a non-traditional dataset composed of

1. 100,000 labeled examples randomly chosen from the whole labeled data, and
2. 100,000 unlabeled examples randomly chosen from the whole unlabeled data.

And for estimating $p(s=1|y=1)$--with the first proposed estimator--I am using a validation dataset composed of 30,000 labeled instances randomly chosen from a separate labeled dataset.

According to the paper, the probability $f(x)$ is guaranteed to be well-formed if (1) and (2) overlap in the example space. In my case, (1) and (2) have a 20% of overlapped examples, but I am still getting non well-formed probabilities (>1).

How could I achieve a well-defined probability for $f(x)$?

EDIT 8/21

1. According to the paper, $g(x)$ must be a classifier that produces correct probabilities as its output, like Logistic Regression, or a calibrated classifier such as Naive Bayes/SVM, in order to get the approach to work. I am simply using Maximum Entropy classifier (from the NLTK package), also known as Logistic Regression. Therefore I guess there should not be any problem with this.

2. Although the paper states that the labeled (1) and unlabeled (2) datasets for training $g(x)$ are "samples from overlapping regions in feature space", such datasets seem to be disjoint (see experiment from Section 5, P and U are disjoint). I have tried with disjoint labeled and unlabeled datasets as well, however I am still getting probabilities over one for $f(x)$.

3. Balancing datasets does not make any difference, neither.

4. I have tried the second estimator proposed(e2). Still getting probabilities over 1 for $f(x)$.

EDIT 8/29

1. In section 5, which describes an example with real-world data, we have a set P of labeled+positive examples from the database TCDB, and a set U of unlabeled examples randomly sampled from the database SwissProt, being P and U disjoint. Then they use P,U to learn a non traditional classifier. I think that this approach can be applied to my problem, since I also have a set of positive examples, and a set of unlabeled examples randomly sampled. What do you think ?

2. I have tried the third estimator proposed(e3). Since it takes the maximum probability of the examples from the positive-labeled set (in my case around 0.98), I am no longer getting probabilities over one. However, since this estimate is only based in one example and not the average between all examples, therefore this does not look like a good estimator to me. Any thoughts regarding the validity of this estimator?

Thanks

-

I tried to follow authors' instructions with a very simple test case. Here is the R code that I used.

set.seed(123)
# Create the data according to authors' notations.
# For the first 100 observations y = 1, and for the last 100 y = 0.
# Only the first 25 obersvations are labelled, according to their
# "chosen completely at random" criterion.
c <- 25/100
data <- data.frame(
y = c(rep(1,100), rep(0,100)),
x = c(rnorm(100, mean=2), rnorm(100, mean=0)),
s = c(rep(1,25), rep(0, 175))
)
# Train a standard logistic classifier on s
g <- glm(s ~ x, data=data, family="binomial")
max(g$fitted.values / c) # 1.676602  So even on very simple cases the estimated probabilities go higher than one. The reason this happens is that the estimated probabilities$g(x) = p(s=1|x)$are estimated. If we actually have$g(x) \approx p(s=1|x)$, and$c$itself is estimated, nothing prevents$ g(x) / c$to be greater than one. Actually the method has very strong practical limits. First you need to have a good estimate of$c$, which you can only get with a traditional dataset. Second, there has to be a single sample "chosen completely at random". Third... well you just pointed out the third point ;-) Note: from your description, I got the feeling that your sampling scheme is not "chosen completely at random", as the authors insist heavily. There is a subtle but important difference between the scenario considered here, and the scenario considered in [21]. The scenario here is that the training data are drawn randomly from$p(x, y, s)$, but for each tuple$\langle x, y, s\rangle$that is drawn, only$\langle x, s\rangle$is recorded. The scenario of [21] is that two training sets are drawn independently from$p(x, y, s)$. - Thanks for your time and patience. Regarding my sampling, in my problem I have a pool with lots of labeled examples, where labeled examples are only from class P <x,y=P,s=1>, and unlabeled ones can be from either class P or N <x,y=None,s=0>. Then, I randomly choose X examples <x,s=1> from the labeled data of the pool, and X examples <x,s=0>from the unlabeled data of the pool to train g. The validation dataset for estimating c is also retrieved similarly, using data from another pool. Isn't my sampling scheme completely at random? And, should I build a traditional dataset to estimate c? Thanks! – AM2 Aug 22 '12 at 15:28 What they call "completely at random" means that you first draw a sample from the population, then from that sample, choose at random among the examples such that$y=1$a labelled subsample ($s=1$). This is important to estimate$c$, which is the probability that an example such that$y=1$is labelled. To estimate it, you need a sample of which you know the value of$y$, and to me this looks like a traditional sample. – gui11aume Aug 22 '12 at 17:27 Thanks again. I am sorry but I still have some doubts with this 2 questions: (1) regarding the sampling, choosing random labeled (and thus positive) examples from the population is exactly what I am doing, right? And (2) regarding c, what about using a dataset P containing m positive labeled and n positive unlabeled examples, and estimate c as sum[g(x) for all x in P]/(m+n) ? – AM2 Aug 23 '12 at 1:38 (1) What you do: start from a population of labeled and unlabeled examples; draw labeled examples at random; draw unlabeled examples at random. What they do: start from a population of unlabled examples for which$y$is know; draw a sample; among those for which$y=1$in that sample, choose some at random that you label; provide only$(x,s)$. – gui11aume Aug 23 '12 at 7:25 (2) If you have such a random sample, why not take$c = m / (m+n)$? If$m$and$n$are not random (chosen by you) this will not work of course. But in this case you can also not follow this whole approach. The important point in my answer to (1) is that "sampling completely at random" depends on$p(s=1|y=1)$, in your case it does not, so this quantity has no meaning for your model. Here it is the same, you have to have a sample that depends on$p(s=1|y=1)$, which is not the case of$m$and$n\$ are not random. – gui11aume Aug 23 '12 at 7:34