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

%%% Change commenting to get your filepath, Oded
\newcommand{\relatedfilesdir}{.}
%% \newcommand{\relatedfilesdir}{/home/r2/oded/research/NIPS93/include.tex}
%% 
%% \input{\relatedfilesdir/include.tex}

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

\begin{document}

\begin{center}
{\Large \bf The Racing Algorithm: Model Selection for Lazy Learners}

\ \\

{\small
\mbox{\begin{minipage}{3in}
\begin{center}
{\bf Oded Maron}\\
MIT AI Lab\\
NE45-755, 545 Technology Square\\
Cambridge, MA 02139\\
{\tt oded@ai.mit.edu}
\end{center}
\end{minipage}
\begin{minipage}{3in}
\begin{center}
 {\bf Andrew W. Moore} \\
 Carnegie Mellon University \\
 5000 Forbes Ave \\
 Pittsburgh, PA 15213 \\
 {\tt awm@cs.cmu.edu}
\end{center}
\end{minipage}}}

%% 
%% \ \\
%% 
%% {\small {\bf Abstract}}
%% 
%% \ \\
%% 

\begin{abstract}
Given a set of models and some training data, we would like to find
the model that 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 that is
arbitrarily worse than the best one or cannot be used
because there is no distance metric on the space of discrete models.
In this paper we develop a technique called ``racing'' that tests the
set of models in parallel, quickly discards those models that are
clearly inferior and concentrates the computational effort on
differentiating among the better models.  Racing is especially
suitable for selecting among lazy learners since training requires
negligible expense, and incremental testing using leave-one-out cross
validation is efficient.  We use racing to select among various lazy
learning algorithms and to find relevant features in applications
ranging from robot juggling to lesion detection in MRI scans.
\end{abstract}

%% \begin{minipage}{0.9\textwidth}
%% {\small
%% 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{minipage}
\end{center}
 

\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 repeatedly 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 lazy
learner, or a random guesser?  Which of the 50 features are relevant
for this problem?  The answer to these questions changes depending on
the training set.  We would like to find an answer efficiently, given
a training set and a collection of models.

%% We would like to
%% efficiently answer these questions for one problem at a time, and not
%% in general for all problems.

There are a number of popular ways to determine a student's grade, or
a model's generalization error~\cite{weiss:systems}.  In this paper we
will 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.
Other methods are discussed below.

%% awm2 delete
%% 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~\cite{maron:hoeffding} 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 distinguish the 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
again.  The more test points that are seen, the tighter the
estimated error is to the true error; therefore, 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.

Unlike other machine learning methods, lazy learning algorithms do not
force the training points into a decision tree, a neural net, symbolic
rules, or any abstract representation.  The points act as their own
best representation.  A direct implication of this fact is that very
little work needs to be performed during training --- we simply store
the points in memory.  Most of the computational expense comes when we
use the learner for prediction.  Racing uses laziness to its
advantage, and also attempts to limit the number of predictions.

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

This paper combines the authors' previous work on racing,
\cite{maron:hoeffding},\cite{moore:schemata},\cite{maron:thesis}, and
adds additional experiments, discussion, and connections to lazy
learning techniques.

\subsection{Lazy learning algorithms}
\label{sec-lazy-learning}

The collection of models to which we apply the racing algorithms in
this paper are {\em lazy learning} methods.  Lazy learning is an
encompassing name for a variety of statistical and machine learning
methods such as nearest-neighbor~\cite{dasarathy:collection} and local
weighted regression~\cite{cleveland:lwr}.  The underlying principle of
lazy learning is to simply remember the training examples.  Almost all
of the computational work is performed not during training, but only
when a query is made.  Variants of the nearest-neighbor method are
then used for prediction.

%% 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.  

%% awm2 add changed bits from above
With a lazy learner, the data points, which are of the form \mbox{(
$<$input-vector$>$ , $<$output-vector$>$ )} are kept in memory.  The
task is for the learner to predict output values when queried with
inputs that might not be in memory.  When the learner 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 output values at those points is
averaged (or regressed~\cite{moore:brute-force}) and returned as the
predicted value.  We assume in this paper that both the attributes
(inputs) and predictions (outputs) are numeric, though many variations
exist~\cite{aha:thesis}.

Within this general framework, there are still many choices for
specifying a model: 
\begin{itemize}
\item How do we measure {\em similarity}?
\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}

