2.1. Sequential Prediction

We consider sequential prediction of binary digits (bits), elements of the set $B≔\{0,1\}$. Having witnessed a finite sequence σ of bits, we are to make a probability forecast, based on σ only, of what bit comes next; then this bit is revealed, and the procedure is repeated. Dawid (Reference Dawid1984) names it the prequential approach, for sequential prediction in a probabilistic fashion.

2.2. Computability and Effectiveness

This subsection introduces the basic notions from the theory of computability that we require in our setting of sequential prediction.Footnote ⁴

3.1. Step 1: The Predictor

A monotone machine is a particular kind of Turing machine that can be seen to execute an “online” operation: in the course of processing a continuous stream of input bits, it produces a potentially infinite stream of output bits. Formally, such a machine M has the property that for any extension ρ′ of any input sequence ρ (we write ρ ≼ ρ′), if M yields an output on ρ′ at all, it yields an output M(ρ′) that is also an extension of M(ρ) (so $M\left(\rho \right)\preccurlyeq M\left({\rho }^{\prime }\right)$). The monotone machine model suffers no loss of generality in what can be computed: every function calculable by a standard Turing machine is calculable by some monotone machine. The reason why this machine model is central to the theory is that the monotonicity property allows us to directly infer from each monotone machine a particular probabilistic source. We now proceed to do so for a universal monotone machine.

So suppose we have some universal monotone machine U, and suppose we feed it random bits for input: we repeatedly present it a 0 or a 1 with equal probability 0.5. For any sequence ρ, the probability that we in this way end up giving the machine a sequence starting with ρ only depends on the length |ρ|: this probability is 2^−|ρ|. Having processed ρ, the machine will have produced some output sequence. For a sequence σ of any length that starts this output sequence, we can say that input ρ has served as an instruction for U to produce σ. For this reason we call sequence ρ a U-description of σ.

We can now ask the question: If we feed machine U random bits, what is the probability that it will return the sequence σ? In other words, if we generate random bits, what is the probability that we arrive at some U-description of given σ? This probability is given by Solomonoff’s algorithmic probabilistic source.

We see that a sequence σ receives greater algorithmic probability Q_U(σ) as it has shorter descriptions ρ. The accompanying intuition is that σ receives greater algorithmic probability as it is more compressible. If we further accept this measure of compressibility as a general measure of simplicity of finite data sequences, then we can say that a sequence receives greater algorithmic probability as it is simpler.

By the formal equivalence of probabilistic sources and predictors (sec. 2.1), we can reinterpret an algorithmic probabilistic source as an algorithmic probability predictor. Given data sequence σ, the probability according to predictor Q_U of bit b showing next is the conditional probability $Q_U\left(b\right|\sigma )≔Q_U(\sigma b)/Q_U(\sigma )$.

Following the above intuition about data compression, the one-bit extension σb with the greatest algorithmic probability Q_U(σb) among the two possibilities σ0 and σ1 is the one that is the more compressible. Consequently, we see from the above equation that Q_U(b|σ) is greatest for the b such that σb is the more compressible. Hence, the algorithmic probability predictor Q_U will prefer the bit b that renders the complete sequence σb more compressible. This is, in the words of Ortner and Leitgeb (Reference Ortner, Leitgeb, Gabbay, Hartmann and Woods2011, 734), “evidently an implementation of Occam’s razor that identifies simplicity with compressibility.”

The above reasoning applies to the algorithmic probability predictor Q_U for any choice of universal Turing machine U. Since there are infinitely many universal machines, we have an infinite class of algorithmic probability predictors.

Let us denote $Q≔\{Q_U{\}}_U$ the class of algorithmic probability predictors via all universal machines U. Thus, we have specified a class of predictors $Q$ that possess a distinctive simplicity-qua-compressibility bias.

3.2. Step 2: The Reliability of the Predictor

