nips nips2013 nips2013-107 knowledge-graph by maker-knowledge-mining

107 nips-2013-Embed and Project: Discrete Sampling with Universal Hashing

Source: pdf

Author: Stefano Ermon, Carla P. Gomes, Ashish Sabharwal, Bart Selman

Abstract: We consider the problem of sampling from a probability distribution deﬁned over a high-dimensional discrete set, speciﬁed for instance by a graphical model. We propose a sampling algorithm, called PAWS, based on embedding the set into a higher-dimensional space which is then randomly projected using universal hash functions to a lower-dimensional subspace and explored using combinatorial search methods. Our scheme can leverage fast combinatorial optimization tools as a blackbox and, unlike MCMC methods, samples produced are guaranteed to be within an (arbitrarily small) constant factor of the true probability distribution. We demonstrate that by using state-of-the-art combinatorial search tools, PAWS can efﬁciently sample from Ising grids with strong interactions and from software veriﬁcation instances, while MCMC and variational methods fail in both cases. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 Abstract We consider the problem of sampling from a probability distribution deﬁned over a high-dimensional discrete set, speciﬁed for instance by a graphical model. [sent-14, score-0.304]

2 We propose a sampling algorithm, called PAWS, based on embedding the set into a higher-dimensional space which is then randomly projected using universal hash functions to a lower-dimensional subspace and explored using combinatorial search methods. [sent-15, score-0.802]

3 Our scheme can leverage fast combinatorial optimization tools as a blackbox and, unlike MCMC methods, samples produced are guaranteed to be within an (arbitrarily small) constant factor of the true probability distribution. [sent-16, score-0.39]

4 We demonstrate that by using state-of-the-art combinatorial search tools, PAWS can efﬁciently sample from Ising grids with strong interactions and from software veriﬁcation instances, while MCMC and variational methods fail in both cases. [sent-17, score-0.402]

5 Since this can be used to approximate #P-complete inference problems, sampling is also believed to be computationally hard in the worst case [1, 2]. [sent-20, score-0.229]

6 Sampling from a succinctly speciﬁed combinatorial space is believed to much harder than searching the space. [sent-21, score-0.197]

7 MCMC techniques are a specialized form of local search that only allows moves that maintain detailed balance, thus guaranteeing the right occupation probability once the chain has mixed. [sent-26, score-0.173]

8 However, in the context of hard combinatorial spaces with complex internal structure, mixing times are often exponential. [sent-27, score-0.192]

9 It is therefore a natural question whether one can construct sampling techniques based on these more powerful complete search methods rather than local search. [sent-29, score-0.244]

10 [3] showed that it is possible to uniformly sample witnesses of an NP language leveraging universal hash functions and using only a small number of queries to an NP-oracle. [sent-31, score-0.517]

11 Practical algorithms based on these ideas were later developed [4–6] to near-uniformly sample solutions of propositional SATisﬁability instances, using a SAT solver as an NP-oracle. [sent-33, score-0.123]

12 We ﬁll this gap by extending this approach, based on hashing-based projections and NP-oracle queries, to the weighted sampling case. [sent-37, score-0.184]

13 Our algorithm, called PAWS, uses a form of approximation by quantization [7] and an embedding technique inspired by slice sampling [8], before applying projections. [sent-38, score-0.25]

14 This parallels recent work [9] that extended similar ideas for unweighted counting to the weighted counting world, addressing the problem of discrete integration. [sent-39, score-0.213]

15 Although in theory one could use that technique to produce samples by estimating ratios of discrete integrals [1, 2], the general sampling-by-counting reduction requires a large number of such estimates (proportional to the number of variables) for each sample. [sent-40, score-0.095]

16 Further, the accuracy guarantees on the sampling probability quickly become loose when taking ratios of estimates. [sent-41, score-0.235]

17 In contrast, PAWS is a more direct and practical sampling approach, providing better accuracy guarantees while requiring a much smaller number of NP-oracle queries per sample. [sent-42, score-0.291]

18 We rely on the fact that combinatorial search tools, however, are often extremely fast in practice, and any complete solver can be used as a black box in our sampling scheme. [sent-44, score-0.448]

19 Another key advantage is that when combinatorial search succeeds, our analysis provides a certiﬁcate that, with high probability, any samples produced will be distributed within an (arbitrarily small) constant factor of the desired probability distribution. [sent-45, score-0.43]

20 We empirically demonstrate that PAWS outperforms MCMC as well as variational methods on hard synthetic Ising Models and on a realworld test case generation problem for software veriﬁcation. [sent-47, score-0.157]

21 2 Setup and Problem Deﬁnition We are given a probability distribution p over a (high-dimensional) discrete set X , where the probability of each item x ∈ X is proportional to a weight function w : X → R+ , with R+ being the set of non-negative real numbers. [sent-48, score-0.183]

22 As our driving example, we consider the case of undirected discrete graphical models [10] with n = |V | random variables {xi , i ∈ V } where each xi takes values in a ﬁnite set Xi . [sent-53, score-0.113]

23 (1) α∈I This is a compact representation for p(x) based on the weight function w(x) = α∈I ψα ({x}α ), deﬁned as the product of potentials or factors ψα : {x}α → R+ , where I is an index set and {x}α ⊆ V the subset of variables factor ψα depends on. [sent-55, score-0.091]

24 We consider the fundamental problem of (approximately) sampling from p(x), i. [sent-57, score-0.15]

25 , sampling solutions of a SATisﬁability instance speciﬁed as a factor graph entails ﬁnding at least one solution, or deciding there is none). [sent-63, score-0.193]

26 3 Sampling by Embed, Project, and Search Conceptually, our sampling strategy has three steps, described in Sections 3. [sent-65, score-0.15]

27 Speciﬁcally, p′ is based on a new weight function w′ that takes values only in a discrete set of geometrically increasing weights. [sent-70, score-0.101]

28 (2) From p′ , we deﬁne a uniform probability distribution p′′ over a carefully constructed higher-dimensional embedding of X = {0, 1}n . [sent-71, score-0.158]

29 The previous discretization step allows us to specify p′′ in a compact form, and sampling from p′′ can be seen to be precisely equivalent to sampling from p′ . [sent-72, score-0.433]

30 (3) Finally, we indirectly sample from the desired distribution p by sampling uniformly from p′′ , by randomly projecting the embedding onto a lowerdimensional subspace using universal hash functions and then searching for feasible states. [sent-73, score-0.632]

31 A key advantage is that our technique reduces the weighted sampling problem to that of solving one MAP query (i. [sent-75, score-0.184]

32 , ﬁnding the most likely state) and a polynomial number of feasibility queries (i. [sent-77, score-0.232]

33 In practice, we use a combinatorial optimization package, which requires exponential time in the worst case (consistent with the hardness of sampling) but is often fast in practice. [sent-80, score-0.155]

34 Our analysis shows that whenever the underlying combinatorial search and optimization queries succeed, the samples produced are guaranteed, with high probability, to be coming from an approximately accurate distribution. [sent-81, score-0.443]

35 1 Weight Discretization We use a geometric discretization of the weights into “buckets”, i. [sent-83, score-0.133]

36 , there are 264 possible weights in double precision ﬂoating point), for every b ≥ 1 there is a possibly large but ﬁnite value of ℓ (such that M/rℓ is smaller than the smallest representable weight) such that Bℓ is empty and the discretization error ǫ is effectively zero. [sent-110, score-0.133]

37 2 Embed: From Weighted to Uniform Sampling We now show how to reduce the problem of sampling from the discrete distribution p′ (weighted sampling) to the problem of uniformly sampling, without loss of accuracy, from a higherdimensional discrete set into which X = {0, 1}n is embedded. [sent-112, score-0.301]

