M.Sc Student | Wattad Ehab |
---|---|

Subject | On Exact Learning Halfspaces with Random Consistent Hypothesis Oracle |

Department | Department of Computer Science |

Supervisor | Professor Nader Bshouty |

Full Thesis text |

We investigate several
learning strategies for exact learning halfspaces over the domain *{0, 1, …,
n - 1} ^{2}* and study the query complexity and the time complexity
of exact learning using those strategies. Our strategies are based on the
RCH-oracle that returns a random consistent hypothesis with the counterexamples
received from the equivalence query oracle.

We first give a new polynomial time learning algorithm that uses the RCH-oracle for learning halfspaces from majority of halfspaces. We show that the query complexity of this algorithm is less (by some constant factor) than the best known algorithm that learns halfspaces from halfspaces.

We then study the query
complexity of exact learning when limited number of calls to the RCH-oracle is
allowed in each trial, i.e., before each equivalence query. We first show that
an *Õ(d)* calls to the RCH-oracle in each trial is sufficient for
learning in polynomial number of queries. We then show that any “reasonable” strategy
must use the RCH-oracle at least *Ω(√d)* times in each trial.

Then we show that if only one
call to RCH-oracle is allowed in each trial then the query complexity of the learning
algorithm is *2 ^{θ(d)}log n*. We then give a tight lower bound