27 September 1993, 3:00, WeH 4601 Three new algorithms for fast, massive-scale cross-validation searches Andrew Moore For many learning control problems it is not clear which, out of an enormous range of possible state and action variables, would be the best combination for the controller to use for the problem at hand. It can be argued that in making this decision the human programmer is biasing a supposedly autonomous system. The family-tree algorithm is an attempt to harness a technique called leave-one-out cross validation to search the combinatoric space of combinations of variables in reasonable time. I will begin by reviewing the essentially brutal but powerful technique of cross-validation, then introduce a technique called Hoeffding Racing (work performed with Oded Maron) to be cleverer about where we assign the computational resources. I'll move on to discuss further extensions which promise to help out even more effectively in the search for families of relevant features. I will then speculate on the relation between this kind of search and what happens in genetic algorithms. Finally, if time permits (which it won't), I will describe how things can be speeded up further still for memory-based learners by means of a new kd-tree algorithm.