Chapter 4

How Well Do Bayes Methods Work for On-Line Prediction of {±1} Values?^{∗}

D. Haussler^{†}  A. Barron^{‡}

Abstract

We look at sequential classification and regression problems in which {±1}-labeled instances are given on-line, one at a time, and for each new instance, before seeing the label, the learning system must either predict the label, or estimate the probability that the label is +1. We look at the performance of Bayes method for this task, as measured by the total number of mistakes for the classification problem, and by the total log loss (or information gain) for the regression problem. Our results are given by comparing the performance of Bayes method to the performance of a hypothetical “omniscient scientist” who is able to use extra information about the labeling process that would not be available in the standard learning protocol. The results show that Bayes methods perform only slightly worse than the omniscient scientist in many cases. These results generalize previous results of Haussler, Kearns and Schapire, and Opper and Haussler.

1 Introduction

Several recent papers in the area of computational learning theory have studied sequential classification problems in which {±1}-labeled instances (examples) are given on-line, one at a time, and for each new instance, the learning system must predict the label before it sees it [18, 19, 20, 30, 17, 22, 27, 21]. Such systems adapt on-line, learning to make better predictions as they see more examples. If n is the total number of examples, then the performance of these on-line learning systems, as a function of n, has

∗Both authors acknowledge the support of the Mathematical Sciences Research Institute at Berkeley where much of the work was done, and NSF grant NSF-DMS 8505550, which supported the work at MSRI.

†Baskin Center for Computer Engineering and Information Sciences, University of California, Santa Cruz, CA 95064, haussler@cse.ucsc.edu. The work of this author was supported by ONR grant N00014-91-J-1162 and NSF grants CDA-9115268 and IRI-9123692.

‡Department of Statistics, Yale University, Box 2179, New Haven, CN 06520-2179, barron@stat.yale.edu. Work supported by ONR grants N00014-89-J-1811 and N00014-93-1-0085.

been measured both by the total number of mistakes (incorrect predictions) they make during learning, and by the probability of a mistake on the nth example alone. The latter function is often called a learning curve (see also [15]).

Sequential regression problems have also been studied [11, 9, 10, 31, 32, 33, 34, 1, 2, 27, 21]. In this case, instead of predicting either +1 or −1, the learning system outputs a probability distribution, predicting that the label will be +1 with a certain probability, and −1 with one minus that probability. When there is some noise or uncertainty in the labeling process, an output of this type is more informative than a simple prediction of either +1 or −1. The notion that the purpose of statistical inference is to make sequential probability forecasts for future observations, rather than to extract information about parameters, is known as the prequential approach in statistics [11]. To measure the performance of a sequential regression system of this type, it is common to use the log loss function. If you predict that the label will be +1 with probability p and −1 with probability 1 − p, then your log loss is − log p if the label is +1 and − log(1−p) if the label is −1, i.e., whatever happens, your loss is the negative logarithm of the probability you assigned to that event. As in sequential classification, performance has been measured both in terms of total log loss over all examples, and in terms of expected loss on the nth example (and in several other ways as well).

In this paper we look at the performance of Bayes methods for both classification and regression, analyzing only the total loss over all examples. Our viewpoint is decision theoretic, so both classification and regression are treated in a common framework. When the examples are generated randomly, the average total loss of a method will be called the risk. Bayes methods are optimal in that they have the smallest possible risk, at least when the examples are generated randomly by the same process implicit in the prior distribution used by the method. When the examples are not generated at random by this process, then the performance of Bayes methods degrade. However, we show that they still perform well in many cases.

We do this by introducing the idea of an “omniscient scientist” who is privy to extra information about the nature of the process that generates the examples, and comparing the performance of Bayes method to that of the omniscient scientist. For example, if each label is generated by applying a fixed function to the instance and then adding noise to the result (i.e., flipping the sign of the value with some probability), then the omniscient scientist will already know the fixed “target function” and will only have to deal with the noise, whereas the Bayes method will have to try to learn the target function and also deal with the noise. We show that Bayes method does not perform much worse than the omniscient scientist in many cases of this type. In particular, the total loss of the omniscient scientist is usually linear in n, whereas the additional loss of Bayes method is only logarithmic in n. We obtain upper bounds on this additional loss that generalize related bounds obtained in [17] and [22] (see also [1, 2, 27]). We also look at the performance of the Bayes method on an arbitrary sequence of examples, as compared with the performance of an omniscient scientist who already knows the best target function to use in predicting the labels of that particular sequence of examples. Again, in many cases Bayes methods do not do much worse. These results extend work in [30, 20] and also tie in with the coding/information theory approach in [21, 3, 4] (see also [35]). Throughout the paper, our emphasis is on obtaining performance bounds that hold for all sample sizes n, rather than asymptotic bounds that hold only for large n.

2 Formal Framework

Here we outline the general decision theoretic framework we use. Let X, Y and A be sets, called the instance, outcome, and decision spaces, respectively, and let L : Y × A → ℜ be a loss function. In this paper we assume that Y = {±1}, although the basic formal framework, definition of Bayes method, and the results for log loss hold for more general Y. When Y = {±1}, elements of Y may be thought of as classification labels. However, because we sometimes consider more general Y, we will use the more general term “outcomes”. The particular kinds of loss functions we consider are the following.

1. 0-1 loss (used for the classification problem): A = Y = {±1}, action ŷ ∈ A is interpreted as a prediction of the outcome y ∈ Y, and L(y, ŷ) = 1 if ŷ ≠ y, L(y, ŷ) = 0 if ŷ = y.

2. log loss (used for the regression problem): Here instead of predicting a single outcome, an action specifies a probability for each possible outcome y ∈ Y. The decision space A is the family of all probability distributions on Y, and for y ∈ Y and distribution P ∈ A, L(y, P) = − log P (y). The base of the logarithm can be arbitrarily chosen. If we need to be specific, we use the notation ln and log_{2} to denote the natural logarithm and the logarithm base two, respectively.

A pair (x, y), with x ∈ X and y ∈ Y is called an example. We assume that we receive a sequence S^{n} = (x_{1}, y_{1}), …, (x_{n}, y_{n}) of examples on line, one at a time. The number n of examples is called the sample size. For each time t, 1 ≤ t ≤ n, given only (x_{1}, y_{1}), …, (x_{t−1}, y_{t−1}) and x_{t}, we must choose an action a_{t} ∈ A. After taking this action, we observe the outcome y_{t}, and suffer loss L(y_{t}, a_{t}). Our goal is to choose actions a_{1}, …, a_{n} so as to minimize our total loss ∑_{t=1}^{n} L(y_{t}, a_{t}).

Throughout most of this paper we focus on the case when the sequence x_{1}, …, x_{n} of instances is fixed arbitrarily and only the outcomes y_{1}, …, y_{n} vary. If one wants to use these results for the case when both the instances and the outcomes vary, one can either average over possible sequences x_{1}, …, x_{n}, or take the worst case over such sequences, depending on what type of result one desires. For now let us fix the sequence of instances x_{1}, …, x_{n}. To simplify the notation in what follows, we will no longer mention the x_{t}s in our formulae, focusing only on the sequence y_{1}, …, y_{n} of outcomes. For a particular sequence y_{1}, …, y_{n}, for further brevity, we define y^{t} = (y_{1}, …, y_{t}) for every 0 ≤ t ≤ n. Thus y^{0} denotes the empty sequence.

Finally, for a random variable X, we denote by E(X) the expectation of X. We use P, P_{θ}, etc. to denote probability distributions. For random variables X and Y, we denote a conditional distribution on Y given that X = x by P_{Y |x}. If the distribution is not clear from the context when we take an expectation, then we make it explicit by subscripting, as in E_{P_{θ}}(Y) or E_{P_{Y |x}}(Y). The latter is abbreviated E(Y |x).

2.1 Priors

In this paper we concentrate on Bayes methods for choosing the actions a_{1}, …, a_{n} to try to minimize the total loss on the outcomes y_{1}, …, y_{n}. Bayes methods utilize prior information on which sequences of outcomes are more likely than others in order to choose appropriate actions. For fixed instance sequence x_{1}, …, x_{n} this prior information consists of a prior distribution P over an (arbitrary) index set Θ, and a class {P_{θ} : θ ∈ Θ} of probability distributions over the set Y^{n} of possible outcome sequences. (When Θ is continuous, P is a density.) Each distribution P_{θ} actually represents a conditional distribution on possible outcome sequences y_{1}, … y_{n}, given that the instance sequence is x_{1}, …, x_{n}. However, since this instance sequence is fixed for now, to avoid cluttering our notation, we omit this implicit conditioning on the x_{t}s.

