nips nips2009 nips2009-198 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Parikshit Ram, Dongryeol Lee, Hua Ouyang, Alexander G. Gray
Abstract: The long-standing problem of efďŹ cient nearest-neighbor (NN) search has ubiquitous applications ranging from astrophysics to MP3 ďŹ ngerprinting to bioinformatics to movie recommendations. As the dimensionality of the dataset increases, exact NN search becomes computationally prohibitive; (1+đ?œ–) distance-approximate NN search can provide large speedups but risks losing the meaning of NN search present in the ranks (ordering) of the distances. This paper presents a simple, practical algorithm allowing the user to, for the ďŹ rst time, directly control the true accuracy of NN search (in terms of ranks) while still achieving the large speedups over exact NN. Experiments on high-dimensional datasets show that our algorithm often achieves faster and more accurate results than the best-known distance-approximate method, with much more stable behavior. 1
Reference: text
sentIndex sentText sentNum sentScore
1 edu Abstract The long-standing problem of efďŹ cient nearest-neighbor (NN) search has ubiquitous applications ranging from astrophysics to MP3 ďŹ ngerprinting to bioinformatics to movie recommendations. [sent-6, score-0.149]
2 As the dimensionality of the dataset increases, exact NN search becomes computationally prohibitive; (1+đ? [sent-7, score-0.32]
3 œ–) distance-approximate NN search can provide large speedups but risks losing the meaning of NN search present in the ranks (ordering) of the distances. [sent-8, score-0.415]
4 This paper presents a simple, practical algorithm allowing the user to, for the ďŹ rst time, directly control the true accuracy of NN search (in terms of ranks) while still achieving the large speedups over exact NN. [sent-9, score-0.323]
5 1 Introduction In this paper, we address the problem of nearest-neighbor (NN) search in large datasets of high dimensionality. [sent-11, score-0.208]
6 NN search has extensive applications in databases [5] and computer vision for image search Further applications abound in machine learning. [sent-18, score-0.298]
7 ‘‘-trees are used for efďŹ cient exact NN search but do not scale better than the na¨ve linear search in sufďŹ ciently high dimensions. [sent-21, score-0.402]
8 Distance-approximate NN (DANN) Äą search, introduced to increase the scalability of NN search, approximates the distance to the NN and any neighbor found within that distance is considered to be “good enoughâ€? [sent-22, score-0.142]
9 Although the DANN search places bounds on the numerical values of the distance to NN, in NN search, distances themselves are not essential; rather the order of the distances of the query to the points in the dataset captures the necessary and sufďŹ cient information [6, 7]. [sent-25, score-0.603]
10 Appending non-informative dimensions to each of the reference points produces higher dimensional datasets of the form (1, 1, 1, 1, 1, . [sent-30, score-0.163]
11 For a ďŹ xed distance approximation, raising the dimension increases the number of points for which the distance to the query (i. [sent-47, score-0.289]
12 However, the ordering (and hence the ranks) of those distances remains the same. [sent-50, score-0.135]
13 The proposed framework, rank-approximate nearestneighbor (RANN) search, approximates the NN in its rank rather than in its distance, thereby making the approximation independent of the distance distribution and only dependent on the ordering of the distances. [sent-51, score-0.266]
14 1 This paper is organized as follows: Section 2 describes the existing methods for exact NN and DANN search and the challenges they face in high dimensions. [sent-52, score-0.253]
15 Section 3 introduces the proposed approach and provides a practical algorithm using stratiďŹ ed sampling with a tree data structure to obtain a user-speciďŹ ed level of rank approximation in Euclidean NN search. [sent-53, score-0.371]
16 Section 4 reports the experiments comparing RANN with exact search and DANN. [sent-54, score-0.226]
17 2 Related Work The problem of NN search is formalized as the following: Problem. [sent-56, score-0.149]
18 1 Exact Search The simplest approach of linear search over đ? [sent-78, score-0.149]
19 Hashing the dataset into buckets is an efďŹ cient technique, but scales only to very low dimensional đ? [sent-82, score-0.157]
20 ‘‘-trees [9], ball trees [10] and metric trees [11] utilize the triangular inequality of the distance metric đ? [sent-87, score-0.242]
21 ‘‘ (commonly the Euclidean distance metric) to prune away parts of the dataset from the computation and answer queries in expected O(log đ? [sent-88, score-0.228]
22 Non-binary cover trees [12] answer queries in theoretically bounded O(log đ? [sent-90, score-0.181]
23 The dual-tree algorithm [13] for NN search also builds a tree on the queries instead of going through them linearly, hence amortizing the cost of search over the queries. [sent-96, score-0.558]
24 2 Nearest Neighbors in High Dimensions The frontier of research in NN methods is high dimensional problems, stemming from common datasets like images and documents to microarray data. [sent-101, score-0.094]
25 But high dimensional data poses an inherent problem for Euclidean NN search as described in the following theorem: Theorem 2. [sent-102, score-0.211]
26 This implies that in high dimensions, the Euclidean distances between uniformly distributed points lie in a small range of continuous values. [sent-136, score-0.134]
27 This hypothesizes that the tree based algorithms perform no better than linear search since these data structures would be unable to employ sufďŹ ciently tight bounds in high dimensions. [sent-137, score-0.324]
28 This prompted interest in approximation of the NN search problem. [sent-139, score-0.176]
29 3 Distance-Approximate Nearest Neighbors The problem of NN search is relaxed in the following form to make it more scalable: Problem. [sent-141, score-0.149]
30 ‘‘-trees, balls trees, and cover trees by modifying the search algorithm to prune more aggressively. [sent-167, score-0.283]
31 This introduces the allowed error while providing some speedup over the exact algorithm [12]. [sent-168, score-0.204]
32 Another approach modiďŹ es the tree data structures to 2 bound error with just one root-to-leaf traversal of the tree, i. [sent-169, score-0.251]
33 ‘‘-trees or ball-trees are modiďŹ ed to share points near their boundaries, forming spill trees [14]. [sent-174, score-0.155]
34 They provide 1-2 orders of magnitude speedup in moderately large datasets with suitable đ? [sent-180, score-0.116]
35 However, they can be used in combination with the assumption that high dimensional data actually lies on a lower dimensional subspace. [sent-184, score-0.097]
36 Hybrid spill trees [14] build spill trees on the randomly projected data to obtain signiďŹ cant speedups. [sent-186, score-0.23]
37 Locality sensitive hashing [18, 19] hashes the data into a lower dimensional buckets using hash functions which guarantee that “close� [sent-187, score-0.092]
38 points are hashed into the same bucket with high probability and “farther apart� [sent-188, score-0.125]
39 points are hashed into the same bucket with low probability. [sent-189, score-0.12]
40 The exact treebased algorithms failed to be efďŹ cient because many datasets encountered in practice suffered the same concentration of pairwise distances. [sent-197, score-0.109]
41 Using DANN in such a situation leads to the loss of the ordering information of the pairwise distances which is essential for NN search [6]. [sent-198, score-0.259]
42 3 Rank Approximation To approximate the NN rank, we formulate and relax NN search in the following way: Problem. [sent-202, score-0.176]
43 ‘ } be the set of distances between the query and all the points in the dataset đ? [sent-220, score-0.343]
44 The rank-approximation of NN search would then be to efďŹ ciently ďŹ nd a point đ? [sent-255, score-0.149]
45 RANN search may use any order statistics of the population đ? [sent-269, score-0.202]
46 ›ź is computed using binary search over the range (1 + đ? [sent-374, score-0.149]
47 ‘†, parts of the tree would be pruned away for the query đ? [sent-390, score-0.361]
48 ‘† be in the form of a binary tree (say đ? [sent-394, score-0.148]
49 ‘Ÿ points respectively in the left and right child of the root node đ? [sent-462, score-0.179]
50 The following theorem provides a way to decide how much to sample from a particular node, subsequently providing a lower bound on the number of samples required from the unpruned part of the tree without violating Eq. [sent-468, score-0.248]
51 ‘‘tree since the pruned part does not add to the computation in the exact tree based algorithms. [sent-575, score-0.277]
52 ‘ž in a tree, most of the computation in the traversal involves computing the distance of the query đ? [sent-578, score-0.267]
53 The NN candidate in that leaf is computed using the linear search (C OMPUTE B RUTE NN subroutine in Fig. [sent-621, score-0.235]
54 The traversal of the exact algorithm in the tree is illustrated in Fig. [sent-623, score-0.309]
55 To approximate the computation by sampling, traversal down the tree is stopped at a node which can be summarized with a small number of samples (below a certain threshold M AX S AMPLES). [sent-625, score-0.368]
56 If a node is summarizable within the desired error bounds (decided by the C ANA PPROX IMATE subroutine in Fig. [sent-629, score-0.201]
57 2), required number of points are sampled from such a node and the nearest neighbor candidate is computed from among them using linear search (C OMPUTE A PPROX NN subroutine of Fig. [sent-630, score-0.501]
58 ‘† is stored as a binary tree rooted at đ? [sent-636, score-0.17]
59 During the search, if a leaf node is reached (since the tree is rarely balanced), the exact NN candidate is computed. [sent-648, score-0.359]
60 In case a non-leaf node cannot be approximated, the child node closer to the query is always traversed ďŹ rst. [sent-649, score-0.428]
61 4 Figure 1: The traversal paths of the exact and the rank-approximate algorithm in a đ? [sent-667, score-0.161]
62 ‘…)): Then number of points required to be sampled from the node is at least ⌈đ? [sent-701, score-0.185]
63 However, since this node is pruned, we ignore these points. [sent-704, score-0.104]
64 ‘…)): In this subroutine, linear search is used to ďŹ nd the NN candidate. [sent-708, score-0.149]
65 ‘…âˆŁ samples are made and linear search is performed over them. [sent-718, score-0.176]
66 2 can be extended to the dual tree algorithm in case of O(đ? [sent-733, score-0.198]
67 The dual tree RANN algorithm (DTR ANK A PPROX NN(đ? [sent-735, score-0.198]
68 Even though the queries do not share samples from the reference set, when a query node of the query tree prunes a reference node, that reference node is pruned for all the queries in that query node simultaneously. [sent-745, score-1.239]
69 4 Experiments and Results A meaningful value for the rank error đ? [sent-747, score-0.193]
70 should be relative to the size of the reference dataset đ? [sent-749, score-0.104]
71 Although the value of M AX S AMPLES for maximum speedup can be obtained by cross-validation, for practical purposes, any low value (≈ 20-30) sufďŹ ces well, and this is what is used in the experiments. [sent-760, score-0.106]
72 1 Comparisons with Exact Search The speedups of the exact dual-tree NN algorithm and the approximate tree-based algorithm over the linear search algorithm is computed and compared. [sent-762, score-0.394]
73 ‘„ Figure 2: Single tree (STR ANK A PPROX NN) and dual tree (DTR ANK A PPROX NN) algorithms and subroutines for RANN search for a query đ? [sent-1108, score-0.634]
74 ‘„) Different datasets drawn for the UCI repository (Bio dataset 300kĂ—74, Corel dataset 40kĂ—32, Covertype dataset 600kĂ—55, Phy dataset 150kĂ—78)[21], MN IST handwritten digit recognition dataset (60kĂ—784)[22] and the Isomap “imagesâ€? [sent-1122, score-0.407]
75 is a synthetic dataset of points uniform randomly sampled from a unit ball (1mĂ—20). [sent-1125, score-0.136]
76 This dataset is used to show that even in the absence of a lower-dimensional subspace, RANN is able to get signiďŹ cant speedups over exact methods for relatively low errors. [sent-1126, score-0.249]
77 For each dataset, the NN of every point in the dataset is found in the exact case, and (1 + ⌈đ? [sent-1127, score-0.152]
78 ‘ ⌉)-rank-approximate NN of every point in the dataset is found in the approximate case. [sent-1129, score-0.102]
79 œ€ (high accuracy setting), the RANN algorithm is signiďŹ cantly more scalable than the exact algorithms for all the datasets. [sent-1133, score-0.123]
80 Note that for some of the datasets, the low values of approximation used in the experiments are equivalent to zero rank error (which is the exact case), hence are equally efďŹ cient as the exact algorithm. [sent-1134, score-0.421]
81 95 4 speedup over linear search 10 3 10 2 10 1 10 0 10 bio corel covtype images mnist phy urand Figure 3: Speedups(logscale on the Y-axis) over the linear search algorithm while ďŹ nding the NN in the exact case or (1 + đ? [sent-1139, score-0.605]
82 The ďŹ rst(white) bar in each dataset in the X-axis is the speedup of exact dual tree NN algorithm, and the subsequent(dark) bars are the speedups of the approximate algorithm with increasing approximation. [sent-1150, score-0.516]
83 2 Comparison with Distance-Approximate Search In the case of the different forms of approximation, the average rank errors and the maximum rank errors achieved in comparable retrieval times are considered for comparison. [sent-1152, score-0.357]
84 The rank errors are compared since any method with relatively lower rank error will obviously have relatively lower distance error. [sent-1153, score-0.389]
85 Subsets of two datasets known to have a lower-dimensional embedding are used for this experiment - Layout Histogram (10kĂ—30)[21] and MN IST dataset (10kĂ—784)[22]. [sent-1155, score-0.107]
86 The approximate NN of every point in the dataset is found with different levels of approximation for both the algorithms. [sent-1156, score-0.129]
87 The average rank error and maximum rank error is computed for each of the approximation levels. [sent-1157, score-0.433]
88 For our algorithm, we increased the rank error and observed a corresponding decrease in the retrieval time. [sent-1158, score-0.226]
89 To obtain the best retrieval times with low rank error, we ďŹ xed one parameter and changed the other two to obtain a decrease in runtime and did this for many values of the ďŹ rst parameter. [sent-1160, score-0.207]
90 The results show that even in the presence of a lower-dimensional embedding of the data, the rank errors for a given retrieval time are comparable in both the approximate algorithms. [sent-1164, score-0.212]
91 The advantage of the rank-approximate algorithm is that the rank error can be directly controlled, whereas in LSH, tweaking in the cross-product of its three parameters is typically required to obtain the best ranks for a particular retrieval time. [sent-1165, score-0.31]
92 Another advantage of the tree-based algorithm for RANN is the fact that even though the maximum error is bounded only with a probability, the actual maximum error is not much worse than the allowed maximum rank error since a tree is used. [sent-1166, score-0.505]
93 In the case of LSH, at times, the actual maximum rank error is extremely large, corresponding to LSH returning points which are very far from being the NN. [sent-1167, score-0.253]
94 5 Conclusion We have proposed a new form of approximate algorithm for unscalable NN search instances by controlling the true error of NN search (i. [sent-1184, score-0.417]
95 This allows approximate NN search to retain meaning in high dimensional datasets even in the absence of a lower-dimensional embedding. [sent-1187, score-0.27]
96 The proposed algorithm for approximate Euclidean NN has been shown to scale much better than the exact algorithm even for low levels of approximation even when the true dimension of the data is relatively high. [sent-1188, score-0.197]
97 When compared with the popular DANN method (LSH), it is shown to be comparably efďŹ cient in terms of the average rank error even in the presence of a lower dimensional subspace of the data (a fact which is crucial for the performance of the distance-approximate method). [sent-1189, score-0.247]
98 Moreover, the use of spatial-partitioning tree in the algorithm provides stability to the method by clamping the actual maximum error to be within a reasonable rank threshold unlike the distance-approximate method. [sent-1190, score-0.383]
99 However, note that the proposed algorithm still beneďŹ ts from the ability of the underlying tree data structure to bound distances. [sent-1191, score-0.17]
100 Regardless, RANN provides a new paradigm for NN search which is comparably efďŹ cient to the existing methods of distance-approximation and allows the user to directly control the true accuracy which is present in ordering of the neighbors. [sent-1193, score-0.211]
wordName wordTfidf (topN-words)
[('nn', 0.646), ('ompute', 0.265), ('rann', 0.265), ('pprox', 0.232), ('dtrann', 0.199), ('query', 0.161), ('rank', 0.152), ('search', 0.149), ('tree', 0.148), ('lsh', 0.146), ('dann', 0.132), ('rute', 0.132), ('node', 0.104), ('eaf', 0.099), ('ank', 0.093), ('exact', 0.077), ('dataset', 0.075), ('speedups', 0.075), ('strati', 0.072), ('distances', 0.067), ('amples', 0.066), ('ana', 0.066), ('strann', 0.066), ('trees', 0.065), ('queries', 0.065), ('speedup', 0.064), ('traversal', 0.062), ('nearest', 0.057), ('subroutine', 0.056), ('neighbor', 0.054), ('population', 0.053), ('pruned', 0.052), ('str', 0.05), ('pproximate', 0.05), ('spill', 0.05), ('else', 0.045), ('distance', 0.044), ('dtr', 0.043), ('ordering', 0.043), ('ranks', 0.042), ('error', 0.041), ('ist', 0.04), ('points', 0.04), ('ree', 0.035), ('euclidean', 0.035), ('child', 0.035), ('dimensional', 0.035), ('metric', 0.034), ('ize', 0.033), ('phy', 0.033), ('sedransk', 0.033), ('strata', 0.033), ('unpruned', 0.033), ('urand', 0.033), ('retrieval', 0.033), ('ax', 0.032), ('hashing', 0.032), ('datasets', 0.032), ('leaf', 0.03), ('layout', 0.029), ('reference', 0.029), ('hashed', 0.029), ('unscalable', 0.029), ('bucket', 0.029), ('ample', 0.029), ('bio', 0.029), ('dual', 0.028), ('approximate', 0.027), ('approximation', 0.027), ('cover', 0.027), ('dimensions', 0.027), ('samples', 0.027), ('corel', 0.027), ('high', 0.027), ('mn', 0.025), ('buckets', 0.025), ('hence', 0.025), ('answer', 0.024), ('computations', 0.024), ('scalable', 0.024), ('traversed', 0.024), ('mnist', 0.022), ('indyk', 0.022), ('rooted', 0.022), ('algorithm', 0.022), ('sampling', 0.022), ('low', 0.022), ('farther', 0.022), ('sampled', 0.021), ('histogram', 0.021), ('maximum', 0.02), ('success', 0.02), ('required', 0.02), ('moderately', 0.02), ('prune', 0.02), ('sample', 0.02), ('comparably', 0.019), ('dimensionality', 0.019), ('gray', 0.019), ('curse', 0.019)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000006 198 nips-2009-Rank-Approximate Nearest Neighbor Search: Retaining Meaning and Speed in High Dimensions
Author: Parikshit Ram, Dongryeol Lee, Hua Ouyang, Alexander G. Gray
Abstract: The long-standing problem of efďŹ cient nearest-neighbor (NN) search has ubiquitous applications ranging from astrophysics to MP3 ďŹ ngerprinting to bioinformatics to movie recommendations. As the dimensionality of the dataset increases, exact NN search becomes computationally prohibitive; (1+đ?œ–) distance-approximate NN search can provide large speedups but risks losing the meaning of NN search present in the ranks (ordering) of the distances. This paper presents a simple, practical algorithm allowing the user to, for the ďŹ rst time, directly control the true accuracy of NN search (in terms of ranks) while still achieving the large speedups over exact NN. Experiments on high-dimensional datasets show that our algorithm often achieves faster and more accurate results than the best-known distance-approximate method, with much more stable behavior. 1
2 0.1961055 139 nips-2009-Linear-time Algorithms for Pairwise Statistical Problems
Author: Parikshit Ram, Dongryeol Lee, William March, Alexander G. Gray
Abstract: Several key computational bottlenecks in machine learning involve pairwise distance computations, including all-nearest-neighbors (ďŹ nding the nearest neighbor(s) for each point, e.g. in manifold learning) and kernel summations (e.g. in kernel density estimation or kernel machines). We consider the general, bichromatic case for these problems, in addition to the scientiďŹ c problem of N-body simulation. In this paper we show for the ďŹ rst time O(đ?‘ ) worst case runtimes for practical algorithms for these problems based on the cover tree data structure [1]. 1
3 0.098525316 74 nips-2009-Efficient Bregman Range Search
Author: Lawrence Cayton
Abstract: We develop an algorithm for efficient range search when the notion of dissimilarity is given by a Bregman divergence. The range search task is to return all points in a potentially large database that are within some specified distance of a query. It arises in many learning algorithms such as locally-weighted regression, kernel density estimation, neighborhood graph-based algorithms, and in tasks like outlier detection and information retrieval. In metric spaces, efficient range search-like algorithms based on spatial data structures have been deployed on a variety of statistical tasks. Here we describe an algorithm for range search for an arbitrary Bregman divergence. This broad class of dissimilarity measures includes the relative entropy, Mahalanobis distance, Itakura-Saito divergence, and a variety of matrix divergences. Metric methods cannot be directly applied since Bregman divergences do not in general satisfy the triangle inequality. We derive geometric properties of Bregman divergences that yield an efficient algorithm for range search based on a recently proposed space decomposition for Bregman divergences. 1
4 0.088673152 190 nips-2009-Polynomial Semantic Indexing
Author: Bing Bai, Jason Weston, David Grangier, Ronan Collobert, Kunihiko Sadamasa, Yanjun Qi, Corinna Cortes, Mehryar Mohri
Abstract: We present a class of nonlinear (polynomial) models that are discriminatively trained to directly map from the word content in a query-document or documentdocument pair to a ranking score. Dealing with polynomial models on word features is computationally challenging. We propose a low-rank (but diagonal preserving) representation of our polynomial models to induce feasible memory and computation requirements. We provide an empirical study on retrieval tasks based on Wikipedia documents, where we obtain state-of-the-art performance while providing realistically scalable methods. 1
5 0.088537015 135 nips-2009-Learning to Hash with Binary Reconstructive Embeddings
Author: Brian Kulis, Trevor Darrell
Abstract: Fast retrieval methods are increasingly critical for many large-scale analysis tasks, and there have been several recent methods that attempt to learn hash functions for fast and accurate nearest neighbor searches. In this paper, we develop an algorithm for learning hash functions based on explicitly minimizing the reconstruction error between the original distances and the Hamming distances of the corresponding binary embeddings. We develop a scalable coordinate-descent algorithm for our proposed hashing objective that is able to efficiently learn hash functions in a variety of settings. Unlike existing methods such as semantic hashing and spectral hashing, our method is easily kernelized and does not require restrictive assumptions about the underlying distribution of the data. We present results over several domains to demonstrate that our method outperforms existing state-of-the-art techniques. 1
6 0.086305335 199 nips-2009-Ranking Measures and Loss Functions in Learning to Rank
7 0.084305011 142 nips-2009-Locality-sensitive binary codes from shift-invariant kernels
8 0.08056853 129 nips-2009-Learning a Small Mixture of Trees
9 0.078768089 166 nips-2009-Noisy Generalized Binary Search
10 0.071796469 241 nips-2009-The 'tree-dependent components' of natural scenes are edge filters
11 0.064429447 127 nips-2009-Learning Label Embeddings for Nearest-Neighbor Multi-class Classification with an Application to Speech Recognition
12 0.063188531 208 nips-2009-Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization
13 0.062542491 223 nips-2009-Sparse Metric Learning via Smooth Optimization
14 0.061602872 48 nips-2009-Bootstrapping from Game Tree Search
15 0.058654275 202 nips-2009-Regularized Distance Metric Learning:Theory and Algorithm
16 0.058168504 82 nips-2009-Entropic Graph Regularization in Non-Parametric Semi-Supervised Classification
17 0.057921272 31 nips-2009-An LP View of the M-best MAP problem
18 0.056398392 147 nips-2009-Matrix Completion from Noisy Entries
19 0.054844622 87 nips-2009-Exponential Family Graph Matching and Ranking
20 0.054100338 255 nips-2009-Variational Inference for the Nested Chinese Restaurant Process
topicId topicWeight
[(0, -0.139), (1, 0.063), (2, -0.043), (3, -0.001), (4, -0.018), (5, -0.036), (6, -0.156), (7, 0.041), (8, 0.014), (9, -0.076), (10, -0.079), (11, 0.009), (12, 0.132), (13, 0.178), (14, 0.03), (15, -0.14), (16, 0.13), (17, 0.117), (18, -0.025), (19, 0.039), (20, 0.011), (21, 0.024), (22, 0.096), (23, 0.1), (24, 0.106), (25, -0.122), (26, -0.035), (27, 0.061), (28, 0.107), (29, -0.033), (30, 0.003), (31, 0.028), (32, -0.019), (33, -0.019), (34, -0.099), (35, -0.028), (36, -0.082), (37, -0.059), (38, 0.043), (39, -0.001), (40, -0.011), (41, 0.038), (42, 0.033), (43, -0.013), (44, -0.051), (45, -0.086), (46, -0.044), (47, 0.006), (48, 0.041), (49, -0.025)]
simIndex simValue paperId paperTitle
same-paper 1 0.95786607 198 nips-2009-Rank-Approximate Nearest Neighbor Search: Retaining Meaning and Speed in High Dimensions
Author: Parikshit Ram, Dongryeol Lee, Hua Ouyang, Alexander G. Gray
Abstract: The long-standing problem of efďŹ cient nearest-neighbor (NN) search has ubiquitous applications ranging from astrophysics to MP3 ďŹ ngerprinting to bioinformatics to movie recommendations. As the dimensionality of the dataset increases, exact NN search becomes computationally prohibitive; (1+đ?œ–) distance-approximate NN search can provide large speedups but risks losing the meaning of NN search present in the ranks (ordering) of the distances. This paper presents a simple, practical algorithm allowing the user to, for the ďŹ rst time, directly control the true accuracy of NN search (in terms of ranks) while still achieving the large speedups over exact NN. Experiments on high-dimensional datasets show that our algorithm often achieves faster and more accurate results than the best-known distance-approximate method, with much more stable behavior. 1
2 0.76781029 139 nips-2009-Linear-time Algorithms for Pairwise Statistical Problems
Author: Parikshit Ram, Dongryeol Lee, William March, Alexander G. Gray
Abstract: Several key computational bottlenecks in machine learning involve pairwise distance computations, including all-nearest-neighbors (ďŹ nding the nearest neighbor(s) for each point, e.g. in manifold learning) and kernel summations (e.g. in kernel density estimation or kernel machines). We consider the general, bichromatic case for these problems, in addition to the scientiďŹ c problem of N-body simulation. In this paper we show for the ďŹ rst time O(đ?‘ ) worst case runtimes for practical algorithms for these problems based on the cover tree data structure [1]. 1
3 0.61161989 74 nips-2009-Efficient Bregman Range Search
Author: Lawrence Cayton
Abstract: We develop an algorithm for efficient range search when the notion of dissimilarity is given by a Bregman divergence. The range search task is to return all points in a potentially large database that are within some specified distance of a query. It arises in many learning algorithms such as locally-weighted regression, kernel density estimation, neighborhood graph-based algorithms, and in tasks like outlier detection and information retrieval. In metric spaces, efficient range search-like algorithms based on spatial data structures have been deployed on a variety of statistical tasks. Here we describe an algorithm for range search for an arbitrary Bregman divergence. This broad class of dissimilarity measures includes the relative entropy, Mahalanobis distance, Itakura-Saito divergence, and a variety of matrix divergences. Metric methods cannot be directly applied since Bregman divergences do not in general satisfy the triangle inequality. We derive geometric properties of Bregman divergences that yield an efficient algorithm for range search based on a recently proposed space decomposition for Bregman divergences. 1
4 0.50018257 48 nips-2009-Bootstrapping from Game Tree Search
Author: Joel Veness, David Silver, Alan Blair, William W. Cohen
Abstract: In this paper we introduce a new algorithm for updating the parameters of a heuristic evaluation function, by updating the heuristic towards the values computed by an alpha-beta search. Our algorithm differs from previous approaches to learning from search, such as Samuel’s checkers player and the TD-Leaf algorithm, in two key ways. First, we update all nodes in the search tree, rather than a single node. Second, we use the outcome of a deep search, instead of the outcome of a subsequent search, as the training signal for the evaluation function. We implemented our algorithm in a chess program Meep, using a linear heuristic function. After initialising its weight vector to small random values, Meep was able to learn high quality weights from self-play alone. When tested online against human opponents, Meep played at a master level, the best performance of any chess program with a heuristic learned entirely from self-play. 1
5 0.49158299 166 nips-2009-Noisy Generalized Binary Search
Author: Robert Nowak
Abstract: This paper addresses the problem of noisy Generalized Binary Search (GBS). GBS is a well-known greedy algorithm for determining a binary-valued hypothesis through a sequence of strategically selected queries. At each step, a query is selected that most evenly splits the hypotheses under consideration into two disjoint subsets, a natural generalization of the idea underlying classic binary search. GBS is used in many applications, including fault testing, machine diagnostics, disease diagnosis, job scheduling, image processing, computer vision, and active learning. In most of these cases, the responses to queries can be noisy. Past work has provided a partial characterization of GBS, but existing noise-tolerant versions of GBS are suboptimal in terms of query complexity. This paper presents an optimal algorithm for noisy GBS and demonstrates its application to learning multidimensional threshold functions. 1
6 0.47514048 190 nips-2009-Polynomial Semantic Indexing
7 0.47495577 142 nips-2009-Locality-sensitive binary codes from shift-invariant kernels
8 0.47158358 249 nips-2009-Tracking Dynamic Sources of Malicious Activity at Internet Scale
9 0.46042868 91 nips-2009-Fast, smooth and adaptive regression in metric spaces
10 0.42779848 135 nips-2009-Learning to Hash with Binary Reconstructive Embeddings
11 0.42338556 32 nips-2009-An Online Algorithm for Large Scale Image Similarity Learning
12 0.39416826 234 nips-2009-Streaming k-means approximation
13 0.38345659 255 nips-2009-Variational Inference for the Nested Chinese Restaurant Process
14 0.38235265 241 nips-2009-The 'tree-dependent components' of natural scenes are edge filters
15 0.37850973 129 nips-2009-Learning a Small Mixture of Trees
16 0.37805489 24 nips-2009-Adapting to the Shifting Intent of Search Queries
17 0.36606055 87 nips-2009-Exponential Family Graph Matching and Ranking
18 0.33656088 191 nips-2009-Positive Semidefinite Metric Learning with Boosting
19 0.32896349 197 nips-2009-Randomized Pruning: Efficiently Calculating Expectations in Large Dynamic Programs
20 0.32032904 136 nips-2009-Learning to Rank by Optimizing NDCG Measure
topicId topicWeight
[(24, 0.035), (25, 0.051), (35, 0.072), (36, 0.101), (39, 0.047), (48, 0.348), (58, 0.075), (61, 0.017), (71, 0.022), (75, 0.013), (81, 0.017), (86, 0.091), (91, 0.011)]
simIndex simValue paperId paperTitle
same-paper 1 0.74647939 198 nips-2009-Rank-Approximate Nearest Neighbor Search: Retaining Meaning and Speed in High Dimensions
Author: Parikshit Ram, Dongryeol Lee, Hua Ouyang, Alexander G. Gray
Abstract: The long-standing problem of efďŹ cient nearest-neighbor (NN) search has ubiquitous applications ranging from astrophysics to MP3 ďŹ ngerprinting to bioinformatics to movie recommendations. As the dimensionality of the dataset increases, exact NN search becomes computationally prohibitive; (1+đ?œ–) distance-approximate NN search can provide large speedups but risks losing the meaning of NN search present in the ranks (ordering) of the distances. This paper presents a simple, practical algorithm allowing the user to, for the ďŹ rst time, directly control the true accuracy of NN search (in terms of ranks) while still achieving the large speedups over exact NN. Experiments on high-dimensional datasets show that our algorithm often achieves faster and more accurate results than the best-known distance-approximate method, with much more stable behavior. 1
2 0.72135979 82 nips-2009-Entropic Graph Regularization in Non-Parametric Semi-Supervised Classification
Author: Amarnag Subramanya, Jeff A. Bilmes
Abstract: We prove certain theoretical properties of a graph-regularized transductive learning objective that is based on minimizing a Kullback-Leibler divergence based loss. These include showing that the iterative alternating minimization procedure used to minimize the objective converges to the correct solution and deriving a test for convergence. We also propose a graph node ordering algorithm that is cache cognizant and leads to a linear speedup in parallel computations. This ensures that the algorithm scales to large data sets. By making use of empirical evaluation on the TIMIT and Switchboard I corpora, we show this approach is able to outperform other state-of-the-art SSL approaches. In one instance, we solve a problem on a 120 million node graph. 1
3 0.62510848 77 nips-2009-Efficient Match Kernel between Sets of Features for Visual Recognition
Author: Liefeng Bo, Cristian Sminchisescu
Abstract: In visual recognition, the images are frequently modeled as unordered collections of local features (bags). We show that bag-of-words representations commonly used in conjunction with linear classifiers can be viewed as special match kernels, which count 1 if two local features fall into the same regions partitioned by visual words and 0 otherwise. Despite its simplicity, this quantization is too coarse, motivating research into the design of match kernels that more accurately measure the similarity between local features. However, it is impractical to use such kernels for large datasets due to their significant computational cost. To address this problem, we propose efficient match kernels (EMK) that map local features to a low dimensional feature space and average the resulting vectors to form a setlevel feature. The local feature maps are learned so their inner products preserve, to the best possible, the values of the specified kernel function. Classifiers based on EMK are linear both in the number of images and in the number of local features. We demonstrate that EMK are extremely efficient and achieve the current state of the art in three difficult computer vision datasets: Scene-15, Caltech-101 and Caltech-256. 1
4 0.58405846 215 nips-2009-Sensitivity analysis in HMMs with application to likelihood maximization
Author: Pierre-arnaud Coquelin, Romain Deguest, Rémi Munos
Abstract: This paper considers a sensitivity analysis in Hidden Markov Models with continuous state and observation spaces. We propose an Infinitesimal Perturbation Analysis (IPA) on the filtering distribution with respect to some parameters of the model. We describe a methodology for using any algorithm that estimates the filtering density, such as Sequential Monte Carlo methods, to design an algorithm that estimates its gradient. The resulting IPA estimator is proven to be asymptotically unbiased, consistent and has computational complexity linear in the number of particles. We consider an application of this analysis to the problem of identifying unknown parameters of the model given a sequence of observations. We derive an IPA estimator for the gradient of the log-likelihood, which may be used in a gradient method for the purpose of likelihood maximization. We illustrate the method with several numerical experiments.
5 0.47911286 135 nips-2009-Learning to Hash with Binary Reconstructive Embeddings
Author: Brian Kulis, Trevor Darrell
Abstract: Fast retrieval methods are increasingly critical for many large-scale analysis tasks, and there have been several recent methods that attempt to learn hash functions for fast and accurate nearest neighbor searches. In this paper, we develop an algorithm for learning hash functions based on explicitly minimizing the reconstruction error between the original distances and the Hamming distances of the corresponding binary embeddings. We develop a scalable coordinate-descent algorithm for our proposed hashing objective that is able to efficiently learn hash functions in a variety of settings. Unlike existing methods such as semantic hashing and spectral hashing, our method is easily kernelized and does not require restrictive assumptions about the underlying distribution of the data. We present results over several domains to demonstrate that our method outperforms existing state-of-the-art techniques. 1
6 0.46811545 104 nips-2009-Group Sparse Coding
7 0.4643676 30 nips-2009-An Integer Projected Fixed Point Method for Graph Matching and MAP Inference
8 0.46365431 167 nips-2009-Non-Parametric Bayesian Dictionary Learning for Sparse Image Representations
9 0.46363053 137 nips-2009-Learning transport operators for image manifolds
10 0.45816058 70 nips-2009-Discriminative Network Models of Schizophrenia
11 0.45811158 158 nips-2009-Multi-Label Prediction via Sparse Infinite CCA
12 0.45794514 139 nips-2009-Linear-time Algorithms for Pairwise Statistical Problems
13 0.45667973 3 nips-2009-AUC optimization and the two-sample problem
14 0.45629948 119 nips-2009-Kernel Methods for Deep Learning
15 0.45596451 169 nips-2009-Nonlinear Learning using Local Coordinate Coding
16 0.45551699 145 nips-2009-Manifold Embeddings for Model-Based Reinforcement Learning under Partial Observability
17 0.45548275 191 nips-2009-Positive Semidefinite Metric Learning with Boosting
18 0.45437688 87 nips-2009-Exponential Family Graph Matching and Ranking
19 0.45411307 132 nips-2009-Learning in Markov Random Fields using Tempered Transitions
20 0.45400807 100 nips-2009-Gaussian process regression with Student-t likelihood