%% This LaTeX-file was created by <jl> Tue Apr  9 22:29:45 2002
%% LyX 1.0 (C) 1995-1999 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{amsart}
\usepackage[T1]{fontenc}
\usepackage{graphics}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}
%% Special footnote code from the package 'stblftnt.sty'
%% Author: Robin Fairbairns -- Last revised Dec 13 1996
\let\SF@@footnote\footnote
\def\footnote{\ifx\protect\@typeset@protect
    \expandafter\SF@@footnote
  \else
    \expandafter\SF@gobble@opt
  \fi
}
\expandafter\def\csname SF@gobble@opt \endcsname{\@ifnextchar[%]
  \SF@gobble@twobracket
  \@gobble
}
\edef\SF@gobble@opt{\noexpand\protect
  \expandafter\noexpand\csname SF@gobble@opt \endcsname}
\def\SF@gobble@twobracket[#1]#2{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\theoremstyle{plain}    
\newtheorem{thm}{Theorem}[section]
\numberwithin{equation}{section} %% Comment out for sequentially-numbered
\numberwithin{figure}{section} %% Comment out for sequentially-numbered
\theoremstyle{plain}    
\newtheorem{cor}[thm]{Corollary} %%Delete [thm] to re-start numbering
\theoremstyle{plain}    
\newtheorem{lem}[thm]{Lemma} %%Delete [thm] to re-start numbering
\theoremstyle{plain}    
\newtheorem{algorithm}[thm]{Algorithm} %%Delete [thm] to re-start numbering
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\theoremstyle{definition}
 \newtheorem{problem}[thm]{Problem}
\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}

\makeatother

\begin{document}


\title{Introductory Learning Theory}


\author{John Langford}

\begin{abstract}
This is an introduction to basic learning theory in the setting of classical
statistics. In addition, we discuss simple practical techniques for tightening
general learning theory bounds and show their use. Some notes on computational
tricks are included.
\end{abstract}
\maketitle

\section{Formal Model}

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

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

\begin{defn}
(True error) The true error \( e_{D}(h) \) of a hypothesis \( h \) is defined
in the following way:
\[
e_{D}(h)=\Pr _{D}(h(x)\neq y)\]

\end{defn}
Unfortunately, the true error is not an observable quantity in our model because
the distribution, \( D \), is unknown. However, there is a related quantity
which is observable. 

\begin{defn}
(Empirical Error) Given a sample set \( S \), the \emph{empirical error}, \( \hat{e}_{S}(h) \)
is defined as: 
\[
\hat{e}_{S}(h)=\Pr _{S}(h(x)\neq y)=\frac{1}{m}\sum _{i=1}^{m}I(h(x_{i})\neq y_{i})\]
 where \( I() \) is a function which maps ``true'' to \( 1 \) and ``false''
to \( 0 \). Here \( \Pr _{S}(...) \) is a probability taken with respect to
the uniform distribution over the set of examples, \( S \).
\end{defn}

\section{Basic observations}

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

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

\begin{defn}
(Binomial Distribution) The Binomial distribution is given by:
\[
\Pr _{\{0,1\}^{m}}\left( \hat{p}=\frac{k}{m}|p\right) =\binom{m}{k}p^{k}(1-p)^{m-k}\]
Here we use 'choose' notation defined by \( \binom{m}{k}=\frac{m!}{(m-k)!k!} \). 
\end{defn}

\subsection{The Basic Building Block}

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

\begin{defn}
(Binomial Tail) 
\[
\textrm{Bin}(m,k,p)\equiv \Pr _{\{0,1\}^{m}}\left( \hat{p}\leq \frac{k}{m}|p\right) =\sum _{j=1}^{k}\binom{m}{j}p^{j}(1-p)^{m-j}\]
= the probability that \( m \) coins with bias \( p \) produce \( k \) or
fewer heads.
\end{defn}
For the learning problem, we will always choose \( p=e_{D}(h) \) and \( \hat{p}=\hat{e}_{S}(h) \).
With these definitions, we can interpret the Binomial tail as the probability
of an empirical error less than or equal to \( \frac{k}{m} \).


\subsection{Binomial Tail calculation techniques}

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

The answer is: not very fast. It is an open problem to calculate \( \binom{m}{k} \)
in time not exponential in \( \log m \) and \( \log k \) (the representation
length of \( m \) and \( k \)). In general, this problem is intractable. For
example, we note that 
\[
\binom{m}{\frac{m}{2}}\simeq \frac{2^{m}}{\sqrt{m}}\]
 which has an asymptotic representation length of \( O(m) \). Since it takes
\( O(m) \) time to write the answer, we can not hope to compute the answer
in less than \( O(m) \) time. The problem is more difficult than this though
- even calculating the most significant bits of the appears to take \( O(m) \)
time.

