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