# Inductive inference

Inductive inference

:"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. Solomonoff's theory attempts to be 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 E. Mark 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.

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

ee also

* Algorithmic probability
* Kolmogorov complexity
* Confirmation bias
* Language identification in the limit

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• inductive inference — noun : induction 2b(1) …   Useful english dictionary

• Inference — is the act or process of deriving a conclusion based solely on what one already knows. Inference is studied within several different fields. * Human inference (i.e. how humans draw conclusions) is traditionally studied within the field of… …   Wikipedia

• INFÉRENCE — Opération de l’esprit qui passe de propositions assertives, comme prémisses, à des propositions assertives, comme conclusions. Au sens strict, on distingue l’inférence du raisonnement en ce qu’elle peut être soit médiate soit immédiate (passer de …   Encyclopédie Universelle

• Inference bayesienne — Inférence bayésienne On nomme inférence bayésienne la démarche logique permettant de calculer ou réviser la probabilité d une hypothèse. Cette démarche est régie par l utilisation de règles strictes de combinaison des probabilités, desquelles… …   Wikipédia en Français

• Inférence Bayésienne — On nomme inférence bayésienne la démarche logique permettant de calculer ou réviser la probabilité d une hypothèse. Cette démarche est régie par l utilisation de règles strictes de combinaison des probabilités, desquelles dérive le théorème de… …   Wikipédia en Français

• inductive — deductive (see under DEDUCTION) Analogous words: ratiocinative, inferential (see under INFERENCE) …   New Dictionary of Synonyms

• inductive — ► ADJECTIVE 1) Logic characterized by the inference of general laws from particular instances. 2) relating to electric or magnetic induction. 3) Physics possessing inductance. DERIVATIVES inductively adverb inductiveness noun inductivism noun… …   English terms dictionary

• Inductive reasoning — Induction or inductive reasoning, sometimes called inductive logic, is the process of reasoning in which the premises of an argument are believed to support the conclusion but do not entail it; i.e. they do not ensure its truth. Induction is a… …   Wikipedia

• Inférence bayésienne — On nomme inférence bayésienne la démarche logique permettant de calculer ou réviser la probabilité d un événement. Cette démarche est régie en particulier par théorème de Bayes. Dans la perspective bayésienne, une probabilité n est pas… …   Wikipédia en Français

• Inférence inductive — Induction (logique) Pour les articles homonymes, voir Induction. À la différence de la déduction qui impose des propositions de départ non supposées vraies, l induction se propose de chercher des lois générales à partir de l observation de faits… …   Wikipédia en Français

### Share the article and excerpts

##### Direct link
Do a right-click on the link above
and select “Copy Link”