Definition
In inductive inference, the complexity of learning can be measured in various ways: by the number of hypotheses issued in the worst case until the correct hypothesis is found, by the number of data items to be consumed or to be memorized in order to learn in the worst case, by the Turing degree of oracles needed to learn the class under a certain criterion, and by the intrinsic complexity which is – like the Turing degrees in recursion theory – a way to measure the complexity of classes by using reducibilities between them.
Detail
We refer the reader to the article Inductive Inference for basic definitions in inductive inference and the notations used below. Let \(\mathbb{N}\) denote the set of natural numbers. Let φ0, φ1, … denote a fixed acceptable numbering of the partial-recursive functions (Rogers 1967). Let W i = domain(φ i ).
Mind Changes and Anomalies
The first measure of complexity of learning can be considered as the number of mind changes needed before the learner...
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Recommended Reading
Adleman L, Blum M (1991) Inductive inference and unsolvability. J Symb Log 56:891–900
Angluin D (1980) Finding patterns common to a set of strings. J Comput Syst Sci 21:46–62
Case J, Smith CH (1983) Comparison of identification criteria for machine inductive inference. Theor Comput Sci 25:193–220
Case J, Jain S, Lange S, Zeugmann T (1999) Incremental concept learning for bounded data mining. Inf Comput 152(1):74–110
Chen K-J (1982) Tradeoffs in inductive inference of nearly minimal sized programs. Inf Control 52:68–86
Daley RP, Smith CH (1986) On the complexity of inductive inference. Inf Control 69:12–40
Freivalds R (1975) Minimal Gödel numbers and their identification in the limit. Lect Not Comput Sci 32:219–225
Freivalds R, Smith CH (1993) On the role of procrastination in machine learning. Inf Comput 107(2):237–271
Freivalds R, Kinber E, Smith CH (1995) On the intrinsic complexity of learning. Inf Comput 123:64–71
Jain S, Sharma A (1993) On the non-existence of maximal inference degrees for language identification. Inf Process Lett 47:81–88
Jain S, Sharma A (1994) Program size restrictions in computational learning. Theor Comput Sci 127:351–386
Jain S, Sharma A (1996) The intrinsic complexity of language identification. J Comput Syst Sci 52:393–402
Jain S, Sharma A (1997a) The structure of intrinsic complexity of learning. J Symb Log 62:1187–1201
Jain S, Sharma A (1997b) Elementary formal systems, intrinsic complexity and procrastination. Inf Comput 132:65–84
Jain S, Kinber E, Wiehagen R (2001) Language learning from texts: degrees of intrinsic complexity and their characterizations. J Comput Syst Sci 63:305–354
Lange S, Zeugmann T (1996) Incremental learning from positive data. J Comput Syst Sci 53:88–103
Pitt L (1989) Inductive inference, DFAs, and computational complexity. In: Analogical and inductive inference, second international workshop (AII 1989). LNAI, vol 397. Springer, Heidelberg, pp 18–44
Rogers H (1967) Theory of recursive functions and effective computability. McGraw-Hill, New York (Reprinted, MIT Press 1987)
Shinohara T (1994) Rich classes inferable from positive data: length–bounded elementary formal systems. Inf Comput 108:175–186
Slaman TA, Solovay R (1991) When oracles do not help. In: Proceedings of the fourth annual workshop on computational learning theory, Santa Cruz. Morgan Kaufmann, pp 379–383
Wiehagen R (1976) Limes-Erkennung rekursiver Funktionen durch spezielle Strategien. J Inf Process Cybern EIK 12:93–99
Wiehagen R (1986) On the complexity of effective program synthesis. In: Jantke K (ed) Analogical and inductive inference. Proceedings of the international workshop. LNCS, vol 265. Springer, pp 209–219
Acknowledgements
Sanjay Jain was supported in part by NUS grant numbers C252-000-087-001, R146-000-181-112, R252-000-534-112. Frank Stephen was supported in part by NUS grant numbers R146-000-181-112, R252-000-534-112.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer Science+Business Media New York
About this entry
Cite this entry
Jain, S., Stephan, F. (2017). Complexity of Inductive Inference. In: Sammut, C., Webb, G.I. (eds) Encyclopedia of Machine Learning and Data Mining. Springer, Boston, MA. https://doi.org/10.1007/978-1-4899-7687-1_46
Download citation
DOI: https://doi.org/10.1007/978-1-4899-7687-1_46
Published:
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4899-7685-7
Online ISBN: 978-1-4899-7687-1
eBook Packages: Computer ScienceReference Module Computer Science and Engineering