Exact Learning Composed Classes with a Small Number of Mistakes

@incollection{citeulike:2324810, 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.}, author = {Bshouty, Nader and Mazzawi, Hanna }, citeulike-article-id = {2324810}, doi = {10.1007/11776420\_17}, journal = {Learning Theory}, keywords = {learning-theory, phase-learning}, pages = {199--213}, posted-at = {2008-02-03 04:37:25}, priority = {3}, title = {Exact Learning Composed Classes with a Small Number of Mistakes}, url = {http://dx.doi.org/10.1007/11776420\_17}, year = {2006} }

TY - CHAP ID - citeulike:2324810 L3 - citeulike-article-id:2324810 TI - Exact Learning Composed Classes with a Small Number of Mistakes JF - Learning Theory SP - 199 EP - 213 N2 - 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. KW - learning-theory KW - phase-learning AU - Bshouty, Nader AU - Mazzawi, Hanna PY - 2006/// UR - http://dx.doi.org/10.1007/11776420_17 ER -