David R Bickel
email: dbickel@uottawa.ca

Computable priors sharpened into Occam's razors

Keywords: algorithmic probability, Bayesian inference, entropy rate, Kolmogorov complexity, universal prior

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Two general formalisms for data analysis based on Bayes's theorem are standard Bayesian statistics and Solomonoff's approach to universal distributions under algorithmic information theory. The posterior probabilities available under the former are computable and explicitly represent previous knowledge in terms of probability distributions. While lacking those advantages, Solomonoff's use of universal distributions implements Occam's razor by assigning more prior probability to sequences of symbols that are simpler in the sense of having lower Kolmogorov complexity (see [START_REF] Solomonoff | Complexity-based induction systems: Comparisons and convergence theorems[END_REF][START_REF] Solomonoff | The probability of 'undefined' (non-converging) output in generating the universal probability distribution[END_REF].

In this note, the two approaches are combined to make their advantages simultaneously applicable to data analysis, inference, and decision. The complexity of each stochastic process under consideration will determine its prior probability for Bayesian inference and decision making consistent with Occam's razor.

That prior probability of a process will be defined as the limit of its probability that an observation coincides with a symbol distributed according to a universal prior under algorithmic information theory.

To make that precise, consider a stationary process X θ,1 , X θ,2 , . . . such that the law of X θ,t is a probability mass function f θ,t on a finite alphabet X for all t = 1, 2, . . . and for each parameter value θ in a set Θ. Strings, finite sequences of τ symbols (Nies, 2012, §1.2), are written as X τ θ = (X θ,1 , . . . , X θ,τ ). The length of any string x is (x); thus, (X τ θ ) = τ . Throughout, log = log 2 . Convergence in probability and weak convergence as τ → ∞ are both denoted by weak ---→ (see Billingsley, 1999, p. 27).

Let ϑ denote a random variable with distribution π 0 , a probability measure on the measurable space (Θ, H), where H is a σ-field of subsets of Θ. For any H ∈ H, π 0 (H) is then P (ϑ ∈ H), the probability of the hypothesis that the process X ϑ,1 , X ϑ,2 , . . . is in {(X θ,1 , X θ,2 , . . . ) : θ ∈ H}. Since π 0 enables but does not depend on the complexity considerations of Occam's razor, it is called the blunted prior distribution. It is used below to incorporate any application-specific information into the universal prior Q, defined such that Q (x) is the algorithmic probability that a given prefix-free machine generates output x from a program consisting of independent and equally probable symbols [START_REF] Downey | Five lectures on algorithmic randomness[END_REF]Nies, 2012, §2.2;cf. Hutter, 2006, §2.4.1).

As a discrete semimeasure, the total probability mass of Q may be less than 1 (Downey and Hirschfeldt, 2010, §3.9). For that reason, normalization is required to transform Q to a probability mass function before applying standard probability theory. According to the universal probability mass function Q norm , 1 the conditional probability of a symbol following τ previous symbols based on Q is

Q norm (x τ +1 |x τ ) = Q norm x τ +1 Q norm (x τ ) ∝ Q x τ +1 Q (x τ ) , (1)
normalized such that y∈X Q norm (y|x τ ) = 1, as required for Q norm (•|x τ ) to be a probability mass function, for all x τ ∈ X τ (cf. Li and Vitányi, 2008, §4.5.3). While Q norm is incomputable and was originally intended for making predictions without any blunted π 0 or other explicit reliance on prior knowledge (see Rathmanner and Hutter, 2011, §10.1), the leverage of such a π 0 leads to a computable posterior distribution suitable for predictions and other Bayes actions, decisions that minimize posterior expected loss.

Let U θ,τ +1 be a random variable distributed according to the random probability mass function

Q norm (•|X τ θ )
for each θ ∈ Θ. (The randomness of Q norm (•|X τ θ ) comes from that of X τ θ and is meant in the sense of probability theory, not in the sense in which an individual string can be random.) For any H ∈ H and t = 1, 2, . . . , the τ -whetted probability π τ (H) and the whetted probability π (H) that ϑ ∈ H are defined by

π τ (H) = P (ϑ ∈ H|X ϑ,τ +1 = U ϑ,τ +1 ) (2) π (H) = π 0 (H) H dπ 0 (θ|H) 2 -H(θ) dπ 0 (θ) 2 -H(θ) , (3)
where the function H on Θ gives the entropy rate H (θ) = lim τ →∞ H (X θ,1 , . . . , X θ,τ ) / τ on the basis of the Shannon entropy H (X θ,1 , . . . , X θ,τ ) for each θ ∈ Θ. Equations ( 2)-(3) define two prior probability measures on (Θ, H), the τ -whetted distribution π τ and the whetted distribution π. Describing both with the same adjective will be justified by π τ weak ---→ π.

Example 1. Suppose Θ is the set of nonnegative integers. For any θ ∈ Θ and t = 1, 2, . . . , the τwhetted probability π τ (θ) and the whetted probability π (θ) that the process is X θ,1 , X θ,2 , . . . are, with

π 0 (θ) = π 0 ({θ}), π τ (θ) = π τ ({θ}) = P (ϑ = θ|X ϑ,τ +1 = U ϑ,τ +1 ) π (θ) = π ({θ}) = π 0 (θ) 2 -H(θ) i∈Θ π 0 (i) 2 -H(i) . ( 4
)
Example 2. In the finite-Θ setting, suppose X θ,1 , X θ,2 , . . . are mutually independent, Θ = X = {1, 2, . . . , m},

π 0 (θ) = 1/m, and f θ,t (x) = 1/θ if x ≤ θ but f θ,t (x) = 0 if x > θ for all θ, x = 1, 2, . . . , m and t = 1, 2, . . . .
The entropy rate H (θ) is the entropym x=1 f θ,t (x) log f θ,t (x) = log θ under independence. Thus, according to equation (4), the whetted distribution is given by π

(θ) ∝ m -1 2 -log θ = m -1 θ -1 .
Under ergodicity, the τ -whetted distribution converges to the whetted distribution, which is computable since π 0 and f θ,t are computable.

Theorem 1. If the process X θ,1 , X θ,2 , . . . is ergodic for every θ ∈ Θ, then π τ weak ---→ π.

Proof. Let H denote any continuity set in H. For any t = 1, 2, . . . ,

π τ (H) = P (ϑ ∈ H) P (U ϑ,τ +1 = X ϑ,τ +1 |ϑ ∈ H) P (U ϑ,τ +1 = X ϑ,τ +1 ) = π 0 (H) H dπ 0 (θ|H) P (U θ,τ +1 = X θ,τ +1 ) P (U ϑ,τ +1 = X ϑ,τ +1 ) . ( 5
)
The key factor is H dπ 0 (θ|H) P (U θ,τ +1 = X θ,τ +1 ), in which

P (U θ,τ +1 = X θ,τ +1 ) = x∈X P (X θ,τ +1 = x) P (U θ,τ +1 = X θ,τ +1 |X θ,τ +1 = x) = x∈X f θ,τ +1 (x) P (U θ,τ +1 = x|X θ,τ +1 = x) = x∈X f θ,τ +1 (x) E (Q norm (x|X τ θ ) |X θ,τ +1 = x) = E (Q norm (X θ,τ +1 |X τ θ )) = E Q norm (X θ,τ +1 ) Q norm (X τ θ ) (6)
for all θ ∈ H, with the last step from equation (1). Since X θ,1 , X θ,2 , . . . is an ergodic process,

K (X τ θ | τ ) / τ weak ---→ H (θ),
where K (x| τ ) is the prefix Kolmogorov complexity of a sequence x conditional on (x) = τ [START_REF] Horibe | A note on Kolmogorov complexity and entropy[END_REF]. Li and Vitányi, 2008, p. 605), for there are constants c 1 , c 2 > 0 that satisfy Li and Vitányi (2008, p. 119), and the upper bound from Cover and Thomas (2006, Theorem 14.2.3); cf. Li and Vitányi (2008, p. 204). Writing o P (U τ )

