Quantitatively Tight Sample Complexity Bounds John Langford

I present many new results on sample complexity bounds (bounds on the future error rate of learning algorithms). Of theoretical interest are qualitative and quantitative improvements in sample complexity bounds as well as some techniques and criteria for judging the tightness of sample complexity bounds.

On the practical side, I show quantitatively interesting results applying these sample complexity bounds to real world problems and present a technique for using both sample complexity bounds and (more traditional) holdout techniques. Code for calculating these bounds is provided.

Contents

3 4 CONTENTS

Part 1

Introductory Learning Theory

CHAPTER 1 Introduction

What is a sample complexity bound? Informally, it is a bound on the number of examples required to learn a function. Therefore, in order to motivate the use of a sample complexity bound, we must first motivate the learning problem.

1.1. The learning problem

What is learning? Learning is the process of discovering relationships between events. Knowledge of the relationships between events is of great importance in coping with the environment. Naturally, humans are incredibly good at the process of learning—so good that we sometimes do not even realize when it is hard.

The learning problem which we focus on is learning for computers. In particular, “How can a computer learn?” A few examples are illustrative:

(1) How can we make a computer with a microphone output a text version of what is being spoken?

(2) How can we make a computer with a camera recognize John?

(3) How can we make a computer controlling a robot arrive at some location?

1.2. The problem with the learning problem

The learning problem, as stated, is somewhat ill-posed. There are some very obvious ways for a computer to learn—for example by memorization. The difficulty arises when memorization is too expensive. Essentially, the real learning problem becomes, “Given incomplete information, how can a computer learn?” This formulation of the learning problem gives rise to a new problem - quantifying the amount of information required to learn. Sample complexity bounds address this second question: “When can a computer learn?”

In some cases learning is essentially hopeless. There are two notions of “hopeless”: information theoretic and computational. Information theoretic difficulties arise when it is simply not possible to predict the output given the input. For example, predicting when a radioactive nucleus will decay is always difficult no matter what observations are made according to current physics theory. Even when simple relations exist between inputs and outputs exist the computation required to discover the simple relation can be formidable. A fine example of this is provided by cryptography where a common task is to work out functions for which it is not feasible to predict the input given the output.

1.3. A plethora of learning models

There are several possible learning models which can be divided along several axes. Our first axis is the type of information given to the learning algorithm. There are several possibilities:

(1) Labeled Examples: Vectors of observations.

(2) Partial relations: partial relations between events such as might be provided by experts. This could include constraints or partial functions.

We will assume that just examples are available as a lowest common denominator amongst learning problems. It is worth noting that this does not preclude the use of other forms of information which could be much more powerful then mere examples.

Another important axis is the level of helpfulness in the world. Is the world making it hard to learn? Is the world making it easy to learn? Or is the world oblivious?

(1) Teacher: The teacher model is a “best case” model. Here, we assume that the world is providing the best examples possible in order to learn a relationship.

(2) Oblivious: The oblivious model is an “in between” model where we assume that the world doesn’t care whether or not we learn. Examples are picked in some unspecified manner and our goal is to do an ’average case’ analysis.

(3) Opponent: The opponent model is a “worst case” model. Here, we assume that world is choosing examples in way which minimize our chance of learning.

Clearly, the strongest form of learning is learning in the opponent model, because if something is learnable in the opponent model, then it is learnable in the oblivious model. The same relationship also holds for oblivious and teacher models. We will work in an oblivious model where examples are chosen by uncaring nature. Why the oblivious model? Aside from the intractability of analysis in an opponent model, we expect that most learning problems actually are oblivious: we have neither an active teacher nor an active opponent. Thus an analysis in the oblivious model will be directly applicable to many learning problems.

We have committed to an oblivious model with examples as our source of information. With these two questions decided all the remaining questions will essentially be decided in favor of simplicity. There are two more very important questions to decide. The first is: does our algorithm get to pick the examples or are the examples picked for us?

(1) Active learning: The learning algorithm chooses a partial example and the remainder is filled in by nature.

(2) Inactive learning: The learning algorithm is simply given examples.

Active learning (aka experimental science) is inherently more powerful then inactive learning. Despite this, we will choose to work with an inactive learning model, because analyzing the active learning setting in a generic manner appears very difficult. In addition, opportunities for inactive learning are typically more common than opportunities for active learning because inactive learning only requires observation while active learning requires experimentation.

Our plan is to focus on an oblivious model with examples chosen by the world. The remaining question is: Do we know which relation we want to learn? The two possibilities are:

(1) Supervised learning: We want to learn to model an output in terms of an input.

(2) Unsupervised learning: We want to learn to model an arbitrary subset of observations in terms of other observations.

Again, we will choose the simple thing: supervised learning.

The question we want to answer then is, “When is supervised learning in an oblivious model with examples chosen by the world feasible?”.

1.4. The oblivious inactive supervised learning model

Oblivious will be modeled by an unknown distribution D over examples. The fundamental assumption we will make in all of our sample complexity bounds is that all examples are drawn independently from the unknown distribution D. This assumption must be stated explicitly and always kept in mind when considering the relevance of sample complexity bounds.

Axiom 1.4.1. All examples are drawn independently from an unknown distribution D.

With the exception of this assumption, all of the other parameters in our bounds will be verifiable at the time the bound is applied.

Since this is a supervised learning model, all of our examples will split into two parts, (x, y) where x is the “input” and y is the “output” (the thing we wish to predict). For simplicity, we will typically work with theorems for binary valued y. This choice is not critical to the idea of a sample complexity bound—it is just made for simplicity of presentation.

The number of samples, m, required for learning is the fundamental quantity we will be concerned with. In particular, we will not be concerned with the time complexity or the space complexity of learning algorithms. This choice is made for the purposes of simplicity and implies that the relationship between sample complexity bounds and learning algorithms will be similar to the difference between information theory and coding information for transmission across a noisy channel.

Any learning algorithm must output some hypothesis, h, for predicting the output given the input. This hypothesis is essentially a program which, given the input, predicts the output. The hypothesis may or may not be randomized.

The next item to quantify is learning. When has learning occurred? We will say that learning has occurred when the true error is less than a random hypothesis would give us. The true error e_{D}(h) is defined in the following way:

e_{D}(h) = Pr_{D}(h(x) ≠ y)

Unfortunately, the true error is not an observable quantity in our model because the distribution, D, is unknown. However, there is a related quantity which is observable. Given a sample set S, the empirical error, ê_{S}(h) is defined similarly as:

ê_{S}(h) = Pr_{S}(h(x) ≠ y) = \frac{1}{m} ∑_{i=1}^{m} I(h(x_{i}) ≠ y_{i})

where I() is a function which maps “true” to 1 and “false” to 0. Here Pr_{S}(...) is a probability taken with respect to the uniform distribution over the set of examples, S.

1.5. Questions we can answer

Our real goal in learning theory is to answer the question “When can we learn?” Unfortunately, there is no good answer to this question in the model we have chosen and, in particular, it may be impossible to learn. The simplest example of such a learning problem is the case of a distribution D which always flips a coin in deciding the value of the output y. The bias of the coin is the same irrespective of the input x. Since the value of the input is explicitly independent of the output we surely can not hope to learn a useful relation between the input and output.

We will instead focus on a different question: “Have we learned?” This question is answerable in a probabilistic manner. In particular we can make a statement such as “With high probability over samples drawn from D we have learned if the empirical error is less then some value.” In practice, we will want to know how much we have learned which we can do by providing a high confidence bound on the true error rate of the learned hypothesis.

The question answered here differs significantly from the learning theory results of Vapnik [28], Valiant [?] and many others which address the question “When is learning possible?” We instead address “Have we learned?” The second question appears to be more mathematically elegant to answer. It is unnecessary to make assumption about the learning algorithm. Our results will apply to all possible learning algorithms and thus are more similar to information theory than complexity theory.

1.6. Overview of the document

This document is primarily about the theory of sample complexity for answering the question “Have we learned?”. However, we do not neglect the experimental side. In particular, following the theory we will present results for application of sample complexity bounds to machine learning problems. These results are the ’best known results’ in terms of bound tightness and should be considered as a guide and challenge to others working on sample complexity bounds.

All of the sample complexity bounds presented here will fall within the paradigm of classical (non-Bayesian) statistics. This is not meant to scare away Bayesians or Bayesian analysis. In particular, it’s worth noting that we will consider the use of a ’prior’ and a ’posterior’ (in a classical manner) within these bounds.

In order to make this thesis more coherent, previous work (of which there is quite a bit) will be integrated into the presentation rather then separated into a section of it’s own. Credit will be given at the time the work is introduced.

The document is organized into 3 parts:

(1) Introductory material.

(2) New results on Sample Complexity.

(3) Experimental results of applying Sample Complexity. What follows is a brief chapter-by-chapter summary of the theoretical results in this thesis. Much of the work can be summarized as approaches which use extra information (in the algorithm, in error rates of hypotheses which are not chosen, in test sets, etc...) in order to construct tighter bounds on the future error rate of a hypothesis.

1.6.1. Microchoice Bounds. The Microchoice technique allows for online construction of a “prior” which can be used in the Occam’s Razor bound (3.5.1).

Empirical testing (presented in chapter 11) shows that this approach is practical and yields useful results on decision trees for real-world problems drawn from the UCI database of problems. The Adaptive Microchoice bounds further extend this approach and can result in functional improvements over the Occam’s Razor bound.

1.6.2. Pac-Bayes Bounds. Pac-Bayes bounds are a new approach (first presented by David McAllester [20]) for for dealing with continuously parameterized classifiers such as (stochastic) neural networks. This chapter refines and improves the PAC-Bayes bound giving it an information theoretic interpretation. Empirical results (presented in chapter 12) show that refined PAC-Bayes bound works to produce nonvacuous bounds on realistic learning problems. Nonvacuous bounds for continuous-valued classifiers are extremely rare so these results are quite exciting.

1.6.3. Averaging Bounds. Averaging bounds deal with classifiers formed by picking according to the weighted majority on some other set of classifiers. Averaging is a very common technique in practice, so results specialized for averaging classifiers are reasonably interesting. This chapters states and proves a bound on averaging classifiers which shows that “hypothesis space complexity” decreases as averaging becomes more uniform. Prior work mostly was of the form “averaging does not hurt much”.

1.6.4. Shell Bounds. Shell bounds are a new approach which trades extra information for tighter bounds. Empirical results in (presented in chapter 11) show this can be a useful approach. In order to ameliorate the increased information requirements, a sampled version of the bound is stated which allows for smooth interpolation between simpler bounds and the full shell bound. In addition, the shell bound has been extended to continuous spaces with an approach similar to PAC-Bayes bounds.

1.6.5. Bracketing Covering Number Bounds. The results of this chapter are entirely theoretical. They point out an approach which may lead to useful technique for bounds on continuous valued hypothesis spaces. Using a stronger notion of cover (the bracketing cover), simplified bounds on the future error rate of continuous classifiers can be constructed. This approach can be significantly tighter than the standard covering number approach. More work in calculation of bracketing covers is needed before these results can be applied.

1.6.6. Progressive Validation. Progressive Validation is a variant of the holdout bound (??) which is roughly twice as efficient about how it uses examples. Progressive Validation is not used in the experimental results chapter(s) because more work is required in order to prove the bound in a nonagnostic setting.

1.6.7. Combining training and test sets. The idea behind this chapter is that it should be possible to combine any test set bound with any training set based bound in order to derive a bound with more robust behavior. A general technique is stated and proved to work. Empirical results (in chapter 11) show that this approach can work well in practice.

CHAPTER 2 Basic Observations

Let X be the space of the input to a predictor and Y be the space of the output. A labeled example (x, y) consists of an input, x and the desired output, y. Our formal model starts with the assumption that all labeled examples are drawn independenty from a distribution D over the space X × Y. This is strictly more general than the ’target concept’ model which assumes that there exists some function f : X → Y used to generate the label. In particular we can model probabilistic learning problems which do not have a particular Y value for each X value. This generalization is essentially “free” in the sense that it does not add to the complexity of presenting the results.

The set of m independently drawn samples presented to a learning algorithm will be denoted as S. The learning algorithm will output a hypothesis h : X → Y which which has some unobservable true error rate e_{D}(h) and an observable empirical error rate, ê_{S}(h).

Definition 2.0.1. (True error) The true error e_{D}(h) is defined in the following way:

e_{D}(h) = Pr_{D}(h(x) ≠ y)

Unfortunately, the true error is not an observable quantity in our model because the distribution, D, is unknown. However, there is a related quantity which is observable.

Definition 2.0.2. (Empirical Error) Given a sample set S, the empirical error, ê_{S}(h) is defined as:

ê_{S}(h) = Pr_{S}(h(x) ≠ y) = \frac{1}{m} ∑_{i=1}^{m} I(h(x_{i}) ≠ y_{i})

where I() is a function which maps “true” to 1 and “false” to 0. Here Pr_{S}(...) is a probability taken with respect to the uniform distribution over the set of examples, S.

The principle observable quantity is the empirical error rate (ê_{S}(h)) of a hypothesis. What is the distribution of the empirical error rate for a fixed hypothesis? For each example, we know that the probability that the hypothesis will err is given by true error rate, e_{D}(h). This can be modeled by a biased coin flip: heads if you are wrong and tails if you are right.

Let us call the bias of the coin p = e_{D}(h). What then is the probability of observing k heads out of m coin flips? This is a very familiar distribution in statistics called the Binomial distribution. Let p̂ be the observed rate of heads.

Definition 2.0.3. (Binomial Distribution) The Binomial distribution is given by:

Pr_{\{0,1\}^{m}} (p̂ = \frac{k}{m}|p) = \binom{m}{k}p^{k}(1 − p)^{m−k}

Here we use ’choose’ notation defined by \binom{m}{k} = \frac{m!}{(m−k)!k!}.

2.1. The Basic Building Block

Our real interest will be captured by Binomial tails because we wish to bound the probability of observing a misleadingly small event. The probability of a Binomial tail is just the cumulative distribution function:

Definition 2.1.1. (Binomial Tail)

Bin(m, k, p) ≡ Pr_{\{0,1\}^{m}} (p̂ ≤ \frac{k}{m}|p) = ∑_{j=1}^{k} \binom{m}{j}p^{j}(1 − p)^{m−j}

2.2. Binomial Tail calculation techniques

One fundamental question arises: How quickly can we calculate the binomial coefficient, \binom{m}{k}? This question is important to answer because we will apply the bounds derived later to real problems, and this application will require calculation of Binomial coefficients and Binomial tails.

The answer is: not very fast. It is an open problem to calculate \binom{m}{k} in time not exponential in log m and log k (the representation length of m and k). In general, this problem is intractable. For example, we note that

\binom{m}{\frac{m}{2}} ≃ \frac{2^{m}}{\sqrt{m}}

which has an asymptotic representation length of O(m).

Our real goal is not merely calculating binomial coefficients but rather calculating the probability of a tail, Bin(m, k, p). How can we calculate the tail probability quickly? For all approaches, it is necessary to calculate log Bin(m, k, p) rather then Bin(m, k, p) to avoid underflow issues.

There are several possible approaches of increasing sophistication:

(1) Calculate log \binom{m}{i} independently from i = 0 to i = k and use the results in the sum, log ∑_{i=0}^{k} \binom{m}{i}p^{i}(1 − p)^{m−i}

(2) Calculate Pascal’s triangle and extract the Binomial coefficients.

(3) Use the fact that

\binom{m}{i + 1} = \frac{m!}{(m − i − 1)!(i + 1)!}

= \frac{m − i}{i + 1} \frac{m!}{(m − i)!i!} = \frac{m − i}{i + 1} ( \begin{matrix}m \\ i \end{matrix} )

and

\binom{m}{i − 1} = \frac{m!}{(m − i + 1)!(i − 1)!}

= \frac{i}{m − i + 1} \frac{m!}{(m − i)!i!} = \frac{i}{m − i + 1} ( \begin{matrix}m \\ i \end{matrix} )

to calculate each of the coefficients in sequence.

(4) Calculate \binom{m}{k} directly and then \binom{m}{i−1} given \binom{m}{i} until the added quantity

falls below the machine precision.

Approaches (1) and (2) both require O(m^{2}) work while approaches (3) and (4) require merely O(m) work. We will use approach (4) here. Yet, as noted in the beginning of this section, O(m) is still too expensive for us. Luckily, there exist some quick approximations which can reduce the computation to constant time (or O(log m) time depending on your computational model).

2.3. Approximation techniques

Exact calculation of Bin(m, k, p) can require computation at least proportional to m, which is often too expensive. In practice we will only need to calculate an upper bound on the quantity Bin(m, k, p). There are several inequalities which are often used. The first of these is the Hoeffding inequality. Assume that \frac{k}{m} < p then we have:

Bin(m, k, p) ≤ e^{−2m(p− \frac{k}{m})^{2}}

Intuitively, this inequality can be seen as fitting a gaussian to the Binomial distribution with p = \frac{1}{2}. For any particular m, the variance of the Binomial distribution is maximized when p = \frac{1}{2}. Therefore, the Hoeffding inequality is relatively tight when p = \frac{1}{2}. Unfortunately, the Hoeffding approximation is not tight enough for our purposes. In machine learning, our goal is to find a hypothesis with a true error rate far away from \frac{1}{2} where the Hoeffding inequality becomes loose.

There is another bound known as the “realizable bound” which applies only when the k = 0. The realizable bound is:

Bin(m, 0, p) = (1 − p)^{m} ≤ e^{−mp}

The realizable bound is noticeably tighter with an exponent proportional to |p − \frac{k}{m} | rather then (p − \frac{k}{m})^{2}. The disadvantage of the realizable bound is that it only applies to a very limited setting - when our empirical error rate happens to be 0.

Luckily, there exists a quickly calculable bound which achieves the generality of the Hoeffding bound along with the tightness of the realizable bound. We have the relative entropy Chernoff bound for \frac{k}{m} < p:

(2.3.1)  Bin(m, k, p) ≤ e^{−mKL(\frac{k}{m} ||p)}

Here KL(q||p) = q ln \frac{q}{p} + (1 − q) ln \frac{(1−q)}{(1−p)} is the KL-divergence between a coin of bias q and another coin of bias p. The relative Chernoff bound is as tight as the Hoeffding bound when p is near \frac{1}{2} and as tight as the realizable bound when k = 0.

We are concerned with the different bounds here because much of the learning theory literature works with either the realizable bound or the Hoeffding bound, or both. In contrast, we will work with either the relative Chernoff bound or the exact tail probability, Bin(m, k, p). There are several advantages to this approach:

(1) Sometimes, a different approach to producing a bound will appear better then previous approaches, but the apparent benefit can simply be traced to the use of a tighter bound on Bin(m, k, p).

(2) The bounds presented here will all be immediately applicable to direct calculation.

Figure 2.4.1. A plot of the difference between the true error upper bound and the empirical error for various Binomial tail bound approximations. The relative entropy approximation to the Binomial tail is relatively well behaved while the Hoeffding approximation is not. In particular, the Hoeffding approximation does not take into account the decreased variance of low bias Binomials.

(3) We avoid the need to state two versions of the same theorem: once for the realizable (0 empirical error) case and once for the agnostic (arbitrary empirical error) case.

The principle disadvantage of this approach is that both the relative entropy Chernoff bound and Bin(m, k, p) are not analytically invertible. In particular, we can not discover max_{p}{p : Bin(m, k, p) = δ} via an analytic calculation. This is not a severe computational disadvantage because the quantity Bin(m, k, p) is convex in p implying that a binary search is capable of solving the inequality. The process of (and need for) inversion is discussed next.

2.4. Converting to a P-value approach

When making judgments about which hypothesis to choose, the relevant quantity is not the probability of error as we calculate above. Instead, it is a bound on the true error rate which holds with high probability over draws of the sample set. We might decide that δ = 0.05 was an acceptable rate of bound failure and then ask ourselves, “What is a bound on the true error rate that holds with probability 0.9?”

Functionally, instead of calculating:

