nips nips2011 nips2011-64 knowledge-graph by maker-knowledge-mining

64 nips-2011-Convergent Bounds on the Euclidean Distance

Source: pdf

Author: Yoonho Hwang, Hee-kap Ahn

Abstract: Given a set V of n vectors in d-dimensional space, we provide an efﬁcient method for computing quality upper and lower bounds of the Euclidean distances between a pair of vectors in V . For this purpose, we deﬁne a distance measure, called the MS-distance, by using the mean and the standard deviation values of vectors in V . Once we compute the mean and the standard deviation values of vectors in V in O(dn) time, the MS-distance provides upper and lower bounds of Euclidean distance between any pair of vectors in V in constant time. Furthermore, these bounds can be reﬁned further in such a way to converge monotonically to the exact Euclidean distance within d reﬁnement steps. An analysis on a random sequence of reﬁnement steps shows that the MS-distance provides very tight bounds in only a few reﬁnement steps. The MS-distance can be used to various applications where the Euclidean distance is used to measure the proximity or similarity between objects. We provide experimental results on the nearest and the farthest neighbor searches. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 kr Abstract Given a set V of n vectors in d-dimensional space, we provide an efﬁcient method for computing quality upper and lower bounds of the Euclidean distances between a pair of vectors in V . [sent-3, score-0.395]

2 For this purpose, we deﬁne a distance measure, called the MS-distance, by using the mean and the standard deviation values of vectors in V . [sent-4, score-0.208]

3 Once we compute the mean and the standard deviation values of vectors in V in O(dn) time, the MS-distance provides upper and lower bounds of Euclidean distance between any pair of vectors in V in constant time. [sent-5, score-0.501]

4 Furthermore, these bounds can be reﬁned further in such a way to converge monotonically to the exact Euclidean distance within d reﬁnement steps. [sent-6, score-0.249]

5 An analysis on a random sequence of reﬁnement steps shows that the MS-distance provides very tight bounds in only a few reﬁnement steps. [sent-7, score-0.105]

6 The MS-distance can be used to various applications where the Euclidean distance is used to measure the proximity or similarity between objects. [sent-8, score-0.236]

7 We provide experimental results on the nearest and the farthest neighbor searches. [sent-9, score-0.399]

8 1 Introduction The Euclidean distance between two vectors x and y in d-dimensional space is a typical distance measure that reﬂects their proximity in the space. [sent-10, score-0.402]

9 Measuring the Euclidean distance is a fundamental operation in computer science, including the areas of database, computational geometry, computer vision and computer graphics. [sent-11, score-0.099]

10 In machine learning, the Euclidean distance, denoted by dist(x, y), or it’s variations(for example, e||x−y|| ) are widely used to measure data similarity for clustering [1], classiﬁcation [2] and so on. [sent-12, score-0.05]

11 Given two sets X and Y of vectors in d-dimensional space, our goal is to ﬁnd a pair (x, y), for x ∈ X and y ∈ Y , such that dist(x, y) is the optimum (minimum or maximum) over all such pairs. [sent-14, score-0.113]

12 For the nearest or farthest neighbor searches, X is the set consisting of a single query point while Y consists of all candidate data points. [sent-15, score-0.451]

13 In d dimensional space, a single distance computation already takes O(d) time, thus the cost for ﬁnding the nearest or farthest neighbor becomes O(dnm) time, where n and m are the cardinalities of X and Y , respectively. [sent-18, score-0.515]

14 1 If we restrict ourselves to the nearest neighbor search, some methods using space partitioning trees such as KD-tree [4], R-tree [5], or their variations have been widely used. [sent-23, score-0.291]

15 Recently, cover tree [6] has been used for high dimensional nearest neighbor search, but its construction time increases drastically as the dimension increases [7]. [sent-25, score-0.383]

16 One of such methods is to compute a distance bound using the inner product approximation [8]. [sent-27, score-0.153]

17 Another method is to compute a distance bound using bitwise operations [9]. [sent-29, score-0.164]

18 In this paper, we deﬁne a distance measure, called the MS-distance, by using the mean and the standard deviation values of vectors in V . [sent-33, score-0.208]

19 Once we compute the mean and the standard deviation values of vectors in V in O(dn) time, the MS-distance provides tight upper and lower bounds of Euclidean distance between any pair of vectors in V in constant time. [sent-34, score-0.534]

20 Furthermore, these bounds can be reﬁned further in such a way to converge monotonically to the exact Euclidean distance within d reﬁnement steps. [sent-35, score-0.249]