Our real goal is not merely calculating binomial coefficients but rather calculating
the probability of a tail, \( \textrm{Bin}(m,k,p) \). How can we calculate
the tail probability quickly? For all approaches, it is necessary to calculate
\( \log \textrm{Bin}(m,k,p) \) rather than \( \textrm{Bin}(m,k,p) \) to avoid
underflow issues. This is generally possible because we can calculate \( \log (a+b) \)
given \( \log (a) \) and \( \log (b) \) without losing precision.

There are several possible approaches of increasing sophistication:

\begin{enumerate}
\item Calculate \( \binom{m}{i} \) independently from \( i=0 \) to \( i=k \) and
use the results to calculate the sum, \( \sum ^{k}_{i=0}\binom{m}{i}p^{i}(1-p)^{m-i} \). 
\item Calculate Pascal's triangle and extract the Binomial coefficients.
\item Use the fact that 
\[
\binom{m}{i+1}=\frac{m!}{(m-i-1)!(i+1)!}\]
\[
=\frac{m-i}{i+1}\frac{m!}{(m-i)!i!}=\frac{m-i}{i+1}\left( \begin{array}{c}
m\\
i
\end{array}\right) \]

\item Calculate \( \binom{m}{k} \) directly and then \( \binom{m}{i-1} \) given
\( \binom{m}{i} \) until the added quantity falls below the machine precision. 
\end{enumerate}
Approaches (1) and (2) both require \( O(m^{2}) \) work while approaches (3)
and (4) require merely \( O(m) \) work. We will use approach (4) here. Yet,
as noted in the beginning of this section, \( O(m) \) is still sometimes too
expensive for us. Luckily, there exist some quick approximations which can reduce
the computation to constant time (or \( O(\log m) \) time depending on your
computational model).


\subsection{Approximation techniques}

\label{sec-approximation}

Exact calculation of \( \textrm{Bin}(m,k,p) \) can require computation at least
proportional to \( m \), which is often too expensive. For the bounds in this
thesis, we will only need to calculate an upper bound on the quantity \( \textrm{Bin}(m,k,p) \).
There are several inequalities which are often used. The first of these is the
Hoeffding inequality\cite{Hoeffding}. Assume that \( \frac{k}{m}<p \) then
we have:
\[
\textrm{Bin}(m,k,p)\leq e^{-2m\left( p-\frac{k}{m}\right) ^{2}}\]
Intuitively, this inequality can be seen as fitting a gaussian to the Binomial
distribution with \( p=\frac{1}{2} \). For any particular \( m \), the variance
of the Binomial distribution is maximized when \( p=\frac{1}{2} \). Therefore,
the Hoeffding inequality is relatively tight when \( p=\frac{1}{2} \). Unfortunately,
the Hoeffding approximation is not tight enough for our purposes. In machine
learning, our goal is to find a hypothesis with a true error rate far away from
\( \frac{1}{2} \) where the Hoeffding inequality becomes loose. 

There is another bound known as the ``realizable bound'' which applies only
when \( k=0 \). The realizable bound is:
\[
\textrm{Bin}(m,0,p)=(1-p)^{m}\leq e^{-mp}\]
 The realizable bound is noticeably tighter with an exponent proportional to
\( \left| p-\frac{k}{m}\right|  \) rather than \( \left( p-\frac{k}{m}\right) ^{2} \).
The disadvantage of the realizable bound is that it only applies to a very limited
setting - when our empirical error rate happens to be \( 0 \). 

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

\begin{equation}
\label{eq-recb}
\textrm{Bin}(m,k,p)\leq e^{-m\textrm{KL}\left( \frac{k}{m}||p\right) }
\end{equation}
Here \( \textrm{KL}(q||p)=q\ln \frac{q}{p}+(1-q)\ln \frac{(1-q)}{(1-p)} \)
is the KL-divergence between a coin of bias \( q \) and another coin of bias
\( p \). The relative Chernoff bound is as tight as the Hoeffding bound when
\( p \) is near \( \frac{1}{2} \) and as tight as the realizable bound when
\( k=0 \). In between the extremes, the relative Chernoff bound smoothly interpolates
between these possibilities.

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

\begin{enumerate}
\item Sometimes, a different approach to producing a bound will appear better than
previous approaches, but the apparent benefit can simply be traced to the use
of a tighter bound on \( \textrm{Bin}(m,k,p) \).
\item The bounds presented here will all be immediately applicable to direct calculation. 
\item We avoid the need to state two versions of the same theorem: once for the realizable
(\( 0 \) empirical error) case and once for the agnostic (arbitrary empirical
error) case.
\end{enumerate}
The principle \emph{dis}advantage of this approach is that both the relative
entropy Chernoff bound and \( \textrm{Bin}(m,k,p) \) are not analytically invertible.
Lack of invertibility is a theoretical disadvantage because it means we can
not easily parameterize our ``precision'' paremeter, \( \epsilon  \) in terms
of \( \delta  \). Nonetheless, this is not a severe computational disadvantage
because the quantity \( \textrm{Bin}(m,k,p) \) is convex in \( p \) implying
that a binary search is capable of solving the inequality. The process of (and
need for) inversion is discussed next.