Bin(m, k, p) = δ

we want to invert the output, δ, with respect to the input, p. Since p and δ are monotonically related to each other, this inversion can be defined as:

ē(m, k, δ) ≡ max_{p} {p : Bin(m, k, p) = δ}

What is the interpretation of ē? The inversion ē(m, k, δ) is a high confidence bound on the true error rate. With probability at least 1 − δ (over the draws of the examples), the true error rate will be less then ē(m, k, δ). This is exactly the kind of quantity that we desire in making decisions about which hypothesis is more desirable. This calculation has been done for several values of m and Binomial tail bounds in figure (2.4).

We will use the process of inversion in many places. The fundamental soundness of inversion rests upon the following lemma.

Lemma 2.4.1. (Inversion Lemma) For all predicates, ϕ(X)

sup_{P} Pr_{X∼P}(ϕ_{P} (X)) ≤ δ ⇒ ∀P Pr_{X∼P}(ϕ_{P} (X)) ≤ δ

Proof. By contradiction. Assume there exists P such that the right hand side is not satisfied. Then, the left hand side can not be correct. □

2.5. Bounding the Union

One very common technique we will use is the union bound. Given two coins, each with a bias of p, what is the probability that if we flip each coin m times, one of the coins will have k or fewer heads?

Let X_{1} = the proportion of heads in the first coin flip and X_{2} = the proportion of heads in the second coin flip. Then we get:

Pr (X_{1} ≤ \frac{k}{m} or X_{2} ≤ \frac{k}{m})

≤ Pr (X_{1} ≤ \frac{k}{m}) + Pr (X_{2} ≤ \frac{k}{m})

where the inequality is known as the union bound. This step is very applicable because it works even when the values of X_{1} and X_{2} are correlated in arbitrary ways.

2.6. Arbitrary Loss functions

A loss function is any function which takes a hypothesis, h, and an example (x, y) as input then outputs a real number. In particular, we could choose l(h, (x, y)) = I(h(x) ≠ y) and regard most of the prior discussion as working with a specialized hamming loss function. Many other possibilities exist. For any bounded loss function, l(h, (x, y)) ∈ [0, 1], we can define:

e_{D}(h) = E_{D}l(h, (x, y))

and

ê_{S}(h) = E_{S}l(h, (x, y))

All of the bounds reported here will apply for general 0-1 bounded loss functions. The fundamental advantage that this gives us is the ability to treat the hypothesis not as a black box. Instead, we can derive a bound dependent on the structure of the hypothesis. This will be important later when discussing averaging bounds (theorem 6.1.1) where the bound will partly depend upon the structure of the hypothesis.

For clarity of presentation, the bounds will all be presented using the hamming loss. However, they will all apply to the more general setting of arbitrary 0 − 1 loss functions.

CHAPTER 3 Simple Sample Complexity bounds

The observations presented in this chapter are mostly “common knowledge”.

3.1. Simple Holdout

The simplest bound arises for the classical technique of splitting the data set into two pieces: a training set of size m_{train} and a test set of size m_{test}. In this setting, the following simple bound applies:

Theorem 3.1.1. (Holdout Sample Complexity) Let ê_{test}(h) be the empirical error on the test set and e_{D}(h) be the true error rate of the hypothesis, then we have:

∀h Pr_{D^{m}} ( e(h) ≥ ē(m, ê_{test}(h), δ)) ≤ δ

where ē(m, \frac{k}{m}, δ) ≡ max_{p}\{p : Bin(m, k, p) = δ\}

Proof. The proof is just a simple identification with the Binomial. For any distribution over (x, y) pairs and any hypothesis, h, there exists some probability, e_{D}(h), that the hypothesis predicts incorrectly. We can regard this event as a coin flip with bias e_{D}(h). Since each example is picked independently, the distribution of the empirical error rate will then be a Binomial distribution. Given that the distribution is Binomial we calculate an upper bound which holds with high probability. □

There are two immediate corollaries of the holdout theorem (??) which are mathematically simpler although not as tight. The first corollary applies to the limited “realizable” setting where you happen to observe 0 test errors.

Corollary 3.1.2. (Realizable Holdout Sample Complexity)

∀h Pr_{D}(ê_{test}(h) = 0|e_{D}(h) ≥ \frac{ln \frac{1}{δ}}{m_{test}} ) ≤ δ

Proof.

Bin(m_{test}, 0, ϵ) = (1 − ϵ)^{m_{test}} ≤ e^{−ϵm_{test}}

Setting this equal to δ and solving for ϵ gives us the result. □

A second corollary applies to all results, not just those where we observe 0 errors.

Corollary 3.1.3. (Agnostic Holdout Sample Complexity)

∀h Pr_{D}(e_{D}(h) − ê_{test}(h) ≥ \sqrt{\frac{ln \frac{1}{δ}}{2m_{test}}} ) ≤ δ

Proof. Use the Hoeffding approximation which for \frac{k}{m_{test}} < ϵ, says:

Bin(m_{test}, k, ϵ) ≤ e^{−2m_{test}(ϵ− \frac{k}{m_{test}} )^{2}}

Now, set this equal to δ, and solve for ϵ to get the result. □

Remark 3.1.4. Similar theorems apply to bound ê_{test}(h) − e_{D}(h).

How tight is the test sample complexity theorem? The answer is very tight. Let us define

ē(m, ê(h), δ) ≡ max_{p} p : Bin(m_{test}, m_{test}ê_{S}(h), p) ≥ δ

as our true error bound. We wish to know how much e_{D}(h) and ē(m_{test}, ê(h), δ) differ. Applying the Hoeffding approximation, we know that with high probability,

e_{D}(h) ≥ ē(m_{test}, ê(h), δ) − 2\sqrt{\frac{ln \frac{1}{δ}}{2m_{test}}} . Thus the region in which e_{D}(h) is confined

with high confidence is of size 2\sqrt{\frac{ln \frac{1}{δ}}{2m_{test}}} or smaller.

It is common practice in the field of machine learning to use the gaussian approximation in reporting error bars. The practice is reasonably safe because it is usually pessimistic. However, it can occasionally lead to embarrassing results where you report error rates such as 0.01 ± 0.02. The test sample complexity theorem is the “right” way to report error bars because it works with the actual distribution over errors.

Given that the bounds for the simple holdout technique are so tight, why do we need to engage in further work? There is one serious drawback to the holdout technique—application of the holdout technique requires m_{test} otherwise unused examples. This can strongly degrade the value of the learned hypothesis because an extra m_{test} examples for the training set could reduce the true error of the learned hypothesis from 0.5 to 0.0 on some learning problems. In particular, many learning algorithm implicitly assume that the training error “behaves like” the true error in choosing the hypothesis. With an inadequate number of training examples, there may be very little relationship between the behavior of the training error and the true error.

There are two basic approaches to this difficulty:

(1) Try to reduce m_{test} using more sophisticated holdout techniques.

(2) Don’t use a holdout set. Instead, train and test on the same set of exam-

ples using a more sophisticated bound.

Analyzing these techniques is significantly more complicated and so it is delayed for later chapters except for some thoughts on cross validation.

3.1.1. Cross Validation. One of the standard techniques for attempting to improve on the holdout bound is cross validation. K-fold cross validation divides the data into K folds of size \frac{m}{K} (assume m is divisible by K for simplicity). Then, for every fold i, holdout fold i, train on the remainder of the data and test on fold i. Let the hypotheses we found by training be known as h_{1}, ..., h_{K} and their respective holdout errors as ê_{1}, ..., ê_{K}. Also let ê_{cv} = \frac{1}{K} ∑_{i=1}^{K} ê_{i}.

There are several variations of cross validation. If K = m, the procedure is often called “leave one out cross validation”. In one variant, you train on all of the data to learn a new hypothesis, h, and assume a true error rate near ê_{CV}. In another variant, you predict according to h_{cv} = Uniform(h_{1}, ..., h_{K}). The latter variant is simpler to analyze because linearity of expectation implies that ê_{cv} is an unbiased estimate of ē_{cv}.

There are strong results known for cross validation on nearest-neighbor, kernel, and histogram classifiers [?]. In general, only very weak results are known about bounds on the variance of cross validation for general classifiers. The “general” results include “Sanity check bounds” [?] which state that cross validation is not much worse than a holdout set and some slightly stronger results [?] and [?].

Problem 3.1.5. (Open) Construct a tight bound the variance of cross validation for arbitrary classifiers.

3.2. The most basic result

The most basic of training set based sample complexity bounds is the simple combination of a Binomial tail bound and the union bound. In particular, we have:

Theorem 3.2.1. (Discrete Hypothesis Bound) For all hypothesis spaces, H, for all δ ∈ (0, 1]

Pr_{D^{m}} (∃h ∈ H : e(h) ≥ ē(m, ê(h), \frac{δ}{|H|})) ≤ δ

where ē(m, \frac{k}{m}, δ) ≡ max_{p}\{p : Bin(m, k, p) = δ\}

Note that this theorem can only be nonvacuous when the hypothesis space, H, has some finite (discrete) bound.

Proof. For every individual hypothesis, we know that:

Pr_{D^{m}}(e(h) ≥ ē(m, ê(h), δ)) ≤ δ

Applying the union bound for every hypothesis gives us the result. □

Intuitively, this theorem says that as the number of hypotheses grows, we can not guarantee as tight a uniform convergence.

A better understanding can be gained by considering some of the Binomial tail bound approximations. This is also worth mentioning in order to compare this theorem with theorems in more common forms.

Corollary 3.2.2. (Relative Entropy Discrete Hypothesis Bound) For all hypothesis spaces, H, for all δ ∈ (0, 1]:

Pr_{D^{m}} (∃h ∈ H : KL(ê(h)||e(h)) ≥ \frac{ln |H| + ln \frac{1}{δ}}{m} ) ≤ δ

Proof. Loosen (theorem 3.1.1) with the relative entropy Chernoff bound (Eqn. 2.3.1) and solve for the minimum. □

The form of this corollary allows us to make two more important observations:

(1) The “cost” of doubling the hypothesis space size is about one extra example. In other words, we can keep a constant bound on the probability of a large deviation with e^{m} hypotheses.

(2) The value of δ is not very important as m grows larger. We can further loosen the last corollary with Hoeffding approximation to get the following commonly stated bound:

Corollary 3.2.3. (Agnostic Discrete Hypothesis Bound) For all hypothesis spaces, H, for all δ > 0,

Pr_{D^{m}} (∃h ∈ H : e(h) ≥ ê(h) + \sqrt{\frac{ln |H| + ln \frac{1}{δ}}{2m}} ) ≤ δ

Proof. Loosen corollary (3.1.2) with the bound KL(q||p) ≤ 2(q − p)^{2}. □

The agnostic form of this bound has the advantage that it explicitly shows that we are forcing the convergence (in high probability) of the empirical error rate to the true error rate. Graphically, we are forcing every empirical error to be near to its true error. This is a picture which represents the connection

Later bounds will have more complicated convergence conditions with more complicated graphs.

3.3. Lower Bounds

There are two forms of lower bound. One is a lower bound on the true error rate for which essentially the same theorem applies with the bound reversed. This form of lower bound allow us to construct a two-sided confidence interval on the location of the true error rate. Typically, such lower bounds can be formed by simply changing the sign in upper bound arguments.

Theorem 3.3.1. (Discrete Hypothesis Lower Bound) For all hypothesis spaces, H, for all δ ∈ (0, 1]

Pr_{D^{m}} (∃h ∈ H : e(h) ≤ ē(m, ê(h), \frac{δ}{|H|})) ≤ δ

where ē(m, \frac{k}{m}, δ) ≡ min_{p}\{p : Bin(m, k, p) = δ\}

Proof. For every individual hypothesis, we know that:

Pr_{D^{m}}(e(h) ≤ ē(m, ê(h), δ)) ≤ δ

Applying the union bound for every hypothesis gives us the result. □

3.4. Lower Upper Bounds

The second form of lower bound is a lower bound on the upper bound (similar to the results of [?]). If we can lower bound the upper bound (as a function of its observables), then we can be confident that the upper bound is no looser than the gap between the lower upper bound and the upper bound.

How tight is the discrete hypothesis bound (3.1.1)? The answer is sometimes tight. In particular, we can exhibit a set of learning problem where the discrete hypotheses bound can not be made significantly lower as a function of the observables, m, δ, |H|, and ê(h). Fix the value of these quantities and then we will construct a learning problem for which a lower upper bound can not be stated.

Our learning problem will be defined over the input space X = {0, 1}^{|H|}. The hypotheses will be h_{i}(x) = x_{i} where x_{i} is the ith component of the vector x. This construction allows us to vary the true error rate of each hypothesis independent of the other hypotheses. In fact, we can pick any true error rate for any hypothesis by simply adjusting the probability that x_{i} = y. Our learning problem can therefore generate problems according to the following algorithm:

(1) Pick y ∈ {0, 1} uniformly

(2) For each hypothesis, h_{i}, pick x_{i} ≠ y with probability e(h_{i}). By construction, the true error rate of each hypothesis will be e(h_{i}). Now, we can prove the following theorem:

Theorem 3.4.1. (Discrete Hypothesis lower upper bound) For all true error rates e > \frac{ln |H|+ln \frac{1}{δ}}{m} there exists a learning problem and algorithm such that:

Pr_{D^{m}} (∃h ∈ H : e(h) ≥ ē(m, ê(h), \frac{δ}{|H|})) ≥ 1 − e^{−δ}

where ē(m, \frac{k}{m}, δ) ≡ max_{p}\{p : Bin(m, k, p) = δ\}

Proof. Using the family of learning problems discussed above, we know that

∀h, ∀δ ∈ [0, 1] : Pr_{D^{m}} (e(h) ≥ ē(m, ê(h), \frac{δ}{|H|})) ≥ \frac{δ}{|H|}

(negation)

⇒ ∀h, ∀δ ∈ [0, 1] : Pr_{D^{m}} (e(h) < ē(m, ê(h), \frac{δ}{|H|})) < 1 − \frac{δ}{|H|}

(independence)

⇒ ∀δ ∈ [0, 1] : Pr_{D^{m}} (∀h e(h) < ē(m, ê(h), \frac{δ}{|H|})) < (1 − \frac{δ}{|H|})^{|H|}

(negation)

⇒ ∀δ ∈ [0, 1] : Pr_{D^{m}} (∃h e(h) ≥ ē(m, ê(h), \frac{δ}{|H|})) ≥ 1 − (1 − \frac{δ}{|H|})^{|H|}

(approximation)

⇒ ∀δ ∈ [0, 1] : Pr_{D^{m}} (∃h e(h) ≥ ē(m, ê(h), \frac{δ}{|H|})) ≥ 1 − e^{−δ}

□

For small δ, we get that 1 − e^{−δ} ≃ δ which implies that, no significantly better true error bound can be stated for all learning algorithms. In particular, the empirical risk minimization algorithm (which chooses the hypothesis with minimal empirical error) will have a significant probability of a large deviation between the empirical and true error.

3.5. Structural Risk Minimization

Structural Risk Minimization works with a sequence of nested hypothesis sets, H_{1} ⊂ H_{2} ⊂ .... ⊂ H_{l}. For each hypothesis set, a discrete hypothesis bound (3.1.1) on the difference between empirical and true error exists. For “small” hypothesis sets, this bound may be tight while for large hypothesis sets it may be inherently loose. However, we also expect that the best hypothesis in the hypothesis set improves as the hypothesis set becomes larger. This naturally induces a trade-off: there will be some hypothesis set H_{i} for which the true error bound is minimized.

We can’t simply apply the discrete hypothesis bound to the meta-algorithm which picks the algorithm (and associated hypothesis space) with the smallest true error bound since this meta-algorithm could, potentially, output any hypothesis in H_{l}. The simplest way to retrofit the bound to include all hypothesis sets is with the following simple theorem.

Theorem 3.5.1. (Structural Risk Minimization) Let p(i) be some measure across the l hypothesis sets with ∑_{i=1}^{l} p(i) = 1. Then:

Pr_{D^{m}} (∃h ∈ H_{i} ∈ \{H_{1}, ..., H_{l}\} : e(h) ≤ ē(m, ê(h), \frac{p(i)δ}{|H_{i}|} )) ≤ δ

where ē(m, \frac{k}{m}, δ) ≡ min_{p}\{p : Bin(m, k, p) = δ\}

Proof. Apply the union bound to the discrete hypothesis bound (3.1.1). □

The SRM bound is slightly inefficient in the sense that the bound for all hypotheses in H_{2} includes a bound for every hypothesis in H_{1}. This effect is typically small because the size of the hypothesis sets usually grows exponentially, implying that the extra confidence given to a hypothesis h in H_{1} by the bounds used on hypothesis set H_{2}, H_{3}, ... is small relative to the confidence given by the bound for H_{1}. One can remove this slack in Structural Risk Minimization bound by “cutting out” the nested portion of each hypothesis set in the formulation of H_{1}, ..., H_{l}. We will call this Disjoint Structural Risk Minimization.

3.6. Incorporating a “Prior”

In constructing the discrete hypothesis bound (3.1.1), it is notable that an arbitrary choice was made. In the union bound, we decided to give the same error allowance to every hypothesis. This is an arbitrary choice which, in practice, we will wish to make differently. The next theorem is essentially a restatement of the discrete hypothesis bound with this arbitrary choice made explicit. The same bound using the Hoeffding approximation has appeared elsewhere [3][20].

Theorem 3.6.1. (Occam’s Razor Bound) For all hypothesis spaces, H, for all “priors” p(h) over the hypothesis space, H, for all δ ∈ (0, 1]:

Pr_{D^{m}} (∃h ∈ H : e(h) ≥ ē(m, ê(h), δp(h))) ≤ δ

where ē(m, \frac{k}{m}, δ) ≡ max_{p}\{p : Bin(m, k, p) = δ\}

Proof. The proof again starts with the basic observation that:

Pr_{D^{m}} (e(h) ≥ ē(m, ê(h), δ)) ≤ δ

then, we apply the union bound in a nonuniform manner. In particular, we allocate confidence δp(h) to hypothesis h. Since p is normalized, we know that

∑_{h} δp(h) = δ

which implies that the union bound completes the proof. □

Once again, we can relax the Occam’s Razor bound (theorem 3.5.1) with the relative entropy Chernoff bound (2.3.1) to get a somewhat more tractable expression.

Corollary 3.6.2. (Relative Entropy Occam’s Razor Bound) For all hypothesis spaces, H, for all “priors” p(h) over the hypothesis space, H, for all δ ∈ (0, 1]:

Pr_{D^{m}} (∃h ∈ H : KL(ê(h)||e(h)) ≥ \frac{ln \frac{1}{p(h)} + ln \frac{1}{δ}}{m} ) ≤ δ

Proof. approximate the Binomial tail with (2.3.1) and solve for the minimum. □

The Occam’s razor bound is often nonvacuous for discrete learning algorithms such as decision lists and decision trees. The next chapter will discuss a particular motivated choice of the measure p(h) which can lead to much tighter bounds in practice.

Part 2

New Techniques

CHAPTER 4 Microchoice Bounds (the algebra of choices)

The work in this chapter is joint with Avrim Blum and was first presented at ICML [14] and then in the Machine Learning Journal [15]. The fundamental bounds have been refined and improved since then.

Many learning algorithms work by an iterative process in which they take a sequence of steps each from a small set of choices (small in comparison to the overall hypothesis set size). Local optimization algorithms such as hill-climbing or simulated annealing, for example, work in this manner. Each step in a local optimization algorithm can be viewed as making a choice from a small set of possible steps to take. If we take into account the number of choices made and the size of each choice set, can we produce a tighter bound?

The microchoice bounds can be thought of in several ways. The simple microchoice bound can be thought of as a well motivated application of the Occam’s Razor bound (3.5.1). The idea is to use the learning algorithm itself to define a description language for hypotheses, so that the description length of the hypothesis actually produced gives a bound on the estimation error. The adaptive microchoice Theorem can be thought of as a computationally tractable adaptation of Self-bounding Learning algorithms [8]. Microchoice bounds tie together and show the relationship between these different sample complexity bounds.

