### Approximate Nearest Neighbors Methods for Learning and Vision

Presentation 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 non-metric. 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 sphere-packing 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
Locality-Sensitive Hashing Scheme Based on p-Stable Distributions
Joint work with Nicole Immorlica, Piotr Indyk and Vahab Mirrokni.

The Nearest-Neighbor (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 nearest-neighbor problem are known, that are relatively efficient. One such algorithm, that has been used in numerous applied settings, uses the Locality-Sensitive Hashing (LSH) technique.
We present a novel locality-sensitive hashing scheme for the decision version of the approximate nearest-neighbor 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 state-of-the-art 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 Earth-Mover Distance into Normed Spaces
Joint work with Nitin Thaper

In many applications, the metric defining dis-similarity between two shapes is not induced by a norm. Examples of such metrics include Hausdorff metric or Earth-Mover 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 well-approximated 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 Earth-Mover 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 high-dimensional 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 K-NN classifications without finding the K-NN
Joint work with Ting Liu and Alex Gray

In this talk we will discuss algorithms and empirical results in accelerating K-NN classifiers in high dimensions without resorting to approximation.
Spatial structures such as ball-trees and metric trees have frequently used as high dimensional indexes for finding the exact set of k-nearest 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 k-NN classification we usually do not need to explicitly find the k-nearest 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 k-nearest neighbors. This talk is about new ball-tree search algorithms that exploit this distinction. We will show cases from very high dimensional real-world datasets in which finding the k-NN using ball-trees is slower than a conventional linear scan, but performing k-NN 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 k-NN 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 on-line 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 on-line learning in humanoid robotics will serve to illustrate the efficiency of the suggested methods.
Greg Shakhnarovich
MIT Computer Science and Artificial Intelligence Lab
Fast Example-Based Estimation with Parameter-Sensitive Hashing
Joint work with Paul Viola and Trevor Darrell

Example-based methods are effective for parameter estimation problems when the underlying system is simple or the dimensionality of the input is low. For complex and high-dimensional 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 locality-sensitive 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 Parameter-Sensitive 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, k-means 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, locality-sensitive 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 k-means 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 k-nearest-neighbor 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 real-world adaptive image interpretation system, MR ADORE, which is described in the poster. The experimental results are quite promising. They showed that the machine-learned similarity functions can work better than human-designed 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 multi-class 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 two-dimensional 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 low-distortion 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.