\noindent
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 (or distance) is
usually measured by using the Manhattan or Euclidean
metric\footnote{The Manhattan metric assumes that you can travel
between two points only along a grid, so the distance between
$(x_1,y_1)$ and $(x_2,y_2)$ is $\|x_1-x_2\| + \|y_1-y_2\|$.  Using a
Euclidean metric, the distance is $\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$.},
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 lazy 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 \mbox{$\langle$ height, weight, hat-size$\rangle$.}  Given a
query $q$ of the form $\langle$6ft,155LB$\rangle$, we look for the point $p$ that
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 $\langle$2ft,155LB$\rangle$ is closer to $q$ than someone who is
$\langle$6ft,165LB$\rangle$ 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 remove any assumptions about the
best representation for the data.  The best weighting, like the best
value of $k$, should be searched for.  Other, non-symmetric distance
measures are possible~\cite{maron:thesis}, but are not discussed in
this paper.


\subsubsection{Kernel regression}

It is intuitive that some neighbors are more important than others.
Specifically, neighbors that are closer to the queried point should
count more toward its classification than neighbors that are farther
away.  {\em 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$.

%% awm2 removed the c
\begin{equation}
w_i = \frac{1}{1 + 20 \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 empirically testing various values of it.  
%% awm2 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 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
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 accuracy of
1-nearest-neighbor on new points (the generalization error) can be
much lower.  What is needed is a way to test not only rote
memorization, but also the ability to generalize.

There are a number of 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.

%% awm2 minor changes below
The second method of estimating generalization is called {\em
leave-one-out cross validation}.  Here, 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 that 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, for lazy learners, leave-one-out cross validation is efficient.

Another popular method is multifold cross validation, where instead
leaving just one point out, a different set of points is held out
during each iteration and is then used as the test set.  The average
of the errors gives an estimation of the generalization 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{Summary}

The paper is organized as follows: we discuss previous approaches to
model selection such as brute force, gradient descent and genetic
algorithms.  We show that they are either slow or inappropriate.  We
then describe the racing algorithm, and talk about two bounds that can
be used to differentiate the various models' errors.  We show that
using Hoeffing's bound is general and correct, but it is not a very
tight bound.  We give a Bayesian bound which turns out to be faster in
practice.  We also discuss various extensions and heuristics that can
be made to help the race.

We then describe a set of experiments that show some empirical results
of running the various types of races on real datasets.  We then
discuss a different usage of racing; namely, to find the relevant
attributes for prediction.  Finally, we conclude with some related
work and future directions.


%% \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}.  



%% awm2 delete
%% 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.  We discuss
these approaches in the following subsections.
Racing~\cite{maron:hoeffding} 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 that
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 that has less error.  This
approach to optimizing the lazy learner has been taken
by~\cite{atkeson:approximating,lowe:95}

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 that 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= 2in \epsfysize= 2.8in \epsffile{\relatedfilesdir/local-minima.ps}}
\end{minipage}
\ \ \
\begin{minipage}{3.5in}
{\footnotesize
\caption[Example of local minima in model selection]{The
cross-validation error of 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.  An example of it in the realm of model selection is given in
Figure~1.
%% 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 value for $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?

%% awm2 delete
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, although we can impose a metric, it 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~\cite{press:recipes} and conjugate
gradient are as susceptible to this problem as the plain version of
gradient descent.

\subsection{Genetic algorithms and simulated annealing}

The same problems described with descent methods also apply to these
techniques, 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 that is
proportional to the average number of generations it takes to get
between two representations.  Again, this distance metric is
arbitrary and is based solely on the representation of the
models, which is as meaningless as having it based on their
position in a room.  Assuming that there is structural similarity
between bit-string descriptions of a 1-nearest-neighbor and a neural net
is dubious.

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 that 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 that 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}.  This bound does not make any assumptions
other than the independence of the samples.

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}

\noindent
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
section~\ref{sec-bounding-errors}.  We can also determine the number
of samples $n$ necessary to obtain a certain accuracy $\epsilon$ and
confidence $\delta$:

\begin{equation}
n > \frac{B^{2}  \log(2/\delta)}{2 \epsilon ^2}
\end{equation}

