The representation of recursive languages and its impact on the efficiency of learning

ABSTRACT

In the present paper we study the learnability of the enumerable families L of uniformly recursive languages in dependence on the number of allowed mind changes, i.e., with respect to a well-studied measure of efficiency. We distinguish between exact learnability ( L has to be learnt w.r.t. the hypothesis space L itself), class preserving learning ( L has to be inferred w.r.t. some hypothesis space G having the same range as L ), and class comprising inference ( L has to be inferred w.r.t. some hypothesis space G that has a range including range ( L )) as well as between learning from positive and negative examples. The measure of efficiency is applied to prove the superiority of class comprising learning algorithms over class preserving learning which itself turns out to be superior to exact learning algorithms. In particular, we considerably improve results obtained previously and show that a suitable choice of the hypothesis space may result in a considerable speed up of learning algorithms, even if instead of positive and negative data only positive examples will be presented. Furthermore, we completely separate all modes of learning with a bounded number of mind changes from class preserving learning that avoids overgeneralization.

REFERENCES

• 1: Angluin, D. (1980), Inductive inference of formal languages from positive data, Information and Control 45, 117- 135.
• 2: Barzdin, Y., and Freivalds, R. (1972), On the prediction of general recursive functions, Soy. Math. Dokl. 13, 1224- 1228.
• 3: Barzdin, Y., and Freivalds, R. (1974), Prognosirowanie i predelny sintez effektiwno perechislimych klassow funkzi, in "Teorija Algoritmow i Programm," Vol. 1, Latvian State University, Riga, pp. 101 - 111.
• 4: Case, J., and Smith, C. (1983), Comparison of identification criteria for machine inductive inference, Theoretical Computer Science 25, 193 - 220.
• 5: Gold, E.M. (1967), Language identification in the limit, Information and Control 10,447 - 474.
• 6: 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
• 7: 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]
• 8: 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
• 9: Steffen Lange , Thomas Zeugmann, Language Learning with a Bounded Number of Mind Changes, Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, p.682-691, February 25-27, 1993
• 10: 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]
• 11: Lange, S., and Zeugmann, T. (1993d), Learning recursive languages with bounded mind changes, International Journal of Foundations of Computer Science 4, 157- 178.
• 12: Michael Machtey , Paul Young, An Introduction to the General Theory of Algorithms, Elsevier Science Inc., New York, NY, 1978
• 13: Yasuhito Mukouchi, Inductive Inference with Bounded Mind Changes, Proceedings of the Third Workshop on Algorithmic Learning Theory, p.125-134, October 20-22, 1992
• 14: 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
• 15: Leonard Pitt , Leslie G. Valiant, Computational limitations on learning from examples, Journal of the ACM (JACM), v.35 n.4, p.965-984, Oct. 1988 [doi>10.1145/48014.63140]
• 16: Arto Salomaa, Formal languages, Academic Press Professional, Inc., San Diego, CA, 1987
• 17: Takeshi Shinohara, Inductive inference from positive data is powerful, Proceedings of the third annual workshop on Computational learning theory, p.97-110, August 06-08, 1990, Rochester, New York, United States
• 18: Wiehagen, R. (1977), Identification of formal languages, in "Proc. Mathematical Foundations of Computer Science," Lecture Notes in Computer Science Vol. 53, Springer-Verlag, Berlin, pp. 571 - 579.
• 19: Wiehagen, R., Freivalds, R., and Kinber, B. (1984), On the power of probabilistic strategies in inductive inference, Theoretical Computer Science 28, 111- 133.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Algorithms, Theory, Verification