טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentMazzawi Hanna
SubjectLearning Composed Classes with a Small Number of Mistakes
DepartmentDepartment of Computer Science
Supervisor Professor Nader Bshouty
Full Thesis textFull thesis text - English Version


Abstract

Computational Learning Theory is a research field devoted to studying the design and analysis of learning algorithms and learnability of concept classes. In this field enormous effort has been made over the last few decades in order to classify classes of concepts into those that are learnable and those that are not learnable, provide new techniques for learning concept classes and study their learning time and query complexity. Our research studies the learnability of composed classes in the Exact Learning Model.


In the exact learning model, we have a learner (learning algorithm) and a teacher (oracle). The teacher holds a target function from a class of functions (unlike the target function the class of functions is known to the learner). The learner must identify the target function by asking queries. The learner may ask equivalence queries, that is, he/she may provide the teacher a hypothesis, the teacher answers ``Yes'' if the learner's hypothesis is equivalent to the target function and provide a counterexample otherwise. The learning process ends when the learner outputs a hypothesis that is equivalent to the target function.


One of the strongest tools for learning complex classes is the Composition Lemma. 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 research 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.