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

\documentclass{article}
\usepackage{cmu-titlepage}
\usepackage{epsf}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsopn}
\usepackage{psfig}
\usepackage{graphics}

% --- 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}
\newtheorem{coro}{Corollary}

% --- 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{Bounds for Averaging Classifiers}

\author{
\begin{minipage}[t]{9\unitlength}
\begin{center}
\normalsize\bf John Langford \\
School of Computer Science \\
Carnegie Mellon \\
{\em jcl@cs.cmu.edu} \\
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} \\
www.dai.ed.ac.uk/homes/seeger/
\end{center}
\end{minipage} 
}

\trnumber{CMU-CS-01-102}

\date{January 2001}

\abstract{
We present a generalized PAC bound for averaging classifiers which
applies to base hypotheses with a bounded real valued output.  In
addition, we discuss several methods for quantitatively tightening the
bound.  In the process, a tightened version of the PAC-Bayes bound
\cite{McAllester} is proved.
}

\keywords{PAC bound, Maximum entropy discrimination, averaging hypotheses}

\begin{document}
%\pagestyle{empty}

\maketitle

% --- Abstract ---

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

The improved averaging bound arises from improving one critical step in
the proof of the original margin bound, which we state here for
reference.  We denote by $\pr{D}$ the probability measure of the
distribution $D$ defined above.  For any set $S$ of examples, we
denote by $\pr{S}$ the uniform probability distribution over the set
$S$.

\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}
  \pr{D}[ y f(x)\le 0 ] \le \pr{S}[ y f(x)\le \theta ] 
  + O\left(
      \sqrt{\frac{\theta^{-2} \ln |{\cal H}|  \log m + \ln\delta^{-1} }
           {m}} 
    \right),
\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, also called ``discriminants'',
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
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
\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$ iff $Q=P$ almost everywhere.

\begin{theo}[PAC-Bayes \cite{McAllester}]\label{th-mcall}
Let $l(h,(x,y))$ be a binary loss function, $P$ 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}$:
\begin{equation}
  \pr{{D,Q}}[l(h,(x,y))=1] \leq \pr{{S,Q}}[l(h,(x,y))=1]
  +\sqrt{ \frac{\KL(Q\|P) +\ln\delta^{-1} +\ln m+2}{2m-1} }
\end{equation}
\end{theo}

An example of a loss function is the well-known {\em zero-one loss}
$l(h,(x,y)) = I_{\{h(x)\ne y\}}$.

We can tighten this bound by employing a more accurate tail bound on
the Binomial distribution, which leads us to the following theorem.

\begin{theo}
(PAC-Bayes Relative Entropy bound)\label{th-pbr} 
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}$:

\[
\KL(Ber_{S,Q}\|Ber_{D,Q})\leq \frac{\KL(Q\|P)+\ln \frac{2m}{\delta
}}{m-1}\]
where $Ber_{S,Q} = 1$ with probability $ \pr{S,Q}(l(h,(x,y))=1) $ and $
0 $ otherwise, and $Ber_{D,Q} = 1$ with probability $
\pr{D,Q}(l(h,(x,y))=1)$ and $0$ otherwise.

\end{theo}

This theorem gives a constraint on the KL divergence between the
average empirical and average true errors rather then the standard
$l_1$ distance.  This bound is always at least as tight as the
original PAC-Bayes bound \cite{McAllester} and sometimes much tighter,
such as when the average empirical error is near $0$.  A proof is
given in section \ref{sec-improve}.

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}
  \pr{D}[ h(x) \ne y ] \le \pr{S}[ h(x)\ne y ] 
   + \sqrt{ \frac{ \ln(1/p(h)) + \ln\delta^{-1} }
                 {2 m} 
          }\ .
\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-pbr}, where we
choose delta distributions $Q=(0,\dots,0,1,0,\dots,0)$ in theorem
\ref{th-pbr} and upper bound the KL divergence with the hoeffding
bound.  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{A generalized averaging bound}\label{sec-main}