The crucial result is that under a “mild constraint” on the presupposed actual data-generating source S*, we can derive a precise constant upper bound on the total risk of the predictor Q_U. The “mild constraint” on S* is that it is itself effective. It can be shown that this property guarantees that we can represent S* in terms of the behavior of some monotone machine M*, which in turn can be emulated by the universal monotone machine U. Then we can define a weight W_U(S*) that is a measure of how easily U can emulate M*, more precisely, how short the U-codes of M* are. This weight gives the constant bound on Q_U’s risk, as defined in section 2.1.

A direct consequence of the constant bound on the total risk is that the predictions of Q_U must rapidly converge, with S*-probability 1, to the presupposed actual probability values given by probabilistic source S*.Footnote ⁷ With S*-probability 1, we have that $Q_U\left(b\right|X^{t-1}\left)\stackrel{t\to \infty }{\to }{S}^{*}\right(b\left|X^{t-1}\right)$.Footnote ⁸

Let us more precisely define a predictor P to be reliable for S* if, with S*-probability 1, its predictions converge to the actual conditional S*-probability values. Then, under the “mild constraint” of effectiveness of the actual source, the predictor Q_U is reliable. It would motivate the conclusion that Q_U is reliable “in essentially every case.”

3.3. The Complete Argument

Let me restate the full argument:

1. 1. Predictors in class $Q$ possess a distinctive simplicity-qua-compressibility bias.

2. 2. Predictors in class $Q$ are reliable in essentially every case.

3. ∴ Predictors that possess a simplicity-qua-compressibility bias are reliable in essentially every case.

Again, the conclusion of the argument asserts a connection between two seemingly distinct properties of predictors: a preference for simplicity and a general reliability. The establishment of this connection between a simplicity preference and a general reliability justifies the principle that a predictor should prefer simplicity, the principle of Occam’s razor.

Note, however, that compared to the statement of the argument at the beginning of this section, I have added a minor qualification to both of the steps. Both qualifications are actually very much related, and spelling them out will show that the two properties are not so distinct after all. At heart, it is this fact that makes the conclusion of the argument fail to justify Occam’s razor. In order to make all of this explicit, I now turn to the framework of Bayesian prediction.

4.1. Bayesian Predictors

Bayesian prediction sets off with the selection of a particular class $S$ of probabilistic sources, which serves as our class of hypotheses. (I here restrict discussion to hypothesis classes that are countable.) Next, we define a prior distribution (or weight function) $W:S\to [0,1]$ over our hypothesis class. The prior W is to assign a positive weight to the hypotheses and only the hypotheses in $S$. An equally valid way of looking at things is that the definition of a particular prior W induces a hypothesis class $S$, simply defined as the class of hypotheses that receive a positive prior. In any case, we have $W\left(S\right)>0\iff S\in S$.

Following Howson (Reference Howson2000) and Romeijn (Reference Romeijn2004), the prior embodies our inductive assumption. If induction, in our setting of sequential prediction, is the procedure of extrapolating a pattern in the past to the future, then the lesson of the new riddle of induction (Goodman Reference Goodman1955; also see Stalker Reference Stalker1994) is that there is actually always a multitude of candidate patterns. One can therefore only perform induction relative to a particular pattern or a hypothesis that represents a pattern that we have seen in the past data and that we deem projectable in the future. From a Bayesian perspective, the hypotheses that we give a positive prior represent the potential patterns in the data that we deem projectable; the other hypotheses, receiving prior 0, represent the patterns that we exclude from the outset. The great merit of the Bayesian framework is that it locates our inductive assumption very precisely, namely, in the prior.

We are now in the position to define a Bayesian prediction method. It is a prediction method that operates under the inductive assumption of the corresponding prior W.

Given data sequence σ, the probability according to $P_W^S$ of bit b appearing next is the conditional probability $P_W^S\left(b\right|\sigma )=P_W^S(\sigma b)/P_W^S(\sigma )={\sum }_{S\in S}W(S\left|\sigma \right)S\left(b\right|\sigma )$.