\noindent
The number of samples increases quickly as we attempt to increase the
accuracy.  This is a problem with using Hoeffding's bound, and we try
to resolve it by using Bayesian bounds which are less general but
tighter.

\subsubsection{Hoeffding races}

The racing 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 do not consider how complex or
time-consuming each prediction is, but only 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
test points it has processed 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$.
%% awm2 changed to
Assume the dataset has $N$ datapoints.

At each iteration of the algorithm, we randomly select a point from
the test set.  Then for each learning box:
\begin{itemize}
%% awm2 added leave-one-out
\item compute the leave-one-out 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{\relatedfilesdir/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}

The algorithm iterates, repeatedly picking test points until one of
three conditions occurs:
\begin{enumerate}
\item All but one of the learning boxes have been eliminated.  
%% awm2 delete The algorithm simply returns it as the best one.  
\item A sufficient number (e.g., N) of test points have been picked.
\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 
{\footnotesize \begin{equation}
\Pr\{ \; all \; learning \; boxes \; are \; within \; \epsilon(n) \;
on \; all \; iterations \; up \; to \;n\}
\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 for any events $A$ and $B$,
$Pr\{A \vee B\} \leq Pr\{A\} + Pr\{B\}$.

Assume that there are $n$ iterations, and $m$ learning boxes ($LB_{1},
\cdots, LB_{m}$).  We start with the fact that: {\footnotesize
\begin{equation} Pr\{ \; a \; particular \; LB \; is \; within \;
\epsilon(i) \; on \; a
\; particular \; iteration \; i\} \geq 1-\delta
\end{equation}}
Which is equivalent to:
{\footnotesize \begin{equation}
Pr\{ \; a \; particular \; LB \; is \; wrong \; on \; a \; particular \;
iteration\} < \delta
\end{equation}}
Using the disjunctive inequality, 
{\footnotesize \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}}
Rewrite this as:
{\footnotesize \begin{equation}
Pr\{ \; a \; particular \; LB \; is \; wrong \; on \; any \; iteration
\; up \; to \; n\}
\leq \delta \cdot n
\end{equation}}
And likewise for all learning boxes:
{\footnotesize \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:
{\footnotesize \begin{equation}
Pr\{ \; some \; LB \; is \; wrong \; in \; some \; iteration\} \leq \delta
\cdot n \cdot m
\end{equation}}
which is equivalent to:
{\footnotesize \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 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~\cite{haussler:genpac}.

\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
model.  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 model 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 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, since
$\ejtrue$ refers to the leave-one-out errors, not the out of sample
errors.  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)
\mbox{\ \ \ \ \ }
\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.  These statistics can be updated
incrementally efficiently: $\hat{\mu}_{(n+1)j}$ and
$\hat{\sigma}^2_{(n+1)j}$ can be defined as a closed form 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.
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}
\mbox{\ \ \ \ \ }
p(\vjtrue) = \mbox{Constant} / \sigma
\end{equation}
where $p(.)$ denotes a probability density function.\footnote{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.
%% awm2 delete
%% 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~3 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) ) < \delta
\end{equation}
$\delta$ again denotes the confidence that is required.
%% awm2 delete
%% 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~3
it would be very probable that $\evtrue{2}$ is lower than $\evtrue{4}$,
but only marginally 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}
{\footnotesize
\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 unknown
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 , 
\mbox{\ \ \ }
u_2 = s^2_2 / n_2 ,
\mbox{\ \ \ }
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 distribution, we get
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 then describe a method for tightening the confidence
intervals for each model and for eliminating redundant models in the
set (models that are statistically equivalent).  We also talk about a
statistical method known as {\em blocking}~\cite{box:blocking} that
helps with the problems of large variances and dependent models.

\subsection{Bounding errors}
\label{sec-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}

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

There is a simple heuristic to 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.

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 top model.  We can also try to
speed up the race by eliminating models that seem to be identical in
predictive power to other models.  In other words, we wish to
eliminate any model that we are confident is worse than some other
model; we also wish to stop a race between two models that 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 that 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 
%% awm2 minor change
test points 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, the 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 on the parameters)
before one of the models was eliminated.  This 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 of Hoeffding and Bayesian racing}

