11
$\begingroup$

I have 2 datasets, one with positive instances of what I would like to detect, and one with unlabeled instances. What methods can I use ?

As an example, suppose we want to understand detect spam email based on a few structured email characteristics. We have one dataset of 10000 spam emails, and one dataset of 100000 emails for which we don't know whether they are spam or not.

How can we tackle this problem (without labeling manually any of the unlabeled data) ?

What can we do if we have additional information about the proportion of spam in the unlabeled data (i.e. what if we estimate that between 20-40% of the 100000 unlabeled emails are spam) ?

$\endgroup$
  • 1
    $\begingroup$ The post should be added the tags semi-supervised and pu-learning. These tags still do not exist and currently I cannot create them. $\endgroup$ – DaL Dec 7 '15 at 7:11
  • $\begingroup$ @DanLevin Yeah, [tag: semi-supervised-learning] makes sense. Added :) I'm not sure with the pu-learning part(atleast I'm not aware of it), so someone else can do it! $\endgroup$ – Dawny33 Dec 7 '15 at 10:51
  • 1
    $\begingroup$ PU-learning is a specific case of semi supervised learning. It is less common (7K results at Google) then semi supervised (298K results at Google) that this question is PU (the labeled dataset is just positives). While the topic is discussed the academy (e.g., cs.uic.edu/~liub/NSF/PSC-IIS-0307239.html) it is possible that this question will be alone with this tag for quite a while. $\endgroup$ – DaL Dec 7 '15 at 11:19
7
$\begingroup$

My suggestion would be to attempt to build some kind of clustering on your unlabeled data that somewhat approximates a labelled dataset. The rationale is more or less as follows:

  • You have some feature vector for representing your documents
  • Based on that feature vector, you can come up with a number of different clusterings, with either fuzzy, rough, or class-based clustering methods
  • Knowing what a positive example looks like, you can quickly evaluate the overall similarity of a cluster to your positive cluster
  • Knowing that there should really only be two clusters, you can adjust the hyperparameters on your clustering method so that the above two metrics are closer and closer to satisfaction
  • With the two clusters, you have what is likely a close approximation of a labelled dataset, which you can then use as a silver-standard corpus of sorts to actually train your model

Hope that makes sense, if you're specifically looking for clustering algorithms, a few that I personally enjoy that might be good in this scenario are FLAME and tsne. Alternately, looking at the spectacular gensim library in python will get you a long way toward the clustering you're looking for.

Hope that helps and makes sense, leave a comment if you've got any questions.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your answer. Do I understand right: your starting point is to merge the 2 datasets ? $\endgroup$ – nassimhddd Jul 9 '14 at 14:31
  • $\begingroup$ @cafe876 That is certainly one way to start, and then trying to basically recreate a clustering that closely approximates the original. $\endgroup$ – indico Jul 11 '14 at 0:36
3
$\begingroup$

Your problem belongs to the framework of PU learning (only positives, a lot of unlabelled).

It is also close to the more common frameworks of Semi supervised learning (few positives and negatives, a lot of unlabeled).

There are many survey papers that you can look up on the field.

A classical method in the field, that was also tested on spam as in your case, is co-training In co training you build two independent learners (e.g, one based on the mail content and one based on the sending scheme) and you use the results of one of the to train the other and vice versa.

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

Train 2 generative models, one for each dataset (spam only, spam plus ham), that will give you the probability that a datapoint is drawn from the same probability distribution of the training data. Assign emails as spam or ham based on which model gives you the highest probability of the document arising from the training data used to train it. Example generative models are RBM's, autoencoders (in that case, which model has the lowest reconstruction error). There are likely some bayesian generative models also that will assign a probability to a data point based on some training data.

The best option though would be to take time to curate a second dataset containing only ham. That will give you higher classification accuracy. Assuming a lower proportion of spam to ham emails, that should not be too hard. You can even use Mechanical Turk if you lack the time or resources (or interns \ graduates students or other cheap labor).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your answer. It's a great example of what generative models can do that discriminative models cannot. $\endgroup$ – nassimhddd Jul 9 '14 at 14:34

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.