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

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

Source: pdf

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.

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 ir 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. [sent-7, score-1.026]

2 The comparison oracle, given two reference objects and a query object, returns the reference object most similar to the query object. [sent-8, score-1.148]

3 The main problem we study is how to search the database for the nearest neighbor (NN) of a query, while minimizing the questions. [sent-9, score-0.612]

4 We show the importance of a characterization: combinatorial disorder D which deﬁnes approximate triangle n inequalities on ranks. [sent-11, score-0.426]

5 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. [sent-12, score-1.003]

6 We develop 3 a randomized scheme for NN retrieval in O(D3 log2 n + D log2 n log log nD ) 3 questions. [sent-13, score-0.573]

7 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. [sent-14, score-0.806]

8 1 Introduction Consider the situation where we want to search and navigate a database, but the underlying relationships between the objects are unknown and are accessible only through a comparison oracle. [sent-15, score-0.449]

9 The comparison oracle, given two reference objects and a query object, returns the reference object most similar to the query object. [sent-16, score-1.148]

10 Using such an oracle, the best we can hope for is to obtain, for every object u in the database, a ranking of the other objects according to their similarity to u. [sent-20, score-0.566]

11 However, the use of the oracle to get complete information about ranking could be costly, since invoking the oracle is to represent human input to the task (preferences in movies, comparison of images etc). [sent-21, score-0.412]

12 We can pre-process the database by asking questions during a learning phase, and use the resulting answers to facilitate the search process. [sent-22, score-0.772]

13 Therefore, the main question we ask in this paper is to design a (approximate) nearest neighbor retrieval algorithm while minimizing the number of questions to such an oracle. [sent-23, score-0.716]

14 We show our ﬁrst lower bound of n Ω(D log D +D2 ) on average number of questions in the search phase for any randomized algorithm, and therefore demonstrate the fundamental importance of D for worst case behavior. [sent-29, score-1.003]

15 This allows us to design a novel hierarchical scheme which considerably improves the existing bounds for nearest neighbor search based on a similarity oracle, and performs provably close to the lower bound. [sent-31, score-0.548]

16 If no characterization of the hidden space can be used as an input, we develop algorithms that can decompose the space such that dissimilar objects are likely to get separated, and similar objects have the tendency to stay together; generalizing the notion of randomized k-d-trees [2]. [sent-32, score-0.737]

17 The main limitation of this algorithm is the fact that all rank relationships need to be known in advance, which amounts to asking the oracle O(n2 log n) questions, in a database of size n. [sent-40, score-0.736]

18 It is shown that a learning phase with complexity O(D7 n log2 n) questions and a space complexity of O(D5 n + Dn log n) allows to retrieve the NN in O(D4 log n) questions. [sent-42, score-0.847]

19 However, the fact that we do not have access to distances forces us to use new techniques in order to minimize the number of questions (or ranks we need to compute). [sent-48, score-0.456]

20 To the best of our knowledge, the notion of randomized NN search using similarity oracle is studied for the ﬁrst time in this paper. [sent-55, score-0.472]

21 2 Deﬁnitions and Problem Statement We consider a hidden space K, and a database of objects T ⊂ K, with |T | = n. [sent-58, score-0.454]

22 We can only access this space through a similarity oracle which for any point q ∈ K, and objects u, v ∈ T returns O(q, u, v) = u v if u is more similar to q than v else. [sent-59, score-0.522]

23 (1) The goal is to develop and analyse algorithms which for any given q ∈ K, can ﬁnd an object in the database a ∈ T which is the nearest neighbor (NN) to q, using the smallest number of questions of type (1). [sent-60, score-1.054]

24 Note that this phase has to be done prior to knowing the query q ∈ K. [sent-63, score-0.392]

25 Then, once the query is given, the search phase of the algorithm asks a certain number of questions of type (1) and ﬁnds the closest object in the database. [sent-64, score-1.175]

26 The performance of the algorithm is measured by three components among which there could be a trade-off: the number of questions asked in the learning phase, the number of questions asked in the searching phase, and the total memory to be stored. [sent-65, score-0.878]

27 The rank of u in a set S with respect to v, rv (u, S) is equal to c, if u is the cth nearest object to v in S, i. [sent-69, score-0.519]

28 an object o by asking the oracle O(m log m) questions, using standard sort algorithms [15]. [sent-84, score-0.71]

