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

300 nips-2013-Solving the multi-way matching problem by permutation synchronization

Source: pdf

Author: Deepti Pachauri, Risi Kondor, Vikas Singh

Abstract: The problem of matching not just two, but m different sets of objects to each other arises in many contexts, including ﬁnding the correspondence between feature points across multiple images in computer vision. At present it is usually solved by matching the sets pairwise, in series. In contrast, we propose a new method, Permutation Synchronization, which ﬁnds all the matchings jointly, in one shot, via a relaxation to eigenvector decomposition. The resulting algorithm is both computationally efﬁcient, and, as we demonstrate with theoretical arguments as well as experimental results, much more stable to noise than previous methods. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 Solving the multi-way matching problem by permutation synchronization Deepti Pachauri,† Risi Kondor§ and Vikas Singh‡† Dept. [sent-1, score-0.925]

2 edu † Abstract The problem of matching not just two, but m different sets of objects to each other arises in many contexts, including ﬁnding the correspondence between feature points across multiple images in computer vision. [sent-10, score-0.409]

3 At present it is usually solved by matching the sets pairwise, in series. [sent-11, score-0.217]

4 In contrast, we propose a new method, Permutation Synchronization, which ﬁnds all the matchings jointly, in one shot, via a relaxation to eigenvector decomposition. [sent-12, score-0.291]

5 1 Introduction Finding the correct bijection between two sets of objects X = {x1 , x2 , . [sent-14, score-0.119]

6 In this paper, we consider its generalization to matching not just two, but m different sets X1 , X2 , . [sent-21, score-0.217]

7 However, our approach is fully general and equally applicable to problems such as matching multiple graphs [10, 11]. [sent-26, score-0.217]

8 Presently, multi-matching is usually solved sequentially, by ﬁrst ﬁnding a putative permutation τ12 matching X1 to X2 , then a permutation τ23 matching X2 to X3 , and so on, up to τm−1,m . [sent-27, score-1.186]

9 While one can conceive of various strategies for optimizing this process, the fact remains that when the data are noisy, a single error in the sequence will typically create a large number of erroneous pairwise matches [12, 13, 14]. [sent-28, score-0.19]

10 For consistency, the recovered matchings must satisfy τkj τji = τki . [sent-30, score-0.205]

11 While ﬁnding an optimal matrix of permutations satisfying these relations is, in general, combinatorially hard, we show that for the most natural choice of loss function the problem has a natural relaxation to just ﬁnding the n leading eigenvectors of the cost matrix. [sent-31, score-0.425]

12 In addition to vastly reducing the computational cost, using recent results from random ( ) theory, we show that the eigenvectors are very effective at aggregating matrix information from all m pairwise matches, and therefore make the algorithm surprisingly robust to 2 noise. [sent-32, score-0.302]

13 Our experiments show that in landmark matching problems Permutation Synchronization can recover the correct correspondence between landmarks across a large number of images with small error, even when a signiﬁcant fraction of the pairwise matches are incorrect. [sent-33, score-0.943]

14 on a similar problem involving ﬁnding the right rotations (rather than matchings) between electron microscopic 1 images [15][16][17]. [sent-35, score-0.088]

15 However, independently of, and concurrently with the present work, Huang and Guibas [18] have recently proposed a semideﬁnite programming based solution, which parallels our approach, and in problems involving occlusion might perform even better. [sent-37, score-0.085]

16 2 Synchronizing permutations Consider a collection of m sets X1 , X2 , . [sent-38, score-0.171]

17 , xi }, such n 1 2 i that for each pair (Xi , Xj ), each xp in Xi has a natural counterpart xj in Xj . [sent-44, score-0.233]

18 For example, in q computer vision, given m images of the same scene taken from different viewpoints, xi , xi , . [sent-45, score-0.196]

19 , xi n 1 2 might be n visual landmarks detected in image i, while xj , xj , . [sent-48, score-0.467]

20 , xj are n landmarks detected in n 1 2 i i image j, in which case xp ∼ xj signiﬁes that xp and xj correspond to the same physical feature. [sent-51, score-0.735]

