# Technical Report MSC-2006-30

 TR#: MSC-2006-30 Class: MSC Title: On Exact Learning Halfspaces with Random Consistent Hypothesis Oracle Authors: Ehab Wattad Supervisors: Nader Bshouty PDF MSC-2006-30.pdf Abstract: We investigate several learning strategies for exact learning halfspaces over the domain $\{0,1,\ldots,n-1\}^d$ 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 $\tilde O(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 $\Omega(\sqrt{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^{\Theta(d)}\log n$. We then give a tight lower bound $2^{\Omega(d)}+\Omega(d^2\log n)$. This proves that this learning algorithm does not run in polynomial time for $d=\omega(\log\log n)$. Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2006/MSC/MSC-2006-30), rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.