TCS -TR-A-06-11

TCS Technical Report

Potential Functions for Stochastic Model Selection

byJ. Poland

Division of Computer Science
Report Series A
March 3, 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

1

Potential Functions for Stochastic Model Selection

TCS-TR-A-06-11

March 3, 2006

Potential Functions for Stochastic
Model Selection
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
We prove performance guarantees for Bayesian learning algorithms, inparticular stochastic model selection, with the help of potential functions.
Such a potential quantifies the current state of learning in the system, ina way that the expected error in the next step is bounded by the expected
decrease of the potential. For Bayesian stochastic model selection, an appropriate potential function will be specified by introducing the entropy
potential, a quantity which we define as the worst-case entropy of a model
class with regard to the true model. The resulting cumulative error bounds
correspond to Solomonoff’s theorem and are essentially sharp. They imply
consistency, namely almost sure convergence of the predictive probabilities
to the true ones, and loss/regret bounds for arbitrary bounded loss function. Although we formulate our results in the classification framework,
they are equally applicable to the prediction of non-i.i.d. sequences.

1

Introduction

Most of the performance guarantees proven recently in learning theory fall into thecategory of “data dependent bounds”. They are powerful for constructing learningalgorithms and usually do not need any assumption on the data generating process.
On the other hand, if we want to make assertions about a learner’s (expected) quality,
before we have seen any data, a different type of performance guarantees is required:bounds that hold prior to any observation under certain assumptions on the data
generating process. This is the topic of the present paper.
An archetype for this latter sort of performance guarantees is Solomonoff ’s universal induction result [Sol78] (see Theorem 3 below). It gives a tight bound on the∗This work was supported by JSPS 21st century COE program C01.

2

J. Poland

expected cumulative quadratic error of a Bayesian mixture learner, provided that thelearner is based on a countable model class containing the data generating distribution. This does not only imply a very strong consistency assertion (namely almost
sure convergence, i.e. convergence with probability one), but also loss bounds for arbitrary loss function. A variant for continuously parameterized model class has been
given in [CB90]. Minimum description length (MDL) defines another class of learners
for which corresponding results are known [Ris96, PH05].
While, for given data, MDL and Bayes mixture learners make deterministic predictions, this is different for stochastic model selection, sometimes also referred to as
Gibbs sampling. For this learner we know of no corresponding theorem so far: Thisis the main focus of the present paper. A different important type of theorems has
been intensely studied for stochastic model selection in the recent past, namely PACBayesian theorems, e.g. [McA03]: They state that PAC bounds for a single model
carry over to a learner which selects models randomly according to a suitable posterior distribution.
By proving cumulative error bounds for the stochastic model selection learner,
we will obtain two conclusions: We will show that this learner is consistent in the(strong) sense that the predictive probabilities converge to the true ones almost surely.
Moreover we will obtain loss or regret bounds under arbitrary bounded loss functions.
Both results are, to our knowledge, new for this learner.
The present proofs 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. Again Solomonoff’s result can be understood as an archetype for thismethod, as we will see below. The potential method used here has been inspired bya related (but technically different) proof technique in prediction with expert advice[CBL03]. Also, note the fundamental difference between Bayesian stochastic model
selection, which we focus on, and the very popular stochastic expert selection algorithms, e.g. [FS97]. In the latter case, the posterior, according to which is sampled,is not Bayesian, but specifically designed for regret minimization. Expert algorithms
do not yield estimates for the probabilities governing the data.
In order to get a potential function for stochastic model selection satisfying thedesired properties, we will introduce the entropy potential. This quantity is definedas the worst-case entropy of the model class under all admissible transformations of
the weights, where the weight of the true distribution (which is in the model class by
assumption) is kept fixed. The entropy potential is possibly a novel definition in thiswork.
This paper is structured as follows. In the next section, we will introduce thenotation and prove Solomonoff’s result with a potential function. In Section 3, weconsider stochastic model selection and prove the main auxiliary result in order toobtain bounds. Section 4 defines the entropy potential and proves bounds for general

3

Potential Functions for Stochastic Model Selection

countable model class. In Section 5 we turn to the question how large the newly
defined entropy potential can be. The last section contains discussion and conclusions.

2

Setup and Bayes Mixture

