M.Sc Student | Mazzawi Hanna |
---|---|

Subject | Learning Composed Classes with a Small Number of Mistakes |

Department | Department of Computer Science |

Supervisor | Professor Nader Bshouty |

Full Thesis text |

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.