4
$\begingroup$

When learning from only positive and unlabelled data (PU learning), how are performance measures affected, when compared to a standard supervised setting?

For simplicity, let's assume that the entire unlabelled set is treated as negative.

For example, intuitively, I think that the number of true positives will be underestimated due to the fact that some of the unlabelled observations are positive in reality.

However, I can't really wrap my head around other measures. What happens to these?

  • True Positives
  • True Negatives
  • False Positives
  • False Negatives
  • Accuracy
  • AUC
  • Precision
  • Recall/Sensitivity
  • Specificity
$\endgroup$
  • 2
    $\begingroup$ I will write an answer here soon. In the meantime, I think you will find our paper on assessing binary classifiers in a PU setting useful (arXiv). $\endgroup$ – Marc Claesen Jul 20 '16 at 20:59
  • 1
    $\begingroup$ Thanks Marc, much appreciated! Referring to your publication, I'm trying to draw a parallel between a PU setting where the unlabelled class is treated as negative and a standard supervised setting. Are the measurements above in the PU setting over or underestimated compared to the supervised setting? $\endgroup$ – enricoferrero Jul 21 '16 at 10:12
  • 2
    $\begingroup$ I hope my answer covers your question in sufficient detail, if not please let me know! $\endgroup$ – Marc Claesen Aug 5 '16 at 7:46
2
$\begingroup$

Introduction

Many practical applications have only positive and unlabeled data (aka PU learning), which poses problems in building and evaluating classifiers. Evaluating classifiers using only positive and unlabeled data is a tricky task, and can only be done by making some assumptions, which may or may not be reasonable for a real problem.

Shameless self-advertisement: For a detailed overview, I suggest reading my paper on the subject.


I will describe the main effects of the PU learning setting on performance metrics that are based on contingency tables. A contingency table relates the predicted labels to the true labels:

+---------------------+---------------------+---------------------+
|                     | positive true label | negative true label |
+---------------------+---------------------+---------------------+
| positive prediction | true positive       | false positive      |
| negative prediction | false negative      | true negative       |
+---------------------+---------------------+---------------------+

The problem in PU learning is that we don't know the true labels, which affects all cells in the contingency table (not just the last column!). It is impossible to make claims about the effect of the PU learning setting on performance metrics without making additional assumptions. For example, if your known positives are biased you can't make any reliable inference (this is common!).


Treating the unlabeled set as negative

A common simplification used in PU learning is to treat the unlabeled set as if it is negative, and then compute metrics as if the problem is fully supervised. Sometimes this is good enough, but this can be detrimental in many cases. I highly recommend against it.

Effect on precision. Say we want to compute precision:

$$p = \frac{TP}{TP + FP}.$$

Now, suppose we have a perfect classifier if we would know the true labels (i.e., no false positives, $p=1$). In the PU learning setting, using the approximation that the unlabeled set is negative, only a fraction of (in reality) true positives are marked as such, while the rest will be considered false positives, immediately yielding $\hat{p} < 1$. Obviously this is wrong, but it gets worse: the estimation error can be arbitrarily large, depending on the fraction of known positives over latent positives. Suppose only 1% of positives are known, and the rest is in the unlabeled set, then (still with a perfect classifier), we would get $\hat{p} = 0.01$ ... Yuck!

Effect on other metrics:

  • True Positives: underestimated
  • True Negatives: overestimated
  • False Positives: overestimated
  • False Negatives: underestimated
  • Accuracy: depends on balance and classifier

For AUC, sensitivity and specificity I recommend reading the paper as describing it in sufficient detail here would take us too far.


Start from the rank distribution of known positives

A reasonable assumption is that the known positives are a representative subset of all positives (e.g., they are a random, unbiased sample). Under this assumption, the distribution of decision values of known positives can be used as a proxy for the distribution of decision values of all positives (and hence also associated ranks). This assumption enables us to compute strict bounds on all entries of the contingency table, which then translates into (guaranteed!) bounds on all derived performance metrics.

A crucial observation we've made is that in the PU learning context under the assumption mentioned above is that the bounds on most performance metrics are a function of the fraction of positives in the unlabeled set ($\beta$). We have shown that computing (bounds on) performance metrics without an estimate of $\beta$ is basically impossible, as the bounds are then no longer strict.

$\endgroup$
  • $\begingroup$ Thanks Marc, excellent answer. Given that TP and FN are underestimated and TN and FP are overestimated, is it not obvious that sensitivity [TP/(TP+FN)] is underestimated and specificity [TN/(FP+TN)] is overestimated? $\endgroup$ – enricoferrero Aug 19 '16 at 12:07
  • $\begingroup$ It's a little more subtle, and depends on further assumptions. Lets work with sensitivity. Suppose an unlabeled set of size $U$, a fraction of positives in the unlabeled set $\beta \in [0, 1]$. If the known positives are a random sample of all positives, then their rank distribution approximates the rank distribution of all positives (see paper for details). This means that, at a given cutoff, the recall in the set of known positives is approximately equal to that of all positives. $\endgroup$ – Marc Claesen Aug 20 '16 at 2:44
  • $\begingroup$ Suppose we are at recall $r(0) \in [0, 1]$ in the set of known positives at a given cutoff, then $TP(\beta) = TP(0) + \beta U r(0)$ and $FN(\beta) = FN(0) + \beta U (1-r(0))$. Here, $TP(0)$ and $FN(0)$ are the number of true known positives and false known positives, and $\beta U$ is the number of positives in the unlabeled set. Then, $r(\beta) = TP(\beta) / \big(TP(\beta) + FN(\beta)\big) = \big(TP(0) + \beta U r(0)\big) / \big(TP(0) + FN(0) + \beta U \big) = r(0)$. $\endgroup$ – Marc Claesen Aug 20 '16 at 2:54

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.