21 We provide an analysis on a random sequence of k reﬁnement steps for 0 ≤ k ≤ d, which shows a good expectation on the lower and upper bounds. [sent-37, score-0.091]

22 This can justify that the MS-distance provides very tight bounds in a few reﬁnement steps of a typical sequence. [sent-38, score-0.146]

23 The MS-distance can be used to various applications where the Euclidean distance is a measure for proximity or similarity between objects. [sent-41, score-0.236]

24 Among them, we provide experimental results on the nearest and the farthest neighbor searches. [sent-42, score-0.399]

25 , xd ], we denote its mean by µx = d i=1 xi and its d 1 2 2 variance by σx = d i=1 (xi − µx ) . [sent-46, score-0.057]

26 For a pair of vectors x and y, we can reformulate the squared Euclidean distance between x and y as follows. [sent-47, score-0.273]

27 d dist(x, y)2 = (xi − yi )2 i=1 d ((µx + ai ) − (µy + bi ))2 = i=1 d (µ2 + 2ai µx + a2 + µ2 + 2bi µy + b2 − 2(µx µy + ai µy + bi µx + ai bi )) (1) x i y i = i=1 d (µ2 − 2µx µy + µ2 + a2 + b2 − 2ai bi ) x y i i = (2) i=1 d = d (µx − µy )2 + (σx + σy )2 − 2dσx σy − 2 ai bi (3) ai bi . [sent-55, score-1.962]

28 (4) i=1 d = d (µx − µy )2 + (σx − σy )2 + 2dσx σy − 2 i=1 2 d d d 1 2 By the deﬁnitions of ai and bi , we have i=1 ai = i=1 bi = 0, and d i=1 a2 = σx . [sent-56, score-0.704]

29 By the ﬁrst i properties, equation (1) is simpliﬁed to (2), and by the second property, equations (2) becomes (3) and (4). [sent-57, score-0.078]

30 Note that equations (3) and (4) are composed of the mean and variance values (their products and squared values, multiplied by d) of x and y, except the last summations. [sent-58, score-0.074]

31 Thus, once we preprocess V of n vectors such that both µx and σx for all x ∈ V are computed in O(dn) time and stored in a table of size O(n), this sum can be computed in constant time for any pair of vectors, regardless of the dimension. [sent-59, score-0.17]

32 d The last summation, i ai bi , is the inner product a, b , and therefore by applying the CauchySchwarz inequality we get d d | a, b | = | ai bi | ≤ d a2 )( i ( i=1 i=1 b2 ) = dσx σy . [sent-60, score-0.755]

33 i (5) i=1 This gives us the following upper and lower bounds of the squared Euclidean distance from equations (3) and (4). [sent-61, score-0.313]

34 Lemma 1 For two d-dimensional vectors x, y, the followings hold. [sent-62, score-0.078]

35 However, in some applications these bounds may not be tight enough. [sent-64, score-0.105]

36 In this section, we introduce the MSdistance which not only provides lower and upper bounds of the Euclidean distance in constant time, but also could be reﬁned further in such a way to converge to the exact Euclidean distance within d steps. [sent-65, score-0.43]

37 To do this, we reformulate the last term of equations (3) and (4), that is, the inner product a, b . [sent-66, score-0.111]

38 If d d d 2 2 the norms ||a|| = i=1 ai or ||b|| = i=1 bi are zero, then i=1 ai bi = 0, thus the upper and lower bounds become the same. [sent-67, score-0.867]

39 This implies that we can compute the exact Euclidean distance in constant time. [sent-68, score-0.144]

40 We can also get equation (10) by i i switching the roles of the term −dσx σy and the term dσx σy in the above equations. [sent-72, score-0.053]

41 Now we deﬁne the MS-distance between x and y in its lower bound form, denoted by MSL (x, y, k), by replacing the last term of equation (3) with equation (9), and in its upper bound form, denoted by MSU(x, y, k) by replacing the last term of equation (4) with equation (10). [sent-74, score-0.437]

42 The MS-distance makes use of the nonincreasing intermediate values for its upper bound and the nondecreasing intermediate values for its lower bound. [sent-75, score-0.21]

43 k MSL (x, y, k) = d (µx − µy )2 + (σx − σy )2 + σx σy i=0 k MSU (x, y, k) = d (µx − µy )2 + (σx + σy )2 − σx σy i=0 bi ai − σy σx 2 bi ai + σy σx 2 (11) (12) Properties. [sent-77, score-0.704]

44 Note that equation (11) is nondecreasing and equation (12) is nonincreasing while i ai bi ai bi increases from 0 to d, because d, σx , and σy are all nonnegative, and ( σy − σx )2 and ( σy + σx )2 are also nonnegative for all i. [sent-78, score-0.884]

45 This is very useful because, in equation (11), the ﬁrst term, MSL(x, y, 0), is already a lower bound of dist(x, y)2 by inequality (6) , and the lower bound can be reﬁned further nondecreasingly over the summation in the second term. [sent-79, score-0.237]

46 If we stop the summation at i = k, for k < d, the intermediate result is also a reﬁned lower bounds of dist(x, y)2 . [sent-80, score-0.204]

47 Similarly, in equation (12), the ﬁrst term, MSU(x, y, 0), is already an upper bound of dist(x, y)2 by inequality (7) , and the upper bound can be reﬁned further nonincreasingly over the summation in the second term. [sent-81, score-0.259]

48 This means we can stop the summation as soon as we ﬁnd a bound good enough for the application under consideration. [sent-82, score-0.097]

49 Lemma 2 (Monotone Convergence) Let MSL(x, y, k) and MSU(x, y, k) be the lower and upper bounds of MS-distance as deﬁned above, respectively. [sent-85, score-0.163]

50 Let φ denote a threshold for ﬁltering deﬁned in some proximity search problem under consideration. [sent-94, score-0.147]

51 If φ < MSL(x, y, 0) in case of nearest search or φ > MSL(x, y, 0) in case of farthest search, we do not need to consider this pair (x, y) as a candidate, thus we can save time from computing their exact Euclidean distance. [sent-95, score-0.423]

52 , xd ] into a pair of points, ˆ ˆ ˆ ˆ x+ and x− , in the 2-dimensional plane such that x+ = [µx , σx ] and x− = [µx , −σx ]. [sent-99, score-0.094]

