% --------------------------------------------------------------
% --------------------------------------------------------------

\documentclass{article}
\usepackage{icml2001}
\usepackage{epsf}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsopn}
\usepackage{psfig}
\usepackage{graphics}
\usepackage{url}

% --- Local macros ---

\def\KL{\textrm{D}}
\def\half{\mbox{$\frac{1}{2}$}}
\def\halftheta{\mbox{$\frac{1}{2}$}\theta}
\def\mAth{\mathsurround=0pt}
\def\eqalign#1{\,\vcenter{\openup1\jot \mAth
  \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
    \crcr#1\crcr}}\,}



\newcommand{\vx}[1]{\vect{x}_{#1}}
\newcommand{\vy}[1]{\vect{y}_{#1}}
\newcommand{\vz}[1]{\vect{z}_{#1}}
\newcommand{\vX}[1]{\vect{X}_{#1}}
\newcommand{\vY}[1]{\vect{Y}_{#1}}
\newcommand{\vt}[1]{\vect{t}_{#1}}
\newcommand{\vth}[1]{\vect{\theta}_{#1}}
\newcommand{\valpha}[1]{\vect{\alpha}_{#1}}
\newcommand{\vm}[1]{\vect{\mu}_{#1}}
\newcommand{\va}[1]{\vect{a}_{\lambda(#1)}}
\newcommand{\ml}[1]{\mat{\Lambda}_{#1}}
\newcommand{\mpa}[1]{\mat{\Phi}_{\lambda(#1)}(\va{k})}
\newcommand{\vxmm}[2]{(\vx{#1} - \vm{#2})}
\newcommand{\ms}[1]{\mat{\Sigma}_{#1}}
\newcommand{\mw}[1]{\mat{W}_{\lambda(#1)}}
\newcommand{\hvt}[1]{\hat{\vect{\theta}}_{#1}}
\newcommand{\tvt}[1]{\tilde{\vect{\theta}}_{#1}}
\newcommand{\hvm}[1]{\hat{\vect{\mu}}_{#1}}
\newcommand{\hva}[1]{\hat{\vect{a}}_{\lambda(#1)}}
\newcommand{\hml}[1]{\hat{\mat{\Lambda}}_{#1}}
\newcommand{\hmpa}[1]{\mat{\Phi}_{\lambda(#1)}(\hva{#1})}
\newcommand{\hvxmm}[2]{(\vx{#1} - \hvm{#2})}
\newcommand{\hms}[1]{\hat{\mat{\Sigma}}_{#1}}
\newcommand{\hmw}[1]{\hat{\mat{W}}_{\lambda(#1)}}
\def\pr#1{\mbox{$\Pr_{#1}$}}
\newcommand{\sset}{\{\vx{i}\}}
\newcommand{\rotate}[2]{#1^t #2 #1}
\newcommand{\rota}[1]
   {\rotate{\mw{k}}{\ml{k}^{-1}}}
\newcommand{\hrota}[1]
   {\rotate{\hmw{k}}{\hml{k}^{-1}}}
\newcommand{\rotb}[1]
   {\mw{k} \ms{k} \mw{k}^t}
\newcommand{\hrotb}[1]
   {\hmw{k} \hms{k} \hmw{k}^t}

\newtheorem{theo}{Theorem}
\newtheorem{lemma}{Lemma}

% --- Domains ---

\setlength{\unitlength}{0.05\textwidth}
\newlength{\mywidth}
\newlength{\myheight}

\bibliographystyle{plain}

%\renewcommand{\textfraction}{0}
%\renewcommand{\topfraction}{1}

%\title{An Improved Bound for Averaging Classifiers}
\title{An Improved Predictive Accuracy Bound for Averaging Classifiers}

\author{\begin{minipage}[t]{\textwidth}
\begin{minipage}[t]{9\unitlength}
\begin{center}
\normalsize\bf John Langford \\
School of Computer Science \\
Carnegie Mellon \\
{\em jcl@cs.cmu.edu} \\
\url{http://www.cs.cmu.edu/~jcl}
\end{center}
\end{minipage}\hfill
\begin{minipage}[t]{9\unitlength}
\begin{center}
\normalsize\bf Matthias Seeger \\
Institute for Adaptive and Neural Computation \\
University of Edinburgh \\
{\em seeger@dai.ed.ac.uk} \\
\url{http://www.dai.ed.ac.uk/homes/seeger/}
\end{center}
\end{minipage} \\
\begin{center}
\normalsize\bf Nimrod Megiddo \\
IBM Almaden Research Center \\
{\em megiddo@almaden.ibm.com} \\
\url{http://theory.stanford.edu/~megiddo/}
\end{center}
\end{minipage}
}
\date{}

\begin{document}
%\pagestyle{empty}

\maketitle

% --- Abstract ---

\begin{abstract}

We present an improved bound on the difference between training and
test errors for voting classifiers.  This improved averaging bound
provides a theoretical justification for popular averaging techniques
such as {\em Bayesian classification}, {\em Maximum Entropy
discrimination}, {\em Winnow} and {\em Bayes point machines} and has
implications for learning algorithm design.

\end{abstract}

\section{Introduction}\label{sec-intro}

Averaging is a standard technique in applied machine learning for
combining multiple classifiers to achieve greater accuracy.
% via averaging.  
Examples include {\em Bayesian classification} \cite{Cheeseman}, {\em
boosting} \cite{Freund}, {\em bagging} \cite{Breiman}, {\em Winnow}
\cite{Littlestone}, {\em Maximum Entropy discrimination }
\cite{Jaakkola}, and {\em Bayes point machines}
\cite{Herbrich}.  Despite the prevalence of this technique there is
only weak theoretical justification so far for the practice.  This paper
provides a new stronger theoretical justification for the practice of
averaging.  In particular, we state and prove a bound on the gap
between the training set error rate and the predictive error rate
which improves as more hypotheses are averaged over.

Until 1998, theoretical bounds such as the Occam's razor bound
\cite{Blumer} suggested that averaging was \emph{wrong} because it
increased the description length of the resulting
hypothesis.\footnote{We note, however, that it is the {\em minimum}
description length that should be used in the bound.}  The Occam's
razor bound \emph{only suggests} that averaging \emph{may} be bad
since there is no corresponding lower bound.  Schapire, Freund,
Bartlett and Lee \cite{Schapire} showed a great improvement on the
naive bound for an average-of-classifiers hypothesis. Loosely
speaking, their margin bound states that if the average has a small
empirical error rate (i.e., it is accurate on most training examples)
and has a large ``margin'' (defined in \ref{sec-setting}), then its
true error rate is also small. The proof itself works in a very
intuitive manner by showing that the accuracy of a large margin
classifier is close to the accuracy of a simple classifier, for which
standard bounds are tight.

The problem with this result is that the value of the bound depends
only on the empirical margin which does not necessarily improve with
an average over a larger number of hypotheses.  This bound suggests
using the simple criteria: choose the average to maximize the margin.
However, empirical results \cite{Grove} indicate that this procedure
is not optimal.  

In this paper, we prove a new bound on the true error rate, which
suggests a new optimization criterion, namely, optimize for a large
margin \emph{and} for a uniform average over as many hypotheses as
possible.

% BEGIN OLD
The layout of this paper is as follows:

\begin{enumerate}
\item Discussion of the relationship with prior relevant results.
\item Development of the improved theoretical bound with an emphasis on simplicity.
\item A proof of the bound.
\item An example of the benefit of the new bound on a toy problem.
\item Discussion of implications of the new bound on prior work.
\end{enumerate}
% END OLD
% BEGIN SUGGESTION: Saves space! 
% We aren't short -John
%The layout of the paper is as follows. First, we discuss the relationship
%with prior results. We then develop and discuss the improved theoretical bound
%with an emphasis on simplicity, followed by a self-contained proof. In
%section \ref{sec-implic}, we give an example showing the benefits of the
%new bound on a toy problem, and we discuss implications of our result to
%prior work, namely to a range of frequently used machine learning algorithms.
% END SUGGESTION

\section{The setting and important earlier results}\label{sec-sett-earlier}

\subsection{The setting}\label{sec-setting}

We first explain the setting, which is the same as the one used in
\cite{Schapire}.  

An input space $\cal X$ is given, where the members of $\cal X$ are
also referred to as {\em examples}. The set ${\cal X} \times \{-1,1\}$
is the space of {\em labeled} examples.  A {\em base hypothesis} $h$
is a mapping from the input space $\cal X$ into $\{-1,1\}$. A (possibly infinite)
space $\cal H$ (the hypothesis space) is given
and the goal is to construct an {\em averaging classifier} $c:{\cal X}
\rightarrow \{-1,1\}$ as a weighted average of base hypotheses:
\[ c(x)=\mathop{\rm sign} \sum_{j=1}^{k}q_{j}h_{j}(x) \quad (x \in \cal X)\ , \]
where $q_j\ge 0$, $j=1,\ldots,k$, and $\sum_{j=1}^k q_i = 1$.  The
fundamental assumption here is that labeled training examples are
drawn independently, with replacement, from some probability
distribution $D$ over ${\cal X} \times \{-1,1\}$.  In all the theorems
we discuss, $D$ is assumed to be unknown to the procedure which constructs the
classifier, and the results hold for all
$D$. Probabilities and expectations over $D$ will be denoted by the
subscript $D$; for example, the true error of an averaging classifier
is denoted by:
\begin{equation}
  e_D(c) = E_D[I(c(x) \neq y)] = E_{(x,y)\sim D}[I(c(x) \neq y)].
\end{equation}
Here, $I(\cdot)$ is the indicator function, which is $1$ if its argument
evaluates to \emph{true} and $0$ otherwise. Probabilities with respect to
$D$ are written as $\pr{D}$.

With $S$, we denote a sample $\{(x_i,y_i)\, |\, i=1,\dots,m\}$ drawn
independently and identically distributed (i.i.d.) from $D(x,y)$. The
i.i.d assumption is the one fundamental assumption we make in this
work.  The subscript $S$ denotes empirical expectation or probability
over $S$, for example the empirical error of an averaging classifier
is given by:
\begin{equation}
  e_S(c) = E_S[I(c(x) \neq y)] = \frac{1}m \sum_{i=1}^m I(c(x_i) \neq y)
\end{equation}
Probabilities with respect to $S$ are written as $\pr{S}$.

\subsection{Quantities used in the bound}\label{sec-quantities}
The basic learning model needs to be augmented with a few definitions
for the analysis.

Given a subset $\{h_1,\ldots,h_k\} \subseteq \cal H$, the set
$\{q_1,\ldots,q_k\}$ can be interpreted as a probability distribution
over the set $\cal H$.\footnote{
  In the case of finite or countably infinite ${\cal H}$, this is achieved
  by assigning all hypotheses outside the subset the weight zero. If
  ${\cal H}$ is finite, we will usually work with ${\cal H} = \{h_1,\ldots,
  h_k\}$ for simplicity. For
  uncountable spaces, we define $Q$ as $\sum_j q_j \delta(h,h_j)$, where
  $\delta(h,h_j)$ is the delta distribution centered on $h_j$.}
This distribution will be denoted by \( Q \).
We will also often use the unsigned version of the classifier:
\[ f(x)= E_{h\sim Q}[h(x)] = \sum_{j=1}^{k}q_{j}h_{j}(x)\ . \]
It is important to note that we make no assumption about how the weights 
$q_1,\ldots,q_k$ are obtained, so our results are applicable to many algorithms.

The derived bounds depend on the powerful concept of the {\em margin}, $t (x,y)$, 
of a labeled example with respect to a classifier, namely, 
\[ t(x,y) = y \sum _{j=1}^{k}q_{j}h_{j}(x) = y f(x)\ .\]
The margin is a quantitative measure of how decided the average is.
Obviously, $-1\le t(x,y) \le 1$. If $t(x,y)=1$ (resp.\
$t(x,y)=-1$), then all the base hypotheses classify correctly (resp.\
incorrectly).  When $t(x,y)$ is close to zero, the classifier is, in
some sense, undecided. Note that $c(x) = y$ iff $t(x,y) > 0$.

\subsection{Earlier results}\label{sec-earlier}

The new averaging bound arises from improving one critical step in
the proof of the original margin bound, which we state here for
reference.

\begin{theo}[Margin Bound \cite{Schapire}]\label{th-schapire}
Let $\delta\in (0,1)$. With probability at least $1-\delta$ over random
samples $S$ from $D$ we have that for all distributions $Q=(q_1,\dots,q_k)$
over the finite hypothesis space ${\cal H}$ and all $\theta\in (0,1]$:
\begin{equation}
\eqalign{
  \pr{D}[ y f(x)\le 0 ] \le &\ \pr{S}[ y f(x)\le \theta ] \cr
                          + &\ O\left(
      \sqrt{\frac{\theta^{-2} \ln |{\cal H}|  \log m + \ln\delta^{-1} }
           {m}} 
    \right), \cr }
\end{equation}
where $f(x) = E_{h\sim Q}[h(x)] = \sum_j q_j h_j(x)$.
\end{theo}
Here, the notation $b(m)=O(a(m))$ means there exists a constant $C$ such
that $b(m)\leq C\cdot a(m)$ for all $m$.
This margin bound implies that
if most training examples have a large margin $\theta$ (i.e. $t(x,y) >
\theta$ for most $(x,y)\in S$) and the hypothesis space is not too
large, then the generalization error cannot be large.

To improve on this bound, we employ a PAC-Bayes bound from McAllester
\cite{McAllester}. In the PAC-Bayes setting, a classifier is also
defined by a distribution $Q$ over the hypothesis space. However, each
classification\footnote{Such classifiers are called {\em Gibbs classifiers}
(e.g.  \cite{Haussler}).}   
is carried out according to a hypothesis sampled from
$Q$ rather than by the averaging classifier
$c$ defined by $Q$.  We are interested in the gap between the {\em
expected} generalization error and the {\em expected} empirical error,
where both expectations are taken with respect to $Q$. We need to
introduce the {\em relative entropy} (or {\em Kullback-Leibler (KL)
divergence}; e.g., \cite{Cover}):
\begin{equation}\label{eq-relent}
  \KL(Q\|P) = E_{h\sim Q} \left[ \ln \frac{q(h)}{p(h)} \right]\ ,
\end{equation}
where $q, p$ denote the probability densities of the distributions $Q, P$.
If ${\cal H}$ is finite, we have\footnote{
  Here and elsewhere, we agree on the definition $0 \log 0 = \lim_{t\to 0+}
  t \log t = 0$.}
\begin{equation}
  \KL(Q\|P) = \sum_{j=1}^k q_j \ln \frac{q_j}{p_j},
\end{equation}
where $Q=(q_1,\dots,q_k),\; P=(p_1,\dots,p_k)$. The relative entropy is an
asymmetric distance measure between probability distributions, with
$\KL(Q\|P)=0$ if and only if $Q=P$ almost everywhere.

\begin{theo}[PAC-Bayes \cite{McAllester}]\label{th-mcall}
% Let $\ell$ be a loss function mapping $R$ into $\{0,1\}$. 
Let $P$ be any prior
distribution over ${\cal H}$ and $\delta\in (0,1)$. With
probability at least $1-\delta$ over random samples $S$ from $D$ we have that
for all distributions $Q$ over the hypothesis space ${\cal H}$:
\[
\eqalign{% \begin{split}
  \pr{{D,Q}}[h(x)\neq y] \leq &\ \pr{{S,Q}}[h(x)\neq y] \cr
  +&\sqrt{ \frac{\KL(Q||P) +\ln\delta^{-1} +\ln m+2}{2m-1} }
\cr } %\end{split}
\]
\end{theo}
Here, $\pr{{D,Q}}[\cdot]$ is short for $E_{h\sim Q}[\pr{D}[\cdot]]$, and
$\pr{{S,Q}}[\cdot]$ stands for $E_{h\sim Q}[\pr{S}[\cdot]]$.
This theorem holds for finite and infinite hypothesis spaces.  The
PAC-Bayes theorem guarantees a tighter bound (except at low order)
than earlier results such as the following Occam's razor theorem.

\begin{theo}[Occam's Razor \cite{Blumer}]\label{th-occam}
Let $P$ be a distribution over a hypothesis space ${\cal H}$ and
$\delta\in (0,1)$. With probability at least $1-\delta$ over random
samples $S$ from $D$, for all hypotheses $h\in {\cal H}$:
\begin{equation}
\eqalign{ %\begin{split}
  \pr{D}[ h(x) \ne y ] \le &\ \pr{S}[ h(x)\ne y ] \cr
   +&\  \sqrt{ \frac{ \ln(1/p(h)) + \ln\delta^{-1} }
                 {2 m} 
          }\ .
\cr} %\end{split}
\end{equation}
\end{theo}

Note that, for finite ${\cal H}$ and up to low order terms, theorem
\ref{th-occam} is a special
case of theorem \ref{th-mcall}, where we choose delta distributions
$Q=(0,\dots,0,1,0,\dots,0)$ in theorem \ref{th-mcall}.  The essence of
our improvement of the standard margin bound comes from the
application of the PAC-Bayes bound instead of the Occam's razor bound
within the standard proof of the margin bound.

\section{An improved averaging bound}\label{sec-main}

In this section, we state and prove our main result, a PAC-Bayes
generalization error bound for averaging classifiers. Before we do
this, we provide a discussion of a special case in order to put across
an intuition of how our bound can improve upon theorem
\ref{th-schapire}. In this discussion, we limit ourselves to a finite
${\cal H} = \{h_1,\dots,h_k\}$, while the main result will be stated for
arbitrary ${\cal H}$. Our bound relies on a ``posterior'' distribution
$Q=(q_1,\ldots,q_k)$ over ${\cal H}$, from which the average $f(x)$ is
defined as $f(x) = \sum_k q_k h_k(x)$. The ``posterior'' $Q$ may
depend on the training sample $S$ in an arbitrary
way.\footnote{ An example is, in Bayesian classification, the {\em
posterior distribution} over ${\cal H}$. The corresponding averaging
classifier $f(x)$ is called {\em Bayes classifier} or {\em
Bayes-optimal classifier} (e.g.  \cite{Haussler}).}

The {\em entropy} $H(Q)$ (e.g. \cite{Cover}) of $Q$ is defined as
$H(Q) = -\sum_i q_i \ln q_i$. It measures the ``uncertainty''
in $Q$, in that delta distributions $Q=(0,\dots,0,1,0,\dots,0)$ have
minimum entropy $0$ and the uniform distribution has maximum entropy
$\ln k$. We can state a special case of our main result as follows.
\begin{theo}[Special Case]\label{th-special}
Let $\delta\in (0,1)$. With probability at least $1-\delta$ over random
samples $S$ from $D$, for all distributions $Q$ over the
hypothesis space ${\cal H}$ and for all $\theta \in (0,1]$:
\begin{equation}
\eqalign{ % \begin{split}
  \pr{D} & [ y f(x)\le 0 ] \le \pr{S}[ y f(x) \le \theta ] \cr
  + O & \left( \sqrt{\frac{
                          \theta^{-2}(\ln |{\cal H}| - H(Q)) \ln m +  \ln m +
                             \ln\delta^{-1}
                         }
                         {m} } \right).
\cr }% \end{split}
\end{equation}
\end{theo}
This theorem is just a simplification of theorem \ref{th-main} to finite
hypothesis spaces with a uniform prior $P$.

How much can the improvement help us? About the best case we could
hope for is a uniform average over half the hypothesis space\footnote{
An average over a subset of the hypothesis space ${\cal H}$ includes
only those hypotheses $h_j$ with coefficients $q_j$ significantly
different from zero.}. In that case, the complexity term \( (\ln
|H|-H(Q)) \ln m \) is quite small: \( \ln m \ln 2 \). In the worst
case, when the average is over only a number of hypotheses \( k \)
similar to the number of examples \( m \), there is no significant
improvement over the original margin bound.

It is easy to generalize the improved averaging bound to continuous
spaces with arbitrary priors by carefully applying the PAC-Bayes
bound.

\begin{theo}[Main theorem]\label{th-main}
Let $P$ be any continuous probability distribution over ${\cal H}$ and
let $\delta\in (0,1)$. With probability at least $1-\delta$ over random
samples $S$ of $D$, for all $\theta>0$ and for every
%(data dependent) This is meaningless
distribution $Q$ over ${\cal H}$:
\begin{equation}
\eqalign{% \begin{split}
  \pr{D}& \left[ y f(x)\le 0 \right] \le \pr{S}\left[ y f(x)\le \theta \right] \cr
  &+ O \left( 
              \sqrt{ \frac{\theta^{-2} \KL(Q\|P) \ln m + \ln m 
                           +  \ln \delta^{-1} 
                          }{m}
                   } 
        \right)
\cr }%\end{split}
\end{equation}
where $f(x)=E_{h\sim Q}[h(x)]$.
\end{theo}
The proof is given in \ref{sec-main-proof}. 

Theorem \ref{th-main} holds also for the case of bounded real-valued
hypotheses, without any loss in the tightness of the bound.  The
theorem can also be tightened in several quantitatively important
ways. Details can be found in \cite{TR}.

There exists an alternative approach for deriving a bound similar to
Theorem \ref{th-main} which needs to be mentioned.  Essentially,
starting with the covering number based approach of \cite{Bartlett} we
can use the covering number results from theorem 3.6 of \cite{Zhang}
to arrive at a similar bound.  The principle advantage of our approach
over this one is simplicity of argumentation combined with
quantitatively tighter results.

The continuous form of the improved averaging bound applies to arbitrary
averages over continuous hypothesis spaces, the {\em finite} averages
defined in subsection \ref{sec-quantities} are special cases.
Note that in this setting,
the average needs to be an integral over an uncountably infinite set
of hypotheses, otherwise the KL-divergence does not converge.  In practice,
this is not 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.

\subsection{Proof of main theorem}\label{sec-main-proof}

The proof has the same structure as the original margin bound proof
\ref{th-schapire} with one step replaced by the application of the
PAC-Bayes theorem \ref{th-mcall}.

Our averaging classifier is specified by 
\[c(x) = \mathop{\rm sign}\, E_{h\sim Q}[h(x)] \ .\]
Let $N$ be any natural number; later, the choice of $N$
will be optimized.
For every distribution $Q$, we construct a random function $g=g_Q$ as
follows. Draw $N$ hypotheses i.i.d. from $Q$ and define
\begin{equation}\label{eq-sample}
  g(x) = \frac{1}N \sum_{j=1}^N h_j(x).
\end{equation}
The set of all possible $g$'s is denoted
\begin{equation}\label{eq-cnset}
  {\cal H}_N = \biggl\{ \frac{1}N \sum_{j=1}^N h_j(x)\; \biggl|\;
  h_j\in {\cal H} \biggr\},
\end{equation}
and we denote the distribution of $g$ (i.e., over
the set ${\cal H}_N$) by $Q^N$.
Note that for a fixed pair $(x,y)$, the quantities $h_j(x)$ in the
expression for $g(x)$ (see (\ref{eq-sample})) are i.i.d.\ Bernoulli
variables (over $\{-1,1\}$) with mean
\begin{equation}
 y E_{h_j\sim Q}[ h_j(x) ] = y f(x) \ .
\end{equation}
Therefore, $y E_{g\sim Q^N}[ g(x) ] = y f(x)$. Since $g(x)$ is the
average over $N$ i.i.d.\ Bernoulli variables, Hoeffding's bound (see
\cite{Devroye}, p.122)
applies. Thus, for every $x \in {\cal X},\; y\in\{-1,+1\}$, the probabilities
with respect to the sampling of $h_1,\ldots,h_N$ satisfy
\begin{equation}\label{eq-purehoeff}
  \pr{g\sim Q^N} \left[ y (g(x)- f(x)) >  \epsilon \right] \leq
  e^{-\frac{1}{2} N \epsilon^2}
\end{equation}
For every $\theta>0$ and for every (fixed) $g\in {\cal H}_N$, the following simple
inequality holds:
\begin{equation}\label{eq-simple}
\begin{split}
  & \pr{D}[ y f(x)\le 0 ] \\
  & = \pr{D}[ y g(x)\le \halftheta,\, y f(x)\le 0 ] \\ 
  & + \pr{D}[ y g(x) > \halftheta,\, y f(x)\le 0 ] \\
%  & \le \pr{D}[ y g(x)\le \halftheta ] + \pr{D}[ y g(x) > \halftheta\, |\, y f(x)\le 0 ]
% \pr{D}[ y f(x)\le 0 ] \\
  & \le \pr{D}[ y g(x)\le \halftheta ] + \pr{D}[ y g(x) > \halftheta\, |\, y f(x)\le 0 ].
\end{split}
\end{equation}
Note that the left-hand side does not depend on $g$. 
By taking the expectation over $g\sim Q^N$ (and exchanging the order of expectations 
in the second term on the right-hand side), we arrive at
\begin{equation}
\begin{split}
  \pr{D}[ y f(x)\le 0 ] & \le E_{g\sim Q^N}\left[ \pr{D}[ y g(x)\le \halftheta ]
  \right] \\
  & + E_D\left[ P_{g\sim Q^N}[ y g(x)>\halftheta\, |\,
  y f(x)\le 0 ] \right].
\end{split}
\end{equation}
As discussed above, we are now ready to apply \mbox{Hoeffding's} inequality
(\ref{eq-purehoeff}) with $\epsilon=\theta/2$. For any fixed $(x,y)$ we have
\begin{equation}\label{eq-prefirsthoeff}
  Pr_{g\sim Q^N}[ y g(x)>\halftheta\, |\, y f(x)\le 0 ] 
          \le e^{-\frac{1}{8} N \theta^2},
\end{equation}
so
\begin{equation}\label{eq-firsthoeff}
  \pr{D}[ y f(x)\le 0 ] \le E_{g\sim Q^N}\left[ \pr{D}[ y g(x)\le \halftheta ]
  \right] + e^{-\frac{1}{8} N \theta^2}.
\end{equation}
We would like to apply the PAC-Bayes theorem \ref{th-mcall} to the
right-hand side. For simplicity we stated theorem \ref{th-mcall} for
the common {\em zero-one loss} $I(h(x)\neq y)$, but it holds more generally
for arbitrary binary loss functions (see \cite{McAllester}). Here we use
the loss function $I(y g(x)\leq \theta/2)$. Recall that theorem
\ref{th-mcall} applies for any fixed hypothesis space and ``prior''
distribution. The
hypothesis space here will be ${\cal H}_N$. We use as the ``prior''
the distribution $P^N$ over ${\cal H}_N$, which is constructed from
the prior $P$ over ${\cal H}$ exactly as $Q^N$ is constructed from $Q$
(see (\ref{eq-sample})). It is easy to see that $\KL(Q^N\| P^N) = N
\KL(Q\|P)$.\footnote{Note that this reveals a tradeoff between $N$ and
$\KL(Q\| P)$. Namely, for large $N$, $g\sim Q^N$ will be a close
approximation to the averaging classifier $f$, which keeps
(\ref{eq-prefirsthoeff}) small, but if $\KL(Q\| P)$ is not very small,
$Q^N$ will be rather far from $P^N$ in terms of relative entropy, as a
consequence of the strict factorized forms of the two distributions
(they are constructed using i.i.d.\ samples of size $N$).}

It follows from Theorem \ref{th-mcall} that with probability at least
$1-\delta$ over random choices of $S$, for every $Q$,
\begin{equation}\label{eq-usemcall}
\begin{split}
  & E_{g\sim Q^N}\left[ \pr{D}[ y g(x)\le \halftheta ] \right] \\
& \le E_{g\sim Q^N}\left[ \pr{S}[ y g(x)\le \halftheta ] \right] \\
  & + \sqrt{\frac{N \KL(Q\|P) + \ln m + \ln(1/\delta) + 2}
  {2m-1}}.
\end{split}
\end{equation}
By the same argument as in (\ref{eq-simple}), for every $g\in {\cal H}_N$:
\begin{equation}
\begin{split}
  & \pr{S}[ y g(x)\le \halftheta ] \\
  & \le \pr{S}[ y g(x)\le \halftheta,\; y f(x) >
  \theta ] + \pr{S}[ y f(x) \le \theta ] \\
  & \le \pr{S}[ y g(x)\le \halftheta\, |\,  y f(x) > \theta ] + \pr{S}[ y f(x) \le
  \theta ].
\end{split}
\end{equation}
Again, we take expectations over $g\sim Q^N$ on both sides, interchange the
order of the expectations and apply Hoeffding's inequality (\ref{eq-purehoeff})
with $\epsilon=\theta/2$:
\begin{equation}
  E_S\left[ P_{g\sim Q^N}\left[ y g(x)\le \halftheta\, |\,  y f(x) > \theta
  \right] \right] \le e^{-\frac{1}{8}N\theta^2},
\end{equation}
to arrive at
\begin{equation}\label{eq-secondhoeff}
  E_S\left[ P_{g\sim Q^N}[y g(x)\le \halftheta] \right] \le e^{-\frac{1}{8}N\theta^2}
  + \pr{S}\left[ y f(x)\le \theta \right].
\end{equation}
Combining (\ref{eq-firsthoeff}), (\ref{eq-usemcall}) and
(\ref{eq-secondhoeff}), we conclude that with probability at least $1-\delta$,
for every $Q$
\begin{equation}
\begin{split}
  \pr{D}\left[ y f(x)\le 0 \right] - \pr{S}\left[ y f(x)\le \theta \right]
  \le 2 e^{-\frac{1}{8}N\theta^2} \\
  + \sqrt{\frac{N \KL(Q\|P) + \ln m + \ln(1/\delta) + 2}{2m-1}}.
\end{split}
\end{equation}
This bound holds for any fixed $N$ and $\theta$, 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
$\theta$, namely the probability of each event is smaller than $\delta$.
However, we need to prove that the probability of the {\em union} of all these
events is smaller than $\delta$. To this end, we first observe that this
union is contained in the union over only a {\em countable} number of events.
Note that if $g\in {\cal H}_N$ (see (\ref{eq-sample})), then
$g(x)\in \{(2k-N)/N | k=0,1,\ldots,N\}$. Thus, even with all the
possible (positive) values of $\theta$, there are no more
than $N+1$ events of the form $\{y g(x)\le \theta/2\}$.
Denote by $k(\theta,N)$ the largest integer $k\le N$ such that
$k/N \le \theta/2$. We observe that for every
$\theta>0$, every $g\in {\cal H}_N$ and every distribution over $(x,y)$:
\begin{equation}
  Pr\left[ y g(x)\le \theta/2 \right] = Pr\left[ y g(x)\le k(\theta,N)/N \right].
\end{equation}
This means that the middle step in the proof above, i.e.\ the application of
theorem \ref{th-mcall}, depends on $(N,\theta)$ only through $(N,k)$. Since
the other steps, i.e. the applications of Hoeffding's inequality, 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 $\delta$ to each of these
events, namely $(N,k)$ receives $\delta_{N,k}=\delta/(N(N+1)^2),\; N=1,2,
\dots;\, k=0,\dots,N$. It follows easily that the union of all these events
has probability at most $\sum_{N,k} \delta_{N,k} = \delta$.
Therefore we have proved that with probability at least
$1-\delta$ over random choices of $S$, for {\em all} $N$ and
{\em all} $\theta>0$,
\begin{equation}\label{eq-finalbound}
\begin{split}
  & \pr{D}\left[ y f(x)\le 0 \right] - \pr{S}\left[ y f(x)\le \theta \right] \\
  & \le 2 e^{-\frac{1}{8}N\theta^2} + \sqrt{\frac{N \KL(Q\|P) + \ln m +
  \ln(1/\delta_{N,k}) + 2}{2m-1}} \\
  & \le 2 e^{-\frac{1}{8}N\theta^2} \\ 
        & + \sqrt{\frac{N \KL(Q\|P) + \ln m +
  \ln(1/\delta) + 3 \ln(N+1) + 2}{2m-1}}
\end{split}
\end{equation}
where $k=k(\theta,N)$. The asymptotic bound stated in the theorem can
be derived by choosing $N$ (with respect to $\theta$ and $Q$) so as to
approximately minimize the bound we have derived above.  We can choose
\[ N=\left\lceil 4 \theta^{-2} \ln \frac{m}{\KL(Q||P) + 1}\right\rceil. \]

\section{Implications}\label{sec-implic}

We wish to apply the preceding theory to two general learning methods: Maximum
Entropy discrimination\cite{Jaakkola} and Bayes as well as
Bayes Point Classifiers
\cite{Minka} \cite{Herbrich}.  We choose these two learning methods
because the average in these cases is over many hypotheses, so
that the low order terms in the bound are not very significant. We
begin with a simple toy example that illustrates the bound
application.

\subsection{Example}\label{sec-toyex}
A quick example will illustrate the advantage of the improved bound.
Suppose the input space is ${\cal X} = \{-1,1\}^n$, and let  
${\cal H}= \{h_1,\ldots,h_n\}$, where for every $x=(x_1,\ldots,x_n)\in {\cal X}$,
$h_i(x)=x_i$, $i=1,\ldots,n$. Fix a parameter $0< \theta< 1$.

The setting falls within the naive Bayes probability model.  The
probability distribution $D$ can be described as follows: First, the
value of $y$ is $1$ with probability $0.5$, and $-1$ with probability
$0.5$.  Given $y$, the entries of an instance
$(x_1,\ldots,x_n,y)\in{\cal X}\times\{-1,1\}$ are (conditionally)
independent.  For every $i$, $x_i$ equals $y$ with probability
$\half+\half \theta$, and $-y$ with probability $\half-\half\theta$.

It follows, that for every $i$, $y h_i(x)=1$ (i.e., $h_i$ predicts
correctly) with probability $\half+\half\theta$, so the expected
value of $y h_i(x)$ is $\half+\half\theta-(\half-\half\theta)= \theta$.
Thus, the expected value of
$t(x,y) = \sum_{i=1}^n q_i (yh_i(x))$ is also $\theta$.
For a large number of independent hypotheses, with uniform weights $q_i$, 
the value of $t(x,y)$ is probably approximately $\theta$.

What will the old margin bound suggest using?  The old margin bound
depends purely on the proportion of examples at some margin so it
suggests averaging over the few hypotheses which happen to do better
than expected on this particular sample set.

What does the improved averaging bound suggest?  The improved averaging
bound will include many more hypotheses because it becomes tighter
with a more uniform average over the hypothesis space.

We implemented two quick learning algorithms to explore the
implications of this bound to this problem.

The first algorithm, which motivated the development of the original
margin bound, is Adaboost \cite{Freund}.  Our Adaboost implementation
uses a weak learning algorithm which simply selects the hypotheses
with smallest error under the distribution over examples and we set
the number of rounds to \( 100 \).

The second algorithm is a Gibbs averaging algorithm.  The Gibbs
averaging algorithm picks a weight for each hypothesis proportional
to
\[ e^{e_S(h)/T}\ , \]
where \( T \) is a ``temperature'' parameter.  Motivated by the variance of a
binomial distribution, we set \( T = 1/\sqrt{n} \).  After finding the
weights of all hypotheses we create an averaging classifier by taking
the sign of the expectation with respect to the Gibbs distribution.

In real world examples, the number of hypotheses is typically much
larger than the number of examples so we use examples with $10000$
hypotheses/features and $10$ to $150$ examples.  For all experiments
we set the true margin in data generation to $0.5$.

{\par\centering \resizebox*{0.9\columnwidth}{!}{\rotatebox{270}{\includegraphics{plot.ps}}} \par}

This is a plot of the complexity \( \KL(Q\|P)\) of the averaging
hypotheses returned by Adaboost and Gibbs-averaging versus the number
of examples.  All error bars are at one standard deviation.  

Adaboost just picks one hypothesis (the one which happens to get every
example correct) when the number of examples is small and eventually
limits to a near uniform distribution over as many hypotheses as it
has iterations.  The Gibbs-averaging hypothesis instead always
controls complexity well.  The error bars are very small everywhere
except for 30 and 40 examples where Adaboost suddenly starts using
more then one hypothesis.

This example is arranged so the ``right'' answer is to use every
hypothesis with the same weight.  In general, the goals of complexity
control and error minimization are often opposed and the averaging
bound suggests how to trade off between these goals.

\subsection{Maximum Entropy Discrimination}

Maximum Entropy discrimination (MED) is tailor-made to take advantage
of our new bound. This is especially interesting because it was
proposed before the averaging bound was developed. Consequently, the
application of the the improved averaging bound to the MED framework
provides an additional motivation for its use.

Maximum Entropy discrimination (MED) is founded on Minimum Relative
Entropy discrimination (MRED) which is equivalent to MED when the
prior happens to be uniform. In the MRED paradigm, one starts with
some prior distribution $P$ over the hypothesis space and the goal 
is to find a distribution $Q$ which minimizes the KL-divergence 
$\KL(Q||P)$ to the prior subject to classification constraints (further
explained below). The latter are stated in terms of the expectation 
over \( Q \) of the so-called discriminant function (see below).

For each hypothesis $h$, the discriminant function
$L(x) = L(x|h)$ assigns real numbers to examples $x\in \cal X$.
The value of $L(x|h)$ can be interpreted as a
``confidence-rated'' classification.  Thus, if $L(x|h)$ is large, the
hypothesis $h$ places great confidence on the
classification of $x$ as positive.  

For every $h$, the discriminant function $L(\cdot|h)$ is determined
by a parameter triple $\Theta^h=\{\theta^h_{+},\theta^h_{-},b^h\}$.
It is derived from some parameterized family $P(\cdot|\theta)$ of 
probability distributions over the set $\cal X$. 
The discriminant function is:
\[
L(x|h)=\ln \frac{P(x|\theta^h_{+})}
                {P(x|\theta^h_{-})}
        +b^h \ .
\]
Intuitively, $P(\cdot|\theta^h_{+})$ (resp.\ $P(\cdot|\theta^h_{-})$)
is the posterior distribution over $\cal X$, given a ``positive''
(resp.\ ``negative") classification.  Thus, the discriminant is a
``biased'' (by $b^h$) log-likelihood ratio with respect to the
distributions $P(\cdot|\theta^h_{+})$ and $P(\cdot|\theta^h_{-})$.
Every distribution $Q$ over $\cal H$ induces an average over the
discriminant functions of the individual hypotheses.  The constraints
imposed on \( Q \) guarantee a desired margin $\theta$:
\[ \forall x,y\in S:\,\,y\int_{\cal H}L(x|h)\, dQ(h)\geq \theta \ .\]
Classification is then done in the MED framework by calculating the
expected value of the discriminant function under the distribution $Q$:
\[
c(x)=\mathop{\rm sign} \int_{\cal H}L(x|h)\, dQ(h) \ .
\]
For details on how to find \( Q \) subject to these constraints 
see \cite{Jaakkola}. 

How does our theoretical result apply to MRED? The latter averages
over real-valued discriminant functions $L(x|h)$ instead of binary
hypotheses $h$, as in our setting. As already mentioned above, our
main theorem \ref{th-main} holds also for spaces ${\cal H}$ of {\em
bounded real-valued} hypotheses, without further loss. If the $L(x|h)$
in an MRED application are bounded, our result therefore applies,
using the hypothesis space $\{ L(x|h) | h\in {\cal H} \}$ instead of
${\cal H}$ directly. However, in most MRED applications, the
discriminant functions are not bounded, and an extension of our result
to this case is subject to future work.
%In all applications of MRED we know of, the class of discriminant
%functions {\em is} uniformly bounded if we restrict ourselves to a
%bounded region in ${\cal X}$ where all the data lies with high
%probability. Therefore, even our current result motivates MRED in a
%strong theoretical sense.

The algorithm directly motivated by the averaging bound would be
``Minimum Relative Entropy Classification'' (MREC) which is identical
to the MRED framework except that instead of averaging over
real-valued discrminants the average is done over binary valued
classifiers.  It is unclear whether the MREC criteria is actually
better then the MRED framework in practice for either accuracy or ease
of solution.

\subsection{Bayes and Bayes Point Classifiers}

In the Bayesian approach to classification, given an i.i.d.\ training sample
$S$, a posterior distribution
\( Q \) over the hypotheses is derived according to Bayes law:
\[
  dQ(h) = d\Pr(h | S) = \frac{\Pr(S | h)\, d\Pr(h)}{\int \Pr(S | h)\, d\Pr(h)}
  \ . \]
Here, $\Pr(S | h)$ is the likelihood of the sample $S$, given the hypothesis
$h$, and $\Pr(h)$ is a prior distribution over ${\cal H}$. The classification
for a new example $x$ is done by calculating the expectation over
\( Q \), as in the MRED classifier above:
\[
  c(x)=\mathop{\rm sign} \int_{\cal H} h(x)\, dQ(h)\ .
\]
The Bayes (optimal) classifier is an average over many classifiers, and so our
improved averaging bound applies with a prior $P$, given by $P(h) = \Pr(h)$,
and a ``posterior'' \( Q \), which in this case is the Bayesian posterior
distribution.

One significant drawback of this technique is that it is very often
intractable. Bayes Point classifiers attempt to address this
intractability by finding a {\em single} hypothesis \( h_{BP}(x)\in
{\cal H} \), which is close
to the Bayes (optimal) classifier \( c(x) \). Thus, if
\( h_{BP}(x) \) is a good approximation to \( c(x) \), then the improved
averaging bound will approximately apply to the Bayes Point classifier
as well.

\section{Conclusion and Future Work}

We have presented a simple qualitative improvement to the margin bound, which
motivates the techniques of several learning algorithms and validates the intuition
that ``averaging is good''. There are many directions for interesting future
work including the following:

\begin{enumerate}
\item The improved averaging bound has some messy low order constants, which are probably
removable with an improved argument.
\item Can we give a stronger theoretical motivation of the Maximum Entropy
  discrimination framework with unbounded discriminant functions?
\item Empirical application of the bound. When applying this bound in the boosting
framework, can we get quantitatively interesting results on real world problems?
\end{enumerate}

\subsubsection*{Acknowledgments}

We thank Ralf Herbrich, Chris Williams, Robert Schapire, and David
McAllester for helpful discussions.  MS is supported through a
research studentship from {\em \mbox{Microsoft} \mbox{Research} Ltd}.

\begin{thebibliography}{1}

\bibitem{Bartlett} Peter 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, 1998

\bibitem{Breiman} L.~Breiman, "Bagging Predictors" Machine Learning, Vol. 24, No. 2, pp. 123-140.

\bibitem{Blumer} A.~Blumer, A.~Ehrenfucht, D.~Haussler, and M.~K.\ Warmuth, ``Occam's Razor''
Information Processing Letters, 24:377-380, April 1987

\bibitem{Cheeseman} P.~Chesseman, J.~Kelly, M.~Self, J.~Stutz,
W.\ Taylor, and D.\ Freeman. Autoclass: A Bayesian classification
system. In Proc. Fifth Intl. Conf. Machine Learning, pages 54--64,
1988.

\bibitem{Cover} Thomas Cover and Joy Thomas, ``Elements of Information
Theory'' Wiley, New York 1991

\bibitem{Devroye} L.~Devroye, L.~Gy\"orfi and G.~Lugosi ``Applications
of Mathematics: Stochastic Modelling and Applied Probability''
Springer 1996

\bibitem{Freund} Yoav Freund and Robert E.\ Schapire, ``A Decision
Theoretic Generalization of On-line Learning and an Application to
Boosting'' Eurocolt 1995

\bibitem{Grove} Adam J.\ Grove and Dale Schuurmans ``Boosting in the
limit: Maximizing the margin of learned ensembles'' In Proceedings of
the Fifteenth National Conference on Artificial Intelligence 1998

\bibitem{Herbrich} Ralf Herbrich, Thore Grapel, and Colin Campbell, ``Bayes Point Machines: Estimating
the Bayes Point in Kernel Space'', IJCAI 1999 pages 23-29.

\bibitem{Haussler} David Haussler, Michael Kearns, and Robert
Schapire, ``Bounds on the Sample Complexity of {Bayesian} Learning
Using Information Theory and the {VC} Dimension'', Machine Learning
1994 14:83--113

\bibitem{Jaakkola} T.~Jaakkola, M.~Meila, T.~Jebara, \char`\"{}Maximum Entropy Discrimination\char`\"{}
NIPS 1999.

\bibitem{TR} J.~Langford, M.~Seeger, ``Bounds for Averaging
Classifiers'', Technical report, Carngeie Mellon, 2001, CMU-CS-01-102

\bibitem{Littlestone} Nick Littlestone. Redundant noisy attributes,
attribute errors, and linear threshold
learning using winnow. In COLT-91, pages 147--156, 1991.

\bibitem{McAllester} David McAllester, ``PAC-Bayesian Model Averaging'' COLT 1999

\bibitem{Minka} Thomas Minka, ``Expectation Propagation for approximate Bayesian inference'',
thesis.

\bibitem{Schapire} 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{Shawe-Taylor} John Shawe-Taylor, Peter Bartlett, Robert
Williamson and Martin Anthony, ``A framework for {Structural Risk
Minimization}'', COLT-96 pages 68-76

\bibitem{Zhang} Tong Zhang, ``Analysis of Certain Regularized
Linear Function Classes with Special Emphasis on Classification'', IBM
Research Report RC-21572 

\end{thebibliography}
\end{document}
