Learning via queries
- 1 July 1992
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 39 (3) , 649-674
- https://doi.org/10.1145/146637.146670
Abstract
Traditional work in inductive inference has been to model a learner receiving data about a function f and trying to learn the function. The data is usually just the values f (0), f (1),…. The scenario is modeled so that the learner is also allowed to ask questions about the data (e.g., (∀ χ) [χ> 17 → f ( χ ) = 0]?). An important parameter is the language that the lerner may use to formulate queries. We show that for most languages a learner can learn more by asking questions than by passively receiving data. Mathematical tools used include the solution to Hilbert's tenth problem, the decidability of Presuburger arithmetic, and ω-automata.Keywords
This publication has 23 references indexed in Scilit:
- On the complexity of inductive inferenceInformation and Control, 1986
- A theory of the learnableCommunications of the ACM, 1984
- Inductive Inference: Theory and MethodsACM Computing Surveys, 1983
- Comparison of identification criteria for machine inductive inferenceTheoretical Computer Science, 1983
- The Power of Pluralism for Automatic Program SynthesisJournal of the ACM, 1982
- Extended universal theories of the integersAlgebra and Logic, 1977
- Theories of automata on ω-tapes: A simplified approachJournal of Computer and System Sciences, 1974
- Language identification in the limitInformation and Control, 1967
- The Decision Problem for Exponential Diophantine EquationsAnnals of Mathematics, 1961
- Gödel numberings of partial recursive functionsThe Journal of Symbolic Logic, 1958