nips nips2012 nips2012-334 knowledge-graph by maker-knowledge-mining

334 nips-2012-Tensor Decomposition for Fast Parsing with Latent-Variable PCFGs

Source: pdf

Author: Michael Collins, Shay B. Cohen

Abstract: We describe an approach to speed-up inference with latent-variable PCFGs, which have been shown to be highly effective for natural language parsing. Our approach is based on a tensor formulation recently introduced for spectral estimation of latent-variable PCFGs coupled with a tensor decomposition algorithm well-known in the multilinear algebra literature. We also describe an error bound for this approximation, which gives guarantees showing that if the underlying tensors are well approximated, then the probability distribution over trees will also be well approximated. Empirical evaluation on real-world natural language parsing data demonstrates a signiﬁcant speed-up at minimal cost for parsing performance. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract We describe an approach to speed-up inference with latent-variable PCFGs, which have been shown to be highly effective for natural language parsing. [sent-4, score-0.069]

2 Our approach is based on a tensor formulation recently introduced for spectral estimation of latent-variable PCFGs coupled with a tensor decomposition algorithm well-known in the multilinear algebra literature. [sent-5, score-1.454]

3 We also describe an error bound for this approximation, which gives guarantees showing that if the underlying tensors are well approximated, then the probability distribution over trees will also be well approximated. [sent-6, score-0.413]

4 Empirical evaluation on real-world natural language parsing data demonstrates a signiﬁcant speed-up at minimal cost for parsing performance. [sent-7, score-0.509]

5 1 Introduction Latent variable models have shown great success in various ﬁelds, including computational linguistics and machine learning. [sent-8, score-0.066]

6 In computational linguistics, for example, latent-variable models are widely used for natural language parsing using models called latent-variable PCFGs (L-PCFGs; [14]). [sent-9, score-0.259]

7 The mainstay for estimation of L-PCFGs has been the expectation-maximization algorithm [14, 16], though other algorithms, such as spectral algorithms, have been devised [5]. [sent-10, score-0.078]

8 A by-product of the spectral algorithm presented in [5] is a tensor formulation for computing the inside-outside probabilities of a L-PCFG. [sent-11, score-0.681]

9 Tensor products (or matrix-vector products, in certain cases) are used as the basic operation for marginalization over the latent annotations of the L-PCFG. [sent-12, score-0.083]

10 The computational complexity with the tensor formulation (or with plain CKY, for that matter) is cubic in the number of latent states in the L-PCFG. [sent-13, score-0.83]

11 In this paper, we show that tensor decomposition can be used to signiﬁcantly speed-up the parsing performance with L-PCFGs. [sent-15, score-0.946]

12 Our approach is also provided with a theoretical guarantee: given the accuracy of the tensor decomposition, one can compute how accurate the approximate parser is. [sent-16, score-0.748]

13 We will make use of tensors of rank 3:1 1 All PCFGs in this paper are assumed to be in Chomsky normal form. [sent-25, score-0.283]

14 Our approach generalizes to arbitrary PCFGs, which require tensors of higher rank. [sent-26, score-0.283]

15 A tensor C ∈ R(m×m×m) is a set of m3 parameters Ci,j,k for i, j, k ∈ [m]. [sent-28, score-0.602]

16 Given a tensor C, and vectors y 1 ∈ Rm and y 2 ∈ Rm , we deﬁne C(y 1 , y 2 ) to be the m-dimensional row 1 2 vector with components [C(y 1 , y 2 )]i = j∈[m],k∈[m] Ci,j,k yj yk . [sent-29, score-0.712]

17 In addition, we deﬁne the tensor C(1,2) ∈ R(m×m×m) for any tensor C ∈ R(m×m×m) to be the 1 2 function C(1,2) : Rm × Rm → Rm×1 deﬁned as [C(1,2) (y 1 , y 2 )]k = i∈[m],j∈[m] Ci,j,k yi yj . [sent-31, score-1.265]

18 Similarly, for any tensor C we deﬁne C(1,3) : Rm × Rm → Rm×1 as [C(1,3) (y 1 , y 2 )]j = 1 2 1 2 1 2 i∈[m],k∈[m] Ci,j,k yi yk . [sent-32, score-0.651]

19 Finally, for vectors x, y, z ∈ Rm , xy z is the tensor D ∈ Rm×m×m where Di,j,k = xi yj zk (this is analogous to the outer product: [xy ]i,j = xi yj ). [sent-37, score-0.757]

20 3 Latent-Variable Parsing In this section we describe latent-variable PCFGs and their parsing algorithms. [sent-38, score-0.24]

21 • For all a ∈ I, b ∈ N, c ∈ N, h1 , h2 , h3 ∈ [m], we have a context-free rule a(h1 ) → b(h2 ) c(h3 ). [sent-48, score-0.059]

22 • For all a ∈ P, h ∈ [m], x ∈ [n], we have a context-free rule a(h) → x. [sent-49, score-0.059]

23 An L-PCFG corresponds to a regular PCFG with non-terminals annotated with latent states. [sent-54, score-0.106]

24 For each triplet of latent states and a rule a → b c, we have a rule probability p(a(h1 ) → b(h2 ) c(h3 )|a(h1 )) = t(a → b c, h2 , h3 |h1 , a). [sent-55, score-0.25]

25 In addition, there are initial probabilities of generating a non-terminal with a latent at the top of the tree, denoted by π(a, h). [sent-57, score-0.083]

26 L-PCFGs induce distributions over two type of trees: skeletal trees, i. [sent-58, score-0.265]

27 trees without values for latent states (these trees are observed in data), and full trees (trees with values for latent states). [sent-60, score-0.53]

28 A skeletal tree consists of a sequence of rules r1 . [sent-61, score-0.403]

29 We now turn to the problem of computing the probability of a skeletal tree, by marginalizing out the latent states of full trees. [sent-67, score-0.424]

30 rN be a derivation, and let ai be the non-terminal on the left (2) hand-side of rule ri . [sent-71, score-0.167]

31 For any ri = a → b c, deﬁne hi to be the latent state associated with the left (3) child of the rule ri and hi to be the hidden variable value associated with the right child. [sent-72, score-0.524]

32 The distribution over full trees is then: (2) p(r1 . [sent-73, score-0.105]

33 hN ) = π(a1 , h1 ) × (3) t(ri , hi , hi |hi , ai ) × i:ai ∈I 2 q(ri |hi , ai ) i:ai ∈P S1 NP2 VP5 D3 N4 V6 P7 the man saw him r1 r2 r3 r4 r5 r6 r7 = S → NP VP = NP → D N = D → the = N → man = VP → V P = V → saw = P → him Figure 1: An s-tree with its sequence of rules. [sent-79, score-0.392]

34 (The nodes in the tree are indexed by the derivation order, which is canonicalized as top-down, left-most derviation. [sent-80, score-0.11]

35 ) Marginalizing out the latent states leads to the distribution over the skeletal tree r1 . [sent-81, score-0.507]

36 For example, vanilla EM has been used in [14], hierarchical state splitting EM has been suggested in [16], and a spectral algorithm is proposed in [5]. [sent-103, score-0.125]

37 In the rest of the paper, we assume that the parameters for these tensors have been identiﬁed, and focus mostly on the problem of inference – i. [sent-104, score-0.306]

38 The reason for this linear complexity is that the skeletal trees are observed during EM training. [sent-108, score-0.37]

39 2 Tensor Formulation for Inside-Outside There are several ways to parse a sentence with latent-variable PCFGs. [sent-111, score-0.349]

40 Most of these approaches are taken by using an inside-outside algorithm [12] which computes marginals for various non-terminals and spans in the sentence, and then eventually ﬁnding a parse tree which maximizes a score which is the sum of the marginals of the spans that appear in the tree. [sent-112, score-0.535]

41 Here T(x) denotes the set of all possible s-trees for the sentence x, and we write (a, i, j) ∈ τ if non-terminal a spans words xi . [sent-114, score-0.264]

42 Then, the parsing algorithm seeks for a given sentence x = x1 . [sent-118, score-0.422]

43 xN the skeletal tree arg maxτ ∈T(x) (a,i,j)∈τ µ(a, i, j). [sent-121, score-0.375]

