Training a binary classifier acting on n-class data

Question

Given a classifier, that was trained on a data having two classes e.g. class red and class blue. The training samples are hand picked and only contains those two classes. After training the classifier should classify some samples, but it turns out that those samples contain the classes red, blue and a third one magenta (red+blue) e.g a class that contains features of both classes. The classifier will correctly identify red and blue but will degrade to a random guesser for magenta.

I try to give an example here (of course this is much simpler than in real life...): assume that a sample has the features A and B, which are binary fields (either 0 or 1).

The training data looks like this:

A   B   Label
-------------
1   0   red
1   0   red
0   1   blue
0   1   blue

One possibility for the classifier (e.g. a tree) would be to have the following output:

If A == 1: red
If A == 0: blue

Well, obviously this model is too general (but for this example I hope this makes no difference).

Now the classifier is tested on some samples:

A   B   Output
--------------
1   0   red
0   1   blue
1   1   red

Here is the problem. The classifier will just output some "random" label for the third sample, depending on the training. If this oversimplified classifier would have looked at label B, it would outputted blue.

From other knowledge (e.g. a Gold-Standard) we can see that the third sample is actually neither red or blue but our magenta class. The classifier is just too general (?) or not well-trained (?). Is this a Sampling Error, because the third class was not identified as such during training (because the data was not available in the training set)?

How is this problem called exactly? I'm searching for the term but can not find one... What could be a countermeasure? Of course, one could add samples of class magenta into the training set. Are there other possibilities?

Answer 1

When you train a classifier $f$ using a set of $m$ training classes $C=\{1,2,...,m\}$, it is possible that your classifier will encounter some class $c\notin C$ after it has already been trained. For instance, in object recognition, it may not be possible to obtain a training example for every type of object your sensor will encounter in practice. As you pointed out, if $f$ is not trained to recognize $c$, then it's impossible to make a correct decision! The classifier has been trained under the closed set assumption: the only classes we will encounter in the field are in $C$.

Depending on the problem at hand, this can occur quite frequently, and classification errors can really pile up. Researchers have been trying to deal with this problem since the 1970s or earlier under a number of names. In the past, these approaches were usually called something like "classification with reject option," but lately the term open set recognition has been popping up.

Whatever the case, many of these approaches boil down to picking some score threshold $\tau$ below which we forgo a decision on the input and simply call it "unknown." They typically deal with rejection at the classifier output, rather than the feature level (the decision is based on $f(x)$ rather than $x$).

In your example, we might build a classifier that returns probabilities that the example is red or blue:

$$ \begin{split} p_1 &= f(y=\texttt{red} | x)\\ p_2 &= f(y=\texttt{blue} | x) \end{split} $$

Then, we can define a decision function

$$ \delta_\tau(p_1,p_2) = \begin{cases} \operatorname{argmax}(p_1,p_2) & \text{if } p_1>\tau \text{ or } p_2>\tau\\ \text{unknown} & \text{otherwise} \end{cases} $$ or some incarnation thereof. In that case, the output would hopefully look something like

A   B   Output
--------------
1   0   red
0   1   blue
1   1   unknown

Now, this doesn't directly address the problem of getting the magenta label into the classifier. In fact, this is an open topic of research—check into open world recognition.