\subsection{Converting to a P-value approach}

\label{sec-pvalue}

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

Functionally, instead of calculating:
\[
\textrm{Bin}(m,k,p)=\delta \]
we want to invert the output, \( \delta  \), with respect to the input, \( p \).
Since \( p \) and \( \delta  \) are monotonically related to each other, this
inversion can be defined as:
\[
\bar{e}(m,k,\delta )\equiv \max _{p}\left\{ p:\, \, \textrm{Bin}(m,k,p)=\delta \right\} \]


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

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

\begin{lem}
\label{lem-inversion}(Inversion Lemma) For all predicates, \( \phi (X) \)
\[
\sup _{P}\Pr _{X\sim P}(\phi _{P}(X))\leq \delta \Rightarrow \forall P\, \, \Pr _{X\sim P}(\phi _{P}(X))\leq \delta \]

\end{lem}
This lemma is the trivial statement that a set of objects is less than the \( \sup  \)
over the set of objects. Nonetheless, it is a very important step which will
appeal to implicitly and explicitly later on.

\begin{proof}
By contradiction. Assume there exists \( P \) such that the right hand side
is not satisfied. Then, the left hand side can not be correct.
\end{proof}
The Inversion lemma allows us to implicitly parameterize \emph{all} precision
parameters \( \epsilon (\delta ) \) in terms of a fixed probability of failure,
\( \delta  \). This is important for practical application because it means
we can choose our probability of failure \( \delta  \) before looking at any
examples.
\begin{figure}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\rotatebox{270}{\includegraphics{thesis/bound_plot.ps}}} \par}


\caption{\label{fig-bounds}A plot of the difference between the true error upper bound
and the empirical error for various Binomial tail bound approximations. Here
\protect\( m=1000\protect \) coins of an unknown bias are used and a confidence
of \protect\( \delta =0.1\protect \) and the horizontal axis is the number
of errors between \protect\( k=0\protect \) and \protect\( k=1000\protect \).
The relative entropy approximation to the Binomial tail is relatively well behaved
while the Hoeffding approximation is not. In particular, the Hoeffding approximation
does not take into account the decreased variance of low bias Binomials. }

Note that the dip at the end of the Hoeffding bound is due to the fact that
the true error rate is \emph{always} less than \( 1 \).
\end{figure}



\subsection{Bounding the Union}

\label{sec-union} One very common technique we will use is the union bound
(known as the Bonferroni bound in statistics). Given two coins, each with a
bias (probability of heads) of \( p \), what is the probability that if we
flip each coin \( m \) times, one of the coins will have \( k \) or fewer
heads? 

Let \( X_{1} \) = the proportion of heads in the first coin flip and \( X_{2} \)
= the proportion of heads in the second coin flip. Then we get: 
\[
\Pr \left( X_{1}\leq \frac{k}{m}\textrm{ or }X_{2}\leq \frac{k}{m}\right) \]
\[
\leq \Pr \left( X_{1}\leq \frac{k}{m}\right) +\Pr \left( X_{2}\leq \frac{k}{m}\right) \]
where the inequality is known as the union bound. This step is very applicable
because it works even when the values of \( X_{1} \) and \( X_{2} \) are correlated
in arbitrary ways.

The union bound is the fundamental tool which allows us to reason about multiple
hypotheses, each with possibly correllated empirical errors, \( X_{1}=\hat{e}_{S}(h_{1}) \)
and \( X_{2}=\hat{e}_{S}(h_{2}) \). The use (and avoidance of the use) of the
union bound is a constant issue.


\subsection{Arbitrary Loss functions}

A loss function is \emph{any} function which takes a hypothesis, \( h \), and
an example \( (x,y) \) as input then outputs a real number. In particular,
we could choose \( l(h,(x,y))=I(h(x)\neq y) \) and regard most of the prior
discussion as working with a specialized hamming loss function which is \( 1 \)
when \( h(x)\neq y \) and \( 0 \) otherwise. Many other possibilities exist.
For any bounded loss function, \( l(h,(x,y))\in [0,1] \), we can define: 
\[
e_{D}(h)=E_{D}l(h,(x,y))\]
and 
\[
\hat{e}_{S}(h)=E_{S}l(h,(x,y))\]
All of the bounds reported here will apply for loss functions bounded on the
interval \( [0,1] \). The fundamental advantage that this gives us is the ability
to treat the hypothesis \emph{not} as a black box. Instead, we can derive a
bound with a loss function dependent on the structure of the hypothesis (as
in margin bounds). 

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


\section{Simple Sample Complexity bounds}

