Upper bounds on the Natarajan dimensions of some function classes
This work addresses a foundational theoretical problem in machine learning for researchers studying multi-class classification, but it appears incremental as it extends existing VC dimension concepts to multi-class settings.
The paper tackles the problem of characterizing multi-class PAC learnability by establishing upper bounds on Natarajan dimensions for function classes like multi-class decision trees, random forests, and neural networks with specific activations, providing theoretical limits without concrete numerical results.
The Natarajan dimension is a fundamental tool for characterizing multi-class PAC learnability, generalizing the Vapnik-Chervonenkis (VC) dimension from binary to multi-class classification problems. This work establishes upper bounds on Natarajan dimensions for certain function classes, including (i) multi-class decision tree and random forests, and (ii) multi-class neural networks with binary, linear and ReLU activations. These results may be relevant for describing the performance of certain multi-class learning algorithms.