53 x ˆ (13) (14) To see why it is useful in fast ﬁltering, consider the case of ﬁnding the nearest vector. [sent-101, score-0.167]

54 For ddimensional vectors in V of size n, we have n pairs of points in the plane as in Figure 1. [sent-102, score-0.13]

55 Let q be a query vector, and let q+ denote the point mapped in the plane as deﬁned above. [sent-104, score-0.113]

56 Among these n points lying on or below µ-axis, let ˆi ˆ x− be the point that is nearest to q+ . [sent-105, score-0.136]

57 Note that the closest point from the query can be computed efﬁciently in 2-dimensional space, for example, after constructing some space partitioning structures such as kd-trees or R-trees, each query can be answered in poly-logarithmic search time. [sent-106, score-0.182]

58 4 ˆ Then we can ignore all d-dimensional vectors x whose mapped point x+ lies outside the circle ˆ centered at q+ and of radius dist(ˆ + , x− ) in the plane, because they are strictly farther than xi q ˆi from q. [sent-107, score-0.225]

59 All d-dimensional vectors x whose ˆ mapped point x+ lies outside the circle are strictly farther than xi from q. [sent-109, score-0.225]

60 Observe that MSL(x, y, k) is almost the same as MSL(x, y, k − 1) if bk /σy ≈ ak /σx . [sent-111, score-0.076]

61 Hence, in the worst case, MSL(x, y, 0) = MSL(x, y, d − 1) < MSL(x, y, d) = dist(x, y)2 when bk /σy = ak /σx for all k = 0, 1, . [sent-112, score-0.076]

62 Therefore, if we need a lower bound strictly better than MSL (x, y, 0), then we need to go through all d reﬁnement steps, which takes O(d) time. [sent-116, score-0.085]

63 Consider a random order for the last term in equation MSL (x, y, k) and for the last term in equation MSU (x, y, k). [sent-119, score-0.152]

64 We measure the expected quality of the bounds by the difference between the bounds, that is, MSU(x, y, k) − MSL(x, y, k) as follows. [sent-122, score-0.092]

65 k MSU (x, y, k) − MSL (x, y, k) = 4dσx σy − 2σx σy i=0 = 4dσx σy − 2σx σy k d d i=0 aγ(i) σx 2 ai σx 2 + + bi σy 2 bγ(i) σy = 4dσx σy − 4kσx σy = 4σx σy (d − k) (15) 2 (16) (17) (18) Let us explain how we get Equation (16) from (15). [sent-123, score-0.352]

66 d d 2 2 Equations (17) and (18) are because i=1 a2 = dσx and i=1 b2 = dσy by deﬁnitions of ai and bi . [sent-128, score-0.352]

67 This shows a good theoretical expectation on the lower and upper bounds. [sent-133, score-0.091]

