View source for Solomonoff's theory of inductive inference

{{Short description|Mathematical theory}}
{{multiple issues|
{{unreliable sources|date=February 2024}}
{{confusing|reason=large swathes of this article are filled with [[WP:JARGON|jargon]] and (unsourced!) vague generalizations|date=June 2017}}
{{more citations needed|date=June 2017}}
}}

'''Solomonoff's theory of inductive inference''' proves that, under its common sense assumptions (axioms), the best possible scientific model is the shortest algorithm that generates the empirical data under consideration.  In addition to the choice of data, other assumptions are that, to avoid the post-hoc fallacy, the [[programming language]] must be chosen prior to the data<ref>{{cite journal |last1=Rathmanner |first1=Samuel |title=A Philosophical Treatise of Universal Induction |journal=Entropy |date=3 June 2011 |volume=13 |issue=6 |pages=1076–1136 |doi=10.3390/e13061076 |doi-access=free |arxiv=1105.5721 }}</ref> and that the environment being observed is generated by an unknown algorithm.  This is also called a theory of [[Inductive reasoning|induction]].  Due to its basis in the dynamical ([[state-space representation|state-space model]]) character of [[Algorithmic Information Theory]],  it encompasses [[Model_selection#Criteria| ''statistical'' as well as dynamical information criteria for model selection]]. It was introduced by [[Ray Solomonoff]], based on [[probability theory]] and [[Computer science|theoretical computer science]].<ref name="Theory and Applications">{{Citation|last=Solomonoff|first=Ray J.|title=Algorithmic Probability: Theory and Applications|date=2009|url=https://doi.org/10.1007/978-0-387-84816-7_1|work=Information Theory and Statistical Learning|pages=1–23|editor-last=Emmert-Streib|editor-first=Frank|place=Boston, MA|publisher=Springer US|language=en|doi=10.1007/978-0-387-84816-7_1|isbn=978-0-387-84816-7|access-date=2020-07-21|editor2-last=Dehmer|editor2-first=Matthias|url-access=subscription}}</ref><ref name="BayesNguyên">{{cite book | last=Lê | first=Nguyên Hoang | title=The equation of knowledge: from Bayes' rule to a unified philosophy of science | publisher=CRC press | publication-place=Boca Raton, Fla | date=2020 | isbn=978-0-367-42815-0 }}</ref> In essence, Solomonoff's induction derives the [[posterior probability]] of any [[Computability|computable]] theory, given a sequence of observed data. This posterior probability is derived from [[Bayes' theorem|Bayes' rule]] and some ''universal'' prior, that is, a prior that assigns a positive probability to any computable theory.

Solomonoff proved that this induction is [[incomputable]] (or more precisely, lower semi-computable), but noted that "this incomputability is of a very benign kind", and that it "in no way inhibits its use for practical prediction" (as it can be approximated from below more accurately with more computational resources).<ref name="Theory and Applications"/>  It is only "incomputable" in the benign sense that no scientific consensus is able to prove that the best current [[scientific theory]] is the best of all possible theories.  However, Solomonoff's theory does provide an objective criterion for deciding among the current scientific theories explaining a given set of observations.

Solomonoff's induction naturally formalizes [[Occam's razor]]<ref name="ReferenceA">JJ McCall. Induction: From Kolmogorov and Solomonoff to De Finetti and Back to Kolmogorov – Metroeconomica, 2004 – Wiley Online Library.</ref><ref name="ReferenceB">D Stork. Foundations of Occam's razor and parsimony in learning from ricoh.com – NIPS 2001 Workshop, 2001</ref><ref name="ReferenceC">A.N. Soklakov. Occam's razor as a formal basis for a physical theory [https://arxiv.org/abs/math-ph/0009007 from arxiv.org] – Foundations of Physics Letters, 2002 – Springer</ref><ref name="Hernandez.1999">{{cite journal| author=Jose Hernandez-Orallo| title=Beyond the Turing Test| journal=Journal of Logic, Language and Information| year=1999| volume=9| url=http://users.dsic.upv.es/proy/anynt/Beyond.pdf}}</ref><ref name="Hutter.2003">M Hutter. On the existence and convergence of computable universal priors [https://arxiv.org/abs/cs/0305052 arxiv.org] – Algorithmic Learning Theory, 2003 – Springer</ref> by assigning larger prior credences to theories that require a shorter algorithmic description.

==Origin==

===Philosophical===
The theory is based in philosophical foundations, and was founded by [[Ray Solomonoff]] around 1960.<ref>Samuel Rathmanner and [[Marcus Hutter]]. A philosophical treatise of universal induction. Entropy, 13(6):1076–1136, 2011</ref> It is a mathematically formalized combination of [[Occam's razor]]<ref name="ReferenceA"/><ref name="ReferenceB"/><ref name="ReferenceC"/><ref name="Hernandez.1999"/><ref name="Hutter.2003"/> and the [[Principle of Multiple Explanations]].<ref name="Paul Vitanyi p 339">Ming Li and Paul Vitanyi, ''An Introduction to Kolmogorov Complexity and Its Applications.''  Springer-Verlag, N.Y., 2008p 339 ff.</ref> All [[computable]] theories which perfectly describe previous observations are used to calculate the probability of the next observation, with more weight put on the shorter computable theories. [[Marcus Hutter]]'s [[universal artificial intelligence]] builds upon this to calculate the [[expected value]] of an action.

===Principle===
Solomonoff's induction has been argued to be the computational formalization of pure [[Bayesian probability|Bayesianism]].<ref name="BayesNguyên" /> To understand, recall that Bayesianism derives the posterior probability <math>\mathbb P[T|D]</math> of a theory <math>T</math> given data <math>D</math> by applying Bayes rule, which yields

:<math>\mathbb P[T|D] = \frac{\mathbb P[D|T] \mathbb P[T]}{\mathbb P[D|T] \mathbb P[T] + \sum_{A \neq T} \mathbb P[D|A] \mathbb P[A]} </math>

where theories <math>A</math> are alternatives to theory <math>T</math>. For this equation to make sense, the quantities <math>\mathbb P[D|T]</math> and <math>\mathbb P[D|A]</math> must be well-defined for all theories <math>T</math> and <math>A</math>. In other words, any theory must define a probability distribution over observable data <math>D</math>. Solomonoff's induction essentially boils down to demanding that all such probability distributions be [[computable]].

Interestingly, the set of computable probability distributions is a subset of the set of all programs, which is [[Countable set|countable]]. Similarly, the sets of observable data considered by Solomonoff were finite. [[Without loss of generality]], we can thus consider that any observable data is a finite [[bit array|bit string]]. As a result, Solomonoff's induction can be defined by only invoking discrete probability distributions.

Solomonoff's induction then allows to make probabilistic predictions of future data <math>F</math>, by simply obeying the laws of probability. Namely, we have <math>\mathbb P[F|D] = \mathbb E_T [\mathbb P[F|T,D] ] = \sum_T \mathbb P[F|T,D] \mathbb P[T|D]</math>. This quantity can be interpreted as the average predictions <math>\mathbb P[F|T,D]</math> of all theories <math>T</math> given past data <math>D</math>, weighted by their posterior credences <math>\mathbb P[T|D]</math>.

===Mathematical===
The proof of the "razor" is based on the known mathematical properties of a probability distribution over a [[countable set]]. These properties are relevant because the [[infinite set]] of all programs is a denumerable set. The sum S of the probabilities of all programs must be exactly equal to one (as per the definition of [[probability]]) thus the probabilities must roughly decrease as we enumerate the infinite set of all programs, otherwise S will be strictly greater than one.  To be more precise, for every <math>\epsilon</math> > 0, there is some length ''l'' such that the probability of all programs longer than ''l'' is at most <math>\epsilon</math>.  This does not, however, preclude very long programs from having very high probability.

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.

==Mathematical guarantees==

===Solomonoff's completeness===

The remarkable property of Solomonoff's induction is its completeness. In essence, the completeness theorem guarantees that the expected cumulative errors made by the predictions based on Solomonoff's induction are upper-bounded by the [[Kolmogorov complexity]] of the (stochastic) data generating process. The errors can be measured using the [[Kullback–Leibler divergence]] or the square of the difference between the induction's prediction and the probability assigned by the (stochastic) data generating process.

===Solomonoff's uncomputability===

Unfortunately, Solomonoff also proved that Solomonoff's induction is uncomputable. In fact, he showed that [[computability]] and completeness are mutually exclusive: any complete theory must be uncomputable. The proof of this is derived from a game between the induction and the environment. Essentially, any computable induction can be tricked by a computable environment, by choosing the computable environment that negates the computable induction's prediction. This fact can be regarded as an instance of the ''[[no free lunch theorem]]''.

==Modern applications==

===Artificial intelligence===
Though Solomonoff's inductive inference is not [[computable]], several [[AIXI]]-derived algorithms approximate it in order to make it run on a modern computer. The more computing power they are given, the closer their predictions are to the predictions of inductive inference (their mathematical [[limit (math)|limit]] is Solomonoff's inductive inference).<ref>J. Veness, K.S. Ng, M. Hutter, W. Uther, D. Silver. "A Monte Carlo AIXI Approximation" – [https://arxiv.org/abs/0909.0801 Arxiv preprint], 2009 arxiv.org</ref><ref>J. Veness, K.S. Ng, M. Hutter, D. Silver. "Reinforcement Learning via AIXI Approximation" [https://arxiv.org/abs/1007.2049 Arxiv preprint], 2010 – aaai.org</ref><ref>S. Pankov. A computational approximation to the AIXI model from agiri.org – Artificial general intelligence, 2008: proceedings of …, 2008 – books.google.com</ref>

Another direction of inductive inference is based on [[E. Mark Gold]]'s model of [[Language identification in the limit|learning in the limit]] from 1967 and has developed since then more and more models of learning.<ref>{{Cite journal | last1 = Gold | first1 = E. Mark | year = 1967 | title = Language identification in the limit | journal = Information and Control | volume = 10 | issue = 5 | pages = 447–474 | doi = 10.1016/S0019-9958(67)91165-5 | url=http://web.mit.edu/~6.863/www/spring2009/readings/gold67limit.pdf | doi-access = free }}</ref> The general scenario is the following: Given a class ''S'' of computable functions, is there a learner (that is, recursive functional) which for any input of the form (''f''(0),''f''(1),...,''f''(''n'')) outputs a hypothesis (an index ''e'' with respect to a previously agreed on acceptable numbering of all computable functions; the indexed function may be required consistent with the given values of ''f''). A learner ''M'' learns a function ''f'' if almost all its hypotheses are the same index ''e'', which generates the function ''f''; ''M'' learns ''S'' if ''M'' learns every ''f'' in ''S''. Basic results are that all [[Computably enumerable set|recursively enumerable]] classes of functions are learnable while the class REC of all computable functions is not learnable.{{citation needed|reason=The previously cited paper (Gold 1967) is only about learning of a language, i.e. (a description of) a set of strings, from a sequence of member strings. Another reference is needed for the more general scenario about learning functions from sample values, in particular about the basic results.|date=January 2014}}
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 Schmidhuber's theory of generalized Kolmogorov complexities,<ref name="GenKolm">{{cite journal| author=J. Schmidhuber | title=Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit | journal=International Journal of Foundations of Computer Science | volume=13 | issue=4 | pages=587–612 | year=2002 | url=ftp://ftp.idsia.ch/pub/juergen/ijfcspreprint.pdf| archive-url=https://web.archive.org/web/20170706015921/ftp://ftp.idsia.ch/pub/juergen/ijfcspreprint.pdf | archive-date=2017-07-06 | url-status=dead | doi=10.1142/S0129054102001291}}</ref> which are kinds of [[super-recursive algorithm]]s.

==See also==
* [[Algorithmic information theory]]
* [[Bayesian inference]]
* [[Inductive inference]]
* [[Inductive probability]]
* [[Mill's methods]]
* [[Minimum description length]]
* [[Minimum message length]]
* For a philosophical viewpoint, see: [[Problem of induction]] and [[New riddle of induction]]

==References==
{{reflist}}

==Sources==
* {{cite journal| last1=Angluin | first1=Dana | last2= Smith| first2= Carl H.| title=Inductive Inference: Theory and Methods| journal=Computing Surveys|date=Sep 1983| volume=15| number=3| pages=237–269| url=https://dl.acm.org/doi/pdf/10.1145/356914.356918| doi=10.1145/356914.356918| s2cid=3209224 | url-access=subscription}}
* Burgin, M. (2005), ''Super-recursive Algorithms'', Monographs in computer science, Springer. {{ISBN|0-387-95569-0}}
* Burgin, M., "How We Know What Technology Can Do", ''Communications of the ACM'', v. 44, No. 11, 2001, pp.&nbsp;82–88.
* Burgin, M.; Eberbach, E., "Universality for Turing Machines, Inductive Turing Machines and Evolutionary Algorithms", ''Fundamenta Informaticae'', v. 91, No. 1, 2009, 53–77.
* Burgin, M.; Eberbach, E., "On Foundations of Evolutionary Computation: An Evolutionary Automata Approach", in ''Handbook of Research on Artificial Immune Systems and Natural Computing: Applying Complex Adaptive Technologies'' (Hongwei Mo, Ed.), IGI Global, Hershey, Pennsylvania, 2009, 342–360.
* Burgin, M.; Eberbach, E., "Evolutionary Automata: Expressiveness and Convergence of Evolutionary Computation", ''Computer Journal'', v. 55, No. 9, 2012, pp.&nbsp;1023–1029.
* Burgin, M.; Klinger, A. Experience, Generations, and Limits in Machine Learning, ''Theoretical Computer Science'', v. 317, No. 1/3, 2004, pp.&nbsp;71–91
* [[Martin Davis (mathematician)|Davis, Martin]] (2006) "The Church–Turing Thesis: Consensus and opposition]". Proceedings, Computability in Europe 2006.  Lecture Notes in Computer Science, 3988 pp.&nbsp;125–132.
* [[William Gasarch|Gasarch, W.]]; [[Carl Herbert Smith|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.&nbsp;225–260.
* Hay, Nick. "[http://www.cs.auckland.ac.nz/CDMTCS/researchreports/300nick.pdf Universal Semimeasures: An Introduction]," CDMTCS Research Report Series, University of Auckland, Feb. 2007.
* Jain, Sanjay; Osherson, Daniel; Royer, James; Sharma, Arun, ''Systems that Learn: An Introduction to Learning Theory'' (second edition), [[MIT Press]], 1999.
* {{Citation | last1=Kleene | first1=Stephen C. | author1-link=Stephen C. Kleene| title=Introduction to Metamathematics | publisher=North-Holland | location=Amsterdam | year=1952|edition=First}}.
* Li Ming; Vitanyi, Paul, ''An Introduction to Kolmogorov Complexity and Its Applications'', 2nd Edition, Springer Verlag, 1997.
* Osherson, Daniel; Stob, Michael; Weinstein, Scott, ''Systems That Learn, An Introduction to Learning Theory for Cognitive and Computer Scientists'', [[MIT Press]], 1986.
* {{cite journal| last = Solomonoff | first = Ray J.| title=Two Kinds of Probabilistic Induction| journal=The Computer Journal| year=1999| volume=42| number=4|doi=10.1093/comjnl/42.4.256 | page=256| citeseerx = 10.1.1.68.8941| url=http://world.std.com/~rjs/compj99.pdf}}
* {{cite journal | doi=10.1016/S0019-9958(64)90223-2 | last=Solomonoff | first= Ray | title=A Formal Theory of Inductive Inference Part I | journal = Information and Control | url=http://world.std.com/~rjs/1964pt1.pdf | volume=7 | issue= 1 | pages= 1&ndash;22 | date=March 1964| doi-access=free }}
* {{cite journal | doi=10.1016/S0019-9958(64)90131-7 | last=Solomonoff |first= Ray | title=A Formal Theory of Inductive Inference Part II | journal = Information and Control | url=http://world.std.com/~rjs/1964pt2.pdf |volume=7 |issue= 2 |pages= 224&ndash;254 |date=June 1964|doi-access=free }}

==External links==
*[http://www.scholarpedia.org/article/Algorithmic_probability Algorithmic probability – Scholarpedia]

[[Category:Algorithmic information theory]]
[[Category:Bayesian statistics]]
[[Category:Epistemology]]
[[Category:Inductive reasoning]]
[[Category:Machine learning]]
[[Category:Statistical inference]]