3
$\begingroup$

I have a multiclass classification problem with more than 1,000 classes. I've trained several classifiers (SVM, kNN, Random forests, etc) for 10, 100, 500 and 1000 of the classes to estimate the tendency of classifier's accuracy as the number of classes increases.

I have around 100 samples per each class and do 10-fold cross-validation. What I observe is that the accuracy (# correct classified samples divided by total tested samples) saturates as I increase the number of classes ( 100% accuracy for 10 classes, 87% for 50 classes, 75% for 100 classes, 67% accuracy for 500 classes and 63% for 1,000 classes...).

I'm trying to understand this phenomenon because I was expecting the accuracy to steadily drop to zero. What I had in my mind is that as the number of classes increases, it is more likely to find two classes that are similar to each other and, thus, have more errors.

Can anybody provide an insight on what is happening?

Improve this question
$\endgroup$
4
  • $\begingroup$ What do you mean by increasing number of classes? Are you selecting sub sets of the data with only 10, 100 classes or are you merging the classes? $\endgroup$
    – Hooman
    Apr 28, 2017 at 16:39
  • $\begingroup$ I am selecting subsets of the data. I am not merging the classes. Sorry for the confusion. $\endgroup$
    – synack
    Apr 28, 2017 at 22:10
  • $\begingroup$ Then I think based on the explanations that I added the error should not change that much. $\endgroup$
    – Hooman
    Apr 28, 2017 at 23:34
  • $\begingroup$ I cannot believe there is no scientific article in machine learning that tackle this question at all $\endgroup$
    – synack
    May 3, 2017 at 11:11

2 Answers 2

Reset to default
2
$\begingroup$

It is not clear what you mean by increasing the number of classes. It can be interpreted in two ways:

1- More data is added where they belong to new classes. This is shown in the following figure where we start with 2 classes and add two more class of data each time.

enter image description here

2- The target variable is broken into more values. This is shown in the following figure where each label for target is broken to more labels.

enter image description here

Consider that most of incorrectly classified data points are close to the lines that separate the classes from each other. The exact picture would be a bit different when you use a one versus all encoding for the multi class classifiers, but the same concept holds. In both cases you are increasing the number of lines. So the total area around the lines increases. In the first case however you are also covering a larger space. So it is likely that the ratio of the area around the lines to the total area remains constant. In the second case however you are passing more lines through the same space. So indeed it is expected that the error rate increase. In the second case however since you have less data for each class then you are more likely to overfit and get a result that looks better on your training data.

Consider that in some cases classifying in a smaller number of classes might even seems more difficult. For example in the following figure the two class classifier seems more comlex than 4 class classifier (although both will probably have the same accuracy).

enter image description here

Improve this answer
$\endgroup$
4
  • $\begingroup$ Your answer makes sense. I need to think more about it. Does this explanation hold for other models other than svm (that are not based on support vectors to separate the data, eg probabilistic/generative)? Can you point me to a paper that formalizes the concept of "area around the line"? $\endgroup$
    – synack
    Apr 29, 2017 at 6:45
  • $\begingroup$ I cannot point to any reference. But I think that's what happening. I far as I know for other classifiers likes neural net and decision trees also you can draw the decision boundary. For what I have seem most of the errors happen as boundary. For classes generated from simple distributions (e.g. multiple Gaussian distributions with different means) you can derive the decision boundary and calculate the error rate. $\endgroup$
    – Hooman
    May 1, 2017 at 8:11
  • $\begingroup$ This is is also done in the determining symbol error rate for multi symbol digital communication, where the error rate is calculated based in terms of means and variance of distributions. $\endgroup$
    – Hooman
    May 1, 2017 at 8:12
  • $\begingroup$ I'm still not convinced by the answer, though. The more I think about it the more I see it like this: as more classes are considered, more populated the classification space is and thus the classifier is more likely to make an error... $\endgroup$
    – synack
    May 3, 2017 at 11:07
0
$\begingroup$

Your model is likely severely overfit. In a classification error problem, a misclassification error rate is likely to stabilize at a certain number akin to random guessing. Think about it. Suppose you have two classes. Which is worse? An error rate of 0% or an error rate of 50%? 0% is perfect classification... you just have the classes backwards. 50% is the worst - it is random guessing.

Improve this answer
$\endgroup$
3
  • $\begingroup$ If you get 50% error rate for two classes, your classifier is random guessing. My classifiers are far away from random guessing: 67% accuracy for 500 classes and 63% for 1,000 classes. I don't understand your argument on why the classifier is overfit. $\endgroup$
    – synack
    Apr 28, 2017 at 14:02
  • $\begingroup$ I presume random guessing would just estimate marginal class probabilities from the training set, ignoring features. But these do not need to be uniform. $\endgroup$
    – GeoMatt22
    Apr 28, 2017 at 19:58
  • 1
    $\begingroup$ @GeoMatt22, good point. As I said in the question, I have the same number of training instances for each class, so in this case it would indeed be uniform. $\endgroup$
    – synack
    Apr 29, 2017 at 6:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.