ML Anthology

On Exact Learning Halfspaces with Random Consistent Hypothesis Oracle

Nader H. Bshouty, Ehab Wattad
ALT 2006 pp. 48-62
doi:10.1007/11894841_8 /alt/2006/bshouty2006alt-exact-a/

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.

PDF ALT Semantic Scholar

Cite

Text

Bshouty and Wattad. "On Exact Learning Halfspaces with Random Consistent Hypothesis Oracle." International Conference on Algorithmic Learning Theory, 2006. doi:10.1007/11894841_8

Markdown

[Bshouty and Wattad. "On Exact Learning Halfspaces with Random Consistent Hypothesis Oracle." International Conference on Algorithmic Learning Theory, 2006.](https://mlanthology.org/alt/2006/bshouty2006alt-exact-a/) doi:10.1007/11894841_8

BibTeX

@inproceedings{bshouty2006alt-exact-a,
  title     = {{On Exact Learning Halfspaces with Random Consistent Hypothesis Oracle}},
  author    = {Bshouty, Nader H. and Wattad, Ehab},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {2006},
  pages     = {48-62},
  doi       = {10.1007/11894841_8},
  url       = {https://mlanthology.org/alt/2006/bshouty2006alt-exact-a/}
}