The prior information used by a Bayes method can be interpreted as the belief that the sequence of outcomes is generated at random in the following manner. First an index θ is selected at random from Θ according to the prior distribution P. The index θ is viewed as an unknown underlying “state of Nature” that determines the probabilities of various sequences of outcomes via the corresponding distribution P_{θ}. After θ is chosen, the actual outcome sequence y^{n} = y_{1}, …, y_{n} is chosen at random from Y^{n} according to P_{θ}. Thus the outcome y_{t} can be considered to be a realization of the random variable Y_{t}, 1 ≤ t ≤ n, where Y_{1}, …, Y_{n} are (not usually independent) random variables with joint distribution defined by the above two step process. Note that implicit in this model is the assumption that the action taken at the current time t does not affect the outcome at time t, nor do past actions influence future instances or outcomes. Thus the model studied in this paper is much more appropriate for problems like predicting the weather than for learning to fly an airplane.

Even though they implicitly make very specific assumptions about how outcomes are generated, Bayes methods can be applied whether or not outcome sequences are really generated in the assumed manner or an equivalent manner. We evaluate the performance of Bayes methods both under the optimistic assumption that outcome sequences are generated in the manner described above, and under certain more pessimistic assumptions. In the extreme case, even though the Bayes method uses a prior distribution, we analyze the performance of the method assuming nothing about the way the actual outcome sequence is generated [11, 30, 20].

We are often interested in certain special types of prior information that may be available to help choose an appropriate action. The type of prior information available determines the kind of learning problem one has. Three special cases of interest are described below, in order of increasing generality. We present results for some of these special cases later.

Case 1: Noise-free functions. In this case, for each state of nature θ ∈ Θ there is a function f_{θ} : X → Y. Let F = {f_{θ} : θ ∈ Θ}. By assuming that initially a state of nature θ ∈ Θ is chosen at random according to the prior P, we are in effect assuming that a target function f_{θ} is chosen at random from F according to the induced prior on F. After the target function is chosen, for any instance x ∈ X, the outcome y is f_{θ}(x), independent of any previous instances, outcomes and actions, i.e., a state of nature is deterministic and noise-free. Thus for any θ and any fixed sequence of instances x_{1}, …, x_{n}, the outcome sequence y_{1}, …, y_{n} is completely determined: the distribution P_{θ} assigns probability 1 to the event (y_{1}, …, y_{n}) = (f_{θ}(x_{1}), …, f_{θ}(x_{n})). The performance of Bayes methods for this case was studied in [17, 23].

Case 2: Functions corrupted by i.i.d. noise. Here a state of nature is represented by a function, but the the observations are altered by an independent noise process. Thus, as in Case 1, for each θ ∈ Θ there is a possible target function f_{θ} : X → Y, and some f_{θ} is chosen at random according to the prior P. However, for the instance sequence x_{1}, …, x_{n}, instead of observing the outcome sequence (y_{1}, …, y_{n}) = (f_{θ}(x_{1}), …, f_{θ}(x_{n})), we observe (y_{1}, …, y_{n}) = (η_{1}f_{θ}(x_{1}), …, η_{n}f_{θ}(x_{n})), where the (unobserved) noise events η_{1}, … η_{n} are independent and identically distributed, with η_{t} = −1 with probability λ and η_{t} = +1 with probability 1−λ, the noise rate λ being known. Since for a given θ and instance sequence x_{1}, …, x_{n}, many different outcome sequences are possible, here P_{θ} is not a trivial distribution on Y^{n} like it was in Case 1. The performance of Bayes method for this case was studied in [22] for a particular class of functions.

Case 3: Conditionally independent Y_{t}s. In this case, the random variables Y_{1}, …, Y_{n} are conditionally independent given θ and x_{1}, …, x_{n} (and completely independent of the actions taken). This includes the previous case, as well as the more general cases in which either the noise rate is not known but we have a prior distribution over possible noise rates, or the noise events are independent but not identically distributed. This latter case occurs, for example, if the distribution for the noise event η_{t} depends on the instance x_{t}, i.e., observations of the outcome are less reliable for some instances than they are for others. One way to capture this is with the statistical regression setup in which for each θ ∈ Θ there is a distribution D_{θ} on X × Y, and after θ is chosen, examples (x_{1}, y_{1}), …, (x_{n}, y_{n}) are chosen independently according to D_{θ}. Thus for a given θ and x_{1}, …, x_{n}, the random variables Y_{1}, …, Y_{n} are independent, and the distribution of Y_{t} is the marginal of D_{θ} for X = x_{t}. For this case P_{θ} is the joint distribution of these Y_{t}s.

2.2 Definition of Bayes Method

We now return to the most general case where Θ indexes an arbitrary set {P_{θ} : θ ∈ Θ} of distributions on Y^{n}, i.e., arbitrary joint distributions on the random variables Y_{1}, …, Y_{n}. In this section we derive the general form of Bayes method for this case. To simplify our formulae, we use the following notation.

• P (θ) denotes the prior probability of state θ ∈ Θ, or the density at θ if the prior is given as a density function.

• For all t, 0 ≤ t ≤ n, and θ ∈ Θ,

P (y^{t}|θ) = P_{θ}(y^{t}) = P_{θ}{(ŷ_{1}, …, ŷ_{n}) : ŷ_{i} = y_{i}, 1 ≤ i ≤ t}.

• For any y ∈ Y,

P (Y_{t} = y|y^{t−1}, θ) = P_{θ}(Y_{t} = y|y^{t−1})
= P_{θ}{(ŷ_{1}, …, ŷ_{n}) : ŷ_{i} = y_{i}, 1 ≤ i ≤ t − 1, ŷ_{t} = y}
/P_{θ}(y^{t−1})

(assuming that P_{θ}(y^{t−1}) ≠ 0, else it is undefined.).

• P (y^{t}) = ∑_{θ∈Θ} P (y^{t}|θ)P (θ) if Θ is countable, otherwise P (y^{t}) = ∫_{θ∈Θ} P (y^{t}|θ)P (θ)dθ.

• For any y ∈ Y, P (Y_{t} = y|y^{t−1}) = ∑_{θ∈Θ} P (Y_{t} = y|y^{t−1}, θ)P (θ|y^{t−1}) if Θ is countable, otherwise P (Y_{t} = y|y^{t−1}) = ∫_{θ∈Θ} P (Y_{t} = y|y^{t−1}, θ)P (θ|y^{t−1})dθ.

Note that P (θ|y^{t}), used above, is calculated by Bayes rule:

P (θ|y^{t}) = \frac{P (θ)P (y^{t}|θ)}{P (y^{t})}.

Given the above notation, Bayes method of choosing actions can be stated quite simply:

At each time t, choose the action a ∈ A that minimizes

∑_{y∈Y} P (Y_{t} = y|y^{t−1})L(y, a).

The logic of this is simple. If your belief that outcome sequences are generated at random in the two step process described above is correct, then P (Y_{t} = y|y^{t−1}) is the probability that the t^{th} outcome will be y, given that the previous t − 1 outcomes were y_{1}, …, y_{t−1}. This is called the posterior probability of y (having seen y^{t−1}). Hence ∑_{y∈Y} P (Y_{t} = y|y^{t−1})L(y, a) is the expected loss you will suffer if you take action a at time t (the posterior expected loss). Bayes method is simply to choose the action that minimizes the (posterior) expected loss.

Bayes method leads to familiar strategies for both the 0-1 and log losses. Here we describe the action a_{t} taken by Bayes method in each of these cases for a general outcome space Y.

1. 0-1 loss:

a_{t} = ŷ_{t} = argmin_{ŷ∈Y} ∑_{y∈Y,y≠ŷ} P (Y_{t} = y|y^{t−1})
(1)  = argmax_{ŷ∈Y} P (Y_{t} = ŷ|y^{t−1})

Hence in this case Bayes method predicts the outcome that has the highest posterior probability.

2. log loss:

a_{t} = P̂_{t} = argmin_{P̂∈A} ∑_{y∈Y} P (Y_{t} = y|y^{t−1}) log \frac{1}{P̂(y)}
(2)  = P_{Y^{t}|y^{t−1}} (whenever this distribution is in A)

The latter equality follows from the fact that the relative entropy^{1} is minimal between a distribution and itself (see, e.g., [8]). Hence in this case Bayes method simply produces the posterior distribution on Y_{t} as its action.

Since Bayes method always chooses the action that minimizes the posterior expected loss, it is clear that when the actual outcome sequence is in fact generated by the two step random process implicit in the Bayes prior, then the expected loss at each time t is minimized by this strategy, among all possible prediction strategies. Hence the expected total loss is also minimized by the Bayes method. The expected (total) loss is known as Bayes risk, and denoted

(3) R(P) = Rbayes(P) = ∑_{y^{n}∈Y^{n}} P (y^{n})L_{bayes,P}^{T} (y^{n}),

where L_{bayes,P}^{T} (y^{n}) is the total loss on the outcome sequence y_{1}, …, y_{n} when the actions taken are those of the Bayes method using prior P.

2.3 Evaluating Bayes Performance: Omniscient Scientists