In this section, we state and prove our main result, a PAC-Bayes
generalization error bound for averaging {\em bounded real-valued}
hypotheses. Averaging binary hypotheses, with which we have been
concerned with so far, is a special case for which we do not have to
sacrifice any accuracy for the generalization.

Within this section, let $A>0$, and let $\tilde{\cal H}$ be a set of
real-valued hypotheses $h: {\cal X}\to [-A,A]$. If $Q$ denotes a
distribution
over $\tilde{\cal H}$, we focus on the average classifier
$c(x) = \textrm{sign} f(x)$ where $f(x)=E_{h\sim Q}[h(x)]$.

\begin{theo}[Relative Chernoff Main theorem]\label{th-relmain}
Let $P$ be any probability distribution over $\tilde{\cal H}$ and
let $\delta\in (0,1)$. With probability at least $1-\delta$ over random
samples $S$ of $D$ we have that for all $\theta\in (0,1]$ and for every
distribution $Q$ over $\tilde{\cal H}$:
\begin{equation}
\eqalign{
  \KL (\pr{S}\left[ y f(x)\le \theta A \right] || \pr{D}& \left[ y f(x)\le 0 \right] ) \cr
  &\leq O \left(\frac{\theta^{-2} \KL(Q\|P) \ln m + \ln m 
                           +  \ln \delta^{-1} 
                          }{m}
        \right)
\cr }
\end{equation}
where $f(x)=E_{h\sim Q}[h(x)]$.
\end{theo}

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.

\[ D(p||q) \geq 2(p-q)^2 \]

This relaxation gives us an immediate corollary.