The observations presented in this chapter are mostly ``common knowledge''
in the learning theory community. The goal of this chapter is to introduce basic
common learning theory which the remainder of the thesis will depend upon. 


\subsection{Simple Holdout}

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

\begin{thm}
\label{th-hb}(Holdout Sample Complexity) Let \( \hat{e}_{\textrm{test}}(h) \)
be the empirical error on the test set and \( e_{D}(h) \) be the true error
rate of the hypothesis, then we have: 
\[
\forall h\, \, \Pr _{D^{m}}\left( \, \, e(h)\geq \bar{e}\left( m_{\textrm{test}},\hat{e}_{\textrm{test}}(h),\delta \right) \right) \leq \delta \]
where \( \bar{e}\left( m,\frac{k}{m},\delta \right) \equiv \max _{p}\{p:\, \, \textrm{Bin}(m,k,p)=\delta \} \)
\end{thm}
\begin{proof}
The proof is just a simple identification with the Binomial. For any distribution
over \( (x,y) \) pairs and any hypothesis, \( h \), there exists some probability,
\( e_{D}(h) \), that the hypothesis predicts incorrectly. We can regard this
event as a coin flip with bias \( e_{D}(h) \). Since each example is picked
independently, the distribution of the empirical error rate will then be a Binomial
distribution. Given that the distribution is Binomial we calculate an upper
bound which holds with high probability.
\end{proof}
There are two immediate corollaries of the holdout theorem (\ref{th-hb}) which
are mathematically simpler although not as tight. The first corollary applies
to the limited ``realizable'' setting where you happen to observe \( 0 \)
test errors.

\begin{cor}
(Realizable Holdout Sample Complexity) 
\[
\forall h\, \, \Pr _{D}(\hat{e}_{\textrm{test}}(h)=0|e_{D}(h)\geq \frac{\ln \frac{1}{\delta }}{m_{\textrm{test}}})\leq \delta \]

\end{cor}
\begin{proof}
Specializing theorem \ref{th-hb} to the zero empirical error case, we get:
\[
\textrm{Bin}(m_{\textrm{test}},0,\epsilon )=(1-\epsilon )^{m_{\textrm{test}}}\leq e^{-\epsilon m_{\textrm{test}}}\]
Setting this equal to \( \delta  \) and solving for \( \epsilon  \) gives
us the result.
\end{proof}
A second corollary applies to all results, not just those where we observe \( 0 \)
errors.

\begin{cor}
(Agnostic Holdout Sample Complexity) 
\[
\forall h\, \, \Pr _{D}(e_{D}(h)-\hat{e}_{\textrm{test}}(h)\geq \sqrt{\frac{\ln \frac{1}{\delta }}{2m_{\textrm{test}}}})\leq \delta \]

\end{cor}
\begin{proof}
Loosening theorem \ref{th-hb} with the Hoeffding approximation for \( \frac{k}{m_{\textrm{test}}}<\epsilon  \),
we get:
\[
\textrm{Bin}(m_{\textrm{test}},k,\epsilon )\leq e^{-2m_{\textrm{test}}(\epsilon -\frac{k}{m_{\textrm{test}}})^{2}}\]
Using the inversion lemma \ref{lem-inversion} we can set this equal to \( \delta  \),
and solve for \( \epsilon  \) to get the result.
\end{proof}
\begin{rem}
Similar theorems apply to bound \( \hat{e}_{\textrm{test}}(h)-e_{D}(h) \).
\end{rem}
How tight is the test sample complexity theorem? The answer is very tight. Let
us define \-
\[
\bar{e}(m,\hat{e}(h),\delta )\equiv \max _{p}p:\, \, \textrm{Bin}(m_{\textrm{test}},m_{\textrm{test}}\hat{e}_{S}(h),p)\geq \delta \]
as our true error bound. We wish to know how much \( e_{D}(h) \) and \( \bar{e}(m_{\textrm{test}},\hat{e}(h),\delta ) \)
differ. Applying the Hoeffding approximation, we know that with high probability,
\( e_{D}(h)\geq \bar{e}(m_{\textrm{test}},\hat{e}(h),\delta )-2\sqrt{\frac{\ln \frac{1}{\delta }}{2m_{\textrm{test}}}} \).
Thus the region in which \( e_{D}(h) \) is confined with high confidence is
of size \( 2\sqrt{\frac{\ln \frac{1}{\delta }}{2m_{\textrm{test}}}} \) or smaller. 

It is common practice in the field of machine learning to use the gaussian approximation
in reporting error bars. The practice is reasonably safe because it is usually
pessimistic. However, this can occasionally lead to embarrassing results where
error rates such as \( 0.01\pm 0.02 \) are reported. The test sample complexity
theorem avoids \emph{never} produces an upper bound greater than \( 1 \) or
lower bound less than \( 0 \) because it uses the fundamental Binomial distribution.
This approach is the ``right'' way to report test-set based errors, given
the assumption of indepence. Pictorially we can represent this as in figure
\ref{fig-holdout-protocol}.
\begin{figure}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\includegraphics{thesis/thesis-presentation/test_set.eps}} \par}


