How can I assess performance of a semi-supervised learning method?

Question

I'm working with a semi-supervised learning task, where I only have positive and unlabelled data (PU learning).

I've tested a few algorithms and would like to assess their performance.

For supervised learning, I normally use:

1. Misclassification error
2. Accuracy
3. ROC curves

to assess performance.

However, since I only have positive and unlabelled data in my training and validation sets I'm not sure these metrics make sense.

What metrics can I use to properly assess the performance of a semi-supervised learning method?

Answer 1

We have addressed this problem in Assessing binary classifiers using only positive and unlabeled data. Specifically, we show how to compute strict bounds on any metric based on contingency tables (accuracy, precision, ROC/PR curves, ...). Our work was accepted by all reviewers at this year's NIPS conference, but then rejected by the editor for lack of significance (go figure). We will submit it to the upcoming KDD.

Our approach is based on the reasonable assumption that known positives are sampled completely at random from all positives. If you can't rely on this assumption, any form of performance evaluation is infeasible. Additionally, we require an estimate of the fraction of positives in the unlabeled set, which you can often acquire via domain knowledge or by explicitly obtaining labels for a small, random subset of the unlabeled set.

Answer 2

Here's a sideways thinking idea: You have some positive labels and you can estimate the natural grouping of data using unsupervised learning. Try to measure the overlap between the known information and the way the data groups together, use the overlap as a ground truth measure.

So, perform unsupervised learning, see how the labeled data corresponds to the clusters. If your're in luck, then the labels will correlate to only one of the clusters or to outliers (which might turn out to be clusters given more data).

Outcome A - disjoint groups of data

Let's say that you have 10 labels from 100 unlabeled examples and after clustering it turns out that the 10 labels belong to a cluster with 20 data points. This is the happy case and you can now label all 20 with 1 and everything else as 0. Problem solved, just use AUC.

Outcome B - more than 2 groups, fuzzy clusters

What if this is not the case? What about the other groups?

If not, let's say you have 9 labels in cluster with 20 and 1 in one of the other clusters (hopefully the only other one). Repeat multiple times and count how many times did a label 'land' in a certain group. Compute the mutual information between the labeled data (positive examples) $X$ and the other groups $Y$ over multiple clusterings.

$$ I(X;Y) = \sum_{y \in Y} \sum_{x \in X} p(x,y) \log{ \left(\frac{p(x,y)}{p(x)\,p(y)} \right) }, \,\! $$

So, with $K=3$ clusters you will finally have $I_k(X;Y)$ for each group. Assume that these values are the ground truth (target values) when you evaluate your final model.

This is based on the assumption that your prediction will also have the positive labels (now, more of them) distributed in a certain way in the unsupervised grouping of data.