Because the Bayes method is optimal in terms of the risk when outcome sequences are drawn according to the given prior, the Bayes risk is a lower

1See section 3.2 for a definition of relative entropy.

bound on the risk of any strategy for choosing actions in this case. In the following sections we give some estimates of the Bayes risk, as a function of the sample size n, in some common cases. However, before proceeding with this, we define a few more pessimistic types of risks we want to look at.

First, let us still assume that the true underlying “state of Nature” is some θ^{∗} ∈ Θ, and that the outcome sequence y^{n} is chosen at random according to the distribution P_{θ^{∗}}. However, let us not assume that θ^{∗} itself is actually chosen at random. Rather, for each possible θ ∈ Θ, we define the risk when θ is true by

(4) r(θ) = rbayes(θ) = ∑_{y^{n}∈Y^{n}} P (y^{n}|θ)L_{bayes,P}^{T} (y^{n}).

Thus r(θ) is the average total loss of Bayes method using an (implicit) prior P over possible states of Nature, when the outcome sequences are in fact generated randomly according to the particular state of nature θ. Of course, Bayes method does not minimize the risk in this case (i.e., for a particular θ = θ^{∗}). To minimize the risk for a particular θ^{∗}, we would require an omniscient scientist (OS) who somehow knew at the outset, before any examples were given, that θ^{∗} was the true state of nature. To obtain optimal risk for this particular θ^{∗}, the omniscient scientist would then use a Bayes method in which the prior distribution P over the index set Θ assigns probability 1 to θ^{∗} and probability 0 to everything else. Hence the omniscient scientist is also a Bayesian, but a better informed one. We denote the total loss on the outcome sequence y_{1}, …, y_{n} when the actions taken are those of the omniscient scientist using true state θ^{∗} by L_{os,θ^{∗}}^{T}(y^{n}). Similarly, we denote the risk of the omniscient scientist when θ^{∗} is true by

ros(θ^{∗}) = ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗})L_{os,θ^{∗}}^{T}(y^{n}). (5)

Note that for noise-free functions, the risk ros(θ^{∗}) of the omniscient scientist is zero for any reasonable loss function, since in this case knowledge of the true state of nature θ^{∗} allows one to predict the outcomes perfectly. In the case that Θ indexes a set of functions corrupted by i.i.d. noise, the risk r_{OS}(θ^{∗}) is simply n times the average loss of predicting one noisy outcome, knowing the distribution of that outcome. Surprisingly, we show below that in many cases the risk of the original Bayes method, which does not know θ^{∗}, is not much worse than that of the omniscient scientist, no matter what θ^{∗} is the true state of Nature.

Finally, we might be much more pessimistic, and assume nothing whatsoever about the actual outcome sequence y^{n}. We can simply look directly at the total loss L_{bayes,P}^{T} (y^{n}) of the Bayes method (using prior P) for each fixed outcome sequence y^{n}. Of course, it is usually the case that for any outcome sequence y^{n} there is a strategy for choosing actions that does extremely well on that particular sequence. So it is uninteresting (and perhaps unfair) to compare the performance of Bayes algorithm on each particular sequence to the performance of the best strategy for that sequence. However, if we again restrict ourselves to the type of omniscient scientist introduced above, then we do get some interesting results. In this case the omniscient scientist is not as omniscient as she could be, i.e., she doesn’t know beforehand what the outcome sequence y^{n} will be; rather, she knows which state of nature θ ∈ Θ is the best one to assume true for the particular sequence of outcomes y^{n} that is about to happen, i.e., she knows θ̂ = θ̂(y^{n}) = argmin_{θ∈Θ}L_{os,θ}^{T}(y^{n}). The risk for the OS in this case is

L_{os,θ̂}^{T}(y^{n}) = min_{θ∈Θ} L_{os,θ}^{T}(y^{n}).

Again surprisingly, we show below that in many cases the risk of the original Bayes method is not much worse than that of the omniscient scientist, no matter what the actual outcome sequence y^{n} is.

One final note: In defining r(θ), R(P), etc. in this and the previous section, we have assumed that the particular loss function being used is clear from the context. If this is not the case, then a subscript will be used to denote the loss function, as in R_{log} or R_{0−1}. Other subscripts may be dropped if they are clear from the context.

3 Results for Log Loss

Throughout this section the loss function is assumed to be the log loss. All of the results in this section, except for the specific applications mentioned in the last subsection, hold when Y is an arbitrary countable set. By changing to densities in appropriate places, they hold also for continuous Y.

3.1 Performance on Arbitrary Outcome Sequences

We begin with the most pessimistic case, assuming nothing about the outcome sequence y^{n}. As we have noted above, for the log loss scenario, Bayes method simply returns the posterior distribution as its action. Thus the action taken at time t is

a_{t} = P_{Y^{t}|y^{t−1}}.

Hence the total loss of Bayes method is

L_{bayes,P}^{T} (y^{n}) = ∑_{t=1}^{n} L(y_{t}, a_{t})

= − ∑_{t=1}^{n} log P (y_{t}|y^{t−1})

= − log ∏_{t=1}^{n} P (y_{t}|y^{t−1})
(6)  = − log P (y^{n}).

Hence the total loss is the information gained by seeing the outcome sequence y^{n}. This simple information theoretic interpretation of the total loss is what makes the log loss so useful.

We want to compare the total loss of Bayes method to that of an omniscient scientist who already knows the best state of nature θ̂ ∈ Θ to assume for predicting the outcome sequence y^{n}, even before the outcomes are observed.

For each time t, the omniscient scientist returns the distribution

a_{t} = P̂_{t} = P_{Y^{t}|y^{t−1},θ̂}.

Hence the total loss of the omniscient scientist is

L_{os,θ̂}^{T}(y^{n}) = ∑_{t=1}^{n} L(y_{t}, a_{t})

= − ∑_{t=1}^{n} log P (y_{t}|y^{t−1}, θ̂)

= − log ∏_{t=1}^{n} P (y_{t}|y^{t−1}, θ̂)
(7)  = − log P (y^{n}|θ̂).

The state θ̂ used by the omniscient scientist is the best possible for the sequence y^{n}, i.e.,

θ̂ = θ̂(y^{n})
= argmin_{θ∈Θ}{L_{os,θ}^{T}(y^{n})}
= argmin_{θ∈Θ}{− log P (y^{n}|θ)}
= argmax_{θ∈Θ}P (y^{n}|θ).

Hence in the case of the log loss, θ̂ is the maximum likelihood estimate (MLE) of the “true” state of nature, based on the (as yet unseen) outcome sequence y^{n}. (Even though in this section we do not assume there really is a “true” state of nature.)

We focus now on the difference between the Bayes loss and the loss of the omniscient scientist. This difference is given by

L^{Δ}(y^{n}) ≐ L_{bayes,P}^{T} (y^{n}) − L_{os,θ̂}^{T}(y^{n})
(8)  = log \frac{P (y^{n}|θ̂)}{P (y^{n})}.

Let us first assume that Θ is countable. Then from the above, we have

L^{Δ}(y^{n}) = log \frac{P (y^{n}|θ̂)}{P (y^{n})}

= log \frac{P (y^{n}|θ̂)}{∑_{θ∈Θ} P (y^{n}|θ)P (θ)}
≤ log \frac{P (y^{n}|θ̂)}{P (y^{n}|θ̂)P (θ̂)}
(9)  = log \frac{1}{P (θ̂)}.

Thus the additional loss suffered by the Bayes method is at most the extra information provided to the omniscient scientist, namely the number of bits needed to describe the MLE θ̂ with respect to the prior P. This observation was made in [12]. However, it may be something of a “folk theorem” in the statistics/information theory community.

The above argument cannot be applied if Θ is uncountable and P is a distribution on Θ unless P puts positive mass at the point θ̂ ∈ Θ (and hence cannot be represented as a density), or P assigns positive probability to the set of all θ that are MLEs, in the case that the MLE θ̂ is not unique. Furthermore, for both countable and uncountable Θ, even if the prior distribution does put positive mass on the MLE θ̂, the above estimate ignores the beneficial effect of other θ ∈ Θ that may also give the outcome sequence y^{n} relatively high probability, and thereby help the Bayes method to perform better on y^{n}. We now derive some better upper bounds that overcome these shortcomings. These upper bounds can also be applied in the case of countable Θ, although we state them only in the continuous form here. We begin with the following observation.

L^{Δ}(y^{n}) = log \frac{P (y^{n}|θ̂)}{P (y^{n})}
= log \frac{P (y^{n}|θ̂)}{∫_{θ∈Θ} P (y^{n}|θ)P (θ)dθ}
= − log ∫_{θ∈Θ} \frac{P (y^{n}|θ)}{P (y^{n}|θ̂)}P (θ)dθ
(10)  = − log ∫_{0}^{1} P \{θ : \frac{P (y^{n}|θ)}{P (y^{n}|θ̂)} ≥ z\} dz