21 q q i Since the correspondence between Xi and Xj is a bijection, one can write it as xp ∼ xjτji(p) for some permutation τji : {1, 2, . [sent-52, score-0.521]

22 , Xm is consistent if xp ∼ xj and q j k i k xq ∼ x r together imply that xp ∼ x r . [sent-67, score-0.306]

23 In terms of permutations this is equivalent to requiring that the array (τij )m satisfy i,j=1 τkj τji = τki ∀i, j, k. [sent-68, score-0.222]

24 , xn , we can think of each Xi as realizing its own permutation σi (in the sense of xℓ ∼ xi i(ℓ) ), and then τji becomes σ −1 τji = σj σi . [sent-72, score-0.414]

25 Rather, in a typical application we have some tentative (noisy) τji matchings which we ˜ must synchronize into the form (2) by ﬁnding the underlying σ1 , . [sent-79, score-0.205]

26 In this paper we limit ourselves to the simplest choice d(σ, τ ) = n − ⟨P (σ), P (τ )⟩ , where P (σ) ∈ R (4) n×n are the usual permutation matrices { 1 if σ(p) = q [P (σ)]q,p := 0 otherwise, ∑n and ⟨A, B⟩ is the matrix inner product ⟨A, B⟩ := tr(A⊤ B) = p,q=1 Ap,q Bp,q . [sent-88, score-0.45]

27 Intuitively, each Tji is an objective i matrix, the (q, p) element of which captures the utility of matching xp in Xi to xj in Xj . [sent-97, score-0.412]

28 This q i generalization is very useful when the assignments of the different xp ’s have different conﬁdences. [sent-98, score-0.111]

29 For example, in the landmark matching case, if, due to occlusion or for some other reason, the i counterpart of xp is not present in Xj , then we can simply set [Tji ]q,p = 0 for all q. [sent-99, score-0.562]

30 1 Representations and eigenvectors The generalized Permutation Synchronization problem (5) can also be written as maximize ⟨P, T ⟩ , (6) σ1 ,σ2 ,. [sent-101, score-0.143]

31 Tmm (7) A matrix valued function ρ : Sn → Cd×d is said to be a representation of the symmetric group if ρ(σ2 ) ρ(σ1 ) = ρ(σ2 σ1 ) for any pair of permutations σ1 , σ2 ∈ Sn . [sent-135, score-0.26]

32 The synchronization matrix P is of rank n and is of the form P = U · U ⊤ , where   P (σ1 )  . [sent-140, score-0.376]

33 m [P (σm )]ℓ are mutually orthogonal unit eigenvectors of P with the same eigenvalue m, and together span the row/column space of P. [sent-170, score-0.235]

34 The columns of U are orthogonal because the columns of each constituent P (σi ) are orthogonal. [sent-172, score-0.122]

35 However, Proposition 1 and its corollary suggest relaxing it to maximize ⟨P, T ⟩ , n P∈Mm (10) where Mm is the set of mn–dimensional rank n symmetric matrices whose non-zero eigenvalues n are m. [sent-177, score-0.127]

36 , vℓ are the n leading normalized eigenvectors of T . [sent-181, score-0.209]

37 | Thus, in contrast to the original combinatorial problem, (10) can be solved by just ﬁnding the m leading eigenvectors of T . [sent-192, score-0.179]

38 Of course, from P we must still recover the inAlgorithm 1 Permutation Synchronization dividual permutations σ1 , σ2 , . [sent-193, score-0.204]

39 However, as long as P is relatively close in form Input: the objective matrix T Compute the n leading eigenvectors (v1 , v2 , . [sent-197, score-0.223]

40 , vn ) (7), this is quite a simple and stable process. [sent-200, score-0.105]

41 , when Tji = P (˜ji ) for some array (˜ji )j,i of permutations that alτ τ ready satisfy the consistency relations (1), T will have precisely the same structure as described by Proposition 1 for P. [sent-209, score-0.261]

42 In particular, it will have n mutually orthogonal eigenvectors   [P (˜1 )]ℓ σ 1   . [sent-210, score-0.191]

43 Due to the n–fold degeneracy, however, the matrix of eigenvectors (12) is only deﬁned up to multiplication by an arbitrary rotation matrix O on the right, which means that instead of the “correct” U (whose columns are (13)), the eigenvector decomposition of T may return any U ′ = U O. [sent-217, score-0.358]

44 Fortunately, when forming the product P = U′ · U′ ⊤ = U O O⊤ U ⊤ = U · U ⊤ this rotation cancels, conﬁrming that our algorithm recovers P = T , and hence the matchings τji = τji , with no error. [sent-218, score-0.24]

45 ˜ Of course, rather than the case when the solution is handed to us from the start, we are more interested in how the algorithm performs in situations when either the Tji blocks are not permutation matrices, or they are not synchronized. [sent-219, score-0.376]

46 To this end, we set T = T0 + N , (14) where T0 is the correct “ground truth” synchronization matrix, while N is a symmetric perturbation matrix with entries drawn independently from a zero-mean normal distribution with variance η 2 . [sent-220, score-0.508]

47 In general, to ﬁnd the permutation best aligned with a given n × n matrix T , the Kuhn–Munkres algorithm solves for τ = arg maxτ ∈Sn ⟨P (τ ), T ⟩ = arg maxτ ∈Sn (vec(P (τ )) · vec(T )). [sent-221, score-0.42]

48 85} is replaced by a random permutation (m = 100, n = 30). [sent-226, score-0.376]

49 writing T = P (τ0 ) + ϵ, where P (τ0 ) is the “ground truth”, while ϵ is an error term, it is guaranteed to return the correct permutation as long as ∥ vec(ϵ) ∥ < ′ min ∥ vec(τ0 ) − vec(τ ′ ) ∥ /2. [sent-229, score-0.431]

50 , the permutation that swaps 1 with 2 and leaves 3, 4, . [sent-236, score-0.376]

51 The corresponding permutation matrix differs from the idenity in exactly 4 entries, therefore a sufﬁcient condition for correct reconstruction is that √ ∥ϵ∥Frob = ⟨ϵ, ϵ⟩1/2 = ∥vec(ϵ)∥ < 1 4 = 1. [sent-240, score-0.475]

52 As n grows, ∥ϵ∥Frob becomes tightly concentrated 2 around ηn, so the condition for recovering the correct permutation is η < 1/n. [sent-241, score-0.431]

53 Permutation Synchronization can achieve a lower error, especially in the large m regime, because the eigenvectors aggregate information from all the Tji matrices, and tend to be very stable to perturbations. [sent-242, score-0.143]

54 As long as the largest eigenvalue of the random matrix N falls below a given multiple of the smallest non-zero eigenvalue of T0 , adding N will have very little effect on the eigenvectors of T . [sent-244, score-0.275]

55 If N is a symmetric matrix with independent N (0, η 2 ) entries, as nm → ∞, its spectrum will tend to Wigner’s famous semicircle distribution supported on the interval (−2η(nm)1/2 , 2η(nm)1/2 ), and with probability one the largest eigenvalue will approach 2η(nm)1/2 [20, 21]. [sent-246, score-0.218]

56 In contrast, the nonzero eigenvalues of T0 scale with m, which guarantees that for large enough m the two spectra will be nicely separated and Permutation Synchronization will have very low error. [sent-247, score-0.086]

57 max min Below this limit, to quantify the actual expected error, we write each leading normalized eigenvector ∗ ⊥ ∗ v1 , v2 , . [sent-251, score-0.121]

58 , vn of T as vi = vi + vi , where vi is the projection of vi to the space U0 spanned by the 0 0 0 non-zero eigenvectors v1 , v2 , . [sent-254, score-0.693]

59 ⊥ ⊥ ∗ ∗ ⊥ ⊥ It is easy to see that ⟨vi , vj ⟩ − → 0, which implies ⟨vi , vj ⟩ = ⟨vi , vj ⟩ − ⟨vi , vj ⟩ − → 0, − − ∗ ∗ so, setting λ = (1 − η 2 n/m)−1/2 , the normalized vectors λv1 , . [sent-268, score-0.194]

60 In terms of the individual Pji blocks of P = U U ⊤ , neglecting second order terms, 0 0 ⊤ Pji = (Uj + λEj )(Ui0 + λEi )⊤ ≈ P (τji ) + λUj Ei + λEj Ui0⊤ , where τji is the ground truth matching and Ui0 and Ei denote the appropriate n × n submatrices of U 0 and E. [sent-287, score-0.301]

61 1 + 4(m/n)−1 This is much better than our η < 1/n result for the naive algorithm, and remarkably only slightly stricter than the condition η < (m/n)1/2 for recovering the eigenvectors with any accuracy at all. [sent-290, score-0.143]

62 The baseline method is to compute (˜ji )m τ i,j=1 by solving m inde2 pendent linear assignment problems based on matching landmarks by their shape context features [23]. [sent-297, score-0.562]

63 Our method takes the same pairwise matches and synchronizes them with the eigenvector based procedure. [sent-298, score-0.245]

64 Figure 3 shows that this clearly outperforms the baseline, which tends to degrade progressively as the number of images increases. [sent-299, score-0.088]

65 This is due to the fact that the appearance (or descriptors) of keypoints differ considerably for large offset pairs (which is likely when the image set is large), leading to many false matches. [sent-300, score-0.193]

66 While simple, this experiment demonstrates the utility of Permutation Synchronization for multi-view stereo matching, showing that instead of heuristically propagating local pairwise matches, it can ﬁnd a much more accurate globally consistent matching at little additional cost. [sent-302, score-0.475]

67 (Green circles) landmark points, (green lines) ground truth matchings, (red lines) found matches. [sent-311, score-0.233]

68 Next, we considered a dataset with severe geometric ambiguities due to repetitive structures. [sent-315, score-0.099]

69 There is some consensus in the community that even sophisticated features (like SIFT) yield unsatisfactory results in this scenario, and deriving a good initial matching for structure from motion is problematic (see [24] and references therein). [sent-316, score-0.217]

70 Our evaluations included 16 images from the Building dataset [24]. [sent-317, score-0.088]

71 We identiﬁed 25 “similar looking” landmark points in the scene, and hand annotated them across all images. [sent-318, score-0.186]

72 Many landmarks were occluded due to the camera angle. [sent-319, score-0.23]

73 Qualitative results for pairwise matching and Permutation Synchronization are shown in Fig 4 (top). [sent-320, score-0.332]

74 First, our method resolved geometrical ambiguities by enforcing mutual consistency efﬁciently. [sent-322, score-0.13]

75 In contrast, pairwise matching struggles with occlusion in the presence of similar looking landmarks (and feature descriptors). [sent-324, score-0.594]

76 The Books dataset (Fig 4, bottom) contains m = 20 images of multiple books on a “L” shaped study table [24], and suffers geometrical ambiguities similar to the above with severe occlusion. [sent-329, score-0.226]

77 Here we identiﬁed n = 34 landmark points, many of which were occluded in most images. [sent-330, score-0.202]

78 Our ﬁnal experiment deals with matching problems where keypoints in each image preserve a common structure. [sent-335, score-0.374]

79 In the literature, this is usually tackled as a graph matching problem, with the keypoints deﬁning the vertices, and their structural relationships being encoded by the edges of the graph. [sent-336, score-0.33]

80 Ideally, one wants to solve the problem for all images at once but most practical solutions operate on image (or graph) pairs. [sent-337, score-0.172]

81 In contrast, in keypoint matching, the background is not controlled and even sophisticated descriptors may go wrong. [sent-340, score-0.099]

82 Recent solutions often leverage supervision to make the problem tractable [25, 26]. [sent-341, score-0.142]

83 Instead of learning parameters [25, 27], we utilize supervision directly to provide the correct matches on a small subset of randomly picked image pairs (e. [sent-342, score-0.356]

84 For our experiments, we used the baseline method output to set up our objective matrix T but with a ﬁxed “supervision probability”, we replaced the Tji block by the correct permutation matrix, and ran Permutation Synchronization. [sent-346, score-0.524]

85 We considered the “Bikes” sub-class from the Caltech 256 dataset, which contains multiple images of common objects with varying backdrops, and chose to match images in the “touring bike” class. [sent-347, score-0.209]

86 Our analysis included 28 out of 110 images in this dataset that were taken “side-on”. [sent-348, score-0.088]

87 SUSAN corner detector was used to identify landmarks in each image. [sent-349, score-0.177]

88 Further, we identiﬁed 6 interest points in each image that correspond to the frame of the bicycle. [sent-350, score-0.156]

89 We modeled the matching cost for an image pair as the shape distance between interest points in the pair. [sent-351, score-0.392]

90 For a ﬁxed degree of supervision, we randomly selected image pairs for supervision and estimated matchings for the rest of the image pairs. [sent-353, score-0.515]

91 Mean error and standard deviation is shown in Fig 5 as supervision increases. [sent-355, score-0.142]

92 Fig 6 demonstrates qualitative results by our Figure 5: Normalized error as the degree of supervision varies. [sent-356, score-0.142]

93 5 line method PLA (red) and Permutation Synchronization (blue) Conclusions Estimating the correct matching between two sets from noisy similarity data, such as the visual feature based similarity matrices that arise in computer vision is an error-prone process. [sent-358, score-0.302]

94 However, ( ) when we have not just two, but m different sets, the consistency conditions between the m pair2 wise matchings severely constrain the solution. [sent-359, score-0.244]

95 Our eigenvector decomposition based algorithm, Permutation Synchronization, exploits this fact and pools information from all pairwise similarity matrices to jointly estimate a globally consistent array of matchings in a single shot. [sent-360, score-0.487]

96 (Green lines) Ground truth matching for image pairs (left-center) and (center-right). [sent-368, score-0.345]

97 Shape matching and object recognition using low distortion correspondences. [sent-415, score-0.252]

98 Three-dimensional structure determination from common lines in cryo-EM by eigenvectors and semideﬁnite programming. [sent-481, score-0.184]

99 The eigenvalues and eigenvectors of ﬁnite, low rank perturbations of large random matrices. [sent-516, score-0.195]

100 An integer projected ﬁxed point method for graph matching and map inference. [sent-547, score-0.257]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('permutation', 0.376), ('synchronization', 0.332), ('ji', 0.285), ('tji', 0.219), ('matching', 0.217), ('matchings', 0.205), ('landmarks', 0.177), ('permutations', 0.171), ('landmark', 0.149), ('eigenvectors', 0.143), ('supervision', 0.142), ('sn', 0.121), ('pairwise', 0.115), ('stereo', 0.112), ('xp', 0.111), ('vn', 0.105), ('frob', 0.097), ('munkres', 0.097), ('vi', 0.089), ('images', 0.088), ('nm', 0.085), ('fig', 0.085), ('occlusion', 0.085), ('xj', 0.084), ('image', 0.084), ('vec', 0.08), ('matches', 0.075), ('keypoints', 0.073), ('kuhn', 0.068), ('assignment', 0.065), ('green', 0.065), ('wigner', 0.064), ('snavely', 0.064), ('ej', 0.062), ('keypoint', 0.059), ('ei', 0.058), ('ambiguities', 0.056), ('eigenvector', 0.055), ('correct', 0.055), ('shape', 0.054), ('occluded', 0.053), ('eigenvalues', 0.052), ('array', 0.051), ('baseline', 0.049), ('caetano', 0.049), ('curless', 0.049), ('hadani', 0.049), ('pachauri', 0.049), ('risi', 0.049), ('touring', 0.049), ('orthogonal', 0.048), ('books', 0.047), ('wisconsin', 0.047), ('surely', 0.045), ('singer', 0.045), ('symmetric', 0.045), ('house', 0.044), ('truth', 0.044), ('eigenvalue', 0.044), ('matrix', 0.044), ('mcauley', 0.043), ('repetitive', 0.043), ('lines', 0.041), ('vj', 0.041), ('descriptors', 0.04), ('graph', 0.04), ('ground', 0.04), ('hotel', 0.04), ('shot', 0.04), ('consistency', 0.039), ('xi', 0.038), ('points', 0.037), ('bike', 0.037), ('pji', 0.037), ('columns', 0.037), ('leading', 0.036), ('viewpoints', 0.035), ('geometrical', 0.035), ('uj', 0.035), ('rotation', 0.035), ('object', 0.035), ('frame', 0.035), ('correspondence', 0.034), ('spectra', 0.034), ('microscopy', 0.034), ('objects', 0.033), ('xm', 0.033), ('recover', 0.033), ('scene', 0.032), ('entries', 0.032), ('cmu', 0.031), ('bijection', 0.031), ('semide', 0.031), ('red', 0.031), ('globally', 0.031), ('relaxation', 0.031), ('matrices', 0.03), ('normalized', 0.03), ('alignment', 0.03), ('nding', 0.029)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.9999994 300 nips-2013-Solving the multi-way matching problem by permutation synchronization

Author: Deepti Pachauri, Risi Kondor, Vikas Singh

2 0.19734547 306 nips-2013-Speeding up Permutation Testing in Neuroimaging

Author: Chris Hinrichs, Vamsi Ithapu, Qinyuan Sun, Sterling C. Johnson, Vikas Singh

Abstract: Multiple hypothesis testing is a signiﬁcant problem in nearly all neuroimaging studies. In order to correct for this phenomena, we require a reliable estimate of the Family-Wise Error Rate (FWER). The well known Bonferroni correction method, while simple to implement, is quite conservative, and can substantially under-power a study because it ignores dependencies between test statistics. Permutation testing, on the other hand, is an exact, non-parametric method of estimating the FWER for a given α-threshold, but for acceptably low thresholds the computational burden can be prohibitive. In this paper, we show that permutation testing in fact amounts to populating the columns of a very large matrix P. By analyzing the spectrum of this matrix, under certain conditions, we see that P has a low-rank plus a low-variance residual decomposition which makes it suitable for highly sub–sampled — on the order of 0.5% — matrix completion methods. Based on this observation, we propose a novel permutation testing methodology which offers a large speedup, without sacriﬁcing the ﬁdelity of the estimated FWER. Our evaluations on four different neuroimaging datasets show that a computational speedup factor of roughly 50× can be achieved while recovering the FWER distribution up to very high accuracy. Further, we show that the estimated α-threshold is also recovered faithfully, and is stable. 1

3 0.18589784 282 nips-2013-Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching

Author: Marcelo Fiori, Pablo Sprechmann, Joshua Vogelstein, Pablo Muse, Guillermo Sapiro

Abstract: Graph matching is a challenging problem with very important applications in a wide range of ﬁelds, from image and video analysis to biological and biomedical problems. We propose a robust graph matching algorithm inspired in sparsityrelated techniques. We cast the problem, resembling group or collaborative sparsity formulations, as a non-smooth convex optimization problem that can be efﬁciently solved using augmented Lagrangian techniques. The method can deal with weighted or unweighted graphs, as well as multimodal data, where different graphs represent different types of data. The proposed approach is also naturally integrated with collaborative graph inference techniques, solving general network inference problems where the observed variables, possibly coming from different modalities, are not in correspondence. The algorithm is tested and compared with state-of-the-art graph matching techniques in both synthetic and real graphs. We also present results on multimodal graphs and applications to collaborative inference of brain connectivity from alignment-free functional magnetic resonance imaging (fMRI) data. The code is publicly available. 1

4 0.14163652 73 nips-2013-Convex Relaxations for Permutation Problems

Author: Fajwel Fogel, Rodolphe Jenatton, Francis Bach, Alexandre D'Aspremont

Abstract: Seriation seeks to reconstruct a linear order between variables using unsorted similarity information. It has direct applications in archeology and shotgun gene sequencing for example. We prove the equivalence between the seriation and the combinatorial 2-SUM problem (a quadratic minimization problem over permutations) over a class of similarity matrices. The seriation problem can be solved exactly by a spectral algorithm in the noiseless case and we produce a convex relaxation for the 2-SUM problem to improve the robustness of solutions in a noisy setting. This relaxation also allows us to impose additional structural constraints on the solution, to solve semi-supervised seriation problems. We present numerical experiments on archeological data, Markov chains and gene sequences. 1

5 0.11115441 5 nips-2013-A Deep Architecture for Matching Short Texts

Author: Zhengdong Lu, Hang Li

Abstract: Many machine learning problems can be interpreted as learning for matching two types of objects (e.g., images and captions, users and products, queries and documents, etc.). The matching level of two objects is usually measured as the inner product in a certain feature space, while the modeling effort focuses on mapping of objects from the original space to the feature space. This schema, although proven successful on a range of matching tasks, is insufﬁcient for capturing the rich structure in the matching process of more complicated objects. In this paper, we propose a new deep architecture to more effectively model the complicated matching relations between two objects from heterogeneous domains. More speciﬁcally, we apply this model to matching tasks in natural language, e.g., ﬁnding sensible responses for a tweet, or relevant answers to a given question. This new architecture naturally combines the localness and hierarchy intrinsic to the natural language problems, and therefore greatly improves upon the state-of-the-art models. 1

6 0.097466275 169 nips-2013-Learning to Prune in Metric and Non-Metric Spaces

7 0.095354952 224 nips-2013-On the Sample Complexity of Subspace Learning

8 0.091105901 155 nips-2013-Learning Hidden Markov Models from Non-sequence Data via Tensor Decomposition

9 0.090989433 192 nips-2013-Minimax Theory for High-dimensional Gaussian Mixtures with Sparse Mean Separation

10 0.089754805 324 nips-2013-The Fast Convergence of Incremental PCA

11 0.079355441 288 nips-2013-Scalable Influence Estimation in Continuous-Time Diffusion Networks

12 0.07533212 114 nips-2013-Extracting regions of interest from biological images with convolutional sparse block coding

13 0.068802953 25 nips-2013-Adaptive Anonymity via $b$-Matching

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

15 0.066116311 113 nips-2013-Exact and Stable Recovery of Pairwise Interaction Tensors

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

17 0.063611157 349 nips-2013-Visual Concept Learning: Combining Machine Vision and Bayesian Generalization on Concept Hierarchies

18 0.062539309 166 nips-2013-Learning invariant representations and applications to face verification

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

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

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.187), (1, 0.102), (2, -0.007), (3, 0.042), (4, 0.045), (5, -0.012), (6, -0.014), (7, -0.046), (8, -0.094), (9, 0.033), (10, -0.023), (11, -0.011), (12, 0.09), (13, -0.001), (14, -0.02), (15, 0.051), (16, -0.026), (17, -0.071), (18, -0.15), (19, 0.042), (20, 0.025), (21, -0.101), (22, -0.043), (23, 0.024), (24, -0.052), (25, -0.102), (26, -0.019), (27, 0.109), (28, -0.137), (29, 0.056), (30, 0.066), (31, 0.078), (32, -0.015), (33, 0.094), (34, 0.002), (35, 0.057), (36, -0.014), (37, -0.065), (38, 0.091), (39, 0.144), (40, 0.044), (41, 0.001), (42, 0.152), (43, 0.027), (44, 0.066), (45, 0.098), (46, -0.005), (47, 0.041), (48, -0.05), (49, 0.093)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.95001423 300 nips-2013-Solving the multi-way matching problem by permutation synchronization

Author: Deepti Pachauri, Risi Kondor, Vikas Singh

2 0.71426803 282 nips-2013-Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching

Author: Marcelo Fiori, Pablo Sprechmann, Joshua Vogelstein, Pablo Muse, Guillermo Sapiro

3 0.65412706 306 nips-2013-Speeding up Permutation Testing in Neuroimaging

Author: Chris Hinrichs, Vamsi Ithapu, Qinyuan Sun, Sterling C. Johnson, Vikas Singh

4 0.64037043 73 nips-2013-Convex Relaxations for Permutation Problems

Author: Fajwel Fogel, Rodolphe Jenatton, Francis Bach, Alexandre D'Aspremont

5 0.5171842 25 nips-2013-Adaptive Anonymity via $b$-Matching

Author: Krzysztof M. Choromanski, Tony Jebara, Kui Tang

Abstract: The adaptive anonymity problem is formalized where each individual shares their data along with an integer value to indicate their personal level of desired privacy. This problem leads to a generalization of k-anonymity to the b-matching setting. Novel algorithms and theory are provided to implement this type of anonymity. The relaxation achieves better utility, admits theoretical privacy guarantees that are as strong, and, most importantly, accommodates a variable level of anonymity for each individual. Empirical results conﬁrm improved utility on benchmark and social data-sets.

6 0.4989545 350 nips-2013-Wavelets on Graphs via Deep Learning

7 0.49529329 207 nips-2013-Near-optimal Anomaly Detection in Graphs using Lovasz Extended Scan Statistic

8 0.49052674 316 nips-2013-Stochastic blockmodel approximation of a graphon: Theory and consistent estimation

9 0.48643494 114 nips-2013-Extracting regions of interest from biological images with convolutional sparse block coding

10 0.47030145 130 nips-2013-Generalizing Analytic Shrinkage for Arbitrary Covariance Structures

11 0.46971893 195 nips-2013-Modeling Clutter Perception using Parametric Proto-object Partitioning

12 0.46306449 324 nips-2013-The Fast Convergence of Incremental PCA

13 0.46288866 357 nips-2013-k-Prototype Learning for 3D Rigid Structures

14 0.44948852 145 nips-2013-It is all in the noise: Efficient multi-task Gaussian process inference with structured residuals

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

16 0.44272575 302 nips-2013-Sparse Inverse Covariance Estimation with Calibration

17 0.43814194 117 nips-2013-Fast Algorithms for Gaussian Noise Invariant Independent Component Analysis

18 0.43801779 284 nips-2013-Robust Spatial Filtering with Beta Divergence

19 0.4354319 138 nips-2013-Higher Order Priors for Joint Intrinsic Image, Objects, and Attributes Estimation

20 0.42696649 153 nips-2013-Learning Feature Selection Dependencies in Multi-task Learning

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(16, 0.028), (33, 0.183), (34, 0.104), (41, 0.021), (49, 0.042), (56, 0.098), (70, 0.039), (80, 0.226), (85, 0.06), (89, 0.044), (93, 0.071), (95, 0.015)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.84556764 300 nips-2013-Solving the multi-way matching problem by permutation synchronization

Author: Deepti Pachauri, Risi Kondor, Vikas Singh

2 0.81991714 295 nips-2013-Simultaneous Rectification and Alignment via Robust Recovery of Low-rank Tensors

Author: Xiaoqin Zhang, Di Wang, Zhengyuan Zhou, Yi Ma

Abstract: In this work, we propose a general method for recovering low-rank three-order tensors, in which the data can be deformed by some unknown transformation and corrupted by arbitrary sparse errors. Since the unfolding matrices of a tensor are interdependent, we introduce auxiliary variables and relax the hard equality constraints by the augmented Lagrange multiplier method. To improve the computational efﬁciency, we introduce a proximal gradient step to the alternating direction minimization method. We have provided proof for the convergence of the linearized version of the problem which is the inner loop of the overall algorithm. Both simulations and experiments show that our methods are more efﬁcient and effective than previous work. The proposed method can be easily applied to simultaneously rectify and align multiple images or videos frames. In this context, the state-of-the-art algorithms “RASL” and “TILT” can be viewed as two special cases of our work, and yet each only performs part of the function of our method.

3 0.74043268 285 nips-2013-Robust Transfer Principal Component Analysis with Rank Constraints

Author: Yuhong Guo

Abstract: Principal component analysis (PCA), a well-established technique for data analysis and processing, provides a convenient form of dimensionality reduction that is effective for cleaning small Gaussian noises presented in the data. However, the applicability of standard principal component analysis in real scenarios is limited by its sensitivity to large errors. In this paper, we tackle the challenge problem of recovering data corrupted with errors of high magnitude by developing a novel robust transfer principal component analysis method. Our method is based on the assumption that useful information for the recovery of a corrupted data matrix can be gained from an uncorrupted related data matrix. Speciﬁcally, we formulate the data recovery problem as a joint robust principal component analysis problem on the two data matrices, with common principal components shared across matrices and individual principal components speciﬁc to each data matrix. The formulated optimization problem is a minimization problem over a convex objective function but with non-convex rank constraints. We develop an efﬁcient proximal projected gradient descent algorithm to solve the proposed optimization problem with convergence guarantees. Our empirical results over image denoising tasks show the proposed method can effectively recover images with random large errors, and signiﬁcantly outperform both standard PCA and robust PCA with rank constraints. 1

4 0.74011421 251 nips-2013-Predicting Parameters in Deep Learning

Author: Misha Denil, Babak Shakibi, Laurent Dinh, Marc'Aurelio Ranzato, Nando de Freitas

Abstract: We demonstrate that there is signiﬁcant redundancy in the parameterization of several deep learning models. Given only a few weight values for each feature it is possible to accurately predict the remaining values. Moreover, we show that not only can the parameter values be predicted, but many of them need not be learned at all. We train several different architectures by learning only a small number of weights and predicting the rest. In the best case we are able to predict more than 95% of the weights of a network without any drop in accuracy. 1

5 0.7373631 22 nips-2013-Action is in the Eye of the Beholder: Eye-gaze Driven Model for Spatio-Temporal Action Localization

Author: Nataliya Shapovalova, Michalis Raptis, Leonid Sigal, Greg Mori

Abstract: We propose a weakly-supervised structured learning approach for recognition and spatio-temporal localization of actions in video. As part of the proposed approach, we develop a generalization of the Max-Path search algorithm which allows us to efﬁciently search over a structured space of multiple spatio-temporal paths while also incorporating context information into the model. Instead of using spatial annotations in the form of bounding boxes to guide the latent model during training, we utilize human gaze data in the form of a weak supervisory signal. This is achieved by incorporating eye gaze, along with the classiﬁcation, into the structured loss within the latent SVM learning framework. Experiments on a challenging benchmark dataset, UCF-Sports, show that our model is more accurate, in terms of classiﬁcation, and achieves state-of-the-art results in localization. In addition, our model can produce top-down saliency maps conditioned on the classiﬁcation label and localized latent paths. 1

6 0.73649359 99 nips-2013-Dropout Training as Adaptive Regularization

7 0.73580015 331 nips-2013-Top-Down Regularization of Deep Belief Networks

8 0.73576331 190 nips-2013-Mid-level Visual Element Discovery as Discriminative Mode Seeking

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

10 0.73533767 114 nips-2013-Extracting regions of interest from biological images with convolutional sparse block coding

11 0.73482478 335 nips-2013-Transfer Learning in a Transductive Setting

12 0.73453617 275 nips-2013-Reservoir Boosting : Between Online and Offline Ensemble Learning

13 0.73344529 304 nips-2013-Sparse nonnegative deconvolution for compressive calcium imaging: algorithms and phase transitions

14 0.73343593 153 nips-2013-Learning Feature Selection Dependencies in Multi-task Learning

15 0.73311311 30 nips-2013-Adaptive dropout for training deep neural networks

16 0.73236579 333 nips-2013-Trading Computation for Communication: Distributed Stochastic Dual Coordinate Ascent

17 0.73176426 301 nips-2013-Sparse Additive Text Models with Low Rank Background

18 0.73156595 183 nips-2013-Mapping paradigm ontologies to and from the brain

19 0.73123431 201 nips-2013-Multi-Task Bayesian Optimization

20 0.73109472 64 nips-2013-Compete to Compute