| TR#: | MSC-2006-30 |
| Class: | MSC |
| Title: | On Exact Learning Halfspaces with Random Consistent Hypothesis Oracle |
| Authors: | Ehab Wattad |
| Supervisors: | Nader Bshouty |
| 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 <<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)$.
|
| 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.
To the list of the MSC technical reports of 2006
To the main CS technical reports page