That implies K (X τ θ ) / τ weak ---→ H (θ) (cf.
K (x τ | τ ) -c 1 ≤ K (x τ ) ≤ K (x τ | τ ) + 2 log τ +c 2 ∀x τ ∈ X τ with the lower bound from K (x τ | τ ) ≤ K (x τ ) + c 1 , following
for any random sequence such that o P (U τ ) /U τ weak ---→ 0 given a random sequence U τ (Serfling, 1980, §1.2.5),

K (X τ θ ) τ = K (X τ θ | τ ) τ + o P (1) = H (θ) + o P (1) . (7)
The coding theorem (e.g., Downey, 2008, Theorem 2.8;Nies, 2012, Theorem 2.2.25) entails that there are a c 3 > 0 and a c 4 > 0 satisfying

K (x τ ) -c 3 ≤ -log Q (x τ ) ≤ K (x τ ) + c 4 . That yields (-log Q (X τ θ ) -K (X τ θ )) / τ
weak ---→ 0 and thus, with equation ( 7),

-log Q (X τ θ ) τ = K (X τ θ ) τ + o P (1) = H (θ) + o P (1) . ∴ -log Q X τ +1 θ -(-log Q (X τ θ )) = (τ +1) K X τ +1 θ τ +1 + o P (1) -τ K (X τ θ ) τ + o P (1) = (τ +1) (H (θ) + o P (1)) -τ (H (θ) + o P (1)) weak ---→ H (θ) .
The continuous mapping theorem then yields

Q X τ +1 θ Q (X τ θ ) = 2 -(-log Q(X τ +1 θ )-(-log Q(X τ θ ))) weak ---→ 2 -H(θ) . ∴ lim τ →∞ P (U θ,τ +1 = X θ,τ +1 ) ∝ 2 -H(θ)
according to equation (6) since exp -Q X τ +1 θ -Q (X τ θ ) is bounded. From equation ( 5), π τ (H) converges to a quantity proportional to π 0 (H) H dπ 0 (θ|H) exp (-H (θ)). Since dπ τ (θ) = 1 for all τ = 1, 2, . . . , it follows that π τ (H) → π (H) for every continuity set H in H. The portmanteau theorem makes that equivalent to π τ weak ---→ π.

Since θ → 2 -H(θ) in equation ( 3) is mathematically equivalent to a likelihood function and yet does not depend on any data, it is an example of a prior likelihood function, the logarithm of which is a "prior support" function as defined by [START_REF] Edwards | Likelihood[END_REF]. As likelihood is defined only up to a multiplicative constant, •) for any c > 0 may be called the whetted likelihood function. It relates the whetted and blunted probability densities by (dπ/dη) (θ) ∝ L (θ) (dπ 0 /dη) (θ) for any θ ∈ Θ , where η is any measure that dominates π 0 and π. In the sense that the use of the whetted likelihood justifies the frequent claim that the prior probability density should be higher for simpler hypotheses, it resembles the simplicity postulate, which requires laws with fewer free parameters to have higher prior probabilities (Jeffreys, 1948, pp. 100-101).

