Types of monotonic language learning and their characterization

ABSTRACT

The present paper deals with strong-monotonic, monotonic and weak-monotonic language learning from positive data as well as from positive and negative examples. The three notions of monotonicity reflect different formalizations of the requirement that the learner has to produce always better and better generalizations when fed more and more data on the concept to be learnt. We characterize strong-monotonic, monotonic, weak-monotonic and finite language learning from positive data in terms of recursively generable finite sets, thereby solving a problem of Angluin (1980). Moreover, we study monotonic inference with iteratively working learning devices which are of special interest in applications. In particular, it is proved that strong-monotonic inference can be performed with iteratively learning devices without limiting the inference capabilities, while monotonic and weak-monotonic inference cannot.

REFERENCES

• 1: Angluin, D., (1980), Inductive Inference of Formal Languagues from Positive Data, Information and Control 45, 117- 135
• 2: 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]
• 3: Angluin, D. and C.H. Smith, (1987), Formal Inductive Inference, In Encyclopedia of Artificial Inte}{ligence, St.C. Shapiro (Ed.), Vol. 1, pp. 409 - 4}{8, Wiley-Interscience Publication, New York
• 4: Barzdin, Ya.M., (1974), Inductive Inference of Automata, Functions and Programs, Proc. International Congress of Math., Vancouver, pp. 455 - 460
• 5: Bucher, W. and H. Maurer, (1984), Theoretische Grundlagen der Programmiersprachen, Automaten und Sprachen, Bibliographisches Institut AG, Wissenschaftsverlag, Ziirich
• 6: John Case, The power of vacillation, Proceedings of the first annual workshop on Computational learning theory, p.196-205, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 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: Rusins Freivalds , Efim B. Kinber , Rolf Wiehagen, Inductive Inference from Good Examples, Proceedings of the International Workshop on Analogical and Inductive Inference, p.1-17, October 01-06, 1989
• 9: Freivalds, R., Kinber, E. B. and R. Wiehagen, (1992), Convergently versus Divergently Incorrect Hypotheses in Inductive Inference, GOSLER Report 02/92, January 1992, Fachbereich Mathematik und Informatik, TH Leipzig
• 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: Gold, M.E., (1967), Language Identification in the Limit, Information and Control 10,447 - 474
• 12: Jain, S. and A. Sharma, (1989), Recursion Theoretic Characterizations of Language Learning, The University of Rochester, Dept. of Computer Science, TR 281
• 13: Klaus P. Jantke, Monotonic and non-monotonic inductive inference, New Generation Computing, v.8 n.4, p.349-360, 1991 [doi>10.1007/BF03037092]
• 14: Klaus P. Jantke, Monotonic and Nonmonotonic Inductive Inference of Functions and Patterns, Proceedings of the 1st International Workshop on Nonmonotonic and Inductive Logic, p.161-177, December 04-07, 1990
• 15: Shyam Kapur, Computational learning of languages, Cornell University, Ithaca, NY, 1992
• 16: Shyam Kapur , Gianfranco Bilardi, Language Learning without Overgeneralization, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, p.245-256, February 13-15, 1992
• 17: 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]
• 18: Steffen Lange , Thomas Zeugmann, Monotonic Versus Nonmonotonic Language Learning, Proceedings of the Second International Workshop on Nonmonotonic and Inductive Logic, p.254-269, December 02-06, 1991
• 19: Lange, S. and T. Zeugmann, (1992), On the Power of Monotonic Language Learning, GOSLER-Report 05/92, February 1992, Fachbereich Mathematik und Informatik, TH Leipzig
• 20: Mukouchi, Y., (1991), Definite Inductive Inference as a Successful Identification Criterion, Research Institute of Fundamental Information Science, Kyushu University 33, Fukuoka, December 24, '91 RIFIS-TR-CS-52
• 21: Daniel N. Osherson , Michael Stob , Scott Weinstein, Systems that learn: an introduction to learning theory for cognitive and computer scientists, MIT Press, Cambridge, MA, 1986
• 22: Sara Porat , Jerome A. Feldman, Learning automata from ordered examples, Proceedings of the first annual workshop on Computational learning theory, p.386-396, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 23: Solomonoff, R., (1964), A Formal Theory of Inductive Inference, Information and Control 7, i - 22, 234- 254
• 24: Wiehagen, R., (1976), Limes-Erkennung rekursiver Funktionen dutch spezielle Strategien, J. Information Processing and Cybernetics (EIK) 12, 93 - 99
• 25: Wiehagen, R., (1977), Identification of Formal Languages, Proc. Mathematical Foundations of Computer Science, Tatranska Lomnica, J. Gruska (Ed.), Lecture Notes in Computer Science 53, pp. 571 ~ 579, Springer-Verlag
• 26: Rolf Wiehagen, A Thesis in Inductive Inference, Proceedings of the 1st International Workshop on Nonmonotonic and Inductive Logic, p.184-207, December 04-07, 1990
• 27: Wiehagen, R., (1992), Personal Communication

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Theory, Verification