A General Dimension for Exact Learning
Abstract
We introduce a new combinatorial dimension that gives a good approximation of the number of queries needed to learn in the exact learning model, no matter what set of queries is used. This new dimension generalizes previous dimensions providing upper and lower bounds for all sorts of queries, and not for just example-based queries as in previous works. Our new approach gives also simpler proofs for previous results. We present specific applications of our general dimension for the case of un specified attribute value queries, and show that unspecified attribute value membership and equivalence queries are not more powerful than standard membership and equivalence queries for the problem of learning DNF formulas.
Cite
Text
Balcázar et al. "A General Dimension for Exact Learning." Annual Conference on Computational Learning Theory, 2001. doi:10.1007/3-540-44581-1_23Markdown
[Balcázar et al. "A General Dimension for Exact Learning." Annual Conference on Computational Learning Theory, 2001.](https://mlanthology.org/colt/2001/balcazar2001colt-general/) doi:10.1007/3-540-44581-1_23BibTeX
@inproceedings{balcazar2001colt-general,
title = {{A General Dimension for Exact Learning}},
author = {Balcázar, José L. and Castro, Jorge and Guijarro, David},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2001},
pages = {354-367},
doi = {10.1007/3-540-44581-1_23},
url = {https://mlanthology.org/colt/2001/balcazar2001colt-general/}
}