Relation between number of classes, their separability and classification difficulty

Question

Intuitively, it seems that a classification problem with more classes is "harder" than the same problem with fewer classes. However, this also seems to depends on the separability of the classes by the model in feature space.

Despite my efforts, I haven't food a theoretical reference expanding on that relationship: I only found some empirical results on specific datasets stating that the problem got harder when adding more classes. Is there an existing theoretical reference specifically on that topic? If not, can we derive a relationship between the number of classes, their separability and the difficulty of a classification problem?

Answer 1

I think the best you will do is to recognize that there are more parameters (or relationships of some kind) to recognize as the number of classes increases. However, this is a rather weak relationship. For instance, it’s probably hard to distinguish $1000$ wolves from $1000$ dogs, but if you add $1000$ alligators into the problem, those should be relatively easy to distinguish from the others.