The Intrinsic Complexity of Learning: A Survey

• Autorzy: Jain S.
• Języki publikacji: EN

Abstrakty

EN

The theory of learning in the limit has been a focus of study by several researchers over the last three decades. There have been several suggestions on how to measure the complexity or hardness of learning. In this paper we survey the work done in one specific such measure, called intrinsic complexity of learning. We will be mostly concentrating on learning languages, with only a brief look at function learning.

Słowa kluczowe

EN

language learning theory; weak and strong reductions; intrinsic complexity of natural classes

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 57, nr 1
• Strony: 17--37
• Opis fizyczny: Bibliogr. 32 poz.

Twórcy

autor

Jain S.

• School of Computing, National University of Singapore 119260, Republic of Singapore,

Bibliografia

• [1] Angluin, D.: Finding patterns common to a set of strings, Journal of Computer and System Sciences, 21, 1980, 46-62.
• [2] Bārzdiņš, J., Freivalds, R.: On the prediction of General Recursive Functions, Soviet Mathematics Doklady, 13, 1972, 1224-1228.
• [3] Blum, M.: A Machine-Independent Theory of the Complexity of recursive Functions, Journal of the ACM, 14, 1967, 322-336.
• [4] Case, J.: The Power of Vacillation in Language Learning, SIAM Journal of Computing, 28, 1999, 1941-1969.
• [5] Case, J., Lynes, C.: Machine Inductive Inference and Language Identification, Proceedings of the 9th International Colloquium on Automata, Languages and Programming (M. Nielsen, E. M. Schmidt, Eds.), 140, Springer-Verlag, 1982.
• [6] Case, J., Smith, C.: Comparison of Identification Criteria for Machine Inductive Inference, Theoretical Computer Science, 25, 1983, 193-220.
• [7] Daley, R., Smith, C.: On the Complexity of Inductive Inference, Information and Control, 69, 1986, 12-40.
• [8] Feldman, J.: Some Decidability results on Grammatical Inference and Complexity, Information and Control, 20, 1972, 244-262.
• [9] Freivalds, R.: Inductive Inference of Recursive Functions: Qualitative Theory, in: Baltic Computer Science (J. Bārzdiņš, D. Bjorner, Eds.), vol. 502 of Lecture Notes in Computer Science, Springer-Verlag, 1991, 77-110.
• [10] Freivalds, R., Kinber, E., Smith, C.: On the Intrinsic Complexity of Learning, Second European Conference on Computational Learning Theory (P. Vitányi, Ed.), 904, Springer-Verlag, 1995.
• [11] Gold, E. M.: Language Identification in the Limit, Information and Control, 10, 1967, 447-474.
• [12] Hopcroft, J., Ullman, J.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.
• [13] Jain, S., Kinber, E.: Intrinsic Complexity of Learning Geometrical Concepts from Positive Data, Journal of Computer and System Sciences, 67, 2003, 546-607.
• [14] Jain, S., Kinber, E., Wiehagen, R.: Language Learning from Texts: Degrees of Intrinsic Complexity and Their Characterizations, Journal of Computer and System Sciences, 63, 2001, 305-354.
• [15] Jain, S., Osherson, D., Royer, J., Sharma, A.: Systems that Learn: An Introduction to Learning Theory, second edition, MIT Press, Cambridge, Mass., 1999.
• [16] Jain, S., Sharma, A.: Characterizing Language Learning by Standardizing Operations, Journal of Computer and System Sciences, 49(1), 1994, 96-107.
• [17] Jain, S., Sharma, A.: The Intrinsic Complexity of Language Identification, Journal of Computer and System Sciences, 52, 1996, 393-402.
• [18] Jain, S., Sharma, A.: Elementary formal systems, intrinsic complexity, and procrastination, Information and Computation, 132, 1997, 65-84.
• [19] Jain, S., Sharma, A.: The Structure of Intrinsic Complexity of Learning, Journal of Symbolic Logic, 62, 1997, 1187-1201.
• [20] Kinber, E.: On Comparison of Limit Identification and Limit Standardization of General Recursive Functions, Uch. zap. Latv. univ., 233, 1975, 45-56.
• [21] Kinber, E.: Monotonicity versus Efficiency for Learning Languages from Texts, Algorithmic Learning Theory: Fourth International Workshop on Analogical and Inductive Inference (AII ’94) and Fifth International Workshop on Algorithmic Learning Theory (ALT ’94) (S. Arikawa, K. Jantke, Eds.), 872, Springer-Verlag, 1994.
• [22] Kinber, E., Papazian, C., Smith, C., Wiehagen, R.: On the Intrinsic Complexity of Learning Infinite Objects from Finite Samples, Proceedings of the Twelfth Annual Conference on Computational Learning Theory, ACM Press, 1999.
• [23] Kinber, E., Stephan, F.: Language Learning from Texts: Mind Changes, Limited Memory and Monotonicity, Information and Computation, 123, 1995, 224-241.
• [24] Lange, S., Zeugmann, T.: Learning Recursive Languages With a Bounded Number of Mind Changes, International Journal of Foundations of Computer Science, 4(2), 1993, 157-178.
• [25] Machtey, M., Young, P.: An Introduction to the General Theory of Algorithms, North Holland, New York, 1978.
• [26] Motoki, T., Shinohara, T., Wright, K.: The Correct Definition of Finite Elasticity: Corrigendumto Identification of Unions, Proceedings of the Fourth Annual Workshop on Computational Learning Theory (L. Valiant, M. Warmuth, Eds.), Morgan Kaufmann, 1991.
• [27] Osherson, D., Weinstein, S.: Criteria of Language Learning, Information and Control, 52, 1982, 123-138.
• [28] Rogers, H.: Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967, Reprinted, MIT Press 1987.
• [29] Wiehagen, R.: Identification of Formal languages, Mathematical Foundations of Computer Science, 53, Springer-Verlag, 1977.
• [30] Wiehagen, R.: On the Complexity of Program Synthesis from Examples, Journal of Information Processing and Cybernetics (EIK), 22, 1986, 305-323.
• [31] Wright, K.: Identification of Unions of Languages Drawn from an Identifiable Class, Proceedings of the Second Annual Workshop on Computational Learning Theory (R. Rivest, D. Haussler, M. Warmuth, Eds.), Morgan Kaufmann, 1989.
• [32] Zeugmann, T., Lange, S.: A Guided Tour Across the Boundaries of Learning Recursive Languages, in: Algorithmic Learning for Knowledge-Based Systems (K. Jantke, S. Lange, Eds.), vol. 961 of Lecture Notes in Artificial Intelligence, Springer-Verlag, 1995, 190-258.