ML Anthology

The Consistency Dimension and Distribution-Dependent Learning from Queries (Extended Abstract)

José L. Balcázar, Jorge Castro, David Guijarro, Hans Ulrich Simon
ALT 1999 pp. 77-92
doi:10.1007/3-540-46769-6_7 /alt/1999/balcazar1999alt-consistency/

Abstract

We prove a new combinatorial characterization of polynomial learnability from equivalence queries, and state some of its consequences relating the learnability of a class with the learnability via equivalence and membership queries of its subclasses obtained by restricting the instance space. Then we propose and study two models of query learning in which there is a probability distribution on the instance space, both as an application of the tools developed from the combinatorial characterization and as models of independent interest.

PDF ALT Semantic Scholar

Cite

Text

Balcázar et al. "The Consistency Dimension and Distribution-Dependent Learning from Queries (Extended Abstract)." International Conference on Algorithmic Learning Theory, 1999. doi:10.1007/3-540-46769-6_7

Markdown

[Balcázar et al. "The Consistency Dimension and Distribution-Dependent Learning from Queries (Extended Abstract)." International Conference on Algorithmic Learning Theory, 1999.](https://mlanthology.org/alt/1999/balcazar1999alt-consistency/) doi:10.1007/3-540-46769-6_7

BibTeX

@inproceedings{balcazar1999alt-consistency,
  title     = {{The Consistency Dimension and Distribution-Dependent Learning from Queries (Extended Abstract)}},
  author    = {Balcázar, José L. and Castro, Jorge and Guijarro, David and Simon, Hans Ulrich},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {1999},
  pages     = {77-92},
  doi       = {10.1007/3-540-46769-6_7},
  url       = {https://mlanthology.org/alt/1999/balcazar1999alt-consistency/}
}