Ray Solomonoff

• 1. Introduction

  ›

  Ray Solomonoff was born on the 25th of July 1926 in Cleveland, Ohio, and by the time he was 16 years old, he had already set himself an extraordinary task: to find a general method for solving mathematical problems. Not a specific problem, not a class of problems, but a method for all of them. That ambition would drive him for the next seven decades.

  At 16, most people are learning algebra. Solomonoff was asking whether machines could one day think. He would go on to write the first papers on probabilistic machine learning, lay the mathematical foundations for a form of artificial intelligence that rivals how humans learn from experience, and publish an idea so far ahead of its time that a Russian mathematician independently arrived at the same place five years later, and the world credited the Russian instead.

  Who was Ray Solomonoff? How did a boy from Cleveland reshape the foundations of probability, computation, and artificial intelligence? And why did the scientific community spend decades looking past what he had built?

• 2. Chicago and the Dartmouth Summer

  ›

  From 1947 to 1951, Solomonoff studied at the University of Chicago under professors including Rudolf Carnap and Enrico Fermi, earning a Master of Science in Physics in 1951. The company he kept there speaks to the intellectual environment that shaped him: Fermi, the architect of the first nuclear reactor; Carnap, one of the great philosophers of science.

  In 1952 he met Marvin Minsky and John McCarthy, two figures who would become central to the birth of artificial intelligence. Four years later, in 1956, Minsky and McCarthy organized what would become a pivotal event in the history of computing: the Dartmouth Summer Research Conference on Artificial Intelligence. Solomonoff was among the original ten invitees, and he, McCarthy, and Minsky were the only ones to stay the entire summer. It was in that gathering that the term Artificial Intelligence was first used to name a science.

  The computers of 1956 could solve narrow, specific mathematical problems and not much more. Solomonoff arrived at Dartmouth already holding a different question: not how to make a machine perform a task, but how to make a machine learn. He circulated a report among the attendees titled "An Inductive Inference Machine", which framed machine learning as a probabilistic process and emphasized the importance of training sequences. A published version followed in 1957. These were the first papers ever written on probabilistic machine learning.

  Before he left for Dartmouth, he and Anatol Rapoport had already co-authored papers in 1950-52 that are now regarded as the earliest statistical analysis of networks.

• 3. Algorithmic Probability

  ›

  In February 1960, Solomonoff circulated a report titled "A Preliminary Report on a General Theory of Inductive Inference." He also presented these results at a conference at Caltech that same year. What he had worked out was a new way of defining probability itself.

  Before the 1960s, probability was typically calculated by frequency: the ratio of favorable outcomes to total trials. Solomonoff discarded that foundation and replaced it with something more powerful. He asked how simple a description of an observed sequence could be, and assigned probability based on that simplicity. A sequence with a very short binary description was assigned a high probability; a sequence requiring N digits in its shortest binary description received a probability of 2 to the negative N.

  This was Algorithmic Probability, a mathematically rigorous fusion of Occam's razor and what Solomonoff called the Principle of Multiple Explanations. Rather than picking the single best explanation for an observation, the method assigned weights to every possible explanation, with simpler explanations weighted more heavily. Adding up the predictions of all those models, weighted by the lengths of their descriptions, produced a probability distribution for what would happen next. This procedure became known as Solomonoff Induction.

  In his 1960 paper, he wrote directly about the core idea: "Consider a very long sequence of symbols... We shall consider such a sequence of symbols to be 'simple' and have a high a priori probability, if there exists a very brief description of this sequence." His 1964 publications, "A Formal Theory of Inductive Inference" Part I and Part II, gave the full treatment, presenting five different models, including what would later be called the Universal Distribution.

