%% 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[12pt]{amsart}
\usepackage[T1]{fontenc}
\usepackage{fullpage}

\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

\newcommand{\comment}[1]{}
\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 algorithms which operate by
making a sequence of choices.   These adaptive bounds can be used to
produce a simple class of self-bounding learning algorithms in the style
of Freund \cite{F98}.  Furthermore, when combined with Freund's more
sophisticated query-tree approach, these bounds can be used to produce
a modified query-tree that produces similar bounds to those in
\cite{F98} but permits a much more efficient algorithmic 
approximation.
\end{abstract}

\section{Introduction}

PAC bounds are too 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 are worst-case in nature and do not take
into account what may turn out to be a fortuitous target function
and/or data distribution.  A tighter bound can perhaps be derived by
taking these factors into account. 

Many learning algorithms work by an iterative process where they take
a sequence of steps each from a small (in comparison to the overall
hypothesis space) space of choices.  Local optimization algorithms
such as hill-climbing or simulated annealing, for example, work in
this manner. Each step in a local optimization algorithm can be viewed
as making a choice from a small hypothesis space of possible steps to
take.  Taking 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 algorithm halts before exploring a large
portion of the available hypothesis space.

%%%%commenting out because we may not get into continuous case
%%%%Also, where do we use that the step has to be a small one?
%%%%(We just need the ``size'' of the choice space to be small)
\comment{
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 is a natural approach to analyzing algorithms of
this form and lends itself to the construction of Self Bounding
Learning algorithms in the style of Freund \cite{F98} in a
straightforward way.  Briefly, this bound allows algorithms to bound
the difference between the true and empirical errors of the hypotheses
produced based on the choices actually taken and the choice spaces
actually explored, without needing to consider spaces that ``might
have been'' visited under different circumstances.  Thus, by keeping
track of the sizes of the choice spaces visited, the bound can be
calculated and output along with the answer. This procedure works
without altering the final hypothesis produced by the algorithm.  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{F98}.  Work developing approximately
Self Bounding Learning algorithms was also done by Pedro Domingos
\cite{D98}.  In the second hald of this paper, we show how the
Microchoice bound can be combined with the query-tree approach of
Freund to produce a variant on the query tree than allows for
algorithmic approximation in a much more efficient manner.

\section{Discrete PAC Bound Review}

The initial framework will follow the setup of the standard PAC model
with notation revised for easy extension into the Microchoice learning
model. The basic PAC model is characterized by a hypothesis space, \(
H \), composed of hypotheses, \( h:X\rightarrow Y \).  We will
be considering only discrete hypothesis spaces $H$.   The learning
algorithm is given \( N \)
examples $x_1, \ldots, x_N$ generated according to an unknown distribution
$D$ over the instance space $X$, and labeled by some unknown target
function $c$.  We will call the resulting set of labeled examples $z^N
= \{z_1, \ldots, z_N\}$, where $z_i = (x_i, c(x_i))$.  We use $P$ to
denode the distribution on labeled examples induced by $D$ and $c$,
and assume there is some underlying loss function $l:Y \times Y
\rightarrow [0,1]$ that describes the loss of predicting $y$ when the
true answer is $y'$.
Let $E_P(h)$ denote the true error of some hypothesis $h$ with respect
to $P$, and let $E(h,z^N)$ denote $h$'s empirical error on the sample.

In the realizable setting, we assume there exists some $h\in H$ with
$E_P(h) = 0$.  In this setting, we typically wish to state that with
high probability, no hypothesis of high true error will have zero
empirical error, in order to give us confidence in algorithms that
produce hypotheses of zero empirical error.  The standard result in this
setting, using the union bound, is that for any $P$, for any $\delta>0$,
$$\Pr_{z^N}\left[\exists h\in H:  E(h,z^N) = 0 \mbox{ and } E_{P}(h) >
\epsilon  \right] < \delta, \mbox{ \ for \ }
\epsilon = \frac{1}{N}\left(\ln \frac{|H|}{\delta }\right).$$

A folk result, stated explicity as Preliminary Theorem 1 of McAllester
\cite{M98}, is that one can weight the hypotheses in H according to
any probability metric $m$, resulting in different error bounds for
different hypotheses.  In particular, one way to think of the standard
bound above is that we take our ``supply'' of $\delta$ and split it
evenly among the hypotheses, giving $\delta/|H|$ to each, then
defining $\epsilon$ so that the probability a hypothesis of true error
$\epsilon$ has empirical error 0 is at most $\delta/|H|$.  The
generalization is simply that we can allocate our supply of $\delta$
according to $m$ if we wish, giving $\delta(h) = \delta m(h)$ to each.
We then define $\epsilon(h)$ such that the probability a hypothesis of
true error $\epsilon(h)$ has empirical error 0 is at most $\delta(h)$,
and apply the union bound.  Specifically,

\begin{thm}
(Realizable Folk Theorem \cite{M98}) For any $\delta > 0$, any $P$,
and any measure $m$ over $H$, 
\[
\Pr_{z^N}\left[\exists h\in H:  E(h,z^N) = 0 \mbox{ and }
E_{P}(h)>\epsilon(h)\right] < \delta, \mbox{ \ for \ } \epsilon(h) =
\frac{1}{N}\left(\ln \frac{1}{\delta }+\ln \frac{1}{m(h)}\right)  \]

\end{thm}

In the agnostic case, we simply wish to bound the devation between the
true and empirical errors of any hypothesis. The same trick of
unevenly spreading the confidence $\delta$ over the hypotheses, combined with
Hoeffding bounds, produces the following result stated explicity as
Preliminary Theorem 2 in \cite{M98}.

\begin{thm}
(Agnostic Folk Theorem \cite{M98}) For any $\delta > 0$, any $P$,
and any measure $m$ over $H$, 
$$
\Pr_{z^N}\left[\exists h\in H :E_{P}(h)> E(h,z^{N}) +
\epsilon(h)\right] < \delta, \mbox{\ for \ } \epsilon(h) =
\sqrt{\frac{1}{2N}\left(\ln \frac{1}{\delta }+\ln
\frac{1}{m(h)}\right)}
$$
\end{thm}


\subsection{Preliminaries}

For a given learning algorithm $L$, a distribution $P$ on labeled
examples induces a distribution $p(h)$ over the hypotheses $h \in H$
produced by algorithm $L$ after $N$ examples.  If we were looking from
the outside in and knew $P$, then we could apply the Realizable Folk
Theorem the measure $m(h) = p(h)$.  
This choice of \( m(h) \) is optimal for minimizing the expected value
of \( \epsilon (h) \). In particular, notice that 
\[
\inf_m \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 }+\inf_m \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) \).

