%% This LaTeX-file was created by <jl> Thu Feb 25 22:06:31 1999
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

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

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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{definition}
\newtheorem{defn}[thm]{Definition}

\makeatother

\begin{document}


\title{Microchoice Bounds and Self Bounding Learning Algorithms}


\author{John Langford and Avrim Blum}


\email{\{jcl+,avrim+\}@cs.cmu.edu}

\maketitle
\begin{abstract}
We prove adaptive bounds for learning algorithm which operate by making a sequence
of choices. With these adaptive bounds, we provide a new class of selfbounding
learning algorithms which compliment Yoav's (cite) self-bounding learning algorithms. 
\end{abstract}

\section{Introduction}

PAC bounds are to loose for application to real world learning problems using
common learning algorithms. They require more examples then expirementally necessary
to guarantee a reasonable accuracy with a reasonable probability. Chief amongst
the reasons for this failure is that typical PAC bounds do not take into account
the specific distribution to be learned or the structure of the learning algorithm.
A tighter bound can be derived by taking these factors into account. 

Many learning algorithms work by an iterative process where they take a sequence
of small steps each from a small (in comparison to the overall hypothesis space)
choice space. Neural networks, for example, work in this manner. Each backpropagation
step in a neural network changes the weights by a small amount which corresponds
to changing the hypothesis output by the neural network by a small amount under
a Lipschitz condition. The backpropagation step can be viewed as making a choice
from a small hypothesis space of possible backpropagations. A bound which takes
into account the number of choices made and the size of each choice space can
yield a tighter bound then the standard PAC bound if the neural network training
stops before exploring a large portion of the available hypothesis space. As
a further improvement on this bound, an a priori heuristic can be used to weight
the possible choices unevenly allowing a tighter bound to be derived for some
distributions.

The Microchoice bound lends itself to the construction of Self Bounding Learning
algorithms in a natural way. Any of the algorithms which the Microchoice Bound
can be applied to can be instrumented to keep track of the size of each small
choice space. Then, when the algorithm finishes, the bound can be calculated
and output along with the answer. This procedure work without altering the final
hypothesis output. It is also possible to modify the learning algorithm to use
a current bound in order to implement early stopping in a manner similar to
that of dynamic Structural Risk Minimization (cite Peter Bartlett/John Shawe-Taylor
paper). In fact, the Microchoice bound can be viewed as a compelling choice
of nested hypothesis spaces on which to apply Structural Risk minimization.
Self Bounding Learning algorithms were first suggested by Yoav Freund(cite).
Work developing approximately Self Bounding Learning algorithms was also done
by Pedro Domingos (cite).

First, we will review an agnostic PAC Bound for the discrete case then prove
a Microchoice Bound in a discrete agnostic setting. Next, we will introduce
an agnostic PAC Bound for the continuous case and then prove a Microchoice Bound
in a continuous agnostic setting. We will finish with a comparison to Yoav's
Self Bounding Learning algorithm work and some examples.


\section{Discrete PAC Bound Review}

The initial framework will follow the setup of Haussler\cite{Haussler} with notation revised
for easy extension into the Microchoice learning model. The basic PAC model
is characterized by a hypothesis space, \( H \), composed of hypothesis, \( h:x\rightarrow y \) which take
an input \( x\in X \), and produces an output, \( y\in Y \). Let \( z=(x,y) \) denote a labeled example. Some
number, \( N \), of labeled examples, \( z^{N}\in Z^{N} \), is generated according to an unknown distribution,
\( P \), on the example space, \( Z \). Let \( z_{n} \) denote a particular labeled example in the
set of labeled examples, \( z^{N} \). A learning algorithm, \( L(H,z^{N}) \), in the realizable setting
will output some hypothesis with \( 0 \) error. 

We can weight our confidence on each hypothesis differently. Let \( \delta (h) \) = the probability
that the true error on a hypothesis, \( h \), will be greater than \( \epsilon (h) \). Furthermore,
let \( \sum _{h\in H}\delta (h)=\delta  \) be the probability that any \( h\in H \) will have an error difference greater than
\( \epsilon (h) \). We now have a slightly generalized PAC theorem.