We work in a general discrete Bayesian online classification framework with stochastic concepts. All our theorems and proofs carry over to the prediction of non-i.i.d.
sequences (this setup is defined e.g. in [PH05], compare also Remark 2).
Let X = {1 . . . |X |} be a finite alphabet, Z be a finite or countable set of possible
inputs (see again Remark 2), and C = ν1 , ν2 , . . . be a finite or countable model class.
Each model ν ∈ C specifies probability distributions1 on X for all inputs z ∈ Z, i.e. ν
is a functionX¡¢ν : z 7→ ν(x|z) x∈X where ν(x|z) ≥ 0 andν(x|z) = 1.
(1)
x∈X

P
Each ν ∈ C is assigned a prior weight wν > 0, where ν∈C wν = 1. (We need notconsider models with zero prior weight, as they don’t have any impact for anythingof what follows.) In order to make clear that we talk of the prior or initial weight,
opposed to a posterior weight, we will sometimes write wνinit instead of wν .
We assume that there is one data generating or true distribution µ ∈ C. Then the
online classification proceeds in discrete time t = 1, 2, . . .: An input zt is generated
by some mechanism (compare Remark 2 below) we must issue (i.e. the learner must¡¢
P
compute) a guess p(x) x∈X (where x∈X p(x) = 1) for the current probability vector¡¢¡¢µ(x|zt ) x∈X , and an outcome xt ∈ X is sampled according to µ(x|zt ) and revealed¡¢
to the learner (note that the probabilities µ(x|zt ) are not revealed).
After each observation xt , we may update the weights wν by Bayes’ rule, thus
obtaining, after time t − 1 and before time t, the posterior weightsQwν t−1i=1 ν(xi |ui ),wν (h<t ) = wν (h1:t−1 ) = wν (z1:t−1 , x1:t−1 ) = P
Qt−1 0
0
ν
(x
|u
)
w
0
i
i
ν
i=1
ν ∈C
where h<t = (z<t , x<t ) = (u1 , x1 , u2 , x2 , . . . , zt−1 , xt−1 ) denotes the history. Then, in
the Bayesian sense it is optimal to estimate the current probabilities according to theBayes mixtureXξ(x|zt , h<t ) =wν (h<t )ν(x|zt ).
ν∈C

Example 1 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.
1

We don’t consider semimeasures, as our methods below rely on normalized probability distributions. This restriction can be possibly lifted to some extent, however we do not expect theconsequences to be very interesting (see also Example 22).

4

J. Poland

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 o(− log wµ ) on the expected quadraticerror of Bayes mixture and stochastic model selection predictions, namely the l.h.s.
expressions of (4) and (7), respectively.
Remark 2 The inputs zt are not used at all throughout this paper, so the mechanism
which generates them doesn’t need to be specified. We could as well work in an inputless sequence prediction setup, which is common for Solomonoff induction (Theorem
3 below). We decided to keep the inputs, as stochastic model selection is usuallyconsidered in a classification setup (compare also Example 22). We incorporate theinputs into the history h<t , thus they don’t complicate the notation.
Solomonoff’s [Sol78] remarkable universal induction result tightly bounds the performance guarantee for the Bayes mixture with an arbitrary input sequence zt . For
introductory purpose, we prove it here in the classification setup. We use an appropriate potential function, thereby slightly modifying the proof from [Hut04].
Theorem 3 (Solomonoff’s universal induction result) 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 ).
(2)(All logarithms are natural in this paper.) 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 ) ≥X¡¢2µ(x|zt ) − ξ(x|zt , h<t ) .

(3)

x∈X

By summing up the expectation of (ii) while observing (i), we immediately obtain
Solomonoff’s assertion for arbitrary sequence of inputs z1 , z2 , . . .:∞X
t=1

Ekµ − ξk22 :=

∞
X
°
°2
E°µ(·|zt ) − ξ(·|zt , h<t )°2 ≤ Kinit = − log wµinit ,

(4)

t=1

