`N-Body' Problems in Statistical Learning

We present efficient algorithms for all-point-pairs problems, or'N(cid:173) body '-like problems, which are ubiquitous in statistical learning. We focus on six examples, including nearest-neighbor classification, kernel density estimation, outlier detection, and the two-point correlation. These include any problem which abstractly requires a comparison of each of the N points in a dataset with each other point and would naively be solved using N 2 distance computations. In practice N is often large enough to make this infeasible. We present a suite of new geometric t echniques which are applicable in principle to any'N-body' computation including large-scale mixtures of Gaussians, RBF neural networks, and HMM's.