Exact Learning Composed Classes with a Small Number of Mistakes
Abstract
The Composition Lemma is one of the strongest tools for learning complex classes. It shows that if a class is learnable then composing the class with a class of polynomial number of concepts gives a learnable class. In this paper we extend the Composition Lemma as follows: we show that composing an attribute efficient learnable class with a learnable class with polynomial shatter coefficient gives a learnable class. This result extends many results in the literature and gives polynomial learning algorithms for new classes.
Cite
Text
Bshouty and Mazzawi. "Exact Learning Composed Classes with a Small Number of Mistakes." Annual Conference on Computational Learning Theory, 2006. doi:10.1007/11776420_17Markdown
[Bshouty and Mazzawi. "Exact Learning Composed Classes with a Small Number of Mistakes." Annual Conference on Computational Learning Theory, 2006.](https://mlanthology.org/colt/2006/bshouty2006colt-exact/) doi:10.1007/11776420_17BibTeX
@inproceedings{bshouty2006colt-exact,
title = {{Exact Learning Composed Classes with a Small Number of Mistakes}},
author = {Bshouty, Nader H. and Mazzawi, Hanna},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2006},
pages = {199-213},
doi = {10.1007/11776420_17},
url = {https://mlanthology.org/colt/2006/bshouty2006colt-exact/}
}