How does a classifier handle unseen documents that do not belong to any of the pre-existing classes?

Question

I am doing text classification, and have been playing around with different classifiers. However I have a pretty basic question: what if a new unseen document comes in and it happens to not belong to any of the pre-existing classes? The classifiers that I have seen (in WEKA, libsvm etc.) still go ahead and put the unseen document in one of the existing classes anyway.

This situation comes up pretty frequently in my work. How can I handle it sensibly?

On a related note, is there a way I could get a sense of how confident a classifier is regarding it's classification decision?

================================Edit 1======================================

After reading the comments here, I think I am going to try one of the two things:

(1) Use the approach described in Zadrozny,Elkan paper that Steffen pointed me to, in order to get the probability estimates. If the probabilities are less than a magic threshold, I could then simply discard the unseen instance as noise.

(2) I am increasingly starting to think that I could instead handle this as n 1-class problems. let's say that I have n classes in my data. I could build and train n 1-class classifiers that give a yes/no decision (whether an instance belongs to a particular class or not). So that way when a new instance comes in, I could just pass it through each of there 1-class classifiers.

Thoughts? Any implementations/packages anyone is aware of that would let me do (2)?

===========================================================================

Answer 1

It sounds to me that the problem is one of "novelty detection", you want to identify test patterns of a type not seen in the training data. This can be achieved using the one-class support vector machine, which IIRC tries to construct a small volume in a kernel induced feature space that contains all (or a large fraction) of the training set, so any novel patterns encountered in operation are likely to fall outside this boundary. There are loads of papers on uses of one-class SVM indexed on Google Scholar, so it should be easy to find something relevant to your application.

Another approach would be to build a classifier by constructing a density estimator for each class, and then combine using Bayes rule for the classification. If the likelihood of a test observation for the winning class is low, you can then reject the pattern as a possible novelty.

Answer 2

In a lot of the classification algorithms (note: I do mean classification in the 'classical' sense here), it is silently assumed that the classes are complete, i.e. every observation must belong to one of the classes. So in that sense, the situation you are describing should not occur.

A kind of solution if your classes are not complete, is to provide a 'garbage' class. This may or may not work, depending on your situation, because the items that get assigned to this class could be of diverse nature, so if you take this class along in your classification algorithm, it may not work as expected. If your 'real' classes are strongly predicted, it could still work.

If you roll your own algorithm, you could exclude this class from the algorithm and just throw the nonfitting observations 'in the garbage', but I guess you would be violating some assumptions then (so guarantees provided by some methods will no longer be valid).

A relatively easy way to assess the confidence of a classifier is to do crossvalidation with missclassification.

Answer 3

I find this interesting, you say that you somehow "know" that it does not belong to the classes given. Yet you do not then describe what precisely it is about that item that makes you think this. As soon as you suspect a class coming from "something else" (called SE from now on) you have basically begun to describe a model for predicting that class - if only intuitively. The task then is to "weed out" the model that is hiding in your intuition.

This is always done by describing what distinguishes SE from the rest of your data (this always exists, or else you wouldn't suspect anything). The main problem with the SE is that this distinguishing feature must be based on the prior information alone - no data can possibly be used to train a classifier for SE. For if it could, then SE would effectively not exist as you explain, it would just be one of the classes.

The best way to incorporate SE is to make a prediction about what kind of document you would see if it came from SE. Given that the situation comes up pretty frequently, this should not be too difficult to do (as you would have some idea of the type of features that you would predict).

If you are using a Bayesian posterior probability based approach this is fairly simple to incorporate into a standard analysis. We just add one extra likelihood into the denominator, so you have:

$$P(C_{i}|D_{new}D_{train}I)=\frac{P(C_{i}|D_{train}I)P(D_{new}|C_{i}D_{train}I)}{P(D_{new}|D_{train}I)}$$ $$=\frac{P(C_{i}|D_{train}I)P(D_{new}|C_{i}D_{train}I)}{\left[\sum_{j=1}^{r}P(C_{j}|D_{train}I)P(D_{new}|C_{j}D_{train}I)\right]+P(C_{SE}|D_{train}I)P(D_{new}|C_{SE}D_{train}I)}$$

Where $C_{j}$ is the jth class (plus something else), $D_{new}$ is the data from the document you are trying to classify, $D_{train}$ is the training data, and $I$ is your prior information. Note that the general procedure is not any different in principle from adding any of the other classes. But it is different in practice because the phrase "something else" is vague and does not make any obvious predictions about future data.