where expectation is with respect to µ, and the squared 2-norm of a vector v ∈ R|X |P
is defined as usual, kvk22 = i vi2 . As we will see in the proof of Theorem 7, this
implies that the Bayes mixture probabilities ξ converge to the true probabilities µalmost surely.
t |zt )
Proof. Clearly, (i) holds. In order to show (ii), we observe that wµ (h1:t ) = wµ (h<t ) ξ(xµ(x.
t |zt ,h<t )Then, simplifying the notation by suppressing the history h<t and the current input
zt (e.g. K stands for K(h<t )),
³
´
X
°
£
¤
K − EK(x) = K −µ(x) K − log µ(x)= D µ(·|zt )°ξ(·|zt , h<t ) .
ξ(x)

x∈X

Potential Functions for Stochastic Model Selection

5

The r.h.s. here is called Kullback-Leibler divergence. By the following lemma it is an¡¢2P
upper bound for x∈X µ(x|zt ) − ξ(x|zt , h<t ) .
2
Lemma 4 For two probability distributions µ and ρ on X , we have
X¡
¢2 X
.
µ(a) log µ(a)µ(a) − ρ(a) ≤
ρ(a)
a∈X

a∈X

This well known inequality is proven for instance in [Hut04, Sec.3.9.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 5 Consider a binary alphabet and a model class containing three distributions ν1 , ν2 , ν3 , predicting νi (1|z) = 4i for some input z. Suppose µ = ν2 , i.e. the trueprobability is 12 . Then we cannot measure the learning progress after the observationin terms of K. However, there should be a progress, and indeed there is one, if we
consider the entropy of the model class. This will become clear with Lemma 6.

3

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.
Ξ(·|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 6 Assume that the current entropy of the model class,X
H(h<t ) = −wν (h<t ) log wν (h<t ),ν∈C6

J. Polandis finite. Then, for any input zt ,H(h<t )−Ext ∼ξ(·|zt ,h<t ) H(h1:t ) =≥Xwν (h<t )

ν∈C

X¡

X

wν (h<t )ν∈CX

ν(x|zt )ν(x|zt ) log ξ(x|zt ,h<t )x∈X

ν(x|zt ) − ξ(x|zt , h<t )

¢2

°
°2
=: E°Ξ − ξ °2 .

x∈X

Proof. The equality is straightforward computation. Then use Lemma 4 for theinequality.
2
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 7 (Predictive performance of stochastic model selection: loose bound) As¡¢
sume 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 ,°°2
PE (h<t ) − Ext ∼µ(·|zt ) PE (h1:t ) ≥ E°Ξ(·|zt , h<t ) − ξ(·|zt , h<t )°2 .
(5)Consequently, with Hinit = −

P

init
init
denoting the initial entropy,ν∈C wν log wν

∞
X
°
°2
E°Ξ − ξ °2 ≤ PEinit = Hinit /wµinit ,
t=1
∞
X

(6)

q
°
°2
E°Ξ − µ°2 ≤ − log(wµinit ) + Hinit /wµinit + 2 −Hinit log(wµinit )/wµinit ,

(7)

t=1

and the predictions by Ξ converge to the true probabilities µ almost surely.
t |zt )
Proof. Recall wµ (h1:t ) = wµ (h<t ) ξ(xµ(x. Since always 1/wµ (h<t ) ≥ 1, usingt |zt ,h<t )Lemma 6 we obtain (5) byXX¡¢
PE (h<t ) −µ(x|zt )PE (h1:t ) = wµ (h1 <t ) H(h<t ) −ξ(x|zt , h<t )H(h1:t )

x∈X

x∈X

°
°2
≥ E°Ξ(·|zt , h<t ) − ξ(·|zt , h<t )° .
2

Summing the
expectation up yields
Using thisq
together with (4) and the triangle
qP
qP(6).
°
°2
°
°2
°2
P °
inequality
E°Ξ − µ° ≤E °Ξ − ξ ° +
E°ξ − µ° , we conclude (7).
2Finally, almost sure convergence follows from

2

2

∞
³
´
³[©
ª´ X ¡¢ 1Xn→∞st ≥ ε ≤P st ≥ ε ≤Est −→ 0
P ∃t ≥ n : st ≥ ε = P
ε t=n
t≥n
t≥n

Potential Functions for Stochastic Model Selection

7°°2
for each ε > 0, with st = E°Ξ(·|zt , h<t ) − µ(·|zt , h<t )°2 .

2In particular, this theorem shows that the entropy of a model class, if it is initiallyfinite, necessarily remains finite almost surely. Moreover, it establishes almost sureasymptotic 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 8 Let the alphabet be binary. Let wµ = 1− n1 , in this way K ≈ n1 and can bemade 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 , andK other distributions with the same prior weight 1/(nK). In this way, the entropy ofthe model class is indeed close to H0 log 2. Let the input set be Z = {1 . . . nH0 }, andlet νb (1|z) = bz , where bz is the zth bit of ν’s index b in binary representation. Then
it is not hard to see that on the input stream z1:nH0 = 1, 2, . . . nH0 always µ = ξ.
Moreover, at each time, EkΞ − µk22 = 1/(4n). Therefore the cumulative error is H0 /4,
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 7, we used only one “wasteful” inequality, namely 1/wµ (h<t ) ≥1. The following lemma will be our main tool for obtaining better bounds.
Lemma 9 (Predictive performance of stochastic model selection, main auxiliary result) Suppose that we have some function B(h<t ), depending on the history, with thefollowing 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 ).

(8)

Proof. Because of (iii), we need to prove the lemma only for finite model class, thecountable case then follows by approximation. In this way we avoid dealing with a
Lagrangian on an infinite dimensional space below.

8

J. Poland

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)K + log(1 + H) −µ(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))
(9)
0
0
x0 µ(x )(1 + B(x ))
x∈X
P
P
ν(x)
ν wν
x ν(x) log ξ(x)
≥
,
(10)
1+B
(9) follows from assumption (ii), so that we only need to show (10) in order to complete
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) ≥
(11)
1+B
x∈X
for any probability vector µ̃ = (µ̃x )x∈X ∈ [0, 1]|X | withPx µ̃x = 1.