\begin{thm}
(Realizable Folk Theorem) For any \( 0<\delta <1 \) and any measure, \( m(h)=\frac{\delta (h)}{\delta } \), over hypothesis space,
\( H \), 


\[
P(\exists h\in H:E_{P}(h)>\frac{1}{N}(\ln \frac{1}{\delta }+\ln \frac{1}{m(h)}))<1-\delta \]

\end{thm}
\begin{proof}
This theorem is essentialy a folk theorem covered explicity in preliminary theorem
1 of McCallester's Colt98 paper (cite). The proof is done using an unsymmetric
union bound over the hypothesis space.
\end{proof}
We will also be interested in the agnostic case which will require a little
more development. A loss function, \( l(h(x),y)\in [0,1] \) lets us determine the loss of a hypothesis
on a labeled example. A learning algorithm, \( L(H,z^{N},l) \), in the agnostic PAC setting can
be thought of as taking a hypothesis space, \( H \), a set of examples, \( z^{N} \), and a loss
function, \( l(h(x),y)\in [0,1] \) as arguments and returning a hypothesis, \( h \). Any choice algorithm
based on statistical queries of the sample will work. We will think of the empirical
minimization algorithm: evaluate every hypothesis and pick the one with the
lowest average loss. 

The same trick of unevenly emphasizing the confidence on each hypothesis will
work in the agnostic setting giving us the following theorem:

\begin{thm}
(Agnostic Folk Theorem) For any \( 0<\delta <1 \) and any measure, \( m(h)=\frac{\delta (h)}{\delta } \), over the hypothesis space,
\( H \),


\[
P(\exists h\in H:E_{P}(h^{l})>E(h^{l},z^{N})+\sqrt{\frac{1}{2N}(\ln \frac{1}{\delta }+\ln \frac{1}{m(h)})})<1-\delta \]

\end{thm}
\begin{proof}
This theorem is essentialy a folk theorem covered explicity in preliminary theorem
2 in McCallester's Colt98 paper (cite). The proof is done using a union bound
over the hypothesis.
\end{proof}

\section{Discrete Microchoice Bound}


\subsection{Best possible PAC bound}

The Folk theorems hold for any finite set \( H \). The Microchoice Bound is simply
a compelling choice of the measure, \( m(h) \). Consider a learning algorithm which works
by making a sequence of choices, \( c_{1},...,c_{M} \), from a sequence of choice spaces, \( C_{1},...,C_{M} \) resulting
in a hypothesis, \( h \), in the hypothesis space, \( H \). We can't know in advance which
choice sequence the algorithm will make. However, given any distribution, \( P \)
on examples and hypothesis space, \( H \), and learning algorithm, \( L(H,\cdot ) \), a distribution
over sequences of choices is induced by the distribution over examples, \( P \). The
distribution over sequences in turn induces a distribution over the hypothesis
space, \( H \). Pick the weighting, \( \delta (h)=\delta p(h)=\delta \sum _{\textrm{sequences ending in }h}p(\textrm{sequence}) \). The Realizable Folk Theorem then gives us:


\[
P(\exists h\in H:E_{P}(h)>\frac{1}{N}(\ln \frac{1}{\delta }+\ln \frac{1}{\sum _{\textrm{sequences ending in }h}p(\textrm{sequence})}))<1-\delta \]


This choice of \( m(h) \) is optimal for minimizing the expected value of \( \epsilon (h) \). Notice that

\[
\min _{0<m(h)<1:\sum _{h\in H}m(h)=1}\sum _{h\in H}p(h)\frac{1}{N}(\ln \frac{1}{\delta }+\ln \frac{1}{m(h)})\]

\[
=\frac{1}{N}(\ln \frac{1}{\delta }+\min _{0<m(h)<1:\sum _{h\in H}m(h)=1}\sum _{h\in H}p(h)\ln \frac{1}{m(h)})\]


