\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 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 half 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 in
\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 possible 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 with 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 results from an a. priori to an a. posteriori
bound based upon the following reasoning.  ``I have an a. priori bound
on error in mind, but I do not have the means to compute it
explicitly.  What I can do is run the learning algorithm on the data
available, and based upon the trace of the algorithm, compute an
a. posteriori bound on the a. priori 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 child then does 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_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 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 \), 


\[
\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 }+\sum _{m=1}^{M(h)}\ln
|C_{m}(h)|\right) 
 \]

\end{thm}
\begin{proof}
Specialization of the Realizable Folk Theorem.
\end{proof}
\begin{thm}
(Agnostic 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)>E(h,z^{N})+\sqrt{\frac{1}{2N}(\ln \frac{1}{\delta }+\sum _{m=1}^{M(h)}\ln |C_{m}(h)|)})<\delta \]

\end{thm}
\begin{proof}
Specialization of the Agnostic Folk Theorem.
\end{proof}

The point of these Microchoice bounds is that the quantity
$\epsilon(h)$ is something the algorithm can calculate as it goes
along, based on the sizes of the choice spaces encountered.
Furthermore, in many natural cases, a ``fortuitous distribution and
target concept'' corresponds to a shallow leaf or a part of the
tree with low branching, resulting in a better bound. 

{\tt [Move declist example up to here. Instead of discussing early stopping
separately, can just say that at each step have a
choice of n variables or of ending.  Maybe generalize declist so that
also have choice of expanding the width of each term.  E.g., if no
single variable works then go to conjunction of two...]}

The Microchoice bounds are similar to Occam's razor or SRM kinds of
bounds in that often each $k$-ary choice in the tree corrseponds to 
$\log k$ bits in the natural encoding of the final hypothesis
$h$.  For instance, this is true for the above decision list example.
However, sometimes this may not be the case.  Consider, for instance,
a local optimization algorithm in which there are $n$ parameters and
each step adds or subtracts 1 to one of the parameters.  Suppose in
addition the algorithm knows certain constraints that these parameters
must satsify (perhaps a set of linear inequalities) and the algorithm
restricts itself to choices in the legal region.  In this case, the
branching factor, at most $2n$, might become much smaller if we are
``lucky'' and head towards a highly constrained portion of the
solution space.  One could always reverse-engineer and encoding of
hypotheses based on the choice tree, but the Microchoice approach is
much more natural.