29 Our characterization of the space of objects is through a form of approximate triangle inequalities introduced in [1] and [12]. [sent-85, score-0.431]

30 Instead of deﬁning a inequalities between distances, these triangle inequalities deﬁned over ranks, and depend on a property of the space, called the disorder constant. [sent-86, score-0.441]

31 More precisely, we prove a lower bound on the average search time to retrieve the nearest neighbor of a query point for randomized algorithms in the combinatorial framework. [sent-92, score-1.029]

32 As a consequence of this theorem, there must exist at least one query point in this conﬁguration n which requires asking at least Ω(D log( D ) + D2 ) questions, hence setting a lower bound on the search complexity. [sent-95, score-0.594]

33 We design a randomized algorithm, which for a given query point q, can retrieve 3 its nearest neighbor with high probability in O(D3 log2 n + D log2 n log log nD ) questions. [sent-98, score-1.146]

34 The 3 3 learning requires asking O(nD3 log2 n + D log2 n log log nD ) questions and we need to store O(n log2 n/ log(2D)) bits. [sent-99, score-0.833]

35 Consequently, our schemes are asymptotically (for n) within Dpolylog(n) questions of the optimal search algorithm. [sent-100, score-0.423]

36 4 Lower Bounds for NNS A natural question to ask is whether there are databases and query points for which we need to ask a minimal number of questions, independent of the algorithm used. [sent-101, score-0.421]

37 In this section, we construct a database T of n objects, a universe of queries K\T and similarity relationships, for which no n search algorithm can ﬁnd the NN of a query point in less than expected Ω(D log D + D2 ) questions. [sent-102, score-0.908]