One other insight arises from the microchoice bounds. In general, we know that choice is “bad” for the purposes of creating a uniform bound on the true error rate. The microchoice bounds give a quantitative understanding of how much choice is “bad”. In particular, the log of the choice space size is the natural measure of “badness”. This is directly related to the log of the hypothesis space size in the discrete hypothesis bound (3.1.1). There is also an indirect relationship with information theory where the log of the alphabet size is an important parameter for specifying the number of bits required to send a message.

Important early work developing approximately self-bounding learning algorithms was also done by Domingos [6].

4.1. A Motivating Observation

For a given learning algorithm A, a distribution D on labeled examples induces a distribution q(h) over the possible hypotheses h ∈ H produced by algorithm A after m examples^{1}. A natural choice for the Occam’s Razor bound (3.5.1) is the measure p(h) = q(h). Is this choice optimal? The answer is “yes”, given the right notion of optimal. In particular, if we start with the relative entropy Occam’s razor bound (3.5.2), we can show that p(h) = q(h) minimizes the expected value of the bound on the Kullback-Leibler divergence between the empirical error and true error.

1 q(h) is the probability over draws of examples and any internal randomization of the algorithm.

Theorem 4.1.1. (KL divergence minimization) p(h) = q(h) minimizes the expected value of the KL divergence in the relative entropy Occam’s Razor bound (3.5.2).

Proof. We need to show that

q(h) = argmin_{p(h)} ∑_{h} q(h)\frac{ln \frac{1}{p(h)} + ln \frac{1}{δ}}{m}

removing terms which the minimum does not depend on, we get:

= argmin_{p(h)} ∑_{h} q(h) ln \frac{1}{p(h)}

adding a constant, we get:

= argmin_{p(h)} ∑_{h} q(h) ln \frac{q(h)}{p(h)}

This is equivalent to minimizing the Kullback-Leibler divergence between the distribution of q(h) and p(h) which is minimized for q(h) = p(h). □

Using the KL divergence as our notion of loss is somewhat non-intuitive. However, it is mathematically simple and not irrational. For all true errors, the KL divergence will be upper and lower bounded between an L_{1} and an L_{2} loss function. Since these are two of the most common loss functions, the choice of KL divergence based loss function should behave similarly well.

The point of these observations is to notice that if we can use the structure of the learning algorithm to produce a choice of q(h) that approximates p(h), the result should be better estimation bounds.

4.2. The Microchoice Bound

The microchoice bound is essentially a compelling and easy way to compute the selection of the measure p(h) for learning algorithms that operate by making a series of small choices. In particular, consider a learning algorithm that works by making a sequence of choices, c_{1}, ..., c_{d}, from a sequence of choice sets, C_{1}, ..., C_{d}, finally producing a hypothesis, h ∈ H. Specifically, the algorithm first looks at the choice set C_{1} and the data z^{N} to produce choice c_{1} ∈ C_{1}. The choice c_{1} then determines the next choice set C_{2} (different initial choices produce different choice sets for the second level). The algorithm again looks at the data to make some choice c_{2} ∈ C_{2}. This choice then determines the next choice set C_{3}, and so on. These choice sets can be thought of as nodes in a choice tree, where each node in the tree corresponds to some internal state of the learning algorithm, and a node containing some choice set C has branching factor |C|. Depending on the learning algorithm, sub-trees of the overall tree may be identical. We address optimization of the bound for this case later. Eventually there is a final choice leading to a leaf, and a single hypothesis is output.

For example, the decision list algorithm of Rivest [25] applied to a set of n features uses the data to choose one of 4n + 2 rules (e.g., “if x̄_{3} then −”) to put at the top. Based on the choice made, it moves to a choice set of 4n − 2 possible rules to put at the next level, then a choice set of size 4n − 6, and so on, until eventually it chooses a rule such as “else +” leading to a leaf.

The way we determine p(h) (equivalently, δ(h)) is as follows. We take our “supply” of δ and give it to the root of the choice tree. The root takes its supply and splits it equally among all its children. Recursively, each child then does the same: it takes the supply it is given and splits it evenly among its children, until all of the supplied confidence parameter is allocated among the leafs. If we examine some leaf containing a hypothesis h, we see that this method gives it δ(h) = δ ∏_{i=1}^{d(h)} \frac{1}{|C_{i}(h)|}, where d(h) is the depth of h in the choice tree and C_{1}(h), C_{2}(h), …, C_{d(h)}(h) is the sequence of choice sets traversed on the path to h. Equivalently, we allocate p(h) = ∏_{i=1}^{d(h)} \frac{1}{|C_{i}(h)|} measure to each h. Note it is possible that several leafs will contain the same hypothesis h, and in that case one should really add the allocated measures together. However, we will neglect this issue, implying that the microchoice bound will be unnecessarily loose for learning algorithms which can arrive at the same hypothesis in multiple ways. The reason for neglecting this is that now, p(h) is something the learning algorithm itself can calculate by simply keeping track of the sizes of the choice sets it has encountered so far. It is important to notice that this construction is defined before observing any data. Consequently, every hypothesis has some bound associated with it before the data is used to pick a particular hypothesis and its corresponding bound.

Another way to view this process is that we cannot know in advance which choice sequence the algorithm will make. However, a distribution D on labeled examples induces a probability distribution over choice sequences, inducing a probability distribution q(h) over hypotheses. Ideally we would like to use p(h) = q(h) in our bounds as noted above. However, we cannot calculate q(h), so instead, our choice of p(h) will be just an estimate. In particular, our estimate p(h) is the probability distribution resulting from picking each choice uniformly at random from the current choice set at each level (note: this is different from picking a final hypothesis uniformly at random). I.e., it can be viewed as the measure associated with the assumption that at each step, all choices are equally likely.

We immediately find the following theorem:

Theorem 4.2.1. (Microchoice Bound) For all hypothesis spaces, H, for all δ ∈ (0, 1]:

Pr_{D^{m}} (∃h ∈ H : e(h) > ē(m, ê(h), \frac{δ}{∏_{i=1}^{d(h)} |C_{i}(h)|})) ≤ δ

where ē(m, \frac{k}{m}, δ) ≡ max_{p}\{p : Bin(m, k, p) = δ\}

Proof. Specialization of the Occam’s Razor bound (3.5.1).

Once again, it will be worthwhile to slightly loosen this bound with the following corollary:

Corollary 4.2.2. (Relative Entropy Microchoice Bound) For all hypothesis spaces, H, for all δ ∈ (0, 1]:

Pr_{D^{m}} (∃h ∈ H : KL(ê(h)||e(h)) > \frac{∑_{i=1}^{d(h)} ln |C_{i}(h)| + ln \frac{1}{δ}}{m} ) ≤ δ

The point of the microchoice bound is that the quantity ē(...) is something the algorithm can calculate as it goes along, based on the sizes of the choice sets encountered. Furthermore, in many natural cases, a “fortuitous distribution and target concept” corresponds to a shallow leaf or a part of the tree with low branching, resulting in a better bound. For instance, in the Decision List case, ∑_{i=1}^{d(h)} ln |C_{i}(h)| is roughly d ln F where d is the length of the list produced and F is the number of features. Notice that d ln F is also the description length of the final hypothesis produced in the natural encoding, thus in this case these theorems yield similar bounds to a simple application of Occam’s razor or SRM.

More generally, the microchoice bound is similar to Occam’s razor or SRM bounds when each k-ary choice in the tree corresponds to log k bits in the natural encoding of the final hypothesis h. However, sometimes this may not be the case. Consider, for instance, a local optimization algorithm in which there are n parameters and each step adds or subtracts 1 from one of the parameters. Suppose in addition the algorithm knows certain constraints that these parameters must satisfy (perhaps a set of linear inequalities) and the algorithm restricts itself to choices in the legal region. In this case, the branching factor, at most 2n, might become much smaller if we are “lucky” and head toward a highly constrained portion of the solution space. One could always reverse-engineer an encoding of hypotheses based on the choice tree, but the microchoice approach is much more natural.

There is also an opportunity to use a priori knowledge in the choice of p(h). In particular, instead of splitting our confidence equally at each node of the tree, we could split it unevenly, according to some heuristic function g. If g is “good” it may produce error bounds similar to the bounds when p(h) = q(h). In fact, the method of section (4.3) where we combine these results with Freund’s query-tree approach can be thought of as an attempt to do exactly this.

4.2.1. Examples. The microchoice bound is not always better than the discrete hypothesis bound (3.1.1). To develop some understanding of how they compare we consider several cases.

4.2.1.1. Greedy Set Cover. Consider a greedy set cover algorithm for learning an OR function over F Boolean features. The algorithms begins with a choice space of size F + 1 (one per feature or halt) and chooses the feature that covers the most positive examples while covering no negative ones. It then moves to a choice space of size F (one per feature remaining or halt) and chooses the best remaining feature and so on until it halts. If the number of features chosen is k then the microchoice bound is:

ϵ(h) = \frac{1}{m} (ln \frac{1}{δ} + ∑_{i=1}^{k} ln(F − i + 2)) ≤ \frac{1}{m} (ln \frac{1}{δ} + k ln(F + 1))

The bound of (3.1.1) is:

ϵ = \frac{1}{m} (ln \frac{1}{δ} + F ln 2) .

If k is small, then the microchoice bound is a lot better, but if k = O(F) then the microchoice bound is slightly worse. Notice that in this case the microchoice bound is essentially the same as the standard Occam’s razor analysis when one uses O(ln F) bits per feature to describe the hypothesis.

4.2.1.2. Decision Trees. Decision trees over discrete sets (say, {0, 1}^{F}) are another natural setting for application of the microchoice bound.

A decision tree differs from a decision list in that the size of the available choice set is larger due to the fact that there are multiple nodes where a new test may be applied. In particular, for a decision tree with K leafs at an average depth of d, the choice set size is K(F − d), giving a bound noticeably worse than the bound for the decision list. This motivates a slightly different decision algorithm which considers only one leaf node at a time. The algorithm adds a new test or decides to never add a new test at this node. In this case, there are (F − d(v) + 1) choices for a node v at depth d(v), implying the bound:

(4.2.1)  KL(ê(h)||e(h)) ≤ \frac{1}{m} (ln \frac{1}{δ} + ∑_{v} ln(F − d(v) + 1))

where v ranges over the nodes of the decision tree.

4.2.2. Pruning. Decision tree algorithms for real-world learning problems often have some form of “pruning” as in [24] and [22]. The tree is first grown to full size producing a hypothesis with minimum empirical error. Then the tree is “pruned” starting at the leafs and progressing up through the tree toward the root node using some test for the significance of an internal node. An internal node is not significant if the reduction in total error is small in comparison to the complexity of its children. Insignificant internal nodes are replaced with a leaf resulting in a smaller tree.

Microchoice bounds have the property that they incidentally prove a bound for every decision tree which can be found by pruning internal nodes. In particular, one of the choices available when constructing a node is to make the node a leaf. Therefore, if we begin with the tree T and then prune to the smaller tree T′, we can apply the bound (4.2.1) to T′ as if the algorithm had constructed T′ directly rather than having gone first through the tree T. This suggests another possible pruning criterion: prune a node if the pruning would result in an improved microchoice bound. That is, prune if the increase in empirical error is less than the decrease in ϵ(h). The similarities to SRM are discussed next.

4.2.3. Microchoice and Structural Risk Minimization. The microchoice bound is essentially a compelling application of the Disjoint SRM bound 3.4.1 where the description language for a hypothesis is the sequence of data-dependent choices which the algorithm makes in the process of deciding upon the hypothesis. The hypothesis set H_{i} is all hypotheses with the same description length in this language.

As an example, consider a binary decision tree with F Boolean features and a Boolean label. The first hypothesis set, H_{1} will consist of 2 hypotheses; always false and always true. In general, we will have one hypothesis set for every legal configuration of internal nodes. The size of a hypothesis set where every tree contains k internal nodes will be 2^{k+1} because there are k + 1 leafs each of which can take 2 values. The weighting p(i) across the different hypothesis sets is defined by the microchoice allocation of confidence.

The principle disadvantage of the microchoice bound is that the sequence of data-dependent choices may contain redundancy. A different SRM bound with a different set of disjoint hypothesis sets might be able to better avoid redundancy. As an example, assume that we are working with a decision tree on F binary features.

There are F + 2 choices (any of F features or 2 labels) at the top node. At the next node down there will be F + 1 choices in both the left and right children. Repeat until a maximal decision tree is constructed. There will be ∏_{i=0}^{F}(F −i+2)^{2^{i}} possible trees. This number is somewhat larger than the number of Boolean functions on F features: 2^{2^{F}}.

4.3. Combining Microchoice with Freund’s Query Tree approach

The next section is devoted to an improvement of the microchoice bound called adaptive microchoice which arises from synthesizing Freund’s query trees with the microchoice bound. This improvement is not easily expressed as a simplification of Structural Risk Minimization. First we require some background material in order to state and understand Freund’s bound.

4.3.1. Preliminaries and Definitions. The statistical query framework introduced by Kearns [12] is the same as the statistical query framework, except that the learning algorithm can only access its data using statistical queries. A statistical query takes as input a binary predicate, χ, mapping examples ^{2} to a binary output: (X, Y) → {0, 1}. The output of the statistical query is the average of χ over the examples seen,

D̂_{χ} = \frac{1}{m} ∑_{i=1}^{m} χ(z_{i})

The output is an empirical estimate of the true value D_{χ} = E_{D}[χ(z)] of the query under the distribution D. Naturally, the distribution of D̂_{χ} will be the familiar Binomial distribution.

It is convenient to define

D̄_{χ}(δ) = max_{p} {p : 1 − Bin (m, D̂_{χ}, p) ≥ δ}

and

\underline{D}_{χ}(δ) = min_{p} \{p : Bin (m, D̂_{χ}, p) ≥ δ\}

and let

I_{χ}(δ) = [\underline{D}_{χ}(δ), D̄_{χ}(δ)]

Then, we know that:

Pr [D̂_{χ} ∉ I_{χ}(δ)] < δ

4.3.2. Background and Summary. Freund [8] considers choice algorithms that at each step perform a Statistical Query on the sample, using the result to determine which choice to take. For an algorithm A, tolerance α (defined next), and distribution D, Freund defines the query tree T_{A}(D, α) as the choice tree created by considering only those choices resulting from answers D̂_{χ} to queries χ such that |D̂_{χ} − D_{χ}| ≤ α. The idea is that if a particular predicate, χ, is true with probability .9 on a random example it is very unlikely that the empirical result of the query will be .1. More generally, the chance the answer to a given query is off by more than α is at most 2e^{−2mα^{2}} by Hoeffding’s inequality. So, if the entire tree contains a total of |Q(T_{A}(D, α))| queries in it, the probability any of these queries is off by more than α is at most 2 · |Q(T_{A}(D, α))| · e^{−2mα^{2}}. In other words, this is an upper bound on the probability the algorithm ever “falls off the tree” and makes a low probability choice. The point of this is that we can allocate half (say) of the confidence parameter δ to the event that the algorithm ever falls off the tree, and then spread the remaining half evenly on the hypotheses in the tree (which hopefully is a much smaller set than the entire hypothesis set).

2 In the real SQ model there is no set of examples. The algorithm asks a query χ and is given a response D̂_{χ} that is guaranteed to be near to the true value D_{χ}. That is, the true SQ model is an abstraction of the scenario described here where D̂_{χ} is computed from an observed sample.

Unfortunately, the query tree suffers from the same problem as the q(h) distribution considered in section (4.1), namely that to compute it, one needs to know D. So, Freund proposes an algorithmic method to find a super-set approximation of the tree. The idea is that by analyzing the results of queries, it is possible to determine which outcomes were unlikely given that the query is close to the desired outcome. In particular, each time a query χ is asked and a response D̂_{χ} is received, if it is true that |D̂_{χ} − D_{χ}| ≤ α, then the range [D̂_{χ} − 2α, D̂_{χ} + 2α] contains the range [D_{χ} − α, D_{χ} + α]. Thus, under the assumption that no query in the correct tree is answered badly, a super-set of the correct tree can be produced by exploring all choices resulting from responses within 2α of the response actually received. By applying this method to every node in the query tree we can generate an empirically observable super-set of the query tree: that is, the original query tree is a pruning of the empirically constructed tree.

A drawback of this method is that it can easily take exponential time to produce the approximate tree, because even the smaller correct tree can have a size exponential in the running time of the learning algorithm. Instead, we would much rather simply keep track of the choices actually made and the sizes of the nodes actually followed, which is what the microchoice approach allows us to do. As a secondary point, given δ, computing a good value of α for Freund’s approach is not trivial, see [8]; we will be able to finesse that issue and use the tighter bound D̂_{χ} ∈ I_{χ}(δ).

In order to apply the microchoice approach, we modify Freund’s query tree so that different nodes in the tree receive different confidence, δ, much in the same way that different hypotheses h in our choice tree receive different values of δ(h).

4.3.3. Microchoice Bounds for Query Trees. The manipulations of the choice tree are now reasonably straightforward. We begin by describing the true microchoice query tree and then give the algorithmic approximation. As with the choice tree in section (4.2), one should think of each node in the tree as representing the current internal state of the algorithm.

We incorporate Freund’s approach into the choice tree construction by having each internal node allocate a portion δ′ of its “supply” δ̃ of confidence parameter to the event that D̂_{χ} ∈ I_{χ}(δ′). The node then splits the remainder of its supply, δ̃− δ′, evenly among the children corresponding to choices that result from answers D̂_{χ} with D̂_{χ} ∈ I_{x}(δ′). Choices that would result from “bad” answers to the query are pruned away from the tree and get nothing. This continues down the tree to the leafs.

How should δ′ be chosen? Smaller values of δ′ result in larger values of α(δ′) leading to more children in the pruned tree and less confidence given to each. Larger values of δ′ result in less left over to divide among the children. Unfortunately, our algorithmic approximation (which only sees the empirical answers D̂_{χ} and needs to be efficient) will not be able to make this optimization. Therefore, we define δ′ in the true microchoice query tree to be \frac{δ̃}{d+1} where d is the depth of the current node.

The algorithmic approximation uses the idea of [8] of including all choices within the double confidence interval of the observed value D̂_{χ}. Unlike [8], however, we do not actually create the tree; instead we just follow the path taken by the learning algorithm, and argue that the “supply” δ(h) of confidence remaining at the leaf is no greater than the amount that would have been there in the original tree. Finally, the algorithm outputs a bound calculated with δ(h).

Specifically, the algorithm is as follows. Suppose we are at a node of the tree containing statistical query χ at depth d(χ) and we have a δ̃ supply of confidence parameter. (If the current node is the root, then δ̃ = δ and d(χ) = 1). We choose δ′ = δ̃/(d + 1), ask the query χ, and receive D̂_{χ}. Let

¯D̄_{χ}(δ) = min_{k} \{\frac{k}{m} : 1 − Bin (m, k, D̄_{χ}(δ)) ≤ δ\}

and

\underline{\underline{D}}_{χ}(δ) = max_{k} \{\frac{k}{m} : Bin (m, k, D̄_{χ}(δ)) ≤ δ\}

with

Î_{χ}(δ) = [\underline{\underline{D}}_{χ}(δ), ¯ D̄_{χ}(δ)]

We now let k be the number of children of our node corresponding to answers in the range Î_{χ}(δ′). We then go to the child corresponding to the answer D̂_{χ} that we received, giving this child a confidence parameter supply of (δ̃ − δ′)/k. This is the same as we would have given it had we allocated δ̃− δ′ to the children equally. We then continue from that child. Finally, when we reach a leaf, we output the current hypothesis h along with the error true error bound, ē(δ̃), based upon our remaining confidence bound.

