On Exact Learning Halfspaces with Random Consistent Hypothesis Oracle Authors: Nader H. Bshouty and Ehab Wattad Source: Algorithmic Learning Theory, 17th International Conference, ALT 2006, Barcelona, October 2006, Proceedings, (José L. Balcázar, Phil Long and Frank Stephan, Eds.), Lecture Notes in Artificial Intelligence 4264, pp. 48 - 62, Springer 2006. Abstract. We study exact learning of halfspaces from equivalence queries. The algorithm uses an oracle RCH that returns a random consistent hypothesis to the counterexamples received from the equivalence query oracle. We use the RCH oracle to give a new polynomial time algorithm for exact learning halfspaces from majority of halfspaces and show that its query complexity is less (by some constant factor) than the best known algorithm that learns halfspaces from halfspaces. ©Copyright 2006, Springer