Solomonoff induction
In plain wordsA mathematical recipe for ideal prediction: consider every computer program that could have produced the data so far, trust shorter programs more, and predict what they would output next.
A formal theory of prediction in which the priorprior, n.: What you believe, and how strongly, before looking at the evidence in front of you. In AI it also means built-in assumptions that steer what a system learns. probability of each computable hypothesis is proportional to two raised to the minus the length of a program implementing it on a universal Turing machineTuring machine, n.: An imaginary, extremely simple computer — a read-write head moving along an endless tape — that Alan Turing used in 1936 to define exactly what can be computed at all. (the 'universal prior', or algorithmic probability), and predictions follow by BayesianBayesian inference, n.: Reasoning that treats unknowns as uncertain beliefs and updates them with evidence using Bayes' theorem. The result is not one answer but a range of answers, each with a probability. updating over all such programs. It combines Occam's razorOccam's razor, n.: A rule of thumb for choosing between explanations: if two fit the evidence equally well, bet on the one that assumes less. In AI it motivates preferring simpler models, which are less likely to fit noise., since shorter programs get more weight, with Epicurus's principle of keeping every hypothesis consistent with the data. Solomonoff proved that, for data generated by any computable probability distribution, its predictions converge rapidly to the true conditional probabilities, with total expected error bounded by the generator's Kolmogorov complexityKolmogorov complexity, n.: How briefly something can be described by a computer program that recreates it exactly: a million zeros needs only a tiny program, while a truly random string needs one about as long as itself.. The method is uncomputable — it would require running every program — but serves as a theoretical gold standard for induction, underpins Marcus Hutter's AIXIAIXI, prop. n.: A mathematical description of a perfect learning agent that weighs every possible explanation of its experience and acts to get the most future reward. It cannot actually be built, but it defines an ideal. model of a universally intelligent agent, and is cited in arguments that language modelslarge language model, n.: A computer program trained on enormous amounts of text to predict the words that come next. At vast scale, that simple skill lets it chat, answer questions, translate, summarize and write code. trained on next-token predictionnext-token prediction, n.: The simple task most AI chatbots were trained on: given some text, guess the next small piece of it. Repeating that guess, piece by piece, produces whole answers. approximate a form of universal sequence prediction.
Solomonoff induction is the ideal; a pretrained transformer is at best a fast, crude approximation of it.
Origin
Developed by Ray Solomonoff, a participant in the 1956 Dartmouth workshop, in a 1960 technical report and in 'A Formal Theory of Inductive Inference' (Information and Control, 1964). His convergence theorem appeared in 1978, and Marcus Hutter's AIXI (2000) extended the framework from prediction to action.
Related
- Kolmogorov complexityKolmogorov complexity, n.: How briefly something can be described by a computer program that recreates it exactly: a million zeros needs only a tiny program, while a truly random string needs one about as long as itself.
- Occam's razorOccam's razor, n.: A rule of thumb for choosing between explanations: if two fit the evidence equally well, bet on the one that assumes less. In AI it motivates preferring simpler models, which are less likely to fit noise.
- AIXIAIXI, prop. n.: A mathematical description of a perfect learning agent that weighs every possible explanation of its experience and acts to get the most future reward. It cannot actually be built, but it defines an ideal.
- minimum description lengthminimum description length, n.: The principle that the best explanation of some data is the one that lets you write the data down most briefly, counting both the rule and its exceptions. Good theories compress.
- Bayesian inferenceBayesian inference, n.: Reasoning that treats unknowns as uncertain beliefs and updates them with evidence using Bayes' theorem. The result is not one answer but a range of answers, each with a probability.
- priorprior, n.: What you believe, and how strongly, before looking at the evidence in front of you. In AI it also means built-in assumptions that steer what a system learns.
Sources
- Solomonoff, R. J. (1964). A Formal Theory of Inductive Inference, Parts I and II. Information and Control, 7(1–2).
Mentioned in
inductive reasoninginductive reasoning, n.: Reasoning from particular examples to a general rule or prediction — every swan I have seen is white, so swans are probably white — which is useful but can always turn out wrong., Occam's razorOccam's razor, n.: A rule of thumb for choosing between explanations: if two fit the evidence equally well, bet on the one that assumes less. In AI it motivates preferring simpler models, which are less likely to fit noise., Turing machineTuring machine, n.: An imaginary, extremely simple computer — a read-write head moving along an endless tape — that Alan Turing used in 1936 to define exactly what can be computed at all., AIXIAIXI, prop. n.: A mathematical description of a perfect learning agent that weighs every possible explanation of its experience and acts to get the most future reward. It cannot actually be built, but it defines an ideal., Kolmogorov complexityKolmogorov complexity, n.: How briefly something can be described by a computer program that recreates it exactly: a million zeros needs only a tiny program, while a truly random string needs one about as long as itself., logical inductionlogical induction, n.: A mathematical method for giving sensible, steadily improving probabilities to math claims that haven't been proved or disproved yet, much as a betting market prices uncertain events., Marcus HutterMarcus Hutter, prop. n.: A German computer scientist who defined AIXI, a mathematical ideal of a perfectly intelligent agent, and who argues that compressing data well is a measure of intelligence., minimum description lengthminimum description length, n.: The principle that the best explanation of some data is the one that lets you write the data down most briefly, counting both the rule and its exceptions. Good theories compress., no free lunch theoremno free lunch theorem, n.: A mathematical result saying that no learning or search method is best for every possible problem: any method that wins on some problems must lose on others., Ray SolomonoffRay Solomonoff, prop. n.: An American mathematician who worked out an ideal mathematical recipe for predicting what comes next from past data, and who attended the 1956 meeting that launched AI., universal intelligenceuniversal intelligence, n.: A mathematical definition of intelligence as an agent's average ability to achieve goals across every possible environment, with simpler environments counting more.