6
$\begingroup$

I have a large set of data and a small subset is labelled as being in class 'A' and the rest is unlabelled. I know that some of the unlabelled data should also be labelled 'A'. In order to label some more of the data my idea is to do the following:

  1. Build a classifier on the whole data set separating the class 'A from the unlabelled data.
  2. Run the classifier on the unlabelled data.
  3. Add the unlabelled items classified as being in class 'A' to class 'A'.
  4. Repeat.

There are lots of parts that are unclear and/or problematic such as when to stop and how exactly to set the thresholds for when to accept something as being in class 'A'.

Is a method like this known already in the literature so that I can gain some ideas for how to do it properly?

$\endgroup$
5
  • $\begingroup$ Why not just: (1) run the algorithm on labeled data, (2) use the result for labeling unlabeled data? $\endgroup$
    – Tim
    Sep 8 '15 at 7:18
  • $\begingroup$ There are many classification algorithms out there: classification trees, k-Means, ... It would be easier to know what your data exactly looks like. But I can refer you to this book www-bcf.usc.edu/~gareth/ISL. You can find a well written introduction to some of the concepts in there. $\endgroup$ Sep 8 '15 at 8:35
  • 1
    $\begingroup$ @Tim I think the problem is there's only one label: "A". There's no "Not - A" data to learn from. You're learning from a dataset of "definitely A" and "may or may not be A, who knows." $\endgroup$
    – Zach
    Sep 8 '15 at 14:19
  • $\begingroup$ @Zach ok, but there are classification algorithms for such cases, e.g. one-class SVM. $\endgroup$
    – Tim
    Sep 8 '15 at 16:39
  • 2
    $\begingroup$ @Tim one-class SVM is a poor choice for this task, since it doesn't use the unlabeled data at all. PU learning techniques yield far better results. $\endgroup$ Sep 8 '15 at 19:57
6
$\begingroup$

Learning from positive and unlabeled data is often referred to as PU learning. what you describe is a common approach to these kinds of problems, though I personally dislike such iterative approaches because they are highly sensitive to false positives (if you have any).

You might want to check out two of my papers and references therein for an up-to-date overview on current research for these problems:

The first paper describes a state-of-the-art method to learn classifiers and the second is the only approach that allows you to estimate any performance metric based on contingency tables from test sets without known negatives (you read that right).

Both papers also provide a good overview of the existing literature on this subject.

$\endgroup$
1
  • 2
    $\begingroup$ +1 it's interesting. Your answer would be even more helpful if you provided a short summary of those methods - how do they work? why are they better? $\endgroup$
    – Tim
    Sep 9 '15 at 7:07
2
$\begingroup$

What you describe is very sound idea. It is called Semi-Supervised Expectation-Maximization and is oftenly used in text classification. Here is some literature:

http://research.microsoft.com/en-us/um/people/xiaohe/nips08/paperaccepted/nips2008wsl1_02.pdf

http://ciitresearch.org/dl/index.php/aiml/article/view/AIML052012012

http://www.cs.cmu.edu/~tom/pubs/NigamEtAl-bookChapter.pdf

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