38 We show this even when all possible questions O(u, v, w) related to the n database objects (i. [sent-103, score-0.759]

39 The query is chosen uniformly from the universe of queries and is unknown during the learning phase. [sent-106, score-0.364]

40 Each of the supernodes in turn n contains α database objects (i. [sent-113, score-0.565]

41 Note that the database T only includes the set of objects inside the supernodes, and the supernodes, themselves, are not element of T . [sent-117, score-0.454]

42 We indicate the objects in each branch by numbers from 1 to n/α. [sent-118, score-0.374]

43 We deﬁne the set of queries, M, as follows: every query point q is attached to one object form T on each branch of the star with an edge; this object is called a direct node (DN) on the corresponding branch. [sent-119, score-0.977]

44 Moreover, we assume that the weights of all query edges, the α edges connecting the query to its DNs, are different. [sent-120, score-0.664]

45 , (n/α)α choices for α branches), and the weight of the query edges can be ordered in α! [sent-124, score-0.38]

46 All edges connecting the SNs to each other have weight 1 expect those α edges emitting from the center of the star and ending at the ﬁrst SNs which have weight n/(α2 ). [sent-127, score-0.387]

47 Edges connecting the objects in a supernode to its root are called object edges. [sent-128, score-0.635]

48 We assume that all n/α object edges in branch φi have weight i/(4α). [sent-129, score-0.427]

49 , δq (i) denotes the indicator of the object on φi which is connected to q via a query edge. [sent-138, score-0.502]

50 For a query q ∈ M, the weight of the query edge which connects q to δq (i) is given to be 1 + (Ψq (i)/α)ǫ, where ǫ ≪ 1/(4α) is a constant. [sent-152, score-0.595]

51 The following lemma gives the disorder constant for the database introduced. [sent-154, score-0.448]

52 The star shaped graph introduced above has disorder constant D = Θ(α). [sent-157, score-0.407]

53 In the following, we state two lower bounds for the number of questions in the searching phase of any deterministic algorithm for the database illustrated in Fig. [sent-159, score-0.694]

54 The number of questions asked by a deterministic algorithm A, on average w. [sent-162, score-0.397]

55 Note that the weights of the edges emitting from the center of the graph are chosen so that the branches become independent, in the sense that questioning nodes on one branch will not reveal 4 Figure 1: The star database: a weighted star graph with α branches, each composed of n/α2 “supernodes”. [sent-167, score-0.637]

56 Finally, each query points is randomly connected to one object on each branch of the star via a weighted edge. [sent-169, score-0.728]

57 Hence, roughly speaking, the algorithm needs to ask Ω(log(n/α)) questions for each branch. [sent-174, score-0.375]

58 This yields to a minimum total of Ω(α log(n/α)) questions for α independent branches in the graph. [sent-175, score-0.397]

59 Any deterministic algorithm A solving nearest neighbor search problem in the input query set M with uniform distribution should ask on average Ω(α2 ) questions from the oracle. [sent-177, score-1.081]

60 If QA denotes the average number of questions A asks, according to Proposition 1 and Proposition 2 we have QA ≥ max Ω α log n 1 n , Ω(α2 ) ≥ Ω α log , Ω(α2 ) = Ω α2 + α log n/α . [sent-189, score-0.872]

61 Indeed, we present an algorithm in the appendix [4], which ﬁnds the query by asking Θ α2 + α log n/α questions. [sent-192, score-0.633]

62 At each level i, every object in T is put in the “bin” of the sample in Si closest to it. [sent-198, score-0.431]

63 To ﬁnd this sample at level i, for every object p we rank the samples in Si w. [sent-199, score-0.422]

64 However, we show that given that we know D, we only need to rank those samples that fell in the bin of one of the at most 4aD log n nearest samples to p at level i − 1. [sent-203, score-0.649]

65 Further, the fact that we build the hierarchy top-down, allows us to use the answers to the questions asked at level i, to reduce the number of questions we need to ask at level i + 1. [sent-205, score-1.065]

66 This way, the number of questions per object does not increase as we go down in the hierarchy, even though the number of samples increases. [sent-206, score-0.564]

67 For object p, νp (i) denotes the nearest neighbor to object p in Si . [sent-207, score-0.749]

68 We want to keep the λi = n/(2D)i−1 closest objects in Si to p in the set Γp (i), i. [sent-208, score-0.374]

69 It could be veriﬁed that |Γp (i)| ≤ 4aD log n, therefore Γp (i) can be constructed by ﬁnding the 4aD log n closest objects in Λp (i) to p. [sent-213, score-0.752]

70 Therefore we can recursively build Γp (i), Λp (i) and νp (i) for 1 ≤ i ≤ log n/ log 2D for any object p, as it is done in the algorithm. [sent-215, score-0.599]

71 The key idea is that the sample closest to the query point on the lowest level will be its NN. [sent-219, score-0.491]

72 We ﬁrst bound the number of questions asked by Algorithm 1 (w. [sent-223, score-0.431]

73 Algorithm 1 succeeds with probability higher than 1 − n , and it requires asking no 2 2 3 D3 more than O(nD log n + D log n log log n ) questions w. [sent-229, score-1.184]

74 For every object p ∈ T ∪ {q}, where q is the query point, the following four properties of the data structure are true w. [sent-236, score-0.502]

75 Let mi = a(2D)i log n denote the number of objects we sample at level i, and let Si be the set of samples at level i i. [sent-245, score-0.7]

76 For each object p, we need to ﬁnd νp (i), which is the nearest neighbor in Si with respect to p. [sent-255, score-0.528]

77 In practice our algorithm stores some redundant objects in Γp (i), but we claim that totally no more than 4aD log n objects are stored in Γp (i + 1). [sent-257, score-0.752]

78 To summarize, the properties we want to maintain in each level are: 1∀p ∈ T and 1 ≤ i ≤ log n/ log 2D, Si ∩ βp (λi ) ⊆ Γp (i) and 2- |Γp (i)| ≤ 4aD log n. [sent-258, score-0.67]

79 , pn , and disorder constant D output: For each object u, a vector νu of length log n/ log(2D). [sent-263, score-0.643]

80 , log n/ log(2D); νo : νo (i) =nearest neighbor to object o in Si ; o ∈ T , i = 1, . [sent-268, score-0.543]

81 Hence by 7 taking the ﬁrst 4aD log n closest objects to p in Λp (i + 1) and storing them in Γp (i + 1), we can make sure than both s ∈ Γp (i + 1) for s ∈ Si+1 , s ∈ βp (λi+1 ) and |Γp (i + 1)| ≤ 4aD log n. [sent-281, score-0.752]

82 Note that in the last loop of the algorithm when i = log n/ log 2D, according to Property 1, |Si ∩ βp (λi+1 )| ≥ 1. [sent-282, score-0.378]

83 But λi+1 in the last step is 1, therefore the closest object to p in the database is in Slog n/ log 2D , which means that νp (log n/ log 2D) is the nearest neighbor of p in the database. [sent-283, score-1.2]

84 Repeating this argument for the query point in the Search algorithm shows that after the termination, the algorithm ﬁnds the nearest neighbor. [sent-284, score-0.455]

85 Property 4 tells us that all of the 4aD log n closest samples to p at level i have rank less than 8λi ,so all objects in Λp (i) have ranks less than 8λi with respect to p. [sent-286, score-0.891]

86 If an object s′′ is in Λp (i + 1), it means that it falls in the bin of an object s in Γp (i), i. [sent-288, score-0.489]

87 Thus, by inequality 2, we have: rs′′ (s, T ) ≤ λi+1 and rp (s, T ) ≤ 8λi ⇒ rp (s′′ , T ) < D(8λi + λi+1 ) ≤ 4λi−1 By property 5, there are at most O(D3 log n) such samples at level i + 1, i. [sent-293, score-0.504]

88 To summarize, at each level for each object, we build a heap out of O(D3 log n) objects and apply O(aD log n) ExtractMin procedures to ﬁnd the ﬁrst 4aD log n objects in the heap. [sent-296, score-1.337]

89 Each 3 ExtractMin requires O(log(D3 log n)) = O(log log nD ). [sent-297, score-0.378]

90 Hence the complexity for each level 3 and for each object is O(D3 log n + D log n log log nD ). [sent-298, score-1.08]

91 There are O(log n) levels and n objects, 3 so the overall complexity is O(nD3 log n + nD log2 n log log nD ). [sent-299, score-0.567]

92 The upper bound on the number of questions to be asked in the learning phase is immediate from Theorem 3. [sent-301, score-0.542]

93 Finally, the properties 1-5 shown in the proof of Theorem 3 are also true for an external query object q. [sent-304, score-0.54]

94 Hence, to ﬁnd the closest object to q on every level, we build the same heap structure, the only difference is that instead of repeating this procedure n times in each level, since there is just one 3 query point, we need to ask at most O(D3 log2 n + D log2 n log log nD ) questions totally. [sent-305, score-1.535]

95 In particular, the closest object at level L = log2D (n) will be q’s nearest neighbor w. [sent-306, score-0.738]

96 6 Discussion The use of a comparison oracle is motivated by a human user who can make comparisons between objects but not assign meaningful numerical values to similarities between objects. [sent-315, score-0.474]

97 There are many interesting questions raised by studying such a model including fundamental characterizations of the complexity of search in terms of number of oracle questions. [sent-316, score-0.629]

98 Analogous to locality sensitive hashing, one can develop notions of rank-sensitive hashing, where “similar” objects based on ranks are given the same hash value. [sent-318, score-0.386]

99 2 Making the assumption that every object can be uniquely identiﬁed with log n bits 8 References [1] N. [sent-321, score-0.41]

100 Schutze, “Disorder inequality: A combinatorial approach to nearest neighbor search,” in WSDM, 2008, pp. [sent-324, score-0.378]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('questions', 0.305), ('query', 0.281), ('objects', 0.267), ('disorder', 0.233), ('si', 0.231), ('object', 0.221), ('log', 0.189), ('database', 0.187), ('oracle', 0.177), ('nearest', 0.174), ('nn', 0.159), ('neighbor', 0.133), ('heap', 0.133), ('rx', 0.131), ('randomized', 0.127), ('asking', 0.123), ('star', 0.119), ('search', 0.118), ('phase', 0.111), ('extractmin', 0.111), ('supernode', 0.111), ('supernodes', 0.111), ('closest', 0.107), ('branch', 0.107), ('level', 0.103), ('branches', 0.092), ('asked', 0.092), ('dns', 0.088), ('ranks', 0.085), ('dn', 0.074), ('triangle', 0.074), ('combinatorial', 0.071), ('ask', 0.07), ('rp', 0.068), ('rz', 0.067), ('buildheap', 0.066), ('tschopp', 0.066), ('rs', 0.066), ('edges', 0.066), ('rv', 0.064), ('rank', 0.06), ('nns', 0.058), ('searching', 0.053), ('retrieve', 0.053), ('worst', 0.052), ('similarity', 0.05), ('queries', 0.049), ('inequalities', 0.048), ('hierarchy', 0.048), ('bin', 0.047), ('delgosha', 0.044), ('diggavi', 0.044), ('goyal', 0.044), ('mohajer', 0.044), ('questioning', 0.044), ('sns', 0.044), ('nd', 0.042), ('tells', 0.042), ('characterization', 0.042), ('metric', 0.041), ('appendix', 0.04), ('theorem', 0.04), ('repeating', 0.04), ('lifshits', 0.039), ('ry', 0.039), ('answers', 0.039), ('proof', 0.038), ('samples', 0.038), ('distances', 0.038), ('property', 0.038), ('lower', 0.038), ('connecting', 0.036), ('hierarchical', 0.035), ('retrieval', 0.034), ('bound', 0.034), ('reference', 0.034), ('develop', 0.034), ('universe', 0.034), ('navigate', 0.034), ('emitting', 0.034), ('weight', 0.033), ('movies', 0.032), ('asks', 0.032), ('memory', 0.031), ('qa', 0.03), ('comparison', 0.03), ('bit', 0.029), ('claim', 0.029), ('fundamental', 0.029), ('outline', 0.029), ('node', 0.028), ('los', 0.028), ('graph', 0.028), ('ranking', 0.028), ('access', 0.028), ('lemma', 0.028), ('proposition', 0.027), ('store', 0.027), ('shaped', 0.027), ('angeles', 0.027)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999911 231 nips-2011-Randomized Algorithms for Comparison-based Search

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

2 0.22935522 22 nips-2011-Active Ranking using Pairwise Comparisons

Author: Kevin G. Jamieson, Robert Nowak

Abstract: This paper examines the problem of ranking a collection of objects using pairwise comparisons (rankings of two objects). In general, the ranking of n objects can be identiﬁed by standard sorting methods using n log2 n pairwise comparisons. We are interested in natural situations in which relationships among the objects may allow for ranking using far fewer pairwise comparisons. Speciﬁcally, we assume that the objects can be embedded into a d-dimensional Euclidean space and that the rankings reﬂect their relative distances from a common reference point in Rd . We show that under this assumption the number of possible rankings grows like n2d and demonstrate an algorithm that can identify a randomly selected ranking using just slightly more than d log n adaptively selected pairwise comparisons, on average. If instead the comparisons are chosen at random, then almost all pairwise comparisons must be made in order to identify any ranking. In addition, we propose a robust, error-tolerant algorithm that only requires that the pairwise comparisons are probably correct. Experimental studies with synthetic and real datasets support the conclusions of our theoretical analysis. 1

3 0.1573371 229 nips-2011-Query-Aware MCMC

Author: Michael L. Wick, Andrew McCallum

Abstract: Traditional approaches to probabilistic inference such as loopy belief propagation and Gibbs sampling typically compute marginals for all the unobserved variables in a graphical model. However, in many real-world applications the user’s interests are focused on a subset of the variables, speciﬁed by a query. In this case it would be wasteful to uniformly sample, say, one million variables when the query concerns only ten. In this paper we propose a query-speciﬁc approach to MCMC that accounts for the query variables and their generalized mutual information with neighboring variables in order to achieve higher computational efﬁciency. Surprisingly there has been almost no previous work on query-aware MCMC. We demonstrate the success of our approach with positive experimental results on a wide range of graphical models. 1

4 0.14166975 1 nips-2011-$\theta$-MRF: Capturing Spatial and Semantic Structure in the Parameters for Scene Understanding

Author: Congcong Li, Ashutosh Saxena, Tsuhan Chen

Abstract: For most scene understanding tasks (such as object detection or depth estimation), the classiﬁers need to consider contextual information in addition to the local features. We can capture such contextual information by taking as input the features/attributes from all the regions in the image. However, this contextual dependence also varies with the spatial location of the region of interest, and we therefore need a different set of parameters for each spatial location. This results in a very large number of parameters. In this work, we model the independence properties between the parameters for each location and for each task, by deﬁning a Markov Random Field (MRF) over the parameters. In particular, two sets of parameters are encouraged to have similar values if they are spatially close or semantically close. Our method is, in principle, complementary to other ways of capturing context such as the ones that use a graphical model over the labels instead. In extensive evaluation over two different settings, of multi-class object detection and of multiple scene understanding tasks (scene categorization, depth estimation, geometric labeling), our method beats the state-of-the-art methods in all the four tasks. 1

5 0.12771335 157 nips-2011-Learning to Search Efficiently in High Dimensions

Author: Zhen Li, Huazhong Ning, Liangliang Cao, Tong Zhang, Yihong Gong, Thomas S. Huang

Abstract: High dimensional similarity search in large scale databases becomes an important challenge due to the advent of Internet. For such applications, specialized data structures are required to achieve computational efﬁciency. Traditional approaches relied on algorithmic constructions that are often data independent (such as Locality Sensitive Hashing) or weakly dependent (such as kd-trees, k-means trees). While supervised learning algorithms have been applied to related problems, those proposed in the literature mainly focused on learning hash codes optimized for compact embedding of the data rather than search efﬁciency. Consequently such an embedding has to be used with linear scan or another search algorithm. Hence learning to hash does not directly address the search efﬁciency issue. This paper considers a new framework that applies supervised learning to directly optimize a data structure that supports efﬁcient large scale search. Our approach takes both search quality and computational cost into consideration. Speciﬁcally, we learn a boosted search forest that is optimized using pair-wise similarity labeled examples. The output of this search forest can be efﬁciently converted into an inverted indexing data structure, which can leverage modern text search infrastructure to achieve both scalability and efﬁciency. Experimental results show that our approach signiﬁcantly outperforms the start-of-the-art learning to hash methods (such as spectral hashing), as well as state-of-the-art high dimensional search algorithms (such as LSH and k-means trees).

6 0.12512954 126 nips-2011-Im2Text: Describing Images Using 1 Million Captioned Photographs

7 0.12381072 279 nips-2011-Target Neighbor Consistent Feature Weighting for Nearest Neighbor Classification

8 0.11194883 205 nips-2011-Online Submodular Set Cover, Ranking, and Repeated Active Learning

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

10 0.10411067 182 nips-2011-Nearest Neighbor based Greedy Coordinate Descent

11 0.10213019 64 nips-2011-Convergent Bounds on the Euclidean Distance

12 0.098682277 304 nips-2011-Why The Brain Separates Face Recognition From Object Recognition

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

14 0.094200745 35 nips-2011-An ideal observer model for identifying the reference frame of objects

15 0.092966646 247 nips-2011-Semantic Labeling of 3D Point Clouds for Indoor Scenes

16 0.092817441 137 nips-2011-Iterative Learning for Reliable Crowdsourcing Systems

17 0.089757822 151 nips-2011-Learning a Tree of Metrics with Disjoint Visual Features

18 0.086637676 233 nips-2011-Rapid Deformable Object Detection using Dual-Tree Branch-and-Bound

19 0.086501114 154 nips-2011-Learning person-object interactions for action recognition in still images

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

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.225), (1, 0.031), (2, -0.141), (3, 0.094), (4, 0.059), (5, 0.036), (6, -0.107), (7, -0.065), (8, 0.047), (9, 0.012), (10, 0.006), (11, 0.033), (12, -0.061), (13, 0.06), (14, 0.259), (15, -0.021), (16, 0.096), (17, 0.097), (18, -0.092), (19, 0.084), (20, 0.035), (21, 0.022), (22, 0.172), (23, 0.026), (24, -0.093), (25, -0.032), (26, 0.201), (27, 0.09), (28, 0.061), (29, -0.117), (30, 0.084), (31, -0.045), (32, 0.014), (33, 0.08), (34, 0.025), (35, -0.039), (36, -0.019), (37, 0.083), (38, -0.008), (39, 0.051), (40, 0.015), (41, 0.003), (42, 0.017), (43, -0.003), (44, -0.023), (45, 0.07), (46, 0.022), (47, 0.092), (48, 0.031), (49, -0.034)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.97181678 231 nips-2011-Randomized Algorithms for Comparison-based Search

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

2 0.86579531 22 nips-2011-Active Ranking using Pairwise Comparisons

Author: Kevin G. Jamieson, Robert Nowak

3 0.709252 20 nips-2011-Active Learning Ranking from Pairwise Preferences with Almost Optimal Query Complexity

Author: Nir Ailon

Abstract: Given a set V of n elements we wish to linearly order them using pairwise preference labels which may be non-transitive (due to irrationality or arbitrary noise). The goal is to linearly order the elements while disagreeing with as few pairwise preference labels as possible. Our performance is measured by two parameters: The number of disagreements (loss) and the query complexity (number of pairwise preference labels). Our algorithm adaptively queries at most O(n poly(log n, ε−1 )) preference labels for a regret of ε times the optimal loss. This is strictly better, and often signiﬁcantly better than what non-adaptive sampling could achieve. Our main result helps settle an open problem posed by learning-to-rank (from pairwise information) theoreticians and practitioners: What is a provably correct way to sample preference labels? 1

4 0.6198684 64 nips-2011-Convergent Bounds on the Euclidean Distance

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

5 0.57766777 229 nips-2011-Query-Aware MCMC

Author: Michael L. Wick, Andrew McCallum

6 0.54943991 126 nips-2011-Im2Text: Describing Images Using 1 Million Captioned Photographs

7 0.49099749 35 nips-2011-An ideal observer model for identifying the reference frame of objects

8 0.46805382 95 nips-2011-Fast and Accurate k-means For Large Datasets

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

10 0.45532477 304 nips-2011-Why The Brain Separates Face Recognition From Object Recognition

11 0.45069104 233 nips-2011-Rapid Deformable Object Detection using Dual-Tree Branch-and-Bound

12 0.4456698 7 nips-2011-A Machine Learning Approach to Predict Chemical Reactions

13 0.44266939 162 nips-2011-Lower Bounds for Passive and Active Learning

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

15 0.43352449 138 nips-2011-Joint 3D Estimation of Objects and Scene Layout

16 0.41529718 91 nips-2011-Exploiting spatial overlap to efficiently compute appearance distances between image windows

17 0.4019385 272 nips-2011-Stochastic convex optimization with bandit feedback

18 0.40051755 195 nips-2011-On Learning Discrete Graphical Models using Greedy Methods

19 0.39893553 168 nips-2011-Maximum Margin Multi-Instance Learning

20 0.39477468 1 nips-2011-$\theta$-MRF: Capturing Spatial and Semantic Structure in the Parameters for Scene Understanding

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.042), (4, 0.114), (20, 0.061), (26, 0.061), (31, 0.123), (33, 0.035), (43, 0.054), (45, 0.096), (57, 0.054), (58, 0.147), (74, 0.059), (83, 0.034), (99, 0.028)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.8426044 231 nips-2011-Randomized Algorithms for Comparison-based Search

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