\caption{\label{fig-holdout-protocol} For this diagram ``increasing time'' is pointing
downwards. The only requirement for applying this bound is that the learner
must commit to a hypothesis without knowledge of the test examples. Similar
diagrams for other bounds will be presented later (and they are somewhat more
complicated). We can think of the bound as a technique by which the ``Learner''
can convince the ``Verifier'' that learning has occurred. Each of the proofs
in this thesis can be thought of as a communication protocol for an interactive
proof of learning by the Learner.}
\end{figure}
 

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

There are two basic approaches to this difficulty: 

\begin{enumerate}
\item Try to reduce \( m_{\textrm{test}} \) using more sophisticated holdout techniques.
\item Do not use a holdout set. Instead, train and test on the same set of examples
using a more sophisticated bound.
\end{enumerate}
Before discussing approach (2) we will make a few comments about approach (1)
to suggest the variety of theoretical difficulties which occur when using approach
(1).


\subsection{Cross Validation}

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

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

There are strong results known for cross validation on nearest-neighbor, kernel,
and histogram classifiers \cite{Devroye}. In general, only very weak results
are known about bounds on the variance of cross validation for general classifiers.
The ``general'' results include ``Sanity check bounds'' \cite{Sanity} which
state that cross validation is not much worse than a holdout set and some slightly
stronger results \cite{BKL} and \cite{Kalai}.

\begin{problem}
(Open) Construct a bound on the deviation of cross validation for arbitrary
classifiers which is a quantitative improvement on the results of \cite{BKL}.
\end{problem}

\subsection{The basic training set bound}

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

\begin{thm}
\label{th-DHSCP} (Discrete Hypothesis Bound) For all hypothesis spaces, \( H \),
for all \( \delta \in (0,1] \) 
\[
\Pr _{D^{m}}\left( \exists h\in H:\, \, e(h)\geq \bar{e}\left( m,\hat{e}(h),\frac{\delta }{|H|}\right) \right) \leq \delta \]
where \( \bar{e}\left( m,\frac{k}{m},\delta \right) \equiv \max _{p}\{p:\, \, \textrm{Bin}(m,k,p)=\delta \} \)
\end{thm}
Note that this theorem can only be nonvacuous when the hypothesis space, \( H \),
has some finite (discrete) size.

\begin{proof}
For every individual hypothesis, we know that: 
\[
\forall h\, \, \Pr _{D^{m}}\left( e(h)\geq \bar{e}\left( m,\hat{e}(h),\frac{\delta }{|H|}\right) \right) \leq \frac{\delta }{|H|}\]
Applying the union bound (see section \ref{sec-union}) for every hypothesis
gives us: 
\[
\Pr _{D^{m}}\left( \exists h\in H:\, \, e(h)\geq \bar{e}\left( m,\hat{e}(h),\frac{\delta }{|H|}\right) \right) \leq \delta \]
 which is the result.
\end{proof}
Intuitively, this theorem says that as the number of hypotheses grows, we can
not guarantee that the empirical error will be near to the true error.

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

\begin{cor}
\label{th-REDHSCP}(Relative Entropy Discrete Hypothesis Bound) For all hypothesis
spaces, \( H \), for all \( \delta \in (0,1] \):
\[
\Pr _{D^{m}}\left( \exists h\in H:\, \, \textrm{KL}(\hat{e}(h)||e(h))\geq \frac{\ln |H|+\ln \frac{1}{\delta }}{m}\right) \leq \delta \]

\end{cor}
\begin{proof}
Loosen (theorem \ref{th-DHSCP}) with the relative entropy Chernoff bound (Eqn.
\ref{eq-recb}), and use the inversion lemma \ref{lem-inversion}.
\end{proof}
The form of this corollary allows us to make two more important observations:

\begin{enumerate}
\item The ``cost'' of doubling the hypothesis space size is about one extra example.
In other words, we can keep a constant bound on the probability of a large deviation
with \( c\log |H| \) hypotheses (for any \( c \)).
\item The value of \( \delta  \) is not very important as \( m \) grows larger.
\end{enumerate}
We can further loosen the last corollary with the Hoeffding approximation to
get the following commonly stated bound:

\begin{cor}
\label{th-adhscb} (Agnostic Discrete Hypothesis Bound) For all hypothesis spaces,
\( H \), for all \( \delta >0 \), 
\[
\Pr _{D^{m}}\left( \exists h\in H:\, e(h)\geq \hat{e}(h)+\sqrt{\frac{\ln |H|+\ln \frac{1}{\delta }}{2m}}\right) \leq \delta \]

