Learning via Queries

Gasarch, William I.; Smith, Carl H.

doi:10.1109/sfcs.1988.21931

Learning via Queries

William I. Gasarch, Carl H. Smith

COLT 1988 pp. 227-241

doi:10.1109/sfcs.1988.21931 /colt/1988/gasarch1988colt-learning/

Abstract

The power of various query languages is compared along two dimensions, namely the inherent power of the language and the number of alternations of quantizers. Learning by asking questions is compared to learning by passively reading data. It is found that the extent of what can be learned by queries is largely dependent on the language used by the inference mechanism to formulate questions to ask of its trainer. It is proved that inference machines that are allowed to ask first-order questions with plus and times can be used to solve the halting problem and therefore can learn all the recursive functions. Learning languages are also considered.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>

COLT Semantic Scholar

Cite

Text

Gasarch and Smith. "Learning via Queries." Annual Conference on Computational Learning Theory, 1988. doi:10.1109/sfcs.1988.21931

Markdown

[Gasarch and Smith. "Learning via Queries." Annual Conference on Computational Learning Theory, 1988.](https://mlanthology.org/colt/1988/gasarch1988colt-learning/) doi:10.1109/sfcs.1988.21931

BibTeX

@inproceedings{gasarch1988colt-learning,
  title     = {{Learning via Queries}},
  author    = {Gasarch, William I. and Smith, Carl H.},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {1988},
  pages     = {227-241},
  doi       = {10.1109/sfcs.1988.21931},
  url       = {https://mlanthology.org/colt/1988/gasarch1988colt-learning/}
}