68 This can justify that the MS-distance provides very tight bounds in a few reﬁnement steps of a typical sequence. [sent-134, score-0.146]

69 5 Applications : Proximity Searches The MS-distance can be used to application problems where the Euclidean distance is a measure for proximity or similarity of objects. [sent-135, score-0.236]

70 As a case study, we implemented the nearest neighbor search (NNS) and the farthest neighbor search (FNS) using the MS-distance. [sent-136, score-0.638]

71 Given a set X of d-dimensional vectors xi , for i = 1, . [sent-137, score-0.111]

72 , n, and a d-dimensional query vector q, we use the following simple randomized algorithm for NNS. [sent-140, score-0.052]

73 Consider the vectors in X one at a time according to this sequence. [sent-143, score-0.098]

74 , d : if MSL(q, xi , j) > φ : break; if j = d: φ = MSL(q, xi , d); NN = i; 2. [sent-148, score-0.066]

75 return NN as the nearest neighbor of q with the squared Euclidean distance φ. [sent-149, score-0.38]

76 Note that the ﬁrst line of the pseudocodes ﬁlters out the vectors whose distance to q is larger than φ as in the fast ﬁltering in Section 3. [sent-150, score-0.247]

77 In the for loop, we compute MSL(q, xi , j) from MSL(q, xi , j −1) in constant time. [sent-151, score-0.083]

78 From the last two lines of the pseudocodes, we update φ to the exact Euclidean distance between q and xi and store the index as the current nearest neighbor (NN). [sent-152, score-0.438]

79 The algorithm for the farthest neighbor search is similar to this one, except that it uses MSU(xi , y, j) and maintains the maximum distance. [sent-153, score-0.323]

80 For empirical comparison, we implemented a linear search algorithm that simply computes distances from q to every xi and chooses the one with the minimum distance. [sent-154, score-0.134]

81 We also used the implementation of the cover tree [6]. [sent-155, score-0.091]

82 A cover tree is a data structure that supports fast nearest neighbor queries given a ﬁxed intrinsic dimensionality [7]. [sent-156, score-0.438]

83 We selected data sets D from various dimensions (from 10 to 100, 000), and randomly selected 30 queries points Q ⊂ D, and queried them on D \ Q. [sent-158, score-0.063]

84 Probably this is because the distances from queries to their nearest vectors tend to converge to the distances to their farthest vectors as described in [13]. [sent-166, score-0.586]

85 However, on such high dimensions, both the linear search and the cover tree algorithm also show poor performance. [sent-168, score-0.151]

86 Figure 3 shows the preprocessing time of the MS-distance and the cover tree for NNS. [sent-169, score-0.135]

87 Cover Figure 3: Preprocessing time for nearest neighbor search in log-scaled second. [sent-175, score-0.335]

88 This is because for the MS-distance it requires only O(dn) time to compute the mean and the standard deviation values. [sent-177, score-0.051]

89 Linear Figure 5: Relative running time for the farthest neighbor search queries, normalized by linear search time. [sent-189, score-0.403]

90 The graph shows the query time that is normalized by the linear search time. [sent-191, score-0.132]

91 It is clear that the ﬁltering algorithm based on the MS-distance beats the linear search algorithm, even on high dimensional data in the results. [sent-192, score-0.077]

92 The cover tree, which is designed exclusively for NNS, shows slightly better query performance than ours. [sent-193, score-0.117]

93 However, the MS-distance is more general and ﬂexible: it supports addition of a new vector to the data set (our data structure) in O(d) time for computing the mean and the standard deviation values of the vector. [sent-194, score-0.068]

94 This is outstanding compared to the linear search algorithm. [sent-198, score-0.06]

95 6 Conclusion We introduce a fast distance bounding technique, called the MS-distance, by using the mean and the standard deviation values. [sent-200, score-0.161]

96 The MS-distance between two vectors provides upper and lower bounds of Euclidean distance between them in constant time, and these bounds converge monotonically to the exact Euclidean distance over iteration. [sent-201, score-0.606]

97 The MS-distance can be used to application problems where the Euclidean distance is a measure for proximity or similarity of objects. [sent-202, score-0.236]

98 The experimental results show that our method is efﬁcient enough even to replace the best known algorithms for proximity searches. [sent-203, score-0.087]

99 Dimensionality reduction and similarity computation by inner g g product approximations. [sent-250, score-0.058]

