Degrees of Inferability
Abstract
Most theories of learning consider inferring a function f from either (1) observations about f or, (2) questions about f. We consider a scenario whereby the learner observes fand asks queries to some set A. EX[A] is the set of concept classes EX-learnable by an inductive inference machine with oracle A. A and F are EX-equivalent if EX[A] = EX[B]. The equivalence classes induced are the degrees of inferability. We prove several results about these degrees: (1) There are an uncountable number of degrees. (2) For A r.e., REC e BC[A] iff O'' ≤T A´, and there is evidence this holds for all sets A. (3) For A, B r.e., A ≡T B iff EX[A] = EX[B]. (4) There exists A, B low2 r.e., A|RB, EX[A] = EX[B]. (hence (3) is optimal).
Cite
Text
Cholak et al. "Degrees of Inferability." Annual Conference on Computational Learning Theory, 1992. doi:10.1145/130385.130406Markdown
[Cholak et al. "Degrees of Inferability." Annual Conference on Computational Learning Theory, 1992.](https://mlanthology.org/colt/1992/cholak1992colt-degrees/) doi:10.1145/130385.130406BibTeX
@inproceedings{cholak1992colt-degrees,
title = {{Degrees of Inferability}},
author = {Cholak, Peter and Kinber, Efim B. and Downey, Rodney G. and Kummer, Martin and Fortnow, Lance and Kurtz, Stuart A. and Gasarch, William I. and Slaman, Theodore A.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1992},
pages = {180-192},
doi = {10.1145/130385.130406},
url = {https://mlanthology.org/colt/1992/cholak1992colt-degrees/}
}