\end{cor}
\begin{proof}
Loosen corollary (\ref{th-REDHSCP}) with the bound \( \textrm{KL}(q||p)\leq 2(q-p)^{2} \).
\end{proof}
The agnostic form of this bound has the advantage that it explicitly shows that
we are forcing the convergence (in high probability) of the empirical error
rate to the true error rate. Graphically, we are forcing every empirical error
to be near to its true error. This is a picture which represents the connection

\vspace{0.3cm}
{\par\centering \( \hat{e}(h) \)----------\( e(h) \)\par}
\vspace{0.3cm}

Later bounds will have more complicated convergence conditions with more complicated
graphs. This is \emph{necessary} because the simple holdout bound does not work
in practice. 


\subsection{Lower Bounds}

It is important to study lower bounds in order to discover how much room for
improvement exists in our upper bounds.

There are two forms of lower bounds: a lower bounds on the true error rate and
lower \emph{upper} bounds which lower bound the value our upper bound could
return (given available information). For lower bounds essentially the upper
bound theorem applies with the bound reversed. This form of lower bound allow
us to construct a two-sided confidence interval on the location of the true
error rate. Typically, such lower bounds can be formed by simply changing the
sign in upper bound arguments. 

\begin{thm}
\label{th-dhlb} (Discrete Hypothesis Lower Bound) For all hypothesis spaces,
\( H \), for all \( \delta \in (0,1] \) 
\[
\Pr _{D^{m}}\left( \exists h\in H:\, \, e(h)\leq \bar{e}\left( m,\hat{e}(h),\frac{\delta }{|H|}\right) \right) \leq \delta \]
where \( \bar{e}\left( m,\frac{k}{m},\delta \right) \equiv \min _{p}\{p:\, \, \textrm{Bin}(m,k,p)=\delta \} \)
\end{thm}
\begin{proof}
For every individual hypothesis, we know that: 
\[
\Pr _{D^{m}}(e(h)\leq \bar{e}(m,\hat{e}(h),\delta ))\leq \delta \]
Applying the union bound for every hypothesis gives us the result.
\end{proof}

\subsection{Lower Upper Bounds}

\label{sec-lower_upper}

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

How tight is the discrete hypothesis bound (\ref{th-DHSCP})? The answer is
\emph{sometimes} tight. In particular, we can exhibit a set of learning problem
where the discrete hypotheses bound can not be made significantly lower as a
function of the observables, \( m \), \( \delta  \), \( |H| \), and \( \hat{e}(h) \).
Fix the value of these quantities and then we will construct a learning problem
for which a lower upper bound can not be stated. 

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

\begin{algorithm}
\label{alg-lp} Draw\_Sample(float \( e \))
\end{algorithm}
\begin{enumerate}
\item Pick \( y\in \{0,1\} \) uniformly
\item For \( i \), pick \( x_{i}\neq y \) with probability \( e \).
\end{enumerate}
By construction, the true error rate of each hypothesis will be \( e(h_{i}) \).
Now, we can prove the following theorem:

\begin{thm}
\label{th-dhlub}(Discrete Hypothesis lower upper bound) For all true error
rates \( e(h)>\frac{\ln |H|+\ln \frac{1}{\delta }}{m} \) there exists a learning
problem and algorithm such that: 
\[
\Pr _{D^{m}}\left( \exists h\in H:\, \, e(h)\geq \bar{e}\left( m,\hat{e}(h),\frac{\delta }{|H|}\right) \right) \geq 1-e^{-\delta }\]
where \( \bar{e}\left( m,\frac{k}{m},\delta \right) \equiv \max _{p}\{p:\, \, \textrm{Bin}(m,k,p)=\delta \} \)
\end{thm}
Intuitively, this theorem implies that we can not improve significantly on the
results of theorem \ref{th-DHSCP} without using extra information about our
learning problem. Some of our later results do exactly this - they use extra
information.

\begin{proof}
Using the family of learning problems implicitly defined by algorithm \ref{alg-lp},
we know that 
\[
\forall h,\forall \delta \in [0,1]:\, \, \Pr _{D^{m}}\left( e(h)\geq \bar{e}\left( m,\hat{e}(h),\frac{\delta }{|H|}\right) \right) \geq \frac{\delta }{|H|}\]
(negation)
\[
\Rightarrow \forall h,\forall \delta \in [0,1]:\, \, \Pr _{D^{m}}\left( e(h)<\bar{e}\left( m,\hat{e}(h),\frac{\delta }{|H|}\right) \right) <1-\frac{\delta }{|H|}\]
(independence)
\[
\Rightarrow \forall \delta \in [0,1]:\, \, \Pr _{D^{m}}\left( \forall h\, \, e(h)<\bar{e}\left( m,\hat{e}(h),\frac{\delta }{|H|}\right) \right) <\left( 1-\frac{\delta }{|H|}\right) ^{|H|}\]
(negation)
\[
\Rightarrow \forall \delta \in [0,1]:\, \, \Pr _{D^{m}}\left( \exists h\, \, e(h)\geq \bar{e}\left( m,\hat{e}(h),\frac{\delta }{|H|}\right) \right) \geq 1-\left( 1-\frac{\delta }{|H|}\right) ^{|H|}\]
(approximation)
\[
\Rightarrow \forall \delta \in [0,1]:\, \, \Pr _{D^{m}}\left( \exists h\, \, e(h)\geq \bar{e}\left( m,\hat{e}(h),\frac{\delta }{|H|}\right) \right) \geq 1-e^{-\delta }\]

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