44 Given the marginals µ(a, i, j), one can use the dynamic programming algorithm described in [7] in order to ﬁnd this highest scoring tree. [sent-122, score-0.151]

45 A key question is how to compute the marginals µ(a, i, j) using the inside-outside algorithm. [sent-123, score-0.072]

46 The complexity of a na¨ve imı plementation of the dynamic programming algorithm for this problem is cubic in the number of latent states. [sent-125, score-0.233]

47 This is where we suggest an alternative to the traditional dynamic programming solutions. [sent-126, score-0.079]

48 Our alternative relies on an existing tensor formulation for the inside-outside algorithm [5], which re-formalizes the dynamic programming algorithm using tensor, matrix and vector product operations. [sent-127, score-0.706]

49 The re-formalized algorithm is still cubic in 3 the number of hidden states, and spends most of the time computing the tensor applications b→c b→a T a→b c (αb,i,k , αc,k+1,j ), T(1,2) a (β b,k,j , αc,k,i−1 ) and T(1,3) c (β b,i,k , αc,j+1,k ). [sent-130, score-0.704]

50 4 Tensor Decomposition As mentioned earlier, most computation for the inside-outside algorithm is spent on the tensor calculation of T a→b c on the intermediate inside/outside quantities. [sent-140, score-0.602]

51 For the rest of this section, ﬁx a binary grammar rule a → b c and consider the tensor T T a→b c associated with it. [sent-143, score-0.719]

52 Consider a pair of two vectors y 1 , y 2 ∈ Rm , associated with the distributions over latent-states for the left (y 1 ) and right child (y 2 ) of a given node in a parse tree. [sent-144, score-0.267]

53 Our method for improving the speed of this tensor computation relies on a simple observation. [sent-145, score-0.602]

54 Given an integer r ≥ 1, assume that the tensor T had the following special form, which is also called “Kruskal form”, r T = i=1 ui vi wi , i. [sent-146, score-0.783]

55 it would be the sum of r tensors, each is the tensor product of three vectors. [sent-148, score-0.602]

56 In that case, the cost of computing T (y 1 , y 2 ) could be greatly reduced by computing: r T (y 1 , y 2 ) = r ui vi wi i=1 (y 1 , y 2 ) = ui (vi y 1 )(wi y 2 ) = U (V y 1 W y2 ) (1) i=1 where U, V, W ∈ Rr×m with the ith row being ui , vi and wi respectively. [sent-149, score-0.371]

57 4 We note that it is well-known that an exact tensor decomposition can be achieved by using r = m2 [11]. [sent-152, score-0.731]

58 The minimal r required for an exact solution can be smaller than m2 , but identifying that minimal r is NP-hard [9]. [sent-154, score-0.07]

59 1 CP Decomposition of Tensors In the general case, for a ﬁxed r, our latent-variable PCFG tensors will not have the exact decomposed form from the previous section. [sent-157, score-0.283]

60 Still, by using decomposition algorithms from multilinear algebra, we can approximate the latent-variable tensors, where the quality of approximation is measured according to some norm over the set of tensors Rm×m×m . [sent-158, score-0.454]

61 An example of such a decomposition is the canonical polyadic decomposition (CPD), also known as CANDECOMP/PARAFAC decomposition [3, 8, 10]. [sent-159, score-0.387]

62 Given an integer r, least squares CPD aims to ﬁnd the nearest tensor in Kruskal form according to the analogous norm (for tensors) to the Frobenius norm (for matrices). [sent-160, score-0.698]

63 More formally, for a given tensor D ∈ Rm×m×m , let ||D||F = tensors in Kruskal form Cr be: i,j,k 2 Di,j,k . [sent-161, score-0.885]

64 Let the set of r Cr = {C ∈ Rm×m×m | C = ui vi wi s. [sent-162, score-0.155]

65 i=1 ˆ ˆ ˆ The least squares CPD of C is a tensor C such that C ∈ arg minC∈Cr ||C − C||F . [sent-165, score-0.672]

66 ˆ There are various algorithms to perform CPD, such as alternating least squares, direct linear decomposition, alternating trilinear decomposition and pseudo alternating least squares [6]. [sent-166, score-0.392]

67 Most of these implementations treat the problem of identifying the approximate tensor as an optimization problem. [sent-167, score-0.602]

68 We note that the decomposition optimization problem is hard, and often has multiple local maxima. [sent-170, score-0.129]

69 In our experiments, we use the alternating least squares algorithm. [sent-172, score-0.118]

70 1 (until convergence), each time solving a least squares problem. [sent-174, score-0.07]

71 2 Propagation of Errors We next present a theoretical guarantee about the quality of the CP-approximated tensor formulation of the inside-outside algorithm. [sent-176, score-0.627]

72 We measure the propagation of errors in probability calculations through a given parse tree. [sent-177, score-0.142]

73 We denote by p the distribution induced over trees (skeletal and full), where we approximate each ˆ a→b c ˆ T using the tensor T a→b c . [sent-179, score-0.707]

74 2 is the result of applying Cauchy-Schwarz inequality twice: 2  ||C(y 1 , y 2 )||2 = 2 = ||C||2 F i j,k · ||y 1 ||2 2 · ||y 2 ||2 2 5    1 2 Ci,j,k yj yk  ≤  i  2 Ci,j,k   1 (yj )2  j,k j 2 (yk )2 k (3) For Eq. [sent-186, score-0.11]

75 Let d∗ = where γ is the the “tensor approximalog(2( m + 1)) + log(γ + m) ˆ tion error” deﬁned as γ = maxa→b c ||T a→b c − T a→b c ||F , then: • For a given skeletal tree r1 , . [sent-189, score-0.375]

76 , rN ) can be computed by using a sequence of applications of T a→b c on distribution over latent states for left and right children. [sent-210, score-0.132]

77 ˆ Deﬁne the same quantities y i , only using the approximate tensors T a→b c . [sent-212, score-0.283]

78 We ˆ ˆ will prove inductively that if di is the depth of the subtree at node i, then: δi ≤ min γm √ √ d (2( m + 1)(γ + m)) i − 1 √ √ 2( m + 1)(γ + m) − 1 ,1 For any leaf node (base case): ||y i − y i ||2 = 0. [sent-214, score-0.262]

79 5 20 q q −10 q q −5 q q log threshold threshold seconds per sentence F1 seconds per sentence F1 seconds per sentence F1 no approx. [sent-217, score-1.007]

80 14 Figure 3: Speed and performance of parsing with tensor decomposition for m ∈ {8, 16, 20} (left plots, middle plots and right plots respectively). [sent-260, score-0.946]

81 The left y axis is running time (red circles), the right y axis is F1 performance of the parser (blue squares), the x axis corresponds to log t. [sent-261, score-0.32]

82 Solid lines describe decomposition with r = 2, dashed lines describe decomposition with r = 8. [sent-262, score-0.308]

83 1 and the fact that √ √ ˆ ˆ ||T a→b c ||F ≤ ||T a→b c −T a→b c ||F +||T a→b c ||F ≤ γ + m and ||ˆk ||2 ≤ δk +||y k ||2 ≤ 1+ m y for any node k (under ind. [sent-267, score-0.076]

84 2 log(4|N|) + log(2( m + 1)) + log(γ + m) As expected, the longer a sentence is, or the deeper a parse tree is, the better we need the tensor approximation to be (smaller γ) for the inside-outside to be more accurate. [sent-286, score-1.061]

85 Our goal is to evaluate the trade-off between the accuracy of the tensor decomposition and the speed-up in the parsing algorithm. [sent-288, score-0.946]

86 Whenever we report parsing accuracy, we use the traditional F1 measure from the Parseval metric [2]. [sent-290, score-0.215]

87 It computes the F1 measure of spans (a, i, j) appearing in the gold standard and the hypothesized trees. [sent-291, score-0.082]

88 The total number of tensors extracted from the training data using EM was 7,236 (corresponding ˆ to the number of grammar rules). [sent-292, score-0.318]

89 001, 10 , 10 , 10 , 0} – an approximate tensor T a→b c is used a→b c instead of T only if γa→b c ≤ t. [sent-296, score-0.602]

