Solomonoff Induction and AIXI

Abstract

In 1960 Ray Solomonoff, one of the ten invitees to the 1956 Dartmouth workshop that named artificial intelligence, proposed a complete mathematical answer to the problem of induction: predict the next observation by considering every computer program that reproduces what has been seen so far, giving shorter programs more weight. The method, Solomonoff induction, provably learns any computable regularity and provably cannot be computed. In 2000 Marcus Hutter combined it with decision theory into AIXI, a formal definition of an optimal reinforcement-learning agent, equally uncomputable. Neither has ever been run. Both shaped how a part of the AI field thinks: Hutter’s student Shane Legg co-founded DeepMind, and the view that prediction and compression are the same thing reappeared in 2023 when DeepMind showed that a large language model trained on text compresses images better than PNG.

The Problem of Induction

Science and machine learning both face the question David Hume raised in the 18th century: having seen a sequence of observations, what should one expect next? There is no logical guarantee that the future resembles the past, and any finite sequence is consistent with infinitely many continuations. Statisticians answered with Bayes’ rule, which updates prior beliefs with evidence, but Bayes’ rule needs a prior, a starting assignment of probabilities to hypotheses, and offered no principled way to choose one.

Ray Solomonoff, born in Cleveland in 1926, studied physics at the University of Chicago, where his teachers included the philosopher Rudolf Carnap, who had spent years trying to build a logical theory of inductive probability. Solomonoff wanted a machine that learned. He was one of the ten people invited to the 1956 Dartmouth Summer Research Project on Artificial Intelligence and, with John McCarthy and Marvin Minsky, one of the only three who stayed for the whole summer (see John McCarthy and LISP). In 1957 he circulated “An Inductive Inference Machine,” one of the first papers on probabilistic machine learning.

The Universal Prior

In a report of February 1960, “A Preliminary Report on a General Theory of Inductive Inference,” and in the two-part paper “A Formal Theory of Inductive Inference” in Information and Control in 1964, Solomonoff proposed his answer. Fix a universal computer. Every hypothesis about how the observations were produced is a program for that computer. The prior probability of a sequence is the sum, over all programs whose output begins with that sequence, of 2 raised to the minus length of the program: a program one bit longer counts half as much. To predict the next observation, compare the prior probabilities of the possible continuations.

The scheme formalised two old principles at once. Every program consistent with the data keeps some weight. And shorter programs dominate, which is Occam’s razor stated as arithmetic. The choice of computer matters less than it might seem: changing it changes each program’s length by at most a constant, the length of a translator between the two machines.

Solomonoff’s measure, the length of the shortest program, is the quantity that Andrey Kolmogorov in 1965 and Gregory Chaitin in 1966 introduced independently as the information content of a string (see Kolmogorov Complexity and Gregory Chaitin). Solomonoff published first, but his framing was inductive inference rather than information, and for years he was the least known of the three.

Complete and Uncomputable

Solomonoff proved two things about his method. The first was completeness, in a form he proved in 1968 and published in 1978: if the observations are generated by any computable probabilistic process, the total expected error of the predictions, summed over the entire infinite future, is bounded by a constant depending only on the complexity of that process. The predictor learns any computable regularity, however complex, after a finite amount of evidence. No other prediction method has this property for all computable environments.

The second was that the method cannot be computed. Deciding whether a program produces a given output requires knowing whether it halts, which Alan Turing had shown in 1936 cannot be decided in general (see David Hilbert and the Entscheidungsproblem). The universal prior can be approximated from below, by running more and more programs for longer and longer, but never computed exactly, and Solomonoff showed that completeness and computability are mutually exclusive. He called the incomputability “of a very benign kind” that did not prevent practical approximation. He spent most of his career in his one-person company, Oxbridge Research, founded in 1970, working on such approximations. In 2003 he received the first Kolmogorov Award, and he died on 7 December 2009.

AIXI

