Kolmogorov, Solomonoff, and de Finetti

This is a nice historical article that connects a number of key figures in the history of probability and information theory. See also Frequentists and Bayesians, Jaynes and Bayes, and On the Origin of Probability in Quantum Mechanics.

Induction: From Kolmogorov and Solomonoff to De Finetti and Back to Kolmogorov
John J. McCall DOI: 10.1111/j.0026-1386.2004.00190.x

ABSTRACT This paper compares the solutions to “the induction problem” by Kolmogorov, de Finetti, and Solomonoff. Brief sketches of the intellectual history of de Finetti and Kolmogorov are also composed. Kolmogorov's contributions to information theory culminated in his notion of algorithmic complexity. The development of algorithmic complexity was inspired by information theory and randomness. Kolmogorov's best-known contribution was the axiomatization of probability in 1933. Its influence on probability and statistics was swift, dramatic, and fundamental. However, Kolmogorov was not satisfied by his treatment of the frequency aspect of his creation. This in time gave rise to Kolmogorov complexity. De Finetti, on the other hand, had a profound vision early in his life which was encapsulated in his exchangeability theorem. This insight simultaneously resolved a fundamental philosophical conundrum—Hume's problem, and provided the bricks and mortar for de Finetti's constructive probabilistic theory. Most of his subsequent research involved extensions of his representation theorem. De Finetti was against determinism and celebrated quantum theory, while Kolmogorov was convinced that in every seemingly indeterministic manifestation there lurked a hidden deterministic mechanism. Solomonoff introduced algorithmic complexity independently of Kolmogorov and Chaitin. Solomonoff's motivation was firmly focused on induction. His interest in induction was to a marked extent sparked by Keynes’ 1921 seminal book. This interest in induction has never faltered, remaining prominent in his most recent research. The decisive connection between de Finetti and Kolmogorov was their lifelong interest in the frequency aspect of induction. Kolmogorov's solution to the problem was algorithmic complexity. De Finetti's solution to his frequency problem occurred early in his career with the discovery of the representation theorem. In this paper, we try to explain these solutions and mention related topics which captured the interest of these giants.

Excerpt below from the paper. I doubt Nature (evolution) uses Solomonoff's Universal Prior (determined by minimum length programs), as it is quite expensive to compute. I think our priors and heuristics are much more specialized and primitive.

... There are a host of similarities and equivalences joining concepts like Shannon entropy, Kolmogorov complexity, maximum entropy, Bayes etc. Some of these are noted. In short, the psychological aspects of probability and induction emphasized by de Finetti, Ramsey and Keynes may eventually emerge from a careful and novel neuroscientific study. In this study, neuronal actors would interact as they portray personal perception and mem- ories. In this way, these versatile neuronal actors comprise the foundation of psychology.

... In comparing de Finetti and Kolmogorov one becomes entangled in a host of controversial issues. de Finetti was an indeterminist who championed a subjective inductive inference. Kolmogorov sought determinism in even the most chaotic natural phenomena and reluctantly accepted a frequency approach to statistics, an objective science. In the 1960s Kolmogorov questioned his frequency position and developed algorithmic complexity, together with Solomonoff and Chaitin. With respect to the frequency doubts, he would have been enlightened by de Finetti’s representation theorem. The KCS research remains an exciting research area in probability, statistics and computer science. It has raised a whole series of controversial issues. It appears to challenge both the frequency and Bayesian schools: the former by proclaiming that the foundations of uncertainty are to be found in algorithms, information and combinatorics, rather than probability; the latter by replacing the Bayes prior which differs across individuals in accord with their distinctive beliefs with a universal prior applicable to all and drained of subjectivity.