2 0.78960192 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

3 0.78754985 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

4 0.77985913 204 nips-2011-Online Learning: Stochastic, Constrained, and Smoothed Adversaries

Author: Alexander Rakhlin, Karthik Sridharan, Ambuj Tewari

Abstract: Learning theory has largely focused on two main learning scenarios: the classical statistical setting where instances are drawn i.i.d. from a ﬁxed distribution, and the adversarial scenario wherein, at every time step, an adversarially chosen instance is revealed to the player. It can be argued that in the real world neither of these assumptions is reasonable. We deﬁne the minimax value of a game where the adversary is restricted in his moves, capturing stochastic and non-stochastic assumptions on data. Building on the sequential symmetrization approach, we deﬁne a notion of distribution-dependent Rademacher complexity for the spectrum of problems ranging from i.i.d. to worst-case. The bounds let us immediately deduce variation-type bounds. We study a smoothed online learning scenario and show that exponentially small amount of noise can make function classes with inﬁnite Littlestone dimension learnable. 1

5 0.77844405 64 nips-2011-Convergent Bounds on the Euclidean Distance

Author: Yoonho Hwang, Hee-kap Ahn

6 0.77843672 75 nips-2011-Dynamical segmentation of single trials from population neural data

7 0.77738988 229 nips-2011-Query-Aware MCMC

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

9 0.76976794 49 nips-2011-Boosting with Maximum Adaptive Sampling

10 0.76796836 22 nips-2011-Active Ranking using Pairwise Comparisons

11 0.76756269 180 nips-2011-Multiple Instance Filtering

12 0.76734567 213 nips-2011-Phase transition in the family of p-resistances

13 0.7606619 55 nips-2011-Collective Graphical Models

14 0.7572611 17 nips-2011-Accelerated Adaptive Markov Chain for Partition Function Computation

15 0.75659955 227 nips-2011-Pylon Model for Semantic Segmentation

16 0.75657785 168 nips-2011-Maximum Margin Multi-Instance Learning

17 0.75634289 57 nips-2011-Comparative Analysis of Viterbi Training and Maximum Likelihood Estimation for HMMs

18 0.75464398 193 nips-2011-Object Detection with Grammar Models

19 0.75177377 223 nips-2011-Probabilistic Joint Image Segmentation and Labeling

20 0.75172991 242 nips-2011-See the Tree Through the Lines: The Shazoo Algorithm