Approximate Testing and Learnability
Abstract
A model for approximate testing of concepts, which relates to the PAC model of learning, has been developed. In this model an approximate testing algorithm produces a finite set of examples that distinguishes one concept from others that differ from it by more than a given error bound. This model corresponds closely to the helpful teacher learning model. In this paper we examine properties of a concept class that make it testable or untestable. We define a new measure that is a dual to the VC-dimension, called the testing dimension of a concept class, and show how it yields untestability results for certain concept classes.
Cite
Text
Romanik. "Approximate Testing and Learnability." Annual Conference on Computational Learning Theory, 1992. doi:10.1145/130385.130422Markdown
[Romanik. "Approximate Testing and Learnability." Annual Conference on Computational Learning Theory, 1992.](https://mlanthology.org/colt/1992/romanik1992colt-approximate/) doi:10.1145/130385.130422BibTeX
@inproceedings{romanik1992colt-approximate,
title = {{Approximate Testing and Learnability}},
author = {Romanik, Kathleen},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1992},
pages = {327-332},
doi = {10.1145/130385.130422},
url = {https://mlanthology.org/colt/1992/romanik1992colt-approximate/}
}