Inductive inference

From Wikipedia, the free encyclopedia

This article is about the mathematical concept, for inductive inference in logic, see Inductive reasoning.

Around 1960, Ray Solomonoff founded the theory of universal inductive inference, the theory of prediction based on observations; for example, predicting the next symbol based upon a given series of symbols. Unlike Karl Popper's informal theory of inductive inference, Solomonoff's is mathematically rigorous.

Fundamental ingredients of the theory are the concepts of algorithmic probability and Kolmogorov complexity. The universal prior probability of any prefix p of a computable sequence x is the sum of the probabilities of all programs (for a universal computer) that compute something starting with p. Given some p and any computable but unknown probability distribution from which x is sampled, the universal prior and Bayes' theorem can be used to predict the yet unseen parts of x in optimal fashion.

Another direction of inductive inference is based on Gold's model of learning in the limit from 1967 and has developed since then more and more models of learning. The general scenario is the following: Given a class S of computable functions, is there a learner (that is, recursive functional) which outputs for any input of the form (f(0),f(1),...,f(n)) a hypothesis. A learner M learns a function f if almost all hypotheses are the same index e of f with respect to a previously agreed on acceptable numbering of all computable functions; M learns S if M learns every f in S. Basic results are that all recursively enumerable classes of functions are learnable while the class REC of all computable functions is not learnable. Many related models have been considered and also the learning of classes of recursively enumerable sets from positive data is a topic studied from Gold's pioneering paper in 1967 onwards. A far reaching extension of the Gold’s approach is developed by Burgin theory of inductive Turing machines, which are kinds of super-recursive algorithms.

[edit] References

Angluin, D., and Smith, C. H. (1983) Inductive Inference: Theory and Methods, Comput. Surveys, v. 15, no. 3, pp. 237—269
Mark Burgin (2005), Super-recursive algorithms, Monographs in computer science, Springer. ISBN 0387955690
Burgin, M. and Klinger, A. Experience, Generations, and Limits in Machine Learning, Theoretical Computer Science, v. 317, No. 1/3, 2004, pp. 71-91
Gasarch, W. and Smith, C. H. (1997) A survey of inductive inference with an emphasis on queries. Complexity, logic, and recursion theory, Lecture Notes in Pure and Appl. Math., 187, Dekker, New York, pp. 225-260
Ming Li and Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, 2nd Edition, Springer Verlag, 1997.
Ray Solomonoff "Two Kinds of Probabilistic Induction," The Computer Journal, Vol. 42, No. 4, 1999
Ray Solomonoff "A Formal Theory of Inductive Inference, Part I" Information and Control, Part I: Vol 7, No. 1, pp. 1-22, March 1964
Ray Solomonoff "A Formal Theory of Inductive Inference, Part II" Information and Control, Part II: Vol. 7, No. 2, pp. 224-254, June 1964