We now prove that with probability 1−δ, our error estimate ē(δ̃) is correct. By design, with probability 1 − δ all queries in the true microchoice query tree receive good answers, and all hypotheses in that tree have their true errors within their estimates. We argue that in this case, the confidence assigned to the final hypothesis in the algorithmic construction is no greater than the confidence assigned in the true query tree. In particular, assume inductively that at the current node of our empirical path the supply δ̃_{emp} is no greater than the supply δ̃_{true} given to that node in the true tree. Now, under the assumption that the response D̂_{χ} is “good”, it must be the case that the interval Î_{χ}(δ̃_{emp}/(d+1)) contains the interval I_{χ}(δ̃_{true}/(d+1)). Therefore, the supply given to our child in the empirical path is no greater than the supply given in the true tree.

Let d(h) be the depth of some hypothesis h in the empirical path and Ĉ_{1}(h), Ĉ_{2}(h), …, Ĉ_{d}(h) be the sequence of choice sets resulting in h in the algorithmic construction; i.e., Ĉ_{i}(h) is the number of unpruned children of the i-th node. Then, the confidence placed on h will be:

(4.3.1)  δ′(h) = δ ∏_{i=1}^{d(h)} (\frac{i}{i + 1} \frac{1}{|Ĉ_{i}(h)|}) = δ \frac{1}{d(h) + 1} ∏_{i=1}^{d(h)} \frac{1}{|Ĉ_{i}(h)|}

Let A(z^{m}) = h be the output of the learning algorithm. We now have the following theorem:

Theorem 4.3.1. (Adaptive Microchoice Bound) For all hypothesis spaces, H, for all δ ∈ (0, 1]:

Pr_{D^{m}} (∃h ∈ H : e(h) > ē(m, ê(h), δ′(h))) ≤ δ

where ē(m, \frac{k}{m}, δ) ≡ max_{p}\{p : Bin(m, k, p) = δ\}

Proof. By induction, as stated above.

The corresponding relative entropy corollary is:

Corollary 4.3.2. (Relative Entropy Microchoice Bound) For all hypothesis spaces, H, for all δ ∈ (0, 1],

Pr_{D^{m}} (∃h ∈ H : KL(ê(h)||e(h)) > \frac{∑_{i=1}^{d(h)} ln |Ĉ_{i}(h)| + ln(d(h) + 1) + ln \frac{1}{δ}}{m} ) ≤ δ

The bound in theorem (4.3.1) is very similar to (4.2.1) except that the choice complexity is slightly worsened with the ln(d(h)+1) term but improved by replacing C_{i}(h) with the smaller Ĉ_{i}(h).

4.3.4. Allowing batch queries. Most natural Statistical Query algorithms make each choice based on responses to a set of queries, not just one. For instance, to decide what variable to put at the top of a decision tree, we ask F queries, one for each feature; we then choose the feature whose answer was most “interesting”. This suggests generalizing the query tree model to allow each tree node to contain a set of queries, executed in batch. Requiring each node in the query tree to contain just a single query as in the above construction would result in an unfortunately high branching factor just for the purpose of “remembering” the answers received so far. ^{3}

Extending the algorithmic construction to allow for batch queries is easily done. If a node has q queries χ_{1}, …, χ_{q}, we choose the query confidence δ′ = δ̃/(d + 1) as before, but we now split the δ′ evenly among all q queries. We then let k be the number of children corresponding to answers to the queries χ_{1}, …, χ_{q} in the ranges Î_{χ_{1}}(δ′/q), …, Î_{χ_{q}}(δ′/q) respectively. We then go to the child corresponding to the answers we actually received, and as before give the child a confidence supply of (δ̃− δ′)/k. Theorem (4.3.1) holds exactly as before; the only change is that |Ĉ_{i}(h)| means the size of the i-th choice set in the batch tree rather than the size in the single-query-per-node tree.

3 Consider a decision tree algorithm attempting to find the right feature for a node. If the first query returns a value of D̂_{χ} with a confidence of δ then the branching factor would be approximately m · Î_{χ}(δ). This branching factor would be approximately the same for further queries required by the algorithm to make a decision about what feature to use. This results in a total multiplied choice space size of approximately [4m · Î_{χ}(δ)]^{F} which can be reduced to F or less using a batch query.

4.3.5. Example: Batch Queries for Decision trees. When growing a decision tree, it is natural to make a batch of queries and then make a decision about which feature to place in a node. The process is then repeated to grow the full tree structure. As in the decision tree example described in the simple microchoice section, if we have F features and are considering adding a node at depth d(v), there are F − d(v) + 1 possible features that could be chosen for placement in a particular node. The decision of which feature to use is made by comparing the results of F − d(v) + 1 queries to pick the best feature according to some criteria, such as information gain. We can choose δ′ = δ̃/(d + 1), then further divide δ′ into confidences of size δ′/(F − d(v) + 1), placing each divided confidence on one of the F − d(v) + 1 statistical queries. We now may be able to eliminate some of the F − d(v) + 1 choices from consideration, allowing the remaining confidence, δ̃ − δ′ to be apportioned evenly amongst the remaining choices. Depending on the underlying distribution this could substantially reduce the size of the choice set. The best case occurs when one feature partitions all examples reaching the node perfectly and all other features are independent of the target. In this case the choice set will have size 1 if there are enough examples.

4.3.6. Adaptive Microchoice vs. Basic Microchoice. The adaptive microchoice bound is a significant improvement over the simple microchoice bound when the distribution is such that each choice is clear. For example, consider F Boolean features and N = O(F) examples. Suppose that one feature is identical to the label and all the rest of the features are determined with a coin flip independent of the label.

When we apply a decision tree to a data set generated with this distribution, what will be the resulting bound? Given enough examples, with high probability there will only be one significant choice for the first batch query: the feature identical to the label. The second and third batch queries, corresponding to the children of the root feature, will also have a choice space of size 1 with very high probability. The “right” choice will be the label value. Each choice set has size 1 resulting in a complexity of ln 4 due to allocation of confidence to the statistical queries necessary for learning the decision tree. ln 4 is considerably better than ln(F +2)+2 ln(F +1) which the simple version of the microchoice bound provides. Note that the complexity reduction only occurs with a large enough number of examples m implying that the value of ē(δ̃) calculated can improve faster than (inverse) linearly in the number of examples.

The adaptive microchoice bound is never much looser than the simple microchoice bound because under the assumption that choice sets are of size at least 2, the penalty for using the adaptive version, ln d, is always small compared to the complexity term for the simple microchoice bound, ∑_{i=1}^{d(h)} ln |C_{i}(h)|.

4.3.7. Other Adaptive Microchoice. The adaptive microchoice bound provides a simple scheme for dividing confidence between choices and queries. There are other choices which may be useful in some settings. Any scheme which a priori divides the confidence between queries and choices at every node will generally work. Here are two schemes which may be useful:

• Assign a constant proportion of confidence to the query. This scheme is more aggressive than the one used in the adaptive microchoice bounds and may result in a lower complexity when many choices are eliminatable.

The drawback is we no longer get the telescoping in equation (4.3.1) and so the term logarithmic in d(h) in theorem (4.3.2) becomes linear in d(h).

• For a decision tree, assign a portion dependent on the depth of the node in the decision tree that the choice set is over. It is unlikely that choices are eliminatable from nodes not near the root because the number of examples available at a node typically decays exponentially with the (decision tree) depth. A progressive scheme which allocates less confidence to queries for deep nodes will probably behave better in practice.

4.3.8. Comparison with Freund’s Self-Bounding algorithms. Freund’s approach for self-bounding learning algorithms can require exponentially more computation then the microchoice approach. In its basic form, it requires explicit construction of every path in the state space of the algorithm not pruned in the tree. There exist some learning algorithms where this process can be done implicitly making the computation feasible. However, in general this does not appear to be possible.

The adaptive microchoice bound only requires explicit construction of the size of each subset from which a choice is made. Because many common learning algorithms work by a process of making choices from small subsets, this is often computationally easy. The adaptive microchoice bound does poorly, however, when Freund’s query tree has a high degree of sharing; for example, when many nodes of the tree correspond to the same query, or many leaves of the tree have the same final hypothesis. Allowing batch queries alleviates the most egregious examples of this. It is also possible to interpolate between the adaptive microchoice bound and Freund’s bound by a process of conglomerating the subsets of the microchoice bound.

4.3.9. Choice Set Conglomeration. The mechanism of choice set conglomeration is a similar to the batch query technique. It allows you to trade increased computation for a tighter bound. When starting with the simple microchoice bound, this technique can smoothly interpolate with the discrete hypothesis bound (3.1.1). When starting with the adaptive microchoice bound, we can interpolate with Freund’s bound.

Consider a particular choice set, Ĉ_{i}, with elements c_{i}. Each c_{i} indexes another choice set, Ĉ_{i+1}(c_{i}). If the computational resources exist to calculate the union Ĉ_{i,i+1} = ⋃_{c_{i}∈Ĉ_{i}} Ĉ_{i+1}(c_{i}), then |Ĉ_{i,i+1}| can be used in place of |Ĉ_{i}| · |Ĉ_{i+1}| in the adaptive microchoice bound. The conglomeration can be done repeatedly to build large choice sets and also applies to the simple microchoice bound (4.2.1). Conglomeration can be useful for tightening the bound when there are multiple choice sequences leading to the same hypothesis. However, choice set conglomeration is not always helpful because it trades away the fine granularity of the microchoice bound. The extreme case where all choice sets are conglomerated into one choice set and every hypothesis and query have the same weight is equivalent to Freund’s bound.

When the choices of the attached choice sets are all different, conglomeration will have little use because the size of the union of the choice sets is the sum of the sizes of each choice set |Ĉ_{i,i+1}| = ∑_{c_{i}∈Ĉ_{i}} |Ĉ_{i+1}(c_{i})|. If the child sets each have the same size |Ĉ_{i+1}| then this simplifies to |Ĉ_{i,i+1}| = |Ĉ_{i}| · |Ĉ_{i+1}| which results in the same confidence applied to each choice whether conglomerating or not. The best case for conglomeration is equivalent to the batch query case: every sub-choice set contains the same elements. Then we have |Ĉ_{i,i+1}| = |Ĉ_{i+1}| and can pay no cost for the choice set |Ĉ_{i}|.

4.4. Microchoice discussion

Open Problem: Is there a satisfying, natural bound for the continuous case? Preliminary work and thoughts by several people has occurred, but nothing has yet come of it.

CHAPTER 5 PAC-Bayes bounds

The work presented here is also published in [19].

PAC-Bayes bounds are a generalization of the Occam’s razor bound where the output is a distribution over classifiers rather than just a single classifier. This includes the possibility of a distribution over a single classifier, so it is a generalization. PAC-Bayes bounds were first introduced by McAllester [20]. Here, we will focus on the qualitative improvement of the PAC-Bayes by retrofit with relative entropy Chernoff bound 2.3.1. This retrofit is not as trivial as might be expected, but it can be done. The result is the tightest known^{1} PAC-Bayes bound. In addition to the quantitative improvements, this tightening simplifies the proof and adds to our qualitative understanding of the bound.

5.1. PAC-Bayes Basics

In the PAC-Bayes setting, a classifier is defined by a distribution q(h) over the hypothesis space. Each classification is carried out according to a hypothesis sampled from q(h). We are interested in the gap between the expected generalization error e_{q}(h) ≡ E_{q}e(h) and the expected empirical error ê_{q}(h) = E_{q}, where both expectations are taken with respect to q(h). The gap will be parameterized by the relative entropy (or Kullback-Leibler divergence; e.g. [5]):

(5.1.1)  KL(q||p) = E_{h∼q(h)} ln \frac{q(h)}{p(h)}

If the support is finite, we have

(5.1.2)  KL(q||p) = ∑_{h} q(h) ln \frac{q(h)}{p(h)}

The relative entropy is an asymmetric distance measure between probability distributions, with KL(q||p) = 0 ⇔ q = p almost everywhere.

Theorem 5.1.1. (PAC-Bayes [20]) For all “priors” p(h) and for all δ ∈ (0, 1]:

Pr_{D^{m}} (∃q(h) : e_{q}(h) ≥ ê_{q}(h) + \sqrt{\frac{KL(q||p) + ln \frac{m}{δ} + 2}{2m − 1}}) ≤ δ

Proof. Given in [20]. □

The PAC-Bayes bound is almost the same as the Occam’s Razor bound when the distribution is peaked on a single hypothesis and the Occam’s razor bound is proved using the looser Hoeffding inequality. There are a few low order terms of size \frac{ln m}{m}. The real power of the PAC-Bayes bound occurs when the average is over many hypotheses this might occur if the distribution q(h) is picked using Bayes law or via other techniques. One of the most interesting aspects of the PAC-Bayes bound is that it holds for finite and infinite hypothesis spaces.

1 Tong Zhang may prove a slightly tighter bound soon.

5.2. A Tighter PAC-Bayes Bound

We can tighten this bound by employing a more accurate tail bound on the Binomial distribution. The proof of this improved lemma is not as straightforward as a simple substitution of the Hoeffding bound with the relative entropy Chernoff bound 2.3.1 but it can be worked out nonetheless.

Theorem 5.2.1. (Relative Entropy PAC-Bayes bound) For all binary loss functions, l(h, (x, y)), for all “priors” p(h) and for all δ ∈ (0, 1]:

Pr_{D^{m}} (∃q(h) : KL(ê_{q}(h)||e_{q}(h)) ≥ \frac{KL(q||p) + ln \frac{m}{δ}}{m − 1} ) ≤ δ

This bound is always at least as tight as the original PAC-Bayes bound [20] and sometimes much tighter, such as when the average empirical error is near 0.

One interesting new feature of this PAC-Bayes bound is “dimensionally consistency”^{2}. In particular, each side of the equation is a sum of log probabilities. Rewriting, we get that with high probability, approximately the following holds:

mKL(ê_{q}(h)||e_{q}(h)) ≤ KL(q||p)

There is a coding theory interpretation of KL divergence: KL(q||p) = the expected number of extra bits required to encode symbols drawn from q given a code designed for symbols drawn from p rather than from q.

Using the coding theory interpretation of KL divergence, this says approximately: “With high probability the number of extra bits required to encode the empirical errors is less than the number of extra bits required to encode hypotheses drawn from the posterior.”

The retrofit of the PAC-Bayes bound is accomplished by reproving a technical lemma about distributions. The proof relies upon two lemmas. The first is Lemma 22 from [20] which is given by:

Lemma 5.2.2. For all β > 0, K > 0 and Q, P, y ∈ R^{n} satisfying P_{i} > 0, Q_{i} > 0 and ∑_{i} Q_{i} = 1, if

∑_{i=1}^{n} P_{i}e^{βy_{i}} ≤ K

then

∑_{i=1}^{n} Q_{i}y_{i} ≤ \frac{KL(Q||P) + ln K}{β}

Proof. given in [20]. □

The second lemma we will need to prove ourselves. It is basically an improved version of Lemma 17 from [20].

2 My thanks to Patrick Haffner for pointing this out.

Lemma 5.2.3. For all “priors” p(h), for all δ, α ∈ (0, 1):

Pr_{D^{m}} (E_{p}e^{(1−α)mKL(ê(h)||e(h))} > \frac{1}{αδ} ) ≤ δ

Proof. For any given hypothesis h we will prove the following.

(5.2.1)  ∀h E_{D}e^{(1−α)mKL(ê(h)||e(h))} ≤ \frac{1}{α}

The Lemma then follows from the sequence:

⇒ ∀p E_{p}E_{D}e^{(1−α)mKL(ê(h)||e(h))} ≤ \frac{1}{α}

⇒ ∀p E_{D}E_{p}e^{(1−α)mKL(ê(h)||e(h))} ≤ \frac{1}{α}

⇒ ∀p Pr_{D^{m}} (E_{p}e^{(1−α)mKL(ê(h)||e(h))} ≥ \frac{1}{αδ} ) ≤ δ

Conseqeuntly, wConsequentlye must only prove 5.2.1. The relative entropy Chernoff bound 2.3.1 gives us a bound on the cumulative distribution of Binomial distribution. Since e^{(1−α)mKL(ê(h)||e(h))} increases monotonically with decreasing ê(h), the probability distribution function implied by the relative entropy Chernoff bound will maximize the expected value. In other words:

E_{D}e^{(1−α)mKL(ê(h)||e(h))} ≤ E_{D′}e^{(1−α)mKL(ê(h)||e(h))}

where D′ is the worst case distribution derived from the cumulative distribution bound:

Bin(m, k, p) ≤ e^{−mKL(\frac{k}{m} ||p)}

The worst case distribution is given by:

