PAC-Bayes & Margins

John Langford IBM Research

     Email: jcl@cs.cmu.edu

John Shawe-Taylor Royal Holloway, University of London

                                    Email: jst@cs.rhul.ac.uk

Abstract

We show two related things:

(1) Given a classifier which consists of a weighted sum of features with a large margin, we can construct a stochastic classifier with negligibly larger training error rate. The stochastic classifier has a future error rate bound that depends on the margin distribution and is independent of the size of the base hypothesis class.

(2) A new true error bound for classifiers with a margin which is simpler, functionally tighter, and more data-dependent than all previous bounds.

1 Introduction

PAC-Bayes bounds [8] (improved in [7] and again in [10]) are interesting for constructing bounds on future error rate in classification given only an assumption that examples are drawn independently from some (unknown) distribution. One drawback of PAC-Bayes bounds is that they only apply strongly to stochastic classifiers— classifiers which make randomized predictions. Most learning algorithms do not produce stochastic predictors, so the PAC-Bayes bound can only be applied to classifiers altered to form a stochastic classifier. This alteration can be done either by a sensitivity analysis [5] or by using the Bayesian posterior [10] directly.

Although stochastic classifiers are rare in practice, voting classifiers are quite common. These include “Bayes optimal” classifiers, Maximum Entropy classifiers [4], Adaboost [9], and others which has motivated analysis of true error bounds specialized to voting classifiers. In particular, we know that when the vote is decided by a margin of at least γ on the training set, the true error rate is more tightly bound than might be naively expected. Unfortunately, these bounds are still unsatisfying for practical use because they often give the meaningless “future error rate is less than 1” predictions.

Here we analyze the connection between PAC-Bayes and margin bounds. In particular, we show that the “build a stochastic classifier” approach [5] to constructing a non-vacuous PAC-Bayes bound is always possible given that some margin γ holds for the training set. This also shows that PAC-Bayes bounds are capable of capturing the low effective “sample complexity” which exists when a large margin classifier is used.

An alteration to the PAC-Bayes result proves a new bound for margins which is a shorter argument and much tighter than previous margin bounds.

There are two mathematical flavors of margin bound dependent upon the weights w_{i} of the vote and the features x_{i} that the vote is taken over.

1. Those ([12], [1]) with a bound on ∑_{i} w_{i}^{2} and ∑_{i} x_{i}^{2} (“l_{2}/l_{2}” bounds).

2. Those ([11], [6]) with a bound on ∑_{i} w_{i} and max_{i} x_{i} (“l_{1}/l_{∞}” bounds).

The results here are of the “l_{2}/l_{2}” form. We improve on Shawe-Taylor et al. [12] and Bartlett [1] by a log(m)^{2} sample complexity factor and much tighter constants (1000 or unstated versus 9 or 18 as suggested by Section 2.2). In addition, the bound here covers margin errors without weakening the error-free case.

Herbrich and Graepel [3] moved significantly towards the approach adopted in our paper, but the methodology adopted meant that their result does not scale well to high dimensional feature spaces as the bound here (and earlier results) do.

The layout of our paper is simple - we first show how to construct a stochastic classifier with a good true error bound given a margin, and then construct a margin bound.

2 Margin Implies PAC-Bayes Bound

2.1 Notation and theorem

Consider a feature space X which may be used to make predictions about the value in an output space Y = {−1, +1}. We use the notation x = (x_{1}, …, x_{N}) to denote an N dimensional vector. Let the vote of a voting classifier be given by:

v_{w}(x) = wx = ∑_{i} w_{i}x_{i}.

The classifier is given by c(x) = sign (v_{w}(x)). The number of “margin violations” or “margin errors” at γ is given by:

ê_{γ}(c) = Pr_{(x,y)∼U(S)}(yv_{w}(x) < γ),

where U(S) is the uniform distribution over the sample set S.

For convenience, we assume v_{x}(x) ≤ 1 and v_{w}(w) ≤ 1. Without this assumption, our results scale as \sqrt{v_{x}(x)}\sqrt{v_{w}(w)}/γ rather than 1/γ.

Any margin bound applies to a vector w in N dimensional space. For every example, we can decompose the example into a portion which is parallel to w and a portion which is perpendicular to w.

x_{⊤} = x − \frac{v_{w}(x)}{∥w∥^{2}}w x_{∥} = x − x_{⊤}

