Ray Solomonoff (born 1926, Cleveland, Ohio, son of Russian immigrants) invented Algorithmic Probability in 1960. He first described his results at a Conference at Cal Tech, 1960,^[1] and in a report, "A Preliminary Report on a General Theory of Inductive Inference," in Feb., 1960.^[2] He clarified these ideas more fully in his 1964 publications, "A Formal Theory of Inductive Inference," Part I and Part II."^[3]

Although he is best known for Algorithmic Probability and his General Theory of Inductive Inference, he made other important discoveries in related fields. He wrote three papers, two with Rapoport, in 1950-52, that are regarded as the earliest statistical analysis of networks. He was one of the 10 attendees at the 1956 Dartmouth Summer Research Conference on Artificial Intelligence, a seminal event for artificial intelligence as a field. There he wrote "An Inductive Inference Machine", publishing a version in 1957^[4]. This was the first paper to be written on Machine Learning. He also invented probabilistic languages in the late 1950s.

His most important breakthrough, however, was the invention of Algorithmic Probability. Prior to the 1960s, the usual method of calculating probability was based on frequency: taking the ratio of favorable results to the total number of trials. In his 1960 publication, and, more completely, in his 1964 publications, Solomonoff seriously revised this definition of probability. He called this new form of probability "Algorithmic Probability."

What was later called Kolmogorov Complexity was a side product of his General Theory. He described this idea in 1960: "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 - using, of course, some sort of stipulated description method. More exactly, if we use only the symbols 0 and 1 to express our description, we will assign the probability 2^-N to a sequence of symbols if its shortest possible binary description contains N digits."^[5]

Five years later, in 1965, the Russian mathematician Kolmogorov independently presented a similar idea. When he became aware of Solomonoff's work, he acknowledged Solomonoff's priority, and for several years, Solomonoff's work was better known in the Soviet Union than in the Western World. The general consensus in the scientific community, however, was to associate this type of complexity with Kolmogorov, who was more concerned with randomness of a sequence. Algorithmic Probability became associated with Solomonoff, who was focussed on prediction - the extrapolation of a sequence.

Later in the same 1960 publication Solomonoff describes his improvement on the single-shortest-code theory. This is Algorithmic Probability. He states: "It would seem that if there are several different methods of describing a sequence, each of these methods should be given some weight in determining the probability of that sequence."^[6] He then shows how this idea can be used to generate the universal a priori probability distribution.

In the early 60s, he continued to write and enlarge his theory, publishing a number of reports leading up to his publications in 1964. Although his work at first was not widely known, over the years many people have come to recognize the importance and priority of his discoveries.

In 1968 he found a proof for the efficacy of Algorithmic Probability^[7], but mainly because of lack of general interest at that time, did not publish it until 10 years later. He showed that Algorithmic Probability was "complete"; that if there was any describable regularity in a body of data, that Algorithmic Probability would eventually discover that regularity, needing a relatively small sample of that data. Algorithmic Probability is the only probability system know to be "complete" in this way.In 1986 he described how Algorithmic Probability could be used in applications to A.I. ^[8]

In 1970 he formed his own one man company, Oxbridge Research, and has continued his research there except for short periods at other institutions such as MIT, University of Saarland in Germany and IDSIA in Switzerland. In 2003 he was the first recipient of the The Computer Learning Research Center's Kolmogorov award and gave the inaugural Kolmogorov lecture at Royal Holloway, University of London. Solomonoff is currently visiting Professor at the CRLC.

In 2006 he spoke at AI@50, "Dartmouth Artificial Intelligence Conference: the Next Fifty Years" commemorating the fiftieth anniversary of the original Dartmouth summer study group. Solomonoff was one of five original participants to attend.

Most recently, in Feb. 2008, he gave the keynote address at the Conference, "Current Trends in the Theory and Application of Computer Science" held at Notre Dame University in Lebanon. He followed this with a short series of lectures, and began research on new applications of Algorithmic Probability.

A description of Solomonoff's life and work prior to 1997 is in his paper "The Discovery of Algorithmic Probability", Journal of Computer and System Sciences, Vol 55, No. 1, pp 73-88, August 1997. This paper, as well as most of the others mentioned here, are available on his website at his publications page.

References

See also

• Kolmogorov complexity
• Inductive inference
• Ming Li and Paul Vitanyi, An Introduction to Kolmogorov Complexity and It's Applications. Springer-Verlag, N.Y., 1997, includes historical notes on Solomonoff as well as a description and analysis of his work.

External links

• Ray Solomonoff's Homepage
• For a detailed description of Algorithmic Probability, see "Algorithmic Probability" by Hutter, Legg and Vitanyi in the scholarpedia.

ru:?????????, ???