Complexity Dimensions and Learnability
Abstract
In a discussion of the Vapnik Chervonenkis (VC) dimension ([7]), which is closely related to the learnability of concept classes in Valiant's PAC-model ([6]), we will give an algorithm to compute it. Furthermore, we will take Natarajan's equivalent dimension for well-ordered classes into a more general scheme, by showing that these well-ordered classes happen to satisfy some general condition, which makes it possible to construct for a class a number of equivalent dimensions. We will give this condition, as well as a relatively efficient algorithm for the calculation of one such dimension for well-ordered classes.
Cite
Text
Nienhuys-Cheng and Polman. "Complexity Dimensions and Learnability." European Conference on Machine Learning, 1993. doi:10.1007/3-540-56602-3_149Markdown
[Nienhuys-Cheng and Polman. "Complexity Dimensions and Learnability." European Conference on Machine Learning, 1993.](https://mlanthology.org/ecmlpkdd/1993/nienhuyscheng1993ecml-complexity/) doi:10.1007/3-540-56602-3_149BibTeX
@inproceedings{nienhuyscheng1993ecml-complexity,
title = {{Complexity Dimensions and Learnability}},
author = {Nienhuys-Cheng, Shan-Hwei and Polman, Mark},
booktitle = {European Conference on Machine Learning},
year = {1993},
pages = {348-353},
doi = {10.1007/3-540-56602-3_149},
url = {https://mlanthology.org/ecmlpkdd/1993/nienhuyscheng1993ecml-complexity/}
}