Inductive inference of approximations for recursive concepts

ABSTRACT

This paper provides a systematic study of inductive inference of indexable concept classes in learning scenarios where the learner is successful if its final hypothesis describes a finite variant of the target concept, i.e., learning with anomalies. Learning from positive data only and from both positive and negative data is distinguished.The following learning models are studied: learning in the limit, finite identification, set-driven learning, conservative inference, and behaviorally correct learning.The attention is focused on the case that the number of allowed anomalies is finite but not a priori bounded. However, results for the special case of learning with an a priori bounded number of anomalies are presented, too. Characterizations of the learning models with anomalies in terms of finite tell-tale sets are provided. The observed varieties in the degree of recursiveness of the relevant tell-tale sets are already sufficient to quantify the differences in the corresponding learning models with anomalies. Finally, a complete picture concerning the relations of all models of learning with and without anomalies mentioned above is derived.

REFERENCES

• 1: [1] D. Angluin, Finding patterns common to a set of strings, J. Comput. System Sci. 21 (1980) 46-62.
• 2: [2] D. Angluin, Inductive inference of formal languages from positive data, Inform. Control 45 (2) (1980) 117-135.
• 3: Ganesh R. Baliga , John Case , Sanjay Jain, The synthesis of language learners, Information and Computation, v.152 n.1, p.16-43, July 10, 1999 [doi>10.1006/inco.1998.2782]
• 4: [4] J.M. Barzdinš, Two theorems on the limiting synthesis of functions, in: Theory of Algorithms and Programs, Vol. 1, Latvian State University, 1974, pp. 82-88, (in Russian).
• 5: [5] L. Blum, M. Blum, Toward a mathematical theory of inductive inference, Inform. Control 28 (1975) 125-155.
• 6: Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967 [doi>10.1145/321386.321395]
• 7: John Case , Christopher Lynes, Machine Inductive Inference and Language Identification, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.107-115, July 12-16, 1982
• 8: [8] J. Case, C.H. Smith, Comparison of identification criteria for machine inductive inference, Theoret. Comput. Sci. 25 (1983) 193-220.
• 9: [9] R.P. Daley, On the error correcting power of pluralism in BC-type inductive inference, Theoret. Comput. Sci. 24 (1) (1983) 95-104.
• 10: Mark A. Fulk, Prudence and other conditions on formal language learning, Information and Computation, v.85 n.1, p.1-11, March 1990 [doi>10.1016/0890-5401(90)90042-G]
• 11: [11] E.M. Gold, Language identification in the limit, Inform. Control 10 (1967) 447-474.
• 12: [12] S. Jain, D. Osherson, J.S. Royer, A. Sharma, Systems that Learn, An Introduction to Learning Theory, second edition, MIT Press, Cambridge, MA, 1999.
• 13: Efim Kinber , Thomas Zeugmann, One-sided error probabilistic inductive inference and reliable frequency identification, Information and Computation, v.92 n.2, p.253-284, June 1991 [doi>10.1016/0890-5401(91)90011-P]
• 14: Steffen Lange , Rolf Wiehagen, Polynomial-time inference of arbitrary pattern languages, New Generation Computing, v.8 n.4, p.361-370, 1991 [doi>10.1007/BF03037093]
• 15: Steffen Lange , Thomas Zeugmann, Types of monotonic language learning and their characterization, Proceedings of the fifth annual workshop on Computational learning theory, p.377-390, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130427]
• 16: Steffen Lange , Thomas Zeugmann, Language learning in dependence on the space of hypotheses, Proceedings of the sixth annual conference on Computational learning theory, p.127-136, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168320]
• 17: [17] S. Lange, T. Zeugmann, Set-driven and rearrangement-independent learning of recursive languages, Math. Systems Theory 29 (6) (1996) 599-634.
• 18: James S Royer, Inductive inference of approximations, Information and Control, v.70 n.2-3, p.156-178, Aug/Sept. 1986 [doi>10.1016/S0019-9958(86)80002-X]
• 19: [19] T. Tabe, T. Zeugmann, Two variations of inductive inference of languages from positive data, Tech. Report RIFIS-TR-CS-105, Kyushu University, 1995.
• 20: [20] K. Wexler, P.W. Culicover, Formal Principles of Language Acquisition, MIT Press, Cambridge, MA, 1980.
• 21: [21] R. Wiehagen, T. Zeugmann, Ignoring data may be the only way to learn efficiently, J. Exper. Theoret. Artif. Intell. 6 (1) (1994) 131-144.
• 22: Thomas Zeugmann , Steffen Lange, A Guided Tour Across the Boundaries of Learning Recursive Languages, Algorithmic Learning for Knowledge-Based Systems, GOSLER Final Report, p.190-258, January 1995

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Inference engines
      I.2.6 Learning
          Subjects: Concept learning

General Terms:
Algorithms, Design, Theory

Keywords:
characterization theorems, conservative learning, indexed families, inductive inference, learning from examples, learning theory, learning with anomalies, set-driven learning