Fetching the paper…

Reading the bibliography…

2022

Upper bounds on the Natarajan dimensions of some function classes

Jin, Ying

Original
PDF
Post on X

Understand

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.

Upper bounds on the Natarajan dimensions of some function classes · Around

Built on

On learning sets and functions
Natarajan, B. K. (1989) · 1989
Earlier work this paper cites.
Characterizations of learnability for classes of { \{ O,…, n } \} -valued functions
Ben-David, S., Cesa-Bianchi, N., and Long, P. M. (1992) · 1992
Earlier work this paper cites.
Bounding the vapnik-chervonenkis dimension of concept classes parameterized by real numbers
Goldberg, P. W. and Jerrum, M. R. (1995) · 1995
Earlier work this paper cites.
Vc dimension of neural networks
Sontag, E. D. et al. (1998) · 1998
Earlier work this paper cites.

Similar

Sample complexity of classifiers taking values in r q, application to multi-class svms
Guermeur, Y. (2010) · 2010
Cited alongside, same era.
Multiclass learnability and the erm principle
Daniely, A., Sabato, S., Ben-David, S., and Shalev-Shwartz, S. (2011) · 2011
Cited alongside, same era.
Multiclass learning approaches: A theoretical comparison with implications
Daniely, A., Sabato, S., and Shwartz, S. (2012) · 2012
Cited alongside, same era.

Then

Understanding machine learning: From theory to algorithms
Shalev-Shwartz, S. and Ben-David, S. (2014) · 2014
Later among the works it cites.
On the uniform convergence of relative frequencies of events to their probabilities
Vapnik, V. N. and Chervonenkis, A. Y. (2015) · 2015
Later among the works it cites.
Generalization properties of decision trees on real-valued and categorical features
Original
Leboeuf, J.-S., LeBlanc, F., and Marchand, M. (2022) · 2022
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…