ML Anthology

PExact = Exact Learning

Dmitry Gavinsky, Avi Owshanko
COLT 2004 pp. 200-209
doi:10.1007/978-3-540-27819-1_14 /colt/2004/gavinsky2004colt-pexact/

Abstract

The Probably Exact model (PExact) is a relaxation of the Exact model, introduced in by Bshouty. In this paper, we show that the PExact model is equivalent to the Exact model. We also show that in the Exact model, the adversary (oracle) gains no additional power from knowing the learners’ coin tosses a-priory.

PDF COLT Semantic Scholar

Cite

Text

Gavinsky and Owshanko. "PExact = Exact Learning." Annual Conference on Computational Learning Theory, 2004. doi:10.1007/978-3-540-27819-1_14

Markdown

[Gavinsky and Owshanko. "PExact = Exact Learning." Annual Conference on Computational Learning Theory, 2004.](https://mlanthology.org/colt/2004/gavinsky2004colt-pexact/) doi:10.1007/978-3-540-27819-1_14

BibTeX

@inproceedings{gavinsky2004colt-pexact,
  title     = {{PExact = Exact Learning}},
  author    = {Gavinsky, Dmitry and Owshanko, Avi},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {2004},
  pages     = {200-209},
  doi       = {10.1007/978-3-540-27819-1_14},
  url       = {https://mlanthology.org/colt/2004/gavinsky2004colt-pexact/}
}