\begin{coro}\label{th-corrmain}
Let $P$ be any probability distribution over $\tilde{\cal H}$ and
let $\delta\in (0,1)$. With probability at least $1-\delta$ over random
samples $S$ of $D$ we have that for all $\theta\in (0,1]$ and for every
distribution $Q$ over $\tilde{\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 A
\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{coro}

The proof of the theorem is given in \ref{sec-main-proof}. Note that
the theorems are stated in an asymptotic fashion which may not be very
useful in practical applications. Section \ref{sec-tighten} gives some
ideas of how to tighten the result, and the nonasymptotic form, given
by the inequalities (\ref{eq-finalbound}) can be used directly in
practice.

The continuous form of the improved averaging bound applies to
averages over continuous hypothesis spaces. Note that in this setting,
the average needs to be an integral over an uncountably-infinite set
of hypotheses or 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
Relative Chernoff PAC-Bayes theorem \ref{th-pbr}.

First of all, it is clear that we only have to prove the theorem for the
case $A=1$. Let $N$ be any natural number; later, the choice of $N$
will be optimized. In the first part of the proof, we regard $\theta$ 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\sim Q$ and $N$ variables
$u_i\sim U([-1,1])$ (here, $U(I)$ denotes the uniform distribution over
the
interval $I$) such that $h_1,u_1,\dots,h_N,u_N$ are mutually
independent. $Q_N$ might therefore be viewed as the product distribution
\begin{equation}
  \left( Q\times U([-1,1]) \right)^N.
\end{equation}
Define the binary valued functions $\phi_i: {\cal X}\to \{-1,+1\}$ by
\begin{equation}
  \phi_i(x;\, h_i,u_i) = 2 I_{\{u_i\le h_i(x)\}} - 1.
\end{equation}
Given the $h_i$ and $u_i$ we define
\begin{equation}\label{eq-sample}
  g(x) = \frac{1}N \sum_{i=1}^N \phi_i(x;\, h_i,u_i).
\end{equation}
The set of all such functions $g$ is
\begin{equation}\label{eq-cnset}
  \tilde{\cal H}_N = \left\{ \frac{1}N \sum_{i=1}^N \phi_i(x;\, h_i,u_i)\;
  \Biggl| \Biggr. h_i\in \tilde{\cal H},u_i\in [-1,1] \right\}.
\end{equation}
$Q_N$ therefore induces a distribution over $\tilde{\cal H}_N$, this will
be
denoted by $g\sim Q_N$. Note that for fixed $x,\, y$, the $y \phi_i(x;\,
h_i,u_i)$ are i.i.d.\ Bernoulli variables with mean
\begin{equation}
\begin{split}
  E_{h_i,u_i}\left[ y \phi_i(x;\, h_i,u_i) \right] & = y E_{h_i}\Bigl[
  (+1) P_{u_i}\left[ u_i\le h_i(x)\, \Bigl|\, h_i \right] \\
  & + (-1) P_{u_i}\left[ u_i > h_i(x)\, \Bigl|\, h_i \right] \Bigr] \\
  & = y E_{h_i}\left[ \frac{1}2 (1+h_i(x)) - \frac{1}2 (1-h_i(x)) \right]
\\
  & = y E_{h_i} \left[ h_i(x) \right] = y f(x),
\end{split}
\end{equation}
therefore $E_{g\sim Q_N}[ y g(x) ] = y f(x)$. Since $y 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 probability with respect to the sampling of $g\sim
Q_N$
satisfies
\begin{equation}\label{eq-basichoeff}
  \pr{g\sim Q_N}[ y (g(x)-f(x)) > \epsilon ]\leq e^{-\frac{1}{2} N
\epsilon^2}
\end{equation}
For every $\theta\in (0,1]$ and for every (fixed) $g\in \tilde{\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 Hoeffding's inequality
(\ref{eq-basichoeff}) with $\epsilon=\theta/2$. For any fixed $(x,y)$ we
have
\begin{equation}\label{eq-prefirsthoeff}
  P_{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-pbr} to the
right-hand side. For simplicity we stated theorem \ref{th-pbr} for
the common {\em zero-one loss} $I_{\{h(x)\neq y\}}$, but it holds more
generally for arbitrary binary loss functions. Here
we use the loss function $I_{\{y g(x)\leq \theta/2\}}$. Recall that
theorem
\ref{th-pbr} applies for any fixed hypothesis space and ``prior''
distribution. The hypothesis space here will be $\tilde{\cal H}_N$. We use
as
the ``prior''
the distribution $P_N$ over $\tilde{\cal H}_N$, which is constructed from
the prior $P$ over $\tilde{\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-pbr} that with probability at least
$1-\delta$ over random choices of $S$, for every $Q$,

\begin{equation}\label{eq-usemcall}
\KL(Ber_{S,Q_N}\|Ber_{D,Q_N})\leq \frac{\KL(Q_N\|P_N)+\ln \frac{2m}{\delta
}}{m-1}
\end{equation}
where $Ber_{S,Q_N} = 1$ with probability $ E_{g\sim Q_N}\left[ \pr{D}[ y
g(x)\le \halftheta ] \right] $ and $
0 $ otherwise, and $Ber_{D,Q_N} = 1$ with probability $E_{g\sim Q_N}\left[
\pr{S}[ y g(x)\le \halftheta ] \right] $ and $0$ otherwise.

By the same argument as in (\ref{eq-simple}), for every
$g\in \tilde{\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-basichoeff}) 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}
  \KL(q_S\|p_D)\leq \frac{N\KL(Q\|P)+\ln \frac{2m}{\delta }}{m-1}