We ran races on a wide variety of classification and regression
problems that are described below.  Some of these results were also
presented in~\cite{maron:hoeffding}.  The data files are available
from the UCI repository~\cite{murphy:repository}.  The problems were
chosen arbitrarily, but turned out to have widely different optimal
models: from 3-nearest-neighbor to local weighted regression with a
large smoothing kernel.

%% \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}
\begin{center}
{\footnotesize
\begin{tabular}{p{0.12\textwidth}p{0.80\textwidth}}
{\bf ROBOT} & Given initial and final description of a robot arm,
learn the control needed for juggling~\cite{schaal:openloop}. 10 input
attributes, 5 outputs.
\\
{\bf PROTEIN} & 3 inputs, and output is a classification into one of
three classes.  The famous protein secondary structure database, with
some preprocessing~\cite{zhang:protein}.
\\
{\bf ENERGY} & Given solar radiation sensing, predict cooling load for
a building.  This is taken from the Building Energy Predictor
Shootout~\cite{energy:shootout}.
\\
{\bf POWER} & Market data for electricity generation pricing period class
for the new United Kingdom Power Market.
\\
{\bf POOL} & The visually perceived mapping from pool table configurations
to shot outcome for two-ball collisions~\cite{moore:forward}.
\\
{\bf DISCONT} & An artificial dataset with many discontinuities.
Local models should outperform global ones.
\end{tabular}}
\end{center}
\vspace{0.5in}
We ran the races on a collection of lazy 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 (see Section~\ref{sec-lazy-learning}.  These
combinations give us either 95 or 189 different models, depending on
the permutations used.  The distance metric was not varied, and all
attributes were held to be equally important.  All of the experiments
were run using $\delta=0.01$.  We used the techniques mentioned
earlier for estimating $B$ and for shrinking the intervals.

In Table~\ref{results}, we compare the brute force approach to
Hoeffding races, Bayesian races, and Bayesian races with blocking.
Each of the columns is the results for one of the datasets described
above.  The first two rows of the table describe how many points are
in each dataset and how many learning boxes (LBs) are in the initial
set of models.  BRUTE is the number of leave-one-out cross validation
({\loocv}) queries made by the brute force algorithm.  Likewise,
HOEFFDING, BAYES and BLOCK-BAYES show the average number of {\loocv}
queries made by each of those algorithms over 5 runs.  We also show
the speedup in terms of the number of queries for each of the
algorithms with respect to BRUTE.  Hoeffding races usually returns a
set of LBs that cannot be distinguished, and for these datasets it
always contained the model that BRUTE chose.  However, the Bayes-based
algorithms returned just one model.  We measured its quality by
``regret'', which is the difference between the BRUTE's top model and
the model returned, normalized by the standard deviance of the output.

\begin{table}
\caption{\label{results} Results of various races.}
\begin{center}
\begin{tabular}{|lcccccc|} \hline
 & ROBOT & PROTEIN & ENERGY & POWER & POOL & DISCONT\\
\hline
points & 972 & 4,965 & 2,444 & 210 & 259 & 500 \\
initial learning boxes & 95 & 95 & 189 & 95 & 95 & 95\\
\hline
BRUTE & 92,340 & 471,675 & 461,916 & 19,950 & 24,605 & 47,500 \\
\hline
HOEFFDING & 15,637 & 349,405 & 121,400 & 13,119 & 22,095 & 25,144 \\
LBs left & 6 & 60 & 40 & 48 & 75 & 29 \\
speedup & {\bf 5.91} & {\bf 1.35} & {\bf 3.80} & {\bf 1.52} & {\bf 1.11} & {\bf 1.89} \\
\hline
BAYES & 15,482.8 & 204,466 & 47,689.2 & 9,318.2 & 11,138.4 & 1,158.4 \\
regret & 0.004 & 0.016 & 0 & 0.0001 & 0 & 0 \\
speedup & {\bf 5.96} & {\bf 2.31} & {\bf 9.69} & {\bf 2.14} & {\bf 2.21} & {\bf 41.00} \\
\hline
BLOCK-BAYES & 1,839.4 & 4,430.8 & 19,444.6 & 5,421.8 & 1,409.4 & 906.2 \\
regret & 0.005 & 0.05 & 0 & 0.002 & 0 & 0 \\
speedup & {\bf 50.20} & {\bf 106.45} & {\bf 23.76} & {\bf 3.68} & {\bf 17.46} & {\bf 52.41} \\
\hline
\end{tabular}
\end{center}
\end{table}


There are a few observations to be made from this table:
\begin{itemize}
\item Racing never performs more queries than brute force,
and its overhead is negligible, except in the case of the blocking
race, which has quadratic cost in the number of racers.  In addition,
the accuracy of the model (or models) selected is very close to the
accuracy of the best model in the initial set.

\item Bayesian races always improved on Hoeffding races, and
Bayes with blocking in turn improved upon Bayesian. The improvement
over brute force tends to be greater for larger datasets since 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.

\item The Bayesian methods are faster than Hoeffding, but they do not
carry a formal correctness proof.  Specifically, they will sometimes
throw out good models early in the race, especially if the errors
generated by those good models do not fit the priors (i.e., the errors
are not Gaussian).

\item Hoeffding races (and racing in general) 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 racing is
most effective when there exists a small subset of clear winners
within the initial set of models.  In fact, the larger the size of the
initial set of models, the more effective racing is in comparison to
brute force.
\end{itemize}

\begin{figure}
	\begin{minipage}{2.5in}
		\centerline{\epsfxsize= 2.5in \epsfysize= 3in 
		\epsffile{\relatedfilesdir/hoeff-vs-brute.ps}}
        \end{minipage}
        \hspace{1cm}
	\begin{minipage}{3in}
{\footnotesize
	\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}

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.  Racing lets us
do that without much computational expense.

We do not think that there is a general asymptotic relation between
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 the Racing algorithms work 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.
Using the classroom analogy again, 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).