The argument is simple: we exhibit a “prior” over the weight space and a “posterior” over the weight space with an analytical form for the KL-divergence. The stochastic classifier defined by the posterior has a slightly larger empirical error and a small true error bound.

For the next theorem, let F̄(x) = 1 − ∫_{−∞}^{x} \frac{1}{\sqrt{2π}} e^{−x^{2}/2}dx be the tail probability of a Gaussian with mean 0 and variance 1. Also let

e_{Q(w,γ,ϵ)} = Pr_{(x,y)∼D,h∼Q(w,γ,ϵ)}(h(x) ≠ y)

be the true error rate of a stochastic classifier with distribution Q(ϵ, w, γ) dependent on a free parameter ϵ, the weights w of an averaging classifier, and a margin γ.

Theorem 2.1 There exists a function Q mapping a weight vector w, margin γ, and value ϵ > 0 to a distribution Q(w, γ, ϵ) such that

Pr_{S∼D^{m}} (∀w, γ, ϵ : KL(ê_{γ}(c) + ϵ∥e_{Q(w,γ,ϵ)}) ≤ \frac{ln _{\frac{1}{F̄( \frac{F̄^{−1}(ϵ)}{γ} )}} + ln \frac{m+1}{δ}}{m} ) ≥ 1 − δ

where KL(q∥p) = q ln \frac{q}{p} + (1 − q) ln \frac{1−q}{1−p} = the Kullback-Leibler divergence between two coins of bias q < p.

2.2 Discussion

Theorem 2.1 shows that when a margin exists it is always possible to find a “posterior” distribution (in the style of [5]) which introduces only a small amount of additional training error rate. The true error bound for this stochastization of the large-margin classifier is not dependent on the dimensionality except via the margin.

Since the Gaussian tail decreases exponentially, the value of F̄^{−1}(ϵ) is not very large for any reasonable value of ϵ. In particular, at F̄(3), we have ϵ ≤ 0.01. Thus, for the purpose of understanding, we can replace F̄^{−1}(ϵ) with 3 and consider ϵ ≃ 0. One useful approximation for F̄(x) with large x is:

F̄(x) ≃ \frac{e^{−x^{2}/2}}{\sqrt{2π}} (1/x)

If there are no margin errors ê_{γ}(c) = 0, then these approximations, yield the approximate bound:

Pr_{S∼D^{m}} (e_{Q(w,γ,0)} ≤ \frac{\frac{9}{2γ^{2}} + ln \frac{3\sqrt{2π}}{γ} + ln \frac{m+1}{δ}}{m} ) ≥ 1 − δ

In particular, for large m the true error is approximately bounded by \frac{9}{2γ^{2}m}.

As an example, if γ = 0.25, the bound is less than 1 around m = 100 examples and less than 0.5 around m = 200 examples.

Later we show (see Lemmas 4.1 and 4.2 or Theorem 4.3) that the generalisation error of the original averaging classifier is only a factor 2 or 4 larger than that of the stochastic classifiers considered here. Hence, the bounds of Theorems 2.1 and 3.1 also give bounds on the averaging classifiers w.

This theorem is robust in the presence of noise and margin errors. Since the PAC-Bayes bound works for any “posterior” Q, we are free to choose Q dependent upon the data in any way. In practice, it may be desirable to follow an approach similar to [5] and allow the data to determine the “right” posterior Q. Using the data rather than the margin γ allows the bound to take into account a fortuitous data distribution and robust behavior in the presence of a “soft margin” (a margin with errors). This is developed (along with a full proof) in the next section.

3 Main Full Result

We now present the main result. Here we state a bound which can take into account the distribution of the training set. Theorem 2.1 is a simple consequence of this result. This theorem demonstrates the flexibility of the technique since it incorporates significantly more data-dependent information into the bound calculation. When applying the bound one would choose μ to make the inequality (1) an equality. Hence, any choice of μ determines ϵ and hence the overall bound. We then have the freedom to choose μ to optimise the bound.

As noted earlier, given a weight vector w, any particular feature vector x decomposes into a portion x_{∥} which is parallel to w and a portion x_{⊤} which is perpendicular to w. Hence, we can write x = x_{∥}e_{∥} + x_{⊤}e_{⊤}, where e_{∥} is a unit vector in the direction of w and e_{⊤} is a unit vector in the direction of x_{⊤}. Note that we may have yx_{∥} < 0, if x is misclassified by w.

