\documentclass{article}
\usepackage{nips2002e}
\def\comment#1{}

%\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma} %%Delete [thm] to re-start numbering
\newtheorem{cor}[thm]{Corollary} %%Delete [thm] to re-start numbering

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
%\usepackage[T1]{fontenc}
\usepackage{amssymb}


\newenvironment{proof}[1][Proof]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newcommand{\bfx}{\mathbf{x}}
\newcommand{\bfw}{\mathbf{w}}
\newcommand{\bfe}{\mathbf{e}}
\newcommand{\<}{\langle}
\renewcommand{\>}{\rangle}
\newcommand{\KL}{\mathrm{KL}}
\renewcommand{\Re}{\mathbb{R}}
\newcommand{\PC}{\mathrm{PC}}
\newcommand{\sign}{\mathrm{sign}}

\begin{document}

\title{PAC-Bayes \& Margins}

\author{John Langford \\
IBM Research \\
Email: {\tt jcl@cs.cmu.edu} \And John Shawe-Taylor\\
Royal Holloway, University of London\\
Email: {\tt jst@cs.rhul.ac.uk}}

\maketitle

\begin{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.
\end{abstract}

\section{Introduction}
{\renewcommand{\baselinestretch}{1.0}}

PAC-Bayes bounds \cite{PB} (improved in \cite{averaging_tech} and
again in \cite{Seeger}) 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
\emph{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 \cite{SNN} or by using the Bayesian
posterior \cite{Seeger} directly.

Although stochastic classifiers are rare in practice, voting
classifiers are quite common. These include ``Bayes optimal''
classifiers, Maximum Entropy classifiers \cite{ME}, Adaboost
\cite{Boosting}, 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 \( \gamma \) 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 \cite{SNN} to constructing a non-vacuous PAC-Bayes bound is
always possible given that some margin \( \gamma \) 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.
\begin{enumerate}
\item Those (\cite{ShaBarWilAnt98}, \cite{Bartlett98}) with a bound on
$\sum_i w_i^2$ and $\sum_i x_i^2$ (``$l_2/l_2$'' bounds).
\item Those (\cite{Margin}, \cite{averaging_icml}) with a bound on
$\sum_i w_i$ and $\max_i x_i$ (``$l_1/l_\infty$'' bounds).
\end{enumerate}
The results here are of the ``$l_2/l_2$'' form.  We improve on
Shawe-Taylor et al.~\cite{ShaBarWilAnt98} and
Bartlett~\cite{Bartlett98} by a $\log(m)^2$ sample complexity factor
and much tighter constants (1000 or unstated versus 9 or 18 as
suggested by Section~\ref{discussion1}).  In addition, the bound here
covers margin errors without weakening the error-free case.

Herbrich and Graepel \cite{HerbGraep} 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.

\section{Margin Implies PAC-Bayes Bound}


\subsection{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 \( \bfx =(\bfx _{1},\ldots ,\bfx _{N}) \) to denote an \( N
\) dimensional vector.  Let the vote of a voting classifier be given
by:
\[ v_\bfw(\bfx) = \bfw \bfx = \sum _{i}\bfw _{i}\bfx_{i}. \]
The classifier is given by \( c(\bfx)=\textrm{sign}\left( v_\bfw(\bfx)
\right) \).  The number of ``margin violations'' or ``margin errors''
at $\gamma$ is given by:
\[ \hat{e}_{\gamma}(c) = \Pr_{(\bfx,y) \sim U(S)} ( yv_\bfw(\bfx) < \gamma ), \] where 
$U(S)$ is the uniform distribution over the sample set $S$.

For convenience, we assume \( v_\bfx(\bfx) \leq 1 \) and \(
v_\bfw(\bfw) \leq 1 \).  Without this assumption, our results scale as
\( \sqrt{v_\bfx(\bfx)} \sqrt{v_\bfw(\bfw)} / \gamma
\) rather than \(1 / \gamma \).

Any margin bound applies to a vector \( \bfw  \) in \( N \) dimensional space.
For every example, we can decompose the example into a portion which is parallel
to \( \bfw  \) and a portion which is perpendicular to \( \bfw  \). 
\begin{eqnarray*}
\bfx _{\top }  =  \bfx -\frac{v_\bfw (\bfx)}{\Vert \bfw \Vert^2 }\bfw 
\mbox{\quad}
\bfx _{\Vert }  =  \bfx -\bfx _{\top }
\end{eqnarray*}


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 $\bar{F}(x) = 1 - \int_{-\infty}^x
\frac{1}{\sqrt{2\pi}} e^{- x^2/2} dx $ be the tail probability of a
Gaussian with mean $0$ and variance $1$.  Also let
\[e_{Q(\bfw,\gamma,\epsilon)} = \Pr_{(\bfx,y) \sim D, h \sim Q(\bfw,\gamma,\epsilon)} (h(\bfx)\neq y) \] be the
true error rate of a stochastic classifier with distribution
$Q(\epsilon,\bfw,\gamma)$ dependent on a free parameter $\epsilon$,
the weights $\bfw$ of an averaging classifier, and a margin $\gamma$.

\begin{thm}
\label{thm-pb-from-margin}There exists a function $Q$ mapping a weight
vector $\bfw$, margin $\gamma$, and value $\epsilon > 0$ to a
distribution $Q(\bfw, \gamma, \epsilon)$ such that
\[
\Pr _{S\sim D^{m}}\left( \forall \bfw,\gamma,\epsilon:\,\,\,
\KL (\hat{e}_{\gamma}(c)+\epsilon \Vert e_{Q(\bfw,\gamma,\epsilon)}) 
\leq \frac{ \ln \frac{1}{\bar{F}\left(\frac{\bar{F}^{-1}(\epsilon)}{\gamma}\right)} 
           +\ln\frac{m+1}{\delta }}{m}\right) \geq 1-\delta \]
where $\KL( q \Vert 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$.
\end{thm}

\subsection{Discussion}
\label{discussion1}

Theorem~\ref{thm-pb-from-margin} shows that when a margin exists it is
\emph{always} possible to find a ``posterior'' distribution (in the
style of \cite{SNN}) 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 \(
\bar{F}^{-1}( \epsilon ) \) is not very large for any reasonable value of
\( \epsilon \). In particular, at \( \bar{F}(3) \), we have \( \epsilon \leq
0.01 \). Thus, for the purpose of understanding, we can replace \(
\bar{F}^{-1}( \epsilon ) \) with \( 3 \) and consider \( \epsilon \simeq
0\).  One useful approximation for \( \bar{F}(x) \) with large $x$ is:
\[ \bar{F}(x) \simeq \frac{e^{-x^2/2}}{\sqrt{2 \pi}} (1/x) \]

If there are no margin errors \( \hat{e}_\gamma (c) = 0 \), then these
approximations, yield the approximate bound:
\[
\Pr _{S\sim D^{m}}\left( e_{Q(\bfw,\gamma,0)}\leq \frac{
  \frac{9}{2\gamma^2} + \ln \frac{3 \sqrt{2 \pi}}{\gamma}
  +\ln\frac{m+1}{\delta }}{m}\right) \geq 1-\delta 
\] 
In particular, for large $m$ the true error is approximately bounded
by \( \frac{9}{2\gamma^2 m} \).  

As an example, if $\gamma = 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~\ref{lem-simple} and \ref{sto-det} or
Theorem \ref{thm-margin-bound}) 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~\ref{thm-pb-from-margin} and~\ref{thm-pb-from-margin-full}
also give bounds on the averaging classifiers $\bfw$.

This theorem is robust in the presence of noise and margin errors.
Since the PAC-Bayes bound works for \emph{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
\cite{SNN} and allow the data to determine the ``right'' posterior \(
Q \). Using the data rather than the margin \( \gamma \) 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.

\section{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~\ref{thm-pb-from-margin} 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
$\mu$ to make the inequality~(\ref{mu-formula}) an equality.  Hence,
any choice of $\mu$ determines $\epsilon$ and hence the overall bound.
We then have the freedom to choose $\mu$ to optimise the bound.

As noted earlier, given a weight vector $\bfw$, any particular feature
vector \( \bfx \) decomposes into a portion \( \bfx _{\Vert } \) which
is parallel to \( \bfw \) and a portion \( \bfx _{\top } \) which is
perpendicular to \( \bfw \). Hence, we can write \(\bfx = x_{\Vert}
\bfe_\Vert + x_\top \bfe_\top\), where $\bfe_\Vert$ is a unit vector
in the direction of $\bfw$ and $\bfe_\top$ is a unit vector in the
direction of $\bfx_\top$.  Note that we may have $y x_\Vert < 0$, if $\bfx$ is
misclassified by $\bfw$.

\begin{thm}
\label{thm-pb-from-margin-full} For all averaging classifiers $c$ with normalized weights $\bfw$ 
 and for all $\epsilon > 0$ stochastic error rates, If we choose $\mu
> 0$ such that
\begin{eqnarray}
\label{mu-formula}
E_{\bfx,y \sim S} \bar{F} \left( \frac{y x_\Vert }{x_\top} \mu \right) = \epsilon
\end{eqnarray}
then there exists a posterior distribution $Q(\bfw,\mu,\epsilon)$ 
such that
\[
\Pr _{S\sim D^{m}}\left( \forall \epsilon,\bfw,\mu:\,\,\,
\KL (\epsilon \Vert e_{Q(\bfw,\mu,\epsilon)}) 
\leq \frac{ \ln \frac{1}{\bar{F}\left(\mu\right)} 
           +\ln\frac{m+1}{\delta }}{m}\right) \geq 1-\delta \]
where $\KL( q \Vert 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$.
\end{thm}

\begin{proof}
The proof uses the PAC-Bayes bound, which states that for all prior
distributions \( P \), 
\[
\Pr _{S\sim D^{m}}\left( \forall Q:\,\,\,\KL (\hat{e}_{Q}\Vert e_{Q})\leq \frac{\KL (Q||P)+\ln \frac{m+1}{\delta }}{m}\right) \geq 1-\delta 
\]
We choose \( P=N(0,I) \), an isotropic Gaussian\footnote{Later, the fact
that an isotropic Gaussian has the same representation in all
rotations of the coordinate sytem will be useful.}.

A choice of the ``posterior'' \( Q \) completes the proof. The \( Q \)
we choose depends upon the direction \( \bfw \), the margin $\gamma$,
and the stochastic error \( \epsilon \). In particular, \( Q \) equals
\( P \) in every direction perpendicular to \( \bfw \), and a
rectified Gaussian tail in the $\bfw$ direction\footnote{Note that we
use the invariance under rotation of \( N(0,I) \) here to line up one
dimension with \( \bfw \).}.  The distribution of a rectified Gaussian
tail is given by $ R(\mu) = 0 $ for $x < \mu$ and $R(\mu) =
\frac{1}{\bar{F}(\mu)\sqrt{2\pi}} e^{- x^2/2} $ for $x \geq \mu$.

The chain rule for relative entropy (Theorem 2.5.3 of \cite{Cover})
and the independence of draws in each dimension implies that:
\begin{eqnarray*}
\KL (Q\Vert P)&=&\KL (Q_{\Vert }\Vert P_{\Vert })+\KL (Q_{\top }||P_{\top })
\\
&=&\KL (R(\mu)\Vert N(0,1))+\KL (P_{\top }\Vert P_{\top })
\\
&=&\KL (R(\mu)\Vert N(0,1))+0 \\
&=& \int_\mu ^ \infty \ln \frac{1}{\bar{F}(\mu)} R(x) dx \\
&=& \ln \frac{1}{\bar{F}(\mu)}
\end{eqnarray*}
Thus, our choice of posterior implies the theorem if the empirical
error rate is \( \hat{e}_{Q(\bfw,\bfx,\epsilon)} \leq E_{\bfx,y \sim S} \bar{F} \left( \frac{\bfx _\Vert }{\bfx_\top} \mu \right) \leq \epsilon \) 
which we show next.

Given a point $\bfx$, our choice of posterior implies that we can
decompose the stochastic weight vector, \( \hat{\bfw }=\hat{w}_{\Vert
}\bfe_\Vert+\hat{w}_{\top }\bfe_\top + \tilde{\bfw}\), where
$\bfe_\Vert$ is parallel to $\bfw$, $\bfe_\top$ is parallel to
$\bfx_{\top}$ and $\tilde{\bfw}$ is a residual vector perpendicular to
both.  By our definition of the stochastic generation \( \hat{\bfw}_
\Vert \sim R(\mu) \) and \( \hat{\bfw}_\top \sim N(0,1) \).  To avoid
an error, we must have:
\begin{eqnarray*}
y&=&\sign(v_{\hat{\bfw}} (\bfx)) \\ 
&=&\sign( \hat{w}_{\Vert }x_{\Vert} + \hat{w}_{\top }x _{\top }).
\end{eqnarray*}
Then, since $\hat{w}_\Vert \geq \mu$, no error occurs if:
\[
y(\mu x _{\Vert }+\hat{w}_{\top }x _{\top }) > 0 
\]
Since $\hat{w}_\top$ is drawn from $N(0,1)$ the probability of this event is:
\[
\Pr \left( y(\mu x _{\Vert }+\hat{w }_{\top }x _{\top }) > 0 \right) 
\geq 1 - \bar{F} \left( \frac{y x _\Vert }{x_\top} \mu \right)
\]
And so, the empirical error rate of the stochastic classifier is
bounded by:
\[ 
\hat{e}_Q \leq E_{\bfx,y \sim S} \bar{F} \left( \frac{y x _\Vert }{x_\top} \mu \right) = \epsilon
\]
as required. \end{proof}

\subsection{Proof of Theorem \ref{thm-pb-from-margin}}

\begin{proof} (sketch)
The theorem follows from a relaxation of
Theorem~\ref{thm-pb-from-margin-full}.  In particular, we treat every
example with a margin less than $\gamma$ as an error and use the
bounds $\Vert \bfx_\top \Vert \leq 1$ and $\|\bfx_\Vert\| \geq \gamma$.
\end{proof}

\subsection{Further results}

Several aspects of the Theorem \ref{thm-pb-from-margin-full} appear
arbitrary, but they are not. In particular, the choice of ``prior'' is
not that arbitrary as the following lemma indicates.

\begin{lem}
The set of \( P \) satisfying \( \exists P_{\Vert \Vert }:\,\, \) \( P(\bfx)=P_{\Vert \Vert }(\Vert \bfx\Vert^2 ) \)
(rotational invariance) and \( P(\bfx)=\prod _{i=1}^{N}p_{i}(\bfx_i) \) (independence
of each dimension) is \( N(0, \lambda I) \) for \( \lambda > 0 \).
\end{lem}
\begin{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(\bfx)=\prod _{i=1}^{N}p(\bfx_{i})\]
 for some function \( p(\cdot) \). Applying rotational invariance, we have that: 
\[
P(\bfx)=P_{\Vert \Vert }(\Vert \bfx\Vert^2 )=\prod _{i=1}^{N}p(\bfx_{i})\]
This implies: 
\[
\log P_{\Vert \Vert }\left( \sum _{i=1}^{N}\bfx_{i}^{2}\right) =\sum _{i=1}^{N}\log p(\bfx_{i}).\]
Taking the derivative of this equation with respect to $\bfx_i$ gives
\[
\frac{P'_{\Vert \Vert }(\Vert \bfx\Vert^2 )2\bfx_i}{P_{\Vert \Vert }(\Vert \bfx\Vert^2 )}
    = \frac{p'(\bfx_i)}{p(\bfx_i)}.
\]
Since this holds for all values of $\bfx$ we must have
\[
P_{\Vert \Vert }(t) = \lambda P'_{\Vert \Vert }(t)
\]
for some constant $\lambda$,
or $P_{\Vert \Vert }(t) = C\exp(\lambda t)$, for some constant $C$. Hence,
$
P(\bfx) = C\exp(\lambda \Vert \bfx \Vert^2),
$
as required.
\end{proof}

The constant \( \lambda \) in the previous lemma is a free
parameter. However, the results do not depend upon the precise value
of \( \lambda \) 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.

\section{Margin Implies Margin Bound}

\label{sec-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.

\subsection{Simple Margin Bound}

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

\begin{lem} \label{lem-simple}(Simple Averaging bound) For any stochastic classifier with 
distribution $Q$ and true error rate $e_Q$, the averaging classifier,
\[ c_Q(\bfx) = \mbox{sign} \left(\int_H h(\bfx) dQ(h) \right) \] has true error rate:
\[ e(c_Q) \leq 2 e_Q \]
\end{lem}
\begin{proof}
For every example $(\bfx,y)$, every time the averaging classifier errs, the
probability of the stochastic classifier erring must be at least
$1/2$.
\end{proof}

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(\bfx)$ \emph{is} the original averaging
classifier.

\begin{lem}
\label{sto-det}
 For $Q = Q(\bfw,\gamma,\epsilon)$ derived according to Theorems
 \ref{thm-pb-from-margin}  and
 \ref{thm-pb-from-margin-full}  
and $c_Q(\bfx)$ as in lemma \ref{lem-simple}:
\[ c_Q(\bfx) = \mbox{sign}\left( v_\bfw (\bfx) \right) \]
\end{lem}

\begin{proof}
For every $\bfx$ this equation holds because of two simple facts:

\begin{enumerate}
\item For any $\hat{\bfw}$ that classifies an input $\bfx$ differently
from the averaging classifier, there is a unique equiprobable paired
weight vector that agrees with the averaging classifier.
\item If $v_\bfw(\bfx) \neq 0$, then there exists a nonzero measure 
of classifier pairs which always agrees with the averaging classifier.
\end{enumerate}

Condition (1) is met by reversing the sign of $\hat{\bfw}_\top$ 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 $\hat{\bfw} =
\lambda \bfw$ and nearby classifiers for any $\lambda > 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.
\end{proof}

The simple averaging bound is elegant, but it breaks down when the
empirical error is large because:
\[ e(c) \leq 2 e_Q = 2 (\hat{e}_Q + \Delta_m) \simeq 2 \hat{e}_\gamma(c) + 2 \Delta_m \]
where $\hat{e}_Q$ is the empirical error rate of a stochastic
classifier and $\Delta_m$ goes to zero as $m \rightarrow \infty$.
Next, we construct a bound of the form $e(c_Q) \leq \hat{e}_\gamma(c)
+ \Delta_m'$ where \( \Delta_m' > \Delta_m \) but \( \hat{e}_\gamma(c)
\leq 2 \hat{e}_\gamma(c) \).

\subsection{A (Sometimes) Tighter Bound}

By altering our choice of \( \mu  \) and our notion of ``error'' we can construct
a bound which holds \emph{without} randomization. In particular, we have the
following theorem:

\begin{thm}
\label{thm-margin-bound}  For all averaging classifiers $c$ with normalized weights $\bfw$ 
for all  $\epsilon > 0$ ``extra'' error rates and $\gamma>0$ margins:
\[
\Pr _{S\sim D^{m}}\left( \forall \epsilon,\bfw,\gamma:\,\,\,
\KL (\hat{e}_\gamma(c) + \epsilon \Vert e(c) - \epsilon) 
\leq \frac{ \ln \frac{1}{\bar{F}\left(\frac{2 \bar{F}^{-1}(\epsilon)}{\gamma}\right)} 
           +2 \ln\frac{m+1}{\delta }}{m}\right) \geq 1-\delta \]
where $\KL( q \Vert 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$.

\end{thm}
The proof of this statement is strongly related to the proof given in
\cite{Margin} but noticeably simpler.  It is also very related to the
proof of theorem \ref{thm-pb-from-margin}.

\begin{proof} (sketch)
Instead of choosing \( \hat{\bfw }_{\Vert } \) so that the empirical
error rate is increased by \( \epsilon  \), we instead
choose \( \hat{\bfw }_{\Vert } \) so that the number of margin
violations at margin \( \frac{\gamma }{2} \) is increased by at most
\( \epsilon \). This can be done by drawing from a
distribution such as
\[
\hat{\bfw}_\Vert \sim R\left(\frac{2 \bar{F}^{-1}(\epsilon)}{\gamma}
 \right) \] 

Applying the PAC-Bayes bound to this we reach a bound on the number of
margin violations at \( \frac{\gamma }{2} \) for the true
distribution. In particular, we have:
\[
\Pr _{S\sim D^{m}}\left( \KL \left( \hat{e}_{\gamma}(c) + \epsilon
\Vert e_{Q,\frac{\gamma }{2}}\right) \leq \frac{\ln
\frac{1}{\bar{F}\left(\frac{2 \bar{F}^{-1}(\epsilon)}{\gamma}\right)}
+\ln\frac{m+1}{\delta }}{m}\right) \geq 1-\delta \]

The application is tricky because the bound does not hold uniformly
for all $\gamma$.\footnote{Thanks to David McAllester for pointing
this out.}  Instead we can discretize $\gamma$ at scale $1/m$ and
apply a union bound to get $\delta \rightarrow \delta / m + 1$.

For any fixed example, \( (\bfx,y) \) with probability \( 1-\delta \),
we know that with probability at least \( 1-e_{Q,\frac{\gamma }{2}}
\), the example has a margin of at least \( \frac{\gamma }{2}
\). Since the example has a margin of at least \( \frac{\gamma }{2} \)
and our randomization doesn't change the margin by more than \(
\frac{\gamma }{2} \) with probability \( 1-\epsilon \), the averaging
classifier almost always predicts in the same way as the stochastic
classifier implying the theorem.
\end{proof}

\subsection{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
\ref{lem-simple}) and the margin bound (theorem
\ref{thm-margin-bound}) 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.

\subsection{Acknowledgements}

Many thanks to David McAllester for critical reading and comments.

\begin{thebibliography}{1}
\bibitem{Bartlett98}
P.~L. Bartlett,
\newblock ``The sample complexity of pattern classification with neural
  networks: the size of the weights is more important than the size of the
  network,''
\newblock {\em IEEE Transactions on Information Theory}, vol. 44, no. 2, pp.
  525--536, 1998.
\bibitem{Cover}Thomas Cover and Joy Thomas, ``Elements of Information Theory'' Wiley, New York
1991.
\bibitem{HerbGraep}
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.
\bibitem{ME}T. Jaakkola, M. Meila, T. Jebara, ``Maximum Entropy D iscrimination\textbackslash{}char''
NIPS 1999.
\bibitem{SNN}John Langford and Rich Caruana, (Not) Bounding the True Error NIPS2001.
\bibitem{averaging_icml}John Langford, Matthias Seeger, and Nimrod Megiddo, ``An Improved Predictive
Accuracy Bound for Averaging Classifiers'' ICML2001.
\bibitem{averaging_tech}John Langford and Matthias Seeger, ``Bounds for Averaging Classifiers.'' CMU
tech report, CMU-CS-01-102, 2001. 
\bibitem{PB}David McAllester, ``PAC-Bayesian Model Averaging'' COLT 1999.
\bibitem{Boosting}Yoav Freund and Robert E. Schapire, ``A Decision
Theoretic Generalization of On-line Learning and an Application to
Boosting'' Eurocolt 1995.
\bibitem{Seeger}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
\bibitem{Margin}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.
\bibitem{ShaBarWilAnt98}
J.~Shawe-Taylor, P.~L. Bartlett, R.~C. Williamson, and M.~Anthony.
\newblock Structural risk minimization over data-dependent hierarchies.
\newblock {\em IEEE Transactions on Information Theory}, 44(5):1926--1940,
  1998.
\end{thebibliography}
\end{document}
Content-Description: 

%%%% NIPS Macros (LaTex)
%%%% Style File
%%%% Dec 12, 1990   Rev Aug 14, 1991; Sept, 1995; April, 1997; April, 1999

% This file can be used with Latex2e whether running in main mode, or
% 2.09 compatibility mode.
%
% If using main mode, you need to include the commands
%             \documentclass{article}
%             \usepackage{nips99e,times}
% as the first lines in your document.  Or, if you do not have Times
% Roman font available, you can just use
%             \documentclass{article}
%             \usepackage{nips99e}
% instead.
%
% If using 2.09 compatibility mode, you need to include the command
%             \documentstyle[nips99e,times]{article} 
% as the first line in your document.  Or, if you do not have Times
% Roman font available, you can include the command
%             \documentstyle[nips99e]{article}
% instead.

% Note that 1995 text height has been increased to 8.25in
% Physical page layout
\evensidemargin .75in 
\oddsidemargin .75in
\topmargin=0pt
\setlength\textheight{8.25in} 
\setlength\textwidth{5in}
\setlength\columnsep{0.25in}  \newlength\titlebox 
%\setlength\titlebox{2.375in}
\setlength\headheight{0pt}   \setlength\headsep{0pt}
%\setlength\footheight{0pt}
\setlength\footskip{0pt}
\thispagestyle{empty}        \pagestyle{empty}
\flushbottom \sloppy

% We're never going to need a table of contents, so just flush it to 
% save space --- suggested by drstrip@sandia-2
\def\addcontentsline#1#2#3{}

% Title stuff, taken from deproc.
\def\maketitle{\par 
\begingroup
   \def\thefootnote{\fnsymbol{footnote}}
   \def\@makefnmark{\hbox to 0pt{$^{\@thefnmark}$\hss}} % for perfect author
                                                        % name centering
%   The footnote-mark was overlapping the footnote-text,
%   added the following to fix this problem               (MK)
   \long\def\@makefntext##1{\parindent 1em\noindent
                            \hbox to1.8em{\hss $\m@th ^{\@thefnmark}$}##1}
   \@maketitle \@thanks
\endgroup
\setcounter{footnote}{0}
\let\maketitle\relax \let\@maketitle\relax
\gdef\@thanks{}\gdef\@author{}\gdef\@title{}\let\thanks\relax}

% The toptitlebar has been raised to top-justify the first page

\def\@maketitle{\vbox{\hsize\textwidth
\linewidth\hsize \vskip 0.1in \toptitlebar \centering
{\LARGE\bf \@title\par}  \bottomtitlebar % \vskip 0.1in %  minus
   \def\And{\end{tabular}\hfil\linebreak[0]\hfil
            \begin{tabular}[t]{c}\bf\rule{\z@}{24pt}\ignorespaces}% 
  \def\AND{\end{tabular}\hfil\linebreak[4]\hfil
            \begin{tabular}[t]{c}\bf\rule{\z@}{24pt}\ignorespaces}% 
    \begin{tabular}[t]{c}\bf\rule{\z@}{24pt}\@author\end{tabular}% 
\vskip 0.3in minus 0.1in}}

\renewenvironment{abstract}{\vskip.075in\centerline{\large\bf
Abstract}\vspace{0.5ex}\begin{quote}}{\par\end{quote}\vskip 1ex}

% sections with less space
\def\section{\@startsection {section}{1}{\z@}{-2.0ex plus
    -0.5ex minus -.2ex}{1.5ex plus 0.3ex
minus0.2ex}{\large\bf\raggedright}}

\def\subsection{\@startsection{subsection}{2}{\z@}{-1.8ex plus    
-0.5ex minus -.2ex}{0.8ex plus .2ex}{\normalsize\bf\raggedright}}
\def\subsubsection{\@startsection{subsubsection}{3}{\z@}{-1.5ex
plus      -0.5ex minus -.2ex}{0.5ex plus
.2ex}{\normalsize\bf\raggedright}}
\def\paragraph{\@startsection{paragraph}{4}{\z@}{1.5ex plus   
0.5ex minus .2ex}{-1em}{\normalsize\bf}}
\def\subparagraph{\@startsection{subparagraph}{5}{\z@}{1.5ex plus 
  0.5ex minus .2ex}{-1em}{\normalsize\bf}}
\def\subsubsubsection{\vskip
5pt{\noindent\normalsize\rm\raggedright}}


% Footnotes
\footnotesep 6.65pt %
\skip\footins 9pt plus 4pt minus 2pt
\def\footnoterule{\kern-3pt \hrule width 12pc \kern 2.6pt }
\setcounter{footnote}{0}

% Lists and paragraphs
\parindent 0pt
\topsep 4pt plus 1pt minus 2pt
\partopsep 1pt plus 0.5pt minus 0.5pt
\itemsep 2pt plus 1pt minus 0.5pt
\parsep 2pt plus 1pt minus 0.5pt
\parskip .5pc


%\leftmargin2em 
\leftmargin3pc
\leftmargini\leftmargin \leftmarginii 2em
\leftmarginiii 1.5em \leftmarginiv 1.0em \leftmarginv .5em 

%\labelsep \labelsep 5pt

\def\@listi{\leftmargin\leftmargini}
\def\@listii{\leftmargin\leftmarginii
   \labelwidth\leftmarginii\advance\labelwidth-\labelsep
   \topsep 2pt plus 1pt minus 0.5pt
   \parsep 1pt plus 0.5pt minus 0.5pt
   \itemsep \parsep}
\def\@listiii{\leftmargin\leftmarginiii
    \labelwidth\leftmarginiii\advance\labelwidth-\labelsep
    \topsep 1pt plus 0.5pt minus 0.5pt 
    \parsep \z@ \partopsep 0.5pt plus 0pt minus 0.5pt
    \itemsep \topsep}
\def\@listiv{\leftmargin\leftmarginiv
     \labelwidth\leftmarginiv\advance\labelwidth-\labelsep}
\def\@listv{\leftmargin\leftmarginv
     \labelwidth\leftmarginv\advance\labelwidth-\labelsep}
\def\@listvi{\leftmargin\leftmarginvi
     \labelwidth\leftmarginvi\advance\labelwidth-\labelsep}

\abovedisplayskip 7pt plus2pt minus5pt%
\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip  0pt plus3pt%
\belowdisplayshortskip  4pt plus3pt minus3pt%

% Less leading in most fonts (due to the narrow columns)
% The choices were between 1-pt and 1.5-pt leading
%\def\@normalsize{\@setsize\normalsize{11pt}\xpt\@xpt} % got rid of @ (MK)
\def\normalsize{\@setsize\normalsize{11pt}\xpt\@xpt}
\def\small{\@setsize\small{10pt}\ixpt\@ixpt}
\def\footnotesize{\@setsize\footnotesize{10pt}\ixpt\@ixpt}
\def\scriptsize{\@setsize\scriptsize{8pt}\viipt\@viipt}
\def\tiny{\@setsize\tiny{7pt}\vipt\@vipt}
\def\large{\@setsize\large{14pt}\xiipt\@xiipt}
\def\Large{\@setsize\Large{16pt}\xivpt\@xivpt}
\def\LARGE{\@setsize\LARGE{20pt}\xviipt\@xviipt}
\def\huge{\@setsize\huge{23pt}\xxpt\@xxpt}
\def\Huge{\@setsize\Huge{28pt}\xxvpt\@xxvpt}

\def\toptitlebar{\hrule height4pt\vskip .25in\vskip-\parskip}

\def\bottomtitlebar{\vskip .29in\vskip-\parskip\hrule height1pt\vskip
.09in} %
%Reduced second vskip to compensate for adding the strut in \@author
