|
Abstract : |
This paper addresses the problem of learning boolean functions in query and mistake-bound models in the presence of irrelevant attributes. In learning a concept, a learner may observe a great many more attributes than those the concept depends upon, and in some sense the presence of extra, irrelevant attributes does not change the underlying concept being learned. Because of this, we are interested not only in learnability of concept classes, but also in whether the classes can be learned by an algorithm that is attribute-efficient in that the dependence of the mistake bound (or number of queries) on the number of irrelevant attributes is low. The results presented here apply to projection and embedding-closed (p.e.c.) concept classes. We show that if a p.e.c. class is learnable attribute-efficiently in the mistake-bound model, then it is learnable in the infinite-attribute mistake bound model as well. We show in addition how to convert any algorithm that learns a p.e.c. class in the mistake-bound model with membership queries into an algorithm that learns the class attribute-efficiently in that model, or even in the infinite attribute version. In the membership query only model, we show that learnability does not always imply attribute-efficient learnability for deterministic, |
