5
$\begingroup$

Machine learning can be divided into several areas: supervised learning, unsupervised learning, semi-supervised learning, learning to rank, recommendation systems, etc, etc.

One such area is PU Learning, where only Positive and Unlabeled instances are available.

There are many publications about this, usually involving a lot of mathematics...

When looking at the literature, I was expecting to see methods similar to self-training (from semi-supervised learning), where labels are adjusted gradually according to the classifier margins.

I don't think these is what practitioners from the area do, and I was unable to navigate the mathematics or to find a survey on PU learning.

Could someone from the area perhaps clarify what said practitioners do? Why can they not just use a binary classifier where the negative class=unlabeled? Can negative labels exist among the unlabeled data? What is the goal and what metrics exist to evaluate said goal?

$\endgroup$
  • 2
    $\begingroup$ are you familiar with anomaly detection? $\endgroup$ – Media Jan 17 '18 at 15:02
  • 1
    $\begingroup$ @Media, One-class classification? $\endgroup$ – Ricardo Cruz Jan 17 '18 at 15:04
  • 1
    $\begingroup$ I try to answer, let me know if you don't understand $\endgroup$ – Media Jan 17 '18 at 15:08
  • 1
    $\begingroup$ @Media, I don't understand. Where is your answer? $\endgroup$ – Ricardo Cruz Jan 17 '18 at 15:10
  • 1
    $\begingroup$ I'm typing it :) wait :D $\endgroup$ – Media Jan 17 '18 at 15:13
2
$\begingroup$

Why can they not just use a binary classifier where the negative class=unlabeled?

E.g., when there are only a small portion of data are labeled as positive samples. It happens in reality where you don't have enough resources to label all the data. If you trained your model assuming all unlabeled data are negative samples, your model will have to find a decision boundary between true positive samples. Then your model would most likely perform poorly.

PU learning is just a sub-class of semi-supervised learning.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Sure, but you will bias your model to commit false negatives errors (you reduce sensitivity). This is unacceptable in some contexts like medicine where PU are prevelant. The all point of PU algorithms is to create more sophisticated algorithms than just assuming unlabeled=negatives. Some of the unlabeled are positive! $\endgroup$ – Ricardo Cruz Aug 17 '18 at 9:18
  • $\begingroup$ I think I misunderstood what you meant by "where the negative class = unlabeled". I thought you meant assuming all unlabeled data to be negative class. And my answer was a response to that, saying that can lead to poor performance. $\endgroup$ – plpopk Aug 20 '18 at 6:13
  • $\begingroup$ Personally, I handle semi-supervised learning in this way: for a unlabeled data, I'll let my algorithm figure out which labeled data it is most similar to, e.g. using KNN. Afterward, for those false prediction sample, add it to the NN kernel. Same strategies apply to SVM. $\endgroup$ – plpopk Aug 20 '18 at 6:20
1
$\begingroup$

Whenever you have skewed data-set, it means that you know a typical class better than the others. In such cases it means that the data is your knowledge and is not in a way that finds the minimum of the Bayes error because you don't know the distribution of other available classes and consequently you won't be able to find out whether the distribution of different classes overlap in the current feature space. and there are learning algorithms for such occasions.

Consider an important fact here. Suppose that you have feature vectors of conditions of a nuclear company and they describe whether the company is in danger of nuclear radiation or not. In such cases it is clear that it does not happen a lot that you have infected companies so almost, all of you data has label of healthy condition. You have so much knowledge about the healthy class but you don't know much about the infected class because you don't have much data; consequently, you don't know its distribution and you can not estimate it well. Whenever your data is skewed, it means that e.g. you have 1 million feature vectors of negative class and 5 feature vectors of positive class if there is any.

I quote from here that in statistical learning there is something called Bayes Error, whenever the distribution of classes overlap, the ratio of error is large. without changing the features, the Bayes error of the current distributions is the best performance and can not be reduced at all If the number of samples of each class is equal. In anomaly problems, this is not possible. You can not find balanced samples for each class.

| improve this answer | |
$\endgroup$
1
$\begingroup$

A couple of points I have since found myself:

  1. I was right in suspecting that self-training could be used for PU learning. In fact, I found the original paper on PU Learning, and indeed the paper is a variation on self-training. (Oddly enough, the original authors had Positive, Unlabeled and Negative examples!)
  2. The authors of this survey identify three families of methods: (i) two-step strategy (identify reliable negative examples in the unlabeled data and then use supervised learning), (ii) weight the positive and unlabeled examples, and estimate the conditional probability of positive label given an example (I believe this is akin to semi-supervised self-training), and (iii) just treat the unlabeled data as highly noisy negative data.
  3. There are also some interesting loss functions to be used with neural networks (and I imagine could be adapted for gradient boosting) described in Table 1 of this paper.
| improve this answer | |
$\endgroup$
1
$\begingroup$

Taking the specific example of Collaborative-Filtering recommender systems, an initial dataset containing a large percentage of positive examples and a small percentage of unlabelled examples for one class, is often tackled by imputing a negative value to the unlabelled examples based on the argument of popularity.

This means that for a class which has overall high popularity (based on the number of labelled examples) within the dataset, it is safe to assume a negative inclination for the unknown examples.

@Ricardo Cruz: I believe this would be similar to your point 2(iii).

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.