= − log ∫_{0}^{1} P \{θ : \frac{1}{n} ln \frac{P (y^{n}|θ̂)}{P (y^{n}|θ)} ≤ \frac{− ln z}{n} \} dz

(11)  = − log ∫_{0}^{∞} P \{θ : \frac{1}{n} ln \frac{P (y^{n}|θ̂)}{P (y^{n}|θ)} ≤ x\} ne^{−nx}dx

Step (10) follows from the fact that E(Z) = ∫_{0}^{M} P {Z ≥ z}dz for any random variable Z taking values in the interval [0, M], and the last step follows by a simple change of variable.

Let

N_{r}(θ̂, y^{n}) = \{θ : \frac{1}{n} ln \frac{P (y^{n}|θ̂)}{P (y^{n}|θ)} ≤ r\}

and

g(r) = P (N_{r}(θ̂, y^{n}))

for each r ≥ 0. Intuitively, for small r we may think of N_{r}(θ̂, y^{n}) as a kind of “neighborhood” around the MLE θ̂ in which other θ ∈ Θ live who assign similar probabilities to the outcome sequence y^{n}. When this neighborhood has large enough prior probability g(r) for small enough “radius” r, then Bayes method will work well for that y^{n}. For larger r, the negative exponential term in the integral (11) dominates, and the contribution is negligible. What radius is small enough depends on the rate at which g(r) grows. Since g(r) is nondecreasing, we can use the estimate

∫_{0}^{∞} g(x)ne^{−nx}dx ≥ sup_{r≥0} {g(r) ∫_{r}^{∞} ne^{−nx}dx}
(12)  = sup_{r≥0}{g(r)e^{−nr}}

to obtain (from (11) above)

L^{Δ}(y^{n}) ≤ − log sup_{r≥0}{g(r)e^{−nr}}
= inf_{r≥0}{− log (g(r)e^{−nr})}
= inf_{r≥0}{nr − log(g(r))}
(13)  = inf_{r≥0}{nr − log P (N_{r}(θ̂, y^{n}))}.

Note that when g(0) > 0, i.e., when the prior puts positive mass on the set N_{0}(θ̂, y^{n}) of all θ that are MLEs for y^{n}, then we can use the estimate

(14)  L^{Δ}(y^{n}) ≤ − log P (N_{0}(θ̂, y^{n})).

This gives a slightly more general version of the “folk theorem” (9).

Another interesting case is when g(0) = 0 but the prior probability g(r) = P (N_{r}(θ̂, y^{n})) grows with the radius r at least as fast as a volume of radius r in k-dimensional space for some k. This can happen when Y is continuous and the index set Θ gives a smooth enough finite dimensional real vector-valued parameterization of the class {P_{θ} : θ ∈ Θ} (see, e.g., [24, 7, 9, 34]). In particular, let us assume that g(0) = 0 but there exist c, k, ϵ_{0} > 0 such that g(r) ≥ cr^{k} for all 0 ≤ r ≤ ϵ_{0} In this case from (13) we have

(15)  L^{Δ}(y^{n}) ≤ inf_{0≤r≤ϵ_{0}}{nr − k log r − log c}.

Differentiating with respect to r, we find that the infimum is obtained for r = k/n. When k/n ≤ ϵ_{0}, this gives

(16) L^{Δ}(y^{n}) ≤ k + k log \frac{n}{k} − log c = (1 + o(1))k log n,

where o(1) is a quantity that goes to zero as the sample size n → ∞.

3.2 Performance on Random Sequences Assuming True State of Nature

We now look at the risk (i.e., average total loss) of Bayes method when the outcome sequence is generated at random according to an unknown true state of nature θ^{∗} ∈ Θ, as compared to the risk for an omniscient scientist who knows the true state θ^{∗}. By the same argument used in the previous section, the difference in these two risks is

r^{Δ}(θ^{∗}) ≐ rbayes(θ^{∗}) − r_{OS}(θ^{∗})
= ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗})L_{bayes,P}^{T} (y^{n}) − ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗})L_{OS,θ^{∗}}^{T}(y^{n})
= ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗})(L_{bayes,P}^{T} (y^{n}) − L_{OS,θ^{∗}}^{T}(y^{n}))

= ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗}) log \frac{P (y^{n}|θ^{∗})}{P (y^{n})}
(17)  ≐ I(P_{Y^{n}|θ^{∗}} ∥ P_{Y^{n}}),

where I(P ∥ Q) = E_{P} log \frac{P (X)}{Q(X)} denotes the relative entropy or Kullback-Leibler divergence between distribution P and distribution Q.

Continuing the analogy with the previous section, for each r ≥ 0 let

N_{r}(θ^{∗}) = {θ : I(P_{Y^{n}|θ^{∗}} ∥ P_{Y^{n}|θ}) ≤ rn}.

Hence now we define a neighborhood N_{r}(θ^{∗}) around θ^{∗} instead of a neighborhood around θ̂(y^{n}), and this neighborhood includes all θ ∈ Θ that assign probabilities to outcomes y^{n} that are similar to the probabilities assigned by θ^{∗}, at least on y^{n} that are likely under θ^{∗}. Now for countable Θ and any r ≥ 0

I(P_{Y^{n}|θ^{∗}} ∥ P_{Y^{n}}) = ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗}) log \frac{P (y^{n}|θ^{∗})}{P (y^{n})}

= ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗}) log \frac{P (y^{n}|θ^{∗})}{∑_{θ∈Θ} P (y^{n}|θ)P (θ)}

≤ ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗}) log \frac{P (y^{n}|θ^{∗})}{∑_{θ∈N_{r}(θ^{∗})} P (y^{n}|θ)P (θ)}

= ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗}) log \frac{P (y^{n}|θ^{∗})}{∑_{θ∈N_{r}(θ^{∗})} \frac{P (θ)}{P (N_{r}(θ^{∗}))}P (y^{n}|θ)}
− log P (N_{r}(θ^{∗}))
≤ ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗}) ∑_{θ∈N_{r}(θ^{∗})} \frac{P (θ)}{P (N_{r}(θ^{∗}))} log \frac{P (y^{n}|θ^{∗})}{P (y^{n}|θ)}

− log P (N_{r}(θ^{∗})) (18)

= ∑_{θ∈N_{r}(θ^{∗})} \frac{P (θ)}{P (N_{r}(θ^{∗}))}I(P_{Y^{n}|θ^{∗}} ∥ P_{Y^{n}|θ}) − log P (N_{r}(θ^{∗}))
(19)  ≤ rn − log P (N_{r}(θ^{∗})),

where (18) follows from Jensen’s inequality, using the convexity of log \frac{1}{x}, and (19) follows from the definition of N_{r}(θ^{∗}). The same result follows similarly for continuous Θ (see [5]).

From (17) and (19), in analogy with (13), we have

(20)  r^{Δ}(θ^{∗}) ≤ inf_{r≥0}{rn − log P (N_{r}(θ^{∗}))}.

3.3 Bayes Risk

Finally we look at the Bayes risk. This is the expected cumulative loss of Bayes method when the outcome sequence is generated in the manner specified by the prior P, namely, a true state of nature θ^{∗} ∈ Θ is selected at random according to the prior P, and then a sequence y^{n} of observations is generated at random according to P_{θ}^{∗}. In keeping with the philosophy of the previous sections, we compare the Bayes risk with the risk of an omniscient scientist who knows θ^{∗} before seeing y^{n}. Thus we define

(21)  Ros(P) ≐ ∑_{θ^{∗}∈Θ} P (θ^{∗})r_{OS}(θ^{∗})

and

R^{Δ}(P) ≐ Rbayes(P) − Ros(P)
= ∑_{θ^{∗}∈Θ} P (θ^{∗})(rbayes(θ^{∗}) − r_{OS}(θ^{∗}))
= ∑_{θ^{∗}∈Θ} P (θ^{∗})I(P_{Y^{n}|θ^{∗}} ∥ P_{Y^{n}})
(22)  ≐ I(Θ; Y^{n}),

where I(X; Y) = ∑_{x∈X} P_{X}(x)I(P_{Y |x} ∥ P_{Y}) denotes the mutual information between the random variables X and Y. Here we view the state of nature θ ∈ Θ and the outcome sequence y^{n} ∈ Y^{n} as dependent random variables with the joint distribution defined (implicitly) by the prior P and the set {P_{θ} : θ ∈ Θ}.

Let Π be any partition of Θ into a countable sequence Θ_{1}, Θ_{2}, … of pairwise disjoint subsets of Θ with ⋃_{i} Θ_{i} = Θ. Each Θ_{i} is called an equivalence class. For each θ ∈ Θ, let Π(θ) denote the equivalence class containing θ.

The entropy of Π is given by

H(Π) = −E_{P} log P (Π(θ)) = − ∑_{i=1}^{∞} P (Θ_{i}) log P (Θ_{i}).