90 The value t = 0 implies using vanilla inference, without any approximate tensors. [sent-297, score-0.071]

91 For the tensor approximation, we use the implementation provided in the Matlab tensor toolbox from [1]. [sent-299, score-1.235]

92 As is common, we use a pruning technique to make the parser faster – items in the dynamic programming chart are pruned if their value according to a base vanilla maximum likelihood model is less than 0. [sent-301, score-0.373]

93 We note that the performance of the parser improves as we add more latent states. [sent-306, score-0.229]

94 The performance of the parser with vanilla PCFG (m = 1) is 70. [sent-307, score-0.217]

95 The reason for this happening is that with r = 8, more of the tensors have an approximation error which is smaller than t, and therefore more approximate tensors are used than in the case of r = 2. [sent-312, score-0.566]

96 More specifically, for r = 8, it takes 72% of the time (without considering the pruning phase) of the nonapproximate parser to parse section 22 with m = 8, 24% of the time with m = 16 and 21% of the time with m = 20. [sent-315, score-0.332]

97 The approach approximates tensors which are used in the inside-outside algorithm. [sent-323, score-0.283]

98 We note that tensor formulations are used with graphical models [15], for which our technique is also applicable. [sent-326, score-0.602]

99 Similarly, our technique can be applied to other dynamic programming algorithms which compute marginals of a given statistical model. [sent-327, score-0.151]

100 Algorithm 862: MATLAB tensor classes for fast algorithm prototyping. [sent-333, score-0.602]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('tensor', 0.602), ('tensors', 0.283), ('skeletal', 0.265), ('parsing', 0.215), ('sentence', 0.207), ('pcfgs', 0.2), ('rm', 0.166), ('parser', 0.146), ('parse', 0.142), ('decomposition', 0.129), ('tree', 0.11), ('cpd', 0.109), ('trees', 0.105), ('qa', 0.095), ('hi', 0.09), ('latent', 0.083), ('rn', 0.08), ('node', 0.076), ('em', 0.073), ('marginals', 0.072), ('kruskal', 0.072), ('log', 0.072), ('cubic', 0.071), ('vanilla', 0.071), ('squares', 0.07), ('pcfg', 0.067), ('ri', 0.061), ('ui', 0.061), ('yj', 0.061), ('rule', 0.059), ('spans', 0.057), ('acl', 0.056), ('santorini', 0.055), ('seconds', 0.054), ('spectral', 0.054), ('states', 0.049), ('yk', 0.049), ('child', 0.049), ('alternating', 0.048), ('wi', 0.048), ('ai', 0.047), ('cr', 0.046), ('vi', 0.046), ('treebank', 0.044), ('penn', 0.044), ('pruning', 0.044), ('language', 0.044), ('vp', 0.042), ('multilinear', 0.042), ('marcus', 0.042), ('linguistics', 0.041), ('programming', 0.04), ('threshold', 0.04), ('hn', 0.04), ('dynamic', 0.039), ('recursion', 0.038), ('lesser', 0.037), ('minimal', 0.035), ('grammar', 0.035), ('axis', 0.034), ('base', 0.033), ('english', 0.033), ('xy', 0.033), ('man', 0.032), ('subtree', 0.032), ('hidden', 0.031), ('toolbox', 0.031), ('cohen', 0.031), ('collins', 0.031), ('outside', 0.03), ('inside', 0.029), ('rules', 0.028), ('np', 0.028), ('saw', 0.027), ('leaf', 0.027), ('marginalizing', 0.027), ('di', 0.027), ('triangle', 0.026), ('integer', 0.026), ('formulation', 0.025), ('appearing', 0.025), ('describe', 0.025), ('various', 0.025), ('induction', 0.024), ('per', 0.024), ('parafac', 0.024), ('abney', 0.024), ('latentvariable', 0.024), ('trilinear', 0.024), ('inductively', 0.024), ('catalan', 0.024), ('cfg', 0.024), ('matsuzaki', 0.024), ('miyao', 0.024), ('roukos', 0.024), ('jelinek', 0.024), ('mainstay', 0.024), ('harrison', 0.024), ('rest', 0.023), ('annotated', 0.023)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999994 334 nips-2012-Tensor Decomposition for Fast Parsing with Latent-Variable PCFGs

Author: Michael Collins, Shay B. Cohen

2 0.22500965 318 nips-2012-Sparse Approximate Manifolds for Differential Geometric MCMC

Author: Ben Calderhead, Mátyás A. Sustik

Abstract: One of the enduring challenges in Markov chain Monte Carlo methodology is the development of proposal mechanisms to make moves distant from the current point, that are accepted with high probability and at low computational cost. The recent introduction of locally adaptive MCMC methods based on the natural underlying Riemannian geometry of such models goes some way to alleviating these problems for certain classes of models for which the metric tensor is analytically tractable, however computational efﬁciency is not assured due to the necessity of potentially high-dimensional matrix operations at each iteration. In this paper we ﬁrstly investigate a sampling-based approach for approximating the metric tensor and suggest a valid MCMC algorithm that extends the applicability of Riemannian Manifold MCMC methods to statistical models that do not admit an analytically computable metric tensor. Secondly, we show how the approximation scheme we consider naturally motivates the use of 1 regularisation to improve estimates and obtain a sparse approximate inverse of the metric, which enables stable and sparse approximations of the local geometry to be made. We demonstrate the application of this algorithm for inferring the parameters of a realistic system of ordinary differential equations using a biologically motivated robust Student-t error model, for which the Expected Fisher Information is analytically intractable. 1

3 0.2151642 9 nips-2012-A Geometric take on Metric Learning

Author: Søren Hauberg, Oren Freifeld, Michael J. Black

