\documentstyle[12pt,fullpage,named,epsf]{article} \renewcommand{\baselinestretch}{1.4} \newcommand{\myindex}[1]{\mbox{\scriptsize #1}} \newcommand{\mst}{\mbox{$\star$}} \newcommand{\sbold}[1]{\mbox{\footnotesize \bf #1}} \newcommand{\loocve}{\sbold{LOOCVE}} \newcommand{\loocv}{\sbold{LOOCV}} \newcommand{\expr}{\sbold{expr}} \newcommand{\corrupt}{\mbox{corrupt}} \newcommand{\ndatapoints}{\mbox{$N_{\mbox{\footnotesize datapoints}}$}} \newcommand{\nmodels}{\mbox{$N_{\mbox{\footnotesize models}}$}} \newcommand{\xbar}{\bar{x}} \input{/home/r2/oded/research/NIPS93/include.tex} \newcommand{\mathi}{\it i} \newcommand{\myillustrate}[4]{{\begin{figure} \centerline{\epsfxsize= #4 in \epsffile{#3}} \caption{#2} \label{#1} \end{figure}}} \title{{\bf The Racing Algorithm: Model Selection for Memory Based Learning Boxes}} \author{\parbox[t]{3in} {\begin{center} {\bf Oded Maron} \\ MIT AI Lab\\ NE43-755, 545 Tech.\ Sq.\ \\ Cambridge, MA 02139\\ {\tt oded@ai.mit.edu}\\ \end{center}} \parbox[t]{3in} {\begin{center} {\bf Andrew W.\ Moore}\\ Carnegie Mellon University \\ School of Computer Science \\ Pittsburgh, PA 15213\\ {\tt awm@cs.cmu.edu}\\ \end{center}} } \date{} \begin{document} \maketitle \begin{abstract} Given a set of models and some training data, we would like to find the model which best describes the data. Finding the model with the lowest generalization error is a computationally expensive process, especially if the number of testing points is high or if the number of models is large. Optimization techniques such as hill climbing or genetic algorithms are helpful but can end up with a model which is arbitrarily worse than the best one (local minima) or even worse, cannot be used because of the lack of a distance metric on the space of discrete models. In this paper we develop a technique called ``racing'' which tests the set of models in parallel, quickly discarding those models which are clearly inferior and concentrating the computational effort on differentiating among the better models. We use racing to select among various memory based models and to find relevant features in applications ranging from robot juggling to lesion detection in MRI scans. \end{abstract} \section{Introduction} The problem of model selection can be thought of as trying to find the best student in a classroom. The teacher has the task of not only teaching the students some subject, but also of testing them to find out which student has best learned the subject. This problem, in different scaling, turns up over and over again in the Machine Learning community: which neural net architecture gives the best generalization error? What should the value of $k$ be in a k-nearest-neighbor algorithm? Should I use a decision tree, a neural net, a memory-based learner, or just a random guesser? Which of the 50 features are relevant for this problem? Note that we would like to efficiently answer these questions for one problem at a time, and not in general for all problems. There are two popular ways to determine a student's grade, or a model's generalization error. The first is to use a test set which does not intersect the training set. The average error on the test set is a good estimate of the generalization error of the model on future points drawn from the same distribution. The second method is to use leave-one-out cross validation. The model is trained on all points but one, and is then queried for the value at that point. This is repeated for every point in the training set and the prediction errors are averaged to give an estimate of the generalization error. This paper introduces a method called ``racing'' for both efficiently and accurately selecting the best model out of a set. The efficiency of the algorithm is measured by the number of queries that it makes, where a query returns one model's error on one particular test point. The accuracy of the algorithm is measured by the likelihood of not returning the best model out of a set. Previous approaches such as brute force and descent methods are either too inefficient or arbitrarily inaccurate. The idea behind racing is to test the various models in parallel, one test point at a time. This way, a running average can be maintained for each model's error. This is an estimate of the model's true error had it been tested on all of the test points. Using statistical bounds we can also determine how close the estimated error is to the true error of each model. After only a small number of test points, we can usually tell the very best models (those with lowest error, or highest grade) from the very worst models (those with the highest error). The models which are significantly worse than the best ones are thrown out of the race and are not tested any more. The more test points that are seen, the tighter the estimated error is to the true error; therefore, more and more models can be differentiated from each other and eliminated. This algorithm concentrates the computational effort on the best models, while discarding the inaccurate models and not testing them unnecessarily. \subsection{Memory based learning} Racing can be applied to any collection of models. However, since we implemented the algorithm with one one particular class of models in mind, we introduce them now. Memory based learning (MBL) is an encompassing name for a variety of statistical and machine learning methods such as nearest-neighbor and local weighted regression. The underlying principle of memory based learning is to simply remember all of the training examples. Variants of the nearest-neighbor method are then used for prediction. Every learning method must perform some sort of memorization (otherwise it would be ignoring its training); memory based learning differs in that the training does not modify any internal parameters with each new training point --- it simply stores it in memory. Let us look at a learner which is not memory based. For example, if we assume that the function we are trying to learn is a quadratic, then we need to learn the three parameters ($a$,$b$, and $c$) in the equation $f(x) = ax^2 + bx + c$. When the program is asked to predict the value at $x=5$, it plugs in the value of $x$ into the quadratic with the trained parameter values. This is not a memory based learner since we do not keep track of all of the training points, only of the parameters. On the other hand, with a memory based learner, the training points, which are of the form $(x,f(x))$, are kept in memory. When the program is asked to predict the value at $x=5$, it looks in memory for a few points whose x-values are closest to 5. The value of the function at those points is averaged (or regressed) and returned as the predicted value. Often we do not know that the function we are trying to learn is quadratic, or a polynomial, or piecewise linear, or has a normal distribution. Therefore, nonparametric methods such as nearest-neighbor are more robust than methods that make assumptions about the parameters which characterize the space of functions. In addition, we can see that nearest-neighbor techniques also fall into a different {\em computational} category from parametric methods (or even very weakly parametric methods such as neural nets and decision trees). There is negligible computation involved in training (memorizing) and most of the effort goes into finding the neighbors of the queried point. Within this general framework, there are still many choices for specifying a model: \begin{itemize} \item How do we measure ``nearness''? \item How many neighbors should we look at? \item What method should be used for averaging the outputs of the neighbors? \item Should we try to perform local regression rather than local averaging? \item How much smoothing, or weighting, should we do over the regression or average? \end{itemize} Following are some possible answers to these questions: \subsubsection{k-nearest-neighbors} The motivation for k-nearest-neighbors is summarized by this quote: \begin{quote} There seems to be a need for discrimination procedures whose validity does not require the amount of knowledge required by the normality assumption, the homoscedastic assumption, or any assumption of parametric form. \ldots can reasonable discrimination procedures be found which will work even if no parametric form can be assumed?~\cite{fix:nonparametric} \end{quote} Fix and Hodges answered their own question by introducing nearest-neighbor classification. The principle is simple: when queried for the class of some attributes, return the class of the point with the most similiar attributes. Similarity is usually measured by using the Manhattan or Euclidean metric, depending on the type of the attributes. The method generalizes easily to k-nearest-neighbors, where a majority rule is used to find the correct class, or averaging is used for continuous outputs. A larger value for $k$ makes the rule more stable against outliers and noisy data. However, making $k$ too large destroys the advantage of locality that a nearest-neighbor algorithm inherently owns. \subsubsection{Weighted distance metric} Finding an appropriate distance metric is often the toughest hurdle in attempting to use a memory based learning system. The distance metric is responsible for the representation of the memorized data. It decides which attributes are more important than others and aligns all the attributes into the same representation. To give an example, let us say that we are trying to predict hat size from height and weight. The data points are of the form (height, weight, hat-size). Given a query $q$ of the form (6ft,155LB), we look for the point $p$ which minimizes the distance between $p$ and $q$. However, it is probably not a good idea to use the standard euclidean distance since differences in pounds are much less significant than differences in feet: someone who is (2ft,155LB) is closer to $q$ than someone who is (6ft,165LB) using the plain euclidean distance metric. Clearly, we need a weighted metric that forces differences in heights to be comparable to differences in weight. The initial representation (feet and pounds) should be changed to a more suitable one. However, that is not the end of our problems. What if hat-size is predominantly affected by height, and only marginally by weight? In that case, we need to count the height attribute much more than the weight attribute so that points with similar heights will be close together, even if they have very different weights. Both problems can be solved with a priori knowledge of the importance and scale of the various attributes, but one of the main reasons for using nearest-neighbor methods is to get away from making any assumptions about the best representation for the data. The best weighting, like the best value of $k$, must be searched for or learned. \subsubsection{Kernel regression} It is intuitive that some neighbors are more important than others. Specifically, neighbors which are closer to the queried point should count more toward its classification than neighbors which are farther away. `Kernel regression' performs weighted averaging (instead of a uniform average) over the space of neighbors. The weighting function which we use is taken from~\cite{moore:brute-force}. The weight of the $i^{th}$ point ($x_i$) with respect to the query point $q$ is $w_i$. \begin{equation} w_i = \frac{1}{1 + c \cdot (distance(x_i,q)/K_{width})^2} \label{equation:weighting} \end{equation} The parameter $K_{width}$ determines the width of the weighting (or smoothing) range. The larger it is, the more weight is given to distant points. Again, it is usually not feasible to estimate this parameter before trying out various values of it. In this paper, we use the value of $c=20$. \subsubsection{Local regression and local weighted regression} The computationally intensive part of nearest-neighbor algorithms is usually to find the $k$ neighbors. Once that is done, we can perform more complex operations than averaging in order to predict the queried value. For example, {\em local regression} involves finding a least-squares linear fit of the neighbors. {\em Local weighted regression}~\cite{cleveland:lwr} attempts to minimize the weighted error, where the weighting function is the one shown in Equation~\ref{equation:weighting}. \subsection{Example of different memory based learning boxes} \myillustrate{neighbor-example-train}{75 random training points with noise}{/home/r2/oded/research/msthesis/figures/training_points.ps}{2.5} \begin{figure} \begin{minipage}{2.4in} \centerline{\epsfxsize= 2.4in \epsfysize= 2.4in \epsffile{/home/r2/oded/research/msthesis/figures/A01.ps}} \centerline{(a) one nearest neighbor} \end{minipage} \ \ \ \begin{minipage}{2.4in} \centerline{\epsfxsize= 2.4in \epsfysize= 2.4in \epsffile{/home/r2/oded/research/msthesis/figures/A05.ps}} \centerline{(b) five nearest neighbors} \end{minipage} \\ \begin{minipage}{2.4in} \centerline{\epsfxsize= 2.4in \epsfysize= 2.4in \epsffile{/home/r2/oded/research/msthesis/figures/A30.ps}} \centerline{(c) Kernel regression, $K_{width}=\frac{1}{16}$} \end{minipage} \ \ \ \begin{minipage}{2.4in} \centerline{\epsfxsize= 2.4in \epsfysize= 2.4in \epsffile{/home/r2/oded/research/msthesis/figures/A50.ps}} \centerline{(d)Kernel regression, $K_{width}=\frac{1}{4}$} \end{minipage} \\ \begin{minipage}{2.4in} \centerline{\epsfxsize= 2.4in \epsfysize= 2.4in \epsffile{/home/r2/oded/research/msthesis/figures/L30.ps}} \centerline{(e) Local weighted regression} \centerline{ with $K_{width}=\frac{1}{16}$} \end{minipage} \ \ \ \begin{minipage}{2.4in} \centerline{\epsfxsize= 2.4in \epsfysize= 2.4in \epsffile{/home/r2/oded/research/msthesis/figures/L70.ps}} \centerline{(f) Local weighted regression } \centerline{with $K_{width}=1$} \end{minipage} \caption{Testing results on various memory based learning algorithms} \label{neighbor-example} \end{figure} To give an intuitive notion of how the various memory based learning methods fit a function, We trained some of them on 75 random points from the function $f(x) = 0.01x^3 - 3x^2 - 5x + 4$ in the interval $[-300,400]$. We also added 10\% random noise to all of the training points, which are shown in Figure~\ref{neighbor-example-train}. We then took 1000 random points in the interval $[-350,450]$ and the predictions made by 1-nearest-neighbor, 5-nearest-neighbor, kernel regression with $K_{width}=\frac{1}{16}$ and $K_{width}=\frac{1}{4}$, and local weighted regression with $K_{width}=\frac{1}{16}$ and $K_{width}=1$ are shown in Figure~\ref{neighbor-example}. As can be seen, having a kernel width which is too large results in too much smoothing, while using only a few nearest neighbors results in too much prediction noise. Efficient decision-making of which of these models is best is the topic of this paper. \subsection{Determining the accuracy of a model} To determine the accuracy of a model, we measure the difference between the predictions of the model and the true answers on a set of points where we have the true answers. However, we need to be careful not to use the training set for testing as well. For example, using a 1-nearest-neighbor method, we can get zero prediction error by testing on the training points. However, the performance of 1-nearest-neighbor on new points (the generalization error) can be much poorer. What is needed is a way to test not only rote memorization, but also the ability to generalize. There are two popular methods of estimating the learner's ability to generalize. One is partitioning the entire set of the teacher's examples into a training set and a testing set. The learner is trained on the training set, but its performance is determined on its average prediction error for points in the testing set. A prediction query involves giving the learner the attributes, but withholding the correct outputs. The learner's guess at the outputs is then compared to the true outputs. The second method of estimating generalization is called {em cross validation}. In the case of leave-one-out cross validation, we can use the same set of points for both training and testing by performing the following trick: train on all points except one; perform a prediction query on the one point which was held out; repeat this process for all points and return the average prediction error of all the iterations. This method might seem more computationally expensive than the test-set method, but it does have certain advantages, namely in cases where we cannot afford to partition the few training points that we have (i.e., there are not enough points) or when we need a good estimate of the error distribution over the entire space we are trying to learn. Also, as we will show bellow, for lazy learners such as memory-based methods cross validation is just as cheap computationally as finding the test-set error. Cross validation is a special case of a number of statistical reuse techniques such as jackknife and bootstrapping. For a readable overview of these techniques, see~\cite{efron:statistical}. \subsection{Preprocessing} In order to reduce the cost of finding a nearest neighbor, researchers have used two types of preprocessing methods. The two methods are organizing the data into a fast-access structure (such as a k-d tree) or eliminating redundant training points (also known as editing). By processing the data before the queries, a speedup in prediction is achieved at the expense of non-negligible training time. A k-d tree~\cite{preparata:comp-geometry} divides the space of points into hyper-ranges which span the space and allow nearest-neighbor queries of almost any size to be completed in $O(\log n)$, where $n$ is the number of training points. This is an improvement over the $O(n)$ behavior of the obvious brute force algorithm. There is an $O(n \log n)$ preprocessing cost and O(n) of additional memory is needed to maintain the tree. Editing methods approach the problem by attempting to reduce $n$, the number of points that need to be searched. There are various approaches, which include throwing out points which are classified correctly, merging points which are similar, and iteratively condensing the data set. For more detailed discussion of these methods, see~\cite{dasarathy:collection}. \subsection{The connection between MBL and racing} Unlike other machine learning methods, there is not an attempt to force the training points into a decision tree, a neural net, symbolic rules, or any formal representation. The points act as their own best representation. A direct implication of this fact is that no work needs to be performed during training --- we simply store the points in memory. Therefore, memory based learners are lazy; they only do work when queried for prediction of a new point. In this paper, we leverage the laziness in two ways. First, computing the leave-one-out cross validation error is just as cheap as computing the test-set error. That is because there is no need to retrain on all of the points but one. We can just `cover up' that point in memory and that is equivalent to retraining. Therefore, we have a quick, reliable estimator for the error of a memory based model by performing leave-one-out cross validation on all the points in the training set. Second, we can look at many different learners without worrying about the initial expense of training all of them. The only significant computation arises when they are tested. In fact, even if a k-d tree is built, we can use the same tree for learners with different $k$, different $K_{width}$, and different regression techniques. The only time when different k-d trees need to be built for different learners is if the distance metric varies. Therefore, a model selection technique such as racing is perfectly suited for selecting among various memory based learners. We can train as many as we want to do with zero cost. The only computational expense occurs during testing, and racing attempts to minimize exactly this expense. Using racing with other collections of models is also possible, but training time considerations then need to be included. \section{Previous approaches} Traditionally, there have been a number of popular ways to search through a large collection of models. Brute force was always applicable and gave the desired result, but at a high computational price. Descent methods such as hill climbing and conjugate gradient were much faster, yet did not guarantee to return the right result and, even worse, was not applicable in many cases. Other techniques such as simulated annealing and genetic algorithms fall into similar traps, since provably convergent versions of simulated annealing and genetic algorithms are too slow to be used in practice. Hoeffding Races manages to lessen the evils of these techniques, while retaining their benefits. \subsection{Brute force} Brute force attacks the problem in the simplest possible way. Given $m$ trained learners and a test set which consists of $n$ points, it performs a prediction query on every point for every single learner. It then computes the mean squared error of the predictions of each learner and selects the learner with the lowest error. This algorithm runs in time $O(n \cdot m)$, but always returns the best learner. \subsection{Descent methods} Gradient descent, or hill climbing~\cite{press:recipes}, treats the collection of models and their prediction error as a continuous and differentiable surface. It starts at some point on this surface, and proceeds to `descend' in the direction which has less error. The algorithm stops when it reaches a local minimum. In other words, when all of the neighboring models have higher error, the algorithm returns the current model. This algorithm is much faster than brute force since it does not need to find the error of every single model. It only needs to compute the error for the learners which are on the path to the optimal learner. However, there are two major problems: local minima and applicability. \begin{figure} \begin{minipage}{2.5in} \centerline{\epsfxsize= 2.5in \epsfysize= 2.5in \epsffile{/home/r2/oded/research/NIPS93/local-minima.ps}} \end{minipage} \ \ \ \begin{minipage}{2.5in} \caption[Example of local minima in model selection]{A space of models consisting of local-weighted-regression models with different numbers of nearest neighbors used. The global minimum is at one-nearest-neighbor, but a gradient descent algorithm would get stuck in local minima unless it happened to start in in a model where $k<4$.} \label{local-minima} \end{minipage} \end{figure} Local minimum is a well documented and analyzed problem with gradient descent. To give an example of it in the realm of model selection, let us say that we need to select among nine k-nearest-neighbor learners. They differ in their $k$ (i.e., the number of neighbors they look at in order to make a prediction). The error of each learner is plotted in Figure \ref{local-minima}. The points are connected so that we can pretend that the surface is continuous. Gradient descent starts at one of the points on the surface and moves toward a learner which has lower error. This method works fine if the initial point is $k=3,2,$ or $1$. However, for any other starting point, the algorithm will get stuck at a local minimum either at $k=4$ or $k=9$. In general, the error at the local minimum can be many times larger than the error at the global minimum, and in addition, the chance of starting at a place which will lead to a global minimum can be arbitrarily small. %%\begin{figure} %%\begin{minipage}{3in} %%\centerline{\epsfxsize= 3in \epsfysize= 4in %%\epsffile{/home/r2/oded/research/msthesis/figures/classroom-arrow.ps}} %%\end{minipage} %%\ \ %%\begin{minipage}{2.5in} %% \caption[Gradient descent search for the best student in a classroom] %% {An example of gradient descent search for the best student in %% a classroom} %% \label{classroom} %%\end{minipage} %%\end{figure} There is an even more serious problem with gradient descent that was ignored in the last example --- namely, there are many instances when it is not even applicable to model selection. Let us go back to the analogy of trying to find the best student in the class, and attempt to use gradient descent for this task. We start with some student in the class, compute his grade and the grades of his neighbors. Next we move in the direction of the student with the best grade in this group and compare her grade with her neighbors' grades. This process continues until we get to a student whose grade is the best among his neighbors. Clearly, this is a nonsensical method. There is no reason to presume that just because two students happen to sit next to each other in class means that their grades are related (unless they are cheating). More formally, at every step of the gradient descent algorithm, we need to find a collection of models which are `near' the current model. However, the collection of models may not have a distance metric (and therefore no concept of `near') defined on it. For example, how far is a neural network from a nearest-neighbor model? How far is a decision tree from a local weighted regressor? It is possible to {\em impose} a distance metric on any collection of objects, as shown dramatically in the classroom example, less obviously in the k-nearest-neighbor example, and even more sneakily in the cases where models are ordered according to simplicity. However, just because we can impose a metric does not mean that it is correct, or even useful. Just because there is a parameter to tune (e.g. $k$ in 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. Conjugate gradient is just as susceptible to this problem as its less-capable relative. \subsection{Genetic algorithms and simulated annealing} The same problems described with descent methods apply to these techniques as well, only less explicitly. In a genetic algorithm~\cite{goldberg:genetic}, we start with a population of different models, where each member is represented by a description which can be mutated and crossed with other descriptions. There is a certain probability that some bit in the representation mutates. Therefore, there is a distance imposed between models which is proportional to the average number of generations it takes to get between two representations. Again, this distance metric is completely arbitrary and is based solely on the representation of the models, which is just as meaningless as having it based on their position in a room. Simulated annealing~\cite{kirkpatrick:annealing} at high temperature performs as slowly as brute force. At low temperatures, it is restricted by the same problems described above for gradient descent. There are cooling schedules which guarantee convergence at a global minimum, but they are too slow to be practical. \section{Racing: Hoeffding and Bayes} In this section we formalize the notion of ``racing'' by defining what it means for one model to be winning the race over another. We use two different statistical bounds to determine with a certain confidence when one model's average error is significantly smaller than another's. Hoeffding's bound is a general bound which only relies on the assumption that the error queries are drawn independently. Using Bayesian bounds gives tighter results, at the expense of assuming that the errors are drawn from a normal distribution. \subsection{Hoeffding Races} \subsubsection{Hoeffding's Bound} Let us say that we have $N$ points with which to test a given model. If we were to test a model on all of them, then we would have an average error which we will call $E_{true}$. However, if we only tested the model on 10 points, then we only have an estimate of the true average error. We call the average after only $n$ points ($n < N$) $E_{est}$ since it is an estimate of $E_{true}$. The more points we test on (the bigger $n$ gets), the closer our estimate gets to the true error. How close is $E_{est}$ to $E_{true}$ after $n$ points? Hoeffding's bound lets us answer that question when the $n$ points are picked with an identical independent distribution from the set of $N$ original test points. In this case, we can say that the probability of $E_{est}$ being more than $\epsilon$ away from $E_{true}$ is \begin{equation} \Pr(|E_{true} - E_{est}| > \epsilon) < 2 e^{-2n{\epsilon^2}/B^{2}} \label{equation:hoeffding} \end{equation} \noindent where $B$ bounds the greatest possible error that a model can make~\cite{hoeffding:bound}. We would like to say that ``we are 99\% confident that our estimate of the average error is within $\epsilon$ of the true average error'', or in other words, $\Pr(|E_{true} - E_{est}| > \epsilon) < 0.01$. We denote the confidence parameter with $\delta$. Equating $\delta$ with the right-hand side of Equation~\ref{equation:hoeffding} gives us an expression for $\epsilon$ in terms of $n$, $B$, and $\delta$. \begin{equation} \epsilon(n) = \sqrt{\frac{B^{2} \log(2/\delta)}{2 n}} \label{equation:epsilon} \end{equation} Equation~\ref{equation:epsilon} tells us how close the estimated mean is to the true mean after $n$ points with confidence $1-\delta$. We will discuss how to obtain a value for $B$ in a later section. \subsubsection{The algorithm} The algorithm starts with a collection of learning boxes. We call each model a learning box since we are treating the models as if they were black boxes. We are not looking at how complex or time-consuming each prediction is, just at the input and output of the box. Associated with each learning box are two pieces of information: a current estimate of its average error and the number of points it has been tested upon so far. The algorithm also starts with a test set of size $N$. For leave-one-out cross validation, we can perform $N$ queries on a training set of size $N$. At each iteration of the algorithm, we randomly select a point from the test set. Then for each learning box: \begin{itemize} \item compute the error at the point by using that learning box. \item update the learning box's estimate of its own average error rate. \item use Hoeffding's bound and Equation~\ref{equation:epsilon} to calculate how close the current estimate is to the true error for each learning box. \end{itemize} \begin{figure} \centerline{\epsfxsize= 5in \epsfysize= 3in \epsffile{/home/r2/oded/research/NIPS93/example.ps}} \caption[Use of Hoeffding's bound to eliminate LBs] {An example where the best upper bound of learning box \#2 eliminates learning boxes \#1 and \#5. The size of $\epsilon$ varies since each learning box has its own upper bound on its error range, $B$.} \label{example} \end{figure} Each learning box now has a bound within which its true average error lies. We can eliminate those learning boxes whose best possible error (their lower bound) is still greater than the worst error of the best learning box (its upper bound); see Figure~ \ref{example}. The intervals get smaller as more points are tested (since $\epsilon$ gets smaller as $n$ gets larger), thereby ``racing'' the good learning boxes and eliminating the bad ones. \subsubsection{Ending the race} We iterate and keep picking test points until one of three conditions occur: \begin{enumerate} \item All but one of the learning boxes have been eliminated. The algorithm simply returns it as the best one. \item The algorithm can also be stopped once we have picked more than $N$ test points. However, since we are picking the testing points in an independent indentical distribution, that is not a strict requirement. \item Alternatively, the algorithm can be stopped once $\epsilon$ has reached a certain threshold. \end{enumerate} In any case, the algorithm returns a set of learning boxes whose errors are indistinguishable to within $2 \cdot \epsilon(n)$. \subsubsection{Proof of correctness} The rash reader would ask why a proof of correctness is necessary since we used a proven statistical tool which should make the algorithm proven with confidence $\delta$ as well. However, the careful reader would have noticed that the confidence $1 - \delta$ given in the previous section is not correct for the entire algorithm. $1- \delta$ is the confidence in Hoeffding's bound for {\em one} learning box during {\em one} iteration of the algorithm. What we need is to prove that the {\em entire} algorithm has some confidence $1 - \Delta$ of returning the best learning box. For the sake of a simpler proof, let us make the requirement of a correct algorithm more stringent. We will say that the algorithm is correct if every learning box is within $\epsilon$ of its true error at every iteration of the algorithm. This requirement encompasses the weaker requirement that we do not eliminate the best learning box. An algorithm is correct with confidence $1 - \Delta$ if \begin{equation} \Pr\{ \; all \; learning \; boxes \; are \; within \; \epsilon(n) \; on \; all \; iterations\} \geq 1-\Delta \label{equation1} \end{equation} What we would like to do is show the relationship between $\delta$ (the chance of being wrong on one learning box in one iteration) and $\Delta$ (the chance of being wrong on the whole algorithm), so that when the user wants the algorithm to work with probability $0.999$, we can translate that into the confidence that we need for each learning box at each iteration. We will be relying on the disjunctive probability inequality which states that $Pr\{A \vee B\} \leq Pr\{A\} + Pr\{B\}$. Let us assume that we have $n$ iterations (we have $n$ points in our test set), and that we have $m$ learning boxes ($LB_{1}, \cdots, LB_{m}$). We start with the fact that: \begin{equation} Pr\{ \; a \; particular \; LB \; is \; within \; \epsilon(i) \; on \; a \; particular \; iteration \; i\} \geq 1-\delta \end{equation} Flipping that around we get: \begin{equation} Pr\{ \; a \; particular \; LB \; is \; wrong \; on \; a \; particular \; iteration\} < \delta \end{equation} Using the disjunctive inequality we can say \begin{eqnarray} Pr\{ & a \; particular \; LB \; is \; wrong \; on \; iteration \; 1 \; \vee \nonumber \\ & a \; particular \; LB \; is \; wrong \; on \; iteration \; 2 \; \vee \nonumber \\ & . \; . \; .\nonumber \\ & \; a \; particular \; LB \; is \; wrong \; on \; iteration \; n\} \leq \delta \cdot n \end{eqnarray} Let us rewrite this as: \begin{equation} Pr\{ \; a \; particular \; LB \; is \; wrong \; on \; any \; iteration \; up \; to \; n\} \leq \delta \cdot n \end{equation} Now we do the same thing for all learning boxes: \begin{eqnarray} Pr\{ & LB_{1} \; is \; wrong \; on \; any \; iteration \; \vee \nonumber \\ & LB_{2} \; is \; wrong \; on \; any \; iteration \; \vee \nonumber \\ & . \; . \; .\nonumber \\ & \; LB_{m} \; is \; wrong \; on \; any \; iteration \} \leq \delta \cdot n \cdot m \end{eqnarray} or in other words: \begin{equation} Pr\{ \; some \; LB \; is \; wrong \; in \; some \; iteration\} \leq \delta \cdot n \cdot m \end{equation} We flip this to get: \begin{equation} Pr\{ \; all \; LBs \; are \; within \; \epsilon(n) \; on \; all \; iterations\} \geq 1 - \delta \cdot n \cdot m \label{equation2} \end{equation} Clearly, Equation~\ref{equation2} is the same as Equation~\ref{equation1} and we can therefore conclude that $\delta = \frac{\Delta}{n \cdot m}$. When we plug this into Equation~\ref{equation:epsilon} (our expression for $\epsilon$ from the previous section), we pump up $\epsilon$, and thereby ensure the correctness of this algorithm with confidence $\Delta$. The new $\epsilon$ is expressed as: \begin{equation} \epsilon(n) = \sqrt{\frac{B^{2} (\log(2 n m) - \log(\Delta))}{n}} \end{equation} This is an extremely pessimistic bound on $\Delta$ and tighter proofs are possible \cite{omohundro:suggestion}. It is pessimistic in two regards: first, it assumes that all learning boxes are completely independent of each other. Second, it assumes that the error of a learning box after seeing $n$ points is completely independent of its error after seeing $n+1$ points. This is clearly a worst case assumption, and most PAC bounds are made tighter by leveraging this point. \subsection{Bayesian Races} Hoeffding's bound is as tight as we can get without making additional assumptions about the distribution of the errors we get from a learning box. If we assume that the errors are normally distributed, then we can use Bayesian statistics to achieve a tighter bound on the probability that one learning box is better than another. Specifically, .... A MORE DETAILED DISCUSSION OF THE ML-94 APPENDIX. AND ALSO A FORMULATION OF THE EXACT BOUND WHICH CAN BE COMPARED TO HOEFFDING. \section{Extensions} This section describes several extensions and expansions of the basic racing algorithm. We describe how to determine a bound on $B$ --- the maximum error of a model on any test query, to be used in Hoeffding races. We also describe a method for tightning the confidence intervals for each model and for eliminating redundant models in the set (models which are statistically equivalent). \subsection{Bounding errors} The most obvious obstacle to implementing Hoeffding Races is finding a value for $B$, the maximum error of a learning box. For classification problems, there is no difficulty --- $B$ is simply $1$. That is because the worst mistake that the algorithm can make is a misclassification which has an error of $1$. For regression problems the solution is less straightforward. If we know something about the learner and something about the data, then we can try to put some finite bound on $B$. If that is not possible, then we can attempt to estimate $B$ by adding a few standard variances to the average error of this learner. Since the average error and variance are updated after every new point, the value of $B$ also gets modified at each iteration. The value of $B$ tends to fluctuate wildly during the first few points until the average and variance settle down. To avoid that, we only start racing after collecting errors from about 30 points from each learning box. \subsection{Shrinking the intervals} With a little effort, we can actually tighten the bounds around the estimated error for each learning box. First we need to name a few important components of a learning box. Let us call the estimated error for the $k^{th}$ learning box at the $i^{th}$ iteration $E_{est}^k(i)$. We will call the lower bound of that learning box $lower^k(i)$ and likewise the upper bound will be called $upper^k(i)$. These can be calculated by $E_{est}^k(i) - \epsilon(i)$ and $E_{est}^k(i) + \epsilon(i)$ respectively. From now on, we will be dropping the superscript, since we will be talking about one learning box, but applying the ideas to all of them. \begin{figure} \centerline{\epsfxsize= 5in \epsfysize= 4in \epsffile{/home/r2/oded/research/msthesis/figures/shrink.ps}} \caption{Example of how to shrink the interval bounds} \label{shrink-example} \end{figure} During the course of running the race, all three of these components tend to fluctuate. $E_{est}(i)$ moves around with every new point, trying to get closer to the true error. $lower(i)$ and $upper(i)$ move around for two reasons: the first is that $\epsilon$ gets smaller at each iteration; the second is that $E_{est}(i)$ changes after almost every new point. However, despite all of this movement, we are guaranteed that with confidence $1-\Delta$, $E_{est}(i)$ will stay between the lower and upper bounds. What if at iteration $i+1$ we get a point upon which the learning box performs very badly? In this case, $E_{est}(i+1)$ is larger than $E_{est}(i)$. The bounds have become tighter because of the decrease in $\epsilon$, but they have been transformed by the increase in $E_{est}$. However, $E_{est}(i+1)$ is guaranteed to stay not only within the bounds at iteration $i+1$, but also within the bounds at all iterations until now. Therefore, the new upper bound should not be $E_{est}(i+1) + \epsilon(i+1)$, but instead the tighter \begin{equation} upper(i+1) = Min(E_{est}(i+1) + \epsilon(i+1) , E_{est}(i) + \epsilon(i)). \end{equation} Likewise, a tighter lower bound at iteration $i+1$ is \begin{equation} lower(i+1) = Max(E_{est}(i+1) - \epsilon(i+1) , E_{est}(i) - \epsilon(i)) \end{equation} An example of shrinking the intervals is shown in Figure~\ref{shrink-example}. The bound of iteration $i+1$ can be improved based on previous bounds. \subsection{Eliminating indistinguishable models} So far we have only discussed elimination of models that are considerably worse than the best models. However, we can also try to speed up the race by eliminating models which seem to be identical in predictive power to other models. In other words, we wish to eliminate any model which we are confident is worse than some other model; we also wish to stop a race between two models which we believe with high confidence to be extremely similar. The latter can be achieved by defining a threshold $\gamma$ (a small positive number) and eliminating any model which we are confident has an estimated error within $\gamma$ of another model. These two rules can be combined into one formulation: given two distinct learning boxes $LB_{i}$ and $LB_{j}$, with an estimated error of $E_{est}^{i}$ and $E_{est}^{j}$ respectively, we eliminate $LB_{j}$ from the race if \begin{equation} \Pr\{E_{est}^{i} < E_{est}^{j} - \gamma \} < \delta. \end{equation} \subsection{Blocking} There are two common problems that empirically seem to slow down the races. One problem occurs when learning boxes have a vary large variance in error over the test set. In that case, we cannot eliminate them or use them to eliminate other learning boxes since their confidence are so large. Another problem occurs when two or more learning boxes have some degree of dependence, so that they preform badly on the same points. In that case, we need many cycles through the race (many test points) in order to distinguish between them. We deal with both problems by using a statistical method known as {\em blocking}~\cite{box:blocking}. Instead of racing to get a tight estimate of a model's error, we race for a tight estimate of the difference in error between two models. Rather than maintaining an average error for each learning box, we maintain an average error difference (denoted $ED_{est}^{i,j}$) for every pair of learning boxes $(i,j)$. If we let $e_{i}(l)$ be the error of the $i^{th}$ learning box on the $l^{th}$ testing point, then our estimate of the error difference after seeing $k$ test points is \begin{equation} ED_{est}^{i,j} = \frac{1}{k}\sum_{l=1}^{k} (e_{i}(l) - e_{j}(l)) \end{equation} As before, we can use either Hoeffding's Bound or a Bayesian bound in order to determine when the error difference between two models becomes significant, or in other words, when \begin{equation} \Pr\{ED_{est}^{i,j} < 0\} < \delta. \end{equation} We check this condition for every pair $(i,j)$ of learning boxes and eliminate $LB_{j}$ if it is true. Indistinguishable models can be eliminated if $\Pr\{ED_{est}^{i,j} < -\gamma\} < \delta$. The simplest example of blocking having a beneficial effect is the case where two models in the race are identical --- the original racing algorithm would have to race for a long time. The racers would have the same mean at each step of the race, but the race would only end when they both had so many samples that the confidence intervals on its measures of the mean error of each model were both very close to $\gamma$ (its indifference parameter). In contrast, blocking race algorithm would maintain, at each step, the difference between the leave-one-out errors on each datapoint. Because the models are the same, this difference would always be zero and it would only require a very small number of statistics (perhaps less than ten, depending upon the parameters) before one of the models was eliminated. The example of identical models is extreme, but in the more common case of near-identical models there can also be a large reduction in the time to elimination. \section{Empirical results} \subsection{Results from Hoeffding races} We ran Hoeffding Races on a wide variety of classification and regression problems which are described below. These results were also presented in~\cite{maron:hoeffding}. The data files are available from the authors. \begin{description} \item[ROBOT] 10 input attributes, 5 outputs. Given an initial and a final description of a robot arm, learn the control needed in order to make the robot perform devil-sticking~\cite{schaal:openloop}. \item[PROTEIN] 3 inputs, output is a classification into one of three classes. This is the famous protein secondary structure database, with some preprocessing~\cite{zhang:protein}. \item[ENERGY] Given solar radiation sensing, predict the cooling load for a building. This is taken from the Building Energy Predictor Shootout. \item[POWER] Market data for electricity generation pricing period class for the new United Kingdom Power Market. \item[POOL] The visually perceived mapping from pool table configurations to shot outcome for two-ball collisions~\cite{moore:forward}. \item[DISCONT] An artificially constructed set of points with many discontinuities. Local models should outperform global ones. \end{description} We have run Hoeffding Races on a collection of memory based learning algorithms. The learning boxes varied in the number of nearest neighbors that they looked at ($k=1,3,5,7,9$), in the degree of smoothing performed ($K_{width}=4,2,1,\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{16},\frac{1}{32},\frac{1}{64}$), and whether the function was locally constant or performed local weighted regression. The distance metric was not varied. All of the experiments were run using $\delta=0.01$. We used the techniques mentioned earlier for estimating $B$ and for shrinking the intervals, but the indifference parameter $\gamma$ and blocking were not used. We compare Hoeffding Races to brute force relative to the number of queries made, where a query is one learning box finding its error at one point. The results are summarized in Table~\ref{results}, which shows the number of points in the training set (and therefore the number of leave-one-out queries that one learning box can perform), the initial number of learning boxes, the number of queries performed by brute force and Hoeffding Races, the number of learning boxes left at the end of the race, and the speedup factor in number of queries. \begin{table} \begin{center} \begin{tabular}{|lccc|} \hline Problem & \# points & Initial \# & \# queries with \\ & & learning boxes & Brute Force \\ \hline ROBOT & 972 & 95 & 92340 \\ PROTEIN & 4965 & 95 & 471675 \\ ENERGY & 2444 & 189 & 461916 \\ POWER & 210 & 95 & 19950 \\ POOL & 259 & 95 & 24605 \\ DISCONT & 500 & 95 & 47500 \\ \hline \hline Problem & \# queries with & \# learning & speedup \\ & Hoeffding Races & boxes left & factor \\ \hline ROBOT & 15637 & 6 & 5.91\\ PROTEIN & 349405 & 60 & 1.35\\ ENERGY & 121400 & 40 & 3.80\\ POWER & 13119 & 48 & 1.52 \\ POOL & 22095 & 75 & 1.11\\ DISCONT & 25144 & 29 & 1.89\\ \hline \end{tabular} \caption{\label{results} Results of Brute Force vs. Hoeffding Races.} \end{center} \end{table} There are a few observations to be made from this table: \begin{itemize} \item Hoeffding Races never performs more queries than brute force, and its overhead is negligible. \item In all the cases we have tested, the learning box chosen by brute force is also contained by the set returned from Hoeffding Races. Therefore, there is no loss of performance accuracy. \item It is least effective when a large percentage of the original learning boxes are left at the end. For example, in the POOL problem, where there were 75 learning boxes left at the end of the race, the number of queries is only slightly smaller for Hoeffding Races than for brute force. In the ROBOT problem, where only 6 learning boxes were left, a significant reduction in the number of queries can be seen. \item The obvious conclusion from this observation is that Hoeffding Races is most effective when there exists a small subset of clear winners within the initial set of models. In fact, it becomes more and more effective (in comparison to brute force) the larger the size of the initial set of models. \end{itemize} \begin{figure} \begin{minipage}{2.5in} \centerline{\epsfxsize= 2.5in \epsfysize= 2.5in \epsffile{/home/r2/oded/research/NIPS93/hoeff-vs-brute.ps}} \end{minipage} \hspace{1cm} \begin{minipage}{2.5in} \caption[Scaling of Hoeffding Races vs. brute force] {The bottom line shows the number of queries taken by Hoeffding Races for the ROBOT problem as the size of the initial set of learning boxes is increased. The top line shows the performance by brute force. At each point, the set of learning boxes was chosen randomly.} \label{hoeff-vs-brute} \end{minipage} \end{figure} In order to test this conclusion, we created random subsets of increasing sizes from the 95 learning boxes used for the ROBOT experiment. We ran Hoeffding Races on each one of the subsets, and tabulated the results in Figure~\ref{hoeff-vs-brute}. As can be seen, we can search over a large set of models without much concern about the computational expense of a large initial set. In other words, if we have very little knowledge of the problem, we should not preclude any possible solution --- Hoeffding Races lets us do that without much computational expense. We do not think that there is a general asymptotic relation between Hoeffding Races and brute force as the number of models grow. As shown by Table~\ref{results}, it is problem dependent. However, it is clear that Hoeffding Races works badly on `boring' problems, where any arbitrary model does as well as anything else, and works very well on `interesting' problems, where only a few models really fit the domain. Running the classroom analogy completely into the ground, the boring problems can be thought of as picking the best gym student (everybody gets A's in gym), and the interesting problems can be thought of as picking the best history student (where the grade distribution is such that there are only a few excellent students). \subsubsection{Real life application: segmenting Magnetic Resonance Images} In addition to the small datasets described above, we used the combination of Hoeffding Races and memory based learning in a larger application. The input is a 3-D image of the brain, generated in slices from a Magnetic Resonance machine. Each point in the image becomes a point in the training set. A point is described by its $(x,y,z)$ coordinates in the image and by two descriptive attributes: the proton density and the viscosity of the tissue. This quintuple is mapped into a classification (segmentation) of either gray matter, white matter, fluid, or lesion. The entire data set is quite large: 10 patients, two to four images across time for each patient, and about 0.5 million points per image. The segmentation problem is important in several medical imaging applications. For example, Multiple Sclerosis (MS) causes brain lesions, whose volume needs to be tracked over time in order to determine if the treatment is working, or the rate of deterioration. If this were to be done by hand, a specialist would need to look through over 50 slices of the brain, determine the location and size of the lesions in each slice, and add them up to get a piece of information for one person during one time point. This becomes horribly time consuming when there are many patients getting scanned on a weekly basis. We would like to automate the process by training on images from a single patient, taken at different times, and then segmenting future images. An even more ambitious goal is to train on multiple patients and predict on unseen patients' images. A detailed description of the various experiments and results can be found in~\cite{maron:thesis}. In summary, using Hoeffding Races allowed us to make only 69\% of the queries and saved hundreds of hours of CPU time. The best learning box incorrectly classified 18\% of points from new patients. \subsection{Results from Bayesian races and blocking} Table~\ref{tab:comp} shows some results comparing the Bayesian Race algorithm with and without blocking with the standard brute force algorithm that computes all the models exhaustively. In the results, ``Evals'' denotes the number of individual {\loocv} computations needed by the search, ``Correct?'' asks whether the model selected by the search had the true minimum {\loocv}, and the ``Relative evals'' column gives the fraction of the cost of the search relative to the exhaustive search. EXH is the brute force method, RACE is Bayesian Races, and BRACE is Bayesian Races with blocking. The algorithms were tested on datasets from a billiards robot (3 inputs, 1 output, 253 points) and a juggling robot that was used in the Hoeffding Races experiments described earlier(12 inputs, 1 output, 972 points). For these experiments, $\delta = 0.001$ and $\gamma = 0.001$. The $\delta$ value means we have to be $99.9\%$ ($= 100(1 - \delta)$) sure before eliminating a model from a race. The $\gamma$ value means we are prepared to accidently eliminate models which are very slightly better (by a factor $\gamma = 0.001$) than the race winner. There were the same set of twenty models in each race. Ten models were local weighted averaging (also known as kernel regression) and ten models were locally weighted regression~\cite{clvl:lcll}. Each group of ten models had different kernel smoothing parameters from the set $\{ 2^{-9} , 2^{-8} , \ldots 2^{-1} , 2^0 \}$. \begin{table*} \caption{Experiments on Bayesian Races and blocking} \label{tab:comp} \begin{center} \begin{tabular}{|l||lll||lll|} \hline & \multicolumn{3}{|c||}{Billiards} & \multicolumn{3}{|c|}{Juggling} \\ \hline Method & Evals & Correct? & Relative & Evals & Correct? & Relative \\ & & & Evals to & & & Evals to \\ & & & EXH & & & EXH \\ \hline EXH & 5060 & Yes & 1.000 & 19440 & Yes & 1.000 \\ \hline RACE & 2464 & Yes & 0.487 & 2558 & Yes & 0.132 \\ \hline BRACE & 1049 & Yes & 0.207 & 882 & Yes & 0.045 \\ \hline \end{tabular} \end{center} \end{table*} In both these experiments RACE improved on the exhaustive method, and BRACE in turn improved upon RACE. The proportional improvement was greater for the juggling example, mainly because the juggling dataset is larger. A larger dataset means the exhaustive method has to perform proportionally many extra {\loocv} evaluations, whereas the racing methods can stop before all datapoints are evaluated. In three of the four races in Table~\ref{tab:comp} there was only one model left at the end of the race. For the RACE algorithm on the billiards dataset, 8 of the 20 models survived to the end. \section{Racing for relevant attributes} A particularly promising use of cross validation is to automatically choose relevant inputs from a wider set of possible inputs. An obvious benefit is in accelerating the learning rate of algorithms which suffer in the face of irrelevant inputs. Other benefits include helping select relevant visual features for visually controlled robot tasks~\cite{moore:brute-force}, and selecting sets of time windows in time series predictions. This problem, known as ``subset selection'' is a well-known problem in statistics, surveyed thoroughly in~\cite{mllr:sbst} and is rapidly gaining attention in the Machine Learning community. In the recent Conference on Machine Learning proceedings, three other papers addressing subset selection for various machine learning algorithms are:~\cite{crn:grdy,jhn:irrl,sklk:prtt}. Given $D$ inputs there are $2^D$ possible input sets, and so performing an exhaustive cross validation search over all of them soon becomes impractical as $D$ rises, even assuming adequate data support to justify searching so many models. Hill climbing is a sensible alternative since the space we are climbing over has a reasonable ``neighbor'' concept. In this section we provide several hill climbing versions of the racing algorithm; these aim to both speed up the computation and also to reduce the danger of becoming trapped at local maxima. Sets of inputs can be represented as binary strings. Given four possible inputs, 0101 would denote ``ignore inputs 1 and 3, use inputs 2 and 4.'' The standard non-racing hill climbing algorithm begins with a start string (e.g. 0000) then makes all possible 1-feature changes to it (1000, 0100, 0010, 0001) and exhaustively finds which minimizes the leave-one-out cross validation ({\loocv}) error. It then uses this best string (say 0100) as a new base point, generates all its 1-feature successors (1100, 0000, 0110, 0101), and determines the best. It continues in this way until no single-feature change improves it. The special case of starting with all zeroes is termed forward selection (FOR-SEL), and that of starting with all ones is termed backward elimination (BACK-SEL). Forward selection is better if only a few features are expected to be relevant and backward elimination is better if only a few features are expected to be irrelevant. Unfortunately, such prior knowledge may not be available at the start of the search. The racing counterparts to these algorithms are straightforward: from the base string generate all 1-feature changes and race them. Proceed until the winner of a race does not improve on its base. In the experiments described later two versions are tested, FOR-RACE and BACK-RACE, which start at all zeroes and all ones respectively. There is, however, an objection to this simple application of racing. Imagine that inputs 4, 5, and 6 are all relevant and independently provide a reduction in the LOOCV error. If we start at string 0000000 and successors 0000100, 0000010, and 0000001 are all good, it will be a shame to run through three separate hill climbing iterations to switch them all on. This motivates the next algorithm, a Gauss-Seidel version of hill climbing: \begin{itemize} %\begin{tabular}{p{3.2in}} \item Begin with a predefined start string (e.g. 00000) \item Race between the current string and the current string with the first bit flipped (00000 versus 10000) \item Select the winner of that race as the new current string (e.g. 10000) \item Now race between the current string and the current string with the second bit flipped (10000 versus 11000) \end{itemize} \mbox{} \hspace{1.3in} $\vdots$ \mbox{} \hspace{1in} %\end{tabular} \noindent ...until all bits have been raced. Then return to the first bit and proceed until an entire pass through the current string fails to produce an improvement. Versions of this algorithm, FOR-GS-RACE and BACK-GS-RACE, are tested below. On some occasions they do indeed help, but on others their performance is poor. A further new algorithm --- Schemata Search --- does Gauss-Seidel's job better, and also solves another problem. \subsection{SCHEMATA SEARCH} Schemata search is a new algorithm described in~\cite{moore:schemata} which aims to solve the same problem that the Gauss-Seidel method addresses---the problem of forward selection taking a long time if many features are relevant, or similarly backward elimination taking a long time if many features are irrelevant. It will also help with a second problem. Suppose there is a family of three features which must all be on simultaneously for any reduction in the {\loocv} error. If any family member is ignored then the {\loocv} error is just as bad as if all family members were ignored. This can happen quite easily, for example if the features are distributed between -1 and 1 and the function being learned is their product. Forward selection would be very likely to miss this family and to converge on something suboptimal. Backward elimination would not have this problem, but if many features are irrelevant then it can become stuck itself (because in the early stages of hill climbing the removal of one irrelevant attribute among many does not improve the {\loocv} error). Schemata search searches over the space of schemata strings, which have 0's, 1's and {\mst}'s in them. A {\mst} denotes a fifty percent chance of the attribute being ignored, and a fifty percent chance of it being used. The {\loocv} error of such a string is the expected {\loocv} error of a binary string generated from the schemata string according to these random rules, for example \begin{eqnarray*} \loocve(101{\mst}{\mst}) & = & \frac{1}{4} \loocve(10100) + \\ & & \frac{1}{4} \loocve(10101) + \\ & & \frac{1}{4} \loocve(10110) + \\ & & \frac{1}{4} \loocve(10111) \end{eqnarray*} Now a simple algorithm is to begin with all stars (e.g. {{\mst}{\mst}{\mst}{\mst}{\mst}}) , and then to find out (by racing) whether it is better to have the first field as a 1 or a 0 (i.e. we would race {1{\mst}{\mst}{\mst}{\mst}} and {0{\mst}{\mst}{\mst}{\mst}}). Having finished the first race, we could determine the second field by another race, and so on until the entire string is filled with 1's and 0's. In practice, we can do better than this. Instead of beginning by racing the first field, we can race all fields against each other in parallel: \begin{center} \begin{tabular}{lll} 1{\mst}{\mst}{\mst}{\mst} & races against & 0{\mst}{\mst}{\mst}{\mst} \\ {\mst}1{\mst}{\mst}{\mst} & races against & {\mst}0{\mst}{\mst}{\mst} \\ {\mst}{\mst}1{\mst}{\mst} & races against & {\mst}{\mst}0{\mst}{\mst} \\ {\mst}{\mst}{\mst}1{\mst} & races against & {\mst}{\mst}{\mst}0{\mst} \\ {\mst}{\mst}{\mst}{\mst}1 & races against & {\mst}{\mst}{\mst}{\mst}0 \\ \end{tabular} \end{center} Thus, given $D$ inputs, we have $D$ races occurring in parallel, and we stop all races when any one race produces a winner (to confidence level $\delta$). On each step of the race a random binary string is generated, and then the {\loocv} error of one randomly chosen datapoint is computed using that binary string. This statistic is added to the statistics of all the strings in the above sets of races which match the binary string. This continues until one of the pairs of racers becomes significant, i.e. when we believe with probability $1-\delta$ that one member of the significant pair beats its competitor. Then the next iteration of the race begins with a new set of racers which all have the winning field of the previous race switched on. If, in the above race, {\mst}1{\mst}{\mst}{\mst} became significantly better than {\mst}0{\mst}{\mst}{\mst} the next iteration would have \begin{center} \begin{tabular}{lll} 11{\mst}{\mst}{\mst} & races against & 01{\mst}{\mst}{\mst} \\ {\mst}11{\mst}{\mst} & races against & {\mst}10{\mst}{\mst} \\ {\mst}1{\mst}1{\mst} & races against & {\mst}1{\mst}0{\mst} \\ {\mst}1{\mst}{\mst}1 & races against & {\mst}1{\mst}{\mst}0 \\ \end{tabular} \end{center} \noindent This may be preferable to our other hill climbing racers for three reasons: \begin{itemize} \item If any feature is outstandingly good, it will be detected quickly without having to wait for an entire iteration of hill climbing to take place. \item If several features are independently good then one of them will be quickly selected, without having to wait to determine which precisely is the best, which is a weakness of FOR-RACE and BACK-RACE. \item Small, mutually dependent, families of features that would be missed by the other hill climbers may be found. If features 1, 2 and 3 must all be on to gain any benefit, then schemata string 1{\mst}{\mst}{\mst}{\mst}{\mst} will eventually win a race against 0{\mst}{\mst}{\mst}{\mst}{\mst} because 25\% of the strings generated from the former have features 1, 2, and 3 all on, whereas 0\% of the latter do. We have performed experiments, not shown here, to test this phenomena in noisy binary optimization problems with mutually dependent families of up to size five, and schemata search is the only algorithm that finds the correct family. \end{itemize} \subsection{Experiments} We have run all these algorithms on fifty-six randomly generated synthetic datasets. The task was to find the set of features which minimized the leave-one-out cross-validation error of a 1-nearest-neighbor function approximator. The datasets all had between 4 and 12 inputs and one real-valued output which was a noisy multivariate function of a random subset of the inputs. All inputs were randomly generated uniformly in the range {\mbox{$-1 \leq x_i \leq 1$}}. The multivariate function was from the syntax in Table~\ref{tab:syntax}. \begin{table*} \caption{Syntax Of Multivariate Functions In Experiments} \label{tab:syntax} \begin{center} \begin{tabular}{|p{0.5in}p{1in}p{2.9in}|} \hline \expr {\tt ::=} & $X_i$ & the $i$th input \\ & $\expr \times \expr$ & the product of the subexpressions \\ & \mbox{mean}($\expr, \expr$) & the mean of the subexpressions \\ & \mbox{max}($\expr, \expr$) & the maximum of the subexpressions \\ & $\corrupt(\expr)$ & gaussian random noise of $\pm 0.1$ is added to the value of the subexpression \\ & $g(\expr)$ & where $g$ is a non-differentiable function $g(x) = -x^2$ if $x > 0$ and $g(x) = -x^2 - 2x$ if $x \leq 0$.\\ \hline \end{tabular} \end{center} \end{table*} \noindent The number of terms in the dataset was also randomly decided, and varied between 5 and 30. Thus some datasets were trivial, such as $\mbox{output} = \frac{1}{2}(x_2 + x_7)$, and others complex, such as {\tt \begin{quote} output = max( corrupt( product( mean( g( x4 ) , g( corrupt( x2 ) ) ), product( x5 , corrupt( x5 ) ) ) ) , g( corrupt( g( g( g( g( corrupt( max( x5 , corrupt( x3 ) ) ) ) ) ) ) ) ) ) \end{quote}} \noindent It is interesting to note that all the searchers managed to identify the precise set of relevant inputs for this complex dataset, which had 950 datapoints\footnote{The slowest method was FOR-SEL, needing 19000 evaluations, and the fastest was SCHEMATA$+$, described shortly, which needed 2215 evaluations}. In all the experiments, $\delta = \gamma = 0.001$. Figure~\ref{forward} shows the performance of the forward searchers and schemata on the 56 random datasets. There are two measures of performance. \begin{itemize} \item {\bf Accuracy.} How often do the searchers end at suboptimal solutions? This is shown by the columns \begin{itemize} \item $P_{IP} = $ the percentage of datasets for which the searcher produced an ``imperfect'' result. A result is imperfect if any other search produced a feature-set with a lower {\loocv} error. \item $P_{FW} = $ the percentage of datasets for which the result was fairly wrong, i.e. had a {\loocv} error more than 0.001 greater than the minimum found by any other search. To give this number some meaning, the minimum {\loocv} errors found were typically in the range $0.01-0.2$ depending on the dataset, with a similar magnitude of variation. \item $P_{VW} = $ the percentage of datasets for which the result was very wrong, i.e. had a {\loocv} error more than 0.01 greater than the minimum found by any other search. \end{itemize} \item {\bf Search time.} This is given by the number of individual evaluations of {\loocv} errors. The mean figure is shown, but this is dominated by the few hard datasets which required tens of thousands of evaluations for all methods. Many other datasets required only thousands, or in some cases, hundreds of evaluations. For this reason, also shown (by scatterplots) are the distributions of the ratio of number of samples needed compared with the number of samples needed by the conventional forward selection method. As can be seen, this distribution is highly skewed, especially for the schemata searches. $50\%$ of the schemata searches took less than a quarter of the time of the conventional search. 12 of the 56 schemata searches took over twice as long. \end{itemize} \noindent Figure~\ref{backward} is a similar table comparing the various backward methods and the same schemata searches (which have no forward or backward biases). The forward and backward racing methods were usually faster than the conventional methods with little loss of accuracy. The Gauss-Seidel races were similar in performance. The schemata search was also roughly equal in accuracy, except that in this set of experiments it achieved the distinction of no ``very wrong'' errors. Of the twelve schemata searches which were twice as long as the conventional forward method, seven were due to the conventional method quickly becoming stuck with an inferior solution---after considerably more computation schemata search found a better result. Of the other five, four eventually found equally good solutions and one found a slightly inferior solution. Interestingly the schemata searches frequently found all the relevant features very fast, often in a tenth of the total time of their search. This produced strings with only 1's and {\mst}'s in them. But they would then spend a very long time convincing themselves that they were justified in putting 0's elsewhere. As an initial and ugly attempt to address this, we tried an additional algorithm, SCHEMATA$+$, which would give up and replace {\mst}'s with 0's very eagerly. If 2000 iterations of one of its races produced no significant winners, it forced one of the stars to zero (using the race statistics to choose the input least likely to be relevant). SCHEMATA$+$ was the fastest algorithm at converging but was less reliable than SCHEMATA. \newcommand{\heightdiff}{3mm} \newcommand{\scatwid}{60mm} \newcommand{\scatdiff}{5mm} \newcommand{\scatheight}{35mm} \begin{figure*}[tb] \begin{minipage}{6.2in} {\footnotesize \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} \mbox{\psfig{file=forward.ps,height=\scatheight}} \end{minipage}}} \caption{Comparing the conventional forward selection algorithm against its racing counterparts, and against schemata search (which has no forwards-backwards bias).} \label{forward} \end{minipage} \end{figure*} \begin{figure*}[tb] \begin{minipage}{6.2in} {\footnotesize \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} \psfig{file=backward.ps,height=\scatheight} \end{minipage}}} \caption{Comparing the conventional backward elimination algorithm against its racing counterparts, and against schemata search (which has no forwards-backwards bias).} \label{backward} \end{minipage} \end{figure*} \section{Conclusion} In this paper, we presented the racing algorithm and some extensions to it, specifically in the framework of model selection. However, racing can be thought of as just another searching technique such as A* or hill climbing. It can therefore be used in the many of the applications of search in Machine Learning and Artificial Intelligence. It seems to be especially useful for search in spaces which are riddled with local minima, or spaces which are discrete. The speedup over exhaustive search, and the algorithm's ability to quantify the confidence in its result make it a viable alternative to existing heuristic search techniques. \subsection{Related Work} We were motivated to find efficient techniques for model selection by working on Moore's GMBL system~\cite{moore:brute-force}. Haussler's work on generalizations of the PAC model~\cite{haussler:genpac} provided a treasure of ideas which, combined with Kaelbling's confidence bounds~\cite{kaelbling:thesis}, generated the Hoeffding Races algorithm. The notion of racing shows up in related forms in multi-armed bandit problems. To give one example, Rivest and Yin~\cite{rivest:bandit} give a heuristic for picking which arm to pull next according to the probability distributions of the payment of each arm. Greiner has independently developed a PALO (Probably Approximately Locally Optimal) algorithm~\cite{greiner:palo} which also uses Hoeffding's bound in order to decide when one point is better than another. The main differences between our work is that he uses his method for gradient descent , and that he is not trying to select among models, but among Horn clauses and default rules. It is possible to use a descent method in a discretized space by picking among a finite number of discrete gradients. At each iteration, the PALO algorithm compares the estimated error of stopping against the estimated error of each one of the neighboring possibilities. The algorithm then goes in the direction of the least error. The comparison is made faster by using a racing technique. MORE STUFF?? OTHER SYSTEMS RELATED TO GMBL?? \subsection{Future Work} There are many ways to extend this research. We list a few of them: The only criterion used in this paper to compare and evaluate learners has been their accuracy. It is possible for other factors to influence the selection of a learner, but then we can no longer treat it as a learning {\em box}. We need to look inside each learner and consider issues such as response speed, simplicity, or other a priori biases. These issues can be formulated in a bayesian manner as a priori probabilities and incorporated into a racing scheme by making it harder for a favored learner to lose the race. This algorithm should be easy to parallelize. Simply assign one processor per model. If there are less models than processors, then it is probably not even worth racing them. However, there are usually going to be more possible models than processors, in which case whenever a model gets thrown out of the race, its processor gets a new model. Hoeffding's bound was chosen since it is a tight, distribution-free statistical bound. However, it might not be the best bound to use for classification problems. Other tests, such as the f-test, can be used in its place. For a given value of $\delta$ (defining the confidence level at which we are prepared to cut off a competitor from the race) the Bayesian approach cuts off far earlier than the Hoeffding approach. The Bayesian approach achieves its superiority by making stronger assumptions about the distribution of the errors, and so might be expected to be less robust than the almost assumptionless Hoeffding approach. In the experiments we have performed to date the Bayesian method does not seem to converge to the wrong model more easily than the Hoeffding approach, but this is an empirical observation which may not be true for all datasets. Another issue concerns our choice to assume a normal distribution for the errors. In future work it might be more sensible to use a different distribution, such as an exponential or chi-squared. The normal distribution does not take into account the possibility of occasional highly aberrant datapoints (outliers) in the dataset which might have errors very many times greater than the root-mean-square error. An exciting offshoot of this research is a search for an `ideal' collection of models. There is not a single model which is a solution to every problem in the world, but it is possible that a relatively small group of models will cover a large portion of problems. This set of models needs to stretch across the space of possible problems without much overlap. This can be thought of as a basis set of vectors which are orthogonal and span the space. Once we have a basis set of models, then racing is the perfect tool for finding the best model out of this idealized collection since for any given problem, only a few of the models will perform well on it. That is the ideal condition for racing. Finally, there is the danger of cross validation and data mining which we ignored for the most part. The problem of data mining is that if you look at data long enough, you will begin to see patterns even if it is completely random. It is likely that by throwing too many models at the data, we are actually mining it. 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. \renewcommand{\baselinestretch}{1} \bibliography{paper} \bibliographystyle{named} \end{document}