Theorem 3.1 For all averaging classifiers c with normalized weights w and for all ϵ > 0 stochastic error rates, If we choose μ > 0 such that

E_{x,y∼S}F̄ (\frac{yx_{∥}}{x_{⊤}} μ) = ϵ  (1)

then there exists a posterior distribution Q(w, μ, ϵ) such that

Pr_{S∼D^{m}} (∀ϵ, w, μ : KL(ϵ∥e_{Q(w,μ,ϵ)}) ≤ \frac{ln \frac{1}{F̄(μ)} + ln \frac{m+1}{δ}}{m} ) ≥ 1 − δ

where KL(q∥p) = q ln \frac{q}{p} + (1 − q) ln \frac{1−q}{1−p} = the Kullback-Leibler divergence between two coins of bias q < p.

Proof. The proof uses the PAC-Bayes bound, which states that for all prior distributions P,

Pr_{S∼D^{m}} (∀Q : KL(ê_{Q}∥e_{Q}) ≤ \frac{KL(Q||P) + ln \frac{m+1}{δ}}{m} ) ≥ 1 − δ

We choose P = N(0, I), an isotropic Gaussian^{1}.

A choice of the “posterior” Q completes the proof. The Q we choose depends upon the direction w, the margin γ, and the stochastic error ϵ. In particular, Q equals P in every direction perpendicular to w, and a rectified Gaussian tail in the w direction^{2}. The distribution of a rectified Gaussian tail is given by R(μ) = 0 for x < μ and R(μ) = \frac{1}{F̄(μ)\sqrt{2π}} e^{−x^{2}/2} for x ≥ μ.

The chain rule for relative entropy (Theorem 2.5.3 of [2]) and the independence of draws in each dimension implies that:

KL(Q∥P) = KL(Q_{∥}∥P_{∥}) + KL(Q_{⊤}||P_{⊤})
= KL(R(μ)∥N(0, 1)) + KL(P_{⊤}∥P_{⊤})
= KL(R(μ)∥N(0, 1)) + 0
= ∫_{μ}^{∞} ln \frac{1}{F̄(μ)}R(x)dx

= ln \frac{1}{F̄(μ)}

1Later, the fact that an isotropic Gaussian has the same representation in all rotations of the coordinate sytem will be useful.

2Note that we use the invariance under rotation of N(0, I) here to line up one dimension with w.

Thus, our choice of posterior implies the theorem if the empirical error rate is ê_{Q(w,x,ϵ)} ≤ E_{x,y∼S}F̄ (\frac{x_{∥}}{x_{⊤}} μ) ≤ ϵ which we show next.

Given a point x, our choice of posterior implies that we can decompose the stochastic weight vector, ŵ = ŵ_{∥}e_{∥} +ŵ_{⊤}e_{⊤} +w̃, where e_{∥} is parallel to w, e_{⊤} is parallel to x_{⊤} and w̃ is a residual vector perpendicular to both. By our definition of the stochastic generation ŵ_{∥} ∼ R(μ) and ŵ_{⊤} ∼ N(0, 1). To avoid an error, we must have:

y = sign(vŵ(x))
= sign(ŵ_{∥}x_{∥} + ŵ_{⊤}x_{⊤}).

Then, since ŵ_{∥} ≥ μ, no error occurs if:

y(μx_{∥} + ŵ_{⊤}x_{⊤}) > 0

Since ŵ_{⊤} is drawn from N(0, 1) the probability of this event is:

Pr (y(μx_{∥} + ŵ_{⊤}x_{⊤}) > 0) ≥ 1 − F̄ (\frac{yx_{∥}}{x_{⊤}} μ)

And so, the empirical error rate of the stochastic classifier is bounded by:

ê_{Q} ≤ E_{x,y∼S}F̄ (\frac{yx_{∥}}{x_{⊤}} μ) = ϵ

as required.

3.1 Proof of Theorem 2.1

Proof. (sketch) The theorem follows from a relaxation of Theorem 3.1. In particular, we treat every example with a margin less than γ as an error and use the bounds ∥x_{⊤}∥ ≤ 1 and ∥x_{∥}∥ ≥ γ.

3.2 Further results

Several aspects of the Theorem 3.1 appear arbitrary, but they are not. In particular, the choice of “prior” is not that arbitrary as the following lemma indicates.

