Learning via queries

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., ( ∀ &khgr;) [&khgr;> 17 → f(&khgr;) = 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 &ohgr;-automata.

REFERENCES

• 1: ADLEMAN, L., AND BLUM, M. Inductive inference and unsolvability. J. Symb. Logic 56 (1991), 891 - 900.
• 2: ANCLtnN, D. Learning k-term DNF formulas using queries and counter-examples. Tech. Rep. TR-559. Yale Univ., New Haven, Conn., 1987.
• 3: AN~LU~N, D. Learning k-bounded context-free grammars. Tech. Rep. TR-557. Yale Univ., New Haven, Conn., 1987.
• 4: Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
• 5: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• 6: Dana Angluin, Equivalence queries and approximate fingerprints, Proceedings of the second annual workshop on Computational learning theory, p.134-145, December 1989, Santa Cruz, California, United States
• 7: Dana Angluin , Carl H. Smith, Inductive Inference: Theory and Methods, ACM Computing Surveys (CSUR), v.15 n.3, p.237-269, Sept. 1983 [doi>10.1145/356914.356918]
• 8: ANGLUIN, D.. AND SMITH, C. H. Inductive inference. In S. Shapiro, ed., Encyclopedia of Artificial Intelligence. John Wiley and Sons, inc., New York, 1987.
• 9: BERMAN, P., AND ROOS, R. Learning one-counter languages in polynomial time. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science. IEEE, New York. 1987, pp. 61-67.
• 10: BLUM, L., AND BLUM, M. Toward a mathematical theory of inductive inference. Inf. Contr. 28 (1975), 125-155.
• 11: Bucm, J.R. On a decision method in restricted second order arithmetic. In E. Nagel et al., ed., Logic Methodology and Philosophy of Science. Stanford University Press, Stanford, Calif., 1962, pp. 1 - 11.
• 12: Boom, J. R., AND SIEFKES, D. The monadic second order theory of all countable ordinals. In G. Muller and D. Siefkes, eds. Decidable Theories H. Lecture Notes in Mathematics. Vol. 328. Springer-Verlag, New York, 1973.
• 13: CASE, J., AND NGOMANGUELLE, S. Refinements of inducnve inference by popperian machines, Kybernetika, to appear.
• 14: CASE, J, AND SMITH, C. Comparison of ldennfication criteria for machine inductive inference. Theoret Comput. Sci. 25, 2 (t983), 193-220.
• 15: CHANG, C. C., AND KEISLER, H.J. Model theory. North-Holland, New York, 1977
• 16: CHOUEKA, Y Theories of automata on c0-tapes A simplified approach. J. Comput. Syst. Scl. 8 (1974), 117-141.
• 17: Robert P Daley , Carl H Smith, On the complexity of inductive inference, Information and Control, v.69 n.1-3, p.12-40, April/May/June 1986 [doi>10.1016/S0019-9958(86)80042-0]
• 18: DAvis, M. Hilbert's 10th problem is unsolvable. Amer. Math Monthly 80 (1973), 233-269.
• 19: DAVIS, M., PUTNAM, H, AND ROBINSON, J. The decision problem for exponential diophantine equations. Ann. math. 74 (1961), 425-436.
• 20: Rūsiņš Freivalds , C. H. Smith , M. Velauthapillai, Trade-off among parameters affecting inductive inference, Information and Computation, v.82 n.3, p.323-349, Sep. 1989 [doi>10.1016/0890-5401(89)90005-9]
• 21: Efim B. Kinber , William I. Gasarch , Thomas Zeugmann , Mark G. Pleszkoch , Carl H. Smith, Learning via queries with teams and anomilies, Proceedings of the third annual workshop on Computational learning theory, p.327-337, August 06-08, 1990, Rochester, New York, United States
• 22: QASARCH, W., PLESZKOCH, M., AND SOLOVAY, R. Learning via queries with plus and times J. Svmb. Loglc 5 7 (1992), 53-81.
• 23: GOLD, E M. Language identification in the limit Inf. Contr. 10 (1967), 447-474.
• 24: KE4RNS, S., LI, M., AND VALIANT, L. Learning Boolean formulae. J. ACM, to appear
• 25: Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
• 26: Michael Machtey , Paul Young, An Introduction to the General Theory of Algorithms, Elsevier Science Inc., New York, NY, 1978
• 27: MARTJANOV, V. }{. Umversal extended theories of integers. Algebra Log. 16 (1977), 395-404.
• 28: MATIJASEVIC, Y. Enumerable sets are diophantine Doklady Academy Nauk SSSR 191 (1970), 279-282. (Translanon in Sov. Math. Dokl. 11 (1970), 354-357.)
• 29: McNAUGHTON, R. Testing and generating infinite sequences by a finite automaton. Inf. Contr. 9 (1966), 521-530.
• 30: B. K. Natarajan, On learning Boolean functions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.296-304, January 1987, New York, New York, United States [doi>10.1145/28395.28427]
• 31: 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
• 32: Michael Oser Rabin, Automata on Infinite Objects and Church's Problem, American Mathematical Society, Boston, MA, 1972
• 33: ROGERS, H., JR. G6del numberings of partial recursive functions. J. Symb. Logic 23 (1958), 331-341.
• 34: Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
• 35: SAFRa, S. On the complexity of w-automata In Proceedmgs of the 29th S wnposium on the Foundations of Computer Science (White Plains, N.Y.). IEEE, New York, 1988, pp. 314-327.
• 36: SAKAKIBARA, Y. Inferring parsers of context-free languages from structural examples. Fujitsu International Institute for Advanced Study of Social Information Science, Numazu, Japan, 198i.
• 37: SAKAKIBARA, Y. Inductive reference of logic programs based on algebraic semantics. Tech. Rep. 79. Fujitsu International Institute for Advanced Study of Social Informanon Science, Numazu, Japan, 1987.
• 38: Ehud Y. Shapiro, Algorithmic Program DeBugging, MIT Press, Cambridge, MA, 1983
• 39: J. C. Shepherdson, Negation in logic programming, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 40: Carl H. Smith, The Power of Pluralism for Automatic Program Synthesis, Journal of the ACM (JACM), v.29 n.4, p.1144-1165, Oct. 1982 [doi>10.1145/322344.322356]
• 41: Robert I. Soare, Recursively enumerable sets and degrees, Springer-Verlag New York, Inc., New York, NY, 1987
• 42: 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]
• 43: WmHAOEN, R. Inductive inference of recursive functions. In Lecture Notes m Computer Science. Vol. 32 Springer-Verlag, New York, 1974, pp. 462-464.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded); Relations between models; Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction

General Terms:
Theory

Keywords:
learning by example, learning via a teacher, omega automata