It is sufficient to prove (11) 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 (11) follows from
P
P
ν(x)
X ¡
ν wν
x ν(x) log ξ(x)µ(x) ¢µ̃x Ṽ (x) − log ξ̃(x) ≥f (µ̃) = log(1 + H) −
,
(12)
1+B
x∈X̃

where Ṽ (x) = log(1 −Pνwν ν(x)ν ν(x)).
log wξ(x)ξ̃(x)

We now identify the stationary points of the Lagrangian L(µ̃, λ) = f (µ̃)−λ¢1 . The derivative of L w.r.t. all µ̃x vanishes only if
λ = −Ṽ (x) + log µ(x)for all x ∈ X̃ .
ξ̃(x)

¡P

x µ̃x −(13)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 (13), (12) isx ξ(x)erewrites asPPν(x)ν∈C wν
x∈X ν(x) log ξ(x)≤ log(1 + H) + λ
(14)
1+B
X
X
X
£
¤
wν ν(x)ν ν(x)˜ξ(x)= log(1 −wν log wν ) − log 1 −log wξ(x)
.
ξ̃(x)
ν∈C

x∈X̃

ν∈C

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

x∈X0

ν∈C

x∈X0

Potential Functions for Stochastic Model Selection

9

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

ν∈C x∈X0ν ν(x)ν ν(x)
since the wξ(Xsum up to one and always wξ(x)≤ 1 holds.
0)2

