Can I train a multi-class linear classifier to output uniform scores for out-of-domain input?

Question

Suppose I train a multi-class classifier with K classes. However, in a practical application, an input can belong to none of the K classes. Thus, the K+1 class is introduced. The training data for this out-of-domain class is needed of course. The training of such classifier and usage is no different than the K-class classifier.

My question is: Why can't we get away with the original K binary classifiers including the case of out-of-domain input?

If an object belongs to one of of K classes, its score (or confidence) is 1.0 for the respective class. And it is zero for other K-1 classes. This is the case of highest certainty or lowest entropy.

If input belongs to none of the K classes, its score is 1/K for all K classes. This is the case of highest uncertainty or maximum entropy.

In a practical setting, I would compute entropy of the discrete distribution (scores/confidences must sum to one). If it is very close to uniform, the decision is "out-of-domain". If entropy is very low, then the classifier's prediction is the class for which the score is the highest (classical usage).

Is it possible to construct such classifier? If not, what are the reasons? A link to a publication would be great.

By extension, would that work for a multiple layer neural network? The last layer in the feed-forward neural network is essentially a linear classifier with a softmax at the end.

Answer 1

It seems like a reasonable thing to try, but I expect that it will fail in many scenarios.

The problem is the binary classifiers never see out-of-distribution samples during training time, so they might behave arbitrarily poorly on out-of-distribution samples. It's possible that an out-of-distribution sample might be (wrongly) accepted by one of your binary classifiers as belonging to one of the classes, even though it doesn't actually. There is nothing in training to prevent this.

Let me give you a concrete example. Suppose we have $K=2$ classes, and you have a training dataset that comes from the following distribution: each sample lies in a two-dimensional space $\mathbb{R}^2$; class 0 samples are distributed as $(X_0,10)$ where $X_0 \sim \mathcal{N}(5,1)$; and class 1 samples are distributed as $(X_1,10)$ where $X_1 \sim \mathcal{N}(-5,1)$. If we train a binary linear classifier for each class, the class 0 classifier is likely to accept samples $(x,y)$ where $x \ge 0$ as being in class 0; and the class 1 classifier is likely to accept samples $(x,y)$ where $x \le 0$ as being in class 0.

Now suppose that you receive an out-of-distribution sample, say $(5,-10)$. What is going to happen? The class 0 classifier will accept it as being a part of class 0; therefore, you will predict that this sample is "class 0". That is undesirable -- we wish it would recognize that this should be treated as "unknown". Unfortunately, your strategy is unable to recognize this sample as "unknown", because during training, the classifier was never trained on anything outside of the normal distribution, so there was no signal or pressure for the classifier to reject points from outside the in-distribution data.

In short, the issue with your scheme is, when we feed an out-of-distribution sample to a discriminative classifier trained only on in-distribution data, arbitrarily bad things can happen. The classifier is free to do whatever it wants on out-of-distribution data: there is nothing in the training process that forces it to do what you want in that region of the feature space.

Answer 2

It is worth pointing out that your problem of training a classifier to detect $k$ known classes and 1 "unknown" class can be split into a two-step problem. We would like a model to 1) classify a point as being "known" or "unknown" and 2) if "known", classify the point into one of $k$ classes.

Since you are apparently familiar with methods to classify things into $k$ classes, your problem has been reduced to classifying points as being "known" or "unknown". This is what is commonly called novelty detection or anomaly detection. For continuous input, a popular method is one-class SVM, which, in some sense, tries to find a "soft" convex hull for the training data. Other methods for anomaly detection abound in time-series and for other types of input.