Technical Report MSC-2006-30

Title: On Exact Learning Halfspaces with Random Consistent Hypothesis Oracle
Authors: Ehab Wattad
Supervisors: Nader Bshouty
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 <<HS.pdf>> 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)$.

CopyrightThe 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 (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2006
To the main CS technical reports page

Computer science department, Technion