Prediction is not action. An agent in the world must choose what to do, observe the consequences and collect rewards, and its actions change what it will observe. In 2000 Marcus Hutter, a German physicist and computer scientist then working at the IDSIA laboratory in Lugano, combined Solomonoff’s prior with sequential decision theory and defined AIXI. At each step, AIXI considers every computable environment consistent with its history, weights each by Solomonoff’s prior, and chooses the action that maximises the expected sum of future rewards across all of them. Hutter set out the theory in his 2005 book Universal Artificial Intelligence.

AIXI was offered as a definition rather than a program: a precise statement of what an ideally intelligent reinforcement-learning agent would do, against which practical systems could be measured. Hutter proved optimality properties for it, and his student Shane Legg used it to define intelligence itself. Their 2007 paper “Universal Intelligence: A Definition of Machine Intelligence,” in Minds and Machines, collected dozens of informal definitions from psychology and AI and formalised their common core as an agent’s expected performance across all computable environments, weighted by simplicity. Legg’s 2008 doctoral thesis at the Università della Svizzera italiana, Machine Super Intelligence, supervised by Hutter and Jürgen Schmidhuber, was built around AIXI. Two years later Legg co-founded DeepMind with Demis Hassabis and Mustafa Suleyman (see DeepMind and AlphaGo).

Computable approximations were built. Hutter defined AIXItl, bounded in time and program length. In 2009 Joel Veness, Hutter and colleagues built MC-AIXI-CTW, which replaced the space of all programs with a context-tree model and the exact expectation with Monte Carlo search, and showed it learning to play small games, among them a partially observable version of Pac-Man, from rewards alone.

Compression as Intelligence

Hutter argued that if prediction and compression are equivalent, as information theory implies (see Claude Shannon and Information Theory), then better compression of human knowledge is progress toward intelligence. On 6 August 2006 he announced the Hutter Prize: €50,000 for losslessly compressing a 100-megabyte extract of Wikipedia, enwik8, paying out for each improvement on the record. On 21 February 2020 both the file and the pool grew tenfold, to the 1-gigabyte enwik9 and €500,000. The winning entries were dominated by context-mixing compressors, ever larger ensembles of statistical models, which improved the record by around one percent at a time (see Data Compression).

The argument returned with large language models, which are trained to predict the next token and so are, in Shannon’s sense, compressors. In September 2023 a DeepMind team including Hutter and Veness published “Language Modeling Is Compression.” Used with arithmetic coding, the 70-billion-parameter language model Chinchilla, trained mostly on text, compressed ImageNet image patches to 43.4 percent of their raw size, against 58.5 percent for PNG, and LibriSpeech audio samples to 16.4 percent, against 30.3 percent for FLAC. (Counting the size of the model itself, which the Hutter Prize requires, would wipe out the gain many times over.)

Dead End: The Optimal Agent

AIXI’s promise was a theory from which intelligence could be derived, as thermodynamics derives engines. Its weakest point turned out to be the one that had seemed least important, the choice of universal computer. For prediction, Solomonoff’s invariance result made the choice irrelevant in the limit. For action it did not. In 2015 Jan Leike and Hutter showed, in “Bad Universal Priors and Notions of Optimality,” that some legitimate choices of reference machine make AIXI behave arbitrarily badly, for example a “dogmatic” prior under which it sticks to any fixed policy as long as rewards do not drop too far, and that under the Legg-Hutter measure every policy is optimal for some choice of machine. AIXI’s optimality was relative to an arbitrary starting point, and the earlier optimality claims were withdrawn.

The idealisation also assumes that the agent is separate from its environment and communicates with it only through actions and observations, so that it cannot reason about being modified or damaged, and that the environment is computable. The systems that came to dominate AI after 2012 were built from neural networks trained by gradient descent on large data sets, not derived from universal priors. What survived of the programme was a vocabulary, simplicity priors, prediction as compression and intelligence as performance across environments, and a set of people who carried it into the laboratories that built those systems.