Complexity dimensions and learnability
A stochastic model of learning from examples has been introduced by Valiant . This PAC-learning model (PAC = probably approximately correct) reflects differences in complexity of concept classes, i.e. very complex classes are not efficiently PAC-learnable. Blumer et al.  found, that efficient PAC-learnability depends on the size of the Vapnik Chervonenkis dimension [Vapnik & Chervonenkis, 1971] of a class. We will first discuss this dimension and give an algorithm to compute it, in order to provide the reader with the intuitive idea behind it. Natarajan  defines a new, equivalent dimension is defined for well-ordered classes. These well-ordered classes happen to satisfy a general condition, that is sufficient for the possible construction of a number of equivalent dimensions. We will give this condition, as well as a generalized notion of an equivalent dimension. Also, a relatively efficient algorithm for the calculation of one such dimension for well-ordered classes is given.
|Organisation||Erasmus School of Economics|
Nienhuys-Cheng, S-H, & Polman, M. (1992). Complexity dimensions and learnability. Retrieved from http://hdl.handle.net/1765/1483