\documentstyle[12pt,fullpage,named,epsf]{article}

\renewcommand{\baselinestretch}{1.4}

\newcommand{\myindex}[1]{\mbox{\scriptsize #1}}
\newcommand{\mst}{\mbox{$\star$}}
\newcommand{\sbold}[1]{\mbox{\footnotesize \bf #1}}
\newcommand{\loocve}{\sbold{LOOCVE}}
\newcommand{\loocv}{\sbold{LOOCV}}
\newcommand{\expr}{\sbold{expr}}
\newcommand{\corrupt}{\mbox{corrupt}}
\newcommand{\ndatapoints}{\mbox{$N_{\mbox{\footnotesize datapoints}}$}}
\newcommand{\nmodels}{\mbox{$N_{\mbox{\footnotesize models}}$}}

\newcommand{\xbar}{\bar{x}}

\input{/home/r2/oded/research/NIPS93/include.tex}

\newcommand{\mathi}{\it i}

\newcommand{\myillustrate}[4]{{\begin{figure}
    \centerline{\epsfxsize= #4 in \epsffile{#3}}
    \caption{#2} \label{#1}
  \end{figure}}}


\title{{\bf The Racing Algorithm: Model Selection for Memory Based Learners}}

\author{\parbox[t]{3in}
{\begin{center} {\bf Oded Maron} \\ MIT AI Lab\\ NE43-755, 545
Tech.\ Sq.\ \\ Cambridge, MA 02139\\ {\tt oded@ai.mit.edu}\\ \end{center}}
\parbox[t]{3in}
{\begin{center} {\bf Andrew W.\ Moore}\\ Carnegie Mellon University \\
School of Computer Science \\ Pittsburgh, PA 15213\\ {\tt awm@cs.cmu.edu}\\ \end{center}}
}
\date{}

\begin{document}

\maketitle

\begin{abstract}

Given a set of models and some training data, we would like to find
the model which best describes the data.  Finding the model with the
lowest generalization error is a computationally expensive process,
especially if the number of testing points is high or if the number of
models is large.  Optimization techniques such as hill climbing or
genetic algorithms are helpful but can end up with a model which is
arbitrarily worse than the best one (local minima) or even worse,
cannot be used because of the lack of a distance metric on the space
of discrete models.  In this paper we develop a technique called
``racing'' which tests the set of models in parallel, quickly
discarding those models which are clearly inferior and concentrating
the computational effort on differentiating among the better models.
We use racing to select among various memory based models and to find
relevant features in applications ranging from robot juggling to
lesion detection in MRI scans.

\end{abstract}

\section{Introduction}

The problem of model selection can be thought of as trying to find the
best student in a classroom.  The teacher has the task of not only
teaching the students some subject, but also of testing them to find
out which student has best learned the subject.  This problem, in
different scaling, turns up over and over again in the Machine
Learning community: which neural net architecture gives the best
generalization error?  What should the value of $k$ be in a
{\it k}-nearest-neighbor algorithm?  Should I use a decision tree, a neural
net, a memory-based learner, or just a random guesser?  Which of the
50 features are relevant for this problem?  Note that we would like to
efficiently answer these questions for one problem at a time, and not
in general for all problems.

There are two popular ways to determine a student's grade, or a
model's generalization error.  The first is to use a test set which
does not intersect the training set.  The average error on the test
set is a good estimate of the generalization error of the model on
future points drawn from the same distribution.  The second method is
to use leave-one-out cross validation.  The model is trained on all
points but one, and is then queried for the value at that point.  This
is repeated for every point in the training set and the prediction
errors are averaged to give an estimate of the generalization error.

This paper introduces a method called ``racing'' for both efficiently
and accurately selecting the best model out of a set.  The efficiency
of the algorithm is measured by the number of queries that it makes,
where a query returns one model's error on one particular test point.
The accuracy of the algorithm is measured by the likelihood of not
returning the best model out of a set.  An important aim of the paper
is to improve on previous approaches such as brute force and
hill-climbing methods which can be too intractably expensive or highly
inaccurate.

The idea behind racing is to test the various models in parallel, one
test point at a time.  This way, a running average can be maintained
for each model's error.  This is an estimate of the model's true error
had it been tested on all of the test points.  Using statistical
bounds we can also determine how close the estimated error is to the
true error of each model.  After only a small number of test points,
we can usually tell the very best models (those with lowest error, or
highest grade) from the very worst models (those with the highest
error).  The models which are significantly worse than the best ones
are thrown out of the race and are not tested any more.  The more test
points that are seen, the tighter the estimated error is to the true
error; therefore, more and more models can be differentiated from each
other and eliminated.  This algorithm concentrates the computational
effort on the best models, while discarding the inaccurate models and
not testing them unnecessarily.

\subsection{Memory based learning}

Racing can be applied to any collection of models, but is particularly
suited to {\em memory-based} methods.  Memory based learning (MBL) is
an encompassing name for a variety of statistical and machine learning
methods such as nearest-neighbor and local weighted regression.  The
underlying principle of memory based learning is to simply remember
all of the training examples.  Variants of the nearest-neighbor method
are then used for prediction.  Every learning method must perform some
sort of memorization (otherwise it would be ignoring its training);
memory based learning differs in that the training does not modify any
internal parameters with each new training point --- it simply stores
it in memory.

Let us look at a learner which is not memory based.  For example, if
we assume that the function we are trying to learn is a quadratic,
then we need to learn the three parameters ($a$,$b$, and $c$) in the
equation $f(x) = ax^2 + bx + c$.  When the program is asked to
predict the value at $x=5$, it plugs in the value of $x$ into the
quadratic with the trained parameter values.  This is not a memory
based learner since we do not keep track of all of the training points,
only of the parameters.  On the other hand, with
a memory based learner, the training points, which are of the form
$(x,f(x))$, are kept in memory.  When the program is asked to predict
the value at $x=5$, it looks in memory for a few points whose x-values
are closest to 5.  The value of the function at those points is
averaged (or regressed) and returned as the predicted value.

Often we do not know that the function we are trying to learn
is quadratic, or a polynomial, or piecewise linear, or has a normal
distribution.  Therefore, nonparametric methods such as
nearest-neighbor are more robust than methods that make assumptions
about the parameters which characterize the space of functions.  In
addition, we can see that nearest-neighbor techniques also fall into a
different {\em computational} category from parametric methods (or even
very weakly parametric methods such as neural nets and decision
trees).  There is negligible computation involved in training
(memorizing) and most of the effort goes into finding the neighbors of
the queried point.  

Within this general framework, there are still many choices for
specifying a model: 
\begin{itemize}
\item How do we measure ``nearness''?
\item How many neighbors should we look at?
\item What method should be used for averaging the outputs of the
neighbors?
\item Should we try to perform local regression rather than local
averaging?
\item How much smoothing, or weighting, should we do over the
regression or average?
\end{itemize}

Following are some possible answers to these questions:

\subsubsection{{\it k}-nearest-neighbors}

The motivation for {\it k}-nearest-neighbors is summarized by this quote:

\begin{quote}
There seems to be a need for discrimination procedures whose validity
does not require the amount of knowledge required by the normality
assumption, the homoscedastic assumption, or any assumption of
parametric form. \ldots can reasonable discrimination procedures be
found which will work even if no parametric form can be assumed?~\cite{fix:nonparametric}
\end{quote}

Fix and Hodges answered their own question by
introducing nearest-neighbor classification.  The principle is simple:
when queried for the class of some attributes, return the class of the
point with the most similiar attributes.  Similarity is usually measured
by using the Manhattan or Euclidean metric, depending on the type of
the attributes.  The method generalizes easily to {\it k}-nearest-neighbors,
where a majority rule is used to find the correct class, or
averaging is used for continuous outputs.  A larger value for $k$
makes the rule more stable against outliers and noisy data.
However, making $k$ too large destroys the advantage of locality that
a nearest-neighbor algorithm inherently owns.  

\subsubsection{Weighted distance metric}

Finding
an appropriate distance metric is often the toughest hurdle in attempting
to use a memory based learning system.  The distance metric is
responsible for the representation of the memorized data.  It decides
which attributes are more important than others and aligns all the
attributes into the same representation.  To give an example, let
us say that we are trying to predict hat size from height and weight.  The
data points are of the form (height, weight, hat-size).  Given a query
$q$ of the form (6ft,155LB), we look for 
the point $p$ which minimizes the distance between $p$ and $q$.  However,
it is probably not a good idea to use the standard euclidean distance
since differences in pounds are much less significant than differences
in feet: someone who is (2ft,155LB) is closer to $q$
than someone who is (6ft,165LB) using the plain euclidean distance
metric.  Clearly, we need a weighted metric that forces differences in
heights to be comparable to differences in weight.  The initial
representation (feet and pounds) should be changed to a more suitable
one. 

However, that is not the end of our problems.  What if hat-size is
predominantly affected by height, and only marginally by
weight?  In that case, we need to count the height attribute
much more than the weight attribute so that points with similar
heights will be close together, even if they have very different
weights.

Both problems can be solved with a priori knowledge of the importance
and scale of the various attributes, but one of the main reasons for
using nearest-neighbor methods is to get away from making any
assumptions about the best representation for the data.  The best
weighting, like the best value of $k$, must be searched for or learned.

\subsubsection{Kernel regression}

It is intuitive that some neighbors are more important than others.
Specifically, neighbors which are closer to the queried point should
count more toward its classification than neighbors which are farther
away.  `Kernel regression' performs weighted averaging (instead of a
uniform average) over the space of neighbors.  The weighting function
which we use is taken from~\cite{moore:brute-force}.  The weight of the
$i^{th}$ point ($x_i$) with respect to the query point $q$ is $w_i$.

\begin{equation}
w_i = \frac{1}{1 + c \cdot (distance(x_i,q)/K_{width})^2}
\label{equation:weighting}
\end{equation}

The parameter $K_{width}$ determines the width of the weighting (or
smoothing) range.  The larger it is, the more weight is given to
distant points.  Again, it is usually not feasible to estimate this
parameter before trying out various values of it.  In this paper, we
use the value of $c=20$.

\subsubsection{Local regression and local weighted regression}

The computationally intensive part of nearest-neighbor algorithms is
usually to find the $k$ neighbors.  Once that is done, we can perform
more complex operations than averaging in order to predict the queried
value.  For example, {\em local regression} involves finding a
least-squares linear fit of the neighbors.  {\em Local weighted
regression}~\cite{cleveland:lwr} attempts to minimize the weighted
error, where the weighting function is the one shown in
Equation~\ref{equation:weighting}.

%% Deleted by awm
%% \subsection{Example of different memory based learning boxes}
%% 
%% \myillustrate{neighbor-example-train}{75 random training points with
%% noise}{/home/r2/oded/research/msthesis/figures/training_points.ps}{2.5}
%% 
%% \begin{figure}
%% \begin{minipage}{2.4in}
%% \centerline{\epsfxsize= 2.4in \epsfysize= 2.4in
%% \epsffile{/home/r2/oded/research/msthesis/figures/A01.ps}}
%% \centerline{(a) one nearest neighbor}
%% 
%% \end{minipage}
%% \ \ \
%% \begin{minipage}{2.4in}
%% \centerline{\epsfxsize= 2.4in \epsfysize= 2.4in
%% \epsffile{/home/r2/oded/research/msthesis/figures/A05.ps}}
%% \centerline{(b) five nearest neighbors}
%% \end{minipage}
%% \\
%% \begin{minipage}{2.4in}
%% \centerline{\epsfxsize= 2.4in \epsfysize= 2.4in
%% \epsffile{/home/r2/oded/research/msthesis/figures/A30.ps}}
%% \centerline{(c) Kernel regression, $K_{width}=\frac{1}{16}$}
%% \end{minipage}
%% \ \ \
%% \begin{minipage}{2.4in}
%% \centerline{\epsfxsize= 2.4in \epsfysize= 2.4in
%% \epsffile{/home/r2/oded/research/msthesis/figures/A50.ps}}
%% \centerline{(d)Kernel regression, $K_{width}=\frac{1}{4}$}
%% \end{minipage}
%% \\
%% \begin{minipage}{2.4in}
%% \centerline{\epsfxsize= 2.4in \epsfysize= 2.4in
%% \epsffile{/home/r2/oded/research/msthesis/figures/L30.ps}}
%% \centerline{(e) Local weighted regression}
%% \centerline{ with $K_{width}=\frac{1}{16}$}
%% \end{minipage}
%% \ \ \
%% \begin{minipage}{2.4in}
%% \centerline{\epsfxsize= 2.4in \epsfysize= 2.4in
%% \epsffile{/home/r2/oded/research/msthesis/figures/L70.ps}}
%% \centerline{(f) Local weighted regression }
%% \centerline{with $K_{width}=1$}
%% \end{minipage}
%% \caption{Testing results on various memory based learning algorithms}
%% \label{neighbor-example}
%% \end{figure}
%% 
%% To give an intuitive notion of how the various memory based learning
%% methods fit a function, We trained some of them on 75 random points from the
%% function $f(x) = 0.01x^3 - 3x^2 - 5x + 4$ in the interval
%% $[-300,400]$.  We also added 10\% random noise to all of the training
%% points, which are shown in Figure~\ref{neighbor-example-train}.  We
%% then took 1000 random points in the interval $[-350,450]$ and the
%% predictions made by 1-nearest-neighbor, 5-nearest-neighbor, kernel
%% regression with $K_{width}=\frac{1}{16}$ and $K_{width}=\frac{1}{4}$,
%% and local weighted regression 
%% with $K_{width}=\frac{1}{16}$ and $K_{width}=1$ are shown in Figure~\ref{neighbor-example}.
%% 
%% As can be seen, having a kernel width which is too large results in
%% too much smoothing, while using only a few nearest neighbors results
%% in too much prediction noise.  Efficient decision-making of which of
%% these models is best is the topic of this paper.

\subsection{Determining the accuracy of a model}

To determine the accuracy of a model, we measure the difference
between the predictions of the model and the true answers on a set of
points where we have the true answers.  However, we need to be careful
not to use the training set for testing as well.  For example, using a
1-nearest-neighbor method, we can get zero prediction error by testing
on the training points.  However, the performance of
1-nearest-neighbor on new points (the generalization error) can be
much poorer.  What is needed is a way to test not only rote
memorization, but also the ability to generalize.

There are two popular methods of estimating the learner's ability to
generalize.  One is partitioning the entire set of the teacher's
examples into a training set and a testing set.  The learner is
trained on the training set, but its performance is determined on its
average prediction error for points in the testing set.  A prediction
query involves giving the learner the attributes, but withholding the
correct outputs.  The learner's guess at the outputs is then compared
to the true outputs.

The second method of estimating generalization is called {em cross
validation}.  In the case of leave-one-out cross validation, we can
use the same set of points for both training and testing by performing
the following trick: train on all points except one; perform a
prediction query on the one point which was held out; repeat this
process for all points and return the average prediction error of all
the iterations.  This method might seem more computationally expensive
than the test-set method, but it does have certain advantages, namely
in cases where we cannot afford to partition the few training points
that we have (i.e., there are not enough points) or when we need a
good estimate of the error distribution over the entire space we are
trying to learn.  Also, as we will show bellow, for lazy learners such
as memory-based methods cross validation is just as cheap
computationally as finding the test-set error.

Cross validation is a special case of a number of statistical reuse
techniques such as jackknife and bootstrapping.  For a readable
overview of these techniques, see~\cite{efron:statistical}.

%% \subsection{Preprocessing}
%% 
%% In order to reduce the cost of finding a nearest neighbor, researchers
%% have used two types of preprocessing methods.  The two methods are
%% organizing the data into a fast-access structure (such as a k-d tree)
%% or eliminating redundant training points (also known as editing).  By
%% processing the data before the queries, a speedup in prediction is
%% achieved at the expense of non-negligible training time. 
%% 
%% A k-d tree~\cite{preparata:comp-geometry} divides the space of points
%% into hyper-ranges which span the space and allow nearest-neighbor
%% queries of almost any size to be completed in $O(\log n)$, where $n$
%% is the number of training points.  This is an improvement over the
%% $O(n)$ behavior of the obvious brute force algorithm.  There
%% is an $O(n \log n)$ preprocessing cost and O(n) of additional memory
%% is needed to maintain the tree.  
%% 
%% Editing methods approach the problem by attempting to reduce $n$, the
%% number of points that need to be searched.  There are various
%% approaches, which include throwing out points which are classified
%% correctly, merging points which are similar, and iteratively
%% condensing the data set.  For more detailed discussion of these
%% methods, see~\cite{dasarathy:collection}.  

\subsection{The connection between MBL and racing}

Unlike other machine learning methods, there is not an attempt to
force the training points into a decision tree, a neural net, symbolic
rules, or any formal representation.  The points act as their own best
representation.  A direct implication of this fact is that no work
needs to be performed during training --- we simply store the points in
memory.  Therefore, memory based learners are lazy; they only do work
when queried for prediction of a new point. 

In this paper, we leverage the laziness in two ways.  First,
computing the leave-one-out cross validation error is just as cheap as
computing the test-set error.  That is because there is no need to
retrain on all of the points but one.  We can just `cover up' that
point in memory and that is equivalent to retraining.  Therefore, we
have a quick, reliable estimator for the error of a memory based model
by performing leave-one-out cross validation on all the points in the
training set.  Second, we can look at many different learners without
worrying about the initial expense of training all of them.  The only
significant computation arises when they are tested.

Therefore, a model selection technique such as racing is perfectly
suited for selecting among various memory based learners.  We can
train as many as we want to do with zero cost.  The only computational
expense occurs during testing, and racing attempts to minimize exactly
this expense.  Using racing with other collections of models is also
possible, but training time considerations then need to be included.

\section{Previous approaches}
Traditionally, there have been a number of popular ways to search through a
large collection of models.  Brute force was always applicable and
gave the desired result, but at a high computational price.  Descent
methods such as hill climbing and conjugate gradient were much faster,
yet did not guarantee to return the right result and, even worse, was
not applicable in many cases.  Other techniques such as simulated
annealing and genetic algorithms fall into similar traps, since
provably convergent versions of simulated annealing and genetic
algorithms are too slow to be used in practice.  Hoeffding
Races manages to lessen the evils of these techniques, while retaining
their benefits.

\subsection{Brute force}

Brute force attacks the problem in the simplest
possible way.  Given $m$ trained learners and a test set which
consists of $n$ points, it performs a prediction query on every point
for every single learner.  It then computes the mean squared error
of the predictions of each learner and selects the learner with
the lowest error.  This algorithm runs in time $O(n \cdot m)$, but
always returns the best learner.

\subsection{Descent methods}

Gradient descent, or hill climbing~\cite{press:recipes}, treats the
collection of models and their prediction error as a continuous and
differentiable surface.  It starts at some point on this surface, and
proceeds to `descend' in the direction which has less error.  This
approach to memory-based optimization has been taken
by~\cite{atkeson:approximating,david.lowe.unknown}.

The algorithm stops when it reaches a local minimum.  In other words,
when all of the neighboring models have higher error, the algorithm
returns the current model.  This algorithm is much faster than brute
force since it does not need to find the error of every single model.
It only needs to compute the error for the learners which are on the
path to the optimal learner.  However, there are two major problems:
local minima and applicability.

\begin{figure}
\begin{minipage}{2.5in}
\centerline{\epsfxsize= 2.5in \epsfysize= 3.5in \epsffile{/home/r2/oded/research/NIPS93/local-minima.ps}}
\end{minipage}
\ \ \
\begin{minipage}{2.5in}
\caption[Example of local minima in model selection]{A space of models
consisting of local-weighted-regression 
models with different numbers of nearest neighbors used.  The global
minimum is at one-nearest-neighbor, but a gradient
descent algorithm would get stuck in local minima unless it happened
to start in in a model where $k<4$.} 
\label{local-minima}
\end{minipage}
\end{figure}

Local minimum is a well documented and analyzed problem with gradient
descent.  To give an example of it in the realm of model
selection, let us say that we need to select among nine
{\it k}-nearest-neighbor learners.  They differ in their $k$ (i.e., the
number of neighbors they look at in order to make a prediction).  The
error of each learner is plotted in Figure \ref{local-minima}.  The
points are connected so that we can pretend that the surface is
continuous.  Gradient descent starts at one of the points on the
surface and moves toward a learner which has lower error.  This method
works fine if the initial point is $k=3,2,$ or $1$.  However, for any
other starting point, the algorithm will get stuck at a local minimum
either at $k=4$ or $k=9$.  In general, the error at the local minimum
can be many times larger than the error at the global minimum, and in
addition, the chance of starting at a place which will lead to a
global minimum can be arbitrarily small.  

%%\begin{figure}
%%\begin{minipage}{3in}
%%\centerline{\epsfxsize= 3in \epsfysize= 4in
%%\epsffile{/home/r2/oded/research/msthesis/figures/classroom-arrow.ps}}
%%\end{minipage}
%%\ \
%%\begin{minipage}{2.5in}
%%	\caption[Gradient descent search for the best student in a classroom]
%%		{An example of gradient descent search for the best student in
%%		a classroom}
%%	\label{classroom}
%%\end{minipage}
%%\end{figure}

There is an even more serious problem with gradient descent that was
ignored in the last example --- namely, there are many instances when
it is not even applicable to model selection.  At every step of the
gradient descent algorithm, we need to find a collection of models
which are `near' the current model.  However, the collection of models
may not have a distance metric (and therefore no concept of `near')
defined on it.  For example, how far is a neural network from a
nearest-neighbor model?  How far is a decision tree from a local
weighted regressor?

It is possible to {\em impose} a distance metric on any collection of
objects, for example in the {\it k}-nearest-neighbor example, or
somewhat deviously by ordering the models according to simplicity.
However, just because we can impose a metric does not mean that it is
correct, or even useful.  Just because there is a parameter to tune
(e.g. $k$ in {\it k}-nearest-neighbor) does not mean that there is a
predictable relation between a change in the parameter and the
performance of the algorithm.  In the cases where there is no clear
distance metric among the various models, all of them must be raced.
This is a problem with all minimization methods. Gradient descent,
steepest descent, Newton's method and conjugate gradient are just as
susceptible to this problem as its less-capable relative.

\subsection{Genetic algorithms and simulated annealing}

The same problems described with descent methods apply to these
techniques as well, only less explicitly.  In a genetic
algorithm~\cite{goldberg:genetic}, we 
start with a population of different models, where each member is
represented by a description which can be mutated and crossed with
other descriptions.  There is a certain probability that some
bit in the representation mutates.  Therefore, there is a distance imposed
between models which is proportional to the average number of generations it
takes to get between two representations.  Again, this distance metric is
%% awm delete completely
arbitrary and is based solely on the representation of the
models, which is just as meaningless as having it based on their
position in a room.

Simulated annealing~\cite{kirkpatrick:annealing} at high temperature 
performs as slowly as brute
force.  At low temperatures, it is restricted by the same problems
described above for gradient descent.  There are cooling schedules
which guarantee convergence at a global minimum, but they are too slow
to be practical.

\section{Racing: Hoeffding and Bayes}

In this section we formalize the notion of ``racing'' by defining what
it means for one model to be winning the race over another.  We use
two different statistical bounds to determine with a certain
confidence when one model's average error is significantly smaller
than another's.  Hoeffding's bound is a general bound which only
relies on the assumption that the error queries are drawn
independently.  Using Bayesian bounds gives tighter results, at the
expense of assuming that the errors are drawn from a normal
distribution.

\subsection{Hoeffding Races}

\subsubsection{Hoeffding's Bound}

Let us say that we have $N$ points with which to test a given model.
If we were to test a model on all of them, then we would have an
average error which we will call $E_{true}$.  However, if we only tested
the model on 10 points, then we only have an estimate of the true
average error.  We call the average after only $n$ points ($n < N$)
$E_{est}$ since it is an estimate of $E_{true}$.  The more points we test
on (the bigger $n$ gets), the closer our estimate gets to the true
error.  How close is $E_{est}$ to $E_{true}$ after $n$ points?
Hoeffding's bound lets us answer that question when the $n$ points are
picked with an identical independent distribution from the set of $N$
original test points.  In this case, we can say that the probability
of $E_{est}$ being more than $\epsilon$ away from $E_{true}$ is

\begin{equation}
\Pr(|E_{true} - E_{est}| > \epsilon) < 2 e^{-2n{\epsilon^2}/B^{2}} 
\label{equation:hoeffding}
\end{equation}

\noindent
where $B$ bounds the greatest possible error that a model can
make~\cite{hoeffding:bound}. 

We would like to say that ``we are 99\% confident that our estimate of
the average error is within $\epsilon$ of the true average error'', or
in other words, $\Pr(|E_{true} - E_{est}| > \epsilon) < 0.01$.  We
denote the confidence parameter with $\delta$.  Equating $\delta$ with
the right-hand side of Equation~\ref{equation:hoeffding} gives us an
expression for $\epsilon$ in terms of $n$, $B$, and $\delta$.  

\begin{equation}
\epsilon(n) = \sqrt{\frac{B^{2}  \log(2/\delta)}{2 n}}
\label{equation:epsilon}
\end{equation}

Equation~\ref{equation:epsilon} tells us how close the estimated
mean is to the true mean after $n$ points with confidence $1-\delta$.
We will discuss how to obtain a value for $B$ in a later section.

\subsubsection{The algorithm}

The algorithm starts with a collection of learning boxes.  We call
each model a learning box since we are treating the models as if they
were black boxes.  We are not looking at how complex or time-consuming
each prediction is, just at the input and output of the box.  Associated
with each learning box are two pieces of information: a current
estimate of its average error and the number of points it has been
tested upon so far.  The algorithm also starts with a test set of size
$N$.  For leave-one-out cross validation, we can perform $N$ queries
on a training set of size $N$.

At each iteration of the algorithm, we randomly select a point from
the test set.  Then for each learning box:
\begin{itemize}
\item compute the error at the point by using that learning box.

\item update the learning box's estimate of its own average error rate.

\item use Hoeffding's bound and Equation~\ref{equation:epsilon} to
calculate how close the current estimate is to the true error for each
learning box.  
\end{itemize}

\begin{figure}
    \centerline{\epsfxsize= 5in \epsfysize= 3in 
		\epsffile{/home/r2/oded/research/NIPS93/example.ps}}
    \caption[Use of Hoeffding's bound to eliminate LBs]
	{An example where the best upper bound of
	learning box \#2 eliminates learning boxes \#1 and \#5.  The
	size of $\epsilon$ varies since each learning box has its own upper
	bound on its error range, $B$.} 
    \label{example}
\end{figure}

Each learning box now has a bound within which its true average error
lies.  We can eliminate those learning boxes 
whose best possible error (their lower bound) is still greater than the
worst error of the best learning box (its upper bound); see Figure~
\ref{example}.  The intervals get smaller as more points are tested
(since $\epsilon$ gets smaller as $n$ gets larger), thereby ``racing''
the good learning boxes and eliminating the bad ones.

\subsubsection{Ending the race}

We iterate and keep picking test points until one of three conditions
occur: 
\begin{enumerate}
\item All but one of the learning boxes have been eliminated.  The algorithm
simply returns it as the best one.  
\item The algorithm can also be stopped
once we have picked more than $N$ test points.  However, since we are
picking the testing points in an independent indentical distribution,
that is not a strict requirement.  
\item Alternatively, the
algorithm can be stopped once $\epsilon$ has reached a certain
threshold.  
\end{enumerate}
In any case, the algorithm returns a set of
learning boxes whose errors are indistinguishable to within
$2 \cdot \epsilon(n)$.

\subsubsection{Proof of correctness}

Notice that $1 - \delta$ is the confidence in Hoeffding's bound for
{\em one} learning box during {\em one} iteration of the algorithm.
What we need is to prove that the {\em entire} algorithm has some
confidence $1 - \Delta$ of returning the best learning box.

For the sake of a simpler proof, let us make the requirement of a
correct algorithm more stringent.  We will say that the algorithm is
correct if every learning box is within $\epsilon$ of its true error
at every iteration of the algorithm.  This requirement encompasses the
weaker requirement that we do not eliminate the best learning box.
An algorithm is correct with confidence $1 - \Delta$ if 
\begin{equation}
\Pr\{ \; all \; learning \; boxes \; are \; within \; \epsilon(n) \; on \; all \; iterations\}
\geq 1-\Delta \label{equation1} 
\end{equation}

What we would like to do is show the relationship between $\delta$
(the chance of being wrong on one learning box in one iteration) and
$\Delta$ (the chance of being wrong on the whole algorithm), so that when 
the user wants the algorithm to work with probability $0.999$, we can
translate that into the confidence that we need for each learning box
at each iteration.  We will be relying on the disjunctive probability
inequality which states that $Pr\{A \vee B\} \leq Pr\{A\} + Pr\{B\}$.

Let us assume that we have $n$ iterations (we have $n$ points in our
test set), and that we have $m$ learning boxes ($LB_{1}, \cdots,  LB_{m}$).
We start with the fact that: 
\begin{equation}
Pr\{ \; a \; particular \; LB \; is \; within \; \epsilon(i) \; on \; a
\; particular \; iteration \; i\} \geq 1-\delta
\end{equation}

Flipping that around we get:
\begin{equation}
Pr\{ \; a \; particular \; LB \; is \; wrong \; on \; a \; particular \;
iteration\} < \delta
\end{equation}

Using the disjunctive inequality we can say
\begin{eqnarray}
Pr\{ & a \; particular \; LB \; is \; wrong \; on \; iteration \; 1
\; \vee \nonumber \\
      & a \; particular \; LB \; is \; wrong \; on \; iteration \; 2
\; \vee \nonumber \\
      & . \; . \; .\nonumber \\
      & \; a \; particular \; LB \; is \;  wrong \; on \; iteration \; n\}    \leq \delta \cdot n
\end{eqnarray}

Let us rewrite this as:
\begin{equation}
Pr\{ \; a \; particular \; LB \; is \; wrong \; on \; any \; iteration
\; up \; to \; n\}
\leq \delta \cdot n
\end{equation}

Now we do the same thing for all learning boxes:
\begin{eqnarray}
Pr\{ & LB_{1} \; is \; wrong \; on \; any \; iteration \; \vee \nonumber \\
      & LB_{2} \; is \; wrong \; on \; any \; iteration \; \vee \nonumber \\
      & . \; . \; .\nonumber \\
      & \; LB_{m} \; is \; wrong \; on \; any \; iteration \} \leq \delta \cdot n \cdot m
\end{eqnarray}

or in other words:
\begin{equation}
Pr\{ \; some \; LB \; is \; wrong \; in \; some \; iteration\} \leq \delta
\cdot n \cdot m
\end{equation}

We flip this to get:
\begin{equation}
Pr\{ \; all \; LBs \; are \; within \; \epsilon(n) \; on \; all \; iterations\}
\geq 1 - \delta \cdot n \cdot m \label{equation2}
\end{equation}

Clearly, Equation~\ref{equation2} is the same as
Equation~\ref{equation1} and we can therefore conclude that $\delta =
\frac{\Delta}{n \cdot m}$.  When 
we plug this into Equation~\ref{equation:epsilon} (our expression for
$\epsilon$ from the previous section), we pump up $\epsilon$, and
thereby ensure the correctness of this algorithm with confidence
$\Delta$.  The new $\epsilon$ is expressed as: 

\begin{equation}
\epsilon(n) = \sqrt{\frac{B^{2}  (\log(2 n m) - \log(\Delta))}{n}}
\end{equation}

This is an extremely pessimistic bound on $\Delta$ and tighter proofs are
possible \cite{omohundro:suggestion}.  It is pessimistic in two regards:
first, it assumes that all learning boxes are completely independent
of each other.  Second, it assumes that the error of a learning box
after seeing $n$ points is completely independent of its error after
seeing $n+1$ points.  This is clearly a worst case assumption, and
most PAC bounds are made tighter by leveraging this point.

\subsection{Bayesian Races}

Hoeffding's bound is as tight as we can get without making additional
assumptions about the distribution of the errors we get from a
learning box.  If we assume that the errors are normally distributed,
then we can use Bayesian statistics to achieve a tighter bound on the
probability that one learning box is better than another.

\newcommand{\xvt}[3]{{#1}^{#2}_{\mbox{\scriptsize \it #3}}}
\newcommand{\xvtrue}[2]{\xvt{#1}{#2}{true}}
\newcommand{\evtrue}[1]{\xvtrue{E}{#1}}
\newcommand{\vvtrue}[1]{\xvtrue{V}{#1}}
\newcommand{\ejtrue}{\evtrue{j}}
\newcommand{\ejptrue}{\evtrue{j'}}
\newcommand{\vjtrue}{\vvtrue{j}}
%% \newcommand{\bfrac}[2]{\frac{\displaystyle #1}{\displaystyle #2}} 

The RACE algorithm first randomizes the order of the datapoints.  For
the $j$th model the distribution of leave one out errors is
gaussian. Let us say it has unknown mean $\ejtrue$ and unknown
variance $\vjtrue$.

As evidence accumulates, the uncertainty of $\ejtrue$ decreases.
Let \(\hat{\mu}_{nj} \) and
\( \hat{\sigma}^{2}_{nj} \) be the sample mean and variance of model $j$'s
errors up to the $n$th iteration, when all surviving models
have been evaluated on $n$ datapoints.
\begin{equation}
\hat{\mu}_{nj} = \frac{1}{n} \sum_{i=1}^{n} e_j(i)
\end{equation}
\begin{equation}
\hat{\sigma}^{2}_{nj} = \frac{1}{n - 1} \sum_{i=1}^{n} 
       \left(e_j(i) - \hat{\mu}_{nj} \right)^{2}
\end{equation}
defining $e_j(i)$ as the leave-one-out error when the $j$th model is
used to predict the $i$th datapoint.  It should be noted that these
statistics can be updated incrementally: $\hat{\mu}_{(n+1)j}$ and
$\hat{\sigma}^2_{(n+1)j}$ can be defined in terms of $n$,
$\hat{\mu}_{nj}$, $\hat{\sigma}^2_{nj}$, and $e_j(n+1)$.


For each model we use Bayesian statistics, along with the values
$\hat{\mu}_nj$, $\hat{\sigma}^2_{nj}$, and $n$, to put a probability
distribution on $\ejtrue$. This is a relatively elementary process.

Let us assume that a priori we know nothing about the distribution
except that it is normal. The true mean $\ejtrue$ might be any
value between $-\infty$ and $+\infty$. The variance $\vjtrue$ 
might be any value between $0$ and $+\infty$. This ignorance
can be turned into the uninformative priors:
\begin{equation}
p(\ejtrue) = \mbox{Constant}
\end{equation}
\begin{equation}
p(\vjtrue) = \mbox{Constant} / \sigma
\end{equation}
Where $p(.)$ denotes a probability density function (note that
neither of these priors is a legitimate probability density function.
Such an approximation is harmless (see~\cite{schm:msrn} for more details).

The marginal posterior distribution of the mean $\ejtrue$ is a student
distribution with mean $\hat{\mu}_{nj}$, variance
$\hat{\sigma}^{2}_{nj} / n$, and $n - 1$ degrees of freedom.  The
cumulative density function of this distribution can then be used to
compute the probability that the true mean $\ejtrue$ lies within any given
interval.

Figure~\ref{race-fourgauss.ps} gives an example with four models
racing.  
We  eliminate the $j$th model if there exists some other model
$j'$ for which
\begin{equation}
\label{eq:ejj}
\mbox{Prob}(\ejtrue < \ejptrue \mid e_j(1)
, \ldots  e_j(n) , e_{j'}(1) , \ldots  e_{j'}(n) )
\end{equation}
is less than $\delta$.  $\delta$ again denotes the confidence that is
required. For example, if $\delta = 0.001$ that means we are willing
to risk a one in a thousand chance of making an error on this test.
Statistics are gathered and models are eliminated until only one model
remains, or we run out of datapoints, whereupon we select the model
with the lowest $\hat{\mu}_{nj}$.  In Figure~\ref{race-fourgauss.ps}
it would be very probable that $\evtrue{2}$ is lower than $\evtrue{4}$,
but only fairly probable that $\evtrue{1}$ is lower than $\evtrue{4}$.

%% \begin{figure}[thbp]
%% \psfig{file=race-fourgauss.ps,height=4cm}
%% \caption{The posterior distributions on the errors of four models
%% involved in a race. The lower the error the better, so it
%% seems very unlikely that model 4 will turn out to be better than model 2
%% at the end of the race.  Thus model 4 is eliminated at this point.}
%% \label{race-fourgauss.ps}
%% \end{figure}

\begin{figure}
\begin{minipage}{3.5in}
\centerline{\epsfxsize= 3.5in \epsfysize= 2.5in \epsffile{race-fourgauss.ps}}
\end{minipage}
\ \ \
\begin{minipage}{2.5in}
\caption{The posterior distributions on the errors of four models
involved in a race. The lower the error the better, so it
seems very unlikely that model 4 will turn out to be better than model 2
at the end of the race.  Thus model 4 is eliminated at this point.}
\label{race-fourgauss.ps}
\end{minipage}
\end{figure}

We thus need to compute the probability that the means of one unknown
gaussian distribution is less than the mean of another gaussian
distribution, where in each case the posterior distributions of each
mean can be computed with Bayesian statistics. This is achieved by the
Welch approximation to the Behrens-Fisher problem~\cite{wlch:thsg}.

Given two samples with the same assumptions as before, let the
first sample have size $n_1$, sample mean ${\xbar}_1$ and 
sample variance $s^2_1$. The corresponding values for the second sample are
$n_2$, ${\xbar}_2$ and $s^2_2$.
Let
\begin{equation}
u_1 = s^2_1 / n_1 , u_2 = s^2_2 / n_2 ,
\end{equation}
\begin{equation}
b = u_1 / (u_1 + u_2).
\end{equation}
Then $\mu_1 - \mu_2$ (the signed difference between the population
means) has, approximately, a student distribution with mean ${\xbar}_2 - 
{\xbar}_1$, variance $u_1 + u_2$, and degrees of freedom
\begin{equation}
{\left( \bfrac{b^2}{n_1 - 1} + \bfrac{{(1 - b)}^2}{n_2 - 1} \right)}^{-1}.
\end{equation}
By computing the cumulative probability of this distribution, we can compute
the probability that $\mu_1 < \mu_2$.


\section{Extensions}
This section describes several extensions and expansions of the basic
racing algorithm.  We describe how to determine a bound on $B$ --- the
maximum error of a model on any test query, to be used in Hoeffding
races.  We also describe a method for tightning the confidence
intervals for each model and for eliminating redundant models in the
set (models which are statistically equivalent).

\subsection{Bounding errors}

The most obvious obstacle to implementing Hoeffding Races is finding a
value for $B$, the maximum error of a 
learning box.  For classification problems, there is no difficulty ---
$B$ is simply $1$.  That is 
because the worst mistake that the algorithm can make is a
misclassification which has an error of $1$.  For regression problems
the solution is less straightforward.  If we know something about the
learner and something about the data, then we can try to put some
finite bound on $B$.  If that is not possible, then we can attempt to
estimate $B$ by adding a few standard variances to the average error
of this learner.  Since the average error and variance are
updated after every new point, the value of $B$ also gets
modified at each iteration.  The value of $B$ tends to fluctuate wildly
during the first few points until the average and variance settle
down.  To avoid that, we only start racing after collecting errors from
about 30 points from each learning box.  

\subsection{Shrinking the intervals}

With a little effort, we can actually tighten the bounds around the
estimated error for each learning box.  First we need to name a few
important components of a learning box.  Let us call the estimated
error for the $k^{th}$ learning box at the $i^{th}$ iteration
$E_{est}^k(i)$.  We will call the lower bound of that learning box
$lower^k(i)$ and likewise the upper bound will be called $upper^k(i)$.
These can be calculated by $E_{est}^k(i) - \epsilon(i)$ and
$E_{est}^k(i) + \epsilon(i)$ respectively.  From now on, we will be
dropping the superscript, since we will be talking about one learning
box, but applying the ideas to all of them.

\begin{figure}
\centerline{\epsfxsize= 4in \epsfysize= 3in 
		\epsffile{/home/r2/oded/research/msthesis/figures/shrink.ps}}
\caption{Example of how to shrink the interval bounds}
\label{shrink-example}
\end{figure}

During the course of running the race, all three of these components
tend to fluctuate.  $E_{est}(i)$ moves around with every new point,
trying to get closer to the true error.  $lower(i)$ and $upper(i)$
move around for two reasons: the first is that $\epsilon$ gets smaller
at each iteration; the second is that $E_{est}(i)$ changes after
almost every new point.  However, despite all of this movement, we are
guaranteed that with confidence $1-\Delta$, $E_{est}(i)$ will stay
between the lower and upper bounds.  What if at iteration $i+1$ we get
a point upon which the learning box performs very badly?  In this
case, $E_{est}(i+1)$ is larger than $E_{est}(i)$.  The bounds have
become tighter because of the decrease in $\epsilon$, but they have
been transformed by the increase in $E_{est}$.  However,
$E_{est}(i+1)$ is guaranteed to stay not only within the bounds at
iteration $i+1$, but also within the bounds at all iterations until
now.  Therefore, the new upper bound should not be $E_{est}(i+1) +
\epsilon(i+1)$, but instead the tighter 
\begin{equation}
upper(i+1) = Min(E_{est}(i+1) + \epsilon(i+1) , E_{est}(i) +
\epsilon(i)).  
\end{equation}
Likewise, a tighter lower bound at iteration $i+1$ is
\begin{equation}
lower(i+1) = Max(E_{est}(i+1) - \epsilon(i+1) , E_{est}(i) -
\epsilon(i))
\end{equation}

An example of shrinking the intervals is shown in
Figure~\ref{shrink-example}.  The bound of iteration $i+1$ can be
improved based on previous bounds.

\subsection{Eliminating indistinguishable models}

So far we have only discussed elimination of models that are
considerably worse than the best models.  However, we can also try to
speed up the race by eliminating models which seem to be identical in
predictive power to other models.  In other words, we wish to
eliminate any model which we are confident is worse than some other
model; we also wish to stop a race between two models which we
believe with high confidence to be extremely similar.  The latter can
be achieved by defining a threshold $\gamma$ (a small positive number)
and eliminating any model which we are confident has an estimated
error within $\gamma$ of another model.  

These two rules can be combined into one formulation: given two
distinct learning boxes $LB_{i}$ and $LB_{j}$, with an estimated
error of $E_{est}^{i}$ and $E_{est}^{j}$ respectively, we eliminate
$LB_{j}$ from the race if
\begin{equation}
\Pr\{E_{est}^{i} < E_{est}^{j} - \gamma \} < \delta.
\end{equation}

\subsection{Blocking}

There are two common problems that empirically seem to slow down the
races.  One problem occurs when learning boxes have a vary large
variance in error over the test set.  In that case, we cannot
eliminate them or use them to eliminate other learning boxes since
their confidence are so large.  Another problem occurs when two or
more learning boxes have some degree of dependence, so that they
perform badly on the same points.  In that case, we need many cycles
through the race (many test points) in order to distinguish between
them.

We deal with both problems by using a statistical method known as {\em
blocking}~\cite{box:blocking}.  Instead of racing to get a tight
estimate of a model's error, we race for a tight estimate of the
difference in error between two models.  Rather than maintaining an
average error for each learning box, we maintain an average error
difference (denoted $ED_{est}^{i,j}$) for every pair of learning boxes
$(i,j)$.  If we let $e_{i}(l)$ be the error of the $i^{th}$ learning
box on the $l^{th}$ testing point, then our estimate of the error
difference after seeing $k$ test points is 
\begin{equation}
ED_{est}^{i,j} = \frac{1}{k}\sum_{l=1}^{k} (e_{i}(l) - e_{j}(l))
\end{equation}

As before, we can use either Hoeffding's Bound or a Bayesian bound in
order to determine when the error difference between two models
becomes significant, or in other words, when 
\begin{equation}
\Pr\{ED_{est}^{i,j} < 0\} < \delta.
\end{equation}

We check this condition for every pair $(i,j)$ of learning boxes and
eliminate $LB_{j}$ if it is true.

Indistinguishable models can be eliminated if $\Pr\{ED_{est}^{i,j} <
-\gamma\} < \delta$.  The simplest example of blocking having a
beneficial effect is the 
case where two models in the race are identical --- the original
racing algorithm would have to race for a long time. The racers would have
the same mean at each step of the race, but the race would only end when
they both had so many samples that the confidence intervals on its
measures of the mean error of each model were both very close to
$\gamma$ (its indifference parameter). In contrast, blocking race
algorithm would maintain, at each step, the difference between the
leave-one-out errors on each datapoint. Because the models 
are the same, this difference would always be zero and it would only
require a very small number of statistics (perhaps less than ten,
depending upon the parameters) before one of the models was
eliminated.  The example of identical models is extreme, but in the
more common case of near-identical models there can also be a large
reduction in the time to elimination.

\section{Empirical results}

\subsection{Results from Hoeffding races}
We ran Hoeffding Races on a wide variety of classification and
regression problems which are described below.  These results were
also presented in~\cite{maron:hoeffding}.  The data files are
available from the authors.

\begin{description}
\item[ROBOT]  10 input attributes, 5 outputs.  Given an initial and a final
description of a robot arm, learn the control needed in order to make
the robot perform devil-sticking~\cite{schaal:openloop}. 
\item[PROTEIN] 3 inputs, output is a classification into one of three
classes.  This is the famous protein secondary structure database,
with some preprocessing~\cite{zhang:protein}.
\item[ENERGY]  Given solar radiation sensing, predict the cooling load for a
building.  This is taken from the Building Energy Predictor Shootout.
\item[POWER] Market data for electricity generation pricing period class
for the new United Kingdom Power Market.
\item[POOL] The visually perceived mapping from pool table configurations
to shot outcome for two-ball collisions~\cite{moore:forward}.
\item[DISCONT] An artificially constructed set of points with many
discontinuities.  Local models should outperform global ones.
\end{description}

We have run Hoeffding Races on a collection of memory based learning
algorithms.  The learning boxes varied in the number of nearest
neighbors that they looked at ($k=1,3,5,7,9$), in the degree of
smoothing performed
($K_{width}=4,2,1,\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{16},\frac{1}{32},\frac{1}{64}$), 
and whether the function was locally constant or performed local 
weighted regression.  The distance metric was not varied.  All of the
experiments were run using $\delta=0.01$.  We used the techniques
mentioned earlier for estimating $B$ and for shrinking the intervals,
but the indifference parameter $\gamma$ and blocking were not used.
We compare Hoeffding Races to brute force relative to 
the number of queries made, where a query is one learning box finding
its error at one point.  The results are summarized in
Table~\ref{results}, which shows the number of points in the training
set (and therefore the number of leave-one-out queries that one
learning box can perform), the initial number of learning boxes, the
number of queries performed by brute force and Hoeffding Races, the
number of learning boxes left at the end of the race, and the speedup
factor in number of queries.  

\begin{table}
\begin{center}
\begin{tabular}{|lccc|} \hline
Problem & \# points & Initial \# & \# queries with
\\
 & & learning boxes & Brute Force \\
\hline
ROBOT & 972 & 95 & 92340 \\
PROTEIN & 4965  & 95 & 471675 \\
ENERGY & 2444 & 189 & 461916 \\
POWER & 210 & 95 & 19950 \\
POOL & 259  & 95 & 24605 \\
DISCONT & 500  & 95  & 47500 \\
\hline
\hline
Problem & \# queries with & \# learning & speedup \\
 & Hoeffding Races & boxes left & factor \\
\hline
ROBOT & 15637 & 6 & 5.91\\
PROTEIN  & 349405 & 60 & 1.35\\
ENERGY  & 121400 & 40 & 3.80\\
POWER  & 13119 & 48 & 1.52 \\
POOL  & 22095 & 75 & 1.11\\
DISCONT & 25144 & 29 & 1.89\\
\hline
\end{tabular}
\caption{\label{results} Results of Brute Force vs. Hoeffding Races.}
\end{center}
\end{table}

There are a few observations to be made from this table:
\begin{itemize}
\item Hoeffding Races never performs more queries than brute force,
and its overhead is negligible.
\item In all the cases we have tested, the learning box chosen by
brute force is also contained by the set returned from Hoeffding
Races.  Therefore, there is no loss of performance accuracy.
\item It is least effective when a large percentage of the original
learning boxes are left at the end.  For example, in the POOL problem,
where there were 75 learning boxes left at the end of the race, the
number of queries is only slightly smaller for Hoeffding Races than
for brute force.  In the ROBOT problem, where only 6 learning boxes
were left, a significant reduction in the number of queries can be
seen.
\item The obvious conclusion from this observation is that Hoeffding
Races is most effective when there exists a small subset of clear
winners within the initial set of models.  In fact, it becomes more
and more effective (in comparison to brute force) the larger the size
of the initial set of models.  
\end{itemize}

\begin{figure}
	\begin{minipage}{2.5in}
		\centerline{\epsfxsize= 2.5in \epsfysize= 3in 
		\epsffile{/home/r2/oded/research/NIPS93/hoeff-vs-brute.ps}}
        \end{minipage}
        \hspace{1cm}
	\begin{minipage}{3in}
	\caption[Scaling of Hoeffding Races vs. brute force]
		{The bottom line shows the number of
		queries taken by Hoeffding Races for the ROBOT problem
		as the size of the initial set of learning boxes is 
		increased.  The top line shows the performance by
		brute force.  At each point, the set of learning
                boxes was chosen randomly.}  
	\label{hoeff-vs-brute}
	\end{minipage}
\end{figure}

In order to test this conclusion, we created random subsets of
increasing sizes from the 95 learning boxes used for the ROBOT
experiment.  We ran Hoeffding Races on each one of the subsets,
and tabulated the results in Figure~\ref{hoeff-vs-brute}.  As can be
seen, we can search over a large set of models without
much concern about the computational expense of a large initial set.
In other words, if we have very little knowledge of the problem, we
should not preclude any possible solution --- Hoeffding Races lets us
do that without much computational expense.

We do not think that there is a general asymptotic relation between
Hoeffding Races and brute force as the number of models grow.  As
shown by Table~\ref{results}, it is problem dependent.  However, it is
clear that Hoeffding Races works badly on `boring' problems,
where any arbitrary model does as well as anything else, and works
very well on `interesting' problems, where only a few models
really fit the domain.  Running the classroom analogy completely into
the ground, the boring problems can be thought of as picking the best
gym student (everybody gets A's in gym), and the interesting problems
can be thought of as picking the best history student (where the grade
distribution is such that there are only a few excellent students).

\subsubsection{Real life application: segmenting Magnetic Resonance
Images}

In addition to the small datasets described above, we used the
combination of Hoeffding Races and memory based learning in a larger
application.  The input is a 3-D image of the brain, generated in
slices from a Magnetic Resonance machine.  Each point in the image
becomes a point in the training set.  A point is described by its $(x,y,z)$
coordinates in the image and by two descriptive attributes: the proton
density and the viscosity of the tissue.  This quintuple is mapped
into a classification (segmentation) of either gray matter, white
matter, fluid, or lesion.  The entire data set is quite large: 10
patients, two to four images across time for each patient, and about
0.5 million points per image.  

The segmentation problem is important in several medical imaging
applications.  For example, Multiple Sclerosis (MS) causes brain lesions,
whose volume needs to be tracked over time in order to determine if
the treatment is working, or the rate of deterioration.  If this were
to be done by hand, a specialist would need to look through over 50
slices of the brain, determine the location and size of the lesions in
each slice, and add them up to get a piece of information for one
person during one time point.  This becomes horribly time consuming
when there are many patients getting scanned on a weekly basis.

We would like to automate the process by training on images
from a single patient, taken at different times, and then segmenting
future images.  An even more ambitious goal is to train on multiple
patients and predict on unseen patients' images.

A detailed description of the various experiments and results can be
found in~\cite{maron:thesis}.  In summary, using Hoeffding Races
allowed us to make only 69\% of the queries and saved hundreds of
hours of CPU time.  The best learning box incorrectly classified
18\% of points from new patients.

\subsection{Results from Bayesian races and blocking}

Table~\ref{tab:comp} shows some results comparing the Bayesian Race
algorithm with and without blocking with the standard brute force
algorithm that computes all the models exhaustively.  In the results,
``Evals'' denotes the number of individual {\loocv} computations
needed by the search, ``Correct?'' asks whether the model selected by
the search had the true minimum {\loocv}, and the ``Relative evals''
column gives the fraction of the cost of the search relative to the
exhaustive search.  EXH is the brute force method, RACE is Bayesian
Races, and BRACE is Bayesian Races with blocking. 

The algorithms were tested on datasets from a billiards robot (3
inputs, 1 output, 253 points) and a juggling robot that was used in
the Hoeffding Races experiments described earlier(12 inputs, 1
output, 972 points).  For these experiments, $\delta = 0.001$ and
$\gamma = 0.001$.  The $\delta$ value means we have to be $99.9\%$ ($=
100(1 - \delta)$) sure before eliminating a model from a race.  The
$\gamma$ value means we are prepared to accidently eliminate models
which are very slightly better (by a factor $\gamma = 0.001$) than the
race winner.  There were the same set of twenty models in each race.
Ten models were local weighted averaging (also known as kernel
regression) and ten models were locally weighted
regression~\cite{clvl:lcll}. Each group of ten models had different
kernel smoothing parameters from the set $\{ 2^{-9} , 2^{-8} , \ldots
2^{-1} , 2^0 \}$.

\begin{table*}
\caption{Experiments on Bayesian Races and blocking}
\label{tab:comp}
\begin{center}
\begin{tabular}{|l||lll||lll|}
\hline
 & \multicolumn{3}{|c||}{Billiards} & \multicolumn{3}{|c|}{Juggling} \\
\hline
 Method & Evals & Correct? & Relative & Evals & Correct? & Relative \\
        &       &          & Evals to &       &          & Evals to \\
        &       &          & EXH      &       &          & EXH      \\
\hline
EXH     & 5060  & Yes      & 1.000    & 19440 & Yes      & 1.000    \\
\hline
RACE    & 2464  & Yes      & 0.487    & 2558  & Yes      & 0.132    \\
\hline
BRACE   & 1049  & Yes      & 0.207    & 882   & Yes      & 0.045    \\
\hline
\end{tabular}
\end{center}
\end{table*}

In both these experiments RACE improved on the exhaustive method, and
BRACE in turn improved upon RACE. The proportional improvement was
greater for the juggling example, mainly because the juggling dataset
is larger. A larger dataset means the exhaustive method has to perform
proportionally many extra {\loocv} evaluations, whereas the racing
methods can stop before all datapoints are evaluated. In three of the
four races in Table~\ref{tab:comp} there was only one model left at
the end of the race. For the RACE algorithm on the billiards dataset,
8 of the 20 models survived to the end.

\section{Racing for relevant attributes}

A particularly promising use of cross validation is to automatically
choose relevant inputs from a wider set of possible inputs.  An
obvious benefit is in accelerating the learning rate of algorithms
which suffer in the face of irrelevant inputs.  Other benefits include
helping select relevant visual features for visually controlled robot
tasks~\cite{moore:brute-force}, and selecting sets of time windows in time
series predictions. This problem, known as ``subset selection'' is a
well-known problem in statistics, surveyed thoroughly
in~\cite{mllr:sbst} and is rapidly gaining attention in the Machine
Learning community.  In the recent Conference on Machine Learning
proceedings, three other papers addressing 
subset selection for various machine learning algorithms
are:~\cite{crn:grdy,jhn:irrl,sklk:prtt}. 

Given $D$ inputs there are $2^D$ possible
input sets, and so performing an exhaustive cross validation search
over all of them soon becomes impractical as $D$ rises,
even assuming adequate data support to justify searching so many
models.  Hill climbing is a sensible alternative since the space we
are climbing over has a reasonable ``neighbor'' concept.  In this
section we provide several hill climbing versions of the racing
algorithm; these aim to both speed up the computation and also to
reduce the danger of becoming trapped at local maxima.

Sets of inputs can be represented as binary strings.  Given four
possible inputs, 0101 would denote ``ignore inputs 1 and 3, use inputs
2 and 4.''  The standard non-racing hill climbing algorithm begins
with a start string (e.g. 0000) then makes all possible 1-feature
changes to it (1000, 0100, 0010, 0001) and exhaustively finds which
minimizes the leave-one-out cross validation ({\loocv}) error.  It
then uses this best string (say 
0100) as a new base point, generates all its 1-feature successors
(1100, 0000, 0110, 0101), and determines the best.  It continues in
this way until no single-feature change improves it.  The special case
of starting with all zeroes is termed forward selection (FOR-SEL), and
that of starting with all ones is termed backward elimination
(BACK-SEL). Forward selection is better if only a few features are
expected to be relevant and backward elimination is better if only a
few features are expected to be irrelevant. Unfortunately, such prior
knowledge may not be available at the start of the search.

The racing counterparts to these algorithms are straightforward: from
the base string generate all 1-feature changes and race them.  Proceed
until the winner of a race does not improve on its base.  In the
experiments described later two versions are tested, FOR-RACE and
BACK-RACE, which start at all zeroes and all ones respectively.

There is, however, an objection to this simple application of racing.
Imagine that inputs 4, 5, and 6 are all relevant and independently
provide a reduction in the LOOCV error.  If we start at string
0000000 and successors 0000100, 0000010, and 0000001 are all good, it
will be a shame to run through three separate hill climbing iterations
to switch them all on.  This motivates the next algorithm, a
Gauss-Seidel version of hill climbing:

\begin{itemize}
%\begin{tabular}{p{3.2in}}
\item
Begin with a predefined start string (e.g. 00000) 
\item
Race between the current string and the current string 
with the first bit flipped (00000 versus 10000) 
\item
Select the winner of that race as the new current string 
(e.g. 10000) 
\item
Now race between the current string and the current string 
with the second bit flipped (10000 versus 11000) 
\end{itemize}
\mbox{} \hspace{1.3in} $\vdots$  \mbox{} \hspace{1in}
%\end{tabular}

\noindent
...until all bits have been raced. Then return to the first bit
and proceed until an entire pass through the current string fails to produce
an improvement.

Versions of this algorithm, FOR-GS-RACE and BACK-GS-RACE, are
tested below.  On some occasions they do indeed help, but on others
their performance is poor.  A further new algorithm  --- Schemata
Search --- does Gauss-Seidel's job better, and also solves another
problem. 

\subsection{SCHEMATA SEARCH}

Schemata search is a new algorithm described in~\cite{moore:schemata}
which aims to solve the same 
problem that the Gauss-Seidel method addresses---the problem of
forward selection taking a long time if many features are relevant, or
similarly backward elimination taking a long time if many features are
irrelevant. It will also help with a second problem.  Suppose there is
a family of three features which must all be on simultaneously for any
reduction in the {\loocv} error. If any family member is ignored then the
{\loocv} error is just as bad as if all family members were ignored.  This
can happen quite easily, for example if the features are distributed
between -1 and 1 and the function being learned is their product.
Forward selection would be very likely to miss this family and to
converge on something suboptimal. Backward elimination would not have
this problem, but if many features are irrelevant then it can become
stuck itself (because in the early stages of hill climbing the removal
of one irrelevant attribute among many does not improve the
{\loocv} error).

Schemata search searches over the space of schemata strings, which
have 0's, 1's and {\mst}'s in them. A {\mst} denotes a fifty percent
chance of the attribute being ignored, and a fifty percent chance of
it being used.  The {\loocv} error of such a string is the expected
{\loocv} error of a binary string generated from the schemata string
according to these random rules, for example
\begin{eqnarray*}
\loocve(101{\mst}{\mst}) & = & \frac{1}{4} \loocve(10100) +  \\
 & &  \frac{1}{4} \loocve(10101) + \\
 & &  \frac{1}{4} \loocve(10110) + \\
 & &  \frac{1}{4} \loocve(10111) 
\end{eqnarray*}

Now a simple algorithm is to begin with all stars (e.g.
{{\mst}{\mst}{\mst}{\mst}{\mst}}) , and then to find out (by racing)
whether it is better to have the first field as a 1 or a 0 (i.e. we
would race {1{\mst}{\mst}{\mst}{\mst}} and
{0{\mst}{\mst}{\mst}{\mst}}). Having finished the first race, we could
determine the second field by another race, and so on until the entire
string is filled with 1's and 0's.

In practice, we can do better than this. Instead of beginning by
 racing the first field, we can race all fields against each other
in parallel:

\begin{center}
\begin{tabular}{lll}
1{\mst}{\mst}{\mst}{\mst} & races against & 0{\mst}{\mst}{\mst}{\mst} \\
{\mst}1{\mst}{\mst}{\mst} & races against & {\mst}0{\mst}{\mst}{\mst} \\
{\mst}{\mst}1{\mst}{\mst} & races against & {\mst}{\mst}0{\mst}{\mst} \\
{\mst}{\mst}{\mst}1{\mst} & races against & {\mst}{\mst}{\mst}0{\mst} \\
{\mst}{\mst}{\mst}{\mst}1 & races against & {\mst}{\mst}{\mst}{\mst}0 \\
\end{tabular}
\end{center}

Thus, given $D$ inputs, we have $D$ races occurring in parallel, and
we stop all races when any one race produces a winner (to confidence
level $\delta$).  On each step of the race a random binary string is
generated, and then the {\loocv} error of one randomly chosen
datapoint is computed using that binary string. This statistic is
added to the statistics of all the strings in the above sets of races
which match the binary string.  This continues until one of the pairs
of racers becomes significant, i.e. when we believe with probability
$1-\delta$ that one member of the significant pair beats its
competitor. Then the next iteration of the race begins with a new set
of racers which all have the winning field of the previous race
switched on. If, in the above race, {\mst}1{\mst}{\mst}{\mst} became
significantly better than {\mst}0{\mst}{\mst}{\mst} the next iteration
would have

\begin{center}
\begin{tabular}{lll}
11{\mst}{\mst}{\mst} & races against & 01{\mst}{\mst}{\mst} \\
{\mst}11{\mst}{\mst} & races against & {\mst}10{\mst}{\mst} \\
{\mst}1{\mst}1{\mst} & races against & {\mst}1{\mst}0{\mst} \\
{\mst}1{\mst}{\mst}1 & races against & {\mst}1{\mst}{\mst}0 \\
\end{tabular}
\end{center}

\noindent
This may be preferable to our other hill climbing racers for
three reasons:
\begin{itemize}
\item
If any feature is outstandingly good, it will be detected quickly
without having to wait for an entire iteration of hill climbing to
take place.

\item
If several features are independently good then one of them will be
quickly selected, without having to wait to determine which precisely
is the best, which is a weakness of FOR-RACE and BACK-RACE.

\item
Small, mutually dependent, families of features that would be missed
by the other hill climbers may be found. If features 1, 2 and 3 must
all be on to gain any benefit, then schemata string
1{\mst}{\mst}{\mst}{\mst}{\mst} will eventually win a race against
0{\mst}{\mst}{\mst}{\mst}{\mst} because 25\% of the strings generated
from the former have features 1, 2, and 3 all on, whereas 0\% of the
latter do.  We have performed experiments, not shown here, to test
this phenomena in noisy binary optimization problems with mutually
dependent families of up to size five, and schemata search is
the only algorithm that finds the correct family.
\end{itemize}

\subsection{Experiments}

We have run all these algorithms on fifty-six randomly generated
synthetic datasets. The task was to find the set of features which
minimized the leave-one-out cross-validation error of a
1-nearest-neighbor function approximator. The datasets all had between
4 and 12 inputs and one real-valued output which was a noisy
multivariate function of a random subset of the inputs. All inputs
were randomly generated uniformly in the range {\mbox{$-1 \leq x_i
\leq 1$}}. The multivariate function was from the syntax in
Table~\ref{tab:syntax}.

\begin{table*}
\caption{Syntax Of Multivariate Functions In Experiments}
\label{tab:syntax}
\begin{center}
\begin{tabular}{|p{0.5in}p{1in}p{2.9in}|}
\hline
\expr {\tt ::=} & $X_i$ & the $i$th input \\
                & $\expr  \times \expr$ & the product of the 
                                          subexpressions \\
                & \mbox{mean}($\expr, \expr$) & the mean of the 
                                          subexpressions \\
                & \mbox{max}($\expr, \expr$) & the maximum of the 
                                          subexpressions \\
                & $\corrupt(\expr)$ & gaussian random noise of
                  $\pm 0.1$ is added to the value of the subexpression \\
                & $g(\expr)$ & where $g$ is a 
                  non-differentiable function $g(x) = -x^2$ if $x > 0$ and
                  $g(x) = -x^2 - 2x$ if $x \leq 0$.\\ \hline
\end{tabular}
\end{center}
\end{table*}

\noindent
The number of terms in the dataset was also randomly decided, and varied
between 5 and 30. Thus some datasets were trivial, such as $\mbox{output}
= \frac{1}{2}(x_2 + x_7)$, and others complex, such as

{\tt
\begin{quote}
output = max( corrupt( product( mean( g( x4 ) , g( corrupt( x2 ) ) ),
product( x5 , corrupt( x5 ) ) ) ) , g( corrupt( g( g( g( g( corrupt(
max( x5 , corrupt( x3 ) ) ) ) ) ) ) ) ) )
\end{quote}}

\noindent
It is interesting to note that all the searchers managed to identify
the precise set of relevant inputs for this complex dataset, which had
950 datapoints\footnote{The slowest method was FOR-SEL, needing 19000
evaluations, and the fastest was SCHEMATA$+$, described shortly, which
needed 2215 evaluations}. In all the experiments, $\delta = \gamma =
0.001$.

Figure~\ref{forward} shows the performance of the forward searchers
and schemata on the 56 random datasets. There are two measures of performance.
\begin{itemize}
\item
{\bf Accuracy.} How often do the searchers end at suboptimal solutions?
This is shown by the columns
\begin{itemize}
\item
$P_{IP} = $ the percentage of datasets for which the searcher produced an
``imperfect'' result. A result is imperfect if any other search
produced a feature-set with a lower {\loocv} error.

\item
$P_{FW} = $ the percentage of datasets for which the result was fairly
wrong, i.e. had a {\loocv} error more than 0.001 greater than the
minimum found by any other search. To give this number some meaning,
the minimum {\loocv} errors found were typically in the range $0.01-0.2$
depending on the dataset, with a similar magnitude of variation.

\item
$P_{VW} = $ the percentage of datasets for which the result was very
wrong, i.e. had a {\loocv} error more than 0.01 greater than the
minimum found by any other search.
\end{itemize}

\item
{\bf Search time.} This is given by the number of individual
evaluations of {\loocv} errors. The mean figure is shown, but this is
dominated by the few hard datasets which required tens of thousands of
evaluations for all methods. Many other datasets required only
thousands, or in some cases, hundreds of evaluations. For this reason,
also shown (by scatterplots) are the distributions of the ratio of
number of samples needed compared with the number of samples needed by
the conventional forward selection method. As can be seen, this
distribution is highly skewed, especially for the schemata searches.
$50\%$ of the schemata searches took less than a quarter of the time of
the conventional search. 12 of the 56 schemata searches took over twice
as long.
\end{itemize}

\noindent
Figure~\ref{backward} is a similar table comparing the various
backward methods and the same schemata searches (which have no forward
or backward biases).

The forward and backward racing methods were usually faster than the
conventional methods with little loss of accuracy. The Gauss-Seidel
races were similar in performance. The schemata search was also
roughly equal in accuracy, except that in this set of experiments it
achieved the distinction of no ``very wrong'' errors.

Of the twelve schemata searches which were twice as long as the
conventional forward method, seven were due to the conventional method
quickly becoming stuck with an inferior solution---after considerably
more computation schemata search found a better result. Of the other
five, four eventually found equally good solutions and one found a
slightly inferior solution.  Interestingly the schemata searches
frequently found all the relevant features very fast, often in a
tenth of the total time of their search. This produced strings with
only 1's and {\mst}'s in them.  But they would then spend a very long
time convincing themselves that they were justified in putting 0's
elsewhere.

As an initial and ugly attempt to address this, we tried an additional
algorithm, SCHEMATA$+$, which would give up and replace {\mst}'s with
0's very eagerly. If 2000 iterations of one of its races produced no
significant winners, it forced one of the stars to zero (using the
race statistics to choose the input least likely to be relevant).
SCHEMATA$+$ was the fastest algorithm at converging but was less
reliable than SCHEMATA.

\newcommand{\heightdiff}{3mm}
\newcommand{\scatwid}{70mm}
\newcommand{\scatdiff}{5mm}
\newcommand{\scatheight}{43mm}

\begin{figure*}[tb]
\begin{minipage}{6.2in}
{\scriptsize
\noindent
\mbox{\begin{tabular}{|l|l|l|l|l|l|l} \hline
Method & Mean \# & $P_{IP}$ & $P_{FW}$  & $P_{VW}$ & Mean   & Median  \\
       & Evals   &       &           &        & relative  & relative \\
       &         &       &           &        & evals     & evals    \\[\scatdiff]
\hline
FOR-SEL & 17378  & 17.9   & 16.1         & 7.1      & 1           & 1   \\[\heightdiff]
\hline
FOR-RACE & 6658 & 19.6     & 17.9        & 5.4      & 0.51        & 0.43 \\[\heightdiff]
\hline
FOR-GS-RACE & 7960 & 17.9  &  14.3        & 5.4      & 0.67        & 0.53 \\[\heightdiff]
\hline
SCHEMATA & 7779 & 16.1      & 8.9         & 0      & 1.7         & 0.22 \\[\heightdiff]
\hline
SCHEMATA$+$ & 4159 & 19.6     & 14.3         & 5.4      & 0.9         & 0.13 \\[\heightdiff]
\hline
\end{tabular}
\begin{minipage}{\scatwid}
\begin{center}
Distribution of relative evals (relative to
FOR-SEL)
\end{center}
\vspace{0.25in}
\mbox{\psfig{file=forward.ps,width=75mm,height=\scatheight}}
\end{minipage}}}
\caption{Comparing the conventional forward selection algorithm against
its racing counterparts, and against schemata search (which has no
forwards-backwards bias).}
\label{forward}
\end{minipage}
\end{figure*}

\begin{figure*}[tb]
\begin{minipage}{6.2in}
{\scriptsize
\noindent
\mbox{\begin{tabular}{|l|l|l|l|l|l|l} \hline
Method & Mean \# & $P_{IP}$ & $P_{FW}$  & $P_{VW}$ & Mean   & Median  \\
       & Evals   &       &           &        & relative  & relative \\
       &         &       &           &        & evals     & evals    \\[\scatdiff]
\hline
BACK-EL & 26358  & 16.1    & 14.3         & 7.1      & 1           & 1   \\[\heightdiff]
\hline
BACK-RACE & 13943 & 16.1     & 12.5        & 7.1      & 0.62        & 0.57 \\[\heightdiff]
\hline
BACK-GS-RACE & 5611 & 17.9  &  16.1        & 5.4    & 0.46        & 0.23 \\[\heightdiff]
\hline
SCHEMATA & 7779 & 16.1      & 8.9         & 0      & 2.1         & 0.18 \\[\heightdiff]
\hline
SCHEMATA$+$ & 4159 & 19.6     & 14.3         & 5.4      & 1.0         & 0.11 \\[\heightdiff]
\hline
\end{tabular}
\begin{minipage}{\scatwid}
\begin{center}
Distribution of relative evals (relative to
BACK-EL)
\end{center}
\vspace{0.25in}
\psfig{file=backward.ps,width=75mm,height=\scatheight}
\end{minipage}}}
\caption{Comparing the conventional backward elimination algorithm against
its racing counterparts, and against schemata search (which has no
forwards-backwards bias).}
\label{backward}
\end{minipage}
\end{figure*}

\section{Conclusion}

In this paper, we presented the racing algorithm and some extensions
to it, specifically in the framework of model selection.  However,
racing can be thought of as just another searching technique such as
A* or hill climbing.  It can therefore be used in the many of the
applications of search in Machine Learning and Artificial
Intelligence.  It seems to be especially useful for search in spaces
which are riddled with local minima, or spaces which are discrete.
The speedup over exhaustive search, and the algorithm's ability to
quantify the confidence in its result make it a viable alternative to
existing heuristic search techniques.  

\subsection{Related Work}

We were motivated to find efficient techniques for model selection by
working on Moore's GMBL system~\cite{moore:brute-force}.  Haussler's
work on generalizations of the PAC model~\cite{haussler:genpac}
provided a treasure of ideas which, combined with Kaelbling's
confidence bounds~\cite{kaelbling:thesis}, generated the Hoeffding
Races algorithm.  The notion of racing shows up in related forms in
multi-armed bandit problems.  To give one example, Rivest and
Yin~\cite{rivest:bandit} give a heuristic for picking which arm to
pull next according to the probability distributions of the payment of
each arm. 

An extremely thorough survey and investigation of how the $k$-armed
bandit problem and its solution can be used to minimize wasted
computation can be found in~\cite{grtc:unkn}. In earlier work
{\cite{grtc:lrnn}} uses a related method for choosing appropriate
search rules in very large scheduling domains.

Similar questions can be found in the pre-computer science statistics
literature. This work is chiefly concerned with detecting an effect in
a new drug or industrial process with as few experiments as possible.
\cite{box:blocking} is an excellent introduction to this field.

Greiner has independently developed a PALO (Probably
Approximately Locally Optimal) algorithm~\cite{greiner:palo} which
also uses Hoeffding's bound in order to decide when one point is
better than another.  The main differences between our work is that he
uses his method for gradient descent , and that he is not trying to
select among models, but 
among Horn clauses and default rules.  It is possible to use a descent
method in a discretized space by picking among a finite number of
discrete gradients.  At each iteration, the PALO algorithm compares
the estimated error of stopping against the estimated error of each
one of the neighboring possibilities.  The algorithm then goes in the
direction of the least error.  The comparison is made faster by using
a racing technique.

\subsection{Future Work}

There are many ways to extend this research.  We list a few of them:

The only criterion used in this paper to compare and evaluate 
learners has been their accuracy.  It is possible for other factors to
influence the selection of a learner, but then we can no longer treat
it as a learning {\em box}.  We need to look inside each learner and
consider issues such as response speed, simplicity, or other a priori
biases.  These issues can be formulated in a bayesian manner as a
priori probabilities and incorporated into a racing scheme by making
it harder for a favored learner to lose the race.

This algorithm should be easy to parallelize.  Simply assign one
processor per model.  If there are less models than processors, then
it is probably not even worth racing them.  However, there are usually
going to be more possible models than processors, in which case
whenever a model gets thrown out of the race, its processor gets a new
model.

Hoeffding's bound was chosen since it is a tight,
distribution-free statistical bound.  However, it might not be the
best bound to use for classification problems.  Other tests, such as
the f-test, can be used in its place.  For a given value of $\delta$
(defining the confidence level 
at which we are prepared to cut off a competitor from the race) the
Bayesian approach cuts off far earlier than the Hoeffding approach.
The Bayesian approach achieves its superiority by making stronger
assumptions about the distribution of the errors, and so might be
expected to be less robust than the almost assumptionless Hoeffding
approach. In the experiments we have performed to date the Bayesian
method does not seem to converge to the wrong model more easily
than the Hoeffding approach, but this is an empirical observation
which may not be true for all datasets.

Another issue concerns our choice to assume a normal distribution for
the errors. In future work it might be more sensible to use a
different distribution, such as an exponential or chi-squared. The
normal distribution does not take into account the possibility of
occasional highly aberrant datapoints (outliers) in the dataset which
might have errors very many times greater than the root-mean-square
error.

An exciting offshoot of this research is a search for an `ideal'
collection of models.  There is not a single model which is a solution
to every problem in the world, but it is possible that a relatively
small group of models will cover a large portion of problems.  This
set of models needs to stretch across the space of possible problems
without much overlap.  This can be thought of as a basis set of
vectors which are orthogonal and span the space.  Once we have a basis
set of models, then racing is the perfect tool for finding the best
model out of this idealized collection since for any given problem,
only a few of the models will perform well on it.  That is the ideal
condition for racing.

Finally, there is the danger of cross validation and data mining which
we ignored for the most part.  The problem of data mining is that if
one looks at data long enough, one will begin to see patterns even if
it is completely random (this is known as data mining).  If racing is
used, it would be statistically wise to use yet another test set at
the end of the race to make sure that the chosen model really has its
purported error.  In addition, users of Hoeffding or Bayesian Races
should keep in mind Bonferroni's advice that the more models you throw
at the data, the better you should expect to perform.  If that is not
the case, you are probably mining.

{\footnotesize
\bibliography{paper}
\bibliographystyle{named}}

\end{document}