Abstract: Multi-metric learning techniques learn local metric tensors in different parts of a feature space. With such an approach, even simple classiﬁers can be competitive with the state-of-the-art because the distance measure locally adapts to the structure of the data. The learned distance measure is, however, non-metric, which has prevented multi-metric learning from generalizing to tasks such as dimensionality reduction and regression in a principled way. We prove that, with appropriate changes, multi-metric learning corresponds to learning the structure of a Riemannian manifold. We then show that this structure gives us a principled way to perform dimensionality reduction and regression according to the learned metrics. Algorithmically, we provide the ﬁrst practical algorithm for computing geodesics according to the learned metrics, as well as algorithms for computing exponential and logarithmic maps on the Riemannian manifold. Together, these tools let many Euclidean algorithms take advantage of multi-metric learning. We illustrate the approach on regression and dimensionality reduction tasks that involve predicting measurements of the human body from shape data. 1 Learning and Computing Distances Statistics relies on measuring distances. When the Euclidean metric is insufﬁcient, as is the case in many real problems, standard methods break down. This is a key motivation behind metric learning, which strives to learn good distance measures from data. In the most simple scenarios a single metric tensor is learned, but in recent years, several methods have proposed learning multiple metric tensors, such that different distance measures are applied in different parts of the feature space. This has proven to be a very powerful approach for classiﬁcation tasks [1, 2], but the approach has not generalized to other tasks. Here we consider the generalization of Principal Component Analysis (PCA) and linear regression; see Fig. 1 for an illustration of our approach. The main problem with generalizing multi-metric learning is that it is based on assumptions that make the feature space both non-smooth and non-metric. Speciﬁcally, it is often assumed that straight lines form geodesic curves and that the metric tensor stays constant along these lines. These assumptions are made because it is believed that computing the actual geodesics is intractable, requiring a discretization of the entire feature space [3]. We solve these problems by smoothing the transitions between different metric tensors, which ensures a metric space where geodesics can be computed. In this paper, we consider the scenario where the metric tensor at a given point in feature space is deﬁned as the weighted average of a set of learned metric tensors. In this model, we prove that the feature space becomes a chart for a Riemannian manifold. This ensures a metric feature space, i.e. dist(x, y) = 0 ⇔ x = y , dist(x, y) = dist(y, x) (symmetry), (1) dist(x, z) ≤ dist(x, y) + dist(y, z) (triangle inequality). To compute statistics according to the learned metric, we need to be able to compute distances, which implies that we need to compute geodesics. Based on the observation that geodesics are 1 (a) Local Metrics & Geodesics (b) Tangent Space Representation (c) First Principal Geodesic Figure 1: Illustration of Principal Geodesic Analysis. (a) Geodesics are computed between the mean and each data point. (b) Data is mapped to the Euclidean tangent space and the ﬁrst principal component is computed. (c) The principal component is mapped back to the feature space. smooth curves in Riemannian spaces, we derive an algorithm for computing geodesics that only requires a discretization of the geodesic rather than the entire feature space. Furthermore, we show how to compute the exponential and logarithmic maps of the manifold. With this we can map any point back and forth between a Euclidean tangent space and the manifold. This gives us a general strategy for incorporating the learned metric tensors in many Euclidean algorithms: map the data to the tangent of the manifold, perform the Euclidean analysis and map the results back to the manifold. Before deriving the algorithms (Sec. 3) we set the scene by an analysis of the shortcomings of current state-of-the-art methods (Sec. 2), which motivate our ﬁnal model. The model is general and can be used for many problems. Here we illustrate it with several challenging problems in 3D body shape modeling and analysis (Sec. 4). All proofs can be found in the supplementary material along with algorithmic details and further experimental results. 2 Background and Related Work Single-metric learning learns a metric tensor, M, such that distances are measured as dist2 (xi , xj ) = xi − xj 2 M ≡ (xi − xj )T M(xi − xj ) , (2) where M is a symmetric and positive deﬁnite D × D matrix. Classic approaches for ﬁnding such a metric tensor include PCA, where the metric is given by the inverse covariance matrix of the training data; and linear discriminant analysis (LDA), where the metric tensor is M = S−1 SB S−1 , with Sw W W and SB being the within class scatter and the between class scatter respectively [9]. A more recent approach tries to learn a metric tensor from triplets of data points (xi , xj , xk ), where the metric should obey the constraint that dist(xi , xj ) < dist(xi , xk ). Here the constraints are often chosen such that xi and xj belong to the same class, while xi and xk do not. Various relaxed versions of this idea have been suggested such that the metric can be learned by solving a semi-deﬁnite or a quadratic program [1, 2, 4–8]. Among the most popular approaches is the Large Margin Nearest Neighbor (LMNN) classiﬁer [5], which ﬁnds a linear transformation that satisﬁes local distance constraints, making the approach suitable for multi-modal classes. For many problems, a single global metric tensor is not enough, which motivates learning several local metric tensors. The classic work by Hastie and Tibshirani [9] advocates locally learning metric tensors according to LDA and using these as part of a kNN classiﬁer. In a somewhat similar fashion, Weinberger and Saul [5] cluster the training data and learn a separate metric tensor for each cluster using LMNN. A more extreme point of view was taken by Frome et al. [1, 2], who learn a diagonal metric tensor for every point in the training set, such that distance rankings are preserved. Similarly, Malisiewicz and Efros [6] ﬁnd a diagonal metric tensor for each training point such that the distance to a subset of the training data from the same class is kept small. Once a set of metric tensors {M1 , . . . , MR } has been learned, the distance dist(a, b) is measured according to (2) where “the nearest” metric tensor is used, i.e. R M(x) = r=1 wr (x) ˜ Mr , where wr (x) = ˜ ˜ j wj (x) 1 0 x − xr 2 r ≤ x − xj M otherwise 2 Mj , ∀j , (3) where x is either a or b depending on the algorithm. Note that this gives a non-metric distance function as it is not symmetric. To derive this equation, it is necessary to assume that 1) geodesics 2 −8 −8 Assumed Geodesics Location of Metric Tensors Test Points −6 −8 Actual Geodesics Location of Metric Tensors Test Points −6 Riemannian Geodesics Location of Metric Tensors Test Points −6 −4 −4 −4 −2 −2 −2 0 0 0 2 2 2 4 4 4 6 −8 6 −8 −6 −4 −2 0 (a) 2 4 6 −6 −4 −2 0 2 4 6 6 −8 −6 (b) −4 −2 (c) 0 2 4 6 (d) Figure 2: (a)–(b) An illustrative example where straight lines do not form geodesics and where the metric tensor does not stay constant along lines; see text for details. The background color is proportional to the trace of the metric tensor, such that light grey corresponds to regions where paths are short (M1 ), and dark grey corresponds to regions they are long (M2 ). (c) The suggested geometric model along with the geodesics. Again, background colour is proportional to the trace of the metric tensor; the colour scale is the same is used in (a) and (b). (d) An illustration of the exponential and logarithmic maps. form straight lines, and 2) the metric tensor stays constant along these lines [3]. Both assumptions are problematic, which we illustrate with a simple example in Fig. 2a–c. Assume we are given two metric tensors M1 = 2I and M2 = I positioned at x1 = (2, 2)T and x2 = (4, 4)T respectively. This gives rise to two regions in feature space in which x1 is nearest in the ﬁrst and x2 is nearest in the second, according to (3). This is illustrated in Fig. 2a. In the same ﬁgure, we also show the assumed straight-line geodesics between selected points in space. As can be seen, two of the lines goes through both regions, such that the assumption of constant metric tensors along the line is violated. Hence, it would seem natural to measure the length of the line, by adding the length of the line segments which pass through the different regions of feature space. This was suggested by Ramanan and Baker [3] who also proposed a polynomial time algorithm for measuring these line lengths. This gives a symmetric distance function. Properly computing line lengths according to the local metrics is, however, not enough to ensure that the distance function is metric. As can be seen in Fig. 2a the straight line does not form a geodesic as a shorter path can be found by circumventing the region with the “expensive” metric tensor M1 as illustrated in Fig. 2b. This issue makes it trivial to construct cases where the triangle inequality is violated, which again makes the line length measure non-metric. In summary, if we want a metric feature space, we can neither assume that geodesics are straight lines nor that the metric tensor stays constant along such lines. In practice, good results have been reported using (3) [1,3,5], so it seems obvious to ask: is metricity required? For kNN classiﬁers this does not appear to be the case, with many successes based on dissimilarities rather than distances [10]. We, however, want to generalize PCA and linear regression, which both seek to minimize the reconstruction error of points projected onto a subspace. As the notion of projection is hard to deﬁne sensibly in non-metric spaces, we consider metricity essential. In order to build a model with a metric feature space, we change the weights in (3) to be smooth functions. This impose a well-behaved geometric structure on the feature space, which we take advantage of in order to perform statistical analysis according to the learned metrics. However, ﬁrst we review the basics of Riemannian geometry as this provides the theoretical foundation of our work. 2.1 Geodesics and Riemannian Geometry We start by deﬁning Riemannian manifolds, which intuitively are smoothly curved spaces equipped with an inner product. Formally, they are smooth manifolds endowed with a Riemannian metric [11]: Deﬁnition A Riemannian metric M on a manifold M is a smoothly varying inner product < a, b >x = aT M(x)b in the tangent space Tx M of each point x ∈ M . 3 Often Riemannian manifolds are represented by a chart; i.e. a parameter space for the curved surface. An example chart is the spherical coordinate system often used to represent spheres. While such charts are often ﬂat spaces, the curvature of the manifold arises from the smooth changes in the metric. On a Riemannian manifold M, the length of a smooth curve c : [0, 1] → M is deﬁned as the integral of the norm of the tangent vector (interpreted as speed) along the curve: 1 Length(c) = 1 c (λ) M(c(λ)) dλ c (λ)T M(c(λ))c (λ)dλ , = (4) 0 0 where c denotes the derivative of c and M(c(λ)) is the metric tensor at c(λ). A geodesic curve is then a length-minimizing curve connecting two given points x and y, i.e. (5) cgeo = arg min Length(c) with c(0) = x and c(1) = y . c The distance between x and y is deﬁned as the length of the geodesic. Given a tangent vector v ∈ Tx M, there exists a unique geodesic cv (t) with initial velocity v at x. The Riemannian exponential map, Expx , maps v to a point on the manifold along the geodesic cv at t = 1. This mapping preserves distances such that dist(cv (0), cv (1)) = v . The inverse of the exponential map is the Riemannian logarithmic map denoted Logx . Informally, the exponential and logarithmic maps move points back and forth between the manifold and the tangent space while preserving distances (see Fig. 2d for an illustration). This provides a general strategy for generalizing many Euclidean techniques to Riemannian domains: data points are mapped to the tangent space, where ordinary Euclidean techniques are applied and the results are mapped back to the manifold. 3 A Metric Feature Space With the preliminaries settled we deﬁne the new model. Let C = RD denote the feature space. We endow C with a metric tensor in every point x, which we deﬁne akin to (3), R M(x) = wr (x)Mr , where wr (x) = r=1 wr (x) ˜ R ˜ j=1 wj (x) , (6) with wr > 0. The only difference from (3) is that we shall not restrict ourselves to binary weight ˜ functions wr . We assume the metric tensors Mr have already been learned; Sec. 4 contain examples ˜ where they have been learned using LMNN [5] and LDA [9]. From the deﬁnition of a Riemannian metric, we trivially have the following result: Lemma 1 The space C = RD endowed with the metric tensor from (6) is a chart of a Riemannian manifold, iff the weights wr (x) change smoothly with x. Hence, by only considering smooth weight functions wr we get a well-studied geometric structure ˜ on the feature space, which ensures us that it is metric. To illustrate the implications we return to the example in Fig. 2. We change the weight functions from binary to squared exponentials, which gives the feature space shown in Fig. 2c. As can be seen, the metric tensor now changes smoothly, which also makes the geodesics smooth curves (a property we will use when computing the geodesics). It is worth noting that Ramanan and Baker [3] also consider the idea of smoothly averaging the metric tensor. They, however, only evaluate the metric tensor at the test point of their classiﬁer and then assume straight line geodesics with a constant metric tensor. Such assumptions violate the premise of a smoothly changing metric tensor and, again, the distance measure becomes non-metric. Lemma 1 shows that metric learning can be viewed as manifold learning. The main difference between our approach and techniques such as Isomap [12] is that, while Isomap learns an embedding of the data points, we learn the actual manifold structure. This gives us the beneﬁt that we can compute geodesics as well as the exponential and logarithmic maps. These provide us with mappings back and forth between the manifold and Euclidean representation of the data, which preserve distances as well as possible. The availability of such mappings is in stark contrast to e.g. Isomap. In the next section we will derive a system of ordinary differential equations (ODE’s) that geodesics in C have to satisfy, which provides us with algorithms for computing geodesics as well as exponential and logarithmic maps. With these we can generalize many Euclidean techniques. 4 3.1 Computing Geodesics, Maps and Statistics At minima of (4) we know that the Euler-Lagrange equation must hold [11], i.e. ∂L d ∂L , where L(λ, c, c ) = c (λ)T M(c(λ))c (λ) . = ∂c dλ ∂c As we have an explicit expression for the metric tensor we can compute (7) in closed form: (7) Theorem 2 Geodesic curves in C satisfy the following system of 2nd order ODE’s M(c(λ))c (λ) = − 1 ∂vec [M(c(λ))] 2 ∂c(λ) T (c (λ) ⊗ c (λ)) , (8) where ⊗ denotes the Kronecker product and vec [·] stacks the columns of a matrix into a vector [13]. Proof See supplementary material. This result holds for any smooth weight functions wr . We, however, still need to compute ∂vec[M] , ˜ ∂c which depends on the speciﬁc choice of wr . Any smooth weighting scheme is applicable, but we ˜ restrict ourselves to the obvious smooth generalization of (3) and use squared exponentials. From this assumption, we get the following result Theorem 3 For wr (x) = exp − ρ x − xr ˜ 2 ∂vec [M(c)] = ∂c the derivative of the metric tensor from (6) is R ρ R j=1 2 Mr R 2 wj ˜ T r=1 T wj (c − xj ) Mj − (c − xr ) Mr ˜ wr vec [Mr ] ˜ . (9) j=1 Proof See supplementary material. Computing Geodesics. Any geodesic curve must be a solution to (8). Hence, to compute a geodesic between x and y, we can solve (8) subject to the constraints c(0) = x and c(1) = y . (10) This is a boundary value problem, which has a smooth solution. This allows us to solve the problem numerically using a standard three-stage Lobatto IIIa formula, which provides a fourth-order accurate C 1 –continuous solution [14]. Ramanan and Baker [3] discuss the possibility of computing geodesics, but arrive at the conclusion that this is intractable based on the assumption that it requires discretizing the entire feature space. Our solution avoids discretizing the feature space by discretizing the geodesic curve instead. As this is always one-dimensional the approach remains tractable in high-dimensional feature spaces. Computing Logarithmic Maps. Once a geodesic c is found, it follows from the deﬁnition of the logarithmic map, Logx (y), that it can be computed as v = Logx (y) = c (0) Length(c) . c (0) (11) In practice, we solve (8) by rewriting it as a system of ﬁrst order ODE’s, such that we compute both c and c simultaneously (see supplementary material for details). Computing Exponential Maps. Given a starting point x on the manifold and a vector v in the tangent space, the exponential map, Expx (v), ﬁnds the unique geodesic starting at x with initial velocity v. As the geodesic must fulﬁll (8), we can compute the exponential map by solving this system of ODE’s with the initial conditions c(0) = x and c (0) = v . (12) This initial value problem has a unique solution, which we ﬁnd numerically using a standard RungeKutta scheme [15]. 5 3.1.1 Generalizing PCA and Regression At this stage, we know that the feature space is Riemannian and we know how to compute geodesics and exponential and logarithmic maps. We now seek to generalize PCA and linear regression, which becomes straightforward since solutions are available in Riemannian spaces [16, 17]. These generalizations can be summarized as mapping the data to the tangent space at the mean, performing standard Euclidean analysis in the tangent and mapping the results back. The ﬁrst step is to compute the mean value on the manifold, which is deﬁned as the point that minimizes the sum-of-squares distances to the data points. Pennec [18] provides an efﬁcient gradient descent approach for computing this point, which we also summarize in the supplementary material. The empirical covariance of a set of points is deﬁned as the ordinary Euclidean covariance in the tangent space at the mean value [18]. With this in mind, it is not surprising that the principal components of a dataset have been generalized as the geodesics starting at the mean with initial velocity corresponding to the eigenvectors of the covariance [16], γvd (t) = Expµ (tvd ) , (13) th where vd denotes the d eigenvector of the covariance. This approach is called Principal Geodesic Analysis (PGA), and the geodesic curve γvd is called the principal geodesic. An illustration of the approach can be seen in Fig. 1 and more algorithmic details are in the supplementary material. Linear regression has been generalized in a similar way [17] by performing regression in the tangent of the mean and mapping the resulting line back to the manifold using the exponential map. The idea of working in the tangent space is both efﬁcient and convenient, but comes with an element of approximation as the logarithmic map is only guarantied to preserve distances to the origin of the tangent and not between all pairs of data points. Practical experience, however, indicates that this is a good tradeoff; see [19] for a more in-depth discussion of when the approximation is suitable. 4 Experiments To illustrate the framework1 we consider an example in human body analysis, and then we analyze the scalability of the approach. But ﬁrst, to build intuition, Fig. 3a show synthetically generated data samples from two classes. We sample random points xr and learn a local LDA metric [9] by considering all data points within a radius; this locally pushes the two classes apart. We combine the local metrics using (6) and Fig. 3b show the data in the tangent space of the resulting manifold. As can be seen the two classes are now globally further apart, which shows the effect of local metrics. 4.1 Human Body Shape We consider a regression example concerning human body shape analysis. We study 986 female body laser scans from the CAESAR [20] data set; each shape is represented using the leading 35 principal components of the data learned using a SCAPE-like model [21, 22]. Each shape is associated with anthropometric measurements such as body height, shoe size, etc. We show results for shoulder to wrist distance and shoulder breadth, but results for more measurements are in the supplementary material. To predict the measurements from shape coefﬁcients, we learn local metrics and perform linear regression according to these. As a further experiment, we use PGA to reduce the dimensionality of the shape coefﬁcients according to the local metrics, and measure the quality of the reduction by performing linear regression to predict the measurements. As a baseline we use the corresponding Euclidean techniques. To learn the local metric we do the following. First we whiten the data such that the variance captured by PGA will only be due to the change of metric; this allows easy visualization of the impact of the learned metrics. We then cluster the body shapes into equal-sized clusters according to the measurement and learn a LMNN metric for each cluster [5], which we associate with the mean of each class. These push the clusters apart, which introduces variance along the directions where the measurement changes. From this we construct a Riemannian manifold according to (6), 1 Our software implementation for computing geodesics and performing manifold statistics is available at http://ps.is.tue.mpg.de/project/Smooth Metric Learning 6 30 Euclidean Model Riemannian Model 24 20 18 16 20 15 10 5 14 12 0 (a) 25 22 Running Time (sec.) Average Prediction Error 26 10 (b) 20 Dimensionality 0 0 30 50 (c) 100 Dimensionality 150 (d) 4 3 3 2 2 1 1 0 −1 −2 −3 −4 −4 −3 −2 −1 0 1 2 3 4 Shoulder breadth 20 −2 −3 Euclidean Model Riemannian Model 0 −1 25 Prediction Error 4 15 10 0 −4 −5 0 4 10 15 20 Dimensionality 16 25 30 35 17 3 3 5 5 Euclidean Model Riemannian Model 2 15 2 1 1 Prediction Error Shoulder to wrist distance Figure 3: Left panels: Synthetic data. (a) Samples from two classes along with illustratively sampled metric tensors from (6). (b) The data represented in the tangent of a manifold constructed from local LDA metrics learned at random positions. Right panels: Real data. (c) Average error of linearly predicted body measurements (mm). (d) Running time (sec) of the geodesic computation as a function of dimensionality. 0 0 −1 −2 −1 −3 14 13 12 11 −2 −4 −3 −4 −4 10 −5 −3 −2 −1 0 1 Euclidean PCA 2 3 −6 −4 9 0 −2 0 2 4 Tangent Space PCA (PGA) 6 5 10 15 20 Dimensionality 25 30 35 Regression Error Figure 4: Left: body shape data in the ﬁrst two principal components according to the Euclidean metric. Point color indicates cluster membership. Center: As on the left, but according to the Riemannian model. Right: regression error as a function of the dimensionality of the shape space; again the Euclidean metric and the Riemannian metric are compared. compute the mean value on the manifold, map the data to the tangent space at the mean and perform linear regression in the tangent space. As a ﬁrst visualization we plot the data expressed in the leading two dimensions of PGA in Fig. 4; as can be seen the learned metrics provide principal geodesics, which are more strongly related with the measurements than the Euclidean model. In order to predict the measurements from the body shape, we perform linear regression, both directly in the shape space according to the Euclidean metric and in the tangent space of the manifold corresponding to the learned metrics (using the logarithmic map from (11)). We measure the prediction error using leave-one-out cross-validation. To further illustrate the power of the PGA model, we repeat this experiment for different dimensionalities of the data. The results are plotted in Fig. 4, showing that regression according to the learned metrics outperforms the Euclidean model. To verify that the learned metrics improve accuracy, we average the prediction errors over all millimeter measurements. The result in Fig. 3c shows that much can be gained in lower dimensions by using the local metrics. To provide visual insights into the behavior of the learned metrics, we uniformly sample body shape along the ﬁrst principal geodesic (in the range ±7 times the standard deviation) according to the different metrics. The results are available as a movie in the supplementary material, but are also shown in Fig. 5. As can be seen, the learned metrics pick up intuitive relationships between body shape and the measurements, e.g. shoulder to wrist distance is related to overall body size, while shoulder breadth is related to body weight. 7 Shoulder to wrist distance Shoulder breadth Figure 5: Shapes corresponding to the mean (center) and ±7 times the standard deviations along the principal geodesics (left and right). Movies are available in the supplementary material. 4.2 Scalability The human body data set is small enough (986 samples in 35 dimensions) that computing a geodesic only takes a few seconds. To show that the current unoptimized Matlab implementation can handle somewhat larger datasets, we brieﬂy consider a dimensionality reduction task on the classic MNIST handwritten digit data set. We use the preprocessed data available with [3] where the original 28×28 gray scale images were deskewed and projected onto their leading 164 Euclidean principal components (which captures 95% of the variance in the original data). We learn one diagonal LMNN metric per class, which we associate with the mean of the class. From this we construct a Riemannian manifold from (6), compute the mean value on the manifold and compute geodesics between the mean and each data point; this is the computationally expensive part of performing PGA. Fig. 3d plots the average running time (sec) for the computation of geodesics as a function of the dimensionality of the training data. A geodesic can be computed in 100 dimensions in approximately 5 sec., whereas in 150 dimensions it takes about 30 sec. In this experiment, we train a PGA model on 60,000 data points, and test a nearest neighbor classiﬁer in the tangent space as we decrease the dimensionality of the model. Compared to a Euclidean model, this gives a modest improvement in classiﬁcation accuracy of 2.3 percent, when averaged across different dimensionalities. Plots of the results can be found in the supplementary material. 5 Discussion This work shows that multi-metric learning techniques are indeed applicable outside the realm of kNN classiﬁers. The idea of deﬁning the metric tensor at any given point as the weighted average of a ﬁnite set of learned metrics is quite natural from a modeling point of view, which is also validated by the Riemannian structure of the resulting space. This opens both a theoretical and a practical toolbox for analyzing and developing algorithms that use local metric tensors. Speciﬁcally, we show how to use local metric tensors for both regression and dimensionality reduction tasks. Others have attempted to solve non-classiﬁcation problems using local metrics, but we feel that our approach is the ﬁrst to have a solid theoretical backing. For example, Hastie and Tibshirani [9] use local LDA metrics for dimensionality reduction by averaging the local metrics and using the resulting metric as part of a Euclidean PCA, which essentially is a linear approach. Another approach was suggested by Hong et al. [23] who simply compute the principal components according to each metric separately, such that one low dimensional model is learned per metric. The suggested approach is, however, not difﬁculty-free in its current implementation. Currently, we are using off-the-shelf numerical solvers for computing geodesics, which can be computationally demanding. While we managed to analyze medium-sized datasets, we believe that the run-time can be drastically improved by developing specialized numerical solvers. In the experiments, we learned local metrics using techniques specialized for classiﬁcation tasks as this is all the current literature provides. We expect improvements by learning the metrics speciﬁcally for regression and dimensionality reduction, but doing so is currently an open problem. Acknowledgments: Søren Hauberg is supported in part by the Villum Foundation, and Oren Freifeld is supported in part by NIH-NINDS EUREKA (R01-NS066311). 8 References [1] Andrea Frome, Yoram Singer, and Jitendra Malik. Image retrieval and classiﬁcation using local distance functions. In B. Sch¨ lkopf, J. Platt, and T. Hoffman, editors, Advances in Neural Information Processing o Systems 19 (NIPS), pages 417–424, Cambridge, MA, 2007. MIT Press. [2] Andrea Frome, Fei Sha, Yoram Singer, and Jitendra Malik. Learning globally-consistent local distance functions for shape-based image retrieval and classiﬁcation. In International Conference on Computer Vision (ICCV), pages 1–8, 2007. [3] Deva Ramanan and Simon Baker. Local distance functions: A taxonomy, new algorithms, and an evaluation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(4):794–806, 2011. [4] Shai Shalev-Shwartz, Yoram Singer, and Andrew Y. Ng. Online and batch learning of pseudo-metrics. In Proceedings of the twenty-ﬁrst international conference on Machine learning, ICML ’04, pages 94–101. ACM, 2004. [5] Kilian Q. Weinberger and Lawrence K. Saul. Distance metric learning for large margin nearest neighbor classiﬁcation. The Journal of Machine Learning Research, 10:207–244, 2009. [6] Tomasz Malisiewicz and Alexei A. Efros. Recognition by association via learning per-exemplar distances. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 1–8, 2008. [7] Yiming Ying and Peng Li. Distance metric learning with eigenvalue optimization. The Journal of Machine Learning Research, 13:1–26, 2012. [8] Matthew Schultz and Thorsten Joachims. Learning a distance metric from relative comparisons. In Advances in Neural Information Processing Systems 16 (NIPS), 2004. [9] Trevor Hastie and Robert Tibshirani. Discriminant adaptive nearest neighbor classiﬁcation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(6):607–616, June 1996. [10] Elzbieta Pekalska, Pavel Paclik, and Robert P. W. Duin. A generalized kernel approach to dissimilaritybased classiﬁcation. Journal of Machine Learning Research, 2:175–211, 2002. [11] Manfredo Perdigao do Carmo. Riemannian Geometry. Birkh¨ user Boston, January 1992. a [12] Joshua B. Tenenbaum, Vin De Silva, and John C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319–2323, 2000. [13] Jan R. Magnus and Heinz Neudecker. Matrix Differential Calculus with Applications in Statistics and Econometrics. John Wiley & Sons, 2007. [14] Jacek Kierzenka and Lawrence F. Shampine. A BVP solver based on residual control and the Matlab PSE. ACM Transactions on Mathematical Software, 27(3):299–316, 2001. [15] John R. Dormand and P. J. Prince. A family of embedded Runge-Kutta formulae. Journal of Computational and Applied Mathematics, 6:19–26, 1980. [16] P. Thomas Fletcher, Conglin Lu, Stephen M. Pizer, and Sarang Joshi. Principal Geodesic Analysis for the study of Nonlinear Statistics of Shape. IEEE Transactions on Medical Imaging, 23(8):995–1005, 2004. [17] Peter E. Jupp and John T. Kent. Fitting smooth paths to spherical data. Applied Statistics, 36(1):34–46, 1987. [18] Xavier Pennec. Probabilities and statistics on Riemannian manifolds: Basic tools for geometric measurements. In Proceedings of Nonlinear Signal and Image Processing, pages 194–198, 1999. [19] Stefan Sommer, Francois Lauze, Søren Hauberg, and Mads Nielsen. Manifold valued statistics, exact ¸ principal geodesic analysis and the effect of linear approximations. In European Conference on Computer Vision (ECCV), pages 43–56, 2010. [20] Kathleen M. Robinette, Hein Daanen, and Eric Paquet. The CAESAR project: a 3-D surface anthropometry survey. In 3-D Digital Imaging and Modeling, pages 380–386, 1999. [21] Dragomir Anguelov, Praveen Srinivasan, Daphne Koller, Sebastian Thrun, Jim Rodgers, and James Davis. Scape: shape completion and animation of people. ACM Transactions on Graphics, 24(3):408–416, 2005. [22] Oren Freifeld and Michael J. Black. Lie bodies: A manifold representation of 3D human shape. In A. Fitzgibbon et al. (Eds.), editor, European Conference on Computer Vision (ECCV), Part I, LNCS 7572, pages 1–14. Springer-Verlag, oct 2012. [23] Yi Hong, Quannan Li, Jiayan Jiang, and Zhuowen Tu. Learning a mixture of sparse distance metrics for classiﬁcation and dimensionality reduction. In International Conference on Computer Vision (ICCV), pages 906–913, 2011. 9