Now notice that \( \frac{\partial }{\partial m(h)}\ln \frac{1}{m(h)}=-\frac{\partial }{\partial m(h)}\ln m(h) \). This implies that the Lagrangian corresponding to minimizing
the value of \( \epsilon (h) \) will be the same up to a sign as the problem of minimizing \( \sum p(h)\ln m(h) \).
This corresponds to minimizing the Kullback-Liebler divergence which provides
a solution of \( m(h)=p(h) \).

The agnostic case is similar. Again, we pick the weighting, \( \delta (h)=\delta p(h)=\delta \sum _{\textrm{sequences ending in }h}p(\textrm{sequences}) \). The folk theorem
then gives us:


\[
P(\exists h:E_{P}(h^{l})>E(h^{l},z^{N})+\sqrt{\frac{1}{2N}(\ln \frac{1}{\delta }+\ln \frac{1}{\sum _{\textrm{sequences ending in }h}p(\textrm{sequences})})})<1-\delta \]


Somewhat surprisingly, this choice of measure, \( m(h)=p(h) \), does not minimize the expected
value of \( \epsilon (h) \), \( E_{P}\epsilon (h) \) as can be seen from a quick analysis of the two hypothesis case.
Instead, this choice of measure minimizes the expected value of \( \epsilon (h)^{2} \). 


\[
\min _{0<m(h)<1:\sum _{h\in H}m(h)=1}\sum _{h\in H}p(h)\epsilon (h)^{2}\]

\[
\min _{0<m(h)<1:\sum _{h\in H}m(h)=1}\sum _{h\in H}p(h)\frac{1}{2N}(\ln \frac{1}{\delta }+\ln \frac{1}{m(h)})\]


From here, the analysis is the same as for the realizable case.


\subsection{The Microchoice bound}

The choice \( m(h)=p(h) \) isn't useful becuase we can't calculate \( p(h) \). However, it does motivate
the use of an approximation to \( p(h) \). Our choice of \( m(h) \) will be an estimate \( p(h) \). We
will neglect the possibility that multiple sequences of choices can lead to
the same hypothesis implying that the Microchoice Bound will be unnecessarily
loose for learning algorithms which can arrive at the same hypothesis in multiple
ways. Then we will choose \( p(h)\sim m(h)=\prod _{m=1}^{M(h)}\frac{1}{|C_{m}(h)|} \). If there are multiple sequences which arrive at
\( h \), use the sequence which minimizes \( \prod _{m=1}^{M}\frac{1}{|C_{m}|} \). This is a valid measure on the hypothesis
space because the sum of all measures is probability bounded by 1, \( \sum _{h\in H}\prod _{m=1}^{M(h)}\frac{1}{|C_{m}(h)|}\leq 1 \). We immediately
find the following theorems.

\begin{thm}
(Realizable Discrete Microchoice Theorem) For any \( 0<\delta <1 \) and the measure \( m(h)=\prod _{m=1}^{M(h)}\frac{1}{|C_{m}(h)|} \) over hypothesis
space, \( H \), 


\[
P(\exists h\in H:E_{P}(h)>\frac{1}{N}(\ln \frac{1}{\delta }+\sum _{m=1}^{M(h)}\ln |C_{m}(h)|))<1-\delta \]

\end{thm}
\begin{proof}
Specialization of the Realizable Folk Theorem.
\end{proof}
\begin{thm}
(Agnostic Discrete Microchoice Theorem) For any \( 0<\delta <1 \) and the measure \( m(h)=\prod _{m=1}^{M(h)}\frac{1}{|C_{m}(h)|} \) over the
hypothesis space, \( H \),


\[
P(\exists h\in H:E_{P}(h^{l})>E(h^{l},z^{N})+\sqrt{\frac{1}{2N}(\ln \frac{1}{\delta }+\sum _{m=1}^{M(h)}\ln |C_{m}(h)|)})<1-\delta \]

