TCS -TR-A-06-23

TCS Technical Report

Consistency Theorems for Discrete Bayesian Learning

by

J. Poland

Division of Computer Science
Report Series A
November 30, 2006

Hokkaido University

Graduate School ofInformation Science and Technology
Email:

jan@ist.hokudai.ac.jp

Phone:
Fax:+81-011-706-7675+81-011-706-7675

1Consistency Theorems for Discrete Bayesian Learning

TCS-TR-A-06-23

November 30, 2006

Consistency Theorems for Discrete
Bayesian Learning
Jan Poland∗
Graduate School of Information Science and Technology
Hokkaido University, Japan
jan@ist.hokudai.ac.jp
http://www-alg.ist.hokudai.ac.jp/∼jan

Abstract
Bayes’ rule specifies how to obtain a posterior from a class of hypotheses
endowed with a prior and the observed data. There are three fundamental ways to use this posterior for predicting the future: marginalization(integration over the hypotheses w.r.t. the posterior), MAP (taking the aposteriori most probable hypothesis), and stochastic model selection (selecting a hypothesis at random according to the posterior distribution). If
the hypothesis class is countable and contains the data generating distribution (this is termed the “realizable case”), strong consistency theorems are
known for the former two methods, asserting almost sure convergence ofthe predictions to the truth as well as loss bounds. We prove corresponding results for stochastic model selection, for both discrete and continuous
observation spaces. As a main technical tool, we will use the concept ofa potential: this quantity, which is always positive, measures the total
possible amount of future prediction errors. Precisely, in each time step,
the expected potential decrease upper bounds the expected error. We
introduce the entropy potential of a hypothesis class as its worst-case entropy with regard to the true distribution. Our results are proven within ageneral stochastic online prediction framework that comprises both online
classification and prediction of non-i.i.d. sequences.

1

Introduction“When you have eliminated the impossible, whatever remains must be the truth.” Thisfamous quote describes the induction principle of Sherlock Holmes, whose observations
and conclusions are always correct. Real world observations usually lack this desirable∗

This work was supported by JSPS 21st century COE program C01.

2

J. Poland

property, instead they are noisy. Thus, Bayes’ rule, eliminating the improbable, has
emerged as a successful induction principle in practice. The aim of this paper is tocollect and prove statements of the form: “When you have eliminated the improbable,
whatever remains is almost sure to behave like the truth.” We will give different but
tightly connected forms of this assertion: Asymptotic almost sure consistency results
and bounds on the error of a predictor based on Bayes’ rule.

1.1

Structure and contributions of this work

The main technical contribution of this paper, presented in Section 3, are several
proofs of consistency theorems for Bayesian stochastic model selection. This completes a series of recent performance guarantees obtained for all three fundamental
ways of Bayesian learning. It therefore motivates a comparative presentation of allthese results, discussing the basics of Bayesian learning, the fundamental variants ofBayesian induction, its scope of applicability, and the state of the art of Bayesianlearning theorems. This is subject of the next section.

2

Discrete Bayesian Learning

Bayes’ famous rule,

P (D|H) · P (H)
,
(1)
P (D)
says how the probability of a hypothesis H is updated after observing some data D.
Still, different specific induction setups can use Bayes’ rule. First, there are different
possibilities to define the input space, the observation space, and the hypothesis space.
Second, a hypothesis class endowed with a probability distribution can be used for
induction in principally three different ways.
P (H|D) =The reader should keep in mind that Bayes’ rule is no theorem in general. Under
the assumption that hypotheses and data are both sampled from a joint probability
distribution that coincides with the prior P (H), (1) would be a theorem. However,
Bayes’ rule is commonly not applied under such an assumption, in particular the
distribution P (H) on the hypotheses is usually merely a belief distribution, there is
no probabilistic sampling mechanism generating hypotheses assumed. Hence, Bayes’rule is motivated intuitively in the first place. Still, many optimality results andperformance guarantees have been shown for Bayesian induction (e.g. in [BD62, CB90,
BRY98]), including the results of the present work.

2.1

What to learn? Hypotheses, history, inputs, observation
spacesLet X be the observation space. We work in an online prediction setup in discretetime, that is, in each time step t = 1, 2, . . ., an observation xt ∈ X is revealed toConsistency Theorems for Discrete Bayesian Learning3

the learner. The task of the learner will be to predict xt before he observes it. One
question of fundamental technical impact concerns the structure of the observation
space X . We restrict our attention to the two most important cases of (a) X being
discrete (finite or countable) and (b) continuous X ⊂ Rd for suitable dimension d ∈ N.
As any discrete space can be mapped to a subset of Rd , it is technically sufficient to
restrict to X ⊂ Rd , which we will do in the following (except for a few places where
we explicitly deal with finite observation spaces).
A hypothesis ν specifies a probability distribution on the observation space X . In
the simplest case, it does not depend on any input, these hypotheses represent theassumption that the observed data is independently identically distributed (i.i.d.).
In all other cases, there is some input space Z, and a hypothesis maps inputs todistributions on X . In fact, technically, the inputs play no role at all, as we will seein the following. We therefore may assume the existence of an arbitrary input space
Z without any structure (which may consist of just one point, meaning that there are
no inputs at all), and inputs are generated by an arbitrary process. This covers (evenmore than) two of the most important learning setups: Classification, where the datais conditionally i.i.d. given the inputs, and prediction of non-i.i.d. sequences, wherein each time step t, we may define the input zt = (x1 , . . . , xt−1 ) to be the observation
history seen so far. Generally, we will denote the history of inputs and observationsbyh1:t−1 = h<t = (z1 , x1 , z2 , x2 , . . . , zt−1 , xt−1 )(observe that two pieces of notation have been introduced here).
Now, a hypothesis is formally defined as a function
ν : Z → M1D+C (X ).
Here, M1D+C (X ) denotes the probability distributions on X ⊂ Rd , that are mixtures of
discrete distributions (with nonzero mass concentrated on single points) and distributions with continuous density functions. We make this restriction mainly because wewish to be able to define all subsequent quantities, in particular Bayesian posteriors,
effortlessly1 and uniquely (except perhaps on a set of measure zero).2 In particular,
we haveZdν(·|z) = 1 for all z ∈ Z.
Note that we consistently use this integral notation, also for discrete observation space(in which case the integral is in reality a sum).
1

For instance, for a measure defined by a “devil’s staircase”, one has to spend additional effort
in order to define everything properly, which is not the aim of the present work. However, this andother cases can be treated with the methods described here.
2
The continuity assumption will be needed for the main proof in Section 3. It can be immediately
lifted and replaced by “uniform piecewise continuity”, which means that there is a single partitionof X such that the continuous parts of all distributions ν ∈ C and for all z ∈ Z are continuous oneach of the elements of the partition. Maybe it can be even further lifted.

4

J. Poland

A Bayesian learner is always based on a hypothesis class C = {ν1 , ν2 , . . .}. In thiswork with the title “discrete Bayesian learning”, we restrict to discrete, i.e. finite or
countable, hypothesis classes (and in the notation we assume a countable hypothesis
class from now on, without loss of generality). Before the learning process starts, eachPhypothesis ν ∈ C is endowed with a prior weight wν ∈ (0, 1), such that ν∈C wν = 1.
Hypothesis classes considered in statistics are usually continuously parameterized.
One motivation to study discrete classes is that they are technically simpler, so they
can serve as a basis for the more advanced continuous case. In the continuous case,some Bayesian predictors such as MAP (see below) are not consistent at all, whileothers such as MML (minimum message length) [WB68, WD99] and MDL (minimum
description length) [Ris96] require appropriate discretization. Also, countable hypothesis classes always admit stronger performance guarantees than possible for theircontinuously parameterized counterparts. In particular, we will be able to show almost sure consistency, whereas only convergence in probability holds in the continuous
case (e.g. in [BC91]).
Another particular motivation to consider discrete hypothesis classes arises in Algorithmic Information Theory. General continuous hypothesis classes are computationally not tractable. The largest hypothesis class which can be manipulated in thelimit by a computer, is the class of all computable hypotheses on some fixed universal
Turing machine, precisely prefix machine [LV97]. Thus each hypothesis corresponds
to a program, and there are countably many programs. Each hypothesis has a naturaldescription length, namely the length of the corresponding program. If we agree that
programs are binary strings, then a natural prior is defined by two to the negativedescription length.
If we are dealing with such a universal hypothesis class as defined in Algorithmic Information Theory, we need to be careful about the phenomenon of probability
leaks: A hypothesis, that is a program on our universal Turing machine, may not
produce output for certain inputs. Because of our inability of deciding the halting
problem, we cannot generally detect this case. As a consequence, there is no limitcomputable way of defining hypotheses that are proper probability distributions, they
are rather semimeasures. In this paper, we won’t address this issue further, instead wepoint to the references: Consistency theorems for the semimeasure case are known for
marginalization [Sol78, Hut04] and for MAP predictions [PH05], but not for stochastic
model selection. All of the probability distributions considered in this paper will beproper measures.
We rewrite Bayes’ rule (1) using new notation: For a hypothesis ν ∈ C, current
prior weights wν 0 (h<t ) of all hypotheses ν 0 ∈ C depending on the history h<t , input
zt , and observation xt , we set the posterior weight of ν to
ν(xt |zt ) · wν (h<t ),0ν 0 ∈C ν (xt |zt ) · wν 0 (h<t )wν (h1:t ) = P(2)Note that we actually need to distinguish three variants of Bayes’ rule (not to be
confused with the three variants of Bayesian prediction discussed below): In the caseConsistency Theorems for Discrete Bayesian Learning