4 0.21376412 156 nips-2012-Identifiability and Unmixing of Latent Parse Trees

Author: Percy Liang, Daniel J. Hsu, Sham M. Kakade

Abstract: This paper explores unsupervised learning of parsing models along two directions. First, which models are identiﬁable from inﬁnite data? We use a general technique for numerically checking identiﬁability based on the rank of a Jacobian matrix, and apply it to several standard constituency and dependency parsing models. Second, for identiﬁable models, how do we estimate the parameters efﬁciently? EM suffers from local optima, while recent work using spectral methods [1] cannot be directly applied since the topology of the parse tree varies across sentences. We develop a strategy, unmixing, which deals with this additional complexity for restricted classes of parsing models. 1

5 0.16950879 173 nips-2012-Learned Prioritization for Trading Off Accuracy and Speed

Author: Jiarong Jiang, Adam Teichert, Jason Eisner, Hal Daume

Abstract: Users want inference to be both fast and accurate, but quality often comes at the cost of speed. The ﬁeld has experimented with approximate inference algorithms that make different speed-accuracy tradeoffs (for particular problems and datasets). We aim to explore this space automatically, focusing here on the case of agenda-based syntactic parsing [12]. Unfortunately, off-the-shelf reinforcement learning techniques fail to learn good policies: the state space is simply too large to explore naively. An attempt to counteract this by applying imitation learning algorithms also fails: the “teacher” follows a far better policy than anything in our learner’s policy space, free of the speed-accuracy tradeoff that arises when oracle information is unavailable, and thus largely insensitive to the known reward functﬁon. We propose a hybrid reinforcement/apprenticeship learning algorithm that learns to speed up an initial policy, trading off accuracy for speed according to various settings of a speed term in the loss function. 1

