Solomonoff's Theory Of Inductive Inference

Solomonoff's theory of inductive inference is a mathematical proof that if a universe is generated by an algorithm, then observations of that universe, encoded as a dataset, are best predicted by the smallest executable archive of that dataset. This formalization of Occam's razorJJ McCall. Induction: From Kolmogorov and Solomonoff to De Finetti and Back to Kolmogorov – Metroeconomica, 2004 – Wiley Online Library.D Stork. Foundations of Occam's razor and parsimony in learning from ricoh.com – NIPS 2001 Workshop, 2001A.N. Soklakov. Occam's razor as a formal basis for a physical theor
from arxiv.org
– Foundations of Physics Letters, 2002 – SpringerM Hutter. On the existence and convergence of computable universal prior
arxiv.org
– Algorithmic Learning Theory, 2003 – Springer for induction was introduced by Ray Solomonoff, based on probability theory and theoretical computer science. In essence, Solomonoff's induction derives the posterior probability of any computable theory, given a sequence of observed data. This posterior probability is derived from Bayes rule and some ''universal'' prior, that is, a prior that assigns a positive probability to any computable theory.

Origin

Philosophical

The theory is based in philosophical foundations, and was founded by Ray Solomonoff around 1960. It is a mathematically formalized combination of Occam's razor and the Principle of Multiple Explanations.Ming Li and Paul Vitanyi, ''An Introduction to Kolmogorov Complexity and Its Applications.'' Springer-Verlag, N.Y., 2008p 339 ff. 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 Bayesianism. To understand, recall that Bayesianism derives the posterior probability \mathbb P D/math> of a theory $T$ given data $D$ by applying Bayes rule, which yields \mathbb P D= \mathbb P T\mathbb P / (\mathbb P T\mathbb P + \sum_ \mathbb P A\mathbb P , where theories $A$ are alternatives to theory $T$. For this equation to make sense, the quantities \mathbb P T/math> and \mathbb P A/math> must be well-defined for all theories $T$ and $A$. In other words, any theory must define a probability distribution over observable data $D$. Solomonoff's induction essentially boils down to demanding in addition 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. 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 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 $F$, by simply obeying the laws of probability. Namely, we have \mathbb P D= \mathbb E_T T,D.html"_;"title=".html"_;"title="mathbb_P[F">T,D">.html"_;"title="mathbb_P T,D=_\sum_T_\mathbb_P[F.html"_;"title="">T,D.html"_;"title=".html"_;"title="mathbb_P[F">T,D">.html"_;"title="mathbb_P[F">T,D=_\sum_T_\mathbb_P[F">T,D\mathbb_P_D/math>._This_quantity_can_be_interpreted_as_the_average_predictions_\mathbb_P[F.html" ;"title="">T,D=_\sum_T_\mathbb_P[F.html" ;"title="">T,D.html" ;"title=".html" ;"title="mathbb P[F">T,D">.html" ;"title="mathbb P[F">T,D= \sum_T \mathbb P[F">T,D\mathbb P D/math>. This quantity can be interpreted as the average predictions \mathbb P[F">T,D/math> of all theories $T$ given past data $D$, weighted by their posterior credences \mathbb P 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 [ robability) 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 $\epsilon$ > 0, there is some length ''l'' such that the probability of all programs longer than ''l'' is at most $\epsilon$. 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