Lemma 3.2 The set of P satisfying ∃P_{∥∥} : P (x) = P_{∥∥}(∥x∥^{2}) (rotational invariance) and P (x) = ∏_{i=1}^{N} p_{i}(x_{i}) (independence of each dimension) is N(0, λI) for λ > 0.

Proof. Rotational invariance together with the dimension independence imply that for all i, j, x : p_{i}(x) = p_{j}(x) which implies that:

P (x) = ∏_{i=1}^{N} p(x_{i})

for some function p(·). Applying rotational invariance, we have that:

P (x) = P_{∥∥}(∥x∥^{2}) = ∏_{i=1}^{N} p(x_{i})

This implies:

log P_{∥∥} (∑_{i=1}^{N} x_{i}^{2}) = ∑_{i=1}^{N} log p(x_{i}).

Taking the derivative of this equation with respect to x_{i} gives

\frac{P′_{∥∥}(∥x∥^{2})2x_{i}}{P_{∥∥}(∥x∥^{2})} = \frac{p′(x_{i})}{p(x_{i})}.

Since this holds for all values of x we must have

P_{∥∥}(t) = λP′_{∥∥}(t)

for some constant λ, or P_{∥∥}(t) = C exp(λt), for some constant C. Hence, P (x) = C exp(λ∥x∥^{2}), as required.

The constant λ in the previous lemma is a free parameter. However, the results do not depend upon the precise value of λ so we choose 1 for simplicity. Some freedom in the choice of the “posterior” Q does exist and the results are dependent on this choice. A rectified gaussian appears simplest.

4 Margin Implies Margin Bound

There are two methods for constructing a margin bound for the original averaging classifier. The first method is simplest while the second is sometimes significantly tighter.

4.1 Simple Margin Bound

First we note a trivial bound arising from a folk theorem and the relationship to our result.

Lemma 4.1 (Simple Averaging bound) For any stochastic classifier with distribution Q and true error rate e_{Q}, the averaging classifier,

c_{Q}(x) = sign (∫_{H} h(x)dQ(h))

has true error rate:

e(c_{Q}) ≤ 2e_{Q}

Proof. For every example (x, y), every time the averaging classifier errs, the probability of the stochastic classifier erring must be at least 1/2.

This result is interesting and of practical use when the empirical error rate of the original averaging classifier is low. Furthermore, we can prove that c_{Q}(x) is the original averaging classifier.

Lemma 4.2 For Q = Q(w, γ, ϵ) derived according to Theorems 2.1 and 3.1 and c_{Q}(x) as in lemma 4.1:

c_{Q}(x) = sign (v_{w}(x))

Proof. For every x this equation holds because of two simple facts:

1. For any ŵ that classifies an input x differently from the averaging classifier, there is a unique equiprobable paired weight vector that agrees with the averaging classifier.

2. If v_{w}(x) ≠ 0, then there exists a nonzero measure of classifier pairs which always agrees with the averaging classifier.

Condition (1) is met by reversing the sign of ŵ_{⊤} and noting that either the original random vector or the reversed random vector must agree with the averaging classifier.

Condition (2) is met by the randomly drawn classifier ŵ = λw and nearby classifiers for any λ > 0. Since the example is not on the hyperplane, there exists some small sphere of paired classifiers (in the sense of condition (1)). This sphere has a positive measure.

The simple averaging bound is elegant, but it breaks down when the empirical error is large because:

e(c) ≤ 2e_{Q} = 2(ê_{Q} + Δ_{m}) ≃ 2ê_{γ}(c) + 2Δ_{m}

where ê_{Q} is the empirical error rate of a stochastic classifier and Δ_{m} goes to zero as m → ∞. Next, we construct a bound of the form e(c_{Q}) ≤ ê_{γ}(c) + Δ′_{m} where Δ′_{m} > Δ_{m} but ê_{γ}(c) ≤ 2ê_{γ}(c).

4.2 A (Sometimes) Tighter Bound

By altering our choice of μ and our notion of “error” we can construct a bound which holds without randomization. In particular, we have the following theorem:

Theorem 4.3 For all averaging classifiers c with normalized weights w for all ϵ > 0 “extra” error rates and γ > 0 margins:

Pr_{S∼D^{m}} (∀ϵ, w, γ : KL(ê_{γ}(c) + ϵ∥e(c) − ϵ) ≤ \frac{ln _{\frac{1}{F̄( \frac{2F̄^{−1}(ϵ)}{γ} )}} + 2 ln \frac{m+1}{δ}}{m} ) ≥ 1 − δ