\subsection{Structural Risk Minimization}

Structural Risk Minimization \cite{Vapnik} (SRM) is a technique used in the
learning theory community to avoid the difficulties associated with convergence
on hypothesis sets that are too ``large''. SRM works with a sequence of nested
hypothesis sets, \( H_{1}\subset H_{2}\subset ....\subset H_{l} \). For each
hypothesis set, a discrete hypothesis bound (\ref{th-DHSCP}) on the difference
between empirical and true error exists. For ``small'' hypothesis sets, this
bound may be tight while for large hypothesis sets it may be inherently loose.
However, we also expect that the best hypothesis in the hypothesis set improves
as the hypothesis set becomes larger. This naturally induces a trade-off: there
will be some hypothesis set \( H_{i} \) for which the true error bound is minimized. 

We can't simply apply the discrete hypothesis bound to the meta-algorithm which
picks the algorithm (and associated hypothesis space) with the smallest true
error bound since this meta-algorithm could, potentially, output any hypothesis
in \( H_{l} \). The simplest way to retrofit the bound to include all hypothesis
sets is with a simple theorem which essentially states that we can guarantee
\emph{nearly} the same bound as would apply on the smallest hypothesis space
\( H_{i} \) containing the output hypothesis, \( h \). 

\begin{thm}
\label{th-SRM} (Structural Risk Minimization) Let \( p(i) \) be some measure
across the \( l \) hypothesis sets with \( \sum _{i=1}^{l}p(i)=1 \). Then:
\[
\forall p(i):\, \, \, \Pr _{D^{m}}\left( \exists h\in H_{i}\in \{H_{1},...,H_{l}\}:\, \, e(h)\leq \bar{e}\left( m,\hat{e}(h),\frac{p(i)\delta }{|H_{i}|}\right) \right) \leq \delta \]
where \( \bar{e}\left( m,\frac{k}{m},\delta \right) \equiv \min _{p}\{p:\, \, \textrm{Bin}(m,k,p)=\delta \} \).
\end{thm}
\begin{proof}
Apply the union bound to the discrete hypothesis bound (\ref{th-DHSCP}).
\end{proof}
The SRM bound is slightly inefficient in the sense that the bound for all hypotheses
in \( H_{2} \) includes a bound for every hypothesis in \( H_{1} \). This
effect is typically small because the size of the hypothesis sets usually grows
exponentially, implying that the extra confidence given to a hypothesis \( h \)
in \( H_{1} \) by the bounds used on hypothesis set \( H_{2},H_{3},... \)
is small relative to the confidence given by the bound for \( H_{1} \). One
can remove this slack in Structural Risk Minimization bound by ``cutting out''
the nested portion of each hypothesis set in the formulation of \( H_{1},...,H_{l} \).
We will call this Disjoint Structural Risk Minimization (also mentioned in \cite{MC_journal}).


\section{Incorporating a ``Prior''}

In constructing the discrete hypothesis bound (\ref{th-DHSCP}), it is notable
that an arbitrary choice was made. We decided to give the same error allowance
to every hypothesis. This is an arbitrary choice which, in practice, we will
wish to make differently. The next theorem is essentially a restatement of the
discrete hypothesis bound with this arbitrary choice made explicit. The same
bound using the Hoeffding approximation has appeared elsewhere \cite{BEHW}\cite{PB}.