f(x) = \{ \begin{matrix}0 & for x ≥ p \\ −m\frac{∂KL(x||p)}{∂x}e^{−mKL(x||p)} & for x ≤ p \end{matrix}

Taking the expectation with respect to this distribution gives us:

E_{D′} [e^{(1−α)mKL(ê(h)||e(h))}] = ∫_{0}^{1} e^{(1−α)mKL(x||e(h))}f(x)dx

= ∫_{0}^{e(h)} −m\frac{∂KL(x||e(h))}{∂x}e^{−αmKL(x||e(h))}dx

= \frac{1}{α}e^{−αmKL(x||e(h))}|_{0}^{e(h)}
≤ \frac{1}{α}

This finishes the proof of the technical lemma. □

Now, we can prove the relative entropy PAC-Bayes bound 5.2.1.

Proof. First, we can specialize lemma 5.2.3 with α = \frac{1}{m} to get that with probability 1 − δ

E_{p}e^{(m−1)KL(ê(h)||e(h))} ≤ \frac{m}{δ}

Apply lemma 5.2.2 with K = \frac{m}{δ}, β = m − 1, Q_{i} = q(h_{i}) and y_{i} = KL(ê(h)||e(h)) to get:

E_{q}KL(ê(h)||e(h)) = ∑_{i=1}^{n} Q_{i}KL(ê(h_{i})||e(h_{i})) ≤ \frac{KL(q||p) + ln \frac{m}{δ}}{m − 1}

Jensen’s inequality, gives us:

KL(ê_{q}(h)||e_{q}(h)) ≤ E_{q}KL(ê(h)||e(h)) ≤ \frac{KL(q||p) + ln \frac{m}{δ}}{m − 1}

which proves the theorem for the finite case. For the infinite case, a sequence of limits can be defined just as in [20]. □

CHAPTER 6 Averaging Bounds (Improved margin)

The work in this chapter is joint with Matthias Seeger and Nimrod Megiddo. It was first presented at ICML [18].

Averaging bounds are specialized for averaging classifiers. An average has the form

f(x) = ∫ q(h)h(x)dx or f(x) = ∫_{i=1}^{N} q(h_{i})h_{i}(x)dx

where q(h_{i}) ≥ 0 and ∫ q(h)dh = 1. Averaging classifiers have the form:

c(x) = sign (f(x))

Averaging bounds are especially interesting because there are many learning algorithms which use averaging. These techniques include:

(1) Boosting [9]

(2) Bayes-Optimal learning

(3) Support Vector Machines

(4) Bagging [4]

(5) Maximum Entropy classification [11] Averaging is so common that the use of some variety of averaging technique is typical.

The bound in this section is a qualitative improvement on prior results for averaging bounds. For the average learning algorithms listed above, the form of the improvements is most interesting for Maximum Entropy Classification and Bayes-Optimal classification. All (currently known) specialized averaging bounds use as a parameter the “margin”. For this section only, suppose the label and the hypotheses have value −1 or 1. (y ∈ {−1, 1} and h(x) ∈ {−1, 1}). Then, the margin will be defined as

t(x, y) = yf(x)

Some simple observations are immediate:

(1) The margin is bounded. t(x, y) ∈ [−1, 1]

(2) If the classifier is correct, the margin is positive. c(x) = y ⇒ t(x, y) ∈ (0, 1] The error at some margin is the quantity actually used in the averaging bounds. The empirical error at margin θ is defined by:

ê_{θ}(c) = Pr_{S}(t(x, y) ≤ θ)

and the true error at margin θ is defined by:

e_{θ}(c) = Pr_{D^{m}}(t(x, y) ≤ θ)

This definition is consistent in the sense that e_{0}(c) = e(c).

6.1. Earlier Results

The improved averaging bound arises from improving one critical step in the proof of the original margin bound [26] which is stated next.

Theorem 6.1.1. (Margin Bound [26]) For all δ ∈ (0, 1], for all base hypothesis spaces, H,

Pr_{D^{m}} (∃c, θ ∈ (0, 1] : e(c) > ê_{θ}(c) + O (\sqrt{\frac{\frac{ln |H|}{θ^{2}} ln m + ln \frac{1}{δ}}{m}} )) ≤ δ

Proof. Given in [26]. A simplification of the improved averaging bound proof. □

Here, the notation b(m) = O(a(m)) means there exists a constant C such that b(m) ≤ C · a(m) for all m. This margin bound implies that if most training examples have a large margin θ (i.e. t(x, y) > θ for most (x, y) ∈ S) and the hypothesis space is not too large, then the generalization error cannot be large. This theorem can only be non-vacuous when the base hypothesis space is finite. There are various extensions of this bound for continuous hypothesis spaces based upon VC dimension and covering number techniques [26]. However, the extensions tend to result in extremely loose guarantees and are not relevant to the discussion here. One of the advantages of the improved averaging bound is that it can apply in a non-vacuous way to infinite hypothesis spaces. This generalization comes about with essentially zero loosening of the underlying bound.

6.2. A generalized averaging bound

Before discussing the main theorem, it is important to notice that the averaging classifier, f(x) implies a distribution over the base hypothesis space H. This implied distribution is q(h) where

c(x) = sign(∫ h(x)q(h)dh)

The distribution q_{f} will be a parameter in the theorem.

Theorem 6.2.1. (Relative Entropy Averaging Theorem) For all distribution p(h), for all δ ∈ (0, 1]:

Pr_{D^{m}} (∃c, θ ∈ (0, 1] : KL (ê_{θ}(c)||e(c)) ≥ O ( \frac{\frac{KL(q_{f} ||p)}{θ^{2}} ln m + ln m + ln \frac{1}{δ}}{m} )) ≤ δ

Proof. Given in the next section. □

The main theorem uses a KL-divergence based pseudodistance which is a bit hard to understand intuitively. In order to gain intuition, we can relax the tightness of the proof with an inequality.

KL(ê_{θ}(c)||e(c)) ≥ 2(ê_{θ}(c) − e(c))^{2}

This relaxation gives us an immediate corollary.

Corollary 6.2.2. (Relative Entropy Averaging Theorem) For all distribution p(h), for all δ ∈ (0, 1]:

Theorem 6.2.3.

Pr_{D^{m}} (∃c, θ ∈ (0, 1] : e(c) ≥ ê_{θ}(c) + O (\sqrt{\frac{\frac{KL(q_{f} ||p)}{θ^{2}} ln m + ln m + ln \frac{1}{δ}}{m}} )) ≤ δ

The theorems are stated in an asymptotic fashion which is not be very useful in practical applications. Section 6.4 gives some ideas of how to tighten the result, and the non-asymptotic form (6.3.15) given at the end of the proof can be used directly in practice.

The improved averaging bound applies to averages over continuous hypothesis spaces. In this setting, the average needs to be an integral over an uncountablyinfinite set of hypotheses or the KL-divergence will not converge to a finite value. It is exactly because of this limitation that the improvements of this bound are most applicable to Bayes Optimal and Maximum Entropy classifiers.

In practice, the limitation may not be a significant problem because machine learning algorithms over large hypothesis spaces typically have some parameter stability. In other words, a small shift in the parameters of the learned model produces a small change in the prediction of the hypothesis. With hypothesis stability, we can convert any average over a finite set of hypotheses into an average over an infinite set of hypotheses without significantly altering the predictions of the average. This technique is explored in chapter 11 with very positive results.

6.3. Proof of main theorem

6.3.1. Definitions and observations. The proof has the same structure as the original margin bound (6.1.1) proof with one step replaced by the application of the relative entropy PAC-Bayes theorem (5.2.1).

Let N be any natural number; later, the choice of N will be optimized. In the first part of the proof, we regard θ and N as fixed. Later we generalize this so that they may depend on the sample S.

We construct the distribution q_{N} as follows. Draw N hypotheses h_{i} ∼ q(h) independently. Q_{N} might therefore be viewed as the product distribution

(6.3.1)  q(h)^{N}.

Given the h_{i} we define

(6.3.2)  g(x) = \frac{1}{N} ∑_{i=1}^{N} h_{i}(x)

For fixed x, y, the value of yh(x) are i.i.d. Bernoulli variables with the mean equal to the expected margin:

(6.3.3)  E_{q∼h}yg(x) = yf(x)

Therefore, ∀x, y E_{g∼Q_{N}} [yg(x)] = yf(x) and yg(x) is distributed according to the familiar Binomial distribution. Later, we will apply a Binomial tail bound on this quantity.

Before writing out the proof mathematically, it is helpful to consider a graphical view of what we will prove. We will force convergence between three quantities.

The convergences are then tied together with triangle inequalities resulting in the overall proof. The critical improvement of this paper is a refined version of the second convergence.

6.3.2. The Proof. For every θ ∈ (0, 1] and for every (fixed) g, the following simple inequality holds:

(6.3.4)  e(f) = Pr_{D}[yf(x) ≤ 0]

= Pr_{D}[yg(x) ≤ \frac{θ}{2}, yf(x) ≤ 0] + Pr_{D}[yg(x) > \frac{θ}{2}, yf(x) ≤ 0]| yf(x) ≤ 0]

≤ Pr_{D}[yg(x) ≤ \frac{θ}{2}] + Pr_{D}[yg(x) > \frac{θ}{2} | yf(x) ≤ 0]

Note that the left-hand side does not depend on g. By taking the expectation over g ∼ Q_{N} (and exchanging the order of expectations in the second term on the right-hand side), we arrive at

(6.3.5) e(f) ≤ E_{g∼Q_{N}} [Pr_{D}[yg(x) ≤ \frac{θ}{2}]] + E_{D} [P_{g∼Q_{N}} [yg(x) > \frac{θ}{2} | yf(x) ≤ 0]] .

For the rightmost term, we can apply a Binomial tail bound to get:

(6.3.6) e(f) ≤ E_{g∼Q_{N}} [Pr_{D}[yg(x) ≤ \frac{θ}{2}]] + E_{D} [1 − Bin (N, ⌈N \frac{1 + θ/2}{2}⌉ , 0)]

(6.3.7)  = E_{g∼Q_{N}} [Pr_{D}[yg(x) ≤ \frac{θ}{2}]] + 1 − Bin (N, ⌈N \frac{1 + θ/2}{2}⌉ , 0)

We would like to apply the PAC-Bayes theorem5.2.1 to the right-hand term. Here we use the loss function I_{{yg(x)≤θ/2}}. The PAC-Bayes theorem applies for any “prior” distribution. We use as the “prior” the distribution P_{N} = p(h)^{N} where p(h) is the “prior” over the base hypothesis space. The choice of this prior allows us to use the identity:

KL(Q_{N}||P_{N}) = NKL{q(h)||p(h))

It follows from Theorem 5.2.1 that: with probability at least 1 − δ over random choices of S, for every Q,

(6.3.8)  Pr_{D} (∃q(h) : KL (ê_{\frac{θ}{2}} (g)||e_{\frac{θ}{2}} (g)) ≤ \frac{KL(Q_{N}||P_{N}) + ln \frac{m}{δ}}{m − 1} )

where e_{\frac{θ}{2}} (g) = 1 with probability E_{g∼Q_{N}} [Pr_{D}[yg(x) ≤ \frac{θ}{2}]] and 0 otherwise, and ê_{\frac{θ}{2}} (g) = 1 with probability E_{g∼Q_{N}} [Pr_{S}[yg(x) ≤ \frac{θ}{2}]] and 0 otherwise.

By the same argument as in (6.3.4), we get:

(6.3.9) ê_{\frac{θ}{2}} (g) = Pr_{S}[yg(x) ≤ \frac{θ}{2}] ≤ Pr_{S}[yg(x) ≤ \frac{θ}{2}, yf(x) > θ] + Pr_{S}[yf(x) ≤ θ]

(6.3.10)  ≤ Pr_{S}[yg(x) ≤ \frac{θ}{2} | yf(x) > θ] + Pr_{S}[yf(x) ≤ θ]

(6.3.11)  = Pr_{S}[yg(x) ≤ \frac{θ}{2} | yf(x) > θ] + ê_{θ}(f)

Again, we take expectations over g ∼ Q_{N} on both sides, interchange the order of the expectations and apply the Binomial tail bound to get: (6.3.12)

E_{S} [P_{g∼Q_{N}} [yg(x) ≤ \frac{θ}{2}]] ≤ Bin (N, ⌈N \frac{1 + θ/2}{2}⌉ , \frac{1 + θ}{2} ) + Pr_{S} [yf(x) ≤ θ] .

Combining our inequalities, we conclude that with probability at least 1 − δ, for every q(h)

(6.3.13)  KL(q_{S}||p_{D}) ≤ \frac{NKL(q||p) + ln \frac{m}{δ}}{m − 1}

where q_{S} = 1 with probability Bin (N, ⌈N \frac{1+θ/2}{2}⌉ , \frac{1+θ}{2} ) + Pr_{S} [yf(x) ≤ θ] and 0

otherwise, and p_{D} = 1 with probability Pr_{D}[yf(x) ≤ 0]−1+Bin (N, ⌈N \frac{1+θ/2}{2}⌉ , 0) and 0 otherwise.

This bound holds for any fixed N and θ, which is not yet what we need here, since we want to allow these to depend on the data S. We apply a standard technique to resolve this problem. In essence, the bound we proved so far is a statement about certain events, parameterized by N and θ, namely the probability of each event is smaller than δ. However, we need to prove that the probability of the union of all these events is smaller than δ. To this end, we first observe that this union is contained in the union over only a countable number of events. Note that g(x) ∈ {(2k − N)/N|k = 0, 1, …, N}. Thus, even with all the possible (positive) values of θ, there are no more than N +1 events of the form {yg(x) ≤ θ/2}. Denote by k(θ, N) the largest integer k such that k/N ≤ θ/2. We observe that for every θ > 0, every g and every distribution over (x, y):

(6.3.14)  Pr [yg(x) ≤ θ/2] = Pr [yg(x) ≤ \frac{k(θ, N)}{N}] .

This means that the middle step in the proof above, i.e. the application of theorem 5.2.1, depends on (N, θ) only through (N, k). Since the other steps are true with probability one, we see that we can restrict ourselves to the union of countably many events, indexed by (N, k). Now, we “allocate” parts of the confidence quantity δ to each of these events, namely (N, k) receives δ_{N,k} = δ/(N(N + 1)^{2}), N = 1, 2, …; k = 0, …, N. It follows easily that the union of all these events has probability at most ∑_{N,k} δ_{N,k} = δ. Therefore we have proved that with probability at least 1−δ over random choices of S it holds true that for all N and all θ ∈ (0, 1],

(6.3.15)

KL(q_{S}||p_{D}) ≤ \frac{NKL(Q||P) + ln \frac{2m}{δ_{N,k}}}{m − 1} ≤ \frac{NKL(Q||P) + ln \frac{2m}{δ} + 3 ln N + 1}{m − 1}

We can now choose N to minimize this bound. N may depend on θ, Q and the sample S.

The asymptotic bound stated in the theorem can be derived by choosing N (with respect to θ and Q) so as to approximately minimize the bound we have derived above. The first step in this minimization is the replacement of the Binomial tail with a looser approximation such as the Hoeffding bound which gives us:

1 − Bin (N, ⌈N \frac{1 + θ/2}{2}⌉ , 0) ≤ e^{−2N \frac{θ^{2}}{4^{2}}} = e^{−N \frac{θ^{2}}{8}}

Bin (N, ⌈N \frac{1 + θ/2}{2}⌉ , \frac{1 + θ}{2} ) ≤ e^{−2N \frac{θ^{2}}{4^{2}}} = e^{−N \frac{θ^{2}}{8}}

We can then choose

N = ⌈8\frac{ln \frac{m}{KL(q||p)}}{θ^{2}} ⌉ .

This choice gives us:

e^{− \frac{Nθ^{2}}{8}} = \frac{KL(q||p)}{m}

Which implies we have an equation of the form:

(6.3.16) KL (q + \frac{KL(q||p)}{m}||p − \frac{KL(q||p)}{m}) ≤ \frac{θ^{−2}KL(q||p) ln m + ln m + ln \frac{1}{δ}}{m}

In order to prove the result, we must show that:

(6.3.17)  KL (q + \frac{KL(q||p)}{m}||p − \frac{KL(q||p)}{m}) = O (KL (q||p))

We can do this by taking the difference to get an equation of the form: (q + k) ln \frac{q+k}{p−k} + (1 − q − k) ln \frac{1−q−k}{1−p+k} − q ln \frac{q}{p} − (1 − q) ln \frac{1−q}{1−p} If p − q > 2k and k < \frac{1}{2} then we have:

≃ (q + k) ln \frac{q+k+ \frac{k}{p}}{p} + (1 − q − k) ln \frac{1−q−k− \frac{k}{1−p}}{1−p} − q ln \frac{q}{p} − (1 − q) ln \frac{1−q}{1−p}