• 4. Kolmogorov's Shadow

  ›

  In 1965, the Soviet mathematician Andrei Kolmogorov independently published ideas that overlapped significantly with what Solomonoff had already established. When Kolmogorov became aware of Solomonoff's work, he acknowledged it. For several years after that acknowledgment, Solomonoff's work was actually better known in the Soviet Union than in the Western world, which was a striking inversion of what one might expect.

  The scientific community nonetheless settled into a convention that attached Kolmogorov's name to the complexity measure. The reasoning, such as it was, came down to a difference of focus: Kolmogorov was primarily concerned with the randomness of a sequence, while Solomonoff had been focused on prediction, on the extrapolation of a sequence forward in time. The community carved the credit accordingly, giving Kolmogorov the complexity and Solomonoff the induction.

  Solomonoff held a proof of the efficacy of Algorithmic Probability from 1968, but because of the lack of general interest in probabilistic methods at that time, he did not publish that proof until ten years later. The proof established what is called the convergence theorem. It showed that if any describable regularity exists in a body of data, Algorithmic Probability will eventually find it, with a relatively small sample. No other probability system was shown to be complete in this way.

  Completeness came at a price: the system is incomputable. Some algorithms, those that are partially recursive, can never be fully evaluated because the computation would never terminate. But Solomonoff argued this was a feature, not a defect, because those programs are still recognized as possible solutions rather than being silently excluded.

• 5. Probability's Long Exclusion

  ›

  Around 1984, at an annual meeting of the American Association for Artificial Intelligence, a formal conclusion was reached: probability was in no way relevant to artificial intelligence. That judgment, delivered at an official gathering of the field's practitioners, reflected a divide that had been widening for years.

  While Solomonoff had been developing the probabilistic branch of AI throughout the 1960s and 1970s, others who had attended the 1956 Dartmouth conference, including Newell and Simon, were building the dominant alternative: AI systems governed by if-then rules and explicit facts. That branch drew the most attention and resources. Researchers such as Pearl and Peter Cheeseman continued arguing that probability was essential to intelligence, but they were in the minority.

  The backlash to the 1984 ruling was swift enough that a protest group formed, and the following year a dedicated workshop titled "Probability and Uncertainty in AI" was held at the AAAI meeting. That workshop has continued annually since. Solomonoff participated in the first one, presenting a paper on how to apply the universal distribution to problems in AI.

  At that workshop he also described the search technique he had developed. In search problems, the optimal order of search is determined by a ratio of the time needed to test a candidate solution divided by that solution's probability of success. He named this ratio the "Conceptual Jump Size" of the problem. He connected it to a related technique developed by Leonid Levin, which he called Lsearch.

• 6. Oxbridge Research and Later Work

  ›

  In 1970, Solomonoff founded a one-man company called Oxbridge Research, and conducted most of his subsequent work there. He also held periods at MIT, the University of Saarland in Germany, and the Dalle Molle Institute for Artificial Intelligence in Lugano, Switzerland.

  In 1985 he turned his attention to a larger question about AI's trajectory, writing a formula that predicted when artificial intelligence would reach what he called the "Infinity Point." This work placed him in the early history of thinking about what would later become known as the technological singularity.

  Over the following decades he extended the reach of his original framework. A 1999 report generalized the Universal Distribution and its convergence theorems to unordered sets of strings. A 2008 report extended the same to unordered pairs of strings. In 1997, 2003, and 2006 he argued that incomputability and subjectivity are both necessary and desirable properties of any high-performance induction system.

  In 2003 he became the first recipient of the Kolmogorov Award, given by the Computer Learning Research Center at the Royal Holloway, University of London. He delivered the inaugural Kolmogorov Lecture on that occasion, and later became a visiting professor at the same institution.

  In February 2008, he gave the keynote address at the Conference on Current Trends in the Theory and Application of Computer Science, held at Notre Dame University in Lebanon, and began research on new applications of Algorithmic Probability. In 2011, two years after his death on the 7th of December 2009, his final paper appeared in a volume titled "Randomness Through Computation: Some Answers, More Questions", alongside work by Gregory Chaitin and Jurgen Schmidhuber. In it, he reflected on the potential of Algorithmic Probability to achieve artificial general intelligence.