5of discrete observation space, the quantities ν 0 (x|z) (and therefore also the sum inthe denominator) are probabilities, while for continuous observation space, they aredensities. Finally, if at least one hypothesis ν ∈ C is a mixture of a discrete and acontinuous distribution, then all ν 0 (x|z) must be treated as mixtures in the following
way: If for an observation x ∈ X , there is a hypothesis assigning non-zero mass tox, then the ν 0 (x|z) are treated as probabilities (and all hypotheses assigning merely
a non-zero density to that particular x will get posterior weight 0). Otherwise, theν 0 (x|z) are treated as densities.

2.2

How to learn? Three fundamental variants of Bayesianprediction

Given a set of hypotheses C and some observed data h1:t = (z1 , x1 , . . . , zt , xt ), a legitimate question is asking which of the hypotheses in C has actually generated the data.
It is clear that this question might not be well-defined if the process generating thedata, which we will call µ in the sequel, is not member of C. Actually, one can immediately construct examples where any Bayesian learner produces very undesirable
results in this non-realizable learning setup (see [GL04] for sophisticated examples).
In this work, we will restrict to the realizable case, where the true distribution generating the observations is contained in the class, µ ∈ C. (But recall that this only
refers to the distribution of the observation given the inputs, we do not need any
assumption on the generation of the inputs zt ). Of course, the learner does not know
in advance which element of C is the true distribution µ.
However, hypothesis identification has technical difficulties. For instance, consider
the case where two hypothesis are in C that make (almost) identical predictions, oneof them being the true one. Then it is (almost) impossible to identify the right one,but if we just want to make predictions, we need not care: Choosing any of the two
will yield (almost) perfect predictions.
So from now on, we restrict our focus to prediction. That is, for given historyh<t and current input zt ∈ Z, we are interested in a predictive distribution 3 on theobservation space X that comes as closely to the truth as possible. Our hypothesis¡¢
class endowed with the Bayesian posterior wν 0 (h<t ) ν 0 ∈C offers us three fundamental
ways to obtain such a prediction:
1. Marginalization. If we apply Bayes’ rule (1) to the modified setting where
the next observation xt takes the place of the hypothesis H, then, as an easycomputation shows, we get a predictive distribution ξ(xt |zt , h<t ) by integrating
the predictions of all hypotheses w.r.t. the current posterior:Xξ(x|zt , h<t ) =wν 0 (h<t )ν 0 (x|zt ).
(3)
ν 0 ∈C3

In many prediction tasks, a single value is required as prediction, rather than a distribution.
Such a single prediction can be derived from a predictive distribution, e.g. by minimizing a riskfunction, compare Corollary 5 below.

6

J. Poland

2. Maximum a posteriori (MAP). If we are interested in a single hypothesis’
prediction, then we may choose the hypothesis with maximal a-posteriori belief
value, abbreviated as MAP hypothesis:
νh∗<t = arg max{wν (h<t )} and

(4)

ν∈C

m(xt |zt , h<t ) = νh∗<t (xt |zt ),(5)

where the latter m(xt |zt , h<t ) is the MAP prediction.
3. Stochastic model selection. The third possibility is to randomize and sample
a hypothesis according to the probability distribution defined by the current
posterior. This stochastic model selection can be formally written asΞ(xt |zt , h<t ) = Ñ (xt |zt ) where Ñ ∈ C

(6)
0

0

and P(Ñ = ν ) = wν 0 (h<t ) for all ν ∈ C.
Note that for given history h<t , the first two methods are deterministic, resulting ina fixed predictive distribution. Stochastic model selection uses additional randomness.
There are other possibilities than the stated three to use a Bayesian hypothesis
class for prediction. MAP is tightly related to MML and MDL, but the terms MML
and MDL are (also) used for (slightly, in the case of discrete hypothesis class) different concepts [CD05, Ris96]. Also, there is a “dynamic” variant of MAP defined in[PH05], where a MAP hypothesis is chosen for each possible outcome xt and used forprediction. Anyway: many, if not most, Bayesian prediction methods can be roughly
grouped into the three fundamental “integrate over all hypothesis”, “take the hypothesis with the best current score”, and “select one hypothesis at random according to
the current belief distribution”. And we hold (but that is a matter of taste) that theabove representants are the simplest and most natural of the prediction methods toconsider.

2.3

Performance guarantees for Bayesian learners

We are now ready to state the performance guarantees for the three Bayesian learners
defined in (3), (5), and (6). We start with the technically easiest case of marginalization (3). Actually, this result has been originally discovered by Solomonoff [Sol78]
within the context of Algorithmic Information Theory.
Recall that µ ∈ C is the true distribution generating the data, and ξ is the marginalization predictor. The quadratic Hellinger distance between the ξ-predictions andµ-predictions at time t is given by
Z
p
¡p
¢2
2
∆t (µ, ξ) := d µ(·|zt ) − ξ(·|zt , h<t ) .
(7)
It clearly depends on the history h<t and the current input zt . Our main technicalresults are all stated as cumulative (i.e., over t = 1, . . . , ∞) bounds on the Hellinger
distance (that is, errors) of the predictive probabilities to the truth.

Consistency Theorems for Discrete Bayesian Learning

7

Theorem 1 If µ ∈ C, then for any sequence of inputs z1 , z2 , . . .,∞X

Eµ ∆2t (µ, ξ) ≤ log wµ−1

(8)

t=1

holds, where log denotes the natural logarithm and wµ is the prior weight of the true
distribution. Eµ refers to the fact that the expectation is taken w.r.t. the true distribution µ, i.e., all observations are generated w.r.t. µ conditional to the inputs, andthis expectation is computed.
Remark 2 The following convention is used throughout the paper: When we write
wµ , it always refers to the prior weight wµ (∅), with empty history. Posterior weights
are being denoted with explicit history, wµ (h<t ). This convention will extend to otherquantities, such as the entropy H or the entropy Π below. However, in the proofs
below, the history h<t at a given time t is often dropped for notational convenience.
In these cases, a notation like wµ refers to the current posterior weight.
It should not be surprising that the quantity wµ appears on the r.h.s. and therefore
has an impact on how large the error on the l.h.s. can grow. After all, if the Bayesianlearner assigns a high prior weight to the true distribution, the error should be small.
The remarkable fact is the logarithmic dependence in wµ . As by Kraft’s inequality, thelogarithm of a weight can be interpreted as its description length, (8) is a very strong
result asserting that the cumulative error never exceeds the description length of thetrue distribution. In a sense: When finding the truth single-handedly, our error is at
most the number of bits a teacher needs to tell us the truth. We will provide a proofof Theorem 1 at the beginning of Section 3, as an introduction for the subsequent
proof techniques.
Results for the MAP predictor (5) similar to Theorem 1 have been shown in [PH05].
Theorem 3 Assume µ ∈ C. Suppose that, for any history with nonzero probability
density, the hypotheses always admit the specification of a (not necessarily unique)
MAP hypothesis ν ∗ . This is satisfied for instance if all hypotheses correspond tocontinuous probability densities that are uniformly bounded. Then∞X

Eµ ∆2t (µ, m) ≤ 21wµ−1 .

(9)

t=1

The proof uses telescoping and dominance. The most remarkable (and worrying)fact here is the bound O(wµ−1 ) on the r.h.s. While the logarithm in (8) is sufficiently small to be of practical significance, the exponentially larger quantity O(wµ−1 )is generally huge. One can construct examples where this bound is sharp [PH06].
Fortunately, this does not necessarily imply that the MAP predictions are bad, theactual error is smaller in many important cases. Still, there are situations where8

J. Poland

MAP predictions tend to be “unbalanced” and therefore unfavorable compared tomarginalization. Stochastic model selection often gives better results in such cases.
The corresponding theorem for stochastic model selection (6), which is the maintechnical result of this paper, reads as follows.
Theorem 4 Assume µ ∈ C. Then, for any sequence of inputs z1 , z2 , . . .,∞X¢¡
Eµ EΞ ∆2t (µ, Ξ) = O wµ−1 + Π(log H + log wµ−1 ) = O(Π log wµ−1 )

(10)

t=1

holds. The quantities H and Π, the Shannon entropy and the µ-entropy potential of
the hypothesis class, are defined below. EΞ serves as a reminder that the Ξ-predictor
is randomized.
The quantity H in the theorem is the Shannon entropy of the hypothesis class
w.r.t. the current posterior distribution,
X¡¢
H(h<t ) = H [wν (h<t )]ν∈C = −wν (h<t ) log wν (h<t ).
ν∈CAccording to the convention in Remark 2, if we write just H as in the theorem, thiscorresponds to the prior (or, below in the proofs, to the current posterior). Moreover,
we define the current entropy potential of the hypothesis class relative to the true
distribution µ as
¡
¢
© ¡
¢
ª
Π (wν )ν∈C = sup H ( P w̃0 νw̃ 0 )ν∈C : w̃µ = wµ ∧ w̃ν ≤ wν ∀ν ∈ C \ {µ}
(11)
ν
ν
¡
¢
and Π(h<t ) = Π [wν (h<t )]ν∈C , see also Definition 15 below. This can be paraphrased
as “worst-case entropy of the class under all possible Bayesian updates where thetrue distribution always has evidence value 1”. We use the same convention as before:
writing just Π corresponds to the prior, or, in the proofs below, to the current posterior(Remark 2).
As we will see in Section 3.3, the entropy potential Π can grow as large as Ω(Hwµ−1 )in general. However, if the prior (wν )ν∈C has sufficiently light tails, Π is of order at
most log wµ−1 .