≃ (q + k)[ln \frac{q}{p} + \frac{k+ \frac{k}{p}}{\frac{q}{p}} + (1 − q − k) ln \frac{1−q}{1−p} − [\frac{k+ \frac{k}{1−p}}{\frac{1−q}{1−p}} ] − q ln \frac{q}{p} − (1 − q) ln \frac{1−q}{1−p}

≃ (q + k)[ln \frac{q}{p} + k(\frac{p+1}{q})] + (1 − q − k)[ln \frac{1−q}{1−p} − k(\frac{2−p}{1−q})] − q ln \frac{q}{p} − (1 − q) ln \frac{1−q}{1−p} ≃ k(1 + p) − k(2 − p) ≃ k Since we have that the difference

(6.3.18)  KL (q + \frac{KL(q||p)}{m}||p − \frac{KL(q||p)}{m}) − KL (q||p) ≃ [KL (q||p)]

the main theorem follows immediately.

6.4. Methods for tightening

The previous section showed a bound in asymptotic form which is good for understanding the trade-offs between the number of examples (m), the size of the hypothesis space (|H|), the margin (θ) and the entropy of the average (H(Q)). However, it is not a good form for those interested in quantitative application of the bound to specific problems. We state improvements which aid in the development of a quantitatively applicable bound. We can tighten the bound above through several techniques:

(1) Parameterizing and then optimizing the parameterization of arbitrary choices within the proof. In the (improved) margin bound proof, we arbitrarily decided to work with the margin of the randomly produced function g(x) at \frac{θ}{2}. This is a good heuristic, but not the optimal choice when we use the improved tail bounds. Since the decision of the margin for the random function g(x) is a parameter of the proof, we are free to optimize it.

(2) Tighter argument within the proof. The optimal value of N is a function of θ, m, KL(q||p) and δ. All of these are known in advance except for KL(q||p). If we can estimate in advance the value of KL(q||p), then it becomes possible to optimize the value of N in a data-independent manner. Consequently, it becomes unnecessary to split our confidence over the possible values of N and we need only split the confidence over the values of θ in proving the bound. The effect of this improvement is reducing 1/δ_{N,k} = 1/(N(N + 1)^{2}) to 1/δ_{N,k} = 1/(N(N + 1)) giving us a small improvement in the low order terms of the improved averaging bound.

6.5. Final thoughts for Averaging Bounds

The improved averaging bound is not yet as tight as it could be and it appears there are several possible theoretical improvements.

(1) Remove the low order terms from the bound to make it more quantitatively applicable.

(2) Improve the argument to take into account the distribution of the margin rather than the margin at some point.

(3) Prove a lower bound which corresponds to the upper bound given here. Since no good lower bound yet exists, we do not know that large improvements in the upper bound are not possible.

Open Problem: In practice, is the averaging bound (6.3.15) ever better than the PAC-Bayes bound 5.2.1? The extra triangle inequality applications in the averaging bound may make it worse than the PAC-Bayes bound in practice. This needs to be verified or refuted.

CHAPTER 7 Computable Shell bounds (exceeding the speed of light)

The first shell bound paper was joint work with David McAllester and was presented at Colt [17]. The work presented here incorporates significant refinement, generalization, and simplification of the first Colt paper.

Roughly speaking, the shell bound (usually) provides much tighter true error rate upper bounds on learned hypotheses. It does this without violating lower upper bounds 3.3 by incorporating much more information into the bound calculation.

We start with the distribution of empirical errors over hypotheses and subtract a small amount from the empirical error rates to create a pessimistic distribution. With high probability, the cumulative of the pessimistic distribution will lower bound the cumulative distribution of hypothesis true error rates. Given this, we can directly calculate a bound on the probability that a “large” hypothesis will produce a misleadingly small error. This bound can be much tighter than standard union bound techniques although the quantity of improvement is highly problem dependent.

After presenting the first bound, we will transform it into a bound on continuous hypothesis spaces using a PAC-Bayes approach [20].

The strongest criticism of shell bounds is, in fact, that too much information is required. While this information is always theoretically observable, it may not be tractable to collect. There are two answers to this criticism given here. The first is an empirical employment on decision tree learning algorithms which shows that in practice, there are often shortcuts which make the information gathering feasible. The second answer is to construct a sampled version of the shell bound which approximate versions of the information required by the shell bound. We will:

(1) Present the discrete shell bound

(2) Present the sampled version of the shell bound.

(3) Extend the discrete shell bound to continuous spaces

7.1. The Discrete Shell Bound

Let B(K, p, m) = \binom{m}{K}e(h)^{K}(1 − e(h))^{m−K} be the probability that hypothesis with true error p produces K errors on m independent examples.

The discrete shell bound works directly with the probability that there will be a confusingly small empirical error. Let

P (ϵ, K) ≡ ∑_{h:e(h)>K+ϵ} B(K, e(h), m)

Intuitively, P (ϵ, K) is a bound on the probability that a hypotheses with a true error larger than K + ϵ will have an empirical error of K. The contribution to the sum will fall off exponentially as the true error, e(h), increases.

Our first step is stating a shell bound which requires unknown information. The purpose of this bound is motivational - it provides incite into why we can expect a large improvement. Later, we will remove the unknown information requirements and recover a useful bound.

Theorem 7.1.1. (Full knowledge theorem) For all δ ∈ (0, 1]:

Pr_{D^{m}}(∃h ∈ H e(h) ≤ ê(h) + ϵ(δ, ê(h))) ≤ δ

where ϵ(δ, K) = min \{ϵ : P (ϵ, K) = \frac{δ}{m}\}

The full knowledge theorem relies on unobservable information—the true error rates of all hypotheses. This theorem is not (quite) trivial because it does not rely upon information about which hypothesis has a particular true error.

Proof. For every hypothesis with a true error rate of

e(h) > K + ϵ(δ, K)

the probability of producing an empirical error of

ê(h) = K

is B(K, e(h), m). Applying the union bound over all hypotheses and all m possible nontrivial values of K completes the proof. □

There are a couple things to note about this theorem. First, for most balanced machine learning problems most hypotheses typically have a true error rate near to 0.5. Given this, and noticing that Binomial tails fall of exponentially, dramatic improvements in the bound are feasible.

Second, there is the annoying detail that we must use \frac{δ}{m} rather than δ. It is possible that theorem holds without splitting δ “m-ways”. Removing the factor of m is an open problem. For the special case of empirical risk minimization algorithms, McDiarmid’s inequality [21] implies that the range of hypotheses with minimum empirical error is of size O(\sqrt{m}) with high probability. Therefore, we need only apply the union bound to O(\sqrt{m}) possible minimum empirical error rates.

In order to realize the benefits of the Shell bound we must relax the information requirements. First, we need a couple of definitions.

ē(ϵ, K, δ, \frac{i}{m}) = max \{K + ϵ, min \{p : 1 − Bin(m, K, p) ≥ δ\}\}

P̂(ϵ, K, δ) ≡ 2 ∑_{h} B(K, ē(ϵ, K, δ, ê(h)), m)

Noting that there are only m + 1 possible empirical errors, we can first let

c (\frac{i}{m}) = |\{h : ê(h) = \frac{i}{m}\}|

be the count of empirical errors at \frac{i}{m}. Then we can redefine:

P̂(ϵ, K, δ) ≡ 2 ∑_{i=0}^{m} c (\frac{i}{m}) B(K, ē(ϵ, K, δ, \frac{i}{m}), m)

Later, we will prove that with high probability, P̂(ϵ, K, δ) ≥ P (ϵ, K). Given that this is so, we can prove a theorem which only relies on observable quantities.

Theorem 7.1.2. (Observable Shell Bound) For all δ > 0:

Pr_{D^{m}}(∃h ∈ H e(h) ≤ ê(h) + ϵ(δ, ê(h))) ≤ δ

where ϵ(δ, K) = min \{ϵ : P̂ (ϵ, K, \frac{δ}{2}) ≤ \frac{δ}{2m}\}

The observable shell bound preserves the important locality property of the full knowledge shell bound. In particular, when most of the true error rates are “far” from the empirical error rate (and m is large enough), we expect to make large (functional) improvements on the discrete hypothesis bound 3.1.1.

The proof rests upon a technical lemma which allows us to bound the unobservable “probability of a misleading event” with an observable event.

Lemma 7.1.3. (Unobservable bound) For all empirical errors, K, for all distributions Q(h), for all δ ∈ (0, 1]:

Pr_{D^{m}} (2 ∑_{h} Q(h)B(K, ē(ϵ, K, δ, ê(h)), m) ≥ ∑_{h:e(h)>K+ϵ} Q(h)B(K, e(h), m)) ≤ δ

This lemma is powerful because it bounds the unobservable right hand side in terms of the observable left hand side.

Proof. Let ē(m, \frac{k}{m}, δ) ≡ min_{p}\{p : 1 − Bin(m, k, p) ≥ δ\}

∀α ∈ (0, 1] ∀h : E_{D^{m}}I(e(h) < ē(m, ê(h), α)) ≤ α

⇒ ∀P (h) E_{P} E_{D^{m}}I(e(h) < ē(m, ê(h), α)) ≤ α

⇒ ∀P (h) E_{D^{m}}E_{P} I(e(h) < ē(m, ê(h), α)) ≤ α

⇒ ∀P (h) Pr_{D^{m}} (E_{P} I(e(h) < ē(m, ê(h), α)) ≥ \frac{α}{δ}) ≤ δ

⇒ ∀P (h) Pr_{D^{m}} (Pr_{P} (e(h) < ē(m, ê(h), α)) ≥ \frac{α}{δ}) ≤ δ

Let P (h) ∝ Q(h)B(K, e(h), m). Then:

⇒ ∀Q(h) Pr_{D^{m}} (\frac{∑_{h:e(h)>K+ϵ∧e(h)>ē(m,ê(h),α)} Q(h)B(K, e(h), m)}{∑_{h:e(h)>K+ϵ} Q(h)B(K, e(h), m)} ≥ \frac{α}{δ}) ≤ δ

set α = \frac{δ}{2}and replace e(h) with ē(m, ê(h), α) to achieve the result. □

We now have all the tools required to prove the theorem.

Proof. (of theorem 7.1.2) Choose Q(h) = the uniform distribution on a our hypothesis space. Then, we know that with probability 1 − δ, P̂(ϵ, K, δ) ≥ P (ϵ, K). Therefore, we can allocate a \frac{δ}{2} probability of failure to the unobservable bound 7.1.3 and a \frac{δ}{2} probability of failure to the full knowledge bound 7.1.1. Assuming P̂(ϵ, K, δ) ≥ P (ϵ, K), the observable bound will be more pessimistic than the full knowledge bound. □

The Observable Shell bound behaves in a strange manner which is unlike other true error bounds. In particular, the true error bound can be discontinuous in the value of δ. This discontinuity implies that relatively small improvements in the shell bounds can result in dramatic improvements in the value of the true error bound. While dramatic improvements can happen with small improvements in the shell bound, we expect that in practice, such large improvements will not be too common, simply because a small improvement is unlikely (amongst all learning problems) to shift the bound across one of these discontinuous transitions.

7.2. Sampling Shell Bound

The Shell bound relies upon the distribution of empirical errors across the entire hypothesis space. Calculating c (\frac{i}{m}), while theoretically possible, is often practically intractable. For example, the space of all binary functions on n features has size 2^{2^{n}} and for a decision tree with a number of nodes k = O(m) there are more than 2^{k} hypotheses with the same number of nodes. In order to avoid this difficulty, we will use sampling which is made possible by noticing that the Shell bound does not require exact knowledge of the empirical error distribution. Instead, we can safely count a hypothesis twice because over-counting monotonically worsens the bound. Assume that we have an oracle which can be used to sample uniformly from the set of all hypotheses. Then, we can bin the sampled hypotheses according to their error rate on the example set. After repeating k times we will arrive at an empirical distribution over error rates which can be altered into a bound on the true distribution of error rates by upper bounding the count c (\frac{i}{m}). Let ĉ(\frac{i}{m}) be the observed number of hypotheses out of k uniform choices with empirical error \frac{i}{m} and define:

c̄(k, \frac{ĉ}{k}, δ, |H|) ≡ |H| ∗ max_{p} \{p : Bin(k, ĉ, p) = \frac{δ}{m}\}

Intuitively, c̄ will be a high confidence upper bound on the number of hypotheses with empirical error rate ĉ. Given these quantities, we can calculate an approximate P̂ according to the formula:

ˆP̂ (ϵ, K, δ) ≡ 2 ∑_{i=0}^{m} c̄(k, \frac{ĉ(\frac{i}{m})}{k}, \frac{δ}{2m}, |H|) B (K, ē(ϵ, K, \frac{δ}{2}, \frac{i}{m}) , m)

Theorem 7.2.1. (Sampling Shell Bound) For all δ > 0:

Pr_{D^{m}}(∃h ∈ H e(h) ≤ ê(h) + ϵ(δ, ê(h))) ≤ δ

where ϵ(δ, K) = min \{ϵ : ˆ P̂ (ϵ, K, \frac{δ}{2}) ≤ \frac{δ}{2m}\}

Proof. For every i, we know that ˆ P̂ (ϵ, K, δ) ≥ P̂ (ϵ, K, \frac{δ}{2}) with probability at

least 1 − \frac{δ}{2}. This implies that ˆ P̂ (ϵ, K, δ) ≥ P (ϵ, K) with probability at least 1 − δ. Applying the union bound with the full knowledge theorem gives us the result. □

The Sampling Shell bound is still relatively fast to calculate given the sampling results, but it is worth noting that many samples are required—the bound will typically tighten linearly with ln k. Thus, the sampling shell bound will interpolate between the discrete hypothesis bound 3.1.1 and the shell bound with as ln k moves from 1 to ln |H|.

7.3. Lower Bounds

The lower upper bound 3.3 does not apply to shell bounds because we are using extra information in the calculation of the bound. Is there a lower upper bound which applies for the information used by the shell bound? The same independent hypothesis technique will allow us to lower bound the full knowledge theorem 7.1.1. In particular, assume that we are given a set of independent hypotheses, each with some true error e(h). What is a lower bound on the probability that one of these hypotheses will have an empirical error of \frac{K}{m}?

If A and B are independent events, then:

Pr(A or B) = Pr(A) + Pr(B) − Pr(A and B)
= Pr(A) + Pr(B) − Pr(A) Pr(B)
= (1 − Pr(B)) Pr(A) + Pr(B)

This implies that we can “add” the independent probabilities together as long as we rescale. In particular, we might have many “bad” hypotheses each with some small probability of error. Using this principle repeatedly where B is the accumulated probability of a bad event and A is the probability that a hypothesis with a large true error rate will have a small empirical error. We get the following theorem:

Theorem 7.3.1. (Lower Upper Shell Bound) For all true errors e(h), K:

Pr_{D^{m}} (∃h : e(h) > K + ϵ and ê(h) = \frac{K}{m} ) ≥ P (ϵ, K)(1 − P (ϵ, K))

Proof. The proof is by finite induction on the set of hypotheses with a large true error rate. Let

P_{H}(ϵ, K) = ∑_{h∈H} B(K, e(h), m)

be the sum of the probabilities that each hypothesis in H′ produces an empirical error of \frac{K}{m}. Now, we want to prove that:

∀H Pr_{D^{m}} (∃h ∈ H : ê(h) = \frac{K}{m} ) ≥ P_{H}(ϵ, K)(1 − P_{H}(ϵ, K)

This is true for the base case of |H| = 1. Assuming that it is true for the case of |H| = n, we need to prove it for the case of H′ = H ∪ |h|. In particular, we have assumed

Pr_{D^{m}} (∃h ∈ H : ê(h) = \frac{K}{m} ) ≥ P_{H}(ϵ, K)(1 − P_{H}(ϵ, K)

Using the earlier independent principle, we get that:

Pr_{D^{m}} (∃h ∈ H′ : ê(h) = \frac{K}{m} )
≥ P_{H}(ϵ, K)(1 − P_{H}(ϵ, K)) + (1 − P_{H}(ϵ, K)(1 − P_{H}(ϵ, K)))B(K, e(h), m)
≥ P_{H}(ϵ, K)(1 − P_{H}(ϵ, K)) + (1 − P_{H}(ϵ, K))B(K, e(h), m)
= P_{H′}(ϵ, K)(1 − P_{H}(ϵ, K))
≥ P_{H′}(ϵ, K)(1 − P_{H′}(ϵ, K))

By induction, this property therefore holds for the set of all hypotheses with a large true error rate. □

Assuming that δ < \frac{1}{2}, the lower upper shell bound is tight to within a factor (in δ) of 2m with the full knowledge bound 7.1.1. Given the exponential behavior of Binomial tails, this usually (but not always) implies a small impact on the true error bound. One important question remains: how does this bound compare to the Observable shell bound 7.1.2? In the observable shell bound, the distribution of true errors is replaced with a pessimistic distribution based upon the observed empirical errors. The “size” of this pessimism in terms of the true error bound is, in general, of size \frac{1}{\sqrt{m}}. Thus, the gap between the lower upper shell bound and the upper shell bound is typically of size \frac{1}{\sqrt{m}}.

7.4. Shell Bounds for Large Spaces

Applying Shell bounds to continuous hypothesis spaces is not easy. In fact, upon first inspection, this appears to be impossible since shell bounds require knowledge of the number of hypotheses with a particular empirical error. We can avoid these difficulties, while introducing a small amount of slack, by always being concerned with the measure rather than the count of hypotheses. In particular, we will keep track of the measure of hypotheses with a confusingly small error and the measure of the hypotheses that we pick. The approach here is similar to the approach in section 5 although more simplistic.

First assume that there is some measure Q over the hypothesis space H. Suppose that we choose some subset, U, of the hypotheses with measure Q(U). We will be concerned with the largest empirical error rate ê_{U}(h) = max_{h∈U} ê(h) and the average true error rate, e_{U}(h) = E_{Q_{U}} e(h). A bound on the gap between the largest empirical error rate and the average true error rate will imply a true error bound for the stochastic classifier which chooses randomly and evaluates.

We will need a different definition of P. Let:

P_{s}(ϵ, K) ≡ ∫_{h:e(h)>K+ϵ} Q(h)Bin(K, e(h), m)dh

We will also need the concept of rounding. Suppose \frac{1}{m^{i}} ≥ Q(U) ≥ \frac{1}{m^{i+1}} then, define:

⌊Q(U)⌋ = \frac{1}{m^{i+1}}

Now, the following theorem holds:

Theorem 7.4.1. (Stochastic Full knowledge) For all distributions Q, For all δ ∈ (0, 1]:

Pr_{D^{m}} (∃U e_{U}(h) ≤ ê_{U}(h) + \frac{1}{m} + ϵ(δ, ê, U))

where ϵ (δ, \frac{K}{m}, U) = min \{ϵ : P_{s}(ϵ, K) ≤ \frac{δ⌊Q(U)⌋}{m^{3}}\}

Proof. Call a hypothesis with a large true error (e(h) > K + ϵ) and small empirical error (ê(h) ≤ K) a “bad” hypothesis. P_{s}(ϵ, K) is the expected measure of the bad hypotheses. We will use Markov’s inequality to bound the actual measure of bad hypotheses. Then, given that the quantity is bounded, we can bound the expected true error by assuming that we included every bad hypothesis in the set U.

Let

ϵ_{Ki} = min \{ϵ : P_{s}(ϵ, K) ≤ \frac{δ}{m^{3+i}} \}

Intuitively, ϵ_{Ki} is the value we will use when ê = K and ⌊Q(ê)⌋ = \frac{1}{m^{i}}. Also Let

P̂_{s}(ϵ, K) = ∫_{h:e(h)>K+ϵ∧ê(h)≤K} p(h)dh

be the actual measure of bad hypotheses. Then, Markov’s inequality, tells us:

∀δ > 0 Pr_{D}(P̂_{s}(ϵ_{Ki}, K) ≥ \frac{m^{2}}{δ} P_{s}(ϵ_{Ki}, K)) ≤ \frac{δ}{m^{2}}

Taking the union bound over all values of ϵ_{Ki}, we get:

∀δ > 0 Pr_{D}(∀K, i P̂_{s}(ϵ_{Ki}, K) ≥ \frac{m^{2}}{δ} P_{s}(ϵ_{Ki}, K)) ≤ δ

So, with probability 1 − δ for all values of K and i, we have: P̂_{s}(ϵ_{Ki}, K) ≤ \frac{1}{m^{1+i}}. Therefore, if Q(U) ≥ \frac{1}{m^{i}}, we know that \frac{Q(U)}{P̂_{s}(ϵ_{Ki},K)} ≥ m. Assuming that all of the

bad hypotheses have true error 1 and all the rest have true error at most \frac{K}{m} + ϵ_{Ki}, we get the following true error bound:

e_{U}(h) ≤ ê_{U}(h) + \frac{1}{m} + ϵ_{êi}

□

The stochastic full knowledge bound is loose when applied to the full knowledge setting by δ → \frac{δ}{m^{2}} . Typically, this results in only a \frac{2 ln m}{m} increase in the size of ϵ, although the increase can sometimes be much larger near phase transitions. These factors of \frac{ln m}{m} may be removable with improved argumentation. Naturally, the stochastic full knowledge bound can be used to prove a stochastic observable bound.

The next theorem is the observable analog of the stochastic full knowledge bound. Here, we eliminate the unobservable quantities to produce a stochastic observable shell bound. The observable quantity we will use is:

P̂_{s}(ϵ, K, δ) ≡ 2 ∑_{h} Q(h)Bin(K, ē(ϵ, K, δ, ê(h)), m)

where

ē(ϵ, K, δ, \frac{i}{m}) = max \{K + ϵ, min \{p : 1 − Bin(m, K, p) ≥ δ\}\}

is a slightly pessimal estimate of the true error rate given the empirical error rate as before.

Theorem 7.4.2. (Stochastic Observable Shell Bound) For all distributions Q, For all δ ∈ (0, 1]:

Pr_{D^{m}} (∃U e_{U}(h) ≤ ê_{U}(h) + \frac{1}{m} + ϵ(δ, ê, U))

where ϵ (δ, \frac{K}{m}, U) = min \{ϵ : P̂_{s}(ϵ, K, \frac{δ}{2}) ≤ \frac{δ⌊Q(U)⌋}{2m^{3}}\}

Proof. First note that the unobservable bound lemma 7.1.3 implies that with probability 1 − \frac{δ}{2}, we have P̂_{s}(ϵ, K, \frac{δ}{2}) ≥ P_{s}(ϵ, K). Given that this is the case, our choice of ϵ will be at least as pessimistic as the choice defined by the Stochastic Full Knowledge bound 7.4.1. We thus have two sources of failure: the unobservable bound lemma will fail with probability at most \frac{δ}{2} and the stochastic full knowledge bound will fail with probability \frac{δ}{2}. The union bound then implies that the Stochastic Observable Shell Bound holds with probability 1 − \frac{δ}{2}. □

The information requirements for the continuous space shell bound are even more severe than the requirements for the discrete space shell bound. In particular, we need to know the exact measure of the hypotheses with any particular empirical error. Clearly, this is unrealistic. We can relax this requirement to observations computable in a finite amount of time using the sampling techniques of theorem 7.2.1. In particular, given a well-behaved distribution Q, we can make a bounded estimate of the measure of hypotheses with some empirical error rate. Given this bounded estimate, we can then calculate a pessimistic shell bound for the continuous space.

7.5. Conclusion

There remain several important open questions:

(1) Can we remove the remaining division of δ by m?

(2) Is there a natural lower bound on the true error rate which uses the shell approach?

(3) For the continuous space shell bounds, two additional divisions by m were introduced. Is it possible to remove these factors with an improved argument?

(4) Our extension to the continuous case was done in the style of PAC-Bayes bounds, but a more common technique for extending to the continuous case is via the use of covering numbers. Is there a natural way to extend Shell bounds to the continuous case using the concept of a covering number?

CHAPTER 8 Tight covering number bounds

8.1. Introduction

Covering number bounds are used to bound the true error rate of classifiers chosen from an infinite hypothesis space using m examples. A cover is a finite set of hypotheses which satisfies the following property: every hypothesis in the infinite space is “near” some element in the finite cover. When a Lipschitz condition holds on the hypothesis space, it is generally possible to construct these covers and the existence of a cover is required for learnability [2]. Alternatively, Sauer’s lemma bounds the size of the cover in terms of the VC dimension which is defined combinatorially: the VC dimension is the largest number of examples which the hypothesis space can classify in an arbitrary manner.

The principal disadvantage of covering number results is that they are notoriously loose, to the point that they are often useless when applied in practice. Here, “useless” means that the bound on the true error rate is “always wrong”. The amount of “looseness” can be quantified by comparison with other bounds in the regimes where other bounds hold. On a finite hypothesis space we have near-perfect agreement between the upper bound 3.1.1 and the lower upper bound 3.3.1 for independent hypotheses. In fact, as the number of examples goes to infinity, the agreement is perfect, regardless of the size of the hypothesis space. When we apply covering number bounds to this problem such properties do not arise. Since part of the argument involves splitting the examples into 2 sets, the difference between a covering number based upper bound and the lower upper bound can be large even when the number of examples goes to infinity. In practice, the covering number bound at least squares the discrete hypothesis size. Obviously, further loosening of covering number bounds with Sauer’s lemma result in even worse bounds.

Can we construct a calculable true error upper bound for continuous hypothesis spaces which is at least asymptotically tight? In a sense, this has already been done with PAC-Bayes bounds 5, but there are drawbacks in applicability to that approach since PAC-Bayes bounds don’t apply in a meaningful way to a single hypothesis drawn from an infinite hypothesis space. A covering number argument would hopefully apply in a meaningful way to a singly hypothesis. A covering number bound which is asymptotically tight on some learning problems does exist and is covered next.

8.2. The Setting and Prior Results

We will first discuss standard covering number bounds. Define a “distance” in terms of how often hypotheses disagree according to:

d_{D}(h, f) = Pr_{D}(h(x) ≠ f(x))

Now, start with an epsilon net defined by:

N(H, ϵ, d_{D}) = inf_{F} |{F : ∀h∃f ∈ H : d_{D}(h, f) ≤ ϵ}|

Then a covering number is defined as:

C(H, ϵ) = sup_{D}N(H, ϵ, d_{D})

Theorem 8.2.1. (Covering number bound) For all δ ∈ (0, 1]:

∀H Pr_{D^{m}} (e(h) ≥ ê(h) + 4\sqrt{\frac{ln 4C(H, ϵ) + ln \frac{1}{δ}}{m}} ) ≤ δ

Proof. In [10]. □

How tight is this bound when applied to a finite independent hypothesis space? We can improve the constants by elimination of unnecessary triangle inequalities in the discrete case and get the following results:

Pr_{D}(e(h) − ê(h) ≥ 2\sqrt{\frac{ln 4|H| + ln δ}{m}}) ≤ δ

Comparing this with a very loose application of the discrete hypothesis bound 3.1.3 we see that the penalty term in the covering number bound is worse by factor of 2\sqrt{2}. Put another way, dividing the number of samples by 8 or increasing the hypothesis space size to |H|^{8} and then applying a sloppy discrete hypothesis bound is about equivalent to applying a very specialized covering number bound. We seek a covering number bound which does not divide the effective value of a hypothesis by 8.

8.3. Bracketing Covering Number Bound

There is an alternative version of the covering number bounds which has been little used in learning theory. This is mentioned as the “direct method” in [10] and Section II.2 of [23] discusses this approach but is only concerned with asymptotic consistency rather than rates of convergence.

We start with a more restricted notion of covering—a covering in which we bracket the hypotheses. Let Z be the space of (x, y) labeled examples and h(Z) = {(x, y) : h(x) ≠ y} in:

N_{[]}(H, γ, d_{D}) = inf_{F} |\{F : ∀h ∃(f, f′) ∈ F : \begin{matrix}d_{D}(f, f′) ≤ γ \\ and f(Z) > h(Z) > f′(Z) \end{matrix} \}|

In other words, f and f′ are two sets which are “above” and “below” every hypothesis that they cover. Note that it is very important in this definition that the sets f and f′ are not required to correspond to functions in H. In fact, they can simply be understood as arbitrary sets of (x, y) pairs.

It is immediately obvious that:

N_{[]}(H, γ, d_{D}) ≥ N(H, γ, d_{D})

However, the relationship between N_{[]}(H, γ, d_{D}) and C(H, γ) is ambiguous: either could be larger.

Using this alternative notion of a covering, we have the following theorem:

Theorem 8.3.1. Let f(h) be the upper bracket of any hypothesis, h. For all γ ∈ (0, 1], for all δ ∈ (0, 1]:

Pr_{D^{m}} (∃h ∈ H : \begin{matrix}e(h) ≥ ē(m, ê(f(h)), \frac{δ}{2N_{[]}(H,γ,d_{D})}) \\ or ê(f(h)) − ê(h) ≥ b (m, γ, \frac{δ}{2N_{[]}(H,γ,d_{D})}) \end{matrix} ) ≤ δ

where ē(m, \frac{K}{m}, δ) ≡ max_{p}\{p : Bin(m, K, p) = δ\} and b (m, p, δ) ≡′ min_{K} \{\frac{K}{m} : 1 − Bin(m, K, p) ≤ δ\} .

This theorem constrains the distance between ê(f(h)) and e(h) and the distance between ê(f(h)) and ê(h). Consequently, it constrains the distance between e(h) and ê(h). The proof of the theorem rests on the following two lemmas which each assert a convergence. Graphically, the proof has the following form:

Lemma 8.3.2. Let f(h) be the upper bracket of any hypothesis, h. For all γ ∈ (0, 1], for all δ ∈ (0, 1]:

Pr_{D^{m}} (∃h ∈ H : ê(f(h)) − ê(h) ≥ b (m, γ, \frac{δ}{N_{[]}(H, γ, d_{D})})) ≤ δ

where b (m, p, δ) ≡′ min_{K} \{\frac{K}{m} : 1 − Bin(m, K, p) ≤ δ\}

Proof. If f(h), f′(h) bracket h, we have:

e(f(h)) − e(f′(h)) ≤ γ

Therefore a coin which is “heads” when f(h)(z) ≠ f′(h)(z) has a bias of γ or less. Since f′(h) is correct everywhere that h is correct, we also know:

∀ϵ Pr_{D^{m}}(ê(f(h)) − ê(h) ≥ ϵ) ≤ Pr_{D^{m}}(ê(f(h)) − ê(f′(h)) ≥ ϵ)

Therefore, we have at most N_{[]}(H, γ, d_{D}) Binomial distributions, each with bias at most γ, and wish to bound the probability of a large deviation. Using an upper binomial tail calculation, we get the result. □

Lemma 8.3.3. For all δ ∈ (0, 1]:

Pr_{D^{m}} (∃f, f′ ∈ N_{[]}(H, γ, d_{D}) : e(f(h)) ≥ ē(m, ê(f(h)), \frac{δ}{N_{[]}(H, γ, d_{D})}))

where ē(m, \frac{K}{m}, δ) ≡ max_{p}\{p : Bin(m, K, p) = δ\}

Proof. Application of the discrete hypothesis space bound 3.1.1 for f in every (f, f′) pair. □

We can now combine the lemmas to get the theorem.

Proof. (of theorem 8.3.1) Allocate \frac{δ}{2} confidence to each lemma and use the union bound with both lemmas to get:

Pr_{D^{m}} (∃h ∈ H : \begin{matrix}e(f(h)) ≥ ē(m, ê(f(h)), \frac{δ}{2N_{[]}(H,γ,d_{D})}) \\ ê(f(h)) − ê(h) ≥ b (m, γ, \frac{δ}{2N_{[]}(H,γ,d_{D})}) \end{matrix} ) ≤ δ

where ē(m, \frac{K}{m}, δ) ≡ max_{p}\{p : Bin(m, K, p) = δ\} and b (m, p, δ) ≡′ min_{K} \{\frac{K}{m} : 1 − Bin(m, K, p) ≤ δ\} . Since e(h) ≤ e(f(h))

by construction, the proof is complete. □

The alternative covering number argument has a significant advantage over the standard argument: when restricted to a finite hypothesis space, the argument becomes tight. In particular, on a finite hypothesis space, we can set γ = 0 and get: N_{[]}(H, 0, d_{D}) ≤ |H|. The bound reduces to the standard discrete hypothesis space bound 3.1.1. Consequently, there exist learning problems where this bound is quite tight.

The bracketing covering approach has the following advantages and disadvantages:

(1) Advantage: Covering defined in terms of the actual problem rather than a worst case over all problems.

(2) Advantage: Asymptotically tight for some learning problems.

(3) Disadvantage: Less general. There may exist spaces which are not coverable in the alternative approach.

(4) Disadvantage: N_{[]}(H, γ, d_{D}) is more difficult to compute than N(H, γ, d_{D}). In a sense, this bound is useless because it requires knowledge of the unknown distribution D in order to calculate a covering number. In the next section, we will see that bounds on the bracketing covering number which hold for all D can often be found.

8.4. Covering number calculations

It is important to demonstrate that this covering number is feasible to calculate and gives a reasonable answer. Bracketing covering numbers have already been proved for many function classes [7][27]. Here, we will present a proof for the simplest of continuous hypothesis spaces: the step function on a line segment. Each hypothesis will be indexed by a number a ∈ [0, 1] according to:

h_{a}(x) = sign(x − a)

What is N_{[]}(H, γ, d_{D}) for this hypothesis set?

Theorem 8.4.1. Assume that D can be described by a probability density function, then:

N_{[]}(H, γ, d_{D}) ≤ \frac{1}{γ} + 1

Proof. Consider a range of hypotheses from h_{a} to h_{b}. For this range of hypotheses, we can choose a bracketing pair, (f, f′). In particular, we can choose f and f′ which agree on [0, a) and [b, 1] and always predict either incorrectly (f) or correctly (f′) on [a, b). The distance between these functions satisfies:

d_{D}(f, f′) = Pr_{D}(x ∈ [a, b))

and every hypothesis h_{c} in [a, b) satisfies ∀z f(z) ≥ h_{c}(z) ≥ f′(z). Consequently, if a and b are chosen appropriately, we will observe d_{D}(f, f′) ≤ γ.

If D can be described by a probability distribution, then we can simply calculate the marginal distribution, D_{x}, and the cumulative distribution of the margin, F_{D}(x). Now, find a_{i} for which F_{D}(a_{i}) = \frac{i}{γ} for i < \frac{1}{γ}. Choose b_{i} = a_{i+1}. There are at most \frac{1}{γ} + 1 intervals, each with a measure (according to D) of at most γ. Consequently, we can cover H with \frac{1}{γ} + 1 pairs of (f_{i}, f′_{i}). □

There are several important things to note about this proof.

(1) We used the property that a small change in the hypothesis only affected the prediction on a small portion of the input space.

(2) The bound on N_{[]} holds for all D with a density function, not just the D which we happen to observe.

(3) The bound on N_{[]}(H, γ, D) is exactly the same as a bound on N (H, \frac{γ}{2} , D). In fact, the proof can be extended to all D (even ones with point masses) at the cost of a factor of 2 worsening and a messier argument. Property (2) is desirable because it is often not the case that we know the distribution D when we wish to apply the bound. Property (1) is an essential technique that can be used to prove other covering number bounds for this notion of covering number.

Can we show partial order covering number bounds for other classifiers? There is a straightforward extension of the previous proof for classifiers which consist of axis parallel intervals in R^{n}. More work is required to prove partial order covering numbers for the hypothesis spaces of standard learning algorithms.

8.5. Conclusion and Future Work

We presented an alternative covering number argument and showed that the true error rate bounds constructed using this argument are within O (\frac{ln m}{m}) of the lower bound on some learning problems. This is a significant improvement over prior results which just bound the ratio of the lower and upper bounds up to a constant. We also presented a simple improvement on PAC-Bayes bounds for stochastic classifiers which achieves a similar O (\frac{ln m}{m}) difference between the lower and upper bounds.

It is interesting to examine the relationship between the bracketing covering number and the PAC-Bayes bound. With this notion of covering number we can guarantee that all of the hypotheses covered by the same bracketing pair have similar empirical as well as true errors. Thus, we can relate the error rate of an individual hypothesis to a set of hypotheses with a significant measure — exactly the setting where the PAC-Bayes bound is tight.

Much work remains to be done in order to fulfill a quest for quantitatively tight learning bounds.

(1) Proofs on the size of the partial order covering number need to be made for common learning algorithms.

(2) Can this alternate form of covering number be related to the VC dimension or to the standard definition of covering number?

(3) Can we extend the class of problems for which the lower and upper bounds differ by only O (\frac{ln m}{m}) to a larger set?

CHAPTER 9 Holdout bounds: Progressive Validation

9.1. Progressive Validation Technique

Progressive validation is a technique which allows you to use almost \frac{1}{2} of the data in a holdout set for training purposes while still providing the same guarantee as the holdout bound. It first appeared in [33] and is discussed in a more refined and detailed form here.

Suppose that you have a training set of size m_{train} and test set of size m_{pv}. Progressive validation starts by first learning a hypothesis on the training set and then testing on the first example of the test set. Then, we train on training set plus the first example of the test set and test on the second example of the test set. The process continues m_{test} iterations. Let m abbreviate m_{pv}. Then, we have m hypotheses, h_{1}, ..., h_{m} and m error observations, ê_{1}, ..., ê_{m}. The hypothesis output by progressive validation is the randomized hypothesis which chooses uniformly from h_{1}, ..., h_{m} and evaluates to get an estimated output.

Since we are randomizing over hypotheses trained on m_{train} to m_{train} +m_{pv} −1 examples, the expected number of examples used by any hypothesis is m_{train} + \frac{m_{pv}−1}{2}. Given that training can exhibit phase transitions, the extra few examples can greatly improve the accuracy of the trained example.

The true error rate of this randomized hypothesis will be:

e_{pv} = \frac{1}{m_{pv}} ∑_{i=1}^{m_{pv}} e(h_{i})

where e(h_{i}) = Pr_{D}(h_{i}(x) ≠ y) and the empirical error estimate of this randomized hypothesis will be:

ê_{pv} = \frac{1}{m_{pv}} ∑_{i=1}^{m_{pv}} ê_{i}

9.2. Variance Analysis

Bounding the deviation of ê_{pv} is more difficult than bounding the deviation of a holdout error. To understand this, we can think of two games, the holdout game and the progressive validation game.

In the holdout game, your opponent chooses a bias and then nature flips m coins with that bias. If the deviation of the average number of heads is larger than ϵ, then you lose. Otherwise, you win.

In the progressive validation game, the opponent chooses the bias of each coin just before it is flipped. The goal of the opponent remains the same, and the opponent wins if a large deviation is observed.

The progressive validation opponent is stronger than the holdout opponent since the progressive validation opponent could choose the same bias for every coin. Nonetheless, we will see that the progressive validation opponent is not much stronger.

There are two ways in which we can show that the progressive validation opponent is not much stronger. The first technique will show that the variance of the progressive validation estimate is smaller than might be expected.

Theorem 9.2.1. Suppose we test the progressive validation hypothesis on m_{test} = m_{pv} additional examples. Let ê_{test} be the empirical error on these examples. Then, we have:

E_{(x,y)^{mpv +m_{test}} ∼D^{mpv +m_{test}}} (ê_{test} − e_{pv})^{2}
≥ E_{(x,y)^{mpv} ∼D^{mpv}} (ê_{pv} − e_{pv})^{2}

Proof. Every example on the left hand side can be though of as a coin with bias e_{pv}. The variance of the LHS is then m ∗ e_{pv}(1 − e_{pv}). The right hand side is:

E_{(x,y)^{m}∼D^{m}}(ê_{pv} − e_{pv})^{2}

= E_{(x,y)^{m}∼D^{m}} [∑_{i=1}^{m} ê_{i} − e_{i}]^{2}

where e_{i} = e(h_{i})

= E_{(x,y)^{m}∼D^{m}} [∑_{i≠j}(ê_{i} − e_{i})(ê_{j} − e_{j}) + ∑_{i=1}^{m}(ê_{i} − e_{i})^{2}]

= ∑_{i≠j} E_{(x,y)^{m}∼D^{m}}(ê_{i} − e_{i})(ê_{j} − e_{j}) + ∑_{i=1}^{m} E_{(x,y)^{m}∼D^{m}}(ê_{i} − e_{i})^{2}

The cross product term is:

E_{(x,y)^{m}∼D^{m}}(ê_{i} − e_{i})(ê_{j} − e_{j})

Without loss of generality, assume that i < j. What we wish to prove is that the expected value of this quantity is 0 conditional on the values of all random variables other than ith or jth example. Let S_{ij} be the set of examples minus the ith and jth example. Also, let z_{i} and z_{j} be the ith and jth labeled examples. If we can show that:

∀S_{ij} : E_{z_{i},z_{j}|S_{ij}}(ê_{i} − e_{i})(ê_{j} − e_{j}) = 0

then linearity of expectation will imply that:

E_{(x,y)^{m}∼D^{m}}(ê_{i} − e_{i})(ê_{j} − e_{j}) = 0

The value of e_{i} is fixed after conditioning on S_{ij} (and assuming a deterministic learning algorithm) while the value of e_{j} is not fixed: it is dependent on the random variable z_{i}. Let e_{j}(z_{i}) be the derived random variable. Then, the expectation is:

E_{z_{i},z_{j}|S_{ij}}(ê_{i} − e_{i})(ê_{j} − e_{j})

(implicitly conditioning on S_{ij})

= ∑_{z_{i},z_{j}} Pr_{D}(z_{i}) Pr_{D}(z_{j})(ê_{i}(z_{i}) − e_{i})(ê_{j}(z_{j}, z_{i}) − e_{j}(z_{i}))

= ∑_{z_{i}} Pr_{D}(z_{i})(ê_{i}(z_{i}) − e_{i}) ∑_{z_{j}} Pr_{D}(z_{j})(ê_{j}(z_{j}, z_{i}) − e_{j}(z_{i}))

For any fixed z_{i}, we want to show that ∑_{z_{j}} Pr_{D}(z_{j})(ê_{j}(z_{j}, z_{i}) − e_{j}(z_{i})) = 0.With z_{i} fixed, the true error rate of the jth hypothesis is e_{j}(z_{i}). Therefore, the probability of observing an error (ê_{j}(z_{j}, z_{i}) = 1) is e_{j}(z_{i}), and the probability of observing no error (ê_{j}(z_{j}, z_{i}) = 0) is 1 − e_{j}(z_{i}). This implies:

∑_{z_{j}} Pr_{D}(z_{j})(ê_{j}(z_{j}, z_{i}) − e_{j}(z_{i}))

= ∑_{z_{j}:ê_{j}(z_{j},z_{i})=0} Pr_{D}(z_{j})(−e_{j}(z_{i})) + ∑_{z_{j}:ê_{j}(z_{j},z_{i})=1} Pr_{D}(z_{j})(1 − e_{j}(z_{i}))

= (1 − e_{j}(z_{i}))(−e_{j}(z_{i})) + e_{j}(z_{i})(1 − e_{j}(z_{i}))

= 0

Putting this together, we get:

cross term = ∑_{z_{i}} Pr_{D}(z_{i})(ê_{i}(z_{i}) − e_{i}) ∗ 0

= 0

Since this sum is zero regardless of the values of all other random variables, the cross product terms all have expectation zero. Note that we can extend this proof to randomized algorithms by conditioning on the random bits of the algorithm in the above argument. Consequently:

= ∑_{i=1}^{m} E_{(x,y)^{m}∼D^{m}} [(ê_{i} − e_{i})^{2}]

= ∑_{i=1}^{m} e_{i}(1 − e_{i})

So, all that we must show is:

me_{pv}(1 − e_{pv}) ≥ ∑_{i=1}^{m} e_{i}(1 − e_{i})

which follows from Jensen’s inequality and the convexity of x(1 − x) on the interval [0, 1]. □

9.3. Deviation Analysis

The second way in which we can show that the progressive validation opponent is not so strong is by bounding the deviation directly. Surprisingly, we can prove exactly the same bound as for Hoeffding inequality.

Theorem 9.3.1.

Pr_{(x,y)^{m}∼D^{m}}(e_{pv} ≥ ê_{pv} + ϵ) ≤ e^{−2mϵ^{2}}

Proof. (A variant of Chernoff)

Pr_{(x,y)^{m}∼D^{m}}(e_{pv} ≥ ê_{pv} + ϵ)

⇔ ∀λ Pr_{(x,y)^{m}∼D^{m}}(e^{λme_{pv}} ≥ e^{λm(ê_{pv}+ϵ)})

⇔ Pr_{(x,y)^{m}∼D^{m}}(e^{λm(e_{pv}−ê_{pv}−ϵ)} ≥ 1)

≤ E_{(x,y)^{m}∼D^{m}}e^{λm(e_{pv}−ê_{pv}−ϵ)}

= E_{(x,y)^{m}∼D^{m}}e^{λ(∑_{i=1}^{m} e_{i}−ê_{i}−ϵ)}

= ∏_{i=1}^{m} E_{(x,y)∼D} [e^{λ(e_{i}−ê_{i}−ϵ)}|ê_{1}, ..., ê_{i−1}]

The value of e^{λ(e_{i}−ê_{i}−ϵ)} is only dependent on ê_{1}, ..., ê_{i−1} through the value of e_{i}. For all possible hypotheses, h_{i}, we know that ê_{i} is a Bernoulli random variable with bias e_{i} = Pr_{D}(h_{i}(x) ≠ y). This is true regardless of how we choose h_{i}. Consequently, we have:

(9.3.1)  = ∏_{i=1}^{m} E_{(x,y)∼D} [e^{λ(e_{i}−ê_{i}−ϵ)}]

Since this is true for all λ, we can choose the optimal λ. In general, this is an optimization problem which can be worst-case simplified with the inequality:

E_{(x,y)∼D}e^{λ(e_{i}−ê_{i})} ≤ e^{\frac{λ^{2}}{8}}

which implies:

∀λ ≤ ∏_{i=1}^{m} e^{\frac{λ^{2}}{8} −λϵ)}

This is optimized for \frac{2λ}{8} = ϵ which implies λ = 4ϵ giving:

≤ ∏_{i=1}^{m} e^{−2ϵ^{2}}

= e^{−2mϵ^{2}}

□

Open Problem: Starting with 9.2.1, derive a bound similar to the relative entropy Chernoff bound which holds for progressive validation.

CHAPTER 10 Combining sample complexity and holdout bounds

10.1. Combination Possibilities

We have two forms of bound, one which uses training set errors and one which uses holdout set errors. The obvious question to ask is: can we combine the information from both bounds? Presumably, if we use both the training error and the test error, we should be able to construct a better confidence interval for the location of the true error rate.

Given a fixed hypothesis and learning problem, we know that the test error will be Binomially distributed. Given a fixed learning algorithm and learning problem, the training error will have a considerably more complicated distribution. We can nonetheless, regard the training error as a fixed random variable which has some cumulative distribution parameterized by many parameters, one of which is the true error rate of the output hypothesis (which is itself a random variable).

How can we construct a confidence interval based upon information from both the training and testing sets? There are several possibilities.

(1) Construct an interval based upon the probability that both lower bounds are violated.

(2) Construct an interval based upon the probability that at most one of the lower bounds is violated.

(3) Are there better, more general techniques?

Technique (1) can be seen visually by graphing training error vs test error and marking the regions that are bounded away.

The essential problem with technique (1) is that the resulting true error bound takes the maximum (minus a small amount) of the bounds based upon both the test set and the training set. Given that we don’t trust either bound to always return tight information, we expect the maximum will not behave well.

Technique (2) can be seen visually in a similar way:

Technique (2) works moderately well. Mathematically, we can calculate the minimum of the two error bounds and add a small amount. This approach is equivalent to taking a union bound. While this approach allows us to combine the bounds, it does not let us achieve an improvement over either which is intuitively possible. Certainly, if we use two test sets, we expect to construct improved confidence intervals.

A better approach may be possible. We would like to construct a rejection region of the following form:

Such a rejection region has two important properties:

(1) If one bound is loose, it does not greatly harm the final true error bound.

(2) The final true error bound can be tighter than either individual true error bound.

Showing that technique (2) works is just an application of the union bound. Given any two bounds on the true error rate, we can apportion \frac{δ}{2} confidence to each bound. Then both bounds will hold with probability δ which implies that the smaller of the two true error bounds holds.

10.2. General Approaches for Combined Bounds

Showing that a more general technique works must start with a discussion of confidence intervals. Fundamentally, a bound can be viewed as a set of outcomes. Let X be space of outcomes, then a bound ϕ ⊆ X is a subset. The probability that this generalized bound is violated is given by:

Pr_{x∼P}(x ∈ ϕ)

Typically, we parameterize ϕ with both P and δ to get:

Pr_{x∼P}(x ∈ ϕ_{P} (δ)) ≤ δ

We can expand the definition of a high probability set to include a randomized high probability set. In particular, let ϕ_{P} (w, δ) satisfy:

∀w : Pr_{x∼P}(x ∈ ϕ_{P} (w, δ)) ≤ δ

Then, statement such as:

Pr_{w∼Q,x∼P}(x ∈ ϕ_{P} (w, δ)) ≤ δ

In fact, we can make a stronger statement. If

(10.2.1)  E_{w∼Q} Pr_{x∼P}(x ∈ ϕ_{P} (w, δ)) ≤ δ

then

(10.2.2)  Pr_{w∼Q,x∼P}(x ∈ ϕ_{P} (w, δ)) ≤ δ

.

Randomized confidence intervals are useful here because we can regard the the draw of the “test” set as constructing a randomized interval for the “training” set. As long as constraint ?? is obeyed, the bound will hold with probability at least δ. A P-value Inversion of the bound will then yield the following theorem:

Lemma 10.2.1. (Exact test and train bound) Let ϕ_{D}(δ) be any bound satisfying Pr_{D^{m}}(z^{m} ∈ ϕ_{D}(δ)) ≤ δ. Let f(z^{m_{test}} ) be any function satisfying: E_{z^{m_{test}} ∼D^{m_{test}}} Pr_{D^{m}}(z^{m} ∈ ϕ_{D}(f(z^{m_{test}} ) ∗ δ)) ≤ δ , then:

Pr_{D^{m+m_{test}}} (z^{m} ∈ ϕ_{D}(f(z^{m_{test}} ) ∗ δ)) ≤ δ

Proof. Linearity of expectation. □

There are many possible choices of the function f(z^{m_{test}}), each of which leads a different combined training and testing bound. Typically, it will be important to invert this bound into a P-value form where we take a worst case over all D just as in section ??.

The functional form of f(z^{m_{test}}) becomes more constrained when we only work with a bound on the test error cumulative distribution rather than the exact distribution.

10.3. Approximations in Combinations

The inexact nature of bounds forces us to impose a monotonic structure on the function f(z^{m_{test}}). For simplicity, we will restrict to functions of the form f(ê_{test}(h)) where ê_{test}(h) is the test error on hypothesis h.

We can consider any bound θ_{D}(δ) as inducing a cumulative distribution on the test set events. This cumulative distribution is not the cumulative distribution of the underlying (Binomial) probability. To construct this distribution, let:

δ(z^{m_{test}}) = inf{δ : ê_{test}(h) ∈ θ_{D}(δ)}

Intuitively, δ(z^{m_{test}}) is the smallest δ such that the test error constructed from z^{m_{test}} is rejected. The value of δ(z^{m_{test}}) varies between 0 and 1 so it is a cumulative distribution over the set of possible error rates. (note, that different z^{m_{test}} are implicity aliased under this technique). Then, the following inequality must hold by the definition of an upper bound:

∀z^{m_{test}} δ(z^{m_{test}}) ≥ Bin(m, m ∗ ê(h), e(h))

Given the upper bound cumulative, δ(z^{m_{test}}), we can look at distributions satisfying:

E_{z^{m_{test}} ∼δ(z^{m_{test}} )} Pr_{D^{m}}(z^{m} ∈ ϕ(f(ê_{test}(h)) ∗ δ)) ≤ δ

If we are guaranteed that f(ê_{test}(h)) decreases monotonically then equation ?? will hold. This leads to our theorem.

Theorem 10.3.1. (Approximate test and train bound) Let ϕ_{D}(δ) be any bound satisfying Pr_{D^{m}}(z^{m} ∈ ϕ_{D}(δ)) ≤ δ. Let f(z^{m_{test}} ) be any monotonic decreasing function satisfying: E_{z^{m_{test}} ∼δ(z^{m_{test}} )} Pr_{D^{m}}(z^{m} ∈ ϕ_{D}(f(ê_{test}(h)) ∗ δ)) ≤ δ , then:

Pr_{D^{m+m_{test}}} (z^{m} ∈ ϕ_{D}(f(ê_{test}(h)) ∗ δ)) ≤ δ

Proof.

E_{z^{m_{test}} ∼δ(z^{m_{test}} )} Pr_{D^{m}}(z^{m} ∈ ϕ_{D}(f(ê_{test}(h)) ∗ δ))
= ∑_{ê_{test}(h)=0}^{1}[δ(z^{m_{test}}) − δ(z^{m_{test}} − \frac{1}{m})] Pr_{D^{m}}(z^{m} ∈ ϕ_{D}(f(ê_{test}(h)) ∗ δ))

Monotonicity of f() implies that as ê_{test}(h) increases, the rejection region, ϕ_{D}(f(ê_{test}(h)) ∗ δ) decreases. Given this, we can show inductively that:

∀k ∈ \{0, ..., m\} ∑_{z^{m_{test}} :ê_{test}(h)=0}^{\frac{k}{m}}[δ(z^{m_{test}})−δ(z^{m_{test}}−\frac{1}{m})] Pr_{D^{m}}(z^{m} ∈ ϕ_{D}(f(ê_{test}(h))∗δ))

≥ ∑_{ê_{test}(h)=0}^{\frac{k}{m}}[Bin(m, mê_{test}(h), e(h))−Bin(m, mê_{test}(h)−1, e(h))] Pr_{D^{m}}(z^{m} ∈ ϕ_{D}(f(ê_{test}(h))∗δ))

which implies

≥ E_{z^{m_{test}} ∼D^{m_{test}}} Pr_{D^{m}}(z^{m} ∈ ϕ_{D}(f(ê_{test}(h)) ∗ δ))

Given this, an application ?? completes the proof. □

The only constraint that we must check in applying a combined training and test set bound is the monotonic constraint. Heuristically, this is satisfied for the pictures of techniques (1)-(3) because the set of excluded events increases monotonically along the x axis as it decreases along the y axis.

An explicit mathematical form for technique (3) can be given by considering the bound-based cumulative distributions, δ(z^{m_{test}}(h)) and θ(z^{m_{train}}). In particular, we can define the rejection region to be {z^{m_{test}}, z^{m_{train}} : δ(z^{m_{test}})θ(z^{m_{train}}) ≤ t(δ)} where t(δ) satisfies Pr_{z^{m_{test}} ∼δ(z^{m_{test}} ),z^{m_{train}} ∼θ(z^{m_{train}} )}(δ(z^{m_{test}})θ(z^{m_{train}}) ≤ t) ≤ δ. The monotonic constraint is satisfied by this construction because δ(z^{m_{test}}) is implicitly monotonic decreasing with θ(z^{m_{train}}) given a constant t. We will use technique (3) for combining training and test sets in the coming experiments.

Part 3

Experimental Results

CHAPTER 11 Decision Trees

Are Sample Complexity bounds quantitatively tight? The real challenge lies with continuous valued classifiers and will be addressed in the next chapter. Before worrying about continuous valued classifiers it is worthwhile to consider performance on a discrete valued classifier. To do this, we will apply a (discrete valued) decision tree to learning problems in the UCI machine learning database.

The results of this analysis are interesting - competitive bounds are achieved in some cases and the best sample complexity bounds are never more than an order of magnitude worse.

Practitioners of applied machine learning currently use a different technique for free parameter optimization: holdout sets. The simplest form of this technique is to separate the examples into a “training set” and “testing set”. The training set is used by the learning algorithm to output a hypothesis. The hypothesis is then tested on the test set to generate an estimate of the future error rate. The principal advantage of the holdout technique is the (simple theoretical) guarantee that with high probability the estimate will not be much higher or lower than the true error rate. The principal disadvantage of this approach is that not all of the examples are used for training. This is often not a significant problem but it can be important for certain learning algorithms and problems which exhibit phase transitions. Near a phase transition, extra examples can exponentially decrease the expected error rate of the output hypothesis. More sophisticated techniques such as Leave One Out Cross Validation, K-fold Cross Validation, and Progressive Validation [33] attempt to remove this disadvantage. Each of these alternative holdout techniques cannot fully remove the disadvantage and some of them threaten the advantage (a tight bound on the true error). In addition, a new disadvantage is introduced: significantly more computation is required.

The holdout technique is fundamentally unsatisfactory for one important reason: The holdout sets cannot be used multiple times without abrogating the theoretical guarantees on the tightness of the holdout evaluation. In particular, this implies that we can not design a learning algorithm which makes multiple internal decisions based upon the result of evaluating a future error bound without allocating most of our examples to holdout sets leaving very few for training. This drawback does not exist for the sample complexity bounds.

We will compare the following bounds on a decision tree:

(1) The discrete hypothesis bound 3.1.1.

(2) The Occam’s Razor bound 3.5.1 with the Hoeffding Binomial tail bound. This bound might be thought of as an old “state of the art” bound.

(3) The Microchoice bound 4.2.1. In addition, we will prune the decision tree according to the microchoice bound.

(4) The Shell bound 7.1.2 and the Sampled Shell bound 7.2.1.

(5) A simple holdout bound ?? using a holdout set of size 20%.

(6) A combined training and testing bound using the holdout bound ?? and microchoice bound 4.2.1.

(7) A combined training and testing bound using the holdout bound ?? and the (stochastic) shell bound (7.2.1) 7.1.2.

11.1. Bound Preliminaries

When discussing holdout sets it is necessary to split up the set of examples into training and test sets: (x, y)^{m_{train}} and (x, y)^{m_{test}} where m_{train} + m_{test} = m.

11.1.1. Structural Risk Minimization. A naive application of the Shell bound would not prove useful because the size of the hypothesis space can be extremely large. Instead, we must combine it with Structural Risk Minimization (SRM) to achieve useful results. In SRM, you start with a bound for each hypothesis space, H_{i}, in a sequence of nested hypothesis spaces, H_{1} ⊆ ⋯ ⊆ H_{n}. These bounds on individual hypothesis spaces are combined to create a bound which applies for all hypothesis spaces. The particular nesting we use is “H_{i} = all decision trees with i or fewer internal nodes”.

Since the size of the decision tree hypothesis spaces increases exponentially with the index i , we choose p_{i} = \frac{1}{2^{i}}. This choice has the property that \frac{1}{p_{i}} is always small in comparison to |H_{i}|, implying that the SRM bound is never much worse than a simple application of the underlying bound.

11.2. The Decision Tree Learning Algorithm

The bounds are applied to the results of decision trees learned on UCI database problems. The decision tree algorithm is a variant of ID3 which works in two phases: a tree of minimum empirical error is discovered and then pruned with a criteria which arises naturally from the Microchoice bound. The first phase works in a recursive fashion by maximizing the information gain across all splitting criteria. It is assumed that each example consists of n features each of which takes a small number of discrete values. The splitting criteria at each internal node are of the form “feature f has value v” which implies that a binary tree is produced. Leaves of the tree are labeled with the label most common amongst the examples in the training set which reach the leaf. The pruning pass prunes according to the criterion: minimize the upper bound on true error implied by the Microchoice bound. Pruning starts with the internal nodes closest to the leaves and proceeds up the tree toward the root node. This pruning criteria falls in the category of pessimistic criteria [?]. The implementation has been somewhat optimized by careful caching of information. The examples are tokenized into integers for fast comparison and analysis of splitting criteria at each node only loops over the examples once. Sub-calculations of the Microchoice bound are cached for use in pruning.

11.2.1. Pruning. The proof of the Microchoice bound works by assigning a uniform weight to each choice in a choice space. Since the choice space of every node includes the choice of making a leaf, the Microchoice bound incidentally also proves a tighter bound for every pruning of the output tree. We choose to prune when pruning reduces the upper bound on the generalization error. We prune starting with internal nodes nearest to the leaves and working toward the root node. As will be shown by the experiments, other bounds are sometimes tighter than the Microchoice bound. This implies that the Microchoice bound is not always the optimal pruning criteria. However, the Microchoice bound is fast to calculate so it is used here. In practice, it may be desirable to prune according to the criteria “minimize αê_{S}(h) + (1 − α)be(h)” where ē(h) is some high probability upper bound on the true error e_{D}(h). We use α = 0 with the bound produced by the Microchoice bound.

11.2.2. Uniform Sampling from Decision Trees. To use the Sampling Shell bound with Structural Risk Minimization, we need to sample uniformly from the set of all decision trees of a particular size. The number of binary structures of size i is the ith Catalan number, C_{i} = \frac{1}{i+1} \binom{2i}{i} . This implies there are C_{i} different tree structures with i internal nodes. Sampling uniformly from the set of all tree structures with i internal nodes can then be done with a recursive process. For a particular node in a tree, assume that j internal nodes need to be created. If j = 0, we have a leaf. For j ≥ 1, we can construct a distribution over the number of nodes that are left branches of the tree by calculating C_{0}, …, C_{j−1} and normalizing. Draw from this distribution to get j_{l}: the number of internal nodes in the left sub-tree. Let j_{r} = j − j_{l} − 1 be the number of internal nodes in the right sub-tree and recurse. This construction is not yet a decision tree because we have not placed tests in each node. We make another uniform pick from the set of available tests at a particular node. We allow only tests on features with at least two different feature values remaining after tests by parent nodes. This approach is not quite uniform in the set of decision trees because when there are i internal nodes and F < i Boolean features, some trees have a depth greater than F which is not possible in a binary decision tree. In practice this does not make a difference because the number of decision trees with a too-large depth is an exponentially small fraction of the total number of trees. When running the algorithm we did not ever encounter a sampled binary tree structure with depth greater than F. Leaves have a label picked uniformly from the set of labels. A particular label implies some empirical error count amongst all examples which reach the leaf. By adding the leaf error rates together we find the empirical error of a random hypothesis from the hypothesis set.

11.2.3. Fast Sampling. In order for the Sampling Shell bound to be a significant improvement we need the number of samples l to satisfy l = O(m). This is not tractable using the above sampling technique so we “cheated”. At some critical sub-tree size s we switch from sampling to exact enumeration. (The exact value of s is discussed later.) Exact enumeration produces a multiset with elements corresponding to an error rate ê_{i} in the sub-tree and a count c_{i} associated with each element. We recurse up the tree with the entire error multiset rather than just one error. At an internal node we have a multiset of errors from the left child and from the right child. The multiset of errors at an internal node is the cross product of all errors in the left child and right child because the choice of left sub-tree is independent of the choice of right sub-tree. Let S_{l} be the multiset of errors in the left child and S_{r} be the multiset of errors in the right child. The multiset of errors for the internal node is then given by:

{ê_{i} + ê_{j}, c_{i} ∗ c_{j} : ê_{i}, c_{i} ∈ S_{l}, ê_{j}, c_{j} ∈ S_{r}}

This is a graph of the confidence intervals implied by the holdout bound (??). In this figure (and all others) we use δ = 0.1 bounds for each tail so the confidence intervals hold with probability 0.8 over the data set. Note that an estimate of the size of a the holdout set can be inferred by the width of the confidence interval.

The multiset produced is passed recursively to the parent and each element of the set of errors at the root node is considered an “independent” sample for the purposes of applying the Sampling Shell bound.

The power of this techniques comes from the fact that the set of hypotheses sampled is exponential in the number of leaves. However, we never need to represent the exponentially many different hypotheses explicitly because there are only m+1 possible empirical errors. Using multisets, we achieve sampling time similar to the simple uniform sampling approach of the previous section but with exponentially more (dependent) samples. The drawback to this approach is that the samples are no longer independent so it is not “fair” to use them as independent samples in a theoretical sense. We pretend each fast-sample is independent anyway and apply the Sampling Shell bound. It is worth noting that the samples returned by this technique are not biased and sometimes have lower variance than independent samples.

The choice of the critical subtree size s is done in an anytime fashion. The time t required for learning the decision tree is first calculated. Then, starting with a size of s = 0, we sample from the decision tree, increasing the size by one after each sample. When more than t/10 time has been spent on sampling, we cease incrementing s. If s is the size of the tree, then we stop and apply the exact Shell bound. Otherwise, we decrement s and sample repeatedly until as much time has been spent on sampling as was spent on learning the decision tree. The union of all the multisets is returned and the Sampling Shell bound is used.

Figure 11.3.1. This is a graph of the confidence intervals implied by the holdout bound (??) and the approximate confidence intervals implied using the common two sigma rule motivated by asymptotic normality. For this graph only, the upper and lower bounds of the holdout bound have a maximum 2.5% failure rate (each), rather than a 10% failure rate. This is done in order to make the results more comparable with the 2-sigma approach. The holdout bound is better behaved in the sense that the confidence interval is confined to the interval [0, 1] and it is never overoptimistic.

11.3. Results & Discussion

Our goal is to bound the true error of the hypothesis output by our learning algorithm. To do this, we apply sample complexity bounds to the results of the decision tree on UCI database problems. The problems chosen from the UCI database are those for which a discrete decision tree is applicable. All bounds are calculated with a probability of failure of δ = 0.1. As mentioned in the introduction, there are two approaches. The commonly used approach is to first divide the example set into two sets, m_{test} and m_{train}. Then, train using the examples in m_{train} and test on the m_{test} examples. We chose an 80/20 split of the data into m_{train}/m_{test}. We will compare each bound with the simple holdout approach because this is the commonly used baseline.

11.3.1. Comparison with a standard confidence interval approach. When attempting to calculate a confidence interval on the true error rate given the holdout set, many people follow a standard statistical prescription:

(1) Calculate the empirical mean μ̂ = ê_{S_{test}}(h) = \frac{1}{m} ∑_{i=1}^{m} I(h(x_{i}) ≠ y_{i}).

(2) Calculate the empirical variance σ̂^{2} = \frac{1}{m−1} ∑_{i=1}^{m}(I(h(x_{i}) ≠ y_{i}) − μ̂)^{2}.