38 This is inspired by slice sampling [8], and can be intuitively understood as its discrete counterpart where we uniformly sample points (x, y) from a discrete representation of the area under the (y vs. [sent-113, score-0.373]

39 Further, let ′′ ′ p denote a uniform probability distribution over S(w, ℓ, b) and n = n + (ℓ − 1)b. [sent-122, score-0.096]

40 Given a compact representation of w within a combinatorial search or optimization framework, the set S(w, ℓ, b) can often be easily encoded using the disjunctive constraints on the y variables. [sent-123, score-0.298]

41 [3] and n′ -wise independent hash functions we can sample purely uniformly from S(w, ℓ, b) using an NP oracle to answer feasibility queries. [sent-134, score-0.5]

42 However, such hash functions involve constructions that are difﬁcult to implement and reason about in existing combinatorial search methods. [sent-135, score-0.535]

43 Instead, we use a more practical algorithm based on pairwise independent hash functions that can be implemented using parity constraints (modular arithmetic) and still provides accuracy guarantees. [sent-136, score-0.455]

44 The approach is similar to [5], but we include an algorithmic way to estimate the number of parity constraints to be used. [sent-137, score-0.125]

45 We also use the pivot technique from [6] but extend that work in two ways: we introduce a parameter α (similar to [5]) that allows us to trade off uniformity against runtime and also provide upper bounds on the sampling probabilities. [sent-138, score-0.228]

46 The idea is to project by randomly constraining the conﬁguration space using a family of universal hash functions, search for up to P “surviving” conﬁgurations, and then, if fewer than P survive, perform rejection sampling to choose one of them. [sent-140, score-0.644]

47 The number k of constraints or factors (encoding a randomly chosen hash function) to add is determined ﬁrst; this is where we depart from both Gomes et al. [sent-141, score-0.335]

48 Intuitively, we need the hashed space to contain no more than P solutions because that is a base case where we know how to produce uniform samples via enumeration. [sent-145, score-0.097]

49 The small failure probability, accounting for a potentially poor choice of random hash functions, can be bounded irrespective of the underlying graphical model. [sent-148, score-0.346]

50 A combinatorial optimization procedure is used once in order to determine the maximum weight M through MAP inference. [sent-149, score-0.203]

51 Subsequently, several feasibility queries are issued to the underlying combinatorial search procedure in order to, e. [sent-151, score-0.527]

52 , count the number of surviving conﬁgurations and produce one as a sample. [sent-153, score-0.149]

53 We brieﬂy review the construction and properties of universal hash functions [11, 12]. [sent-154, score-0.341]

54 The family H = {hA,c (x) : {0, 1}n → {0, 1}m } where hA,c (x) = Ax + c mod 2 is a family of pairwise independent hash functions. [sent-159, score-0.286]

55 Further, H is also known to be a family of three-wise independent hash functions [5]. [sent-160, score-0.286]

56 The idea is similar to an unweighted version of the WISH algorithm [9] but with tighter guarantees and using more feasibility queries. [sent-168, score-0.135]

57 Then, ∗ ∗ P[kP − γ ≤ k ≤ kP + 1 + γ] ≥ 1 − δ and C OMPUTE K uses O(n′ ln (n′ /δ)) feasibility queries. [sent-172, score-0.135]

58 Brieﬂy, the probability P[σ ∈ S i ] that σ = (x, y) survives is 2−i by the properties of the hash functions in Deﬁnition 3, and the probability of being selected by rejection sampling is 1/(P − 1). [sent-179, score-0.577]

59 Conditioned on σ surviving, the mean and variance of the size of the surviving set |S i | are independent of σ because of 3-wise ∗ ∗ independence. [sent-180, score-0.092]

60 Note that the bound is independent of σ and lets us bound the probability ps (σ) that σ is output: c(α, P ) 2−i = P −1 1− 2γ−α (1 − − 2γ−α )2 1 P 5 2−i 2−i ≤ ps (σ) ≤ . [sent-183, score-0.183]

61 P −1 P −1 (2) ∗ From i = k + α ≤ kP + 1 + γ + α and summing the lower bound of ps (σ) over all σ, we obtain the desired lower bound on the success probability. [sent-184, score-0.107]

62 Note that given σ, σ ′ , ps (σ) and ps (σ ′ ) are within a constant factor c(α, P ) of each other from (2). [sent-185, score-0.185]

63 Therefore, the probabilities p′ (σ) (for various σ) s that σ is output conditioned on outputting a sample are also within a constant factor of each other. [sent-186, score-0.123]

64 From the normalization σ p′ (σ) = 1, one gets the desired result that p′ (x, y) is within a constant s s factor c(α, P ) of the uniform probability p′′ (x, y) = 1/|S|. [sent-187, score-0.139]

65 Then x∈Bℓ p(x) ≤ ǫ and with probability at least (1 − δ)c(α, P )2−(γ+α+1) PP , PAWS(w, ℓ, b, −1 δ, P , α) succeeds and outputs a sample σ from {0, 1}n \ Bℓ . [sent-192, score-0.118]

66 Upon success, each σ ∈ {0, 1}n \ Bℓ is output with probability p′ (σ) within a constant factor ρκ of the desired probability p(σ) ∝ w(σ). [sent-193, score-0.125]

67 By appropriately setting the hyper-parameters b and ℓ we can make the discretization errors ρ and ǫ arbitrarily small. [sent-199, score-0.133]

68 Although this does not change the number of required feasibility queries, it can signiﬁcantly increase the runtime of combinatorial search because of the increased search space size |S(w, ℓ, b)|. [sent-200, score-0.52]

69 Practically, one should set these parameters as large as possible, while ensuring combinatorial searches can be completed within the available time budget. [sent-201, score-0.155]

70 Increasing parameter P improves the accuracy as well, but also increases the number of feasibility queries issued, which is proportional to P (but does not affect the structure of the search space). [sent-202, score-0.37]

71 Then, 1 Ep′ [φ] − ǫηφ ≤ Ep [φ] ≤ ρκEp′ [φ] + ǫηφ s ρκ s where Ep′ [φ] can be approximated with a sample average using samples produced by PAWS. [sent-209, score-0.131]

72 s 4 Experiments We evaluate PAWS on synthetic Ising Models and on a real-world test case generation problem for software veriﬁcation. [sent-210, score-0.12]

73 interactions ψij (xi , xj ) = exp(wij xi xj ), where fi ∈R [−f, f ] and wij ∈R [−w, w] in the mixed case, while wij ∈R [0, w] in the attractive case. [sent-256, score-0.185]

74 Our implementation of PAWS uses the open source solver ToulBar2 [13] to compute M = maxx w(x) and as an oracle to check the existence of at least P different solutions. [sent-257, score-0.134]

75 3 [14] based on techniques borrowed from [15] to efﬁciently reason about parity constraints (the hash functions) using GaussJordan elimination. [sent-259, score-0.411]

76 true marginal probabilities for two Ising grids with mixed and attractive interactions, respectively, representative of the general behavior in the large-weights regime. [sent-264, score-0.161]

77 Marginals computed with Gibbs sampling (run for about 108 iterations) are clearly very inaccurate (far from the 45 degree line), an indication that the Markov Chain had not mixed as an effect of the relatively large weights that tend to create barriers between modes which are hard to traverse. [sent-266, score-0.242]

78 In contrast, samples from PAWS provide much more accurate marginals, in part because it does not rely on local search and hence is not directly affected by the energy landscape (with respect to the Hamming metric). [sent-267, score-0.136]

79 These results highlight the practical value of having accuracy guarantees on the quality of the samples after ﬁnite amounts of time vs. [sent-269, score-0.086]

80 We see in Figure 1 that while samples produced by WISH can sometimes produce fairly accurate marginal estimates, these estimates can also be far from the true value because of an inherent bias introduced by the arg max operator. [sent-274, score-0.097]

81 2 Test Case Generation for Software Veriﬁcation Hardware and software veriﬁcation tools are becoming increasingly important in industrial system design. [sent-276, score-0.125]

82 For example, IBM estimates $100 million savings over the past 10 years from hardware veriﬁcation tools alone [17]. [sent-277, score-0.103]

83 For our experiments, we focus on software (SW) veriﬁcation, using an industrial benchmark [18] produced by Microsoft’s SAGE system [19, 20]. [sent-304, score-0.126]

84 Each instance deﬁnes a uniform probability distribution over certain valid traces of a computer program. [sent-305, score-0.178]

85 We modify this benchmark by introducing soft constraints deﬁning a weighted distribution over valid traces, indicating traces that meet certain criteria should be sampled more often. [sent-306, score-0.165]

86 The weight is chosen to be a power of two, so that there is no loss of accuracy due to discretization using the previous construction with b = 1. [sent-309, score-0.225]

87 These instances are very difﬁcult for MCMC methods because of the presence of very large regions of zero probability that cannot be traversed and thus can break the ergodicity assumption. [sent-310, score-0.115]

88 Indeed we observed that Gibbs sampling often fails to ﬁnd a non-zero probability state, and when it ﬁnds one it gets stuck there, because there might not be a non-zero probability path from one feasible state to another. [sent-311, score-0.232]

89 In contrast, our sampling strategy is not affected and does not require any ergodicity assumption. [sent-312, score-0.185]

90 Table 2a summarizes the results obtained using the propositional satisﬁability (SAT) solver CryptoMiniSAT [21] as the feasibility query oracle for PAWS. [sent-313, score-0.224]

91 CryptoMiniSAT has built-in support for parity constraints Ax = c mod 2. [sent-314, score-0.125]

92 We report the time to collect 1000 samples and the Mean Squared Error (MSE) of the marginals estimated using these samples. [sent-315, score-0.159]

93 We report results only on the subset of instances where we could enumerate all feasible states using the exact model counter Relsat [22] in order to obtain ground truth marginals for MSE computation. [sent-316, score-0.156]

94 observed sampling frequencies (based on 50000 samples) for a small instance with 810 feasible states (execution traces), where we see that the output distribution p′ is indeed very close to the target distribution p. [sent-319, score-0.15]

95 s 5 Conclusions We introduced a new approach, called PAWS, to the fundamental problem of sampling from a discrete probability distribution speciﬁed, up to a normalization constant, by a weight function, e. [sent-320, score-0.292]

96 While traditional sampling methods are based on the MCMC paradigm and hence on some form of local search, PAWS can leverage more advanced combinatorial search and optimization tools as a black box. [sent-323, score-0.453]

97 A signiﬁcant advantage over MCMC methods is that PAWS comes with a strong accuracy guarantee: whenever combinatorial search succeeds, our analysis provides a certiﬁcate that, with high probability, the samples are produced from an approximately correct distribution. [sent-324, score-0.39]

98 Our experiments demonstrate that PAWS outperforms competing sampling methods on challenging domains for MCMC. [sent-327, score-0.15]

99 The Markov chain Monte Carlo method: an approach to approximate counting and integration. [sent-337, score-0.101]

100 Uniform solution sampling using a constraint solver as an oracle. [sent-344, score-0.199]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('paws', 0.577), ('hash', 0.286), ('combinatorial', 0.155), ('sampling', 0.15), ('gomes', 0.138), ('ompute', 0.138), ('feasibility', 0.135), ('discretization', 0.133), ('marginals', 0.117), ('carla', 0.105), ('sabharwal', 0.105), ('veri', 0.102), ('ising', 0.099), ('queries', 0.097), ('mcmc', 0.096), ('kp', 0.095), ('search', 0.094), ('surviving', 0.092), ('sat', 0.087), ('maxx', 0.085), ('traces', 0.082), ('gurations', 0.082), ('bellare', 0.078), ('ermon', 0.078), ('parity', 0.076), ('ibm', 0.076), ('software', 0.071), ('ps', 0.071), ('ashish', 0.069), ('bart', 0.066), ('buckets', 0.064), ('counting', 0.063), ('embedding', 0.062), ('wish', 0.061), ('stefano', 0.06), ('graphical', 0.06), ('rejection', 0.059), ('attractive', 0.058), ('survive', 0.057), ('bi', 0.057), ('count', 0.057), ('universal', 0.055), ('mixed', 0.055), ('uniform', 0.055), ('produced', 0.055), ('tools', 0.054), ('discrete', 0.053), ('cryptominisat', 0.052), ('godefroid', 0.052), ('logr', 0.052), ('naveh', 0.052), ('whitebox', 0.052), ('solver', 0.049), ('generation', 0.049), ('hardware', 0.049), ('ep', 0.049), ('constraints', 0.049), ('hashing', 0.048), ('grids', 0.048), ('weight', 0.048), ('outputting', 0.046), ('cate', 0.046), ('ilog', 0.046), ('issued', 0.046), ('rz', 0.046), ('sage', 0.046), ('lemma', 0.046), ('embed', 0.045), ('uniformly', 0.045), ('accuracy', 0.044), ('succeeds', 0.043), ('chakraborty', 0.043), ('ithaca', 0.043), ('patrice', 0.043), ('certi', 0.043), ('rw', 0.043), ('factor', 0.043), ('believed', 0.042), ('runtime', 0.042), ('samples', 0.042), ('probability', 0.041), ('xor', 0.04), ('propositional', 0.04), ('instances', 0.039), ('gibbs', 0.039), ('slice', 0.038), ('mse', 0.038), ('chain', 0.038), ('hard', 0.037), ('cplex', 0.036), ('levin', 0.036), ('success', 0.036), ('trade', 0.036), ('wij', 0.036), ('propagation', 0.035), ('cornell', 0.035), ('ergodicity', 0.035), ('sample', 0.034), ('weighted', 0.034), ('pp', 0.034)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000006 107 nips-2013-Embed and Project: Discrete Sampling with Universal Hashing

Author: Stefano Ermon, Carla P. Gomes, Ashish Sabharwal, Bart Selman

2 0.15037204 57 nips-2013-Beyond Pairwise: Provably Fast Algorithms for Approximate $k$-Way Similarity Search

Author: Anshumali Shrivastava, Ping Li

Abstract: We go beyond the notion of pairwise similarity and look into search problems with k-way similarity functions. In this paper, we focus on problems related to 3-way Jaccard similarity: R3way = |S1 ∩S2 ∩S3 | , S1 , S2 , S3 ∈ C, where C is a |S1 ∪S2 ∪S3 | size n collection of sets (or binary vectors). We show that approximate R3way similarity search problems admit fast algorithms with provable guarantees, analogous to the pairwise case. Our analysis and speedup guarantees naturally extend to k-way resemblance. In the process, we extend traditional framework of locality sensitive hashing (LSH) to handle higher-order similarities, which could be of independent theoretical interest. The applicability of R3way search is shown on the “Google Sets” application. In addition, we demonstrate the advantage of R3way resemblance over the pairwise case in improving retrieval quality. 1 Introduction and Motivation Similarity search (near neighbor search) is one of the fundamental problems in Computer Science. The task is to identify a small set of data points which are “most similar” to a given input query. Similarity search algorithms have been one of the basic building blocks in numerous applications including search, databases, learning, recommendation systems, computer vision, etc. One widely used notion of similarity on sets is the Jaccard similarity or resemblance [5, 10, 18, 20]. Given two sets S1 , S2 ⊆ Ω = {0, 1, 2, ..., D − 1}, the resemblance R2way between S1 and S2 is deﬁned as: R2way = |S1 ∩S2 | . Existing notions of similarity in search problems mainly work with |S1 ∪S2 | pairwise similarity functions. In this paper, we go beyond this notion and look at the problem of k-way similarity search, where the similarity function of interest involves k sets (k ≥ 2). Our work exploits the fact that resemblance can be naturally extended to k-way resemblance similarity [18, 21], deﬁned over k sets {S1 , S2 , ..., Sk } as Rk−way = |S1 ∩S2 ∩...∩Sk | . |S1 ∪S2 ∪...∪Sk | Binary high-dimensional data The current web datasets are typically binary, sparse, and extremely high-dimensional, largely due to the wide adoption of the “Bag of Words” (BoW) representations for documents and images. It is often the case, in BoW representations, that just the presence or absence (0/1) of speciﬁc feature words captures sufﬁcient information [7, 16, 20], especially with (e.g.,) 3-grams or higher-order models. And so, the web can be imagined as a giant storehouse of ultra high-dimensional sparse binary vectors. Of course, binary vectors can also be equivalently viewed as sets (containing locations of the nonzero features). We list four practical scenarios where k-way resemblance search would be a natural choice. (i) Google Sets: (http://googlesystem.blogspot.com/2012/11/google-sets-still-available.html) Google Sets is among the earliest google projects, which allows users to generate list of similar words by typing only few related keywords. For example, if the user types “mazda” and “honda” the application will automatically generate related words like “bmw”, “ford”, “toyota”, etc. This application is currently available in google spreadsheet. If we assume the term document binary representation of each word w in the database, then given query w1 and w2 , we show that |w1 ∩w2 ∩w| |w1 ∪w2 ∪w| turns out to be a very good similarity measure for this application (see Section 7.1). 1 (ii) Joint recommendations: Users A and B would like to watch a movie together. The proﬁle of each person can be represented as a sparse vector over a giant universe of attributes. For example, a user proﬁle may be the set of actors, actresses, genres, directors, etc, which she/he likes. On the other hand, we can represent a movie M in the database over the same universe based on attributes associated with the movie. If we have to recommend movie M, jointly to users A and B, then a natural measure to maximize is |A∩B∩M | . The problem of group recommendation [3] is applicable |A∪B∪M | in many more settings such as recommending people to join circles, etc. (iii) Improving retrieval quality: We are interested in ﬁnding images of a particular type of object, and we have two or three (possibly noisy) representative images. In such a scenario, a natural expectation is that retrieving images simultaneously similar to all the representative images should be more reﬁned than just retrieving images similar to any one of them. In Section 7.2, we demonstrate that in cases where we have more than one element to search for, we can reﬁne our search quality using k-way resemblance search. In a dynamic feedback environment [4], we can improve subsequent search quality by using k-way similarity search on the pages already clicked by the user. (iv) Beyond pairwise clustering: While machine learning algorithms often utilize the data through pairwise similarities (e.g., inner product or resemblance), there are natural scenarios where the afﬁnity relations are not pairwise, but rather triadic, tetradic or higher [2, 30]. The computational cost, of course, will increase exponentially if we go beyond pairwise similarity. Efﬁciency is crucial With the data explosion in modern applications, the brute force way of scanning all the data for searching is prohibitively expensive, specially in user-facing applications like search. The need for k-way similarity search can only be fulﬁlled if it admits efﬁcient algorithms. This paper fulﬁlls this requirement for k-way resemblance and its derived similarities. In particular, we show fast algorithms with provable query time guarantees for approximate k-way resemblance search. Our algorithms and analysis naturally provide a framework to extend classical LSH framework [14, 13] to handle higher-order similarities, which could be of independent theoretical interest. Organization In Section 2, we review approximate near neighbor search and classical Locality Sensitive Hashing (LSH). In Section 3, we formulate the 3-way similarity search problems. Sections 4, 5, and 6 describe provable fast algorithms for several search problems. Section 7 demonstrates the applicability of 3-way resemblance search in real applications. 2 Classical c-NN and Locality Sensitive Hashing (LSH) Initial attempts of ﬁnding efﬁcient (sub-linear time) algorithms for exact near neighbor search, based on space partitioning, turned out to be a disappointment with the massive dimensionality of current datasets [11, 28]. Approximate versions of the problem were proposed [14, 13] to break the linear query time bottleneck. One widely adopted formalism is the c-approximate near neighbor (c-NN). Deﬁnition 1 (c-Approximate Near Neighbor or c-NN). Consider a set of points, denoted by P, in a D-dimensional space RD , and parameters R0 > 0, δ > 0. The task is to construct a data structure which, given any query point q, if there exist an R0 -near neighbor of q in P, it reports some cR0 -near neighbor of q in P with probability 1 − δ. The usual notion of c-NN is for distance. Since we deal with similarities, we deﬁne R0 -near neighbor of point q as a point p with Sim(q, p) ≥ R0 , where Sim is the similarity function of interest. Locality sensitive hashing (LSH) [14, 13] is a popular framework for c-NN problems. LSH is a family of functions, with the property that similar input objects in the domain of these functions have a higher probability of colliding in the range space than non-similar ones. In formal terms, consider H a family of hash functions mapping RD to some set S Deﬁnition 2 (Locality Sensitive Hashing (LSH)). A family H is called (R0 , cR0 , p1 , p2 )-sensitive if for any two points x, y ∈ RD and h chosen uniformly from H satisﬁes the following: • if Sim(x, y) ≥ R0 then P rH (h(x) = h(y)) ≥ p1 • if Sim(x, y) ≤ cR0 then P rH (h(x) = h(y)) ≤ p2 For approximate nearest neighbor search typically, p1 > p2 and c < 1 is needed. Note, c < 1 as we are deﬁning neighbors in terms of similarity. Basically, LSH trades off query time with extra preprocessing time and space which can be accomplished off-line. 2 Fact 1 Given a family of (R0 , cR0 , p1 , p2 ) -sensitive hash functions, one can construct a data structure for c-NN with O(nρ log1/p2 n) query time and space O(n1+ρ ), where ρ = log 1/p1 . log 1/p2 Minwise Hashing for Pairwise Resemblance One popular choice of LSH family of functions associated with resemblance similarity is, Minwise Hashing family [5, 6, 13]. Minwise Hashing family applies an independent random permutation π : Ω → Ω, on the given set S ⊆ Ω, and looks at the minimum element under π, i.e. min(π(S)). Given two sets S1 , S2 ⊆ Ω = {0, 1, 2, ..., D − 1}, it can be shown by elementary probability argument that P r (min(π(S1 )) = min(π(S2 ))) = |S1 ∩ S2 | = R2way . |S1 ∪ S2 | (1) The recent work on b-bit minwise hashing [20, 23] provides an improvement by storing only the lowest b bits of the hashed values: min(π(S1 )), min(π(S2 )). [26] implemented the idea of building hash tables for near neighbor search, by directly using the bits from b-bit minwise hashing. 3 3-way Similarity Search Formulation Our focus will remain on binary vectors which can also be viewed as sets. We illustrate our method |S1 ∩S2 ∩S3 | using 3-way resemblance similarity function Sim(S1 , S2 , S3 ) = |S1 ∪S2 ∪S3 | . The algorithm and guarantees naturally extend to k-way resemblance. Given a size n collection C ⊆ 2Ω of sets (or binary vectors), we are particularly interested in the following three problems: 1. Given two query sets S1 and S2 , ﬁnd S3 ∈ C that maximizes Sim(S1 , S2 , S3 ). 2. Given a query set S1 , ﬁnd two sets S2 , S3 ∈ C maximizing Sim(S1 , S2 , S3 ). 3. Find three sets S1 , S2 , S3 ∈ C maximizing Sim(S1 , S2 , S3 ). The brute force way of enumerating all possibilities leads to the worst case query time of O(n), O(n2 ) and O(n3 ) for problem 1, 2 and 3, respectively. In a hope to break this barrier, just like the case of pairwise near neighbor search, we deﬁne the c-approximate (c < 1) versions of the above three problems. As in the case of c-NN, we are given two parameters R0 > 0 and δ > 0. For each of the following three problems, the guarantee is with probability at least 1 − δ: 1. (3-way c-Near Neighbor or 3-way c-NN) Given two query sets S1 and S2 , if there ′ exists S3 ∈ C with Sim(S1 , S2 , S3 ) ≥ R0 , then we report some S3 ∈ C so that ′ Sim(S1 , S2 , S3 ) ≥ cR0 . 2. (3-way c-Close Pair or 3-way c-CP) Given a query set S1 , if there exists a pair of ′ ′ set S2 , S3 ∈ C with Sim(S1 , S2 , S3 ) ≥ R0 , then we report sets S2 , S3 ∈ C so that ′ ′ Sim(S1 , S2 , S3 ) ≥ cR0 . 3. (3-way c-Best Cluster or 3-way c-BC) If there exist sets S1 , S2 , S3 ∈ C with ′ ′ ′ ′ ′ ′ Sim(S1 , S2 , S3 ) ≥ R0 , then we report sets S1 , S2 , S3 ∈ C so that Sim(S1 , S2 , S3 ) ≥ cR0 . 4 Sub-linear Algorithm for 3-way c-NN The basic philosophy behind sub-linear search is bucketing, which allows us to preprocess dataset in a fashion so that we can ﬁlter many bad candidates without scanning all of them. LSH-based techniques rely on randomized hash functions to create buckets that probabilistically ﬁlter bad candidates. This philosophy is not restricted for binary similarity functions and is much more general. Here, we ﬁrst focus on 3-way c-NN problem for binary data. Theorem 1 For R3way c-NN one can construct a data structure with O(nρ log1/cR0 n) query time and O(n1+ρ ) space, where ρ = 1 − log 1/c log 1/c+log 1/R0 . The argument for 2-way resemblance can be naturally extended to k-way resemblance. Speciﬁcally, given three sets S1 , S2 , S3 ⊆ Ω and an independent random permutation π : Ω → Ω, we have: P r (min(π(S1 )) = min(π(S2 )) = min(π(S3 ))) = R3way . (2) Eq.( 2) shows that minwise hashing, although it operates on sets individually, preserves all 3-way (in fact k-way) similarity structure of the data. The existence of such a hash function is the key requirement behind the existence of efﬁcient approximate search. For the pairwise case, the probability event was a simple hash collision, and the min-hash itself serves as the bucket index. In case 3 of 3-way (and higher) c-NN problem, we have to take care of a more complicated event to create an indexing scheme. In particular, during preprocessing we need to create buckets for each individual S3 , and while querying we need to associate the query sets S1 and S2 to the appropriate bucket. We need extra mechanisms to manipulate these minwise hashes to obtain a bucketing scheme. Proof of Theorem 1: We use two additional functions: f1 : Ω → N for manipulating min(π(S3 )) and f2 : Ω × Ω → N for manipulating both min(π(S1 )) and min(π(S2 )). Let a ∈ N+ such that |Ω| = D < 10a . We deﬁne f1 (x) = (10a + 1) × x and f2 (x, y) = 10a x + y. This choice ensures that given query S1 and S2 , for any S3 ∈ C, f1 (min(π(S3 ))) = f2 (min(π(S1 )), min(π(S2 ))) holds if and only if min(π(S1 )) = min(π(S2 )) = min(π(S2 )), and thus we get a bucketing scheme. To complete the proof, we introduce two integer parameters K and L. Deﬁne a new hash function by concatenating K events. To be more precise, while preprocessing, for every element S3 ∈ C create buckets g1 (S3 ) = [f1 (h1 (S3 )); ...; f1 (hK (S3 ))] where hi is chosen uniformly from minwise hashing family. For given query points S1 and S2 , retrieve only points in the bucket g2 (S1 , S2 ) = [f2 (h1 (S1 ), h1 (S2 )); ...; f2 (hK (S1 ), hK (S2 ))]. Repeat this process L times independently. For any K S3 ∈ C, with Sim(S1 , S2 , S3 ) ≥ R0 , is retrieved with probability at least 1 − (1 − R0 )L . Using log 1/c log K = ⌈ log n ⌉ and L = ⌈nρ log( 1 )⌉, where ρ = 1 − log 1/c+log 1/R0 , the proof can be obtained 1 δ cR0 using standard concentration arguments used to prove Fact 1, see [14, 13]. It is worth noting that the probability guarantee parameter δ gets absorbed in the constants as log( 1 ). Note, the process is δ stopped as soon as we ﬁnd some element with R3way ≥ cR0 . Theorem 1 can be easily extended to k-way resemblance with same query time and space guarantees. Note that k-way c-NN is at least as hard as k ∗ -way c-NN for any k ∗ ≤ k, because we can always choose (k −k ∗ +1) identical query sets in k-way c-NN, and it reduces to k ∗ -way c-NN problem. So, any improvements in R3way c-NN implies improvement in the classical min-hash LSH for Jaccard similarity. The proposed analysis is thus tight in this sense. The above observation makes it possible to also perform the traditional pairwise c-NN search using the same hash tables deployed for 3-way c-NN. In the query phase we have an option, if we have two different queries S1 , S2 , then we retrieve from bucket g2 (S1 , S2 ) and that is usual 3-way c-NN search. If we are just interested in pairwise near neighbor search given one query S1 , then we will look into bucket g2 (S1 , S1 ), and we know that the 3-way resemblance between S1 , S1 , S3 boils down to the pairwise resemblance between S1 and S3 . So, the same hash tables can be used for both the purposes. This property generalizes, and hash tables created for k-way c-NN can be used for any k ∗ -way similarity search so long as k ∗ ≤ k. The approximation guarantees still holds. This ﬂexibility makes k-way c-NN bucketing scheme more advantageous over the pairwise scheme. ρ 1 One of the peculiarity of LSH based techniques is that the query complexity exponent ρ < 1 is dependent on the choice R0=0.01 0.8 of the threshold R0 we are interested in and the value of c 0.05 0.1 0.3 0.6 which is the approximation ratio that we will tolerate. Figure 1 0.2 0.4 0.8 log 1/c 0.5 plots ρ = 1− log 1/c+log 1/R0 with respect to c, for selected R0 0.4 0.6 0.9 0.7 values from 0.01 to 0.99. For instance, if we are interested in 0.2 0.95 highly similar pairs, i.e. R0 ≈ 1, then we are looking at near R =0.99 0 O(log n) query complexity for c-NN problem as ρ ≈ 0. On 0 0 0.2 0.4 0.6 0.8 1 the other hand, for very lower threshold R0 , there is no much c log 1/c of hope of time-saving because ρ is close to 1. Figure 1: ρ = 1 − log 1/c+log 1/R0 . 5 Other Efﬁcient k-way Similarities We refer to the k-way similarities for which there exist sub-linear algorithms for c-NN search with query and space complexity exactly as given in Theorem 1 as efﬁcient . We have demonstrated existence of one such example of efﬁcient similarities, which is the k-way resemblance. This leads to a natural question: “Are there more of them?”. [9] analyzed all the transformations on similarities that preserve existence of efﬁcient LSH search. In particular, they showed that if S is a similarity for which there exists an LSH family, then there also exists an LSH family for any similarity which is a probability generating function (PGF) transfor∑∞ mation on S. PGF transformation on S is deﬁned as P GF (S) = i=1 pi S i , where S ∈ [0, 1] and ∑∞ pi ≥ 0 satisﬁes i=1 pi = 1. Similar theorem can also be shown in the case of 3-way resemblance. 4 Theorem 2 Any PGF transformation on 3-way resemblance R3way is efﬁcient. Recall in the proof of Theorem 1, we created hash assignments f1 (min(π(S3 ))) and f2 (min(π(S1 )), min(π(S2 ))), which lead to a bucketing scheme for the 3-way resemblance search, where the collision event E = {f1 (min(π(S3 )) = f2 (min(π(S1 )), min(π(S2 )))} happens with probability P r(E) = R3way . To prove the above Theorem 2, we will need to create hash events ∑∞ i having probability P GF (R3way ) = i=1 pi (R3way ) . Note that 0 ≤ P GF (R3way ) ≤ 1. We will make use of the following simple lemma. Lemma 1 (R3way )n is efﬁcient for all n ∈ N. n n Proof: Deﬁne new hash assignments g1 (S3 ) = [f1 (h1 (S3 )); ...; f1 (hn (S3 ))] and g2 (S1 , S2 ) = n n [f2 (h1 (S1 ), h1 (S2 )); ...; f2 (hn (S1 ), hn (S2 ))]. The collision event g1 (S3 ) = g2 (S1 , S2 ) has n n probability (R3way )n . We now use the pair < g1 , g2 > instead of < f1 , f2 > and obtain same 3way n guarantees, as in Theorem 1, for (R ) as well. i i Proof of Theorem 2: From Lemma 1, let < g1 , g2 > be the hash pair corresponding to (R3way )i i i as used in above lemma. We sample one hash pair from the set {< g1 , g2 >: i ∈ N}, where i i the probability of sampling < g1 , g2 > is proportional to pi . Note that pi ≥ 0, and satisﬁes ∑∞ is i=1 pi = 1, and so the above sampling ∑ valid. It is not difﬁcult to see that the collision of the ∞ sampled hash pair has probability exactly i=1 pi (R3way )i . Theorem 2 can be naturally extended to k-way similarity for any k ≥ 2. Thus, we now have inﬁnitely many k-way similarity functions admitting efﬁcient sub-linear search. One, that might be interesting, because of its radial basis kernel like nature, is shown in the following corollary. Corollary 1 eR k−way −1 is efﬁcient. Proof: Use the expansion of eR k−way normalized by e to see that eR k−way −1 is a PGF on Rk−way . 6 Fast Algorithms for 3-way c-CP and 3-way c-BC Problems For 3-way c-CP and 3-way c-BC problems, using bucketing scheme with minwise hashing family will save even more computations. Theorem 3 For R3way c-Close Pair Problem (or c-CP) one can construct a data structure with log 1/c O(n2ρ log1/cR0 n) query time and O(n1+2ρ ) space, where ρ = 1 − log 1/c+log 1/R0 . Note that we can switch the role of f1 and f2 in the proof of Theorem 1. We are thus left with a c-NN problem with search space O(n2 ) (all pairs) instead of n. A bit of analysis, similar to Theorem 1, will show that this procedure achieves the required query time O(n2ρ log1/cR0 n), but uses a lot more space, O(n2(1+ρ )), than shown in the above theorem. It turns out that there is a better way of doing c-CP that saves us space. Proof of Theorem 3: We again start with constructing hash tables. For every element Sc ∈ C, we create a hash-table and store Sc in bucket B(Sc ) = [h1 (Sc ); h2 (Sc ); ...; hK (Sc )], where hi is chosen uniformly from minwise independent family of hash functions H. We create L such hash-tables. For a query element Sq we look for all pairs in bucket B(Sq ) = [h1 (Sq ); h2 (Sq ); ...; hK (Sq )] and repeat this for each of the L tables. Note, we do not form pairs of elements retrieved from different tables as they do not satisfy Eq. (2). If there exists a pair S1 , S2 ∈ C with Sim(Sq , S1 , S2 ) ≥ R0 , using K Eq. (2), we can see that we will ﬁnd that pair in bucket B(Sq ) with probability 1 − (1 − R0 )L . Here, we cannot use traditional choice of K and L, similar to what we did in Theorem 1, as there 2 log are O(n2 ) instead of O(n) possible pairs. We instead use K = ⌈ log 1n ⌉ and L = ⌈n2ρ log( 1 )⌉, δ cR0 log 1/c with ρ = 1 − log 1/c+log 1/R0 . With this choice of K and L, the result follows. Note, the process is stopped as soon as we ﬁnd pairs S1 and S2 with Sim(Sq , S1 , S2 ) ≥ cR0 . The key argument that saves space from O(n2(1+ρ) ) to O(n1+2ρ ) is that we hash n points individually. Eq. (2) makes it clear that hashing all possible pairs is not needed when every point can be processed individually, and pairs formed within each bucket itself ﬁlter out most of the unnecessary combinations. 5 Theorem 4 For R3way c-Best Cluster Problem (or c-BC) there exist an algorithm with running time log 1/c O(n1+2ρ log1/cR0 n), where ρ = 1 − log 1/c+log 1/R0 . The argument similar to one used in proof of Theorem 3 leads to the running time of O(n1+3ρ log1/cR0 n) as we need L = O(n3ρ ), and we have to processes all points at least once. Proof of Theorem 4: Repeat c-CP problem n times for every element in collection C acting as query once. We use the same set of hash tables and hash functions every time. The preprocessing time is O(n1+2ρ log1/cR0 n) evaluations of hash functions and the total querying time is O(n × n2ρ log1/cR0 n), which makes the total running time O(n1+2ρ log1/cR0 n). For k-way c-BC Problem, we can achieve O(n1+(k−1)ρ log1/cR0 n) running time. If we are interested in very high similarity cluster, with R0 ≈ 1, then ρ ≈ 0, and the running time is around O(n log n). This is a huge saving over the brute force O(nk ). In most practical cases, specially in big data regime where we have enormous amount of data, we can expect the k-way similarity of good clusters to be high and ﬁnding them should be efﬁcient. We can see that with increasing k, hashing techniques save more computations. 7 Experiments In this section, we demonstrate the usability of 3-way and higher-order similarity search using (i) Google Sets, and (ii) Improving retrieval quality. 7.1 Google Sets: Generating Semantically Similar Words Here, the task is to retrieve words which are “semantically” similar to the given set of query words. We collected 1.2 million random documents from Wikipedia and created a standard term-doc binary vector representation of each term present in the collected documents after removing standard stop words and punctuation marks. More speciﬁcally, every word is represented as a 1.2 million dimension binary vector indicating its presence or absence in the corresponding document. The total number of terms (or words) was around 60,000 in this experiment. Since there is no standard benchmark available for this task, we show qualitative evaluations. For querying, we used the following four pairs of semantically related words: (i) “jaguar” and “tiger”; (ii) “artiﬁcial” and “intelligence”; (iii) “milky” and “way” ; (iv) “ﬁnger” and “lakes”. Given the query words w1 and w2 , we compare the results obtained by the following four methods. • Google Sets: We use Google’s algorithm and report 5 words from Google spreadsheets [1]. This is Google’s algorithm which uses its own data. • 3-way Resemblance (3-way): We use 3-way resemblance |w1 ∩w2 ∩w| to rank every word |w1 ∪w2 ∪w| w and report top 5 words based on this ranking. • Sum Resemblance (SR): Another intuitive method is to use the sum of pairwise resem|w2 ∩w| blance |w1 ∩w| + |w2 ∪w| and report top 5 words based on this ranking. |w1 ∪w| • Pairwise Intersection (PI): We ﬁrst retrieve top 100 words based on pairwise resemblance for each w1 and w2 independently. We then report the words common in both. If there is no word in common we do not report anything. The results in Table 1 demonstrate that using 3-way resemblance retrieves reasonable candidates for these four queries. An interesting query is “ﬁnger” and “lakes”. Finger Lakes is a region in upstate New York. Google could only relate it to New York, while 3-way resemblance could even retrieve the names of cities and lakes in the region. Also, for query “milky” and “way”, we can see some (perhaps) unrelated words like “dance” returned by Google. We do not see such random behavior with 3-way resemblance. Although we are not aware of the algorithm and the dataset used by Google, we can see that 3-way resemblance appears to be a right measure for this application. The above results also illustrate the problem with using the sum of pairwise similarity method. The similarity value with one of the words dominates the sum and hence we see for queries “artiﬁcial” and “intelligence” that all the retrieved words are mostly related to the word “intelligence”. Same is the case with query “ﬁnger” and “lakes” as well as “jaguar” and “tiger”. Note that “jaguar” is also a car brand. In addition, for all 4 queries, there was no common word in the top 100 words similar to the each query word individually and so PI method never returns anything. 6 Table 1: Top ﬁve words retrieved using various methods for different queries. “JAGUAR” AND “ TIGER” G OOGLE 3- WAY SR LION LEOPARD CHEETAH CAT DOG LEOPARD CHEETAH LION PANTHER CAT CAT LEOPARD LITRE BMW CHASIS “MILKY” AND “ WAY” G OOGLE 3- WAY SR DANCE STARS SPACE THE UNIVERSE GALAXY STARS EARTH LIGHT SPACE EVEN ANOTHER STILL BACK TIME PI — — — — — “ARTIFICIAL” AND “INTELLIGENCE” G OOGLE 3- WAY SR PI COMPUTER COMPUTER SECURITY — PROGRAMMING SCIENCE WEAPONS — INTELLIGENT SECRET — SCIENCE ROBOT HUMAN ATTACKS — ROBOTICS TECHNOLOGY HUMAN — PI — — — — — G OOGLE NEW YORK NY PARK CITY “FINGER” AND “LAKES” 3- WAY SR SENECA CAYUGA ERIE ROCHESTER IROQUOIS RIVERS FRESHWATER FISH STREAMS FORESTED PI — — — — — We should note the importance of the denominator term in 3-way resemblance, without which frequent words will be blindly favored. The exciting contribution of this paper is that 3-way resemblance similarity search admits provable sub-linear guarantees, making it an ideal choice. On the other hand, no such provable guarantees are known for SR and other heuristic based search methods. 7.2 Improving Retrieval Quality in Similarity Search We also demonstrate how the retrieval quality of traditional similarity search can be boosted by utilizing more query candidates instead of just one. For the evaluations we choose two public datasets: MNIST and WEBSPAM, which were used in a recent related paper [26] for near neighbor search with binary data using b-bit minwise hashing [20, 23]. The two datasets reﬂect diversity both in terms of task and scale that is encountered in practice. The MNIST dataset consists of handwritten digit samples. Each sample is an image of 28 × 28 pixel yielding a 784 dimension vector with the associated class label (digit 0 − 9). We binarize the data by settings all non zeros to be 1. We used the standard partition of MNIST, which consists of 10,000 samples in one set and 60,000 in the other. The WEBSPAM dataset, with 16,609,143 features, consists of sparse vector representation of emails labeled as spam or not. We randomly sample 70,000 data points and partitioned them into two independent sets of size 35,000 each. Table 2: Percentage of top candidates with the same labels as that of query retrieved using various similarity criteria. More indicates better retrieval quality (Best marked in bold). T OP Pairwise 3-way NNbor 4-way NNbor 1 94.20 96.90 97.70 MNIST 10 20 92.33 91.10 96.13 95.36 96.89 96.28 50 89.06 93.78 95.10 1 98.45 99.75 99.90 WEBSPAM 10 20 96.94 96.46 98.68 97.80 98.87 98.15 50 95.12 96.11 96.45 For evaluation, we need to generate potential similar search query candidates for k-way search. It makes no sense in trying to search for object simultaneously similar to two very different objects. To generate such query candidates, we took one independent set of the data and partition it according to the class labels. We then run a cheap k-mean clustering on each class, and randomly sample triplets < x1 , x2 , x3 > from each cluster for evaluating 2-way, 3-way and 4-way similarity search. For MNIST dataset, the standard 10,000 test set was partitioned according to the labels into 10 sets, each partition was then clustered into 10 clusters, and we choose 10 triplets randomly from each cluster. In all we had 100 such triplets for each class, and thus 1000 overall query triplets. For WEBSPAM, which consists only of 2 classes, we choose one of the independent set and performed the same procedure. We selected 100 triplets from each cluster. We thus have 1000 triplets from each class making the total number of 2000 query candidates. The above procedures ensure that the elements in each triplets < x1 , x2 , x3 > are not very far from each other and are of the same class label. For each triplet < x1 , x2 , x3 >, we sort all the points x in the other independent set based on the following: • Pairwise: We only use the information in x1 and rank x based on resemblance 7 |x1 ∩x| |x1 ∪x| . • 3-way NN: We rank x based on 3-way resemblance • 4-way NN: We rank x based on 4-way resemblance |x1 ∩x2 ∩x| |x1 ∪x2 ∪x| . |x1 ∩x2 ∩x3 ∩x| |x1 ∪x2 ∪x3 ∪x| . We look at the top 1, 10, 20 and 50 points based on orderings described above. Since, all the query triplets are of the same label, The percentage of top retrieved candidates having same label as that of the query items is a natural metric to evaluate the retrieval quality. This percentage values accumulated over all the triplets are summarized in Table 2. We can see that top candidates retrieved by 3-way resemblance similarity, using 2 query points, are of better quality than vanilla pairwise similarity search. Also 4-way resemblance, with 3 query points, further improves the results compared to 3-way resemblance similarity search. This clearly demonstrates that multi-way resemblance similarity search is more desirable whenever we have more than one representative query in mind. Note that, for MNIST, which contains 10 classes, the boost compared to pairwise retrieval is substantial. The results follow a consistent trend. 8 Future Work While the work presented in this paper is promising for efﬁcient 3-way and k-way similarity search in binary high-dimensional data, there are numerous interesting and practical research problems we can study as future work. In this section, we mention a few such examples. One-permutation hashing. Traditionally, building hash tables for near neighbor search required many (e.g., 1000) independent hashes. This is both time- and energy-consuming, not only for building tables but also for processing un-seen queries which have not been processed. One permutation hashing [22] provides the hope of reducing many permutations to merely one. The version in [22], however, was not applicable to near neighbor search due to the existence of many empty bins (which offer no indexing capability). The most recent work [27] is able to ﬁll the empty bins and works well for pairwise near neighbor search. It will be interesting to extend [27] to k-way search. Non-binary sparse data. This paper focuses on minwise hashing for binary data. Various extensions to real-valued data are possible. For example, our results naturally apply to consistent weighted sampling [25, 15], which is one way to handle non-binary sparse data. The problem, however, is not solved if we are interested in similarities such as (normalized) k-way inner products, although the line of work on Conditional Random Sampling (CRS) [19, 18] may be promising. CRS works on non-binary sparse data by storing a bottom subset of nonzero entries after applying one permutation to (real-valued) sparse data matrix. CRS performs very well for certain applications but it does not work in our context because the bottom (nonzero) subsets are not properly aligned. Building hash tables by directly using bits from minwise hashing. This will be a different approach from the way how the hash tables are constructed in this paper. For example, [26] directly used the bits from b-bit minwise hashing [20, 23] to build hash tables and demonstrated the signiﬁcant advantages compared to sim-hash [8, 12] and spectral hashing [29]. It would be interesting to see the performance of this approach in k-way similarity search. k-Way sign random projections. It would be very useful to develop theory for k-way sign random projections. For usual (real-valued) random projections, it is known that the volume (which is related to the determinant) is approximately preserved [24, 17]. We speculate that the collision probability of k-way sign random projections might be also a (monotonic) function of the determinant. 9 Conclusions We formulate a new framework for k-way similarity search and obtain fast algorithms in the case of k-way resemblance with provable worst-case approximation guarantees. We show some applications of k-way resemblance search in practice and demonstrate the advantages over traditional search. Our analysis involves the idea of probabilistic hashing and extends the well-known LSH family beyond the pairwise case. We believe the idea of probabilistic hashing still has a long way to go. Acknowledgement The work is supported by NSF-III-1360971, NSF-Bigdata-1419210, ONR-N00014-13-1-0764, and AFOSR-FA9550-13-1-0137. Ping Li thanks Kenneth Church for introducing Google Sets to him in the summer of 2004 at Microsoft Research. 8 References [1] http://www.howtogeek.com/howto/15799/how-to-use-autoﬁll-on-a-google-docs-spreadsheet-quick-tips/. [2] S. Agarwal, Jongwoo Lim, L. Zelnik-Manor, P. Perona, D. Kriegman, and S. Belongie. Beyond pairwise clustering. In CVPR, 2005. [3] Sihem Amer-Yahia, Senjuti Basu Roy, Ashish Chawlat, Gautam Das, and Cong Yu. Group recommendation: semantics and efﬁciency. Proc. VLDB Endow., 2(1):754–765, 2009. [4] Christina Brandt, Thorsten Joachims, Yisong Yue, and Jacob Bank. Dynamic ranked retrieval. In WSDM, pages 247–256, 2011. [5] Andrei Z. Broder. On the resemblance and containment of documents. In the Compression and Complexity of Sequences, pages 21–29, Positano, Italy, 1997. [6] Andrei Z. Broder, Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher. Min-wise independent permutations (extended abstract). In STOC, pages 327–336, Dallas, TX, 1998. [7] Olivier Chapelle, Patrick Haffner, and Vladimir N. Vapnik. Support vector machines for histogram-based image classiﬁcation. IEEE Trans. Neural Networks, 10(5):1055–1064, 1999. [8] Moses S. Charikar. Similarity estimation techniques from rounding algorithms. In STOC, 2002. [9] Flavio Chierichetti and Ravi Kumar. LSH-preserving functions and their applications. In SODA, 2012. [10] Dennis Fetterly, Mark Manasse, Marc Najork, and Janet L. Wiener. A large-scale study of the evolution of web pages. In WWW, pages 669–678, Budapest, Hungary, 2003. [11] Jerome H. Friedman, F. Baskett, and L. Shustek. An algorithm for ﬁnding nearest neighbors. IEEE Transactions on Computers, 24:1000–1006, 1975. [12] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisﬁability problems using semideﬁnite programming. Journal of ACM, 42(6):1115–1145, 1995. [13] Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory of Computing, 8(14):321–350, 2012. [14] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In STOC, pages 604–613, Dallas, TX, 1998. [15] Sergey Ioffe. Improved consistent sampling, weighted minhash and l1 sketching. In ICDM, 2010. [16] Yugang Jiang, Chongwah Ngo, and Jun Yang. Towards optimal bag-of-features for object categorization and semantic video retrieval. In CIVR, pages 494–501, Amsterdam, Netherlands, 2007. [17] Alex Kulesza and Ben Taskar. Determinantal point processes for machine learning. Technical report, arXiv:1207.6083, 2013. [18] Ping Li and Kenneth W. Church. A sketch algorithm for estimating two-way and multi-way associations. Computational Linguistics (Preliminary results appeared in HLT/EMNLP 2005), 33(3):305–354, 2007. [19] Ping Li, Kenneth W. Church, and Trevor J. Hastie. Conditional random sampling: A sketch-based sampling technique for sparse data. In NIPS, pages 873–880, Vancouver, Canada, 2006. [20] Ping Li and Arnd Christian K¨ nig. b-bit minwise hashing. In Proceedings of the 19th International o Conference on World Wide Web, pages 671–680, Raleigh, NC, 2010. [21] Ping Li, Arnd Christian K¨ nig, and Wenhao Gui. b-bit minwise hashing for estimating three-way simio larities. In NIPS, Vancouver, Canada, 2010. [22] Ping Li, Art B Owen, and Cun-Hui Zhang. One permutation hashing. In NIPS, Lake Tahoe, NV, 2012. [23] Ping Li, Anshumali Shrivastava, and Arnd Christian K¨ nig. b-bit minwise hashing in practice. In Intero netware, Changsha, China, 2013. [24] Avner Magen and Anastasios Zouzias. Near optimal dimensionality reductions that preserve volumes. In APPROX / RANDOM, pages 523–534, 2008. [25] Mark Manasse, Frank McSherry, and Kunal Talwar. Consistent weighted sampling. Technical Report MSR-TR-2010-73, Microsoft Research, 2010. [26] Anshumali Shrivastava and Ping Li. Fast near neighbor search in high-dimensional binary data. In ECML, Bristol, UK, 2012. [27] Anshumali Shrivastava and Ping Li. Densifying one permutation hashing via rotation for fast near neighbor search. In ICML, Beijing, China, 2014. [28] Roger Weber, Hans-J¨ rg Schek, and Stephen Blott. A quantitative analysis and performance study for o similarity-search methods in high-dimensional spaces. In VLDB, pages 194–205, 1998. [29] Yair Weiss, Antonio Torralba, and Robert Fergus. Spectral hashing. In NIPS, Vancouver, Canada, 2008. [30] D. Zhou, J. Huang, and B. Sch¨ lkopf. Beyond pairwise classiﬁcation and clustering using hypergraphs. o In NIPS, Vancouver, Canada, 2006. 9

3 0.13279079 218 nips-2013-On Sampling from the Gibbs Distribution with Random Maximum A-Posteriori Perturbations

Author: Tamir Hazan, Subhransu Maji, Tommi Jaakkola

Abstract: In this paper we describe how MAP inference can be used to sample efﬁciently from Gibbs distributions. Speciﬁcally, we provide means for drawing either approximate or unbiased samples from Gibbs’ distributions by introducing low dimensional perturbations and solving the corresponding MAP assignments. Our approach also leads to new ways to derive lower bounds on partition functions. We demonstrate empirically that our method excels in the typical “high signal high coupling” regime. The setting results in ragged energy landscapes that are challenging for alternative approaches to sampling and/or lower bounds. 1

4 0.11940625 326 nips-2013-The Power of Asymmetry in Binary Hashing

Author: Behnam Neyshabur, Nati Srebro, Ruslan Salakhutdinov, Yury Makarychev, Payman Yadollahpour

Abstract: When approximating binary similarity using the hamming distance between short binary hashes, we show that even if the similarity is symmetric, we can have shorter and more accurate hashes by using two distinct code maps. I.e. by approximating the similarity between x and x as the hamming distance between f (x) and g(x ), for two distinct binary codes f, g, rather than as the hamming distance between f (x) and f (x ). 1

5 0.11893788 258 nips-2013-Projecting Ising Model Parameters for Fast Mixing

Author: Justin Domke, Xianghang Liu

Abstract: Inference in general Ising models is difﬁcult, due to high treewidth making treebased algorithms intractable. Moreover, when interactions are strong, Gibbs sampling may take exponential time to converge to the stationary distribution. We present an algorithm to project Ising model parameters onto a parameter set that is guaranteed to be fast mixing, under several divergences. We ﬁnd that Gibbs sampling using the projected parameters is more accurate than with the original parameters when interaction strengths are strong and when limited time is available for sampling.

6 0.097899914 355 nips-2013-Which Space Partitioning Tree to Use for Search?

7 0.080973014 184 nips-2013-Marginals-to-Models Reducibility

8 0.079398178 279 nips-2013-Robust Bloom Filters for Large MultiLabel Classification Tasks

9 0.076258153 169 nips-2013-Learning to Prune in Metric and Non-Metric Spaces

10 0.071372159 132 nips-2013-Global MAP-Optimality by Shrinking the Combinatorial Search Area with Convex Relaxation

11 0.071071416 352 nips-2013-What do row and column marginals reveal about your dataset?

12 0.06893447 123 nips-2013-Flexible sampling of discrete data correlations without the marginal distributions

13 0.064507127 102 nips-2013-Efficient Algorithm for Privately Releasing Smooth Queries

14 0.06278161 188 nips-2013-Memory Limited, Streaming PCA

15 0.062660605 168 nips-2013-Learning to Pass Expectation Propagation Messages

16 0.062438503 161 nips-2013-Learning Stochastic Inverses

17 0.06225821 151 nips-2013-Learning Chordal Markov Networks by Constraint Satisfaction

18 0.060727343 243 nips-2013-Parallel Sampling of DP Mixture Models using Sub-Cluster Splits

19 0.0577485 34 nips-2013-Analyzing Hogwild Parallel Gaussian Gibbs Sampling

20 0.056748617 206 nips-2013-Near-Optimal Entrywise Sampling for Data Matrices

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.187), (1, 0.038), (2, -0.004), (3, 0.006), (4, 0.055), (5, 0.095), (6, 0.064), (7, -0.072), (8, 0.01), (9, 0.057), (10, 0.026), (11, 0.002), (12, 0.054), (13, 0.031), (14, 0.041), (15, 0.006), (16, -0.097), (17, 0.001), (18, 0.003), (19, 0.106), (20, -0.057), (21, -0.034), (22, -0.045), (23, 0.075), (24, 0.038), (25, -0.024), (26, -0.091), (27, -0.017), (28, 0.036), (29, 0.075), (30, 0.023), (31, -0.067), (32, 0.021), (33, 0.085), (34, 0.006), (35, -0.053), (36, -0.091), (37, 0.091), (38, -0.024), (39, -0.216), (40, -0.039), (41, 0.056), (42, -0.03), (43, 0.05), (44, 0.025), (45, 0.011), (46, 0.088), (47, 0.077), (48, -0.028), (49, 0.095)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.91292077 107 nips-2013-Embed and Project: Discrete Sampling with Universal Hashing

Author: Stefano Ermon, Carla P. Gomes, Ashish Sabharwal, Bart Selman

2 0.7495119 57 nips-2013-Beyond Pairwise: Provably Fast Algorithms for Approximate $k$-Way Similarity Search

Author: Anshumali Shrivastava, Ping Li

3 0.70206183 326 nips-2013-The Power of Asymmetry in Binary Hashing

Author: Behnam Neyshabur, Nati Srebro, Ruslan Salakhutdinov, Yury Makarychev, Payman Yadollahpour

4 0.60709727 218 nips-2013-On Sampling from the Gibbs Distribution with Random Maximum A-Posteriori Perturbations

Author: Tamir Hazan, Subhransu Maji, Tommi Jaakkola

5 0.60321158 258 nips-2013-Projecting Ising Model Parameters for Fast Mixing

Author: Justin Domke, Xianghang Liu

6 0.57473689 293 nips-2013-Sign Cauchy Projections and Chi-Square Kernel

7 0.55691522 355 nips-2013-Which Space Partitioning Tree to Use for Search?

8 0.54856962 184 nips-2013-Marginals-to-Models Reducibility

9 0.52676344 34 nips-2013-Analyzing Hogwild Parallel Gaussian Gibbs Sampling

10 0.50646877 94 nips-2013-Distributed $k$-means and $k$-median Clustering on General Topologies

11 0.4985604 168 nips-2013-Learning to Pass Expectation Propagation Messages

12 0.4836868 261 nips-2013-Rapid Distance-Based Outlier Detection via Sampling

13 0.47265533 352 nips-2013-What do row and column marginals reveal about your dataset?

14 0.4678424 36 nips-2013-Annealing between distributions by averaging moments

15 0.45852119 33 nips-2013-An Approximate, Efficient LP Solver for LP Rounding

16 0.45620561 245 nips-2013-Pass-efficient unsupervised feature selection

17 0.45431167 142 nips-2013-Information-theoretic lower bounds for distributed statistical estimation with communication constraints

18 0.45231706 102 nips-2013-Efficient Algorithm for Privately Releasing Smooth Queries

19 0.44251478 152 nips-2013-Learning Efficient Random Maximum A-Posteriori Predictors with Non-Decomposable Loss Functions

20 0.43761882 357 nips-2013-k-Prototype Learning for 3D Rigid Structures

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(2, 0.016), (16, 0.04), (33, 0.141), (34, 0.097), (41, 0.06), (49, 0.033), (56, 0.125), (66, 0.266), (70, 0.031), (85, 0.041), (89, 0.032), (93, 0.028), (95, 0.029)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.7814104 352 nips-2013-What do row and column marginals reveal about your dataset?

Author: Behzad Golshan, John Byers, Evimaria Terzi

Abstract: Numerous datasets ranging from group memberships within social networks to purchase histories on e-commerce sites are represented by binary matrices. While this data is often either proprietary or sensitive, aggregated data, notably row and column marginals, is often viewed as much less sensitive, and may be furnished for analysis. Here, we investigate how these data can be exploited to make inferences about the underlying matrix H. Instead of assuming a generative model for H, we view the input marginals as constraints on the dataspace of possible realizations of H and compute the probability density function of particular entries H(i, j) of interest. We do this for all the cells of H simultaneously, without generating realizations, but rather via implicitly sampling the datasets that satisfy the input marginals. The end result is an efﬁcient algorithm with asymptotic running time the same as that required by standard sampling techniques to generate a single dataset from the same dataspace. Our experimental evaluation demonstrates the efﬁciency and the efﬁcacy of our framework in multiple settings. 1

same-paper 2 0.77154177 107 nips-2013-Embed and Project: Discrete Sampling with Universal Hashing

Author: Stefano Ermon, Carla P. Gomes, Ashish Sabharwal, Bart Selman

3 0.75153917 80 nips-2013-Data-driven Distributionally Robust Polynomial Optimization

Author: Martin Mevissen, Emanuele Ragnoli, Jia Yuan Yu

Abstract: We consider robust optimization for polynomial optimization problems where the uncertainty set is a set of candidate probability density functions. This set is a ball around a density function estimated from data samples, i.e., it is data-driven and random. Polynomial optimization problems are inherently hard due to nonconvex objectives and constraints. However, we show that by employing polynomial and histogram density estimates, we can introduce robustness with respect to distributional uncertainty sets without making the problem harder. We show that the optimum to the distributionally robust problem is the limit of a sequence of tractable semideﬁnite programming relaxations. We also give ﬁnite-sample consistency guarantees for the data-driven uncertainty sets. Finally, we apply our model and solution method in a water network optimization problem. 1

4 0.7410273 353 nips-2013-When are Overcomplete Topic Models Identifiable? Uniqueness of Tensor Tucker Decompositions with Structured Sparsity

Author: Anima Anandkumar, Daniel Hsu, Majid Janzamin, Sham M. Kakade

Abstract: Overcomplete latent representations have been very popular for unsupervised feature learning in recent years. In this paper, we specify which overcomplete models can be identiﬁed given observable moments of a certain order. We consider probabilistic admixture or topic models in the overcomplete regime, where the number of latent topics can greatly exceed the size of the observed word vocabulary. While general overcomplete topic models are not identiﬁable, we establish generic identiﬁability under a constraint, referred to as topic persistence. Our sufﬁcient conditions for identiﬁability involve a novel set of “higher order” expansion conditions on the topic-word matrix or the population structure of the model. This set of higher-order expansion conditions allow for overcomplete models, and require the existence of a perfect matching from latent topics to higher order observed words. We establish that random structured topic models are identiﬁable w.h.p. in the overcomplete regime. Our identiﬁability results allow for general (non-degenerate) distributions for modeling the topic proportions, and thus, we can handle arbitrarily correlated topics in our framework. Our identiﬁability results imply uniqueness of a class of tensor decompositions with structured sparsity which is contained in the class of Tucker decompositions, but is more general than the Candecomp/Parafac (CP) decomposition. Keywords: Overcomplete representation, admixture models, generic identiﬁability, tensor decomposition.

5 0.65243453 11 nips-2013-A New Convex Relaxation for Tensor Completion

Author: Bernardino Romera-Paredes, Massimiliano Pontil

Abstract: We study the problem of learning a tensor from a set of linear measurements. A prominent methodology for this problem is based on a generalization of trace norm regularization, which has been used extensively for learning low rank matrices, to the tensor setting. In this paper, we highlight some limitations of this approach and propose an alternative convex relaxation on the Euclidean ball. We then describe a technique to solve the associated regularization problem, which builds upon the alternating direction method of multipliers. Experiments on one synthetic dataset and two real datasets indicate that the proposed method improves signiﬁcantly over tensor trace norm regularization in terms of estimation error, while remaining computationally tractable. 1

6 0.64631253 318 nips-2013-Structured Learning via Logistic Regression

7 0.64603692 180 nips-2013-Low-rank matrix reconstruction and clustering via approximate message passing

8 0.64558983 282 nips-2013-Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching

9 0.64530158 249 nips-2013-Polar Operators for Structured Sparse Estimation

10 0.64424717 239 nips-2013-Optimistic policy iteration and natural actor-critic: A unifying view and a non-optimality result

11 0.64346373 184 nips-2013-Marginals-to-Models Reducibility

12 0.6430921 311 nips-2013-Stochastic Convex Optimization with Multiple Objectives

13 0.64276695 116 nips-2013-Fantope Projection and Selection: A near-optimal convex relaxation of sparse PCA

14 0.64255798 355 nips-2013-Which Space Partitioning Tree to Use for Search?

15 0.64228851 333 nips-2013-Trading Computation for Communication: Distributed Stochastic Dual Coordinate Ascent

16 0.64208984 45 nips-2013-BIG & QUIC: Sparse Inverse Covariance Estimation for a Million Variables

17 0.64146864 218 nips-2013-On Sampling from the Gibbs Distribution with Random Maximum A-Posteriori Perturbations

18 0.6412642 236 nips-2013-Optimal Neural Population Codes for High-dimensional Stimulus Variables

19 0.64113867 52 nips-2013-Bayesian inference as iterated random functions with applications to sequential inference in graphical models

20 0.64002997 295 nips-2013-Simultaneous Rectification and Alignment via Robust Recovery of Low-rank Tensors