(The entropy can be infinite.) The average diameter of Π is defined by

D(Π) = ∑_{i=1}^{∞} P (Θ_{i}) sup_{θ^{∗},θ∈Θ_{i}} I(P_{Y^{n}|θ^{∗}} ∥ P_{Y^{n}|θ}).

Using tricks like those used in the previous section, for any countable Θ and any partition Π we get

I(Θ; Y^{n}) = ∑_{θ^{∗}∈Θ} P (θ^{∗}) ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗}) log \frac{P (y^{n}|θ^{∗})}{P (y^{n})}

= ∑_{θ^{∗}∈Θ} P (θ^{∗}) ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗}) log \frac{P (y^{n}|θ^{∗})}{∑_{θ∈Θ} P (y^{n}|θ)P (θ)}

≤ ∑_{θ^{∗}∈Θ} P (θ^{∗}) ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗}) log \frac{P (y^{n}|θ^{∗})}{∑_{θ∈Π(θ^{∗})} P (y^{n}|θ)P (θ)}

= ∑_{θ^{∗}∈Θ} P (θ^{∗}) ( ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗}) log \frac{P (y^{n}|θ^{∗})}{∑_{θ∈Π(θ^{∗})} \frac{P (θ)}{P (Π(θ^{∗}))}P (y^{n}|θ)}

− log P (Π(θ^{∗})))

≤ ∑_{θ^{∗}∈Θ} P (θ^{∗}) ( ∑_{θ∈Π(θ^{∗})} \frac{P (θ)}{P (Π(θ^{∗}))} ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗}) log \frac{P (y^{n}|θ^{∗})}{P (y^{n}|θ)}

− log P (Π(θ^{∗})))

= ( ∑_{θ^{∗}∈Θ} P (θ^{∗}) ∑_{θ∈Π(θ^{∗})} \frac{P (θ)}{P (Π(θ^{∗}))}I(P_{Y^{n}|θ^{∗}} ∥ P_{Y^{n}|θ})) + H(Π)
≤ D(Π) + H(Π).

(23)

The same result also holds for continuous Θ.

From (22) and (23) we have

(24)  R^{Δ}(P) ≤ inf partitions Π of Θ{D(Π) + H(Π)}.

3.4 Applications

To upper bound the total risk of Bayes method under the log loss, we can simply calculate the risk of the omniscient scientist, and add to it the upper bounds on the difference between the risk of the Bayes method and that of the omniscient scientist. This method is usually easy to use, because the risk for the omniscient scientist is usually easy to calculate. In particular, whenever the Y_{t}s are conditionally independent given θ, then the risk of the omniscient scientist in each of the cases treated in the previous three subsections is:

• for arbitrary y^{n}: L_{os,θ̂}^{T}(y^{n}) = − ∑_{t=1}^{n} log P (y_{t}|θ̂),

• for particular true state of nature θ^{∗}: ros(θ^{∗}) = ∑_{t=1}^{n} H(Y_{t}|θ^{∗}), and

• for random state of nature drawn by P:

Ros(P) = ∑_{θ^{∗}∈Θ} P (θ^{∗}) ∑_{t=1}^{n} H(Y_{t}|θ^{∗}), where H(Y_{t}|θ^{∗}) = − ∑_{y∈Y} P (Y_{t} = y|θ^{∗}) log P (Y_{t} = y|θ^{∗}). Thus, for example, for learning {±1}-valued functions with i.i.d. sign noise with rate λ,

Ros(P) = ros(θ^{∗}) = h_{λ}n, (25)

where h_{λ} = −λ log λ − (1 − λ) log(1 − λ), and

(26) L_{os,θ̂}^{T}(y^{n}) = N log \frac{1}{λ} + (n − N) log \frac{1}{1 − λ},

where N is the minimum number of noisy outcomes in any interpretation of y^{n}, i.e., N = min_{θ∈Θ} |{t : y_{t} ≠ f_{θ}(x_{t})}|.

3.4.1 Finite Θ

Let us illustrate this method with a simple application of the “folk theorem” (9). Suppose that Θ is finite and the prior distribution P is uniform over Θ. Then by (9), for any outcome sequence y^{n},

(27) Lbayes^{Δ}(y^{n}) ≤ log \frac{1}{P (θ̂)} = log |Θ|.

Hence for Θ indexing a class of {±1}-valued functions with i.i.d. sign noise with rate λ,

(28) Lbayes^{T}(y^{n}) ≤ N log \frac{1}{λ} + (n − N) log \frac{1}{1 − λ} + log |Θ|.

For large enough n, the additional loss log |Θ| of the Bayes method over and above that of the omniscient scientist will be negligible. By averaging over y^{n}, we obtain the related upper bound of h_{λ}n + log |Θ| for the risk of Bayes method when the outcome sequence is generated at random, either according to a fixed state of nature θ^{∗} or a random θ^{∗}.

3.4.2 Infinite Θ, Noisy {±1}-Valued Functions

For infinite (possibly uncountable) Θ indexing a class of {±1}-valued functions with i.i.d. sign noise with rate λ, an only slightly more sophisticated method gives useful bounds in many cases. These are the cases when the class F = {f_{θ} : θ ∈ Θ} has finite VC dimension. This notion can be defined briefly as follows:

For any class F of functions from X → {±1} and sequence S = (x_{1}, …, x_{m}) of points in X, we say that S is shattered by F if for any sequence (y_{1}, …, y_{m}) of values in {±1}, there is a function f ∈ F with y_{i} = f(x_{i}) for all i, 1 ≤ i ≤ m. The VC Dimension of F, denoted dim(F), is defined as the length m of the longest such shattered sequence, over all possible finite sequences of points in X. Further discussion and examples of this concept can be found in [28, 6].

Now let us consider the case where F = {f_{θ} : θ ∈ Θ} and x_{1}, …, x_{n} is a fixed instance sequence. Let us define the partition Π of Θ by letting

Π(θ) = Π(θ^{∗}) ↔ f_{θ}(x_{t}) = f_{θ}^{∗}(x_{t}), 1 ≤ t ≤ n.

By the most basic theorem connected with the VC dimension, known as the Sauer/VC lemma [29, 25], the number |Π| of distinct equivalence classes in Π is bounded by

|Π| ≤ ∑_{i=0}^{d} \binom{n}{i} ≤ (\frac{en}{d})^{d} , (29)

where d = dim(F) and e is the base of the natural logarithm. (The latter inequality holds for n ≥ d.) It follows that for any prior P on Θ,

H(Π) ≤ d log \frac{en}{d}, (30)

since the entropy is maximized for the uniform distribution on Π, and takes the value log |Π| in this case. Furthermore, by our definition of Π it is clear that if Π(θ) = Π(θ^{∗}), then θ and θ^{∗} induce the same conditional distribution on Y^{n}. Hence I(P_{Y^{n}|θ^{∗}} ∥ P_{Y^{n}|θ}) = 0. If follows that D(Π) = 0. Putting this all together, and applying (24), we get the following bound for the Bayes risk:

For all n ≥ d = dim(F), all instance sequences x_{1}, …, x_{n}, and all priors P on Θ,

(31) R^{Δ}(P) ≤ D(Π) + H(Π) ≤ d log \frac{en}{d} = (1 + o(1))d log n and hence

R(P) ≤ h_{λ}n + d log \frac{en}{d}, (32)

when the noise rate is λ, where h_{λ} = −λ log λ − (1 − λ) log(1 − λ).

Using the other bounds given in the previous sections, upper bounds can also be obtained for the risk of Bayes method when the outcome sequence y^{n} is arbitrary, and when it is generated at random from a particular θ^{∗}. However, the bounds in these cases depend on the probability P (Π(θ̂)) (resp. P (Π(θ^{∗}))) of the relevant equivalence class in the partition Π. If all equivalence classes have roughly the same prior probability, then the result is much the same as given above for the Bayes risk. Otherwise more careful analysis is required.

Sometimes we can also obtain interesting bounds even in the case that the VC dimension of F is infinite. Here we also average over random choices of the instances x^{n} = (x_{1}, …, x_{n}), and instead of using the VC dimension, we use the VC entropy [29] (see also [17]). Let Q be a distribution on the instance space X, and assume that each x_{t} is chosen independently at random according to Q. For each x^{n} define the partition Π_{x^{n}} of Θ as above by letting

Π_{x^{n}}(θ) = Π_{x^{n}}(θ^{∗}) ↔ f_{θ}(x_{t}) = f_{θ}^{∗}(x_{t}), 1 ≤ t ≤ n.

The VC entropy of F (for sample size n) is E_{Q^{n}}(log |Π_{x^{n}}|). It is clear that the above derivation of (32) can be generalized to obtain

E_{Q^{n}}(R(P)) ≤ h_{λ}n + E_{Q^{n}}(log |Π_{x^{n}}|). (33)

4 0-1 Loss