6 0.11050036 19 nips-2012-A Spectral Algorithm for Latent Dirichlet Allocation

7 0.10049325 180 nips-2012-Learning Mixtures of Tree Graphical Models

8 0.096543543 172 nips-2012-Latent Graphical Model Selection: Efficient Methods for Locally Tree-like Graphs

9 0.089736462 54 nips-2012-Bayesian Probabilistic Co-Subspace Addition

10 0.087135881 22 nips-2012-A latent factor model for highly multi-relational data

11 0.085262567 260 nips-2012-Online Sum-Product Computation Over Trees

12 0.082705833 339 nips-2012-The Time-Marginalized Coalescent Prior for Hierarchical Clustering

13 0.076218374 206 nips-2012-Majorization for CRFs and Latent Likelihoods

14 0.069866091 124 nips-2012-Factorial LDA: Sparse Multi-Dimensional Text Models

15 0.067436226 151 nips-2012-High-Order Multi-Task Feature Learning to Identify Longitudinal Phenotypic Markers for Alzheimer's Disease Progression Prediction

16 0.065570816 287 nips-2012-Random function priors for exchangeable arrays with applications to graphs and relational data

17 0.063316859 178 nips-2012-Learning Label Trees for Probabilistic Modelling of Implicit Feedback

18 0.060746625 204 nips-2012-MAP Inference in Chains using Column Generation

