1
$\begingroup$

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)?

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

$\endgroup$
  • 1
    $\begingroup$ IMO you should ask the second part (confidence) as a different question -- it is a broad topic and very classifier-dependent. $\endgroup$ – user88 May 20 '11 at 9:12
  • $\begingroup$ regarding confidences: this question might help. $\endgroup$ – steffen May 20 '11 at 9:38
  • $\begingroup$ @steffen : That's interesting, and I'll certainly take a look. Although I was actually that there would be something less labor intensive :-) $\endgroup$ – Andy May 20 '11 at 14:03
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So if I understand you right, you are basically suggesting doing what I was alluding to in comment (2) in the edits? I just found a one-class SVM implementation in libsvm, so I think I am going to use that as first cut. $\endgroup$ – Andy May 20 '11 at 19:59
  • $\begingroup$ @Andy, sort of, I was suggesting using a one class classifier for novelty detection, but a standard multi-class classifier for performing the classification of observations that are not novelties. I think that may work out better as one-class classifiers are good for novelty detection, but are not likely to be as good as a discriminative classifier for performing the actual classification. Libsvm is an excellent bit of kit, so you are off to a good start. $\endgroup$ – Dikran Marsupial May 21 '11 at 17:57
  • $\begingroup$ I suppose I am a little confused now. So how will I do the novelty detection? Are you saying that I generate something like one single decision boundary across all my training instances, and then based on this decision boundary determine whether a new instance is an outlier or not? $\endgroup$ – Andy May 21 '11 at 22:36
  • $\begingroup$ @andy, yes that is correct, fit a one-class classifier to the whole of the training set, and reject any observation that falls outside the boundary as being a novelty belonging to a new class. Use a conventional multi-class classifier to classify any pattern that falls within the boundary of the one-class classifier. $\endgroup$ – Dikran Marsupial May 23 '11 at 10:11
  • $\begingroup$ That seems reasonable. Let me give it a shot. $\endgroup$ – Andy May 25 '11 at 2:54
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (-1/+1): 1. The OP did explicitly say that this situation arises pretty frequently. 2. You wrote: If you roll your own algorithm, you could exclude this class from the algorithm and just throw the nonfitting observations 'in the garbage' How to determine non-fitting observations during application of the classifier ? If the garbage class is known, what is the advantage in comparison to keep the garbage class 3. I think with "confidence" the OP referenced to "confidence of a single decision" not total classifier quality. $\endgroup$ – steffen May 20 '11 at 7:17
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Well actually, that "something else" in my case is just noise. So I don't think I will be able to model that. $\endgroup$ – Andy May 20 '11 at 14:25
  • $\begingroup$ @andy - you can model "noise" - but it depends on what sort of noise you are modelling. For example, one way to model noise is using a mixture model with lots of components, or some other "non-parametric" model. The idea is to get a model with lots of parameters, so it can fit any data you give it. you then set non-informative priors over these and you effectively introduce a penalty for each parameter (similar to BIC). $\endgroup$ – probabilityislogic May 21 '11 at 0:26

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.