We now present a simple application of this result for finite model classes.
Theorem 10 (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
£
¤
E°Ξ − ξ °2 ≤ PFinit = (1 + log N ) log(1 + Hinit ) − log(wµinit ) .

(15)

t=1

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

4

Entropy potential and countable classes

We now generalize Theorem 10 to arbitrary countable model classes. First note that
there is one very convenient fact about the potential function proofs so far: (3), (5),and (8) 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 9, 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 11 Fix binary alphabet and let C˜ and Z̃ be model class and input spaceof Example 8. Let C = C˜ ∪ {νfool }, Z = Z̃ ∪ {0}, wfool = 1 − m1 , and the rest of theprior of mass m1 be distributed to the other models as in Example 8. 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 /4, while the entropy can be made arbitrarily small forlarge m.

10

J. Poland¡¢P
Definition 12 (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
¡
© ¡
¢
¢
ª
Π (wν )ν∈C = sup H ( P w0 νwpν0 p 0 )ν : pµ = 1 ∧ pν ∈ [0, 1] ∀ν ∈ C \ {µ} .
(16)
ν

ν

ν

Here, the supremum is taken over all possible assignments of the multiplying probabilities pν ∈ [0, 1], where pµ = 1.
Clearly, Π ≥ H. According to Theorem 7, Π 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 9.
P
Proposition 13 (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 \ {µ}.
(17)
w(A)
ν 0 ∈A

We call A the set of active models (in Π). Then, with log pν = L(A) − log wν forν ∈ C \ S, log pν = 0 for ν ∈ A \ {µ}, and k = |C \ A|, we have¡¢¡¢
Π = Π (wν )ν∈C = H ( P w0 νwpν0 p 0 )ν∈C
¡ ν ν ν¢= log k + w(A)eL(A) .
(18)
Moreover, this is scaling invariant in the weights, i.e. (17) yields the correct active
set and (18) 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 (16) cannot be attained if some pν = 0.
To this aim, let p ∈ [0, 1]|C| be the multiplying probabilities, assume pν = 0, and set¢¡
H̃ = H ( P w0 νwpν0 p 0 )ν . Now assume pν > 0 and observe that
ν

ν

ν

¡
¢
£
¤
H ( P w0 νwpν0 p 0 )ν = −pν wν log(pν wν ) + (1 − pν wν ) − log(1 − pν wν ) + H̃ ≥ H̃νννholds if − log(pν wν ) ≥ H̃. This can be realized for small enough pν > 0, hence themaximum of (16) cannot be attained for pν = 0.
Therefore, for a maximum of (16), we need that for each ν ∈ C \ {µ}, either pν = 1
PPor, with wp (C) = ν wν pν and Lp (C) = − wp1(C) ν wν pν log(wν pν ),0=¢¡dH ( P w0 νwpν0 p 0 )ν
ν

dpν

ν

ν

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

(19)

Those ν satisfying the latter condition have log pν = −L(C)−log wν and hence L(C) =L(C \ {ν}). Therefore, each possible maximum of (16) corresponds to a subset Ã ⊂ CPotential Functions for Stochastic Model Selection11of active models, such that µ ∈ Ã and furthermore pν = 1 for ν ∈ Ã and log pν =−L(Ã) − log wν for ν ∈/ Ã. Since only log pν ≤ 0 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 wν
equals the average complexity of all ν ∈ Ã. Hence
X wν
¢
¡
¢
¡
wν
= L(Ã) + log w(Ã) + ke−L(Ã)
H ( P w0 νwpν0 p 0 )ν = −
log P
ν ν
ν
w(Ã)
ν 0 ∈C wν 0ν∈Ã¡¢
= log k + w(Ã)eL(Ã) ,which proves (18) for any such Ã. Observe that our A defined in the assertion is thesmallest feasible subset and therefore 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 wetake out ν1 . But in this case, the derivative, computed as the r.h.s. of (19), is nonpositive at pν1 = 1. Thus we may increase the entropy by decreasing pν1 until thederivative 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 (17) and the value (18) w.r.t. the weights iseasy to see.
2
The following result states that the the entropy potential decreases in expectation.
This will allow us to obtain the desired bound with Lemma 9.
Theorem 14 For any history h<t and current input zt ,Xµ(xt |zt )Π(h1:t ) ≤ Π(h<t ).
xt ∈XProof. We need to show the assertion only for finite model class: Once this isestablished, 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 ,
(20)
x∈X̃

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

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

12

J. Poland

implies 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 ,(21)

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 (21), 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 13). Denote the respective sets of activemodels by A, A0 , A1 . Recall that the constructions in Proposition 13 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 ) ¡=e− log[w̃ν pν ] − L1 (A1 ) > 0 for ν ∈ A1 \ {µ},
1
dpν
Π
¡
¢
1
1
1
where dΠ>0follows
from
−
log[
w̃
p
]
−
L
(A
)
> 0 for ν ∈ A1 (and analogouslyνν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 it
10
becomes active in Π1 , then, because of dΠ> 0 and dΠ
= 0, the term (1 − µ̃)Π0 + µ̃Π1
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

(22)

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(22). In order to show that I 01 is non-empty, we first argue that I 01 ⊃ I := (1 −

13Potential Functions for Stochastic Model Selection

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) ,1Pw̃ν (1−pν)
1log w̃ (1−pν)Aw̃0 (A)
ν

+

P

1

0

1

= e−L (A) + e−L (A) ≥ e−L(A)w̃ν pν
1
A w̃1 (A) log w̃ν pν

(23)

e
e
implies that I is not empty. We will verify (23) below.
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.
P

Now, in order to show (23), observe that eAw̃ν (1−pν)
1log (1−pν)w̃0 (A)P w̃ν pν
log 1
w̃(A)
≤ w̃0 (A) and e A w̃1 (A) pν ≤w̃(A)by Jensen’s inequality, so (23) follows fromw̃1 (A)w̃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 (21), 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
¢
w̃ν ¡
dΠ
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)2
i,j=1

14

J. PolandThis Hessian is negative semi-definite by Lemma 15 below, and so is the Hessian of
Π0 . This concludes the proof.
2
Lemma 15 Let N ≥ 1 and wi > 0 for 0 ≤ i ≤ N (the wi need not sum up to one).
PN
PN wi
Let W =w
andassume
that
−
log
w
≥
L
:=
−
i
j
i=0
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.

(24)

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 (24) w.r.t. w0 ,
¡ PN
¢2 h
N
i
X
2
u2i
i=1 ui+
1 + L + log w0 ,wiW
i=1
is positive, since − log w0 − L < 0. Thus we may decrease the l.h.s. of (24) 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 W̃ui uj
ui uj+ Di + Dj − 1 =+ Di + Dj − 1
w
w
i
i
i,j=1
i,j∈{1...N }\{k}
¸
·
X
wi 2
wk 2
u − 2(1 − Di )ui uk +
u .
(25)
+
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 (25) isnonnegative. Thus the assertion follows from the induction hypothesis.
2
Now we can prove the main result of this paper.
Theorem 16 (Predictive performance of stochastic model selection) For countablemodel class C containing the true distribution µ, define the potential 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
°
°2
¤
£
E°Ξ − ξ °2 ≤ P init = (1 + Πinit ) log(1 + Hinit ) − log(wµinit ) .

(26)

t=1

Proof. Using Theorem 14, this follows directly from Lemma 9.

2

Theorem 16 implies performance guarantees for arbitrary bounded loss functions.

Potential Functions for Stochastic Model Selection

15

Corollary 17 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 `Ξ<∞ be the corresponding quantity
for the stochastic model selection learner. Then the loss of the learner is bounded byp
E`Ξ<∞ ≤ E`µ<∞ + 2C + 2 2CE`µ<∞ ,
¡q
£
¤ √
¢2
where C =(1 + Πinit ) log(1 + Hinit ) + Kinit + Kinit .
Proof sketch. First, we have to prove Theorem
16 for the°2 Hellinger distance instead
P ∞ °√√of the quadratic distance, arriving at t=1 E° Ξ − µ°2 ≤ C. This is straightforward, since Lemma 4 and Lemma 6 also hold for the Hellinger distance. Then, theresult follows from [PH05, Lemma 24–26] with one additional application of Jensen’s
inequality.
2
Similar and even slightly stronger loss bounds hold for different stochastic model
selection algorithms derived from prediction with expert advice, e.g. the Hedge algorithm [FS97] for finite model class or FPL [HP05] for countable class. The expert
proof techniques do not even require µ ∈ C, but work without any assumption on
the data generating process. The experts posterior, according to which is sampled,is not Bayesian, but specifically designed in order to minimize loss. However, thesealgorithms do not give estimates for the true probabilities µ, and consequently no
consistency in this sense can be proved. We expect that Bayesian algorithms are superior to expert algorithms in cases where probability estimates can be obtained andare beneficial.

5

The magnitude of the entropy potential

In this section, we will partially answer the question how large the newly definedquantity, the entropy potential, can grow. We start with a general bound.
Proposition 18 The µ-entropy potential is always bounded by Π ≤ H/wµ . Thereare cases where this bound is sharp up to a factor.
P
Proof. With A denoting the active set, we have that H ≥ − ν∈A wν log wν =w(A)L(A) ≥ wµ L(A) ≥ wµ Π. In order to see that this bound is sharp in general,consider the model class C = {µ, ν ∗ , ν1 . . . νN }, where wν ∗ ≥ 21 , wµ = 12 (1 − wν ∗ ), and1(1 − wν ∗ ). Then Π > log 2 + 12 log N , but H = H(wν ∗ , 1 − wν ∗ ) +wν1 = . . . = wνN = 2N
2wµ (log 2 + 21 log N ). Thus, Π > 12 wµ−1 (H − H(wν ∗ , 1 − wν ∗ )) holds in this case. 2

16

J. Poland

Proposition 18 gives a worst-case bound which is of course not satisfactory: Using
it in Theorem 16, the resulting bound becomes no better than that of Theorem 7.
Fortunately, in most cases, the entropy potential behaves well and is much smaller.
For finite model classes, it is clearly at most the logarithm of the size of the class.
We present two different infinite model classes in the following, one where the weights
decay rapidly, and one where they decay slowly.
Example 19 Consider a model class with rapidly decaying weights (2−i )i≥1 , andsuppose that the true model has index k. Then it has complexity k log 2. Moreover,P
i log 2since ∞
i=k 2i−k+1 = (k + 1) log 2, in the computation of Π, all models i ≥ k are active,
and consequently Π = log(k + 3) = O(K). In contrast, the entropy of the model classis 2 log 2.
Example 20 Consider a model class with slowly decaying weights ( i26π2 )i≥1 , and let
2 2
the true model have index k, i.e. complexity log k 6π . In order to estimate Π this
£
2 2
2 2
time, we have to find a sufficiently large index j such that log j 6π ≥ k12 log k 6π +¤ 1 P∞ 1
P∞ 1
i2 π 2/[ k2 + j i2 ]. Substituting the sums by appropriate integrals, we makej i2 log 6
the r.h.s. larger and look for a j such thati+2
j 2π2 h 1
k 2 π 2 log
1
1
6
log
+
≥
log
+
.
k2
j
k2
6
6
j−1
(j−1)2 π 2This is satisfied for j − 1 = k 2 , as an elementary computation verifies. Consequently,¡¢
the active set consists of at most k 2 models, and Π ≤ log k 2 + O(k 2 log k 4 ) =¡¢O log(k) = O(K). The entropy of the model class is O(1).
In both of the above examples, we have that Π = O(K) = O(− log wµ ). We believethat this is the typical behavior of the entropy potential, in contrast to Proposition
18. It remains open to precisely characterize those well-behaved cases:
Problem 21 Characterize those weight distributions satisfying Π = O(K).
Finally, our bounds are infinite with the usual definition of a universal model class.
But with a slight modification of the prior, they become finite. Hence we can obtaina universal induction result for stochastic model selection:
Example 22 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 16 implies consistency of universal
stochastic model selection with this prior and normalization. If we would have chosenPthe usual “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
code length must necessarily result in an infinite sum. Hence the bound for universal
stochastic model selection is infinite with the usual prior.

Potential Functions for Stochastic Model Selection

617Discussion and conclusions

We have shown that the cumulative quadratic error of Bayesian stochastic model
selection in countable model classes is finitely bounded if the entropy is so. This
corresponds to results for Bayes mixture and MDL learners (which however have noentropy in their bounds). Unlike the MDL bound [PH05], our bound obtained here
is usually not exponential in the complexity of the true distribution (but can be so
in bad cases). Our results imply strong consistency (almost sure convergence) of thestochastic model selection learner, and moreover loss bounds for arbitrary bounded
loss functions. According to Examples 1, 8, and 11, our cumulative error bound (26),which is of order K · Π, is essentially sharp in the sense that both ingredients K andΠ are necessary. We don’t know if the bound needs to be the product K · Π, or if thesmaller sum K + Π is also possible.
There is hope that the entropy potential introduced in this work has other applications in learning and information theory. It remains open to study this quantity morethoroughly and characterize the weight distributions where it behaves well (Problem
21). Moreover, this paper show new ways to evaluate the state of learning in a discretemodel class. The general potential P from Theorem 16 always strictly decreases in
expectation unless all models predict the same (so it does not share the undesirable
property of K discussed in Example 5). A couple of interesting questions remain open,
such as defining a good potential function for active learning.

References[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.
[FS97]

Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line
learning and an application to boosting. Journal of Computer and System
Sciences, 55(1):119–139, 1997.

[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.
[LV97]

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

[McA03] D. McAllester. PAC-bayesian stochastic model selection. Machine Learning,
51(1):5–21, 2003.

18

J. Poland[PH05]

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

[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.