Abstract
Recently, a new approach to the study of “intrinsic” complexity of learning has originated in the work of Freivalds, and has been investigated for identification in the limit of functions by Freivalds, Kinber, and Smith and for identification in the limit of languages by Jain and Sharma. Instead of concentrating on the complexity of the learning algorithm, this approach uses the notion of reducibility to investigate the complexity of the concept classes being learned. Three representative classes have been presented that classify learning problems of increasing difficulty.
-
(a)
Classes that can be learned by machines that confirm their success (singleton languages).
-
(b)
Classes that can be learned by machines that cannot confirm their success but can provide an upper bound on the number of mind changes after inspecting an element of the language (pattern languages).
-
(c)
Classes that can be learned by machines that can neither confirm success nor can provide an upper bound on the number of mind changes (finite languages).
The present paper shows that there is an infinite hierarchy of language classes that represent learning problems of increasing difficulty. Language classes constituting this hierarchy are languages with bounded cardinality, and it can be shown that collections of languages that can be identified using bounded number of mind changes are reducible to the classes in this hierarchy. It is also shown that language classes in this hierarchy are incomparable, under the reductions introduced, to the collection of pattern languages.
The structure of intrinsic complexity is shown to be rich as any finite, acyclic, directed graph can be embedded in this structure. However, it is also established that this structure is not dense.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. Angluin. Finding patterns common to a set of strings. Journal of Computer and System Sciences, 21:46–62, 1980.
M. Blum. A machine independent theory of the complexity of recursive functions. Journal of the ACM, 14:322–336, 1967.
J. Case. Periodicity in generations of automata. Mathematical Systems Theory, 8:15–32, 1974.
R. Freivalds. Inductive inference of recursive functions: Qualitative theory. In J. Barzdins and D. Bjorner, editors, Baltic Computer Science. Lecture Notes in Computer Science 502, pages 77–110. Springer-Verlag, 1991.
R Freivalds, E. Kinber, and C. H. Smith. On the intrinsic complexity of learning. In Proceedings of the Second European Conference on Computational Learning Theory. Springer-Verlag, March 1995.
E. M. Gold. Language identification in the limit. Information and Control, 10:447–474, 1967.
J. Hopcroft and J. Ullman. Introduction to Automata Theory Languages and Computation. Addison-Wesley Publishing Company, 1979.
S. Jain and A. Sharma. On the intrinsic complexity of language identification. In Proceedings of the Seventh Annual Conference on Computational Learning Theory, New Brunswick, New Jersey, pages 278–286. ACM-Press, July 1994.
M. Machtey and P. Young. An Introduction to the General Theory of Algorithms. North Holland, New York, 1978.
H. Rogers. Theory of Recursive Functions and Effective Computability. McGraw Hill, New York, 1967. Reprinted, MIT Press 1987.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jain, S., Sharma, A. (1995). The structure of intrinsic complexity of learning. In: Vitányi, P. (eds) Computational Learning Theory. EuroCOLT 1995. Lecture Notes in Computer Science, vol 904. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-59119-2_176
Download citation
DOI: https://doi.org/10.1007/3-540-59119-2_176
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-59119-1
Online ISBN: 978-3-540-49195-8
eBook Packages: Springer Book Archive