\begin{thm}
\label{th-ORB} (Occam's Razor Bound) For all hypothesis spaces, \( H \), for
all ``priors'' \( p(h) \) over the hypothesis space, \( H \), for all \( \delta \in (0,1] \):
\[
\forall p(h)\, \, \Pr _{D^{m}}\left( \exists h\in H:\, \, e(h)\geq \bar{e}\left( m,\hat{e}(h),\delta p(h)\right) \right) \leq \delta \]
where \( \bar{e}\left( m,\frac{k}{m},\delta \right) \equiv \max _{p}\{p:\, \, \textrm{Bin}(m,k,p)=\delta \} \)
\end{thm}
It is very important to notice that the ``prior'' \( p(h) \) must be selected
\emph{before} seeing the examples.

\begin{proof}
The proof again starts with the basic observation that:
\[
\Pr _{D^{m}}\left( e(h)\geq \bar{e}(m,\hat{e}(h),\delta )\right) \leq \delta \]
then, we apply the union bound in a \emph{nonuniform} manner. In particular,
we allocate confidence \( \delta p(h) \) to hypothesis \( h \). Since \( p \)
is normalized, we know that 
\[
\sum _{h}\delta p(h)=\delta \]
 which implies that the union bound completes the proof.
\end{proof}
Once again, we can relax the Occam's Razor bound (theorem \ref{th-ORB}) with
the relative entropy Chernoff bound (\ref{eq-recb}) to get a somewhat more
tractable expression. 

\begin{cor}
\label{th-reorb} (Relative Entropy Occam's Razor Bound) For all hypothesis
spaces, \( H \), for all ``priors'' \( p(h) \) over the hypothesis space,
\( H \), for all \( \delta \in (0,1] \):
\[
\Pr _{D^{m}}\left( \exists h\in H:\, \, \textrm{KL}(\hat{e}(h)||e(h))\geq \frac{\ln \frac{1}{p(h)}+\ln \frac{1}{\delta }}{m}\right) \leq \delta \]

\end{cor}
\begin{proof}
approximate the Binomial tail with (\ref{eq-recb}) and solve for the minimum.
\end{proof}
The Occam's razor bound is often nonvacuous for discrete learning algorithms
such as decision lists and decision trees. The next chapter will discuss a particular
motivated choice of the measure \( p(h) \) which can lead to much tighter bounds
in practice. 

The application of the Occam's Razor bound is somewhat more complicated then
the application of the test set bound. Pictorially, the protocol for bound application
is given in figure \ref{fig-training-set}.
\begin{figure}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\includegraphics{thesis/thesis-presentation/training_set.eps}} \par}


\caption{\label{fig-training-set} In order to apply this bound it is necessary that
the choice of ``Prior'' be made before seeing any training examples. Then,
the bound is calculated based upon the chosen hypothesis. Note that it \emph{is}
``legal'' to chose the hypothesis based upon the prior \protect\( p(h)\protect \)
as well as the empirical error \protect\( \hat{e}_{S}(h)\protect \).}
\end{figure}


\begin{thebibliography}{10}
\bibitem{BEHW}A. Blumer, A. Ehrenfeucht, D. Haussler, M. Warmuth. ``Occam's Razor.'' Information
Processing Letters 24: 377-380, 1987.
\bibitem{BKL}Avrim Blum, Adam Kalai, and John Langford 1999. Beating the Holdout: Bounds
for KFold and Progressive Cross-Validation. COLT99. http://www.cs.cmu.edu/\~{}jcl/papers/progressive\_validation/coltfinal.ps
\bibitem{Chernoff}H. Chernoff, ``A Measure of the asymptotic efficiency of tests of a hypothesis
based on the sum of observations'', Annals of Mathematical Statistics, 23:493-507,
1952.
\bibitem{Devroye}Luc Devroye, Laszlo Gyorfi, Gabor Lugosi, ``A Probabilistic Theory of Pattern
Recognition'' Springer-Verlag New York, 1996.
\bibitem{AHKV}A. Ehrenfucht, D. Haussler, M. Kearns, and L. Valiant, ``A General Lower Bound
on the Number of Examples Needed for Learning'', Information and Computation
82(3), pp. 247-261, 1989.
\bibitem{Haussler}David Haussler, ``Mathematical perspectives on Neural networks '', Lawrence
Erlbaum Associates, 1995.
\bibitem{Hoeffding}Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables.
Journal of the American Statistical Association, 58, 13-30
\bibitem{Kalai}Adam Kalai, ``Probabilistic and On-line methods in Machine Learning''.thesis,
CMU-CS-01-132.
\bibitem{Sanity}Michael Kearns and Dana Ron, ``Algorithmic Stability and Sanity-Check Bounds
for Leave-One-Out Cross-Validation.'' Neural Computation 11(6), pages 1427-1453,
1999. Also in Proceedings of the Tenth Annual Conference on Computational Learning
Theory, ACM Press, 1997, pages 152--162.
\bibitem{MC_journal}John Langford and Avrim Blum 1999. Microchoice Bounds and Self Bounding learning
algorithms. Machine Learning Journal. http://www.cs.cmu.edu/\~{}jcl/papers/microchoice/journal/journal\_final.ps
\bibitem{PB}David McAllester, ``PAC-Bayesian Model Averaging'' COLT 1999.
\bibitem{Valiant}L.G. Valiant. ``A Theory of the Learnable.'' Communications of the ACM 27(11):1134-1142,
November 1984
\bibitem{Vapnik}Vladimir N. Vapnik, ``Statistical Learning Theory'', Wiley, December 1999.
\end{thebibliography}
\end{document}