\end{equation}
where $q_S = 1$ with probability $ e^{-\frac{1}{8}N\theta^2} +
  \pr{S}\left[ y f(x)\le \theta \right] $ and $ 0 $ otherwise, and
  $p_D = 1$ with probability $ \pr{D}[ y f(x)\le 0 ] - e^{-\frac{1}{8}
  N \theta^2} $ and $0$ otherwise.

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 \tilde{\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$ such that
$k/N \le \theta/2$. We observe that for every
$\theta>0$, every $g\in \tilde{\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-pbr}, 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$ it holds true that for {\em all} $N$
and
{\em all} $\theta\in (0,1]$,
\begin{equation}\label{eq-finalbound}
\begin{split}
  \KL(q_S\|p_D) & \leq \frac{N\KL(Q\|P)+\ln \frac{2m}{\delta_{N,k} }}{m-1}
\\
        & \leq \frac{N\KL(Q\|P)+\ln \frac{2m}{\delta} + 3 \ln N+1 }{m-1}
\end{split}
\end{equation}
where $k=k(\theta,N)$. We can now choose $N$ such as to minimize this
bound.
$N$ may depend on $\theta,\, Q$ and the sample $S$.

The asymptotic bound stated in the theorem can be derived by choosing $N$
(with respect to $\theta$ and $Q$) so as to {\em approximately} minimize
the
bound we have derived above. If $c\ge 1$ is such that $D(Q\| P)=O(m^c)$,
we
can choose
\[ N=\left\lceil 8 \theta^{-2} \ln \frac{m^c}{\KL(Q\|P)}\right\rceil. \]

This choice gives us:

\[ e^{-\frac{N\theta ^{2}}{8}} = \frac{D(Q\|P)}{m^c} \]

Which implies we have an equation of the form:

\begin{equation}
\begin{split}
 & D(q\|p)+D(q+\frac{D(Q||P)}{m^c}\|p-\frac{D(Q\|P)}{m^c})-D(q||p) \\
 & \leq O\left( \frac{\theta ^{-2}D(Q\|P)\ln m+\ln \frac{1}{\delta }+\ln
m}{m} \right) 
\end{split}
\end{equation}

In order to prove the theorem, we must show that the second and third
terms together are of a similar size to the last term.  The second and
third terms have 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:

\( =\Theta [(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}]
\)

\( =\Theta [(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}] \)

\( =\Theta [(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}] \)

\( =\Theta [k(1+p)-k(2-p)] \)

\( =\Theta [k] \)

This completes the proof of the main theorem.

\section{Methods for tightening}\label{sec-tighten}

The previous section showed a bound in asymptotic form which is good
for understanding the tradeoffs between the number of examples (\( m
\)), the size of the hypothesis space (\( |H| \)), the margin (\(
\theta \)) 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:

\begin{enumerate}
\item Making direct use of the tail distribution for the Binomial.
\item Parameterizing and then optimizing the parameterization of
arbitrary choices within the proof.
\item Tighter argument within the proof.
\end{enumerate}

\subsection{Binomial Tail Bounds}

The direct use of the tail distribution of the Binomial will rely upon the
cumulative
distribution of the Binomial. Let 

\[ Bin(m,p,\hat{p})=\sum _{i=0}^{\frac{i}{m}<\hat{p}}\left(
\begin{array}{c}
m\\
i
\end{array}\right) p^{i}(1-p)^{i} \] 
be the cumulative distribution of a Binomial distribution with true error
\( p \)
up to empirical error \( \hat{p} \). We then have the following equality:
\[
\pr{Bin(m,p)}(p-\epsilon >\hat{p})=Bin(m,p,p-\epsilon )\]
This inequality can be much tighter then the corresponding Hoeffding
bound: 
\[
\pr{Bin(m,p)}(p-\epsilon >\hat{p})\leq e^{-2\epsilon ^{2}m}\]


In using the tail probabilities, it will often be the case that we
want a constant probability of failure (\( \delta \)) and want to
solve for the smallest \( \epsilon \) which has a probability of
failure of \( \delta \) or less. This bound can't be stated concisely
in closed form but can be found moderately quickly by doing a binary
search over \( \epsilon \) to solve for the \( \epsilon \) with our
desired \( \delta \). The binary search solves for the value of \( p
\) s.t. \( Bin(m,p,\hat{p})=\delta \).  We have the equality:
\[
\pr{Bin(m,p)}(\hat{p}|p \geq \max \bar{p}:Bin(m,\bar{p},\hat{p})\geq
\delta ) \leq \delta \]


This equality implies that with probability \( 1-\delta  \), we have: \(
p\leq \max \bar{p}:Bin(m,\bar{p},\hat{p})\geq \delta  \).

The computational cost of calculating the Binomial tail distribution is
often
too large so it is possible to use an intermediate approximation known as
the
relative entropy chernoff bound:
\begin{equation}
\label{eqn:relent-prelim}
\pr{Bin(m,p)}(p-\epsilon >\hat{p})\leq e^{-m\KL(p-\epsilon \|p)}
\end{equation}
\begin{equation}
\label{eqn:relent-prelim_2}
\pr{Bin(m,p)}(p+\epsilon >\hat{p})\leq e^{-m\KL(p+\epsilon \|p)}
\end{equation}
where \( \KL(q\|p) \) is the KL divergence between a coin with a bias of
\( q \)
and a coin with a bias of \( p \).

\subsection{Extra parameterizations}

In the (improved) margin bound proof, we arbitrarily decided to work with
the
margin of the randomly produced function \( g(x) \) at \( \frac{\theta
}{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.


\subsection{PAC-Bayes bound vs. the standard Occam's razor bound}

In the finite case, there are some low order terms in the PAC-Bayes bound
which
can make it worse then the Occam's razor bound when the posterior is over
a
small set of hypotheses. Ideally, we would improve the low order terms in
the
PAC-Bayes bound to remove this discrepancy, but this appears difficult.
Instead,
we can apply another simple technique: When there are two PAC bounds
either
of which may be tighter, we can assign \( \delta \rightarrow \frac{\delta
}{2} \)(slightly
worsening the bound) to each bound and use the minimum of the two bounds.
Since
the probability of failure for each bound is \( \frac{\delta }{2} \), the
total
probability of failure of the minimum is \( \delta  \).

\subsection{Optimizing $N$}

The optimal value of $N$ is a function of $\theta, m, \KL(Q\|P),$ and
$\delta$.  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 stratify over the
possible values of $N$ and we need only stratify over the values of
$\theta$ in proving the bound.  The effect of this improvement is
reducing $1/\delta_{N,k} = 1/(N(N+1)^2)$ to $1/\delta_{N,k} =
1/(N(N+1))$ giving us a small improvement in the low order terms of
the improved averaging bound.

\section{Improving the PAC-Bayes bound}\label{sec-improve}

In order to fully benefit from the improved Chernoff bound we need to
prove \ref{th-pbr} using the Chernoff relative entropy bound.  The
retrofit of the PAC-Bayes bound is not a simple substitution of the
Hoeffding inequality with the Chernoff relative entropy bound so a
proof is given.

The proof of the improved PAC-bayes theorem (\ref{th-pbr})
relies upon two lemmas. The first is Lemma 22 from \cite{McAllester}
which is given by:

\begin{lemma}
\label{lem:helper2}For \( \beta >0,K>0 \) and \( Q,P,y\in R^{n} \)
satisfying
\( P_{i}>0,Q_{i}>0, \) and \( \sum _{i}Q_{i}=1 \), if 
\[
\sum _{i=1}^{n}P_{i}e^{\beta y_{i}}\leq K\]
 then 
\[
\sum _{i=1}^{n}Q_{i}y_{i}\leq \frac{\KL(Q\|P)+\ln K}{\beta }\]
\end{lemma}

The second lemma we will need to prove ourselves. It is basically an
improved
version of Lemma 17 from \cite{McAllester}.

\begin{lemma}
\label{lem:helper1} 
\[
\forall \delta >0\; \forall ^{\delta }S\; \; \; E_{h\sim
P}e^{(m-1)\KL(\hat{e}(h)\|e(h))}\leq \frac{2m}{\delta }\]
\end{lemma}

First, for any given hypothesis \( h \) we prove the following. 
\begin{equation}
\label{eqn:expectation}
E_{S}[e^{(m-1)\KL(\hat{e}(h)\|e(h))}]\leq 2m
\end{equation}
 Lemma~\ref{lem:helper1} follows from (\ref{eqn:expectation}) by
taking an expectation over selecting \( h \) according to any
distribution \( P \) over \( h \), reversing the two expectations, and
applying Markov's inequality.  We now show that
(\ref{eqn:expectation}) follows from (\ref{eqn:relent-prelim}) and
(\ref{eqn:relent-prelim_2}). More specifically, we maximize \( \int
_{0}^{1}e^{(m-1)\KL(x\|p)}f(x)dx \) over all functions \( f(x) \)
satisfying the following for all \( q_{1}\geq e(h) \) and \( q_{2}\leq
e(h) \).
\[
\int _{q_{1}}^{1}f(x)dx\leq e^{-m\KL(q_{1}\|e(h))}\]
 
\[
\int _{0}^{q_{2}}f(x)dx\leq e^{-m\KL(q_{2}\|e(h))}\]
 The value of \( E_{S}[e^{(m-1)\KL(\hat{e}(h)\|e(h))}] \) must be less
than this
maximum. The integral \( \int _{0}^{1}e^{(m-1)\KL(x\|e(h))}f(x)dx \) is
maximized
when \( f(x) \) is as ``spread out'' as possible, i.e., when the above
inequalities
are replaced by equalities. This gives the following. 
\[
f(x)=\left\{ \begin{array}{ll}
m\frac{\partial \KL(x\|p)}{\partial x}e^{-m\KL(x\|p)} & \mbox {for}\;
x\geq p\\
 & \\
-m\frac{\partial \KL(x\|p)}{\partial x}e^{-m\KL(x\|p)} & \mbox {for}\;
x\leq p
\end{array}\right. \]
 Which, in turn, gives the following. 
\begin{eqnarray*}
E_{S}[e^{(m-1)\KL(\hat{e}(h)\|e(h))}] & \leq  & \int
_{0}^{1}e^{(m-1)\KL(x\|e(h))}f(x)dx\\
 &  & \\
 & = & \int _{0}^{e(h)}-m\frac{\partial \KL(x\|e(h))}{\partial
x}e^{-\KL(x\|e(h))}dx \\
 & + & \int _{e(h)}^{1}m\frac{\partial \KL(x\|e(h))}{\partial
x}e^{-\KL(x\|e(h))}dx\\
 & \leq  & 2m
\end{eqnarray*}

Now we have the necessary lemmas to finish the proof of \ref{th-pbr}.

By Jensen's inequality, we have: 

\[ \KL(E_{h\sim Q}\hat{e}(h)\|E_{h\sim Q}e(h))\leq E_{h\sim
Q}\KL(\hat{e}(h)\|e(h)) \]
Furthermore, according to Lemma~\ref{lem:helper1} we can apply
Lemma~\ref{lem:helper2}
with \( K=\frac{2m}{\delta } \) and \( \beta =m-1 \) and \(
y_{i}=\KL(\hat{e}(h)\|\hat{e}(h)+\epsilon ) \)
to get:
\[
E_{h\sim Q}\KL(\hat{e}(h)\|e(h))=\sum
_{i=1}^{n}Q_{i}\KL(\hat{e}(h)\|\hat{e}(h)+\epsilon )\leq
\frac{\KL(Q\|P)+\ln \frac{2m}{\delta }}{m-1}\]
 and we are done.

\section{Conclusion and Future Work}

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

\begin{enumerate}
\item Remove the low order terms from the bound to make it more
quantitatively applicable.  
\item Improve the argument to take into account the {\em distribution}
of the margin rather then the margin at some point.
\item 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.
\end{enumerate}


\end{document}
