Training a binary classifier acting on n-class data

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?

• You turned a binary classifier into a classifier that has 3 possible outputs, how did you change the algorithm? – dimpol Nov 10 '16 at 11:31
• @dimpol No, the classifier will obviously have two outputs, either red or blue. The problem is, that the data I'm testing on has actually three classes, where the third (previously unknown) class magenta is exactly a mix of both classes the classifier was trained with. So if the classifier tries to classify such a sample, it will output either red or blue, depending where the threshold is set. – reox Nov 10 '16 at 17:10
• Then you need a way to determine what inputs correspond to "magenta". If that is obvious, you can manually identify "magenta" inputs and put the rest through your original algorithm. If it isn't obvious and you want to train a model to identify "magenta", you indeed need to add "magenta" training examples. I don't think there is a term for this problem or a special solution. – dimpol Nov 10 '16 at 17:17
• @dimpol I added an example in the question. Yes, adding such samples to the training set and learing the classifier three classes would help. For the term: Is it maybe some kind of sampling error? I think there should be a term for it but I really can not find something to search for... – reox Nov 10 '16 at 17:25

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.