\end{thm}
\begin{proof}
Specialization of the Agnostic Folk Theorem.
\end{proof}
If we can calculate the size of each choice space, \( |C_{m}| \), the algorithm made a choice
from to reach the final hypothesis, \( h \), then we can give a valid bound for the
final hypothesis in terms of the size of each hypothesis space.

The Microchoice Theorem can easily account for choices made based upon the current
value of a computable bound which is used for early stopping. The option to
stop is simply another choice, enlarging all choice spaces by \( 1 \). It is also
possible to weight each choice in a choice space according to an a. priori heuristic
as in the Folk Theorems.

Decision trees over discrete spaces are a natural setting for application of
the Microchoice Bound.


\section{Continuous PAC Framework Review}

The continuous realizable model is essentially the same as the discrete realizable
model except instead of a discrete hypothesis set, we have a continuous hypothesis
space, \( H \). We wish to prove that if the empirical error is \( 0 \), \( \hat{E}(h^{l},z^{N})=\frac{1}{N}\sum _{n=1}^{N}h^{l}(z_{n})=0 \), on a random
example drawn according to the distribution, \( P \), over examples then the true
error, \( E_{P}(h^{l})=\int _{Z}h^{l}(z)dP(z) \) is within \( \epsilon  \) of \( 0 \). In order to achieve this goal, it is necessary to
have some measure of the size of a continuous hypothesis space. We first use
the example distribution, \( P \), to induce a metric, \( d_{P} \) on the hypothesis space:


\[
d_{P}(h^{l},g^{l})=E(|h^{l}-g^{l}|)=\int _{X}\sup _{y\in Y}|h^{l}((x,y))-g^{l}((x,y))|dP_{|X}(x)\]


Here, \( dP_{|X}(x) \) is \( P(x)=\int _{Y}P(x,y)dy \).

