In classification, how does the number of classes affect the model size and amount of data needed to train?

Question

When solving a classification problem with neural nets, be it text or images, how does the number of classes affect the model size and amount of data needed to train?

Are there any soft or hard limitations where the number of outputs starts to stall learning?

Do you know about any analysis of how the number of classes scales the model?

Does the optimal size increase proportionally with the number of outputs? Does it increase at all? If it does increase, is the relationship linear or exponential?

Answer 1

The most obvious way more classes increase the network size is the output layer, but I don't believe there is a rule of thumb for the size of the entire network.

As I understand it, there is no clear answer to how big a network needs to be to achieve a certain performance with regard to the number of layers compared to the number of classes. This is a very active research field, just as an example compare the size of EfficientNet to other State of the art models when it was introduced and you can see the size difference.

Regarding the data needed, in The Deep Learning Book (which is a few years old now) they state as a general that with the models available at that time, you needed ~5000 examples per label for acceptable performance, while to exceed human performance (their words) you would need about 10 million labeled examples.

Answer 2

Model/network design has multiple guidelines, a basic one is: The solving capacity of the network should be larger than the possibility space of the problem to be solved.

Solving capacity (learning capacity) of a network (dense usually) can be calculated as the product of number of neurons in all layers, for example:

Input shape: 10 values
Network shape: [layer1 30 units, layer2 20 units, output 1 unit] should have learning capacity of $30 \times 20 \times 1 = 600$, it learn roughly max 600 different inputs (each input holds 10 values).

Another consideration, the separation lines, even when the inputs of the problem to be learnt are unlimited, but the 2 classes (just example) are always separated on 2 sides of a line without mixing up, just a single neuron can solve the problem.

One neuron can make 1 separation line, 1 layer makes a poly-line with segments are by the neurons in that layer, another layer makes another poly-line.

Thus, more classes, more separations to be done, and more classes would mean the input variety is large, so surely training data are a lot and model size needs to be large.