\subsection{Segmenting Magnetic Resonance Images}

In addition to the small datasets described above, we used the
combination of Hoeffding races and lazy 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 causes brain lesions,
whose volume needs to be tracked over time 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 sum them 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, and more importantly, produced
results that looked reasonable to medical experts.

%% \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*}
%% 
%% Oded you can probably adapt the following paragraph (search back for SPLOK)
%% 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''
or ``feature selection'' is a well-known problem in statistics,
surveyed thoroughly in~\cite{mllr:sbst} and is rapidly gaining
attention in the Machine Learning
community~\cite{crn:grdy,jhn:irrl,sklk:prtt}.
%% awm2 delete
%% In the recent Conference on Machine Learning
%% proceedings, three other papers addressing 
%% subset selection for various machine learning algorithms
%% are:

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, {\em
forward sequential selection}, 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 sequential selection
(FOR-SEL), and that of starting with all ones is termed backward
elimination (BACK-SEL). Forward sequential 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, that start at all zeroes and all ones respectively.

However, there is 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, {\em 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 sequential 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 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 sequential
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
as well (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
{\footnotesize
\begin{center}
\[
\loocve(101{\mst}{\mst}) = \frac{1}{4} \left( \loocve(10100) +
\loocve(10101) +
\loocve(10110) +
\loocve(10111) \right)
\]
\end{center}
}
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:

{\footnotesize
\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

{\footnotesize
\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. 
%% awm2 delete
%% 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 that
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 generated from the syntax in
Table~\ref{tab:syntax}.

\begin{table*}
{\footnotesize
\caption{Syntax Of the 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 \footnotesize
\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 that 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 sequential 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, an issue that we discuss below.
\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 that 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.  Unfortunately, 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 sequential 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 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
that are riddled with local minima, or spaces in which the collection
of models is discretized.  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 that, combined with Kaelbling's
confidence bounds~\cite{kaelbling:thesis}, generated the Hoeffding
races algorithm.  The idea of parallel decision making has been used
repeatedly in AI, but the combination of racing with lazy learners
gives us the ability to make decisions efficiently, soundly, and
incrementally.  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{gratch:bandit}. 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 earlier 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} that also uses
Hoeffding's bound 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 describe a few of them.

%% awm2 delete
%% 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 that 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 that
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 that is a solution
to every problem in the world, but it is possible that there is a
group of models which will cover a large portion of problems, and only
a small number of which are suitable for each problem.  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 that 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.

%% awm2 change
%% 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
Finally, there is the danger of overfitting by searching too many
models.  If one looks at data long enough, one will begin to see
patterns even if it is completely random (this overly optimistic
estimate of the quality of the model is known as {\em 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}