4.2. The Consistency of Bayesian Predictors

To operate under a particular inductive assumption means to predict well whenever the data stream under investigation follows a pattern that conforms to this inductive assumption. More precisely, if a Bayesian predictor operates under a particular inductive assumption, embodied by a prior over a particular hypothesis class $S$, it will predict well whenever some hypothesis $S\in S$ fits the data stream well: whenever the data stream is probable according to some $S\in S$. More precisely still, the predictor will from some point on give a high probability to each next element of a data stream whenever there is some $S\in S$ that has done and keeps on doing so.

This property is closely related to the property of predicting well whenever the data are in fact generated by some source $S^{*}\in S$. If by “predicting well” we mean converging (with probability 1) to the true conditional probabilities, then this is again the property of reliability (sec. 3.2).

We can prove that any Bayesian predictor, operating under the inductive assumption of $S$, is reliable under the assumption that the data are indeed generated by some source $S^{*}\in S$. Indeed, we can derive a result completely parallel to theorem 1 on the total risk (as defined in sec. 2.1) of the Bayesian predictors:Footnote ⁹

Again, this bound on the total risk of $P_W^S$ entails its convergence to S*. For every actual S* that is indeed a member of the hypothesis class $S$, the predictions of the Bayesian predictors $P_W^S$ will converge with S*-probability 1 to the actual probability values given by S*. This is called the consistency property of Bayesian predictors.

4.3. The Effective Bayesian Predictors

Recall that the second step of the argument for Occam’s razor relied on the “mild assumption” of effectiveness. This is an inductive assumption. In the Bayesian framework, we can explicitly define the class of predictors that operate under this inductive assumption.

Let $S_{\text{eff}}$ be the class of probabilistic sources that are effective. The inductive assumption of effectiveness is expressed by any prior W that assigns positive weight to the elements and only the elements of this class. If we moreover put the constraint of effectiveness on the prior W itself, the resulting Bayesian mixture predictor $P_W^{S_{\text{eff}}}$ will itself be effective. A predictor of this kind we call an effective Bayesian mixture predictor, or effective mixture predictor for short.Footnote ¹⁰

Let $R≔\{P_W^{\text{eff}}{\}}_W$ denote the class of effective mixture predictors via all effective priors W, that is, the class of all effective mixture predictors.

5.1. The Theorem

The crucial fact is that definition 3 of the effective mixture predictor is equivalent to definition 1 of the algorithmic probability predictor. Recall that $Q=\{Q_U{\}}_U$ denotes the class of algorithmic probability predictors via all universal monotone Turing machines U and that $R=\{P_W^{\text{eff}}{\}}_W$ denotes the class of effective mixture predictors via all effective priors W. Then:

Thus, every algorithmic probability predictor via some U is an effective mixture predictor via some W and vice versa.Footnote ¹¹

Among the philosophical fruits of theorem 3 is the light it sheds on the discussion about the element of subjectivity in the definition of the algorithmic probabilistic source. I spell this out in section 5.3; to prepare the ground I first discuss the origin of Solomonoff’s work in Carnap’s early program of inductive logic.

5.2. Algorithmic Probability as an Objective Prior

Solomonoff makes explicit reference to Carnap (Reference Carnap1950) when he sets out his aim: “we want c(a, T), the degree of confirmation of the hypothesis that [bit] a will follow, given the evidence that [bit sequence] T has just occurred. This corresponds to Carnap’s probability₁” (Reference Solomonoff1964, 2). Solomonoff’s restriction of scope to what we have been calling sequential prediction aligns with Carnap’s position that “predictive inference is the most important kind of inductive inference” (Reference Carnap1950, 568), from which other kinds may be construed as special cases. Carnap’s “singular predictive inference,” which is “the most important special case of the predictive inference” (568), concerns the degree of confirmation bestowed on the singular prediction that a new individual c has property M by the evidence that s ₁ out of s individuals witnessed so far have this property M. If we translate this information into a bit sequence by simply writing 1 at the ith position for the ith individual having property M (and 0 otherwise), then we recover the problem of sequential prediction.Footnote ¹²