19 0.056290936 81 nips-2012-Context-Sensitive Decision Forests for Object Detection

20 0.056271885 267 nips-2012-Perceptron Learning of SAT

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.17), (1, 0.019), (2, 0.002), (3, -0.084), (4, -0.083), (5, -0.027), (6, -0.023), (7, -0.019), (8, -0.083), (9, 0.039), (10, 0.015), (11, -0.049), (12, 0.072), (13, -0.057), (14, -0.12), (15, 0.128), (16, 0.005), (17, 0.111), (18, 0.293), (19, 0.059), (20, 0.039), (21, 0.082), (22, -0.011), (23, -0.069), (24, -0.026), (25, 0.055), (26, -0.0), (27, -0.131), (28, 0.01), (29, -0.004), (30, 0.049), (31, -0.021), (32, -0.027), (33, 0.095), (34, -0.028), (35, -0.096), (36, -0.027), (37, -0.102), (38, 0.033), (39, -0.073), (40, -0.023), (41, -0.121), (42, -0.014), (43, -0.086), (44, -0.025), (45, -0.165), (46, -0.135), (47, -0.108), (48, 0.088), (49, -0.008)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.94060433 334 nips-2012-Tensor Decomposition for Fast Parsing with Latent-Variable PCFGs

Author: Michael Collins, Shay B. Cohen

2 0.7094605 156 nips-2012-Identifiability and Unmixing of Latent Parse Trees

Author: Percy Liang, Daniel J. Hsu, Sham M. Kakade

3 0.5743919 318 nips-2012-Sparse Approximate Manifolds for Differential Geometric MCMC

Author: Ben Calderhead, Mátyás A. Sustik

4 0.52130306 9 nips-2012-A Geometric take on Metric Learning

Author: Søren Hauberg, Oren Freifeld, Michael J. Black

5 0.48970118 22 nips-2012-A latent factor model for highly multi-relational data

Author: Rodolphe Jenatton, Nicolas L. Roux, Antoine Bordes, Guillaume R. Obozinski

