Algorithmic probability
Encyclopedia
In algorithmic information theory
, algorithmic (Solomonoff) probability is a method of assigning a probability
to each hypothesis
(algorithm/program) that explains a given observation, with the simplest hypothesis (the shortest program) having the highest probability and the increasingly complex hypotheses (longer programs) receiving increasingly small probabilities. These probabilities form a priori
a probability distribution
for the observation, which Ray Solomonoff
proved to be machine-invariant (called the invariance theorem
) and can be used with Bayes' theorem
to predict the most likely continuation of that observation. A theoretic computer, the universal Turing machine
, is used for the computer operations.
Solomonoff invented the concept of algorithmic probability with its associated invariance theorem around 1960. He first published his results at a conference at Caltech in 1960, and in a report, Feb. 1960, "A Preliminary Report on a General Theory of Inductive Inference." He clarified these ideas more fully in 1964 with "A Formal Theory of Inductive Inference," Part I and Part II.
The algorithmic probability of any given finite output prefix q is the sum of the probabilities
of the programs that compute something starting with q. Certain long objects with short programs have high probability.
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. Unlike, for example, Karl Popper
's informal inductive inference theory, however, Solomonoff's is mathematically rigorous.
Algorithmic probability is closely related to the concept of Kolmogorov complexity
. Kolmogorov complexity, however, focuses on the information content of a string while algorithmic probability focuses on the predictive power of a string.
Solomonoff's enumerable measure is universal
in a certain powerful sense, but the computation time can be infinite. To deal with this Solomonoff uses a variant of Leonid Levin's Search Algorithm, which limits the time spent computing the success of possible programs, with shorter programs given more time. Other methods of limiting search space used by Solomonoff include training sequences.
Algorithmic information theory
Algorithmic information theory is a subfield of information theory and computer science that concerns itself with the relationship between computation and information...
, algorithmic (Solomonoff) probability is a method of assigning a probability
Probability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
to each hypothesis
Hypothesis
A hypothesis is a proposed explanation for a phenomenon. The term derives from the Greek, ὑποτιθέναι – hypotithenai meaning "to put under" or "to suppose". For a hypothesis to be put forward as a scientific hypothesis, the scientific method requires that one can test it...
(algorithm/program) that explains a given observation, with the simplest hypothesis (the shortest program) having the highest probability and the increasingly complex hypotheses (longer programs) receiving increasingly small probabilities. These probabilities form a priori
A priori
A priori is Latin for "from the former" or "from before", and may refer to:* A priori knowledge, justification or arguments. See a priori and a posteriori.* A priori , a type of constructed language...
a probability distribution
Probability distribution
In probability theory, a probability mass, probability density, or probability distribution is a function that describes the probability of a random variable taking certain values....
for the observation, which Ray Solomonoff
Ray Solomonoff
Ray Solomonoff was the inventor of algorithmic probability, and founder of algorithmic information theory, He was an originator of the branch of artificial intelligence based on machine learning, prediction and probability...
proved to be machine-invariant (called the invariance theorem
Invariance theorem
In algorithmic information theory, the invariance theorem, originally proved by Ray Solomonoff, states that a universal Turing machine provides an optimal means of description, up to an additive constant...
) and can be used with Bayes' theorem
Bayes' theorem
In probability theory and applications, Bayes' theorem relates the conditional probabilities P and P. It is commonly used in science and engineering. The theorem is named for Thomas Bayes ....
to predict the most likely continuation of that observation. A theoretic computer, the universal Turing machine
Universal Turing machine
In computer science, a universal Turing machine is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simulated as well as the input thereof from its own tape. Alan...
, is used for the computer operations.
Solomonoff invented the concept of algorithmic probability with its associated invariance theorem around 1960. He first published his results at a conference at Caltech in 1960, and in a report, Feb. 1960, "A Preliminary Report on a General Theory of Inductive Inference." He clarified these ideas more fully in 1964 with "A Formal Theory of Inductive Inference," Part I and Part II.
The algorithmic probability of any given finite output prefix q is the sum of the probabilities
Probability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
of the programs that compute something starting with q. Certain long objects with short programs have high probability.
Algorithmic probability is the main ingredient of Solomonoff's theory of inductive inference
Inductive inference
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...
, 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. Unlike, for example, Karl Popper
Karl Popper
Sir Karl Raimund Popper, CH FRS FBA was an Austro-British philosopher and a professor at the London School of Economics...
's informal inductive inference theory, however, Solomonoff's is mathematically rigorous.
Algorithmic probability is closely related to the concept of Kolmogorov complexity
Kolmogorov complexity
In algorithmic information theory , the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object...
. Kolmogorov complexity, however, focuses on the information content of a string while algorithmic probability focuses on the predictive power of a string.
Solomonoff's enumerable measure is universal
Universality (philosophy)
In philosophy, universalism is a doctrine or school claiming universal facts can be discovered and is therefore understood as being in opposition to relativism. In certain religions, universality is the quality ascribed to an entity whose existence is consistent throughout the universe...
in a certain powerful sense, but the computation time can be infinite. To deal with this Solomonoff uses a variant of Leonid Levin's Search Algorithm, which limits the time spent computing the success of possible programs, with shorter programs given more time. Other methods of limiting search space used by Solomonoff include training sequences.
External links
- detailed description of Algorithmic Probability in ScholarpediaScholarpediaScholarpedia is an English-language online wiki-based encyclopedia that uses the same MediaWiki software as Wikipedia, but has features more commonly associated with open-access online academic journals....
- Solomonoff's publications