{\tt [parag below  should already be implicit or maybe early on point out that
leaves don't have to be at same depth]}
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 \).  

{\tt [move next parag to end of paper?]}

There is an opportunity to use a priori knowledge in the choice of
$m(h)$.  If we define a heuristic function which takes a choice space
and choice as input producing some measure, $g: c \times C \rightarrow
m_i$, with $\sum_i m_i = 1$, we can divide our confidence across the
choices according to the weighting, $m_i$.  If $g$ is ``good'' it may
produce error bounds similar to the error bounds which are
significantly tighter.

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

\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{Application to Freund's Query Tree approach}
\subsection{Background}

\section{Incorporating Queries}

By analyzing the results of queries, it is possible to determine which
outcomes were unlikely given that the query is close to the desired
outcome.  We also have a bound on the probability that an individual
query will be bad.  By combining these techniques, we can effectively
reduce the a posteriori size of the choice space to just the likely
choices improving the bound for many cases. 

\subsection{Statistical Query Framework}
The statistical query framework introduced by Kearns \cite{MK93} is the
same as the PAC framework above, except that the learning algorithm
can only access the learning examples using statistical queries.
Statistical queries take as input binary predicates, $\chi$ mapping examples
to a binary output, $(X,Y) \rightarrow {0,1}$.  The output of the
statistical query is the average over the examples of the predicate, 
\[
	E(\chi,z^N)=\frac{1}{N}\sum_{i=1}^N \chi(z_i)
\]

The output is an empirical estimate of the true value of the query under the 
distribution, $P$.

\[
	E_P(\chi(z))
\]

The bound on the difference between the empirical value and the true
value is given by:
\[
	Pr(|E_P(\chi(z)) - E(\chi,z^N)| > \sqrt{\frac{1}{2N}\ln \frac{2}{\delta}}) \leq \delta
\]



\subsection{Nonuniform bounds for statistical queries}

If we knew exactly what the distibution, $P$, and the learning
algorithm, we know the choice tree induced by the distribution on the
learning algorithm.  Not all branches in this tree are equally likely.
For example, if a particular predicate, $\chi$ is true with
probability $.9$ it is very unlikely that the empirical result of the
query will be $.1$.  If there are many such low likelihood
possibilities, applying a uniform measure across all choices will
result in a bound which is loose.  Instead, we can place some
confidence upon the output of the statistical query being within some
error, $\alpha$, of the true answer, then remove all confidence from
choices which would only have been made if the query was more than
$\alpha$ from the true answer.

The manipulations to the choice tree are now relatively
straightforward.  First, we divide our confidence, $\delta$ into two
parts, one part for queries and one part for the final hypothesis.
Every distinct choice in a choice space is associated with a distinct
query.  Start at the root node, and apportion $\delta$ evenly between
the root node choice and the likely (within $\alpha(\chi)$ of the true
value) outcomes of the query at the root node.  Repeat this process
for every query which will be encountered in the query tree formed by
pruning the choice space to only include the likely outcomes of
queries.  

Let $M(\chi)$ be the depth of some query, $\chi$ in the query tree.
If we let $C_p(\chi) = C_{p1}, C_{p2}(\chi), \ldots,
C_{pM}(\chi)(\chi)$ be the shortest sequence of choice spaces
resulting in query $\chi$ in the pruned query tree, the confidence
placed on the query $\chi$ will be
 
\[
\delta(\chi)= \frac{\delta}{2\prod_{i=1}^{M(\chi)}|C_{pi}+1|}
\]

Furthermore, the sum over all queries will be bounded by $\delta/2$:
\[
	\sum_{\chi} \delta(\chi) \leq \frac{\delta}{2}
\]

This pruning of the choice tree can't be easily calculated without
knowledge of the underlying distribution so we will define a different
tree which contains the above tree and can be calculated quickly.
The empirical tree is defined as in Yoav's paper \cite{F98}, by
including all choices which might be made from query results within
$2\alpha$ of the whatever value is returned by a statistical query.

Now, notice that if we define the $\hat{C}_{pi}$ to be the choice
space induced by an empirical pruning these same bounds will apply
because the choice spaces will be strictly larger, loosening the bound.

We spread the remaining $\delta /2$ confidence across all hypothesis
reachable in the pruned query tree in the same manner as the
microchoice bound. 

Let $L(z^N) = h$ be the output of the learning algorithm.

We now have the following two theorems for the realizable and agnostic cases:
\begin{thm}
(Realizable Adaptive Microchoice Theorem) For any \( 0<\delta <1 \) and the measure \( m(h)=\prod _{m=1}^{M(h)}\frac{1}{|\hat{C}_{pm}(h)|} \) over hypothesis
space, \( H \), 

\[
\Pr_{z^N}(L(z^N)=h:E_{P}(h)>\frac{1}{N}(\ln \frac{1}{\delta }+\sum _{m=1}^{M(h)}\ln |\hat{C}_{pm}(h)|))<\delta \]

\end{thm}
\begin{proof}
The same as the Realizable Microchoice theorem, except the choice
spaces, $C_i$ are pruned to include only the likely outcomes
$\hat{C}_{pi}$ and we must have that every query, $\chi$ returned a result within 
\[
\sqrt{\frac{1}{2N}(\ln \frac{2}{\delta} + \sum_{i=1}^{M(\chi)} \ln |C_{pi}+1|)}
\]
\end{proof}
\begin{thm}
(Agnostic Adaptive Microchoice Theorem) For any \( 0<\delta <1 \) and the measure \( m(h)=\prod _{m=1}^{M(h)}\frac{1}{|C_{pm}(h)|} \) over the
hypothesis space, \( H \),

\[
P(L(z^N)=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_{pm}(h)|)})<\delta \]

\end{thm}
\begin{proof}
The same proof as for the Realizable Adaptive Microchoice theorem
starting with the Agnostic Microchoice theorem instead of the
Realizable Microchoice theorem.
\end{proof}

Now, we can compare the results with Yoav's work.

\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 Adaptive 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 choices from small subspaces, this is often
computationally feasible. The Adaptive 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 Adaptive Microchoice bound and Yoav's bound by
a process of conglomerating the the subspaces of the Microchoice bound. Consider
a particular choice space, \( C_{pi} \) with elements, \( c_{pi} \). Each \( c_{pi} \) indexes another choice
space, \( C_{pi+1}(c_{pi}) \). If the computational resources to calculate \( C_{pi,i+1}=\cup _{c_{pi}\in C_{pi}}C_{pi+1}(c_{pi}) \), then \( |C_{pi,pi+1}| \) can be used in
place of \( |C_{pi}||C_{pi+1}| \) in the adaptive microchoice bound. In the extreme case where 
all \( C_{pi+1}(c_{pi}) \) are identical,
this can make the bound significantly tighter. By repeating this process for
the duration of the algorithm we 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 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}
