Getting probabilities over 1 in positive and unlabeled learning

Question

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

Answer 1

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)$.