Solomonoff’s explication of degree of confirmation in our notation is the conditional algorithmic probability $Q_U\left(b\right|\sigma )=Q_U(\sigma b)/Q_U(\sigma )$, analogous to a Carnapian confirmation function $c$ that is defined by $c(h,e)≔m\left(h\right|e)=m(h\&e)/m(e)$ for an underlying regular measure function $m$ on sentences in a chosen monadic predicate language. To Carnap, the value $m\left(h\right)$ that equals the null confirmation $c_0\left(h\right)$ of h is “the degree of confirmation of h before any factual information is available” (Reference Carnap1950, 308), which he allows might be called the “initial probability” or the “probability a priori” of the sentence. Degree of confirmation is a “logical, semantical concept” (19), meaning that the value $c(h,e)$ is established “merely by a logical analysis of h and e and their relations” (20), independent of any empirical fact, and so the underlying null confirmation $c_0$ also corresponds to “a purely logical function for the argument h” (308). Thus, $c_0$ is an objective prior distribution on sentences, where its objectivity derives from its logicality (43).

Likewise, Solomonoff seeks to assign “a priori probabilities” to sequences of symbols; although the approach he takes is to “examine the manner in which these strings might be produced by a universal Turing machine” (Reference Solomonoff1964, 3), following an intuition about objectivity deriving from computation. The resulting explication of the null confirmation is the familiar algorithmic probabilistic source, which is indeed commonly referred to in the literature as the “universal a priori distribution” on the finite bit sequences.

5.3. The Element of Subjectivity

However, if the algorithmic probabilistic source is supposed to function as a “single probability distribution to use as the prior distribution in each different case” (Li and Vitányi Reference Li and Vitányi2008, 347), then it starts to look problematic that Q_U is not uniquely defined (cf. Solomonoff Reference Solomonoff, Kanal and Lemmer1986, 477; Hutter Reference Hutter2007, 44–45).

5.4. Reading the Representation Theorem

De Finetti’s celebrated representation theorem (Reference de Finetti1937/1964) states (translated to our setting of sequential bit prediction) the equivalence of a particular class of predictors, namely, those that are exchangeable (i.e., that assign the same probability to sequences with identical numbers of 0’s and 1’s), and a particular class of Bayesian mixtures, namely, those densities over the independently and identically distributed (i.i.d.) sources. Theorem 3 likewise states the equivalence of a particular class of predictors, the class of algorithmic probability predictors, and a particular class of Bayesian mixtures, the effective mixtures over the effective sources.

For de Finetti, the significance of his result was that “the nebulous and unsatisfactory definition of ‘independent events with fixed but unknown probability,’” that is, the notion of an underlying i.i.d. probabilistic source, could be abandoned for a “simple condition of ‘symmetry’ in relation to our judgments of probability,” that is, a property of our predictors (Reference de Finetti1937/1964, 142). In the interpretation of Braithwaite (Reference Braithwaite and Körner1957) and Hintikka (Reference Hintikka, Buck and Cohen1971), talk of general hypotheses, problematic from a strictly empiricist point of view, could be abandoned for constraints on methods of prediction. An allied sentiment about the dispensability of general hypotheses is expressed by Carnap (Reference Carnap1950, 570–75) and is subsequently embraced by Solomonoff: “I liked [Carnap’s confirmation function] that went directly from data to probability distribution without explicitly considering various theories or ‘explanations’ of the data” (Reference Lemmer1997, 76).

