טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentWattad Ehab
SubjectOn Exact Learning Halfspaces with Random Consistent
Hypothesis Oracle
DepartmentDepartment of Computer Science
Supervisor Professor Nader Bshouty
Full Thesis textFull thesis text - English Version


Abstract

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 2Ω(d) + Ω( d2 log n ). This proves that this learning algorithm does not run in polynomial time for d = ω( log log n ).