We now derive upper bounds on the risk of Bayes method for the 0-1 loss. As shown in (1), for this loss function Bayes method predicts the outcome with the highest posterior probability. Thus for outcome sequence y^{n} = (y_{1}, …, y_{n}) ∈ Y^{n}, where Y = {±1}, and 1 ≤ t ≤ n, the action a_{t} of Bayes method at time t is the prediction

a_{t} = ŷ_{t} = argmax_{y∈{±1}}P (y|y^{t−1}). (34)

The total 0-1 loss for an outcome sequence y^{n} ∈ {±1}^{n} is the total number of times this prediction is incorrect, i.e.,

L_{bayes,P,0−1}^{T}(y^{n}) = |{t : y_{t} ≠ ŷ_{t}, 1 ≤ t ≤ n}|. (35)

This is often called the number of mistakes.

4.1 Performance on Arbitrary Outcome Sequences

Littlestone and Warmuth [20, 19] and Vovk [30] have obtained bounds on the number of mistakes made by Bayes method for arbitrary {±1}-valued outcome sequences for the case that Θ is a countable class {f_{θ} : θ ∈ Θ} of functions and the prior information assumes that outcomes are generated by applying sign noise with known rate λ (even though the actual outcome sequence is arbitrary). The bound from [20] is particularly easy to derive, and generalizes to continuous Θ easily as well. We give a variant of this derivation now.

First, let us define the Heavyside function Θ by letting Θ(x) = 1 if x ≥ 0 and Θ(x) = 0 if x < 0. We use the fact that for any b and x, where 0 < b, x ≤ 1,

Θ(b − x) ≤ \begin{matrix}log & \frac{1}{x} \\ log & \frac{1}{b} \end{matrix} , (36)

which is easily verified (assuming 0/0 = 1). We note also that since 0 ≤ λ ≤ 1/2,

\frac{1}{2(1 − λ)} ≤ 1

and

P (y^{t}) = ∑_{θ∈Θ} P (y^{t}|θ)P (θ)
= ∑_{θ∈Θ} P (y_{t}|θ)P (y^{t−1}|θ)P (θ)
≤ ∑_{θ∈Θ}(1 − λ)P (y^{t−1}|θ)P (θ)
= (1 − λ)P (y^{t−1}),

thus

\frac{P (y^{t})}{(1 − λ)P (y^{t−1})} ≤ 1.

(Of course the same result holds for continuous Θ.)

It is clear that Bayes method makes a mistake only when the posterior probability of the outcome y_{t}, given the previous outcomes y^{t−1}, is less than or equal to one half. Hence the total number of mistakes is bounded by

L_{bayes,P,0−1}^{T}(y^{n}) ≤ |{t : P (y_{t}|y^{t−1}) ≤ 1/2, 1 ≤ t ≤ n}|
= |\{t : \frac{P (y^{t})}{P (y^{t−1})} ≤ 1/2, 1 ≤ t ≤ n\}|

= ∑_{t=1}^{n} Θ (\frac{1}{2} − \frac{P (y^{t})}{P (y^{t−1})})

= ∑_{t=1}^{n} Θ (\frac{1}{2(1 − λ)} − \frac{P (y^{t})}{(1 − λ)P (y^{t−1})})

≤ ∑_{t=1}^{n} \frac{log_{2} \frac{(1−λ)P (y^{t−1})}{P (y^{t})}}{log_{2}(2(1 − λ))}
= \frac{n log_{2}(1 − λ) − log_{2} P (y^{n})}{1 + log_{2}(1 − λ)}

(37)  = \frac{n log_{2}(1 − λ) + L_{bayes,P,log_{2}}^{T}(y^{n})}{1 + log_{2}(1 − λ)},

where the last equality follows from (6).

It is very useful to have a bound for the risk of Bayes method under the 0-1 loss in terms of the risk under the log loss, because this allows us to apply the results of the previous section. In particular, from (26), we have

L_{bayes,P,log}^{T}(y^{n}) = L_{os,θ̂,log}^{T}(y^{n}) + L_{bayes,log}^{Δ}(y^{n})
(38)  = N log \frac{1}{λ} + (n − N) log \frac{1}{1 − λ} + L_{bayes,P,log}^{Δ}(y^{n}),

where N = min_{θ∈Θ} |{t : y_{t} ≠ f_{θ}(x_{t})}| is the minimum number of noisy outcomes in any interpretation on y^{n}. Note that this is the same as the 0-1 loss of the omniscient scientist, i.e., N = L_{OS,P,0−1}^{T}(y^{n}). Hence, combining (37) and (38),

L_{bayes,P,0−1}^{T}(y^{n}) ≤ \frac{(log_{2} \frac{1−λ}{λ}) L_{OS,P,0−1}^{T}(y^{n}) + L_{bayes,P,log_{2}}^{Δ}(y^{n})}{1 + log_{2}(1 − λ)}. (39)

In particular, if Θ is finite and the prior P is uniform on Θ then from (27) we have

(40) L_{bayes,P,0−1}^{T}(y^{n}) ≤ \frac{(log_{2} \frac{1−λ}{λ}) L_{OS,P,0−1}^{T}(y^{n}) + log_{2} |Θ|}{1 + log_{2}(1 − λ)}.

Other bounds on L_{bayes,P,log}^{Δ}(y^{n}) can be plugged in in other circumstances.

4.2 Performance for Random Sequences Assuming True State of Nature

Using the same prior as in the previous section, we now assume that the outcome sequence is actually generated at random according to the distribution P_{θ^{∗}} for some true state of nature θ^{∗}. In the case of {±1}-valued functions with independent sign noise, which we examine here, this means that y_{t} = f_{θ^{∗}}(x_{t}) with probability 1 − λ and y_{t} = −f_{θ^{∗}}(x_{t}) with probability λ. The risk of Bayes method under 0-1 loss for this case is the average total number of mistakes made by Bayes method.

We can obtain bounds on the average total number of mistakes by averaging the formulae from the previous section (e.g., (39)), using the fact that min_{θ∈Θ} |{t : y_{t} ≠ f_{θ}(x_{t})}| ≤ |{t : y_{t} ≠ f_{θ}^{∗}(x_{t})}|, and hence the average performance of the omniscient scientist who uses knowledge of the MLE for each individual outcome sequence is at least as good as the risk (= average performance) of the omniscient scientist that uses knowledge of θ^{∗}. Since the expectation of |{t : y_{t} ≠ f_{θ}^{∗}(x_{t})}| is λn, from (39), this gives

r_{bayes,P,0−1}(θ^{∗}) ≤ \frac{log_{2} \frac{1−λ}{λ}}{1 + log_{2}(1 − λ)}λn + \frac{r_{bayes,P,log_{2}}^{Δ}(θ^{∗})}{1 + log_{2}(1 − λ)}.

Unfortunately, this bound is not tight. We show how to get rid of the extra \frac{log_{2} \frac{1−λ}{λ}}{1+log_{2}(1−λ)} factor in front of the λn. This is especially important, since in most cases the remaining term is O(log n).

The main idea is to bound the difference in 0-1 loss at time t between the Bayes method and the omniscient scientist in terms of the difference at time t of the corresponding log loss. Fix the outcome sequence y^{n}. The loss of Bayes method at time t is − log P (y_{t}|y^{t−1}), and the loss at time t of the omniscient scientist who knows the true state of nature θ^{∗} is − log P (y_{t}|y^{t−1}, θ^{∗}) = − log P (y_{t}|θ^{∗}), since Y_{t} is conditionally independent of Y_{1}, …, Y_{t−1} given θ^{∗} in the case of {±1}-functions with independent sign noise. Thus the difference in these losses is

L_{t,log}^{Δ}(y^{n}) ≐ log \frac{P (y_{t}|θ^{∗})}{P (y_{t}|y^{t−1})}. (41)

Let K_{λ}(x) = λ log \frac{λ}{x} + (1 − λ) log \frac{1−λ}{1−x} for λ ≤ x ≤ 1 − λ. We can rewrite the difference between the risk of Bayes method and the risk of the omniscient scientist under the log loss as follows.

r_{log}^{Δ}(θ^{∗}) = ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗}) ∑_{t=1}^{n} L_{t,log}^{Δ}(y^{n})

= ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗}) ∑_{t=1}^{n} log \frac{P (y_{t}|θ^{∗})}{P (y_{t}|y^{t−1})}

(42)  = ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗}) ∑_{t=1}^{n} ∑_{y∈Y} P (Y_{t} = y|θ^{∗}) log \frac{P (Y_{t} = y|θ^{∗})}{P (Y_{t} = y|y^{t−1})}

(43)  = ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗}) ∑_{t=1}^{n} K_{λ}(p_{t}),