100 idistance: An adaptive b+-tree based indexing method for nearest neighbor search. [sent-270, score-0.255]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('msl', 0.671), ('msu', 0.454), ('dist', 0.23), ('bi', 0.202), ('ai', 0.15), ('farthest', 0.144), ('euclidean', 0.136), ('nearest', 0.136), ('neighbor', 0.119), ('nement', 0.1), ('distance', 0.099), ('proximity', 0.087), ('nns', 0.087), ('fns', 0.079), ('vectors', 0.078), ('bounds', 0.072), ('cover', 0.065), ('search', 0.06), ('equation', 0.053), ('summation', 0.052), ('query', 0.052), ('upper', 0.051), ('re', 0.047), ('ltering', 0.045), ('queries', 0.044), ('distances', 0.041), ('lower', 0.04), ('bitwise', 0.039), ('pohang', 0.039), ('pseudocodes', 0.039), ('bk', 0.039), ('dn', 0.038), ('ak', 0.037), ('reformulate', 0.035), ('pair', 0.035), ('plane', 0.035), ('tight', 0.033), ('xi', 0.033), ('nn', 0.033), ('korea', 0.032), ('sigmod', 0.032), ('deviation', 0.031), ('fast', 0.031), ('similarity', 0.03), ('inner', 0.028), ('exact', 0.028), ('ltered', 0.027), ('nonincreasing', 0.027), ('farther', 0.027), ('squared', 0.026), ('monotonically', 0.026), ('bound', 0.026), ('tree', 0.026), ('mapped', 0.026), ('equations', 0.025), ('preprocessing', 0.024), ('nondecreasing', 0.024), ('usa', 0.024), ('converge', 0.024), ('xd', 0.024), ('nonnegative', 0.023), ('spent', 0.023), ('circle', 0.023), ('ny', 0.023), ('last', 0.023), ('justify', 0.022), ('management', 0.021), ('searches', 0.021), ('intermediate', 0.021), ('time', 0.02), ('measure', 0.02), ('lies', 0.019), ('typical', 0.019), ('stop', 0.019), ('uci', 0.019), ('lter', 0.019), ('strictly', 0.019), ('database', 0.019), ('dimensions', 0.019), ('replacing', 0.018), ('trees', 0.018), ('acm', 0.018), ('partitioning', 0.018), ('york', 0.018), ('constant', 0.017), ('ramakrishnan', 0.017), ('arcene', 0.017), ('archive', 0.017), ('covertype', 0.017), ('ddimensional', 0.017), ('hwang', 0.017), ('isolet', 0.017), ('madelon', 0.017), ('mest', 0.017), ('parkinsons', 0.017), ('schek', 0.017), ('ubuntu', 0.017), ('weber', 0.017), ('supports', 0.017), ('dimensional', 0.017)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000002 64 nips-2011-Convergent Bounds on the Euclidean Distance

Author: Yoonho Hwang, Hee-kap Ahn

2 0.10213019 231 nips-2011-Randomized Algorithms for Comparison-based Search

Author: Dominique Tschopp, Suhas Diggavi, Payam Delgosha, Soheil Mohajer

Abstract: This paper addresses the problem of ﬁnding the nearest neighbor (or one of the R-nearest neighbors) of a query object q in a database of n objects, when we can only use a comparison oracle. The comparison oracle, given two reference objects and a query object, returns the reference object most similar to the query object. The main problem we study is how to search the database for the nearest neighbor (NN) of a query, while minimizing the questions. The difﬁculty of this problem depends on properties of the underlying database. We show the importance of a characterization: combinatorial disorder D which deﬁnes approximate triangle n inequalities on ranks. We present a lower bound of Ω(D log D + D2 ) average number of questions in the search phase for any randomized algorithm, which demonstrates the fundamental role of D for worst case behavior. We develop 3 a randomized scheme for NN retrieval in O(D3 log2 n + D log2 n log log nD ) 3 questions. The learning requires asking O(nD3 log2 n + D log2 n log log nD ) questions and O(n log2 n/ log(2D)) bits to store.

3 0.089594699 149 nips-2011-Learning Sparse Representations of High Dimensional Data on Large Scale Dictionaries

Author: Zhen J. Xiang, Hao Xu, Peter J. Ramadge

Abstract: Learning sparse representations on data adaptive dictionaries is a state-of-the-art method for modeling data. But when the dictionary is large and the data dimension is high, it is a computationally challenging problem. We explore three aspects of the problem. First, we derive new, greatly improved screening tests that quickly identify codewords that are guaranteed to have zero weights. Second, we study the properties of random projections in the context of learning sparse representations. Finally, we develop a hierarchical framework that uses incremental random projections and screening to learn, in small stages, a hierarchically structured dictionary for sparse representations. Empirical results show that our framework can learn informative hierarchical sparse representations more efﬁciently. 1

