Approximate Nearest Neighbors Methods for Learning and VisionPresentation Abstracts 
Saturday Dec 13 
Description

Talks: 
Vassilis Athitsos Boston University 
Approximate Nearest Neighbor Retrieval Using Euclidean Embeddings Joint work with Stan Sclaroff This presentation describes a general framework for improving the efficiency of approximate nearest neighbor retrieval in spaces with computationally expensive distance measures. Lipschitz embeddings into Euclidean spaces lead to efficient approximations of expensive distance measures, metric or nonmetric. Approximate distances allow efficient identification of a small set of candidates, on which the exact distance measure is used to identify the nearest neighbors. This framework is applied in a system that estimates hand pose in an image by retrieving the most similar matches in a database of over 100,000 hand images. The hand pose of each database image is known, and the pose parameters of the retrieved matches are used as estimates of the hand pose in the query image. The chamfer distance is used as a measure of distance between binary edge images of hands. The computational complexity of the chamfer distance can make it impractical for large databases, but the presented framework is used to achieve efficient retrieval with negligible loss of accuracy. 
Ken Clarkson Bell Labs 
Nearest Neighbors in Metric Spaces Many approaches to nearest neighbor searching exploit specific properties of the problem instance, such as a setting in Euclidean space, or in low dimension. We can also attack the search problem armed only with the distance function and its triangle inequality. The latter approach is sometimes forced on us; it also has the clear advantage of generality, and that generality can imply simplicity. In recent years, some data structures have been found that have provable properties under fairly weak restrictions on the metric space, such as a spherepacking bound. These data structures have relatives that can be seen experimentally to have attractive practical properties: ease of implementation, low space, O(log n) performance in low dimension, and graceful degradation to brute force. I'll sketch these data structures, and some of the associated theorems and experiments. 
Mayur Datar Stanford University 
LocalitySensitive Hashing Scheme Based on pStable Distributions Joint work with Nicole Immorlica, Piotr Indyk and Vahab Mirrokni. The NearestNeighbor (NN) search problem has been extensively studied in the fields of computational geometry and algorithms, resulting in the discovery of many algorithms. However, most of these solutions do not scale with growing number of dimensions, i.e., they suffer from the curse of dimensionality. This is a serious concern for many applications, in the fields of vision and learning, where we often deal with very high dimensional data. Algorithms for solving the approximate nearestneighbor problem are known, that are relatively efficient. One such algorithm, that has been used in numerous applied settings, uses the LocalitySensitive Hashing (LSH) technique. We present a novel localitysensitive hashing scheme for the decision version of the approximate nearestneighbor problem in $l_p^d$ for $p \in (0,2]$, based on $p$stable distributions. In particular, this gives the first known approximate NN algorithm for the case $p <1$. Moreover, unlike earlier schemes, our LSH scheme works directly on points in $R^d$ without embeddings. Consequently, the resulting query time bound is free of large polylogarithmic factors, and the algorithm is simple and easy to implement. For the important case $p=2$ (Euclidean norm), it strictly improves the known exponent of $n$ in the space requirement and query time. 
John Fisher MIT 
On the Risk of the Approximate Nearest
Neighbor Classifier Joint work with Gregory Shakhnarovich and Trevor Darrell The nearest neighbor (NN) classification rule has excellent asymptotic performance, and is known to have good accuracy on finite samples. Unfortunately, the computational complexity makes exact NN search infeasible for large samples and in high dimensions. An appealing alternative is provided by stateoftheart approximate NN search algorithms, which greatly improve on the running time and space complexity of the exact NN search. We analyze the accuracy loss incurred by the classification rule based on approximate nearest neighbor, and report empirical results for a variety of distributions. We explore the relationship between the asymptotic and the finite sample risks of the exact and approximate NN rules, and suggest a model for approximate NN search which leads to a bound on the risk deviation with respect to the exact case. 
Jonathan Goldstein Microsoft Research 
Limitations on the performance and approximation of high dimensional
nearest neighbor searches In this talk, I will discuss recent results concerning the properties of high dimensional nearest neighbor searches in metric spaces. These properties are closely tied to the weak law of large numbers and the central limit theorem, and point to inherent limitations on the performance of high dimensional searches. One can also use these results to make some interesting observations concerning limitations on techniques that perform approximate searches. Finally, I will propose a new approach for evaluating nearest neighbor query processing strategies which takes into account data specific properties. 
Piotr Indyk MIT Computer Science and Artificial Intelligence Lab 
Embedding EarthMover Distance into Normed Spaces Joint work with Nitin Thaper In many applications, the metric defining dissimilarity between two shapes is not induced by a norm. Examples of such metrics include Hausdorff metric or EarthMover Distance. In such cases, the nearest neighbor problem becomes much harder to solve. One approach to solving such problem is to design algorithms for general metric spaces (as in Ken Clarkson's talk). In this talk we describe a different approach, which is as follows. In the first step, we embed a given metric into a normed space; that is, we construct a mapping that given a shape A computes a vector f(A), so that the distance between two shapes A and B is wellapproximated by f(A)f(B). In the second step, we solve the nearest neighbor problem in the normed space. We illustrate this approach by providing theoretical and experimental data for the problem of embedding EarthMover Distance into the L_1 norm. 
Jitendra Malik University of California, Berkley 
Object recognition using locality sensitive hashing of shapemes Joint work with Andrea Frome Scalable approaches to object recognition should be sublinear in the number of categories. We combine the idea of representative shape contexts (Mori, Belongie & Malik) with that of locality sensitive hashing (Indyk & Motwani) to achieve this objective. Shape contexts are histograms of the arrangement of shape points relative to a given point and can be defined in 2d or 3d. Corresponding points on objects in a category will have similar shape contexts; we regard these as instances of the same "shapeme" (cf. phoneme). We compute shape contexts at a few randomly chosen ("representative") points on a query image, and find their nearest neighbors in a stored set of shape contexts for a set of sample points on object models. The model with the smallest combined distances is taken to be the best match. Shape contexts are highdimensional vectors; finding nearest neighbors is done using locality sensitive hashing. We will show results on recognizing vehicles in range scans of scenes using a database of more than 50 vehicles. 
Andrew Moore Carnegie Mellon University 
Computing KNN classifications without finding the KNN Joint work with Ting Liu and Alex Gray In this talk we will discuss algorithms and empirical results in accelerating KNN classifiers in high dimensions without resorting to approximation. Spatial structures such as balltrees and metric trees have frequently used as high dimensional indexes for finding the exact set of knearest neighbors. But for certain classes of high dimensional data they can require more distance computations than a simple linear scan of the data. For machine learning applications there may, however, be some good news about such spatial access methods: when doing a kNN classification we usually do not need to explicitly find the knearest neighbors. Instead we only need to know how many neighbors are from the positive class or, in some cases, which class is in the majority among the knearest neighbors. This talk is about new balltree search algorithms that exploit this distinction. We will show cases from very high dimensional realworld datasets in which finding the kNN using balltrees is slower than a conventional linear scan, but performing kNN classification with these new methods is more than one magnitude faster than a linear scan. We will then speculate on the extent to which approximate kNN classification algorithms can be accelerated with the same insight. Some of the technical content of this talk will also be presented in a poster by Liu, Moore and Gray at the main NIPS conference poster session. More details at http://www.autonlab.org/autonweb/showTopic/13/. 
Stefan Schaal University of Southern California 
Approximate Nearest Neighbor Regression in Very High Dimensions As an alternative to fast nearest neighbor search methods, training data can also be online incorporated in appropriate sufficient statistics and adaptive data structures, such that nearest neighbor predictions can be accelerated by orders of magnitude. This talk will outline such an approach for locally weighted regression, together with some novel Bayesian techniques that allow statistically robust and computationally inexpensive estimation of local linear models in input spaces with thousands of dimension, despite potential irrelevant and redundant inputs. Some application to online learning in humanoid robotics will serve to illustrate the efficiency of the suggested methods. 
Greg Shakhnarovich MIT Computer Science and Artificial Intelligence Lab 
Fast ExampleBased Estimation with ParameterSensitive Hashing Joint work with Paul Viola and Trevor Darrell Examplebased methods are effective for parameter estimation problems when the underlying system is simple or the dimensionality of the input is low. For complex and highdimensional problems such as pose estimation, the number of required examples and the computational complexity rapidly become prohibitively high. We describe a new algorithm that learns a set of hashing functions that efficiently index examples in a way relevant to a particular estimation task, thus essentially embedding the parameter similarity in a Hamming space. Our algorithm extends localitysensitive hashing, a recently developed method to find approximate neighbors in time sublinear in the number of examples. Experiments demonstrate that the resulting algorithm, which we call ParameterSensitive Hashing, can rapidly and accurately estimate the articulated pose of human figures or hands using a very large database. 
Ilan Shimshoni Technion 
Adaptive Mean Shift Based Clustering in High Dimensions Joint work with Bogdan Georgescu and Peter Meer Feature space analysis is the main module in many computer vision tasks. The most popular technique, kmeans clustering, however, has two inherent limitations: the clusters are constrained to be spherically symmetric and their number has to be known a priori. In nonparametric clustering methods, like the one based on mean shift, these limitations are eliminated but the amount of computation becomes prohibitively large as the dimension of the space increases. We exploit a recently proposed approximation technique, localitysensitive hashing (LSH), to reduce the computational complexity of adaptive mean shift. In our implementation of LSH the optimal parameters of the data structure are determined by a pilot learning procedure, and the partitions are data driven. As an application, the performance of mode and kmeans based textons are compared in a texture classification study. 
Lihong Li University of Alberta 
Learning similarity metrics for vision problems Although a number of distance/similarity functions have been proposed for the knearestneighbor algorithms, they have several limitations, including (1) the ad hoc nature, (2) demand for expert knowledge, etc. In order to remove human intervention in the similarity metric design process, we instead used machine learning techniques to learn the metric function automatically. Artificial neural networks (ANN) were used to learn the similarity metrics. The input was attributes of the two data points, and the desired output is the similarity (or distance) between them. Other conventional functions, such as the Euclidean distance, were used for comparison. Test beds include the UCI data sets (e.g., letter recognition), and a realworld adaptive image interpretation system, MR ADORE, which is described in the poster. The experimental results are quite promising. They showed that the machinelearned similarity functions can work better than humandesigned functions, besides their advantages of reducing human intervention. 
Darrin P. Lewis Columbia University 
Regularized Nearest Neighbor Joint work with William S. Noble We describe the regularized nearest neighbor (RNN) algorithm for classification, which balances empirical error against the complexity of the class of functions being estimated. Benefits of the RNN algorithm include its inherent applicability to multiclass problems, its ability to learn a vast class of functions, and its ability to avoid overfitting through the use of capacity control. This work presents the algorithm and an wmpirical study focusing visualizable twodimensional toy problems, which demonstrates that improvement in generalization performance is attainable with RNN. 
Kristen Grauman MIT 
Fast Contour Matching Using Approximate Earth Mover's Distance Weighted graph matching is a good way to align a pair of shapes represented by a set of descriptive local features: the set of correspondences produced by the minimum cost of matching features from one shape to the features of the other often reveals how similar the two shapes are. However, due to the complexity of computing the exact minimum cost matching, previous algorithms could only run efficiently when using a limited number of features per shape, and could not scale to perform retrievals from large databases. We present a contour matching algorithm that quickly computes the minimum weight matching between sets of descriptive local features using a recently introduced lowdistortion embedding of the Earth Mover's Distance (EMD) into a normed space. Given a novel embedded contour, the nearest neighbors in a database of embedded contours are retrieved in sublinear time via approximate nearest neighbor search. We demonstrate our shape matching method on databases of 10,000 images of human figures and 60,000 images of handwritten digits. 