Multi-class classification with growing number of classes - question

Question

I have a multi-class classification problem where the algorithm should detect (and later on classify) new classes.

An example for such a task could be classifying if an image shows a dog or a cat. Furthermore, the model should be able to recognize that a goose doesn't fit into one of these two categories, thus create a new class.

Specific Questions:

• How can the model detect new classes?

  • Some unsupervised clustering algorithm
  • When all classes are predicted by a value beyond a certain threshold?

• Is there a (proven) model, which can handle a growing number of classes to classify - without expensive retraining of all the other classes?

  • one vs all?
  • one-class?
  • something completely different?

I greatly appreciate every form of help and experiences you had with such a problem. References to papers or tutorials would be great too. Thank you in advance.

Here are two links where similar questions were asked, but (at least for me) not fully answered.

Stackexchange: Streaming multi-class classification

Stackexchange multi-class classification word2vec

Stackoverflow multiclass classification growing number of classes

Answer 1

This is not the only way, and it may not work for all problems, but one solution would be to compare the performance of a range of class numbers (the current number and one more, or the current number and one either side, or two either side - the number of classes you explore each update depends on how much computational effort you can spare) and use an information criterion (e.g. corrected Akaike's Information Criterion, AICc) to assess goodness-of-fit for each alternative. The model with the lowest AICc is the 'best' fit, although trivial differences (delta-AICc smaller than about 5-10) are not sufficient to conclude that either model is substantially better. You could go one step further and calculate relative likelihoods for different alternatives using Akaike weights.

I'd recommend taking a look at Burnham and Anderson (2002) "Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach".

Answer 2

Rather than new "classes" it should rather be not of the class matching the training data. You would want to actually consider there One-Class Classification (or Single-Class Classification) where the one-class would be defined as both dogs and cats in your training example. This is also called Outlier Detection.

From an implementation perspective, if you wanted to avoid dealing with the weights between the relative classes of Cat and Dog (e.g. if you have many more cat examples than you do dog examples), you could consider doing OCC for each of the Cat and Dog classes, and then you would only reject if both classifiers reject the query point (in other words, with low probability it is a cat and with low probability it is a dog).

An aLternative approach would be "multi-class classification with rejection" - there are many different schemes here and a good number of articles on the subject.