Interestingly, for the Agnostic bound, this choice of measure, \(
m(h)=p(h) \), does not minimize the expected 
value of \( \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} \). 


\[
\inf _m \sum _{h\in H}p(h)\epsilon (h)^{2} = 
\inf _m \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.

\section{The Microchoice Bound}

The Microchoice Bound is simply a compelling and easy to compute
selection of the measure \( m(h) \).  Consider a learning algorithm that
works by making a 
sequence of choices, \( c_{1},...,c_{M} \), from a sequence of choice
spaces, \( C_{1},...,C_{M} \), finally producing a hypothesis, \( h\in
H\).  Specifically, the algorithm first looks at the choice space
$C_1$ and the data $z^N$ to produce choice $c_1 \in C_1$.  The choice $c_1$
then determines the next choice space $C_2$ (different initial choices
could produce different choice spaces for the second level).  The
algorithm again looks at the data to make some choice $c_2 \in C_2$.
This choice then determines the next choice space $C_3$, and so on.
These choice spaces can be thought of as nodes in a 
{\em choice tree}, where a node containing some choice space $C$ has
branching factor $|C|$.
Eventually, some choice space will be a {\em leaf}, containing no
further choices and just a single hypothesis to be produced as output.


For example {\tt [give an example of a simple algorithm that behaves
this way]}


The way we choose $m(h)$ (equivalently, $\delta(h)$) is as follows.
We take our ``supply'' of $\delta$ and give it to the root of the
choice tree. The root takes its supply and splits it equally among all
its children.  Recursively, each non-leaf nodedoes the same: it takes
the supply it is given and splits it evenly among its children, until
all of the supplied confidence parameter is allocated among the
leaves.  If we examine some leaf containing a hypothesis $h$, we see
that this method gives it $\delta(h) = \delta 
\prod _{m=1}^{M(h)}\frac{1}{|C_{m}(h)|}$,
where $M(h)$ is the depth of $h$
in the choice tree and $C_1(h) = C_1, C_2(h), \ldots, C_{M(h)}(h)$ is
the sequence of choice spaces traversed on the path to $h$.
Equivalently, we allocate $m(h) = \prod _{m=1}^{M(h)}\frac{1}{|C_{m}(h)|}$.
measure to each $h$.  Note that it is possible that
several leaves will contain the same hypothesis $h$, and in that case
one should really add the allocated measures together.  However, we
will neglect this issue, implying that the Microchoice Bound will be
unnecessarily loose for learning algorithms which can arrive at the
same hypothesis in multiple ways.

Another way to view this bound is that we can't know in advance which
choice sequence the algorithm will make. However, a distribution $P$
on labeled examples induces a probability distribution over choice
sequences, inducing a probability distribution $p(h)$ over hypotheses.
Ideally we would like to use $m(h) = p(h)$ in our bounds as noted
above.  However, we can't calculate \( p(h) \), so instead, our choice
of \( m(h) \) will be just an estimate.  In particular, our estimate
$m(h)$ is the probability distribution resulting from picking each
choice uniformly at random from the current choice space at each level
(note: this is different from picking a final hypothesis uniformly at
random).  I.e., it can be viewed as the measure associated with the
assumption that at each step, all choices are equally likely. We
immediately find the following theorems.

\comment{
 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.  In fact, for ease of notation we will associate
each hypothesis $h$ with the sequence of choice spaces $C_1 = C_1(h),
C_2(h), \ldots, C_{M(h)}(h)$ used in reaching i.  Then we will choose
\(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}|} \). 
}

\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)|))<\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.

{\tt [move the examples up to here]}

\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? 

\bibliographystyle{alpha}
\bibliography{mc}
\end{document}