where KL(q∥p) = q ln \frac{q}{p} + (1 − q) ln \frac{1−q}{1−p} = the Kullback-Leibler divergence between two coins of bias q < p.

The proof of this statement is strongly related to the proof given in [11] but noticeably simpler. It is also very related to the proof of theorem 2.1.

Proof. (sketch) Instead of choosing ŵ_{∥} so that the empirical error rate is increased by ϵ, we instead choose ŵ_{∥} so that the number of margin violations at margin \frac{γ}{2} is increased by at most ϵ. This can be done by drawing from a distribution such as

ŵ_{∥} ∼ R (\frac{2F̄^{−1}(ϵ)}{γ})

Applying the PAC-Bayes bound to this we reach a bound on the number of margin violations at \frac{γ}{2} for the true distribution. In particular, we have:

Pr_{S∼D^{m}} (KL (ê_{γ}(c) + ϵ∥e_{Q, \frac{γ}{2}} ) ≤ \frac{ln _{\frac{1}{F̄( \frac{2F̄^{−1}(ϵ)}{γ} )}} + ln \frac{m+1}{δ}}{m} ) ≥ 1 − δ

The application is tricky because the bound does not hold uniformly for all γ.^{3} Instead we can discretize γ at scale 1/m and apply a union bound to get δ → δ/m+1.

For any fixed example, (x, y) with probability 1 − δ, we know that with probability at least 1 − e_{Q, \frac{γ}{2}} , the example has a margin of at least \frac{γ}{2} . Since the example has a margin of at least \frac{γ}{2} and our randomization doesn’t change the margin by more than \frac{γ}{2} with probability 1 − ϵ, the averaging classifier almost always predicts in the same way as the stochastic classifier implying the theorem.

3Thanks to David McAllester for pointing this out.

4.3 Discussion & Open Problems

The bound we have obtained here is considerably tighter than previous bounds for averaging classifiers—in fact it is tight enough to consider applying to real learning problems and using the results in decision making.

Can this argument be improved? The simple averaging bound (lemma 4.1) and the margin bound (theorem 4.3) each have a regime in which they dominate. We expect that there exists some natural theorem which does well in both regimes simultaneously.

In order to verify that the margin bound is as tight as possible, it would also be instructive to study lower bounds.

4.4 Acknowledgements

Many thanks to David McAllester for critical reading and comments.

References

[1] P. L. Bartlett, “The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network,” IEEE Transactions on Information Theory, vol. 44, no. 2, pp. 525–536, 1998.

[2] Thomas Cover and Joy Thomas, “Elements of Information Theory” Wiley, New York 1991.

[3] Ralf Herbrich and Thore Graepel, A PAC-Bayesian Margin Bound for Linear Classifiers: Why SVMs work. In Advances in Neural Information Processing Systems 13, pages 224-230. 2001.

[4] T. Jaakkola, M. Meila, T. Jebara, “Maximum Entropy D iscrimination\char” NIPS 1999.

[5] John Langford and Rich Caruana, (Not) Bounding the True Error NIPS2001.

[6] John Langford, Matthias Seeger, and Nimrod Megiddo, “An Improved Predictive Accuracy Bound for Averaging Classifiers” ICML2001.

[7] John Langford and Matthias Seeger, “Bounds for Averaging Classifiers.” CMU tech report, CMU-CS-01-102, 2001.

[8] David McAllester, “PAC-Bayesian Model Averaging” COLT 1999.

[9] Yoav Freund and Robert E. Schapire, “A Decision Theoretic Generalization of On-line Learning and an Application to Boosting” Eurocolt 1995.

[10] Matthias Seeger, “PAC-Bayesian Generalization Error Bounds for Gaussian Processes”, Tech Report, Division of Informatics report EDI-INF-RR-0094. http://www.dai.ed.ac.uk/homes/seeger/papers/gpmcall-tr.ps.gz

[11] Robert E. Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lee, “Boosting the Margin: A new explanation for the effectiveness of voting methods” The Annals of Statistics, 26(5):1651-1686, 1998.

[12] J. Shawe-Taylor, P. L. Bartlett, R. C. Williamson, and M. Anthony. Structural risk minimization over data-dependent hierarchies. IEEE Transactions on Information Theory, 44(5):1926–1940, 1998.