2.4

Implications: almost sure consistency and loss bounds

One important consequence of any finite bound on the expected cumulative Hellinger
error is almost sure consistency of the predictor in the Hellinger sense. That is, theHellinger distance of the predictive to the true distribution tends to zero almost surely.
This is easily verified, as
∞
´
³[©
³
¢ 1X
ª´ X ¡ 2
T →∞2
2
P ∆t ≥ ε ≤∆t ≥ ε ≤P ∃t ≥ T : ∆t ≥ ε = P
E∆2t −→ 0
ε t=T
t≥T
t≥T

(12)

Consistency Theorems for Discrete Bayesian Learning

9

holds. In case of a finite or countable observation space X , this implies in particular convergence of all predictive probabilities ξ(xt |zt , h<t ) to the true probabilitiesµ(xt |zt ). In case of a continuous observation space, the predicted probability massesof any measurable subset of X converges to the true mass. However, we cannot
conclude the convergence of moments, e.g. the expectation, without making further
assumptions.
Other implications of Theorems 1–4 are loss bounds of a Bayes-optimal decision
maker based on the predictive distribution, w.r.t. arbitrary loss functions. The proofof the following corollary proceeds as that of [PH05, Theorem 27].
Corollary 5 For each input z, let `(·, ·|z) : (x̂, x) 7→ `(x̂, x|z) ∈ [0, 1] be a loss
function known to the learner, depending on the true outcome x and the predictionx̂ (` may also depend on the time, but we don’t complicate notation by making thisexplicit). Let `µ<∞ be the cumulative loss of a predictor knowing the true distributionµ, where the predictions are made in a Bayes optimal way (i.e. choosing the prediction
Ξarg minx̂ Ex∼µ `(x̂, x|zt ) for current input zt ), and `ξ<∞ , `m<∞ , `<∞ be the corresponding
quantities for the respective Bayesian learners. Then the loss of the learners arebounded by
¢
¡
¢
¡q
(13)
E`ξ<∞ ≤ E`µ<∞ + O log wµ−1 + O log wµ−1 E`µ<∞ ,q¡ −1 ¢¡¢µE`m+ O wµ−1 E`µ<∞ , and(14)<∞ ≤ E`<∞ + O wµ
q
¡
¢
¡
¢
E`Ξ<∞ ≤ E`µ<∞ + O Π log wµ−1 + O Π(log wµ−1 )E`µ<∞ ,(15)
respectively.
The bound may seem weak to a reader familiar with another learning model,
prediction with expert advice, which has received quite some attention since [LW89,
Vov90]. Algorithms of this type are based on a class of experts rather than hypotheses,
and proceed by randomly selecting experts according to a (non-Bayesian) posterior
based on past performance of the experts. It is straightforward to use a hypothesis
as an expert. Thus the experts theorems (for instance [HP05, Theorem 8(i)]) imply
a bound similar to (15), but without any assumption on the data generating processµ, instead the bounds are relative to the best expert (hypothesis) in hindsight ν̂(and moreover with log wν̂−1 Π(w) replaced by log wν̂−1 ). So the experts bounds arestronger, which does not necessarily imply that the experts algorithms are better:bounds like (15) are derived in the worst case over all loss functions, and in this worst
case Bayesian learning is not better than experts learning, even under the proper
learning assumption. However, experts algorithms do not provide estimates for the
probabilities, which Bayesian algorithms do provide: in many practically relevantcases learning probabilities does yield superior performance.

10

2.5

J. Poland

Discussion

The proofs in this work are based on the method of potential functions. A potential
quantifies the current state of learning, such that the expected error in the next step
does not exceed the expected decrease of the potential function in the next step. If
we then can bound the cumulative decrease of the potential function, we obtain thedesired bounds. The potential method used here has been inspired by similar idea inprediction with expert advice [CBL03], the proof techniques are however completely
different. We will in particular introduce the entropy potential, already stated in(11), which may be interpreted as the worst-case entropy of the model class under all
admissible transformations of the weights, where the weight of the true distribution
is kept fixed. The entropy potential is possibly a novel definition in this work.
Before starting the technical presentation, we discuss the limitations of our online learning setup. A Bayesian online learner defined in the straightforward way iscomputationally inefficient, if in each time step the full posterior is computed: Thus,
marginalization, MAP/MDL, and stochastic model selection are equally inefficient ina naive implementation, and even generally uncomputable in case of a countable model
class. On the other hand, many practical and efficient learning methods (e.g. training of an artificial neural network) are approximations to MAP/MDL and stochastic
model selection. Moreover, bounds for the online algorithm also imply bounds forthe offline variant, if additional assumptions (i.i.d.) on the process generating the
inputs are satisfied. Also, in some cases one can sample efficiently from a probability
distribution without knowing the complete distribution.
But the most important contribution of this paper is theoretical, as it clarifies thelearning behavior of all three variants of Baysian learning in the ideal case. Also,
countable hypothesis classes constitute the limit of what is computationally feasibleat all, for this reason they are a core concept in Algorithmic Information Theory[LV97]. Proving corresponding results for the likewise important case of continuously
parameterized model classes is, to our knowledge, an open problem.
As already indicated, the dependence of the bound (10) on wµ−1 is logarithmic if
the prior weights decay sufficiently rapidly (precisely polynomially), but linear in theworst case. This implies the practical recommendation of using a prior with light tails
together with stochastic model selection.
The remainder of this paper is structured as follows. In the beginning of the next
section, we will introduce the notation and, in order to introduce the methods, prove
Solomonoff’s result with a potential function. In Section 3.1, we consider stochastic
model selection and prove the main auxiliary result. Section 3.2 defines the entropy
potential and proves bounds for general countable model class. In Section 3.3 we turnto the question how large the newly defined entropy potential can be.

11Consistency Theorems for Discrete Bayesian Learning

3

Technical results

The basic notation has been already introduced. We start with a simple example.
Example 6 Assume that X is binary and Z contains only a single element. In thiscase the observations are Bernoulli trials, i.e. they result from fair or unfair coin flips.
C specifies the set of possible coins we consider, and it is well-known that all posteriorweights but the weight of the true coin will converge to zero almost surely for t → ∞.
With the set of coins C ∼= { 41 , 12 , 34 } and the true coin being the fair one, it is easy
to see that this example gives a lower bound Ω(− log wµ ) on the expected quadraticerror of Bayes mixture and stochastic model selection predictions, namely the l.h.s.
expressions of (8) and (23), respectively.
Next, we present a proof of Solomonoff’s [Sol78] remarkable universal induction
result, Theorem 1. The proof presented here slightly differs from the standard one[Hut04] and serves for introducing our main proof technique, namely potential functions.
Lemma 7 Assume that the data generating distribution is contained in the model
class, i.e. µ ∈ C. Define the complexity potential as
K(h<t ) = − log wµ (h<t ).

(16)

For any current input zt and any history h<t , this potential satisfies(i) K(h<t ) ≥ 0,(ii) K(h<t ) − Ext ∼µ(·|zt ) K(h1:t ) ≥ ∆2t (µ, ξ).

(17)

By summing up the expectation of (ii) while observing (i), this lemma immediately
implies Theorem 1 for arbitrary sequence of inputs z1 , z2 , . . .:∞X

Eµ ∆2t (µ, ξ) ≤ K = − log wµ .

(18)

t=1

Proof. Clearly, (i) holds. In order to show (ii), we observe thatwµ (h1:t ) = wµ (h<t )µ(xt |zt ).
ξ(xt |zt , h<t )Then, simplifying the notation by suppressing the history h<t and the current input
zt (e.g. K now stands for K(h<t ), please compare Remark 2 again),
Z
³
´
°
£
¤
K − EK(x) = K − dµ(x) K − log µ(x)= D µ(·|zt )°ξ(·|zt , h<t ) .
ξ(x)

12

J. Poland

The r.h.s. here is called Kullback-Leibler divergence. It is well-known that KullbackLeibler divergence dominates the squared Hellinger distance ∆2t (µ, ξ), see (20).
2
By Kraft’s inequality, the complexity K of µ can be interpreted as µ’s description
length. Thus, Solomonoff’s theorem asserts that the predictive complexity (measured
in terms of the quadratic error) coincides with the descriptive complexity, if the data
is rich enough to distinguish the models. Then K can be viewed as the state oflearning in the discrete model class. Observe that only the expected progress, i.e.
decrease of K, is positive. The actual progress depends on the outcome of xt and ispositive if and only if µ(xt ) ≥ ξ(xt ). If the probability vectors µ and ξ coincide, then– according to this potential function – no learning takes place for any observation,
as then K(xt ) = K for all xt . Hence, the complexity potential K need not always bea good choice to describe the learning state.
Example 8 Consider a binary observation space and a model class containing three
distributions ν1 , ν2 , ν3 , predicting νi (1|z) = 4i for some input z. Suppose µ = ν2 , i.e.
the true probability is 12 . Then we cannot measure the learning progress after theobservation in terms of K. However, there should be a progress, and indeed there isone, if we consider the entropy of the model class. This will become clear with Lemma
9.

3.1

Stochastic model selection

Here is another case where the complexity potential K is not appropriate to quantify
the state of learning. In stochastic model selection, the current prediction vector
Ξ(·|zt , h<t ) is obtained by randomly sampling a model according to the current weightswν (h<t ) and using this model’s prediction, i.e. (compare (6))
Ξ(·|zt , h<t ) = νJ (·|zt ) where P(J = i) = wνi (h<t ).
Hence, Ξ is a random variable depending on the sampled index J. The following
lemma gives a first indication for a suitable potential function for learning withstochastic model selection.
Lemma 9 If the current entropy of the hypothesis class is finite, H(h<t ) < ∞, then,for any input zt ,H(h<t ) − Ext ∼ξ(·|zt ,h<t ) H(h1:t ) ≥ E∆2t (ξ, Ξ).

(19)

Proof. It is a well-known fact, shown e.g. in [BM98, p. 178], that the squared
Hellinger distance of two probability distributions µ and ν on X never exceeds their
Kullback-Leibler divergence:
Z
Z
p
¡p
¢2
µ(·)
2
.
(20)
∆ (µ, ν) = d µ(·) − ν(·) ≤ dµ(·) logν(·)

Consistency Theorems for Discrete Bayesian Learning

13

Therefore, we haveH(h<t ) − Ext ∼ξ(·|zt ,h<t ) H(h1:t ) =XZwν (h<t )ν(x|zt )dν(x|zt ) log ξ(x|zt ,h<t )

ν∈C

≥

X

wν (h<t )∆2 (ξ, ν) = E∆2t (ξ, Ξ). 2

ν∈C2
Unfortunately, the l.h.s. of the above inequality contains an expectation w.r.t. ξ
instead of µ. Since on the other hand µ governs the process and generally differs fromξ, the entropy H is not directly usable as a potential for the Ξ’s deviation from its
mean ξ. The following theorem demonstrates an easy fix, which however exponentiallyblows up the potential.
Theorem 10 (Predictive performance of stochastic model selection, loose bound) Assume that µ ∈ C. Define the potential¡¢
PE (h<t ) = H(h<t ) exp K(h<t ) = H(h<t )/wµ (h<t ).
Then, for any history h<t and any current input zt ,PE (h<t ) − Ext ∼µ(·|zt ) PE (h1:t ) ≥ ∆2t (ξ, Ξ).
Consequently, with H = −∞XPν∈C wν log wν denoting the initial entropy,∆2t (ξ, Ξ) ≤ PE = H/wµ ,

t=1
∞
X

(21)

∆2t (µ, Ξ) ≤ − log(wµ ) + H/wµ + 2(22)q−H log(wµ )/wµ ,

(23)

t=1

and the predictions by Ξ converge to the true probabilities µ almost surely.
t |zt ). Since always 1/wµ (h<t ) ≥ 1, using
Proof. Recall wµ (h1:t ) = wµ (h<t ) ξ(xµ(xt |zt ,h<t )Lemma 9 we obtain (21) by
Z
Z
¡
¢
1
PE (h<t ) − dµ(x|zt )PE (h1:t ) = wµ (h<t ) H(h<t ) − dξ(x|zt , h<t )H(h1:t )≥ ∆2t (ξ, Ξ).
Summing the expectation up yields (22). Using this together with (18) and thetriangle inequality for the Hellinger distance, we conclude (23). Finally, almost sureconvergence follows from (12).
2
In particular, this theorem shows that the entropy of a model class, if it is initiallyfinite, necessarily remains finite almost surely. Moreover, it establishes almost sure

14

J. Poland

asymptotic consistency of prediction by stochastic model selection in our Bayesianframework. However, it does not provide meaningful error bounds for all but verysmall model classes, since the r.h.s. of the bound is exponential in the complexity,
hence possibly huge.
Before continuing to show better bounds, we demonstrate that the entropy is indeed
a lower bound for any successful potential function for stochastic model selection.
Example 11 Let the observation space be binary. Let wµ = 1− n1 , in this way K ≈ n1
and can be made arbitrary small for large n ∈ N. Fix a target entropy H0 ∈ N and
set K = 2nH0 . Choose a model class that consists of the true distribution, always
predicting 12 , and K other distributions with the same prior weight 1/(nK). In thisway, the entropy of the model class is indeed close to H0 log 2. Let the input set
be Z = {1 . . . nH0 }, and let νb (1|z) = bz , where bz is the zth bit of ν’s index b inbinary representation. Then it is not hard to see that on the input stream z1:nH0 =√1, 2, . . . nH0 always µ = ξ. Moreover, at each time, E∆2 (µ, Ξ) = n1 (2 − 2) > 1/(2n).
Therefore the cumulative error exceeds H0 /2, i.e. of order of the entropy. Note that
this error, which can be chosen arbitrarily large, is achievable for arbitrarily small
complexity K.
In the proof of Theorem 10, we used only one “wasteful” inequality, namely
1≥ 1. The following lemma will be our main tool for obtaining better bounds.
wµ (h<t )Lemma 12 (Predictive performance of stochastic model selection, main auxiliary
result) Suppose that we have some function B(h<t ), depending on the history, withthe following properties:(i) B(h<t ) ≥ H(h<t ) (dominates the entropy),(ii) Ext ∼µ(·|zt ) B(h1:t ) ≤ B(h<t ) (decreases in expectation),(iii) the value of B(h<t ) can be approximated arbitrarily close
by restricting to a finite model class.
Then, for any history and current input, the potential function defined by£¤P(h<t ) = K(h<t ) + log(1 + H(h<t )) (1 + B(h<t ))satisfies
P(h<t ) − Ext ∼µ(·|zt ) P(h1:t ) ≥ H(h<t ) − Ext ∼ξ(·|zt ,h<t ) H(h1:t ).

(24)

Proof. The proof is divided into two parts. First, we will assume finite observation
space. In the second part, this is generalized to arbitrary observation spaces.
Part 1: Assume that X is finite. Because of (iii), we need to prove the lemma
only for finite model class, the countable case then follows by approximation. In thisway we avoid dealing with a Lagrangian on an infinite dimensional space below.

15

Consistency Theorems for Discrete Bayesian Learning

Again we drop all dependencies on the history h<t and the current input zt fromthe notation. Then observe that in the inequality chainX£¤ 1 + B(x)µ(x) K(x) + log(1 + H(x))
1+B
x∈X
X µ(x)(1 + B(x)) £¤P≥ K + log(1 + H) −K(x) + log(1 + H(x))
00x0 µ(x )(1 + B(x ))
x∈X
P
P
ν(x)
ν wν
x ν(x) log ξ(x)≥,1+BK + log(1 + H) −

(25)
(26)

(25) follows from assumption (ii), so that we only need to show (26) in order tocomplete the proof. We will demonstrate an even stronger assertion:
P
P
ν(x)
X £
w
¤
ν
ν
x ν(x) log ξ(x)µ(x)
log(1 + H) −µ̃x log(1 + H(x)) − log ξ(x) ≥
(27)
1+B
x∈X
for any probability vector µ̃ = (µ̃x )x∈X ∈ [0, 1]|X | withPx µ̃x = 1.

It is sufficient to prove (27) for all stationary points of the Lagrangian and allboundary points. In order to cover all of the boundary, we allow µ̃x = 0 for all x
in some subset X0 ( X (X0 may be empty). Let X̃ = X \ X0 and define ξ(X̃ ) =P
˜x∈X̃ ξ(x), ξ(X0 ) = 1 − ξ(X̃ ), and ξ(x) = ξ(x)/ξ(X̃ ). Then (27) follows fromf (µ̃) = log(1 + H) −X¡¢
µ̃x Ṽ (x) − log µ(x)
≥
ξ̃(x)

P

ν wν

P

ν(x)
x ν(x) log ξ(x)

1+B

x∈X̃

where Ṽ (x) = log(1 −

P
ν

,

(28)

wν ν(x)ν ν(x)).
log wξ(x)ξ̃(x)

We now identify the stationary points of the Lagrangian¡X¢
L(µ̃, λ) = f (µ̃) − λµ̃x − 1 .
x

The derivative of L w.r.t. all µ̃x vanishes only if
λ = −Ṽ (x) + log µ(x)for all x ∈ X̃ .
ξ̃(x)

(29)

P ˜
λ+Ṽ (x)Ṽ (x)˜This implies µ(x) = ξ(x)e, and, since the µ(x) sum up to one, 1 = eλ x ξ(x)e
.
£P
¤
Ṽ
(x)
˜
This can be reformulated as λ = − log. Using this and (29), (28) isx ξ(x)etransformed toPPν(x)ν∈C wν
x∈X ν(x) log ξ(x)≤ log(1 + H) + λ
(30)
1+B
X
X
X
£
¤
wν ν(x)wν ν(x)˜ξ(x)= log(1 −wν log wν ) − log 1 −
.
log
ξ(x)
ξ̃(x)
ν∈C

x∈X̃

ν∈C

The arguments of both outer logarithms on the r.h.s. of (30) are at most 1 + B: For
the left one this holds by assumption (i), H ≤ B, and for the right one also by (i)16J. Polandy−xbecause Ex∼ξ H(x) ≤ H. Since for x ≤ y ≤ 1 + B we have log(y) − log(x) ≥ 1+B, (30)
follows from
X
X
X
X
wν
ν(x) log ν(x)≤−w
ν(x) log wν .
ν
ξ(x)
ν∈C

x∈X0

ν∈C

x∈X0

But this relation is true by Jensen’s inequality:³X X´
X X w ν(x)wν ν(x)wν ν(x) wν ν(x)
ν
log
≤
log
·
≤ 0,
ξ(X0 )
ξ(x)ξ(X0 )ξ(x)ν∈C x∈X0

ν∈C x∈X0ν ν(x)ν ν(x)
since the wξ(Xsum up to one and always wξ(x)≤ 1 holds.
0)Part 2: So far, we have proven the assertion for finite X . In order to show thegeneralization to arbitrary observation space, we may decompose X into two subsets
X = X discrete ∪ X continuous , where X discrete is the at most countable set of points where
any of the distributions in C has a non-zero mass concentration. We can prove theassertion for the discrete and the continuous parts separately. The discrete part follows
simply by approximating, so we focus on the continuous part and assume without lossof generality that all distributions are (piecewise) continuous probability densities.
We show the assertion by assuming the contrary
Ext ∼µ(·|zt ) P(h1:t ) − P(h<t ) > Ext ∼ξ H(h1:t ) − H(h<t )(31)

and obtaining a contradiction to part 1. Dropping again the history h<t from thenotation, (31) is equivalent toEx∼µ P(x) − P > Ex∼ξ H(x) − H + 11ε for some ε > 0.

(32)

We may assume without loss of generality that X is compact, and that there is anumber R > 0 such thatmax H(x)ξ(x) ≤ R and max ξ(x) ≤ R.
x∈X

x∈X

(33)

To see this, just choose X̃ ⊂ X compact and sufficiently large, such that both (33)and Ex∼ξ|X̃ H(x) ≥ Ex∼ξ H(x) − ε hold, this is possible because ξ(x)H(x) is integrable
w.r.t. the Lebesgue measure λ. Then, replace X by X̃ and (32) byEx∼µ P(x) − P > Ex∼ξ H(x) − H + 10ε.

(34)

Next, we argue that we may even assume without loss of generality that C isfinite. To this aim, first start with approximating P(x) by a step function P̃(x) thatis piecewise constant on relatively compact subsets A1 , A2 , . . . , An ⊂ X and takes
only finitely many (namely n) values ỹ1 , . . . , ỹn > 0. We choose P̃(x) such that it isdominated by P(x), with the propertyEx∼µ P̃(x) ≥ Ex∼µ P(x) − ε.

Consistency Theorems for Discrete Bayesian Learning

17This is possible since P(x) is measurable and non-negative.
We choose an even smaller step function P(x) that is likewise constant on A1 , . . . , An
and is strictly dominated by P̃(x), such thatEx∼µ P(x) ≥ Ex∼µ P(x) − 2ε(35)

and P(x) = P̃(x) − εi = ỹi − εi := yi for x ∈ Ai , where εi > 0 for all 1 ≤ i ≤ n. Then,for each x ∈ A1 , B(x) and therefore P(x) can be approximated with finitely many
hypotheses. Since P(x) ≥ ỹi , we can find a finite set of hypotheses F(x) such that
P F̃ (x) > yi for any F̃ ⊃ F (x), where P F̃ (x) denotes the potential computed with
only the hypotheses in F̃. Since P F̃ (·) is continuous (while F̃ is fixed), we have that
P F̃ (x̃) > yi holds even within an open superset x̃ ∈ U (x) of x. For each x ∈ A1 , there
is such an open U(x), and they form an open cover of Ā1 . Since Ā1 is compact, there isa finite subcover U(x1 ) ∪ . . . ∪ U (xm ) ⊃ A1 . We may choose F1 = F(x1 ) ∪ . . . ∪ F (xm )in order to obtain a finite set of hypotheses approximating P(x) sufficiently closelyon all of A1 .
Analogous approximations F2 , . . . , Fn are obtained for all other A2 , . . . , An . Also,
we choose a finite set of hypotheses F0 ⊂ C such that all supersets F̃ ⊃ F0 approximate the prior P up to ε. Take the union F = F0 ∪ F1 ∪ . . . ∪ Fn . Then, from (35),
we conclude thatEx∼µ P(x) − P F̃ > Ex∼µ P(x) − P − 3ε.
and P F̃ (x) ≥ P(x) for all x ∈ X and any F̃ ⊃ F . We make sure that µ ∈ F.
We perform the same construction an approximation of H(x) from above. Since
X was already assumed to be compact, the constant function R, which dominates
ξ(x)H(x) according to (33) is integrable w.r.t. the Lebesgue measure λ. Therefore,
we may refine the partitioning (Ai )ki=1 of X̃, obtaining a new partitioning (Ãi )mi=1 ofX̃, such that H(x)ξ(x) is approximated from above within ε by functions constant oneach Ãi . We may choose the approximators H(x) and ξ(x) slightly larger, such thatthey need only finitely many hypotheses. We incorporate these hypotheses into F.
Altogether, this shows that we may indeed assume that C is finite, if we replace(34) withEx∼µ P(x) − P > Ex∼ξ H(x) − H + 4ε,(36)knowing that P(x) ≤ P(x) and H(x) ≥ H(x) for all x ∈ X .
In the next step, we further decrease X a tiny little bit and define X ⊂ X suchthat
ν(X ) < 1 for all (finitely many!) ν ∈ C.
(37)
Set Ai = Ai ∩ X for all 1 ≤ i ≤ n. While choosing X , we make sure that it is not too
small. Namely, we assert³
ε ´µ(Ai ) 1 −< µ(Ai ) for all 1 ≤ i ≤ n,
(38)
2yi
(39)
Ex∼µ|X P(x) ≥ Ex∼µ P(x) − ε, andε1 − ξ(X ) <,(40)
2 log |C|

18

J. Poland

where |C| is the number of hypotheses in C.
In the last step, construct a refining partition (A0i )ki=1 of (Ãi ∩ X )m
i=1 and lower andupper approximations ν, ν for each ν ∈ C, with the following properties:Zν < 1 for all ν ∈ C, possible due to (37),
(41)
X
Z
³
ε´
µ ≥ µ(Ai ) 1 −for all 1 ≤ i ≤ n, possible due to (38),
(42)
yi
Ai
Z
ε
1−
ξ<
, possible due to (40).
(43)
log |C|X
Now choose (with λ being the Lebesgue measure)
X 0 = {0, 1, . . . , k},x0i = arg min0 P(x) for all 1 ≤ i ≤ k,

νi0 = ν(x0i )λ(A0i )ν00 = 1 −

Ã
Hi0 = H³x∈Ai

(1 ≤ i ≤ k, ν ∈ C),wν νi0Pk
0
j=0 wν νj

!

´
ν∈C

= H(x0i ),kX

νi0 for all ν ∈ C,

Ã i=1!
³ w ν0 ´ν i
0Pi = P= P(x0i ).
Pk
0 ν∈C
j=0 wν νj

By (41), each ν 0 is in fact a measure on X 0 . Justifying the following estimations withthe respective equations before, we havekX

µ0i Pi0 − P ≥

i=0

k
X

µ0i Pi0 − P≥ Eµ|X P − P(42)≥ Eµ|X P − P − ε

i=1
(39)

≥ Eµ P − P − 2ε

≥

k
X
i=1

ξi0 Hi0 − H + 2ε(36)

≥ Eξ H − H + 2εk(43) X≥≥ Eξ|X H − H + 2ε

ξi0 Hi0 − H + ε.

i=0The last estimate is true since H00 ≤ log |C| holds. This is the desired contradiction
to the first part of the proof.
2
We now present a simple application of this result for finite model classes.
Theorem 13 (Predictive performance of stochastic model selection for finite model
class) Suppose that C consists of N ∈ N models, one of them is µ. Let£¤
PF (h<t ) = K(h<t ) + log(1 + H(h<t )) (1 + log N ).
P
Then PF (h<t ) − Ext ∼µ PF (h1:t ) ≥ H(h<t ) − x∈X ξ(x|zt , h<t )H(h1:t ) holds for any
history h<t and current input zt , Consequently,∞X£¤∆2 (ξ, Ξ) ≤ PF = (1 + log N ) log(1 + H) − log(wµ ) .

(44)

t=1

Proof. Since the entropy of a class with N elements is at most log N , this follows
directly from Lemma 12.
2

Consistency Theorems for Discrete Bayesian Learning

3.2

19

Entropy potential and countable classes

We now generalize Theorem 13 to arbitrary countable model classes. First note that
there is one very convenient fact about the potential function proofs so far: (17),(21), and (24) all are local assertions, i.e. for a single time instance and history. If thelocal expected error is bounded by the expected potential decrease, then the desiredconsequence on the cumulative error holds.
The entropy cannot be directly used as B in Lemma 12, since it may increase
under µ-expectation. Intuitively, the problem is the following: There could be a false
model with a quite large weight, such that the entropy is kept “artificially” low. If
this false model is now refuted with high probability by the next observation, thenthe entropy may (drastically) increase. An instance is constructed in the following
example. Afterwards, we define the entropy potential, which does not suffer from thisproblem.
Example 14 Fix binary observation space and let C˜ and Z̃ be model class and input
space of Example 11. Let C = C˜ ∪ {νfool }, Z = Z̃ ∪ {0}, wfool = 1 − m1 , and the rest of
the prior of mass m1 be distributed to the other models as in Example 11. Also the true
distribution remains the same one. If the input sequence is z1:nH0 +1 = 0, 1, . . . nH0 ,and νfool (1|0) = 0 while ν(1|0) = 1 for all other ν, then like before the cumulative
error is (even more than) H0 /2, while the entropy can be made arbitrarily small forlarge m.
¡¢P
Definition 15 (Entropy potential) Let H (wν )ν∈C = − ν wν log wν be the entropy
function. The µ-entropy potential (or short entropy potential) of a model class C
containing the true distribution µ is, as already stated in (11),
¡
¢
© ¡
¢
ª
Π (wν )ν∈C = sup H ( P w̃0 νw̃ 0 )ν : w̃µ = wµ ∧ w̃ν ≤ wν ∀ν ∈ C \ {µ} .
(45)
ν

ν

Clearly, Π ≥ H. According to Theorem 10, Π is necessarily finite if H is finite,
so the supremum can be replaced by a maximum. Note that the entropy potential isfinitely approximable in the sense of (iii) in Lemma 12.
The following proposition gives a characterization of the entropy potential.
P
Proposition 16 (Characterization of Π) For S ⊂ C, let w(S) = ν∈S wν . There isexactly one subset A ⊂ C with µ ∈ A, such thatX w0
ν− log wν > L(A) := −log wν 0 ⇐⇒ ν ∈ A \ {µ}.
(46)
w(A)
ν 0 ∈A

We call A the set of active models (in Π). Then, with w̃ν = exp(−L(A)) for ν ∈ C \A,w̃ν = wν for ν ∈ A, and k = |C \ A|, we have¢¢¡¡
Π = Π (wν )ν∈C = H ( P w̃0 νw̃ 0 )ν∈C
¡ ν ν¢= log k + w(A)eL(A) .
(47)

20

J. PolandMoreover, this is scaling invariant in the weights, i.e. (46) yields the correct active
set and (47) gives the correct value for weights that are not normalized, if these unnormalized weights are also used for computing w(A) and L(A).
Proof. We first argue that the maximum of (45) cannot be attained if some w̃ν = 0.
To this aim, let p̃ ∈ [0, 1]|C| , assume w̃ν = 0 for a specific ν ∈ C, and set H̃ =¡¢H ( P w̃0 νw̃ 0 )ν . Now assume w̃ν > 0 and observe that
ν

ν

¢
¡
H ( P w̃0 νw̃ 0 )ν =
ν

ν

£
¤
− w̃ν log(w̃ν ) + (1 − w̃ν ) − log(1 − w̃ν ) + H̃ ≥ H̃holds if − log(w̃ν ) ≥ H̃. This can be realized for small enough w̃ν > 0, hence themaximum of (45) cannot be attained for w̃ν = 0.
The maxima of the entropy under p̃ can be found only at the boundary or at
the points where the gradient vanishes. Therefore, for a maximum of (45), we needPthat for each ν ∈ C \ {µ}, either w̃ν = wν or, with p̃(C) =ν w̃ν and L̃(C) =P
1− p̃(C) ν w̃ν log(w̃ν ),0=¡¢dH ( P w̃0 νw̃ 0 )ν
ν

ν

dw̃ν

=

i
1 h
− log(w̃ν ) − L̃(C) .
p̃(C)

(48)

Those elements ν satisfying the latter condition have log w̃ν = −L̃(C) and henceL̃(C) = L̃(C \ {ν}). Therefore, each possible maximum of (45) corresponds to a subsetÃ ⊂ C of active models, such that µ ∈ Ã and furthermore w̃ν = wν for ν ∈ Ã andlog w̃ν = −L̃(Ã) = −L(Ã) for ν ∈/ Ã. Since only log w̃ν ≤ log wν is feasible, for ν ∈/ Ã
we necessarily have − log wν ≤ L(Ã). Subsets Ã that satisfy this latter condition are
called feasible.
Assume that we have a feasible subset Ã, then for all ν ∈/ Ã, the complexity− log w̃ν equals the average complexity of all ν ∈ Ã. Hence
X wν
¢
¡
wν
H ( P w̃0 νw̃ 0 )ν = −
log P
ν
ν
p(Ã)
ν 0 ∈C wν 0ν∈Ã¡¢
= L(Ã) + log p(Ã) + ke−L(Ã)¡¢= log k + p(Ã)eL(Ã) ,which proves (47) for any such Ã.
Observe that our A defined in the assertion is the smallest feasible subset andtherefore unique. So we only have to make sure no larger subset can result in a larger
entropy. To this aim, take any feasible subset Ã ⊂ C. We assume that there isν1 ∈ Ã \ {µ} such that − log wν1 ≤ L(Ã). We need to show that then the entropy
increases if we take out ν1 . But in this case, the derivative, computed as the r.h.s. of(48), is non-positive at w̃ν1 = wν1 . Thus we may increase the entropy by decreasingConsistency Theorems for Discrete Bayesian Learning21wν1 until the derivative vanishes. Repeating this step for all ν with the property− log wν ≤ L(Ã), we conclude that the smallest feasible subset A gives the maximum
entropy.
Finally, scaling invariance of the set (46) and the value (47) w.r.t. the weights iseasy to see.
2
The next result states that the entropy potential possesses the desired property
to decrease in expectation and therefore paves the way for the main theorem of thiswork.
Theorem 17 For any history h<t and current input zt ,Zµ(xt |zt )Π(h1:t ) ≤ Π(h<t ).
xt ∈X

¡
¢
where the posterior entropy potential is defined as Π(h<t ) := Π [wν (h<t )]ν∈C .
Proof. As in the proof of Lemma 12, we need to proceed in two steps. First we show
the assertion for finite observation space X . The second step, the generalization toarbitrary X , is similar as but substantially simpler that the second part of the proof
of Lemma 12, since the approximation of only one side of the bound is required. We
therefore omit the explicit presentation of this second step here.
Restricting to finite observation space X , we need to show the assertion only for
finite model class: Once this is established, the general case follows by approximation.
Again, we drop the dependence on the history and the current input from thenotation. We will show a slightly more general assertion: For any subset of thealphabet X̃ ⊂ X , and any choice of probability vectors ν(x) for all ν ∈ C we have³£X¤ ´µ(x)Π(x) ≤ µ(X̃ )Π wν ν(X̃ ) ν∈C ,
(49)
x∈X̃

P
where ν(X̃ ) = x∈X̃ ν(x) is the total ν-probability of the subset X̃ . We prove (49)by induction over the subset size |X̃ |. For |X̃ | = 1, there is nothing to show. If (49)holds for X̃ , then for X̃ 0 = X̃ ∪ {x},
X

³
´
³
´
(∗)
µ(x)Π(x) ≤ µ(X̃ )Π [wν ν(X̃ )]ν + µ(x)Π(x) ≤ µ(X̃ 0 )Π [wν ν(X̃ 0 )]ν

x∈X̃ 0implies the assertion. It remains to show (∗).
Now let w̃ν = wν ν(X̃ 0 ) and pν = ν(x)/ν(X̃ 0 ) for all ν ∈ C, and set µ̃ = pµ . Then(∗) is equivalent to
¡
¢
¡
¢
¡
¢
(1 − µ̃)Π [w̃ν (1 − pν )]ν∈C + µ̃Π [w̃ν pν ]ν∈C ≤ Π [w̃ν ]ν∈C ,

(50)

22

J. Poland

where for all ν ∈ C their values pν range in pν ∈ [0, 1]. Thus we have reduced theoriginal assertion to binary alphabet.
In order to prove (50), it is sufficient to show that the maximum of the l.h.s. isattained if pν = µ̃ holds for all ν ∈ C. We first argue that the maximum can be
only attained if in all three sets of weights, [w̃ν ]ν , [w̃ν (1 − pν )]ν , and [w̃ν pν ]ν , thesame models are active (see Proposition 16). Denote the respective sets of activemodels by A, A0 , A1 . Recall that the constructions in Proposition 16 do not requireP
the weights to sum up to one, and define the quantities w̃1 (A1 ) = ν∈A1 w̃ν pν and
¡
P
1
1 ¢
L1 (A1 ) = − ν∈A1 w̃w̃1ν(Apν1 ) log(w̃ν pν ) and Π1 = log |C \ A1 | + w̃1 (A1 )eL (A ) , and in
the same way, the quantities w̃0 (A0 ), L0 (A0 ), and Π0 .
For active ν ∈ A0 or ν ∈ A1 , respectively, the respective derivatives of Π0 and Π1are computed as¢dΠ0w̃ν 0 0 ¡= − 0 eL (A ) − log[w̃ν (1 − pν )] − L0 (A0 ) < 0 for ν ∈ A0 \ {µ} and
dpν
Π
1
¢
dΠ
w̃ν L1 (A1 ) ¡
1
1
=
e
−
log[
w̃
p
]
−
L
(A
)
> 0 for ν ∈ A1 \ {µ},
ν
ν
1
dpν
Π
¡
¢
1
> 0 follows from − log[w̃ν pν ] − L1 (A1 ) > 0 for ν ∈ A1 (and analogously
where dΠdpνfor Π0 ). For inactive ν ∈/ A0 or ν ∈/ A1 , respectively, the respective derivatives vanish.
Consider now a model ν ∈/ A which is inactive in Π. If we choose pν = µ, then it is0
1
inactive in both Π and Π , i.e. both ν ∈/ A0 and ν ∈/ A1 hold. If we decrease pν until it01> 0 and dΠ
= 0, the term (1 − µ̃)Π0 + µ̃Π1
becomes active in Π1 , then, because of dΠdpνdpν
decreases. The same happens if we increase pν until it becomes active in Π0 . Hencethe maximum of (1 − µ̃)Π0 + µ̃Π1 can be attained only if the inactive weights in Π
remain inactive in both Π0 and Π1 , and we may set pν = µ̃ for all these ν ∈/ A.
Next, we claim that for a model ν ∈ A \ {µ}, which is active in Π, the maximumof (1 − µ̃)Π0 + µ̃Π1 can be only attained if ν remains active in both Π0 and Π1 . To
show this, we only need to argue that, regardless of the configuration of the other pν 0
(ν 0 6= ν),there is an assignment pν ∈ [0, 1] such that both ν ∈ A0 and ν ∈ A1

(51)

holds. If we then increase pν until (possibly) ν ∈/ A1 , then we have that (1− µ̃)Π0 + µ̃Π1
must decrease, since its derivative is smaller than zero.
0

0

1

1

We have that each pν in the interval I 01 := (1− w̃1ν e−L (A ) , w̃1ν e−L (A ) ) also satisfies(51). In order to show that I 01 is non-empty, we first argue that I 01 ⊃ I := (1 −1 −L0 (A) 1 −L1 (A)e, w̃ν e), which is then proven to be non-empty. Since we know that ν isw̃ν
active in Π and therefore w̃ν < e−L(A) ,1Pew̃ν (1−pν)
1log w̃ (1−pν)Aw̃0 (A)
ν

+

P

e

1

w̃ν pν
1
A w̃1 (A) log w̃ν pν01= e−L (A) + e−L (A) ≥ e−L(A)implies that I is not empty. We will verify (52) below.

(52)

23

Consistency Theorems for Discrete Bayesian Learning

I ⊂ I 01 holds by the following argument. Assume that for some ν 0 ∈ A, pν 0
is so small that ν 0 ∈/ A0 . Varying pν 0 in the range [0, u] where ν 0 ∈/ A0 , does not0011change the left constraint 1 − w̃1ν e−L (A ) , while the right constraint w̃1ν e−L (A ) is
minimal at both boundaries pν 0 = 0 and pν 0 = u. This can be seen by considering the£¤11
derivative dLdp(A0 ) = w̃1w̃(Aν 1 ) − log(w̃ν 0 pν 0 ) − L1 (A1 ) − 1 , which is +∞ at pν 0 = 0 andν
steadily decreases until − w̃1w̃(Aν 1 ) (L1 (A1 ) + 1) at pν 0 = u. Note that for both boundary
points 0 and u, the value of L1 (A1 ) coincides. Thus we can set pν 0 = u, making
the interval I 01 smaller. Letting Ã0 = A0 ∪ {ν 0 } and Ã1 = A1 ∪ {ν 0 }, we then have00
1
1
I 01 = (1 − w̃1ν e−L (Ã ) , w̃1ν e−L (Ã ) ). A symmetric argument holds for the case thatν0 ∈/ A1 . In this way, we can subsequently treat all ν 0 ∈ A \ (A0 ∩ A1 ), constantly
decreasing I 01 , until we arrive at I.
Now, in order to show (52), observe thatPeAw̃ν (1−pν)
1log (1−pν)w̃0 (A)≤P w̃ν pν
1
w̃(A)
w̃(A)
A w̃1 (A) log pν
and
e
≤ 1
0
w̃ (A)w̃ (A)by Jensen’s inequality, so (52) follows fromw̃0 (A)
e
w̃(A)

P
A

w̃ν (1−pν)
log w̃νw̃0 (A)

1(A)+ w̃w̃(A)ePw̃ν pν
A w̃1 (A) log w̃ν

P

≥e

w̃ν
A w(A) log w̃ν.

Applying Jensen’s inequality again to the l.h.s. verifies this. Altogether we have shown
so far that the maximum of (1 − µ̃)Π0 + µ̃Π1 can be only attained if A = A0 = A1 .
Finally, we can turn to proving (50), by showing that the maximum of (1 − µ̃)Π0 +µ̃Π1 is attained if pν = µ̃ for all ν ∈ C. Since we know already that we may setpν = µ̃ for ν ∈/ A in order to attain the maximum, we can just ignore these models
and assume without loss of generality that A = C. Then the derivatives of Π0 and Π1
are
¢
dΠ0
w̃ν ¡
= − 0
− log[w̃ν (1 − pν )] − L0 (A0 ) and
dpν
w (A)
1
¢
dΠ
w̃ν ¡
1
1
=
−
log[
w̃
p
]
−
L
(A
)
,
ν
ν
dpν
w1 (A)
01

respectively. A possible maximum has (1 − µ̃) dΠ
+ µ dΠ
= 0 for all ν 6= µ, whichdpνdpν
occurs in case that pν = µ̃ for all ν ∈ C. This is in fact a global maximum if we canshow the Hessian is globally negative semi-definite. It is sufficient to show that both
Hessians of Π0 and Π1 are negative semi-definite: We identify the model class withan index set C = A ∼= {0, 1, . . . , N } and assign the true distribution to the index 0.
Then, abbreviating Di = log(w̃i pi ) − L1 (A) and using the characteristic function 1i=jwhich is one if i = j and zero otherwise, the Hessian of Π1 is computed as· 2 1 ¸N
h
¡
¢iN
1
dΠ
w̃1 (A)=− 1w̃i w̃j 1i=j w̃i + Di + Dj − 1.
dpi dpj i,j=1w̃ (A)2i,j=1
This Hessian is negative semi-definite by Lemma 18 below, and so is the Hessian of
Π0 . This concludes the proof.
2

24

J. Poland

Lemma 18 Let N ≥ 1 and wi > 0 for 0 ≤ i ≤ N (the wi need not sum up to one).
PN
PN wi
Let W =
i=0 wi and assume that − log wj ≥ L := −i=0 W log wi holds for allN
1 ≤ j ≤ N . Then, for all vectors u ∈ R , we have that
·

N
X

ui uj

1i=j W

i,j=1

wi

¸
− log wi − L − log wj − L − 1 ≥ 0.

(53)

Proof. We proceed by induction over N . For N = 1, the assertion is immediate.
Now, for N , observe that the derivative of the l.h.s. of (53) w.r.t. w0 ,
¡ PN
¢2 h
i
2
i=1 ui+
1 + L + log w0 ,
wi
W
i=1

N
X
u2
i

is positive, since − log w0 − L < 0. Thus we may decrease the l.h.s. of (53) bydecreasing w0 , until eventually − log wk = L holds for one k ∈ {1 . . . N }. Set Di =− log wi − L and W̃ = W − wk . Then
"
#
¸
·
N
X
X
1i=j W̃
1i=j Wui uj
ui uj+ Di + Dj − 1 =+ Di + Dj − 1
wi
wi
i,j=1
i,j∈{1...N }\{k}
·
¸
X
wi 2
wk 2
+
u − 2(1 − Di )ui uk +
u .
(54)
wk k
wi i
i∈{1...N }\{k}Since for all u, v ∈ R and c ≤ 1 we have u2 − 2cuv + v 2 ≥ 0, the term (54) isnonnegative. Thus the assertion follows from the induction hypothesis.
2
The previous theorem, together with Lemma 12, immediately implies the main
result of this paper, Theorem 4. More precisely, it reads as follows.
Theorem 19 (Predictive performance of stochastic model selection) For countablemodel class C containing the true distribution µ, define the potential (for errors in thesquared Hellinger sense) as£¤
P(h<t ) = K(h<t ) + log(1 + H(h<t )) (1 + Π(h<t )).
Then, for any history h<t and current input zt ,P(h<t ) − Ext ∼µ(·|zt ) P(h1:t ) ≥ H(h<t ) − Ext ∼ξ(·|zt ,g<t ) H(h1:t ), and thus∞X£¤
∆2t (ξ, Ξ) ≤ P = (1 + Π) log(1 + H) − log(wµ ) .

(55)

t=1

The bound (10) on
distance.

P2t ∆t (µ, Ξ) follows from the triangle inequality for the Hellinger

Consistency Theorems for Discrete Bayesian Learning

3.3

25

The magnitude of the entropy potential

In this section, we will answer the question how large the newly defined quantity, theentropy potential Π, can grow.
Theorem 20 Let A denote the active set from the Proposition 16. The entropy potential Π of a discrete distribution (wν )ν∈C has the following properties.
¡¢(i) It is lower bounded by the entropy of the distribution, Π ≥ H (wν )ν∈C .
(ii) It is finite if and only if the entropy is finite, hence, in the definition the supremum can be replaced by a maximum.
¡¢(iii) The upper bound Π ≤ H (wν )ν∈C wµ−1 always holds.
(iv) There are cases where this bound is sharp within a multiplicative constant.
(v) Π ≤ L(A), where L(A) from Proposition 16 is used.
©
ª(vi) With ν1 := arg max wν : ν ∈ A \ {µ} and A from Proposition 16, Π ≤ − log wν1
holds.
Proof. Part (i) is obvious. The same holds for (v), this can be seen by observingand (47). Part (ii) follows from (iii), which can be verified byk ≤ 1−p(A)e−L(A)
H≥−

Xwν log wν = p(A)L(A) ≥ wµ L(A) ≥ wµ Π,ν∈Awhere (v) was used. Since L(A) ≤ − log wν1 , (v) also implies (vi).
It remains to show (iv). To this aim, fix large numbers n, m ∈ N and set K = 2nm .
Let
C = {µ, νfool , ν1 , ν2 , . . . , νK }.
Set the probability distribution to
1
1
1
1, wµ = (1 − ), and pi = mnK
m
m
n
¡ ¢
for 1 ≤ i ≤ K. Then for the entropy of the model class, H (p) ≈ log 2, while wµ ≈ m1
and Π ≈ m log 2 ≈ H/wµ holds.
2
wfool = 1 −The general bound in Theorem 20 (iii) does not exclude cases where the entropy
potential is huge. And in fact, there are cases where this bound is sharp up to afactor, and also the cumulative quadratic Hellinger distance is of the same order:
∞
X

¡ ¢
¡ ¢
∆2 (ξ, Ξ) = Ω Π = Ω wHµ .

(56)

t=1

In order to see this, consider the case of Example 14 and choose large m, n > 1 andH0 := m. Then H ≈ log 2, wµ ≈ m1 , and Π ≈ H0 log 2 ≈ H/wµ . Moreover, as seen

26

J. Poland

above, the expected cumulative quadratic Hellinger error exceeds 21 H0 . Hence, forthis model class and prior, (56) holds.
Fortunately, for broad classes of discrete distributions, it is of reasonable sizeO(− log wµ ). Precisely, this happens if the tails of the probability distribution p
are sufficiently light.
Proposition 21 (i) If wν decays exponentially, Π = O(− log wµ ) holds. For simplicity, we may identify ν with its index in an enumeration, then exponential decay isreads as wν = O(αν ) for some α ∈ (0, 1).
(ii) If wν decays inverse polynomially, that is, wν = O(ν −b ) for b > 1, we have¡¢b2
Π = O − b−1
log wµ .
Note that the entropy potential does not depend on a reordering of the elementsof C. That is, we just need that there exists some reordering of C such that theprobabilities decay in the stated way.
Proof. We simplify the exposition and assume that the weights decay exactly exponentially or polynomially, respectively. The general case follows easily.
Therefore, in order to show (i), we identify C with {0, 1, . . .} and assume thatpi = αi (1 − α), for i = 0, 1, . . . and α ∈ (0, 1). For given k ∼= µ, i.e., k ≥ 0 is the index
of the reference element µ, we need to find an index j ≥ 0 such thatPi
αk k log α + ∞i=j α i log αP−j log α ≥ −.
(57)i
αk + ∞
i=j αThen, we know by (46) that the active set is a superset of {j, j + 1, . . .}, and inparticular Π ≤ − log pj = O(j) according to Theorem 20 (vi).
jαBy some elementary transformations, we see that (57) holds if j(αk + 1−α
) ≥
j+1

j

2

jα
α
α
kαk + (1−α)
2 + 1−α . This follows from j ≥ k + (1−α)2 , which is therefore sufficient tostate one index j which is necessarily contained in the active set. Hence O(j) = O(k),and (ii) is proven. (We remark that Theorem 20 (vi) gives a rough estimate here, inreality the order of the entropy potential is even smaller.)Part (ii) is shown in a similar way. Again we identify k ∼= µ. Here we assume

pi ' i−b for i ≥ 1 and b > 1. Then we need to find an index j ≥ 1 satisfying
P
−b
log i
k −b log k + ∞
i=j i
P
.
log j ≥∞ −b−b
k + i=j i(58)

Since (46) is scale invariant, this gives the desired subset of the active set. With some
¡
¢
¡
¢ P
−b
log i − log j implies (58).
transformations, we see that k −b log j − log k ≥ ∞i=j i
We may upper bound the sum on the r.h.s. by an integral and search for j such that
Z ∞
¡
¢
¡
¢
−b
log j − log k ≥ 1 +x−b log x − log j dxkj−(b−1)
1= 1 + (b−1)
2j27Consistency Theorems for Discrete Bayesian Learningb(the additional 1 stems from estimating the sum by the integral). Setting j = k b−1
satisfies this requirement for sufficiently large k and thus completes the proof of (ii).
2
If however the probability distribution decays very slowly, the entropy potential isof exponential order.
Theorem 22 If wν decays as ν −1 (log ν)−b for b > 2 and ν = 1, 2, . . ., we have Π =−1Ω(wµ b+1 ).
Proof. As in the proof of the last result, we assume that exactly pi ' i−1 (log i)− bholds for i = 1, 2, . . . and b > 2. We now need to show that for small j,P−1−bk −1 (log k)−b Lk + ∞i=j i (log i) Li
P
Lj <
,
−1
−b
k −1 (log k)−b + ∞i=j i (log i)where Li = log i + b log log i. This is satisfied if£¤
k −1 (log k)−b log j − log k + b(log log j − log log k <∞X£¤
i−1 (log i)−b log i−log j +b(log log i−log log j

(59)

i=j

holds. The r.h.s. sum can be approximated by an integral which evaluates to
1
b
+
.
b−1
2
(b − 1)(b − 2)(log j)(b − 1) (log j)b−2

(60)

1

We now set j = dexp(k b )e. Then for sufficiently large k, the first term of (60)dominates k −1 (log k)−b log j. Moreover, for sufficiently large k, the second term of (60)dominates k −1 (log k)−b log log j. Hence, this choice of j satisfies (59) for sufficiently
large k.
1

Given that the smallest index in A \ {µ} exceeds j = dexp(k b )e, how large is Π
1
at least? The answer is: Π ≥ 12 Lj = 21 (log j + b log log j) ≥ 12 k b , for k sufficiently
large. This can be seen easily, we just need to make sure that the contribution of theR ∞ dxtail A \ {µ} exceeds 21 . Approximating the tail weight by an integral, j x(log
=
x)b
b−1
1
1
, this contribution is b−1
k− b(b−1)(log j)b−1−1−band therefore exceeds the contribution of
the element µ, namely k (log k) , for large k.
1−

1

Finally, the proof is concluded by observing Π = Ω(k b ) = Ω(wµ b+1 ).

2

The entropy potential is infinite with the usual definition of a universal model class[LV97]. But with a slight modification of the prior, it becomes finite. Hence we canobtain a universal induction result for stochastic model selection:

28

J. Poland

Example 23 Consider a model class C corresponding to the set of programs on auniversal Turing machine. For ν ∈ C, let wν ∼ 2−K(ν) /K(ν)2 , where K denotes
the prefix Kolmogorov complexity – it is shown e.g. in [LV97] how to obtain sucha construction. Then H = O(1), and Theorem 19 implies consistency of universal
stochastic model selection with this prior and normalization. Had we chosen thePusual “canonical” weights wν ∼ 2−K(ν) , then H ∼K(ν)2−K(ν) = ∞, since K is the=smallest possible code length to satisfy the Kraft inequality, and any smaller growthmust necessarily result in an infinite sum. Hence the bound for universal stochastic
model selection is infinite with the usual prior.

References[BC91]

A. R. Barron and T. M. Cover. Minimum complexity density estimation.
IEEE Trans. Inform. Theory, 37(4):1034–1054, 1991.

[BD62]

D. Blackwell and L. Dubins. Merging of opinions with increasing information. Annals of Mathematical Statistics, 33:882–887, 1962.

[BM98] A. A. Borovkov and A. Moullagaliev. Mathematical Statistics. Gordon &Breach, 1998.
[BRY98] A. R. Barron, J. J. Rissanen, and B. Yu. The minimum description lengthprinciple in coding and modeling. IEEE Trans. Inform. Theory, 44(6):2743–
2760, 1998.
[CB90]

B. S. Clarke and A. R. Barron. Information-theoretic asymptotics of Bayes
methods. IEEE Trans. Inform. Theory, 36:453–471, 1990.

[CBL03] N. Cesa-Bianchi and G. Lugosi. Potential-based algorithms in on-line prediction and game theory. Machine Learning, 51(3):239–261, 2003.
[CD05]

J. W. Comley and D. L. Dowe. Minimum message length and generalized
Bayesian nets with asymmetric languages. In P. Grünwald, I. J. Myung,and M. A. Pitt, editors, Advances in Minimum Description Length: Theory
and Applications, pages 265–294. 2005.

[GL04]

P. Grünwald and J. Langford. Suboptimal behaviour of Bayes and MDL inclassification under misspecification. In 17th Annual Conference on Learning
Theory (COLT), pages 331–347, 2004.

[HP05]

M. Hutter and J. Poland. Adaptive online prediction by following the perturbed leader. Journal of Machine Learning Research, 6:639–660, 2005.

[Hut04] M. Hutter. Universal Artificial Intelligence: Sequential Decisions based on
Algorithmic Probability. Springer, Berlin, 2004.

Consistency Theorems for Discrete Bayesian Learning

29[LV97]

M. Li and P. M. B. Vitányi. An introduction to Kolmogorov complexity andits applications. Springer, 2nd edition, 1997.

[LW89]

N. Littlestone and M. K. Warmuth. The weighted majority algorithm. In
30th Annual Symposium on Foundations of Computer Science, pages 256–
261, Research Triangle Park, North Carolina, 1989. IEEE.

[PH05]

J. Poland and M. Hutter. Asymptotics of discrete MDL for online prediction.
IEEE Transactions on Information Theory, 51(11):3780–3795, 2005.

[PH06]

J. Poland and M. Hutter. MDL convergence speed for Bernoulli sequences.
Statistics and Computing, 16:161–175, 2006.

[Ris96]

J. J. Rissanen. Fisher Information and Stochastic Complexity. IEEE Trans.
Inform. Theory, 42(1):40–47, January 1996.

[Sol78]R. J. Solomonoff. Complexity-based induction systems: comparisons andconvergence theorems. IEEE Trans. Inform. Theory, 24:422–432, 1978.

[Vov90] V. G. Vovk. Aggregating strategies. In Proc. Third Annual Workshop on
Computational Learning Theory, pages 371–383, Rochester, New York, 1990.
ACM Press.
[WB68] C. S. Wallace and D. M. Boulton. An information measure for classification.
Computer Jrnl., 11(2):185–194, August 1968.
[WD99] C. S. Wallace and D. L. Dowe. Minimum Message Length and Kolmogorov
Complexity. Computer Journal, 42(4):270–283, 1999.