Some Problems of Learning with an Oracle

Kinber, Efim B.

doi:10.1016/B978-1-55860-146-8.50017-5

Some Problems of Learning with an Oracle

Efim B. Kinber

COLT 1990 pp. 178-186

doi:10.1016/B978-1-55860-146-8.50017-5 /colt/1990/kinber1990colt-some/

Abstract

ABSTRACT In this paper we investigate inductive inference when IIM's (Inductive Inference Machines) have access to an oracle A[1,2]. In our case IIM's are restricted to make a finite number of queries to A. If the number of queries to a specific oracle A is bounded then increasing the number of queries to A helps: we obtain the strict hierarchy of inferable classes with respect to a number of queries to A. Additionally, there are sets inferable via at most 2m queries to some oracle B which are not inferable via at most m queries regardless to an oracle. There are also oracles A and B such that A ≤ TB, but some sets inferable via at most one query to B are not inferable via at most m queries to A. Following [1], we introduce the notion of a degree of inferability (when the number of queries is bounded) and prove the existence of incomparable degrees. Our results solve several problems posed in [1].

COLT Semantic Scholar

Cite

Text

Kinber. "Some Problems of Learning with an Oracle." Annual Conference on Computational Learning Theory, 1990. doi:10.1016/B978-1-55860-146-8.50017-5

Markdown

[Kinber. "Some Problems of Learning with an Oracle." Annual Conference on Computational Learning Theory, 1990.](https://mlanthology.org/colt/1990/kinber1990colt-some/) doi:10.1016/B978-1-55860-146-8.50017-5

BibTeX

@inproceedings{kinber1990colt-some,
  title     = {{Some Problems of Learning with an Oracle}},
  author    = {Kinber, Efim B.},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {1990},
  pages     = {178-186},
  doi       = {10.1016/B978-1-55860-146-8.50017-5},
  url       = {https://mlanthology.org/colt/1990/kinber1990colt-some/}
}