With this metric, we can define the size, \( N(\epsilon ,H^{l},d_{P}) \), of the loss space, \( H^{l} \), as the minimum
size of a subset of the elements such that all portions of the space are \( \epsilon  \) close
to some element in the subset as measured by \( d_{P} \). Formally, \( N(\epsilon ,H^{l},d_{P})=\min _{S\subseteq H:\forall h\in H\exists s\in S:d_{P}(h^{l},s^{l})\leq \epsilon }|S| \). The set \( S \) implies
a partition, \( \Pi  \), of the hypothesis space \( H \). Each element in this partition is
composed of all hypothesis which are closer to some \( s\in S \) then any other \( s'\neq s\in S \).

Now, we have a convergence theorem for this model.

\begin{thm}
For all distributions, \( P \), on tasks, for the partitition, \( \Pi  \), given by \( N(\epsilon ,H^{l},d_{P}) \), for
all measures, \( m \), assigning nonzero probability to each element, \( \pi  \), of the partition,
for all \( \delta >0 \): 
\[
P(\exists h\in \pi \subset H:E_{P}(h^{l})>2\epsilon +\frac{1}{N}(\ln \frac{1}{\delta }+\ln \frac{1}{m(\pi )}))<1-\delta \]

\end{thm}
\begin{proof}
The proof consists of two steps. First define the error of a paritition as:
\( E_{P}(\pi ^{l})=\inf _{h\in \pi }E_{P}(h^{l}) \) = the smallest error on the partition. With this discrete set of hypothesis,
apply the Realizable Folk Theorem to get that: 
\[
P(\exists \pi \subset H:E_{P}(\pi ^{l})>\frac{1}{N}(\ln \frac{1}{\delta }+\ln \frac{1}{m(\pi )}))<1-\delta \]


Now, notice that for any \( h_{1},h_{2}\in \pi  \), \( d_{P}(h_{1},h_{2})<2\epsilon  \) proving the theorem. 
\end{proof}
The continuous agnostic case is similar. 

\begin{thm}
For all distributions, \( P \), on tasks, for the partitition, \( \Pi  \), implied by \( N(\epsilon ,H^{l},d_{P}) \), for
all measures, \( m \), assigning nonzero probability to each element, \( \pi  \), of the partition,
for all \( \delta >0 \): 
\[
P(\exists h\in \pi \subset H:E_{P}(h^{l})>E(h^{l},z^{N})+2\epsilon +\sqrt{\frac{1}{2N}(\ln \frac{1}{\delta }+\ln \frac{1}{m(\pi )})})<1-\delta \]

\end{thm}
\begin{proof}
The proof again consists of the same two steps. 
\end{proof}

\section{Continuous Microchoice Bound}

For the continuous case, we can again define \( p(\pi )= \) the a. priori probability that
an \( h\in \pi  \) will be chosen under the distribution \( P \) with the learning algorithm and
set \( m(\pi )=p(\pi ) \). Similar results also apply - this choice of \( m(\pi ) \) minimize \( \epsilon (h) \) in the realizable
case and \( \epsilon (h)^{2} \) in the agnostic case. 

If an algorithm makes choices from discrete sets in order to arrive at a hypothesis,
there are only a finite set of hypothesis which the algorithm can output and
the discrete microchoice theorems apply. However, for continuous choice spaces
or large discrete choice spaces, it is important to take into account the fact
that certain choices only differ in their outcomes by a small amount.

We need to make an extra assumption to get a theorem analogous to the Discrete
Microchoice theorems for the continuous case. Here is an example of why: Consider
a small continuous choice space, \( C_{1} \). Let's also assume that an element of \( C_{1} \) can
be specified by a point in \( [0,\epsilon ] \), and any element of the hypothesis \( H \) can be specified
by a point in \( [0,1] \). Furthermore, assume that there exists a hypothesis for every
possible parameterization. There exists a smooth function, \( f:[0,\epsilon ]\rightarrow [0,1] \) with \( f(x)=\frac{x}{\epsilon } \). Assume
that if some \( h\in [0,\epsilon ] \) is chosen, then the next choice is from a discrete space of one
element given by \( f(h) \). The two steps in this algorithm will be equivalent to choosing
a hypothesis from \( H \). We must take into account the possibility that a small
parameter range in the choice space can map onto all of the hypothesis space.

\begin{defn}
The size, \( |C_{i}| \), of a choice space, \( C_{i} \), is the capacity of all hypothesis which a
choice from the choice space can lead to.
\end{defn}
This is a teleological definition of \( |C_{i}| \) which is somewhat unsuitable for direct
use because it is difficult to discover \( |C_{i}| \) without examining the tree of all
possible outcomes. In practice, a continuous hypothesis space is parameterized
by some number of parameters, \( m \), which has some size, \( \int _{H}dx^{m} \).

We will assume that \( |C_{m}| \) 

We will assume that learning algorithms obey the following property: \( |C_{i}|\leq \lambda ^{d} \).

The straightforward generalization which gives the bound 
\[
P(\exists h\in \pi \subset H:E_{P}(h^{l})>2\epsilon +\frac{1}{N}(\ln \frac{1}{\delta }+\ln \frac{1}{m(\pi )}))<1-\delta \]
(Microchoice bound with \( |H_{i_{m}}| \) replaced by \( C(H_{i_{m}}) \)) will fail because the real capacity
of possible hypothesis outcomes is \( C(H_{I}) \), not \( C(H_{I_{1}}) \). 

The trouble in the above example is that by moving to a second choice space,
we could essentially violate the distance function in the first space. This
occurred because there exist intervals \( [a,b] \) which \( f \) expands. If we assume that
for all intervals, \( [a,b] \), \( f \) expands the interval by a factor of at most \( \lambda  \), \( |f([a,b])|<\lambda |[a,b]| \), then
we can prove the following result:

(The theorem above with the final capacity increased by \( \lambda ^{M} \)). 


\section{Example}

We will work through an example involving decision trees over a boolean space
of features, \( x_{1},...,x_{F} \). Let's consider several cases.


\subsection{decision list}

Consider the process of learning a decision list. At step \( i \) in the algorithm,
the possible choices for the next variable come from the set of features which
have not yet been used, giving a choice space of size \( F-i \). If the decision list
stops at some length, \( M \), the error output in the agnostic case will be:

\emph{
\[
E(h^{l},z^{N})+\sqrt{\frac{1}{2N}(\ln \frac{1}{\delta }+\sum _{m=1}^{M(h)}\ln m)})\]
}