However, one could also reason the other way around (cf. Romeijn Reference Romeijn2004). Namely, a representation theorem that relates a particular class of Bayesian mixtures and a particular class of predictors, like de Finetti’s theorem or theorem 3, shows that this particular class of predictors operates under a particular inductive assumption. This is the inductive assumption that is codified in the priors of the Bayesian mixtures in this particular class: those patterns are assumed projectable that are represented by hypotheses that receive a nonzero prior. Thus, de Finetti’s representation theorem shows that the exchangeable predictors operate under the inductive assumption of an i.i.d. source, and theorem 3 shows that the algorithmic probability predictors operate under the inductive assumption of an effective source. It is essentially this insight that defuses the argument to justify Occam’s razor, as I show next.

6.1. The Argument Recast

By theorem 3, the following two formulations of step 1 of the argument to justify Occam’s razor are equivalent.

1. 1. Predictors in class $Q$ possess a distinctive simplicity-qua-compressibility bias.

2. 1. Predictors in class $R$ operate under inductive assumption of effectiveness.

Furthermore, since “in essentially every case” is to mean “under the assumption of effectiveness of the actual data-generating source,” theorem 1 about the bound on the total risk of the algorithmic probability predictors Q_U is equivalent to theorem 2 about the consistency of the Bayesian predictors, applied to the class of effective predictors $P_W^{\text{eff}}$. Hence, the following two formulations of step 2 are equivalent.

1. 2. Predictors in class $Q$ are reliable in essentially every case.

2. 2. Predictors in class $R$ are consistent.

If we make the property of consistency in step 2 explicit, the two steps of the argument look as follows.

1. 1. Predictors in class $R$ operate under inductive assumption of effectiveness.

2. 2. Predictors in class $R$ are reliable under assumption of effectiveness.

Taken together, the two steps yield the conclusion that predictors that operate under the inductive assumption of effectiveness are reliable under the assumption of effectiveness.

6.2. The Argument Defused

In the original formulation, we define a class of predictors with a distinctive simplicity bias that we can subsequently prove to be reliable “in essentially every case.” This formulation suggests that we have established a connection between two properties of a predictor that are quite distinct. We got out a general reliability, whereas we put in a specific preference for simplicity. This link between a simplicity bias and reliability provides an epistemic justification of Occam’s razor, the principle that a predictor should have a simplicity bias.

The more explicit reformulation shows that the original formulation is misleading. We got out what we put in, after all. We define a class of predictors that operate under the inductive assumption of effectiveness, which we can subsequently prove to be reliable under the very same assumption of effectiveness.

Indeed, a renewed look at the simplicity bias described in section 3.1 unveils the notion of simplicity involved as a peculiar one. The issue of subjectivity (sec. 5.3) concretely means that we can make any finite sequence arbitrarily “simple” by an apt choice of universal Turing machine, which is the common objection against the idea that algorithmic information theory can provide an objective quantification of the simplicity of finite sequences (cf. Kelly Reference Kelly, van Benthem and Adriaans2008, 324–25). Then this simplicity notion could only meaningfully apply to infinite data streams, with an interpretation of “asymptotic compressibility by some machine,” or, equivalently, “asymptotic goodness-of-fit of some effective hypothesis.” But this notion as a property of a predictor is really the expression of a particular inductive assumption (sec. 4.2), the inductive assumption of effectiveness. The upshot is that this property is certainly a simplicity notion in the weak sense in which any inductive assumption can be seen as a specific simplicity stipulation (if only for the plain reason that an assumption restricts possibilities), but it would require a whole new argument to make plausible that the particular assumption of effectiveness is somehow preferred in defining simplicity in this sense or even gives a simplicity notion in a stronger sense. And even if it could be argued that effectiveness yields such a privileged simplicity notion, it is still not effectiveness (hence not simplicity as such) that drives the connection to reliability: theorem 2 tells us that, at least for countable hypothesis classes, consistency holds for every inductive assumption that we formalize in W.

The conclusion is that the argument fails to justify Occam’s razor.