4 0.078577176 39 nips-2011-Approximating Semidefinite Programs in Sublinear Time

Author: Dan Garber, Elad Hazan

Abstract: In recent years semideﬁnite optimization has become a tool of major importance in various optimization and machine learning problems. In many of these problems the amount of data in practice is so large that there is a constant need for faster algorithms. In this work we present the ﬁrst sublinear time approximation algorithm for semideﬁnite programs which we believe may be useful for such problems in which the size of data may cause even linear time algorithms to have prohibitive running times in practice. We present the algorithm and its analysis alongside with some theoretical lower bounds and an improved algorithm for the special problem of supervised learning of a distance metric. 1

5 0.076214358 303 nips-2011-Video Annotation and Tracking with Active Learning

Author: Carl Vondrick, Deva Ramanan

Abstract: We introduce a novel active learning framework for video annotation. By judiciously choosing which frames a user should annotate, we can obtain highly accurate tracks with minimal user effort. We cast this problem as one of active learning, and show that we can obtain excellent performance by querying frames that, if annotated, would produce a large expected change in the estimated object track. We implement a constrained tracker and compute the expected change for putative annotations with efﬁcient dynamic programming algorithms. We demonstrate our framework on four datasets, including two benchmark datasets constructed with key frame annotations obtained by Amazon Mechanical Turk. Our results indicate that we could obtain equivalent labels for a small fraction of the original cost. 1

6 0.074561507 182 nips-2011-Nearest Neighbor based Greedy Coordinate Descent

7 0.073496282 135 nips-2011-Information Rates and Optimal Decoding in Large Neural Populations

8 0.063916348 279 nips-2011-Target Neighbor Consistent Feature Weighting for Nearest Neighbor Classification

9 0.059274495 157 nips-2011-Learning to Search Efficiently in High Dimensions

10 0.053277746 112 nips-2011-Heavy-tailed Distances for Gradient Based Image Descriptors

11 0.05322919 91 nips-2011-Exploiting spatial overlap to efficiently compute appearance distances between image windows

12 0.053187292 168 nips-2011-Maximum Margin Multi-Instance Learning

13 0.052865013 63 nips-2011-Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization

14 0.051741328 114 nips-2011-Hierarchical Multitask Structured Output Learning for Large-scale Sequence Segmentation

15 0.047055662 229 nips-2011-Query-Aware MCMC

16 0.04493982 22 nips-2011-Active Ranking using Pairwise Comparisons

17 0.044595338 70 nips-2011-Dimensionality Reduction Using the Sparse Linear Model

18 0.043518946 96 nips-2011-Fast and Balanced: Efficient Label Tree Learning for Large Scale Object Recognition

19 0.04339309 151 nips-2011-Learning a Tree of Metrics with Disjoint Visual Features

20 0.043148559 29 nips-2011-Algorithms and hardness results for parallel large margin learning

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.118), (1, 0.001), (2, -0.035), (3, -0.008), (4, -0.002), (5, 0.029), (6, -0.026), (7, -0.033), (8, -0.038), (9, -0.065), (10, 0.014), (11, 0.023), (12, -0.047), (13, -0.003), (14, 0.081), (15, 0.036), (16, -0.014), (17, 0.135), (18, -0.058), (19, -0.039), (20, 0.089), (21, 0.002), (22, 0.138), (23, -0.015), (24, -0.088), (25, -0.069), (26, -0.022), (27, 0.069), (28, -0.011), (29, -0.044), (30, 0.008), (31, -0.097), (32, -0.034), (33, 0.038), (34, -0.031), (35, -0.053), (36, 0.034), (37, 0.08), (38, 0.03), (39, 0.055), (40, 0.063), (41, -0.032), (42, 0.037), (43, -0.082), (44, 0.034), (45, -0.058), (46, -0.013), (47, 0.157), (48, 0.088), (49, 0.01)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.92735207 64 nips-2011-Convergent Bounds on the Euclidean Distance

Author: Yoonho Hwang, Hee-kap Ahn

2 0.54863042 95 nips-2011-Fast and Accurate k-means For Large Datasets

Author: Michael Shindler, Alex Wong, Adam W. Meyerson

