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 f and 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 &egr; BC[A] iff &0slash;&huml; ≤T A´, and there is evidence this holds for all sets A. (3) For A, B r.e., A ≡T Biff EX[A] = EX[B]. (4) There exists A, B low2 r.e., A|RB, EX[A] = EX[B]. (hence (3) is optimal).

REFERENCES

• AB91: Lenny Adleman and Manuel Blum. Inductive inference and unsolvability. Journal of Symbolic Logic, 56(3):891-900, September 1991.
• Ang88: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• CS83: John Case and Carl Smith. Comparison of identification criteria for machine inductive inference. Theoretical Computer Science, 25:193-220, 1983.
• DJ87: Rodney G. Downey and Carl G. Jockusch. T- degrees, jump classes, and strong reducibilities. Transactions of the AMS, 301:103-120, 1987.
• FGK+: Lance Fortnow, William Gasarch, Martin Kummer, Stuart Kurtz, Theodore Slaman, and Robert Solovay. Extremes in the degrees of inferability.
• Gol67: E Mark Gold. Language identification in the limit. Information and Computation, 10(10):447-474, 1967.
• GP89: William I. Gasarch , Mark G. Pleszkoch, Learning via queries to an oracle, Proceedings of the second annual workshop on Computational learning theory, p.214-229, December 1989, Santa Cruz, California, United States
• GS: William I. Gasarch , Carl H. Smith, Learning via queries, Journal of the ACM (JACM), v.39 n.3, p.649-674, July 1992 [doi>10.1145/146637.146670]
• Joc72: C.G. Jockusch, Jr. Degrees in which recursive sets are uniformily recursive. Canadian Journal of Mathematics, 24:1092-1099, 1972.
• Ler83: Manuel Lerman. Degrees of Unsolvabitity. Perspectives in Mathematical Logic. Springer- Verlag, Berlin, 1983.
• Soa87: Robert I. Soare, Recursively enumerable sets and degrees, Springer-Verlag New York, Inc., New York, NY, 1987
• SS91: Theodore A. Slaman , Robert Solovay, When oracles do not help, Proceedings of the fourth annual workshop on Computational learning theory, p.379-383, August 05-07, 1991, Santa Cruz, California, United States
• Val84: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Theory, Verification