If our decision list algorithm is allowed to factor the current value of the
bound into it's computation, we will need to add 1 to the size of each choice
space to take into account the possibility of early stopping yielding the bound:
\[
E(h^{l},z^{N})+\sqrt{\frac{1}{2N}(\ln \frac{1}{\delta }+\sum _{m=1}^{M(h)}\ln (m+1))})\]



\subsection{decision tree}

A decision tree differs from a decision list in that the size of the available
choice space is larger due to the fact that there are multiple nodes where a
new test may be applied. In particular, for a decision tree with \( K \) leaves at
a depth of \( d \) containing dichotomous examples the choice space size is \( K(F-d) \) giving
a bound noticeably worse then the bound for the decision list. This motivates
a slightly different decision algorithm, one which considers only one leaf node
at a time, adding a new test or deciding to never add a new test at this node.
In this case, there are \( (F-d+1) \) choices for a node, \( v \), at depth \( d(v) \) implying a bound
of:

\emph{
\[
E(h^{l},z^{N})+\sqrt{\frac{1}{2N}(\ln \frac{1}{\delta }+\sum _{v\in Nodes(T)}\ln (F-d(v)+1))})\]
}

which can be found by realizing that every node exists from a choice of some
choice space.


\section{Comparison with Yoav's work}

Yoav's approach for selfbounding learning algorithms can require exponentially
more computation then the microchoice approach. Yoav's approach in it's most
simple form requires explicit construction of every path in the state space
of the algorithm which might have high probability under the distribution giving
the task. There exist some learning algorithms where this process can be done
implicitly making the computation feasible. However, for the majority of known
learning algorithms the computational requirement is unfeasible.

The Microchoice bound only requires explicit construction of the size of each
subspace from which a choice is made. Because many common learning algorithms
work by a process of making small steps from small subspaces, this is often
computationally feasible. The Microchoice bound does poorly when directly applied
to the sorts of computations which Yoav's bound works well with. However, it
is possible to interpolate between the Microchoice bound and Yoav's bound by
a process of conglomerating the the subspaces of the Microchoice bound. Consider
a particular choice space, \( C_{i} \) with elements, \( c_{i} \). Each \( c_{i} \) indexes another choice
space, \( C_{i+1}(c_{i}) \). If the computation resources to calculate \( C_{i,i+1}=\cup _{c_{i}\in C_{i}}C_{i+1}(c_{i}) \), then \( |C_{i,i+1}| \) can be used in
place of \( |C_{i}||C_{i+1}| \) in the microchoice bound. In the extreme case where all \( C_{i+1}(c_{i}) \) are identical,
this can make the bound significantly tighter. By repeating this process for
the duration of the algorithm and choosing to weight the likelihood of individual
choice spaces according to a uniform measure if it is likely, we can achieve
Yoav's bound.


\section{Conclusion}

The Microchoice bound can be applied to many common learning algorithms unintrusively
- the path through state space which the algorithm takes need not be effected.
Some extra computation is necessary to assess the size of the choice space which
the algorithm makes choices from. In return, the algorithm can state a bound
with the output hypothesis.

It is not at all clear the the Microchoice bound will always be better than
a typical PAC bound when applied to a problem. In practice, it may be worthwhile
to output a bound which is the minimum of that given by the Microchoice bound
and a more general PAC bound. This can be done theoretically by first mapping
\( \delta \rightarrow \frac{\delta }{2} \) in each bound, slightly worsening the result. The resulting Min(PAC,Microchoice)
bound will then hold with probability \( 1-\delta  \).

There are several remaining open questions. Is there a more satsifying bound
for the continuous case? Can this approach be useful for commonly used learning
algorithms? 

\end{document}