Abstract: Many data such as social networks, movie preferences or knowledge bases are multi-relational, in that they describe multiple relations between entities. While there is a large body of work focused on modeling these data, modeling these multiple types of relations jointly remains challenging. Further, existing approaches tend to breakdown when the number of these types grows. In this paper, we propose a method for modeling large multi-relational datasets, with possibly thousands of relations. Our model is based on a bilinear structure, which captures various orders of interaction of the data, and also shares sparse latent factors across different relations. We illustrate the performance of our approach on standard tensor-factorization datasets where we attain, or outperform, state-of-the-art results. Finally, a NLP application demonstrates our scalability and the ability of our model to learn efﬁcient and semantically meaningful verb representations. 1

6 0.48484305 172 nips-2012-Latent Graphical Model Selection: Efficient Methods for Locally Tree-like Graphs

7 0.48313135 267 nips-2012-Perceptron Learning of SAT

8 0.45993611 25 nips-2012-A new metric on the manifold of kernel matrices with application to matrix geometric means

9 0.4579576 180 nips-2012-Learning Mixtures of Tree Graphical Models

10 0.44706655 301 nips-2012-Scaled Gradients on Grassmann Manifolds for Matrix Completion

11 0.428296 232 nips-2012-Multiplicative Forests for Continuous-Time Processes

12 0.41501471 54 nips-2012-Bayesian Probabilistic Co-Subspace Addition

13 0.410694 339 nips-2012-The Time-Marginalized Coalescent Prior for Hierarchical Clustering

14 0.40692458 206 nips-2012-Majorization for CRFs and Latent Likelihoods

15 0.40438125 19 nips-2012-A Spectral Algorithm for Latent Dirichlet Allocation

16 0.40368849 183 nips-2012-Learning Partially Observable Models Using Temporally Abstract Decision Trees

17 0.38003466 260 nips-2012-Online Sum-Product Computation Over Trees

18 0.36042464 225 nips-2012-Multi-task Vector Field Learning

19 0.35249588 287 nips-2012-Random function priors for exchangeable arrays with applications to graphs and relational data

20 0.34356564 215 nips-2012-Minimizing Uncertainty in Pipelines

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.044), (9, 0.014), (21, 0.018), (22, 0.275), (38, 0.119), (42, 0.032), (54, 0.017), (55, 0.013), (74, 0.077), (76, 0.139), (80, 0.125), (92, 0.038)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.79116136 48 nips-2012-Augmented-SVM: Automatic space partitioning for combining multiple non-linear dynamics

Author: Ashwini Shukla, Aude Billard

Abstract: Non-linear dynamical systems (DS) have been used extensively for building generative models of human behavior. Their applications range from modeling brain dynamics to encoding motor commands. Many schemes have been proposed for encoding robot motions using dynamical systems with a single attractor placed at a predeﬁned target in state space. Although these enable the robots to react against sudden perturbations without any re-planning, the motions are always directed towards a single target. In this work, we focus on combining several such DS with distinct attractors, resulting in a multi-stable DS. We show its applicability in reach-to-grasp tasks where the attractors represent several grasping points on the target object. While exploiting multiple attractors provides more ﬂexibility in recovering from unseen perturbations, it also increases the complexity of the underlying learning problem. Here we present the Augmented-SVM (A-SVM) model which inherits region partitioning ability of the well known SVM classiﬁer and is augmented with novel constraints derived from the individual DS. The new constraints modify the original SVM dual whose optimal solution then results in a new class of support vectors (SV). These new SV ensure that the resulting multistable DS incurs minimum deviation from the original dynamics and is stable at each of the attractors within a ﬁnite region of attraction. We show, via implementations on a simulated 10 degrees of freedom mobile robotic platform, that the model is capable of real-time motion generation and is able to adapt on-the-ﬂy to perturbations.

same-paper 2 0.7870003 334 nips-2012-Tensor Decomposition for Fast Parsing with Latent-Variable PCFGs

Author: Michael Collins, Shay B. Cohen

3 0.78104073 251 nips-2012-On Lifting the Gibbs Sampling Algorithm

Author: Deepak Venugopal, Vibhav Gogate

Abstract: First-order probabilistic models combine the power of ﬁrst-order logic, the de facto tool for handling relational structure, with probabilistic graphical models, the de facto tool for handling uncertainty. Lifted probabilistic inference algorithms for them have been the subject of much recent research. The main idea in these algorithms is to improve the accuracy and scalability of existing graphical models’ inference algorithms by exploiting symmetry in the ﬁrst-order representation. In this paper, we consider blocked Gibbs sampling, an advanced MCMC scheme, and lift it to the ﬁrst-order level. We propose to achieve this by partitioning the ﬁrst-order atoms in the model into a set of disjoint clusters such that exact lifted inference is polynomial in each cluster given an assignment to all other atoms not in the cluster. We propose an approach for constructing the clusters and show how it can be used to trade accuracy with computational complexity in a principled manner. Our experimental evaluation shows that lifted Gibbs sampling is superior to the propositional algorithm in terms of accuracy, scalability and convergence.

4 0.69757849 98 nips-2012-Dimensionality Dependent PAC-Bayes Margin Bound

Author: Chi Jin, Liwei Wang

Abstract: Margin is one of the most important concepts in machine learning. Previous margin bounds, both for SVM and for boosting, are dimensionality independent. A major advantage of this dimensionality independency is that it can explain the excellent performance of SVM whose feature spaces are often of high or inﬁnite dimension. In this paper we address the problem whether such dimensionality independency is intrinsic for the margin bounds. We prove a dimensionality dependent PAC-Bayes margin bound. The bound is monotone increasing with respect to the dimension when keeping all other factors ﬁxed. We show that our bound is strictly sharper than a previously well-known PAC-Bayes margin bound if the feature space is of ﬁnite dimension; and the two bounds tend to be equivalent as the dimension goes to inﬁnity. In addition, we show that the VC bound for linear classiﬁers can be recovered from our bound under mild conditions. We conduct extensive experiments on benchmark datasets and ﬁnd that the new bound is useful for model selection and is usually signiﬁcantly sharper than the dimensionality independent PAC-Bayes margin bound as well as the VC bound for linear classiﬁers.

5 0.65555549 168 nips-2012-Kernel Latent SVM for Visual Recognition

Author: Weilong Yang, Yang Wang, Arash Vahdat, Greg Mori

Abstract: Latent SVMs (LSVMs) are a class of powerful tools that have been successfully applied to many applications in computer vision. However, a limitation of LSVMs is that they rely on linear models. For many computer vision tasks, linear models are suboptimal and nonlinear models learned with kernels typically perform much better. Therefore it is desirable to develop the kernel version of LSVM. In this paper, we propose kernel latent SVM (KLSVM) – a new learning framework that combines latent SVMs and kernel methods. We develop an iterative training algorithm to learn the model parameters. We demonstrate the effectiveness of KLSVM using three different applications in visual recognition. Our KLSVM formulation is very general and can be applied to solve a wide range of applications in computer vision and machine learning. 1

6 0.65236521 172 nips-2012-Latent Graphical Model Selection: Efficient Methods for Locally Tree-like Graphs

7 0.65098667 355 nips-2012-Truncation-free Online Variational Inference for Bayesian Nonparametric Models

8 0.65016347 197 nips-2012-Learning with Recursive Perceptual Representations

9 0.64831907 274 nips-2012-Priors for Diversity in Generative Latent Variable Models

10 0.64741743 200 nips-2012-Local Supervised Learning through Space Partitioning

11 0.64673203 83 nips-2012-Controlled Recognition Bounds for Visual Learning and Exploration

12 0.64549005 316 nips-2012-Small-Variance Asymptotics for Exponential Family Dirichlet Process Mixture Models

13 0.6441747 229 nips-2012-Multimodal Learning with Deep Boltzmann Machines

14 0.6436128 279 nips-2012-Projection Retrieval for Classification

15 0.64082307 180 nips-2012-Learning Mixtures of Tree Graphical Models

16 0.64037889 104 nips-2012-Dual-Space Analysis of the Sparse Linear Model

17 0.63975883 188 nips-2012-Learning from Distributions via Support Measure Machines

18 0.63962221 171 nips-2012-Latent Coincidence Analysis: A Hidden Variable Model for Distance Metric Learning

19 0.63891506 252 nips-2012-On Multilabel Classification and Ranking with Partial Feedback

20 0.63851291 277 nips-2012-Probabilistic Low-Rank Subspace Clustering