L (•) = c2 -H(
Example 3. Let X θ,1 , X θ,2 , . . . denote independent Bernoulli variates of unknown probability θ of success.

By independence, the entropy rate -θ) is the dashed curve in Figure 1. The other two plotted curves are the products of L (θ) and the likelihood functions of the binomial distribution for n = 1 and n = 10 observations, all successes. (The finite sample size n should not be confused with τ , which goes to infinity.) If π 0 is uniform, the density of π is proportional to L (θ), differing markedly from Jeffreys's prior density, instead proportional Robert et al., 2012, p. 73), and the posterior density is proportional to the likelihood functions in Figure 1.

H (θ) is the entropy, -θ log θ -(1 -θ) log (1 -θ). The resulting whetted likelihood L (θ) = θ θ (1 -θ) (1
to θ -1/2 (1 -θ) -1/2 (
Example 4. Consider the two-state Markov chain X θ,1 , X θ,2 , . . . with probability transition matrix

   1 -θ θ φ 1 -φ    ,
where θ has a uniform blunted prior distribution π 0 and φ is known. The entropy rate of the process is

H (θ) = φ θ + φ (-log Λ (θ)) + θ θ + φ (-log Λ (φ)) ,
where (Cover and Thomas, 2006, pp. 73, 78), which is the whetted likelihood function of Example 3. The whetted prior distribution is determined by

Λ (•) = • • (1 -•) (1-•)
π (θ) ∝ L (θ) = (Λ (θ)) φ θ+φ (Λ (φ)) θ θ+φ .
To extend the whetted distribution to continuous random variables, let Y θ,1 , Y θ,2 , . . . denote a stationary process such that, for all θ ∈ Θ and t = 1, 2, . . . , the distribution of Y θ,t is a Riemann-integrable probability density function g θ,τ on an interval Y for all τ = 1, 2, . . . . The differential whetted probability π (H) that

ϑ ∈ H is π (H) = π 0 (H) H dπ 0 (θ|H) 2 -h(θ) dπ 0 (θ) 2 -h(θ) , in which h (θ) is the differential entropy rate h (θ) = lim τ →∞ h (Y θ,1 , . . . , Y θ,τ ) / τ , where h (Y θ,1 , . . . , Y θ,τ ) is
the differential entropy of Y θ,1 , . . . , Y θ,τ for every θ ∈ Θ. In analogy with L, the function

θ → L (θ) = c2 -h(θ)
for any c > 0 is called the differential whetted likelihood function.

Example 5. Suppose Y θ,1 , Y θ,2 , . . . are independent variates drawn from the normal distribution with unknown mean µ and unknown standard deviation σ, where θ = (µ, σ). Invariant measures that are limits of prior probability density functions include the left Haar measure and the right Haar measure, with densities proportional to σ -2 and σ -1 , respectively [START_REF] Kass | The selection of prior distributions by formal rules[END_REF]. Since 2 h(µ,σ) ∝ σ [START_REF] Michalowicz | Handbook of Differential Entropy[END_REF], the whetted likelihood is L (µ, σ) ∝ σ -1 . Thus, if π 0 is the right Haar measure, then π is the left Haar measure, having a density proportional to L (µ, σ) σ -1 ∝ σ -2 . Using that π as the prior, the posterior predictive distribution of the next observation after observing n observations of sample mean µ and unbiased sample variance σ 2 is the t distribution with parameters µ, 1 -n -1 σ 2 , and n -1 (Held and Sabanés Bové, 2014, p. 301). Since the posterior distribution has a mean of µ, the Bayes estimate of µ under squared error loss is µ since that minimizes the posterior expected loss using π as the prior. Like π of Example 3, this π applies to small n as well as to large n.

The differential whetted probability is a limit of the following whetted probabilities that are themselves limits in the sense of Theorem

1. Y 1 , Y 2 , . . . is a sequence of interval subsets of Y ∞ such that Y i ⊂ Y j for i < j, and Y i (∆) is a partition of Y i into intervals of width ∆ > 0 for i = 1, 2, . . . and for i = ∞, where Y ∞ = Y. Denote by X θ,i,∆,t a random member of Y i (∆) with probability masses P (X θ,i,∆,t = Y ) = P (X θ,t ∈ Y |X θ,t ∈ Y i )
for all Y ∈ Y i (∆), θ ∈ Θ, and t = 1, 2, . . . . The entropy H (X θ,i,∆,1 , . . . , X θ,i,∆,τ ) and the whetted distribution for X θ,i,∆,1 , X θ,i,∆,2 . . . are abbreviated by H (θ, i, ∆, τ ) and π i,∆ , respectively. That whetted distribution converges to π, the differential whetted distribution, in the following sense.

Figure 1 :

 1 Figure 1: Likelihood functions for the binomial probability as θ. The whetted likelihood function is combined with the likelihood function for n = 0 (dashed), n = 1 (dotted), and n = 10 (solid) consecutive successes.

Proposition 1 .H

 1 If lim i→∞ H (θ, i, ∆, τ ) = H (θ, ∞, ∆, τ ) for all ∆ > 0 and τ = 1, 2, . . . i, ∆, τ ) + log ∆ for all θ ∈ Θ, then, for all H ∈ H,lim ∆→0 lim i→∞ π i,∆ (H) = π (H) . Proof. Since g θ,τ is Riemann integrable for all θ ∈ Θ and τ = 1, 2, . . . , lim ∆→0 H (θ, ∞, ∆, τ ) + log ∆ = h (Y θ,1 , . . . , Y θ,τ )(Cover and Thomas, 2006, Theorem 8.3.1). Thus, H (θ, i, ∆, τ ) + log ∆ → h (Y θ,1 , . . . , Y θ,τ ) and, with H (θ, i, ∆, τ ) / τ → H (θ, i, ∆), which is the entropy rate of the process X θ,i,∆,1 , X θ,i,∆,2 , . . . , (θ, i, ∆, τ ) + log ∆ / τ= lim τ →∞ h (Y θ,1 , . . . , Y θ,τ ) / τ = h (θ) . Substituting lim ∆→0 lim i→∞ H (θ, i, ∆) for H (θ)in equation (3) completes the proof. This research was partially supported by the Natural Sciences and Engineering Research Council of Canada (RGPIN/356018-2009) and by the Faculty of Medicine of the University of Ottawa.