where p_{t} = P (Y_{t} = −f_{θ^{∗}}(x_{t})|y^{t−1}). Equation (42) looks a bit strange at first, but all that is really being introduced here is superfluous averaging over possibilities that we are already averaging over in the outermost sum. Thus the overall expectation is unchanged. This method is analogous to that used in [17]. The last equation, (43), follows directly from the definition of the noise model. It is easily verified that we always have λ ≤ p_{t} ≤ 1 − λ.

We now derive analogous equations for the 0-1 loss. Let h be the modified Heavyside function defined by h(x) = 1 if x > 0, h(x) = 0 if x < 0 and h(0) = 1/2. We assume that for the 0-1 loss, Bayes method tosses a fair coin to make its prediction when the posterior probabilities of −1 and +1 are each 1/2. This will make our analysis easier, and does not affect previous results.

Under these assumptions, for fixed y^{n} the 0-1 loss of Bayes method at time t (averaging over coin tosses when necessary) is h(\frac{1}{2} −P (y_{t}|y^{t−1})). The 0-1 loss of the omniscient scientist at time t is h(\frac{1}{2} − P (y_{t}|θ^{∗})). Thus the difference in these losses is

L_{t,0−1}^{Δ}(y^{n}) ≐ h(\frac{1}{2} − P (y_{t}|y^{t−1})) − h(\frac{1}{2} − P (y_{t}|θ^{∗})). (44)

In analogy with the function K_{λ}, let us define J_{λ}(x) = (1 − 2λ)h(x − \frac{1}{2}). We can then express the difference between the risk of Bayes method and the risk of the omniscient scientist under the 0-1 loss as follows.

r_{0−1}^{Δ}(θ^{∗}) = ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗}) ∑_{t=1}^{n} L_{t,0−1}^{Δ}(y^{n})

= ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗}) ∑_{t=1}^{n}[h(\frac{1}{2} − P (y_{t}|y^{t−1})) − h(\frac{1}{2} − P (y_{t}|θ^{∗}))]

= ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗}) ∑_{t=1}^{n} ∑_{y∈Y} P (Y_{t} = y|θ^{∗})
[h(\frac{1}{2} − P (Y_{t} = y|y^{t−1})) − h(\frac{1}{2} − P (Y_{t} = y|θ^{∗}))]
= ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗}) ∑_{t=1}^{n}
[λ(h(\frac{1}{2} − p_{t}) − h(\frac{1}{2} − λ)) + (1 − λ)(h(p_{t} − \frac{1}{2}) − h(λ − \frac{1}{2}))]
≤ ∑_{y^{n}∈Y^{n}} P (y^{n}|θ^{∗}) ∑_{t=1}^{n} J_{λ}(p_{t}),

(45)

where p_{t} = P (Y_{t} = −f_{θ^{∗}}(x_{t})|y^{t−1}) as above. The last inequality is readily verified by case analysis.

Note that K_{λ} increases monotonically as x goes from λ to 1 − λ, and J_{λ}(x) is a step function that is 0 for x < 1/2 and 1 − 2λ for x > 1/2. Hence it is clear that

J_{λ}(x) ≤ \frac{1 − 2λ}{K_{λ}(1/2)}K_{λ}(x) = \frac{C_{λ}}{1 − 2λ}K_{λ}(x) (46)

for all λ ≤ x ≤ 1 − λ, where

C_{λ} = \frac{(1 − 2λ)^{2}}{λ log(2λ) + (1 − λ) log(2(1 − λ))}.

It can be shown that if log is the natural log, then \frac{1}{log 2} ≤ C_{λ} ≤ 2 for 0 ≤ λ ≤ 1/2. The lower bound is tight as λ → 0, and the upper bound is tight as λ → 1/2.

Hence it follows from (43), (45) and (46) that

r_{0−1}^{Δ}(θ^{∗}) ≤ \frac{C_{λ}}{1 − 2λ}r_{ln}^{Δ}(θ^{∗}), (47)

where \frac{1}{ln 2} ≤ C_{λ} ≤ 2.

4.3 Bayes Risk for 0-1 Loss

In this final section we look at the 0-1 Bayes risk, that is, the risk of Bayes procedure for 0-1 loss under the assumption that the outcome sequence y^{n} is /generated by choosing θ^{∗} according to the prior distribution and then generating y^{n} according to P_{θ}^{∗}. As above, we compare the risk of the Bayes method to the risk of an omniscient scientist who knows θ^{∗}. Again, we can simply average the results of the previous section to obtain bounds on the excess risk of the Bayes method. However, a direct analysis yields a bound that is better by a factor of 2. As above we consider only the case of {±1}-valued functions times independent sign noise with rate λ. Our analysis is similar to that given in [17] for the noise-free case, and generalizes the corresponding results given there. It also parallels the analysis of the previous section.

The Bayes risk for the log loss is

R_{log}(P) = ∑_{y^{n}∈Y^{n}} P (y^{n}) ∑_{t=1}^{n} log \frac{1}{P (y_{t}|y^{t−1})}

= ∑_{y^{n}∈Y^{n}} P (y^{n}) ∑_{t=1}^{n} ∑_{y∈Y} P (Y_{t} = y|y^{t−1}) log \frac{1}{P (Y_{t} = y|y^{t−1})}

(48)  = ∑_{y^{n}∈Y^{n}} P (y^{n}) ∑_{t=1}^{n} H(Y_{t}|y^{t−1}).

The corresponding risk for the omniscient scientist under the log loss is h_{λ}n, where h_{λ} = λ log \frac{1}{λ} + (1 − λ) log \frac{1}{1−λ}, since the omniscient scientist knows everything except which values are changed by the noise. Hence

R_{log}^{Δ}(P) = ∑_{y^{n}∈Y^{n}} P (y^{n}) ∑_{t=1}^{n}[H(Y_{t}|y^{t−1}) − h_{λ}]. (49)

Now turning to the 0-1 loss, the Bayes risk is

R_{0−1}(P) = ∑_{y^{n}∈Y^{n}} P (y^{n}) ∑_{t=1}^{n} h(\frac{1}{2} − P (y_{t}|y^{t−1}))

= ∑_{y^{n}∈Y^{n}} P (y^{n}) ∑_{t=1}^{n} ∑_{y∈Y} P (Y_{t} = y|y^{t−1})h(\frac{1}{2} − P (Y_{t} = y|y^{t−1}))

(50)  = ∑_{y^{n}∈Y^{n}} P (y^{n}) ∑_{t=1}^{n} H̃(Y_{t}|y^{t−1}),

where H̃(Y_{t}|y^{t−1}) = min(P (Y_{t} = +1|y^{t−1}), P (Y_{t} = −1|y^{t−1})).

The corresponding risk for the omniscient scientist under the 0-1 loss is λn. Hence

R_{0−1}^{Δ}(P) = ∑_{y^{n}∈Y^{n}} P (y^{n}) ∑_{t=1}^{n}[H̃(Y_{t}|y^{t−1}) − λ]. (51)

Both H(Y_{t}|y^{t−1}) − h_{λ} and H̃(Y_{t}|y^{t−1}) − λ are functions of x = P (Y_{t} = +1|y^{t−1}) that are symmetric about x = 1/2, equal 0 for x = λ and x = 1−λ, increasing as x goes from λ to 1/2 and (by symmetry) decreasing as x goes from 1/2 to 1 − λ. In fact, H̃(x) − λ is linear for λ ≤ x ≤ 1/2 and H(x) − h_{λ} is concave. It follows that H̃(x) − λ ≤ \frac{H̃(1/2)−λ}{H(1/2)−h_{λ}} (H(x) − h_{λ}) for all λ ≤ x ≤ 1 − λ, using symmetry again to verify the inequality for the second half of the range. Furthermore,

\frac{H̃(1/2) − λ}{H(1/2) − h_{λ}} = \frac{\frac{1}{2}(1 − 2λ)}{λ log(2λ) + (1 − λ) log(2(1 − λ))} = \frac{C_{λ}}{2(1 − 2λ)},

where C_{λ} is as defined in the previous section, and we assume natural logs. Since x always lies between λ and 1 − λ when x = P (Y_{t} = +1|y^{t−1}), it follows from (49) and (51) that

R_{0−1}^{Δ}(P) ≤ \frac{C_{λ}}{2(1 − 2λ)}R_{ln}^{Δ}(P), (52)

where \frac{1}{ln 2} ≤ C_{λ} ≤ 2.

For λ = 0, C_{λ} = \frac{1}{ln 2} and from (52) we get R_{0−1}^{Δ}(P) ≤ \frac{1}{2 ln 2}R_{ln}^{Δ}(P) = \frac{1}{2}R_{log_{2}}^{Δ}(P), which was the result from [17]. As λ approaches 1/2, C_{λ} approaches 2, and we get R_{0−1}^{Δ}(P) ≤ \frac{1}{1−2λ}R_{ln}^{Δ}(P). Combining this with (31) from section 3.4.2, if the class of functions has VC dimension d then this gives