Abstract: Clustering is a popular problem with many applications. We consider the k-means problem in the situation where the data is too large to be stored in main memory and must be accessed sequentially, such as from a disk, and where we must use as little memory as possible. Our algorithm is based on recent theoretical results, with significant improvements to make it practical. Our approach greatly simplifies a recently developed algorithm, both in design and in analysis, and eliminates large constant factors in the approximation guarantee, the memory requirements, and the running time. We then incorporate approximate nearest neighbor search to compute k-means in o( nk) (where n is the number of data points; note that computing the cost, given a solution, takes 8(nk) time). We show that our algorithm compares favorably to existing algorithms - both theoretically and experimentally, thus providing state-of-the-art performance in both theory and practice.

3 0.53780669 231 nips-2011-Randomized Algorithms for Comparison-based Search

Author: Dominique Tschopp, Suhas Diggavi, Payam Delgosha, Soheil Mohajer

4 0.50486034 149 nips-2011-Learning Sparse Representations of High Dimensional Data on Large Scale Dictionaries

Author: Zhen J. Xiang, Hao Xu, Peter J. Ramadge

5 0.44428059 81 nips-2011-Efficient anomaly detection using bipartite k-NN graphs

Author: Kumar Sricharan, Alfred O. Hero

Abstract: Learning minimum volume sets of an underlying nominal distribution is a very effective approach to anomaly detection. Several approaches to learning minimum volume sets have been proposed in the literature, including the K-point nearest neighbor graph (K-kNNG) algorithm based on the geometric entropy minimization (GEM) principle [4]. The K-kNNG detector, while possessing several desirable characteristics, suffers from high computation complexity, and in [4] a simpler heuristic approximation, the leave-one-out kNNG (L1O-kNNG) was proposed. In this paper, we propose a novel bipartite k-nearest neighbor graph (BPkNNG) anomaly detection scheme for estimating minimum volume sets. Our bipartite estimator retains all the desirable theoretical properties of the K-kNNG, while being computationally simpler than the K-kNNG and the surrogate L1OkNNG detectors. We show that BP-kNNG is asymptotically consistent in recovering the p-value of each test point. Experimental results are given that illustrate the superior performance of BP-kNNG as compared to the L1O-kNNG and other state of the art anomaly detection schemes.

6 0.44078216 143 nips-2011-Learning Anchor Planes for Classification

7 0.42488742 157 nips-2011-Learning to Search Efficiently in High Dimensions

8 0.41977969 303 nips-2011-Video Annotation and Tracking with Active Learning

9 0.41136649 20 nips-2011-Active Learning Ranking from Pairwise Preferences with Almost Optimal Query Complexity

10 0.40948078 241 nips-2011-Scalable Training of Mixture Models via Coresets

11 0.40489107 279 nips-2011-Target Neighbor Consistent Feature Weighting for Nearest Neighbor Classification

12 0.39374256 22 nips-2011-Active Ranking using Pairwise Comparisons

13 0.36802873 114 nips-2011-Hierarchical Multitask Structured Output Learning for Large-scale Sequence Segmentation

14 0.36612296 233 nips-2011-Rapid Deformable Object Detection using Dual-Tree Branch-and-Bound

15 0.35255814 182 nips-2011-Nearest Neighbor based Greedy Coordinate Descent

16 0.34446055 111 nips-2011-Hashing Algorithms for Large-Scale Learning

17 0.33475164 168 nips-2011-Maximum Margin Multi-Instance Learning

18 0.33271399 263 nips-2011-Sparse Manifold Clustering and Embedding

19 0.32769278 181 nips-2011-Multiple Instance Learning on Structured Data

20 0.3264603 287 nips-2011-The Manifold Tangent Classifier

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.029), (4, 0.115), (20, 0.034), (25, 0.235), (26, 0.038), (31, 0.069), (33, 0.022), (43, 0.059), (45, 0.118), (57, 0.046), (65, 0.011), (74, 0.032), (83, 0.06), (99, 0.03)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.7989639 215 nips-2011-Policy Gradient Coagent Networks

Author: Philip S. Thomas

Abstract: We present a novel class of actor-critic algorithms for actors consisting of sets of interacting modules. We present, analyze theoretically, and empirically evaluate an update rule for each module, which requires only local information: the module’s input, output, and the TD error broadcast by a critic. Such updates are necessary when computation of compatible features becomes prohibitively difﬁcult and are also desirable to increase the biological plausibility of reinforcement learning methods. 1

same-paper 2 0.77976203 64 nips-2011-Convergent Bounds on the Euclidean Distance

Author: Yoonho Hwang, Hee-kap Ahn

3 0.72337437 269 nips-2011-Spike and Slab Variational Inference for Multi-Task and Multiple Kernel Learning

