Algorithmic probability

In algorithmic information theory, algorithmic probability, also known as Solomonoff probability, is a mathematical method of assigning a prior probability to a given observation. It was invented by Ray Solomonoff in the 1960s.^[2] It is used in inductive inference theory and analyses of algorithms. In his general theory of inductive inference, Solomonoff uses the method together with Bayes' rule to obtain probabilities of prediction for an algorithm's future outputs.^[3]

In the mathematical formalism used, the observations have the form of finite binary strings viewed as outputs of Turing machines, and the universal prior is a probability distribution over the set of finite binary strings calculated from a probability distribution over programs (that is, inputs to a universal Turing machine). The prior is universal in the Turing-computability sense, i.e. no string has zero probability. It is not computable, but it can be approximated.^[4]

Formally, the probability P {\displaystyle P} is not a probability and it is not computable. It is only "lower semi-computable" and a "semi-measure". By "semi-measure", it means that 0 ≤ ∑ x P ( x ) < 1 {\displaystyle 0\leq \sum _{x}P(x)<1} . That is, the "probability" does not actually sum up to one, unlike actual probabilities. This is because some inputs to the Turing machine causes it to never halt, which means the probability mass allocated to those inputs is lost. By "lower semi-computable", it means there is a Turing machine that, given an input string x {\displaystyle x} , can print out a sequence y 1 < y 2 < ⋯ {\displaystyle y_{1}<y_{2}<\cdots } that converges to P ( x ) {\displaystyle P(x)} from below, but there is no such Turing machine that does the same from above.

Algorithmic probability is the main ingredient of Solomonoff's theory of inductive inference, the theory of prediction based on observations; it was invented with the goal of using it for machine learning; given a sequence of symbols, which one will come next? Solomonoff's theory provides an answer that is optimal in a certain sense, although it is incomputable.

Four principal inspirations for Solomonoff's algorithmic probability were: Occam's razor, Epicurus' principle of multiple explanations, modern computing theory (e.g. use of a universal Turing machine) and Bayes’ rule for prediction.^[5]

Occam's razor and Epicurus' principle are essentially two different non-mathematical approximations of the universal prior.

• Occam's razor: among the theories that are consistent with the observed phenomena, one should select the simplest theory.^[6]
• Epicurus' principle of multiple explanations: if more than one theory is consistent with the observations, keep all such theories.^[7]

At the heart of the universal prior is an abstract model of a computer, such as a universal Turing machine.^[8] Any abstract computer will do, as long as it is Turing-complete, i.e. every computable function has at least one program that will compute its application on the abstract computer.

The abstract computer is used to give precise meaning to the phrase "simple explanation". In the formalism used, explanations, or theories of phenomena, are computer programs that generate observation strings when run on the abstract computer. Each computer program is assigned a weight corresponding to its length. The universal probability distribution is the probability distribution on all possible output strings with random input, assigning for each finite output prefix q the sum of the probabilities of the programs that compute something starting with q.^[9] Thus, a simple explanation is a short computer program. A complex explanation is a long computer program. Simple explanations are more likely, so a high-probability observation string is one generated by a short computer program, or perhaps by any of a large number of slightly longer computer programs. A low-probability observation string is one that can only be generated by a long computer program.

Algorithmic probability is closely related to the concept of Kolmogorov complexity. Kolmogorov's introduction of complexity was motivated by information theory and problems in randomness, while Solomonoff introduced algorithmic complexity for a different reason: inductive reasoning. A single universal prior probability that can be substituted for each actual prior probability in Bayes's rule was invented by Solomonoff with Kolmogorov complexity as a side product.^[10] It predicts the most likely continuation of that observation, and provides a measure of how likely this continuation will be.^{[citation needed]}

Solomonoff's enumerable measure is universal in a certain powerful sense, but the computation time can be infinite. One way of dealing with this issue is a variant of Leonid Levin's Search Algorithm,^[11] which limits the time spent computing the success of possible programs, with shorter programs given more time. When run for longer and longer periods of time, it will generate a sequence of approximations which converge to the universal probability distribution. Other methods of dealing with the issue include limiting the search space by including training sequences.

Solomonoff proved this distribution to be machine-invariant within a constant factor (called the invariance theorem).^[12]

Kolmogorov's Invariance theorem clarifies that the Kolmogorov Complexity, or Minimal Description Length, of a dataset is invariant to the choice of Turing-Complete language used to simulate a Universal Turing Machine:

∀ x ∈ { 0 , 1 } ∗ , | K U ( x ) − K U ′ ( x ) | ≤ O ( 1 ) {\displaystyle \forall x\in \{0,1\}^{*},|K_{U}(x)-K_{U'}(x)|\leq {\mathcal {O}}(1)}

where K U ( x ) = min p { | p | : U ( p ) = x } {\displaystyle K_{U}(x)=\min _{p}\{|p|:U(p)=x\}} .

The minimal description p {\displaystyle p} such that U ( p ) = x {\displaystyle U(p)=x} serves as a natural representation of the string x {\displaystyle x} relative to the Turing-Complete language U {\displaystyle U} . Moreover, as x {\displaystyle x} can't be compressed further p {\displaystyle p} is an incompressible and hence uncomputable string. This corresponds to a scientists' notion of randomness and clarifies the reason why Kolmogorov Complexity is not computable.

It follows that any piece of data has a necessary and sufficient representation in terms of a random string.

The following is taken from ^[13]

From the theory of compilers, it is known that for any two Turing-Complete languages U 1 {\displaystyle U_{1}} and U 2 {\displaystyle U_{2}} , there exists a compiler Λ 1 {\displaystyle \Lambda _{1}} expressed in U 1 {\displaystyle U_{1}} that translates programs expressed in U 2 {\displaystyle U_{2}} into functionally-equivalent programs expressed in U 1 {\displaystyle U_{1}} .

It follows that if we let p {\displaystyle p} be the shortest program that prints a given string x {\displaystyle x} then:

K U 1 ( x ) ≤ | Λ 1 | + | p | ≤ K U 2 ( x ) + O ( 1 ) {\displaystyle K_{U_{1}}(x)\leq |\Lambda _{1}|+|p|\leq K_{U_{2}}(x)+{\mathcal {O}}(1)}

where | Λ 1 | = O ( 1 ) {\displaystyle |\Lambda _{1}|={\mathcal {O}}(1)} , and by symmetry we obtain the opposite inequality.

Given that any uniquely-decodable code satisfies the Kraft-McMillan inequality, prefix-free Kolmogorov Complexity allows us to derive the Universal Distribution:

P ( x ) = ∑ U ( p ) = x P ( U ( p ) = x ) = ∑ U ( p ) = x 2 − K U ( p ) ≤ 1 {\displaystyle P(x)=\sum _{U(p)=x}P(U(p)=x)=\sum _{U(p)=x}2^{-K_{U}(p)}\leq 1}

where the fact that U {\displaystyle U} may simulate a prefix-free UTM implies that for two distinct descriptions p {\displaystyle p} and p ′ {\displaystyle p'} , p {\displaystyle p} isn't a substring of p ′ {\displaystyle p'} and p ′ {\displaystyle p'} isn't a substring of p {\displaystyle p} .

In a Computable Universe, given a phenomenon with encoding x ∈ { 0 , 1 } ∗ {\displaystyle x\in \{0,1\}^{*}} generated by a physical process the probability of that phenomenon is well-defined and equal to the sum over the probabilities of distinct and independent causes. The prefix-free criterion is precisely what guarantees causal independence.

This is an immediate consequence of the Kraft-McMillan inequality.

Kraft's inequality states that given a sequence of strings { x i } i = 1 n {\displaystyle \{x_{i}\}_{i=1}^{n}} there exists a prefix code with codewords { σ i } i = 1 n {\displaystyle \{\sigma _{i}\}_{i=1}^{n}} where ∀ i , | σ i | = k i {\displaystyle \forall i,|\sigma _{i}|=k_{i}} if and only if:

∑ i = 1 n s − k i ≤ 1 {\displaystyle \sum _{i=1}^{n}s^{-k_{i}}\leq 1}

where s {\displaystyle s} is the size of the alphabet S {\displaystyle S} .

Without loss of generality, let's suppose we may order the k i {\displaystyle k_{i}} such that:

k 1 ≤ k 2 ≤ . . . ≤ k n {\displaystyle k_{1}\leq k_{2}\leq ...\leq k_{n}}

Now, there exists a prefix code if and only if at each step j {\displaystyle j} there is at least one codeword to choose that does not contain any of the previous j − 1 {\displaystyle j-1} codewords as a prefix. Due to the existence of a codeword at a previous step i < j , s k j − k i {\displaystyle i<j,s^{k_{j}-k_{i}}} codewords are forbidden as they contain σ i {\displaystyle \sigma _{i}} as a prefix. It follows that in general a prefix code exists if and only if:

∀ j ≥ 2 , s k j > ∑ i = 1 j − 1 s k j − k i {\displaystyle \forall j\geq 2,s^{k_{j}}>\sum _{i=1}^{j-1}s^{k_{j}-k_{i}}}

Dividing both sides by s k j {\displaystyle s^{k_{j}}} , we find:

∑ i = 1 n s − k i ≤ 1 {\displaystyle \sum _{i=1}^{n}s^{-k_{i}}\leq 1}

QED.

Solomonoff invented the concept of algorithmic probability with its associated invariance theorem around 1960,^[14] publishing a report on it: "A Preliminary Report on a General Theory of Inductive Inference."^[15] He clarified these ideas more fully in 1964 with "A Formal Theory of Inductive Inference," Part I^[16] and Part II.^[17]

Sequential Decisions Based on Algorithmic Probability is a theoretical framework proposed by Marcus Hutter to unify algorithmic probability with decision theory. The framework provides a foundation for creating universally intelligent agents capable of optimal performance in any computable environment. It builds on Solomonoff’s theory of induction and incorporates elements of reinforcement learning, optimization, and sequential decision-making.^[18]

Inductive reasoning, the process of predicting future events based on past observations, is central to intelligent behavior. Hutter formalized this process using Occam’s razor and algorithmic probability. The framework is rooted in Kolmogorov complexity, which measures the simplicity of data by the length of its shortest descriptive program. This concept underpins the universal distribution MM, as introduced by Ray Solomonoff, which assigns higher probabilities to simpler hypotheses. Hutter extended the universal distribution to include actions, creating a framework capable of addressing problems such as prediction, optimization, and reinforcement learning in environments with unknown structures.

The AIXI model is the centerpiece of Hutter’s theory. It describes a universal artificial agent designed to maximize expected rewards in an unknown environment. AIXI operates under the assumption that the environment can be represented by a computable probability distribution. It uses past observations to infer the most likely environmental model, leveraging algorithmic probability. Mathematically, AIXI evaluates all possible future sequences of actions and observations. It computes their algorithmic probabilities and expected utilities, selecting the sequence of actions that maximizes cumulative rewards. This approach transforms sequential decision-making into an optimization problem. However, the general formulation of AIXI is incomputable, making it impractical for direct implementation.

AIXI is universally optimal in the sense that it performs as well as or better than any other agent in all computable environments. This universality makes it a theoretical benchmark for intelligence. However, its reliance on algorithmic probability renders it computationally infeasible, requiring exponential time to evaluate all possibilities. To address this limitation, Hutter proposed time-bounded approximations, such as AIXItl, which reduce computational demands while retaining many theoretical properties of the original model. These approximations provide a more practical balance between computational feasibility and optimality.

The AIXI framework has significant implications for artificial intelligence and related fields. It provides a formal benchmark for measuring intelligence and a theoretical foundation for solving various problems, including prediction, reinforcement learning, and optimization. Despite its strengths, the framework has limitations. AIXI assumes that the environment is computable, excluding chaotic or non-computable systems. Additionally, its high computational requirements make real-world applications challenging.

Hutter’s theory raises philosophical questions about the nature of intelligence and computation. The reliance on algorithmic probability ties intelligence to the ability to compute and predict, which may exclude certain natural or chaotic phenomena. Nonetheless, the AIXI model offers insights into the theoretical upper bounds of intelligent behavior and serves as a stepping stone toward more practical AI systems.

• Ray Solomonoff
• Andrey Kolmogorov
• Leonid Levin

• Solomonoff's theory of inductive inference
• Algorithmic information theory
• Bayesian inference
• Inductive inference
• Inductive probability
• Kolmogorov complexity
• Universal Turing machine
• Information-based complexity

• Li, M. and Vitanyi, P., An Introduction to Kolmogorov Complexity and Its Applications, 3rd Edition, Springer Science and Business Media, N.Y., 2008
• Hutter, Marcus (2005). Universal artificial intelligence: sequential decisions based on algorithmic probability. Texts in theoretical computer science. Berlin Heidelberg: Springer. ISBN 978-3-540-22139-5.

• Rathmanner, S and Hutter, M., "A Philosophical Treatise of Universal Induction" in Entropy 2011, 13, 1076-1136: A very clear philosophical and mathematical analysis of Solomonoff's Theory of Inductive Inference

• Algorithmic Probability at Scholarpedia
• Solomonoff's publications