R_{0−1}^{Δ}(P) ≤ \frac{d}{1 − 2λ} ln \frac{en}{d}.

Hence

R_{0−1}(P) ≤ λn + \frac{d}{1 − 2λ} ln \frac{en}{d}. (53)

This holds for any class F of VC dimension d, any sample size n ≥ d, and any prior P.

5 Conclusion

We have derived a number of upper bounds on the risk of Bayes method for sequential classification and regression problems on the outcome space Y = {±1}. Many of our techniques should generalize easily to other kinds of outcome spaces, as well as other decision spaces and loss functions. Some of these techniques may also help in analyzing other learning methods, such as the “Gibbs” method [14, 17, 23, 22, 27]. However, a major problem remaining is to develop equally simple and general techniques to obtain lower bounds on the risk, so that we can see how tight these upper bounds are.

Very tight upper and lower bounds on the risk of Bayes methods under log loss are available for the case when Θ is a compact subset of R^{d} and the relative entropy I(P_{θ} ∥ P_{θ^{∗}}) is twice continuously differentiable at θ = θ^{∗} for almost all θ^{∗} ∈ Θ, so that the Fisher information is well-defined [26, 13, 24, 7, 9, 33, 34]. This is very often not the case for a discrete outcome space such as {±1}, so we have concentrated on more general bounds here, which involve much weaker assumptions, such as finiteness of the VC dimension or bounds on the VC entropy. It remains to see exactly how the results given here relate to the more standard statistical approaches using Fisher information.

It should also be noted that whereas the bounds obtained for the log loss are quite general, those we have obtained for the 0-1 loss are restricted to the case of noisy functions with known noise rate. It would be nice to have more general bounds for 0-1 loss. There are also many cases of interest in which the class of functions indexed by Θ can be decomposed into classes F_{1}, F_{2}, … of increasing VC dimension [28], including the case where Θ consists of a sequence of smooth real parameterizations as above of increasing dimension [34]. Some general results on the performance of Bayes methods in this case for noise-free outcomes are reported in [16]. These results should be (and can be) extended to the noisy case.

Finally, it would be nice to have good bounds on the average loss for the nth example, in addition to bounds on the average total loss for the first n examples. Yamanishi gives bounds of this type for some special cases [33, 34] (see also [1, 2]). The former quantity is what is usually displayed as a “learning curve”. Of course, if we had matching upper and lower bounds on the average total loss for the first n examples for each n, then we could obtain a learning curve by simply subtracting the average loss on the first n − 1 examples from the average loss on the first n. When the average loss grows logarithmically, as it appears to in many of the cases we study here (after subtracting off the loss of the omniscient scientist), and as it provably does in some other cases, then this gives a learning curve of the form c/n for some constant c that we can estimate. However, this subtraction is not valid without extremely tight upper and lower bounds on the average total loss. Thus our current results are merely suggestive regarding the shape of the learning curve for Bayes method.

Acknowledgments

The first author would like to acknowledge the many insights gained from numerous discussions with Michael Kearns and Manfred Opper about the performance of Bayes methods, especially discussions with Michael Kearns about the noisy functions case, in which some interesting preliminary results were obtained, and discussions with Manfred Opper about the critical role played by the scaling behavior of the prior probability of a neighborhood around θ^{∗} as a function of its radius. Discussions with Nick Littlestone about concepts related to that of the omniscient scientist were also very helpful. In many ways these discussions, along with our previous collaborative work, laid the foundation for this paper. He would also like to thank David Helmbold, Phil Long and Anselm Blumer for helpful conversations/comments. Both authors would like to acknowledge helpful discussions with Bin Yu, and, indirectly through Bin, with L. LeCam.

References

[1] S. Amari, A universal theorem on learning curves. Unpublished manuscript, 1992.

[2] S. Amari, N. Fujita and S. Shinomoto, Four types of learning curves, Neural Computation, 4 (1992), pp. 605–619.

[3] M. Feder, N. Merhav and M. Gutman, Universal prediction of individual sequences, IEEE Trans. Info. Th., 38 (1992), pp. 1258–1270.

[4] Meir Feder and Neri Merhav, Relations between entropy and error probability, unpublished manuscript, 1992.

[5] A. Barron, Are Bayes rules consistent in information?, in Open Problems in Communication and Computation, T. M. Cover and B. Gopinath, eds., 1987, ch. 3.20, pp. 85–91.

[6] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the Association for Computing Machinery, 36 (1989), pp. 929–965.

[7] B. Clarke and A. Barron, Information-theoretic asymptotics of Bayes methods, IEEE Transactions on Information Theory, 36 (1990), pp. 453–471.

[8] T. Cover and J. Thomas, Elements of Information Theory, Wiley, New York, 1991.

[9] A. Dawid, Prequential analysis, stochastic complexity and Bayesian inference, Bayesian Statistics 4. To appear.

[10] , Prequential data analysis, Current Issues in Statistical Inference. To appear.

[11] , Statistical theory: The prequential approach, J. Roy. Statist. Soc. A, (1984), pp. 278–292.

[12] A. DeSantis, G. Markowski, and M. N. Wegman, Learning probabilistic prediction functions, in Proceedings of the 1988 Workshop on Computational Learning Theory, Morgan Kaufmann, 1988, pp. 312–328.

[13] S. Y. Efroimovich, Information contained in a sequence of observations, Problems in Information Transmission, 15 (1979), pp. 178–189.

[14] G. Gyorgyi and N. Tishby, Statistical theory of learning a rule, in Neural Networks and Spin Glasses, K. Thuemann and R. Koeberle, eds., World Scientific, 1990.

[15] D. Haussler, M. Kearns, N. Littlestone, and M. K. Warmuth, Equivalence of models for polynomial learnability, Information and Computation, 95 (1991), pp. 129–161.

[16] D. Haussler, M. Kearns, and R. Schapire, Bounds on the sample complexity of Bayesian learning using information theory and the VC dimension, Machine Learning. To appear.

[17] , Bounds on the sample complexity of Bayesian learning using information theory and the VC dimension, in Proceedings of the Fourth Workshop on Computational Learning Theory, 1991, pp. 61–74.

[18] D. Haussler, N. Littlestone, and M. Warmuth, Predicting {0, 1}-functions on randomly drawn points, Tech. Rep. UCSC-CRL-90-54, University of California, Santa Cruz, Computer Research Laboratory, Dec. 1990. To appear in Information and Computation.

[19] N. Littlestone, Mistake Bounds and Logarithmic Linear-threshold Learning Algorithms, PhD thesis, University of California Santa Cruz, 1989.

[20] N. Littlestone and M. K. Warmuth, The weighted majority algorithm, in 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 256– 261.

[21] N. Merhav and M. Feder, Universal sequential learning and decision from individual data sequences, The 1992 Workshop on Computational Learning Theory (1992).

[22] M. Opper and D. Haussler, Calculation of the learning curve of Bayes optimal classification algorithm for learning a perceptron with noise, in Computational Learning Theory: Proceedings of the Fourth Annual Workshop, Morgan Kaufmann, 1991, pp. 75–87.

[23] , Generalization performance of Bayes optimal classification algorithm for learning a perceptron, Physical Review Letters, 66 (1991), pp. 2677–2680.

[24] J. Rissanen, Stochastic complexity and modeling, The Annals of Statistics, 14 (1986), pp. 1080–1100.

[25] N. Sauer, On the density of families of sets, Journal of Combinatorial Theory (Series A), 13 (1972), pp. 145–147.

[26] G. Schwarz, Estimating the dimension of a model, The Annals of Statistics, 6 (1978), pp. 461–464.

[27] H. Seung, H. Sompolinsky, and N. Tishby, Statistical mechanics of learning from examples, Physical Review A, 45 (April 15, 1992), pp. 6056–6091.

[28] V. N. Vapnik, Estimation of Dependences Based on Empirical Data, Springer-Verlag, New York, 1982.

[29] V. N. Vapnik and A. Y. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Theory of Probability and its Applications, 16 (1971), pp. 264–280.

[30] V. Vovk, Aggregating strategies, in Proceedings of the Third Annual Workshop on Computational Learning Theory, Morgan Kaufmann, 1990, pp. 371–383.

[31] V. G. Vovk, Prequential probability theory. unpublished manuscript, 1990.

[32] , Universal forcasting algorithms, Information and Computation, 96 (Feb. 1992), pp. 245–277.

[33] K. Yamanishi, A loss bound model for on-line stochastic prediction strategies, in Proceedings of the 1991 Workshop on Computational Learning Theory, L. G. Valiant and M. Warmuth, eds., 1991, Morgan Kaufmann, San Mateo, CA, pp. 290–302.

[34] , A Statistical Approach to Computational Learning Theory, PhD thesis, University of Tokyo, March 1992.

How Well Do Bayes Methods Work? 101

[35] B. Yu, On optimal rate universal d-semifaithful coding, IEEE Transactions on Information Theory. To appear.