Author: Miguel Lázaro-gredilla, Michalis K. Titsias

Abstract: We introduce a variational Bayesian inference algorithm which can be widely applied to sparse linear models. The algorithm is based on the spike and slab prior which, from a Bayesian perspective, is the golden standard for sparse inference. We apply the method to a general multi-task and multiple kernel learning model in which a common set of Gaussian process functions is linearly combined with task-speciﬁc sparse weights, thus inducing relation between tasks. This model uniﬁes several sparse linear models, such as generalized linear models, sparse factor analysis and matrix factorization with missing values, so that the variational algorithm can be applied to all these cases. We demonstrate our approach in multioutput Gaussian process regression, multi-class classiﬁcation, image processing applications and collaborative ﬁltering. 1

4 0.64413232 139 nips-2011-Kernel Bayes' Rule

Author: Kenji Fukumizu, Le Song, Arthur Gretton

Abstract: A nonparametric kernel-based method for realizing Bayes’ rule is proposed, based on kernel representations of probabilities in reproducing kernel Hilbert spaces. The prior and conditional probabilities are expressed as empirical kernel mean and covariance operators, respectively, and the kernel mean of the posterior distribution is computed in the form of a weighted sample. The kernel Bayes’ rule can be applied to a wide variety of Bayesian inference problems: we demonstrate Bayesian computation without likelihood, and ﬁltering with a nonparametric statespace model. A consistency rate for the posterior estimate is established. 1

5 0.64000607 127 nips-2011-Image Parsing with Stochastic Scene Grammar

Author: Yibiao Zhao, Song-chun Zhu

Abstract: This paper proposes a parsing algorithm for scene understanding which includes four aspects: computing 3D scene layout, detecting 3D objects (e.g. furniture), detecting 2D faces (windows, doors etc.), and segmenting background. In contrast to previous scene labeling work that applied discriminative classiﬁers to pixels (or super-pixels), we use a generative Stochastic Scene Grammar (SSG). This grammar represents the compositional structures of visual entities from scene categories, 3D foreground/background, 2D faces, to 1D lines. The grammar includes three types of production rules and two types of contextual relations. Production rules: (i) AND rules represent the decomposition of an entity into sub-parts; (ii) OR rules represent the switching among sub-types of an entity; (iii) SET rules represent an ensemble of visual entities. Contextual relations: (i) Cooperative “+” relations represent positive links between binding entities, such as hinged faces of a object or aligned boxes; (ii) Competitive “-” relations represents negative links between competing entities, such as mutually exclusive boxes. We design an efﬁcient MCMC inference algorithm, namely Hierarchical cluster sampling, to search in the large solution space of scene conﬁgurations. The algorithm has two stages: (i) Clustering: It forms all possible higher-level structures (clusters) from lower-level entities by production rules and contextual relations. (ii) Sampling: It jumps between alternative structures (clusters) in each layer of the hierarchy to ﬁnd the most probable conﬁguration (represented by a parse tree). In our experiment, we demonstrate the superiority of our algorithm over existing methods on public dataset. In addition, our approach achieves richer structures in the parse tree. 1

6 0.63797075 279 nips-2011-Target Neighbor Consistent Feature Weighting for Nearest Neighbor Classification

7 0.63368261 213 nips-2011-Phase transition in the family of p-resistances

8 0.63130599 193 nips-2011-Object Detection with Grammar Models

9 0.63056415 231 nips-2011-Randomized Algorithms for Comparison-based Search

10 0.62398684 39 nips-2011-Approximating Semidefinite Programs in Sublinear Time

11 0.62233973 150 nips-2011-Learning a Distance Metric from a Network

12 0.61877751 204 nips-2011-Online Learning: Stochastic, Constrained, and Smoothed Adversaries

13 0.61760741 166 nips-2011-Maximal Cliques that Satisfy Hard Constraints with Application to Deformable Object Model Learning

14 0.61492896 233 nips-2011-Rapid Deformable Object Detection using Dual-Tree Branch-and-Bound

15 0.61426759 185 nips-2011-Newtron: an Efficient Bandit algorithm for Online Multiclass Prediction

16 0.61149639 242 nips-2011-See the Tree Through the Lines: The Shazoo Algorithm

17 0.61143243 22 nips-2011-Active Ranking using Pairwise Comparisons

18 0.61032051 80 nips-2011-Efficient Online Learning via Randomized Rounding

19 0.61005223 29 nips-2011-Algorithms and hardness results for parallel large margin learning

20 0.60924864 168 nips-2011-Maximum Margin Multi-Instance Learning