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

265 nips-2012-Parametric Local Metric Learning for Nearest Neighbor Classification

Source: pdf

Author: Jun Wang, Alexandros Kalousis, Adam Woznica

Abstract: We study the problem of learning local metrics for nearest neighbor classiﬁcation. Most previous works on local metric learning learn a number of local unrelated metrics. While this ”independence” approach delivers an increased ﬂexibility its downside is the considerable risk of overﬁtting. We present a new parametric local metric learning method in which we learn a smooth metric matrix function over the data manifold. Using an approximation error bound of the metric matrix function we learn local metrics as linear combinations of basis metrics deﬁned on anchor points over different regions of the instance space. We constrain the metric matrix function by imposing on the linear combinations manifold regularization which makes the learned metric matrix function vary smoothly along the geodesics of the data manifold. Our metric learning method has excellent performance both in terms of predictive power and scalability. We experimented with several largescale classiﬁcation problems, tens of thousands of instances, and compared it with several state of the art metric learning methods, both global and local, as well as to SVM with automatic kernel selection, all of which it outperforms in a signiﬁcant manner. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 ch Abstract We study the problem of learning local metrics for nearest neighbor classiﬁcation. [sent-7, score-0.554]

2 Most previous works on local metric learning learn a number of local unrelated metrics. [sent-8, score-0.661]

3 We present a new parametric local metric learning method in which we learn a smooth metric matrix function over the data manifold. [sent-10, score-0.993]

4 Using an approximation error bound of the metric matrix function we learn local metrics as linear combinations of basis metrics deﬁned on anchor points over different regions of the instance space. [sent-11, score-1.587]

5 We constrain the metric matrix function by imposing on the linear combinations manifold regularization which makes the learned metric matrix function vary smoothly along the geodesics of the data manifold. [sent-12, score-0.986]

6 Our metric learning method has excellent performance both in terms of predictive power and scalability. [sent-13, score-0.396]

7 We experimented with several largescale classiﬁcation problems, tens of thousands of instances, and compared it with several state of the art metric learning methods, both global and local, as well as to SVM with automatic kernel selection, all of which it outperforms in a signiﬁcant manner. [sent-14, score-0.485]

8 Mahalanobis metric learning [4, 15, 9, 10, 17, 14] improves the performance of the NN classiﬁer if used instead of the Euclidean metric. [sent-18, score-0.373]

9 It learns a global distance metric which determines the importance of the different input features and their correlations. [sent-19, score-0.491]

10 However, since the discriminatory power of the input features might vary between different neighborhoods, learning a global metric cannot ﬁt well the distance over the data manifold. [sent-20, score-0.486]

11 Thus a more appropriate way is to learn a metric on each neighborhood and local metric learning [8, 3, 15, 7] does exactly that. [sent-21, score-0.915]

12 It increases the expressive power of standard Mahalanobis metric learning by learning a number of local metrics (e. [sent-22, score-0.8]

13 1 Local metric learning has been shown to be effective for different learning scenarios. [sent-25, score-0.373]

14 One of the ﬁrst local metric learning works, Discriminant Adaptive Nearest Neighbor classiﬁcation [8], DANN, learns local metrics by shrinking neighborhoods in directions orthogonal to the local decision boundaries and enlarging the neighborhoods parallel to the boundaries. [sent-26, score-1.137]

15 It learns the local metrics independently with no regularization between them which makes it prone to overﬁtting. [sent-27, score-0.497]

16 The authors of LMNN-Multiple Metric (LMNN-MM) [15] signiﬁcantly limited the number of learned metrics and constrained all instances in a given region to share the same metric in an effort to combat overﬁtting. [sent-28, score-0.818]

17 In the supervised setting they ﬁxed the number of metrics to the number of classes; a similar idea has been also considered in [3]. [sent-29, score-0.308]

18 However, they too learn the metrics independently for each region making them also prone to overﬁtting since the local metrics will be overly speciﬁc to their respective regions. [sent-30, score-0.843]

19 However, the method learns the local metrics using a learning-order-sensitive propagation strategy, and depends heavily on the appropriate deﬁnition of the target positions for each instance, a task far from obvious. [sent-32, score-0.464]

20 In another effort to overcome the overﬁtting problem of the discriminative methods [8, 15], Generative Local Metric Learning, GLML, [11], propose to learn local metrics by minimizing the NN expected classiﬁcation error under strong model assumptions. [sent-33, score-0.5]

21 In this paper we propose the Parametric Local Metric Learning method (PLML) which learns a smooth metric matrix function over the data manifold. [sent-36, score-0.488]

22 More precisely, we parametrize the metric matrix of each instance as a linear combination of basis metric matrices of a small set of anchor points; this parametrization is naturally derived from an error bound on local metric approximation. [sent-37, score-1.663]

23 We develop an efﬁcient two stage algorithm that ﬁrst learns the linear combinations of each instance and then the metric matrices of the anchor points. [sent-39, score-0.673]

24 To improve scalability and efﬁciency we employ a fast ﬁrst-order optimization algorithm, FISTA [2], to learn the linear combinations as well as the basis metrics of the anchor points. [sent-40, score-0.669]

25 The experimental results clearly demonstrate that PLML signiﬁcantly improves the predictive performance over the current state-of-the-art metric learning methods, as well as over multi-class SVM with automatic kernel selection. [sent-42, score-0.452]

26 The squared Mahalanobis distance between two instances in the input space is given by: d2 (xi , xj ) = (xi − xj )T M(xi − xj ) M where M is a PSD metric matrix (M 0). [sent-50, score-0.867]

27 A linear metric learning method learns a Mahalanobis metric M by optimizing some cost function under the PSD constraints for M and a set of additional constraints on the pairwise instance distances. [sent-51, score-0.972]

28 Depending on the actual metric learning method, different kinds of constraints on pairwise distances are used. [sent-52, score-0.483]

29 A triplet constraint denoted by c(xi , xj , xk ), indicates that in the projected space induced by M the distance between xi and xj should be smaller than the distance between xi and xk . [sent-54, score-0.602]

30 Very often a single metric M can not model adequately the complexity of a given learning problem in which discriminative features vary between different neighborhoods. [sent-55, score-0.405]

31 To address this limitation in local metric learning we learn a set of local metrics. [sent-56, score-0.661]

32 In most cases we learn a local metric for each learning instance [8, 11], however we can also learn a local metric for some part of the instance space in which case the number of learned metrics can be considerably smaller than n, e. [sent-57, score-1.543]

33 We follow the former approach and learn one local metric per instance. [sent-60, score-0.542]

34 In principle, distances should then be deﬁned as geodesic distances using the local metric on a Riemannian manifold. [sent-61, score-0.56]

35 However, this is computationally difﬁcult, thus we deﬁne the distance between instances xi and xj as: d2 i (xi , xj ) = (xi − xj )T Mi (xi − xj ) M 2 where Mi is the local metric of instance xi . [sent-62, score-1.201]

36 Note that most often the local metric Mi of instance xi is different from that of xj . [sent-63, score-0.713]

37 Nevertheless, in accordance to the standard practice we will continue to use the term local metric learning following [15, 11]. [sent-67, score-0.492]

38 3 Parametric Local Metric Learning We assume that there exists a Lipschitz smooth vector-valued function f (x), the output of which is the vectorized local metric matrix of instance x. [sent-68, score-0.634]

39 Learning the local metric of each instance is essentially learning the value of this function at different points over the data manifold. [sent-69, score-0.579]

40 In order to signiﬁcantly reduce the computational complexity we will approximate the metric function instead of directly learning it. [sent-70, score-0.373]

41 By the nonnegative weighting strategy (γ, U), the PSD constraints on the approximated local metric is automatically satisﬁed if the local metrics of anchor points are PSD matrices. [sent-79, score-1.178]

42 Lemma 1 suggests a natural way to approximate the local metric function by parameterizing the metric Mi of each instance xi as a weighted linear combination, Wi ∈ Rm , of a small set of metric basis, {Mb1 , . [sent-80, score-1.365]

43 This parametrization will also provide us with a global way to regularize the ﬂexibility of the metric function. [sent-84, score-0.434]

44 We will ﬁrst learn the vector of weights Wi for each instance xi , and then the basis metric matrices; these two together, will give us the Mi metric for the instance xi . [sent-85, score-1.162]

45 More formally, we deﬁne a m × d matrix U of anchor points, the i-th row of which is the anchor point ui , where uT ∈ Rd . [sent-86, score-0.378]

46 We denote by Mbi the Mahalanobis metric matrix associated with ui . [sent-87, score-0.429]

47 The local metric Mi of an instance xi is parametrized by: Wibk Mbk , Wibk ≥ 0, Mi = bk Wibk = 1 (2) bk where W is a n × m weight matrix, and its Wibk entry is the weight of the basis metric Mbk for the instance xi . [sent-89, score-1.401]

48 Using the parametrization of equation (2), the squared distance of xi to xj under the metric Mi is: Wibk d2 b (xi , xj ) M d2 i (xi , xj ) = M k (3) bk where d2 b (xi , xj ) is the squared Mahalanobis distance between xi and xj under the basis metric M k Mbk . [sent-91, score-1.71]

49 We will show in the next section how to learn the weights of the basis metrics for each instance and in section 3. [sent-92, score-0.534]

50 In addition we want the local metrics to vary smoothly over the data manifold. [sent-97, score-0.497]

51 Following this reasoning we will learn Smooth Local Linear Weights for the basis metrics by minimizing the error bound of (1) together with a regularization term that controls the weight variation 2 of similar instances. [sent-99, score-0.511]

52 The m × n matrix G is the squared distance matrix between each anchor point ui and each instance xj , obtained for p = 1 in (1), i. [sent-104, score-0.496]

53 To set the weights of the basis metrics for a testing instance we can optimize (4) given the weight of the basis metrics for the training instances. [sent-121, score-0.945]

54 2 Large Margin Basis Metric Learning In this section we deﬁne a large margin based algorithm to learn the basis metrics Mb1 , . [sent-125, score-0.513]

55 Given the W weight matrix of basis metrics obtained using Algorithm 1, the local metric Mi of an instance xi deﬁned in (2) is linear with respect to the basis metrics Mb1 , . [sent-129, score-1.531]

56 We deﬁne the relative comparison distance of instances xi , xj and xk as: d2 i (xi , xk ) − d2 i (xi , xj ). [sent-133, score-0.48]

57 In M M a large margin constraint c(xi , xj , xk ), the squared distance d2 i (xi , xk ) is required to be larger M than d2 i (xi , xj ) + 1, otherwise an error ξ ijk ≥ 0 is generated. [sent-134, score-0.667]

58 In LMNN-MM to avoid over-ﬁtting, different local metrics Mj and Mk are used to compute the squared distance d2 j (xi , xj ) and M d2 k (xi , xk ) respectively, as no smoothness constraint is added between metrics of different local M regions. [sent-136, score-1.081]

59 Given a set of triplet constraints, we learn the basis metrics Mb1 , . [sent-137, score-0.568]

60 ,Mbm ,ξ bl Wibl d2 b (xi , xj ) M ξ ijk + α2 (6) l ij ijk bl Wibl (d2 b (xi , xk ) − d2 b (xi , xj )) ≥ 1 − ξ ijk ∀i, j, k M M s. [sent-143, score-1.244]

61 l l bl ξ ijk ≥ 0; ∀i, j, k Mbl 0; ∀bl where α1 and α2 are parameters that balance the importance of the different terms. [sent-145, score-0.363]

62 The large margin triplet constraints for each instance are generated using its k1 same class nearest neighbors and k2 different class nearest neighbors by requiring its distances to the k2 different class instances to be larger than those to its k1 same class instances. [sent-146, score-0.621]

63 In the objective function of (6) the basis metrics are learned by minimizing the sum of large margin errors and the sum of squared pairwise distances of each instance to its k1 nearest neighbors computed using the local metric. [sent-147, score-0.889]

64 Unlike LMNN we add the squared Frobenius norm on each basis metrics in the objective function. [sent-148, score-0.458]

65 First we exploit the connection between LMNN and SVM shown in [5] under which the squared Frobenius norm of the metric matrix is related to the SVM margin. [sent-150, score-0.442]

66 Unlike many special solvers which optimize the primal form of the metric learning problem [15, 13], we follow [12] and optimize the Lagrangian dual problem of (6). [sent-152, score-0.411]

67 The dual formulation leads to an efﬁcient basis metric learning algorithm. [sent-153, score-0.523]

68 Introducing the Lagrangian dual multipliers γ ijk , pijk and the PSD matrices Zbl to respectively associate with every large margin triplet constraints, ξ ijk ≥ 0 and the PSD constraints Mbl 0 in (6), we can easily derive the following Lagrangian dual form γijk − max Zb1 ,. [sent-154, score-0.786]

69 ,Zbm ,γ ijk bl 1 · Zbl + 4α1 1 ≥ γijk ≥ 0; ∀i,j,k Zbl s. [sent-157, score-0.363]

70 g(γ) = − γijk + ijk bl 1 ≥ γijk ≥ 0; ∀i, j, k 5 1 (Kbl )+ − Kbl 4α1 2 F (8) 1 And the optimal condition for Mbl is M∗l = 2α1 ((K∗l )+ − K∗l ). [sent-167, score-0.363]

71 We want to determine whether the addition of manifold regularization on the local metrics improves the predictive performance of local metric learning, and whether the local metric learning improves over learning with single global metric. [sent-174, score-1.51]

72 The ﬁrst, SML, is a variant of PLML where a single global metric is learned, i. [sent-176, score-0.402]

73 Here we learn one local metric for each cluster and we assign a weight of one for a basis metric Mbi if the corresponding cluster of Mbi contains the instance, and zero otherwise. [sent-180, score-1.068]

74 Finally, we also compare against four state of the art metric learning methods LMNN [15], BoostMetric [13]1 , GLML [11] and LMNN-MM [15]2 . [sent-181, score-0.373]

75 The former two learn a single global metric and the latter two a number of local metrics. [sent-182, score-0.571]

76 In addition to the different metric learning methods, we also compare PLML against multi-class SVMs in which we use the one-against-all strategy to determine the class label for multi-class problems and select the best kernel with inner cross validation. [sent-183, score-0.403]

77 Since metric learning is computationally expensive for datasets with large number of features we followed [15] and reduced the dimensionality of the USPS, Isolet and MINIST datasets by applying PCA. [sent-184, score-0.449]

78 In the basis metric learning problem (6), the number of the dual parameters γ is the same as the number of triplet constraints. [sent-196, score-0.621]

79 To speedup the learning process, the triplet constraints are constructed only using the three same-class and the three different-class nearest neighbors for each learning instance. [sent-197, score-0.296]

80 The above setting of basis metric learning for PLML is also used with the SML and CBLML methods. [sent-201, score-0.485]

81 Finally, we use the 1-NN rule to evaluate the performance of the different metric learning methods. [sent-206, score-0.373]

82 6 (a) LMNN-MM (b) CBLML (c) GLML (d) PLML Figure 1: The visualization of learned local metrics of LMNN-MM, CBLML, GLML and PLML. [sent-215, score-0.45]

83 PLML consistently outperforms the single global metric learning methods LMNN, BoostMetric and SML, for all datasets except Isolet on which its accuracy is slightly lower than that of LMNN. [sent-332, score-0.44]

84 Depending on the single global metric learning method with which we compare it, it is signiﬁcantly better in three, four, and ﬁve datasets ( for LMNN, SML, and BoostMetric respectively), out of the six and never singiﬁcantly worse. [sent-333, score-0.471]

85 When we compare PLML with CBLML and LMNN-MM, the two baseline methods which learn one local metric for each cluster and each class respectively with no smoothness constraints, we see that it is statistically signiﬁcantly better in all the datasets. [sent-334, score-0.542]

86 GLML fails to learn appropriate metrics on all datasets because its fundamental generative model assumption is often not valid. [sent-335, score-0.396]

87 Examining more closely the performance of the baseline local metric learning methods CBLML and LMNN-MM we observe that they tend to overﬁt the learning problems. [sent-341, score-0.492]

88 On the other hand PLML even though it also learns local metrics it does not suffer from the overﬁtting problem due to the manifold regularization. [sent-343, score-0.511]

89 Figure 1 shows the learned local metrics by plotting the axis of their corresponding ellipses(black line). [sent-350, score-0.45]

90 Clearly PLML ﬁts the data much better than LMNN-MM and as expected its local metrics vary smoothly. [sent-352, score-0.459]

91 Its performance saturates when the number of basis metrics becomes sufﬁcient to model the underlying training data. [sent-362, score-0.42]

92 In contrast, the performance of CBLML gets worse when the number of basis metrics is large which provides further evidence that CBLML does indeed overﬁt the learning problems, demonstrating clearly the utility of the manifold regularization. [sent-365, score-0.49]

93 5 Conclusions Local metric learning provides a more ﬂexible way to learn the distance function. [sent-366, score-0.475]

94 In this paper we presented PLML, a local metric learning method which regularizes local metrics to vary smoothly over the data manifold. [sent-368, score-0.989]

95 Using an approximation error bound of the metric matrix function, we parametrize the local metrics by a weighted linear combinations of local metrics of anchor points. [sent-369, score-1.482]

96 Our method scales to learning problems with tens of thousands of instances and avoids the overﬁtting problems that plague the other local metric learning methods. [sent-370, score-0.61]

97 The experimental results show that PLML outperforms signiﬁcantly the state of the art metric learning methods and it has a performance which is signiﬁcantly better or equivalent to that of SVM with automatic kernel selection. [sent-371, score-0.429]

98 A metric learning perspective of svm: on the relation of svm and lmnn. [sent-408, score-0.426]

99 Distance metric learning for large margin nearest neighbor classiﬁcation. [sent-479, score-0.543]

100 Locally smooth metric learning with application to image retrieval. [sent-485, score-0.42]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('plml', 0.476), ('metric', 0.373), ('metrics', 0.308), ('ijk', 0.26), ('cblml', 0.238), ('kbl', 0.17), ('anchor', 0.161), ('glml', 0.153), ('wibk', 0.136), ('sml', 0.135), ('lmnn', 0.124), ('wibl', 0.119), ('local', 0.119), ('basis', 0.112), ('bl', 0.103), ('boostmetric', 0.102), ('roj', 0.102), ('zbl', 0.102), ('triplet', 0.098), ('xj', 0.094), ('instances', 0.091), ('cijk', 0.085), ('nearest', 0.078), ('psd', 0.073), ('mbl', 0.068), ('mbm', 0.068), ('mahalanobis', 0.064), ('instance', 0.064), ('xi', 0.063), ('isolet', 0.061), ('optdigits', 0.055), ('svm', 0.053), ('mi', 0.052), ('distance', 0.052), ('mbi', 0.051), ('mbk', 0.051), ('mcnemar', 0.051), ('learn', 0.05), ('pendigits', 0.049), ('constraints', 0.049), ('neighbor', 0.049), ('manifold', 0.047), ('smooth', 0.047), ('bk', 0.044), ('wi', 0.044), ('margin', 0.043), ('xk', 0.043), ('neighbors', 0.043), ('usps', 0.041), ('weight', 0.041), ('squared', 0.038), ('smoothly', 0.038), ('combinations', 0.038), ('datasets', 0.038), ('dual', 0.038), ('learns', 0.037), ('wt', 0.036), ('aij', 0.035), ('switzerland', 0.034), ('boxp', 0.034), ('kalousis', 0.034), ('wib', 0.034), ('lipschitz', 0.034), ('distances', 0.034), ('mnist', 0.033), ('fista', 0.033), ('prone', 0.033), ('parametrization', 0.032), ('vary', 0.032), ('neighborhoods', 0.031), ('matrix', 0.031), ('six', 0.031), ('tr', 0.031), ('kernel', 0.03), ('geneva', 0.03), ('woznica', 0.03), ('lw', 0.03), ('tting', 0.029), ('global', 0.029), ('constructed', 0.028), ('letter', 0.027), ('ij', 0.027), ('pairwise', 0.027), ('tens', 0.027), ('nn', 0.027), ('weighting', 0.026), ('automatic', 0.026), ('cantly', 0.025), ('ui', 0.025), ('respective', 0.025), ('parametrize', 0.025), ('wg', 0.025), ('xij', 0.025), ('points', 0.023), ('classi', 0.023), ('learned', 0.023), ('predictive', 0.023), ('worse', 0.023), ('effort', 0.023), ('lagrangian', 0.023)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000001 265 nips-2012-Parametric Local Metric Learning for Nearest Neighbor Classification

Author: Jun Wang, Alexandros Kalousis, Adam Woznica

2 0.26114827 242 nips-2012-Non-linear Metric Learning

Author: Dor Kedem, Stephen Tyree, Fei Sha, Gert R. Lanckriet, Kilian Q. Weinberger

Abstract: In this paper, we introduce two novel metric learning algorithms, χ2 -LMNN and GB-LMNN, which are explicitly designed to be non-linear and easy-to-use. The two approaches achieve this goal in fundamentally different ways: χ2 -LMNN inherits the computational beneﬁts of a linear mapping from linear metric learning, but uses a non-linear χ2 -distance to explicitly capture similarities within histogram data sets; GB-LMNN applies gradient-boosting to learn non-linear mappings directly in function space and takes advantage of this approach’s robustness, speed, parallelizability and insensitivity towards the single additional hyperparameter. On various benchmark data sets, we demonstrate these methods not only match the current state-of-the-art in terms of kNN classiﬁcation error, but in the case of χ2 -LMNN, obtain best results in 19 out of 20 learning settings. 1

3 0.23600356 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.19153363 307 nips-2012-Semi-Crowdsourced Clustering: Generalizing Crowd Labeling by Robust Distance Metric Learning

Author: Jinfeng Yi, Rong Jin, Shaili Jain, Tianbao Yang, Anil K. Jain

Abstract: One of the main challenges in data clustering is to deﬁne an appropriate similarity measure between two objects. Crowdclustering addresses this challenge by deﬁning the pairwise similarity based on the manual annotations obtained through crowdsourcing. Despite its encouraging results, a key limitation of crowdclustering is that it can only cluster objects when their manual annotations are available. To address this limitation, we propose a new approach for clustering, called semi-crowdsourced clustering that effectively combines the low-level features of objects with the manual annotations of a subset of the objects obtained via crowdsourcing. The key idea is to learn an appropriate similarity measure, based on the low-level features of objects and from the manual annotations of only a small portion of the data to be clustered. One difﬁculty in learning the pairwise similarity measure is that there is a signiﬁcant amount of noise and inter-worker variations in the manual annotations obtained via crowdsourcing. We address this difﬁculty by developing a metric learning algorithm based on the matrix completion method. Our empirical study with two real-world image data sets shows that the proposed algorithm outperforms state-of-the-art distance metric learning algorithms in both clustering accuracy and computational efﬁciency. 1

5 0.12117808 148 nips-2012-Hamming Distance Metric Learning

Author: Mohammad Norouzi, David M. Blei, Ruslan Salakhutdinov

Abstract: Motivated by large-scale multimedia applications we propose to learn mappings from high-dimensional data to binary codes that preserve semantic similarity. Binary codes are well suited to large-scale applications as they are storage efﬁcient and permit exact sub-linear kNN search. The framework is applicable to broad families of mappings, and uses a ﬂexible form of triplet ranking loss. We overcome discontinuous optimization of the discrete mappings by minimizing a piecewise-smooth upper bound on empirical loss, inspired by latent structural SVMs. We develop a new loss-augmented inference algorithm that is quadratic in the code length. We show strong retrieval performance on CIFAR-10 and MNIST, with promising classiﬁcation results using no more than kNN on the binary codes. 1

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

7 0.11369754 318 nips-2012-Sparse Approximate Manifolds for Differential Geometric MCMC

8 0.1062564 189 nips-2012-Learning from the Wisdom of Crowds by Minimax Entropy

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

10 0.078790158 145 nips-2012-Gradient Weights help Nonparametric Regressors

11 0.067883886 97 nips-2012-Diffusion Decision Making for Adaptive k-Nearest Neighbor Classification

12 0.066061355 157 nips-2012-Identification of Recurrent Patterns in the Activation of Brain Networks

13 0.065440848 200 nips-2012-Local Supervised Learning through Space Partitioning

14 0.059308462 197 nips-2012-Learning with Recursive Perceptual Representations

15 0.056052025 188 nips-2012-Learning from Distributions via Support Measure Machines

16 0.05553114 146 nips-2012-Graphical Gaussian Vector for Image Categorization

17 0.053648822 330 nips-2012-Supervised Learning with Similarity Functions

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

19 0.051641908 92 nips-2012-Deep Representations and Codes for Image Auto-Annotation

20 0.05050274 27 nips-2012-A quasi-Newton proximal splitting method

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.17), (1, 0.049), (2, -0.005), (3, -0.099), (4, 0.093), (5, -0.016), (6, -0.001), (7, 0.094), (8, 0.101), (9, -0.003), (10, 0.029), (11, -0.188), (12, 0.088), (13, -0.013), (14, -0.091), (15, 0.075), (16, -0.08), (17, 0.119), (18, 0.203), (19, 0.154), (20, 0.063), (21, -0.147), (22, 0.022), (23, 0.0), (24, 0.079), (25, -0.048), (26, -0.026), (27, -0.03), (28, 0.082), (29, 0.05), (30, -0.093), (31, -0.063), (32, 0.04), (33, 0.015), (34, 0.024), (35, 0.035), (36, 0.105), (37, 0.01), (38, -0.058), (39, 0.031), (40, -0.067), (41, 0.094), (42, 0.001), (43, 0.047), (44, 0.015), (45, 0.065), (46, 0.088), (47, 0.101), (48, -0.054), (49, -0.007)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.96157408 265 nips-2012-Parametric Local Metric Learning for Nearest Neighbor Classification

Author: Jun Wang, Alexandros Kalousis, Adam Woznica

2 0.87614167 242 nips-2012-Non-linear Metric Learning

Author: Dor Kedem, Stephen Tyree, Fei Sha, Gert R. Lanckriet, Kilian Q. Weinberger

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

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

4 0.7197603 307 nips-2012-Semi-Crowdsourced Clustering: Generalizing Crowd Labeling by Robust Distance Metric Learning

Author: Jinfeng Yi, Rong Jin, Shaili Jain, Tianbao Yang, Anil K. Jain

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

Author: Suvrit Sra

Abstract: Symmetric positive deﬁnite (spd) matrices pervade numerous scientiﬁc disciplines, including machine learning and optimization. We consider the key task of measuring distances between two spd matrices; a task that is often nontrivial whenever the distance function must respect the non-Euclidean geometry of spd matrices. Typical non-Euclidean distance measures such as the Riemannian metric δR (X, Y ) = log(Y −1/2 XY −1/2 ) F , are computationally demanding and also complicated to use. To allay some of these difﬁculties, we introduce a new metric on spd matrices, which not only respects non-Euclidean geometry but also offers faster computation than δR while being less complicated to use. We support our claims theoretically by listing a set of theorems that relate our metric to δR (X, Y ), and experimentally by studying the nonconvex problem of computing matrix geometric means based on squared distances. 1

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

7 0.54852813 157 nips-2012-Identification of Recurrent Patterns in the Activation of Brain Networks

8 0.50826079 338 nips-2012-The Perturbed Variation

9 0.50573558 148 nips-2012-Hamming Distance Metric Learning

10 0.48792276 318 nips-2012-Sparse Approximate Manifolds for Differential Geometric MCMC

11 0.47217423 145 nips-2012-Gradient Weights help Nonparametric Regressors

12 0.45016283 146 nips-2012-Graphical Gaussian Vector for Image Categorization

13 0.41621265 225 nips-2012-Multi-task Vector Field Learning

14 0.41168121 189 nips-2012-Learning from the Wisdom of Crowds by Minimax Entropy

15 0.38533607 330 nips-2012-Supervised Learning with Similarity Functions

16 0.37631851 140 nips-2012-Fusion with Diffusion for Robust Visual Tracking

17 0.37509605 97 nips-2012-Diffusion Decision Making for Adaptive k-Nearest Neighbor Classification

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

19 0.36178595 204 nips-2012-MAP Inference in Chains using Column Generation

20 0.35524985 176 nips-2012-Learning Image Descriptors with the Boosting-Trick

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.051), (21, 0.012), (38, 0.126), (42, 0.092), (44, 0.014), (54, 0.026), (55, 0.022), (59, 0.276), (74, 0.049), (76, 0.148), (80, 0.069), (92, 0.025)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.7945593 253 nips-2012-On Triangular versus Edge Representations --- Towards Scalable Modeling of Networks

Author: Qirong Ho, Junming Yin, Eric P. Xing

Abstract: In this paper, we argue for representing networks as a bag of triangular motifs, particularly for important network problems that current model-based approaches handle poorly due to computational bottlenecks incurred by using edge representations. Such approaches require both 1-edges and 0-edges (missing edges) to be provided as input, and as a consequence, approximate inference algorithms for these models usually require Ω(N 2 ) time per iteration, precluding their application to larger real-world networks. In contrast, triangular modeling requires less computation, while providing equivalent or better inference quality. A triangular motif is a vertex triple containing 2 or 3 edges, and the number of such motifs is 2 Θ( i Di ) (where Di is the degree of vertex i), which is much smaller than N 2 for low-maximum-degree networks. Using this representation, we develop a novel mixed-membership network model and approximate inference algorithm suitable for large networks with low max-degree. For networks with high maximum degree, the triangular motifs can be naturally subsampled in a node-centric fashion, allowing for much faster inference at a small cost in accuracy. Empirically, we demonstrate that our approach, when compared to that of an edge-based model, has faster runtime and improved accuracy for mixed-membership community detection. We conclude with a large-scale demonstration on an N ≈ 280, 000-node network, which is infeasible for network models with Ω(N 2 ) inference cost. 1

2 0.7704947 235 nips-2012-Natural Images, Gaussian Mixtures and Dead Leaves

Author: Daniel Zoran, Yair Weiss

Abstract: Simple Gaussian Mixture Models (GMMs) learned from pixels of natural image patches have been recently shown to be surprisingly strong performers in modeling the statistics of natural images. Here we provide an in depth analysis of this simple yet rich model. We show that such a GMM model is able to compete with even the most successful models of natural images in log likelihood scores, denoising performance and sample quality. We provide an analysis of what such a model learns from natural images as a function of number of mixture components including covariance structure, contrast variation and intricate structures such as textures, boundaries and more. Finally, we show that the salient properties of the GMM learned from natural images can be derived from a simplified Dead Leaves model which explicitly models occlusion, explaining its surprising success relative to other models. 1 GMMs and natural image statistics models Many models for the statistics of natural image patches have been suggested in recent years. Finding good models for natural images is important to many different research areas - computer vision, biological vision and neuroscience among others. Recently, there has been a growing interest in comparing different aspects of models for natural images such as log-likelihood and multi-information reduction performance, and much progress has been achieved [1,2, 3,4,5, 6]. Out of these results there is one which is particularly interesting: simple, unconstrained Gaussian Mixture Models (GMMs) with a relatively small number of mixture components learned from image patches are extraordinarily good in modeling image statistics [6, 4]. This is a surprising result due to the simplicity of GMMs and their ubiquity. Another surprising aspect of this result is that many of the current models may be thought of as GMMs with an exponential or infinite number of components, having different constraints on the covariance structure of the mixture components. In this work we study the nature of GMMs learned from natural image patches. We start with a thorough comparison to some popular and cutting edge image models. We show that indeed, GMMs are excellent performers in modeling natural image patches. We then analyze what properties of natural images these GMMs capture, their dependence on the number of components in the mixture and their relation to the structure of the world around us. Finally, we show that the learned GMM suggests a strong connection between natural image statistics and a simple variant of the dead leaves model [7, 8] , explicitly modeling occlusions and explaining some of the success of GMMs in modeling natural images. 1 3.5 .,...- ••.......-.-.. -..---'-. 1 ~~6\8161·· -.. .-.. --...--.-- ---..-.- -. --------------MII+··+ilIl ..... .. . . ~ '[25 . . . ---- ] B'II 1_ -- ~2 ;t:: fI 1 - --- ,---- ._.. : 61.5 ..... '

same-paper 3 0.75894612 265 nips-2012-Parametric Local Metric Learning for Nearest Neighbor Classification

Author: Jun Wang, Alexandros Kalousis, Adam Woznica

4 0.70774585 272 nips-2012-Practical Bayesian Optimization of Machine Learning Algorithms

Author: Jasper Snoek, Hugo Larochelle, Ryan P. Adams

Abstract: The use of machine learning algorithms frequently involves careful tuning of learning parameters and model hyperparameters. Unfortunately, this tuning is often a “black art” requiring expert experience, rules of thumb, or sometimes bruteforce search. There is therefore great appeal for automatic approaches that can optimize the performance of any given learning algorithm to the problem at hand. In this work, we consider this problem through the framework of Bayesian optimization, in which a learning algorithm’s generalization performance is modeled as a sample from a Gaussian process (GP). We show that certain choices for the nature of the GP, such as the type of kernel and the treatment of its hyperparameters, can play a crucial role in obtaining a good optimizer that can achieve expertlevel performance. We describe new algorithms that take into account the variable cost (duration) of learning algorithm experiments and that can leverage the presence of multiple cores for parallel experimentation. We show that these proposed algorithms improve on previous automatic procedures and can reach or surpass human expert-level optimization for many algorithms including latent Dirichlet allocation, structured SVMs and convolutional neural networks. 1

5 0.70752376 294 nips-2012-Repulsive Mixtures

Author: Francesca Petralia, Vinayak Rao, David B. Dunson

Abstract: Discrete mixtures are used routinely in broad sweeping applications ranging from unsupervised settings to fully supervised multi-task learning. Indeed, ﬁnite mixtures and inﬁnite mixtures, relying on Dirichlet processes and modiﬁcations, have become a standard tool. One important issue that arises in using discrete mixtures is low separation in the components; in particular, different components can be introduced that are very similar and hence redundant. Such redundancy leads to too many clusters that are too similar, degrading performance in unsupervised learning and leading to computational problems and an unnecessarily complex model in supervised settings. Redundancy can arise in the absence of a penalty on components placed close together even when a Bayesian approach is used to learn the number of components. To solve this problem, we propose a novel prior that generates components from a repulsive process, automatically penalizing redundant components. We characterize this repulsive prior theoretically and propose a Markov chain Monte Carlo sampling algorithm for posterior computation. The methods are illustrated using synthetic examples and an iris data set. Key Words: Bayesian nonparametrics; Dirichlet process; Gaussian mixture model; Model-based clustering; Repulsive point process; Well separated mixture. 1

6 0.6996004 338 nips-2012-The Perturbed Variation

7 0.66975129 298 nips-2012-Scalable Inference of Overlapping Communities

8 0.63967299 243 nips-2012-Non-parametric Approximate Dynamic Programming via the Kernel Method

9 0.63776141 242 nips-2012-Non-linear Metric Learning

10 0.63636249 219 nips-2012-Modelling Reciprocating Relationships with Hawkes Processes

11 0.63349527 289 nips-2012-Recognizing Activities by Attribute Dynamics

12 0.62382084 162 nips-2012-Inverse Reinforcement Learning through Structured Classification

13 0.62355494 134 nips-2012-Finite Sample Convergence Rates of Zero-Order Stochastic Optimization Methods

14 0.62315702 316 nips-2012-Small-Variance Asymptotics for Exponential Family Dirichlet Process Mixture Models

15 0.62110013 275 nips-2012-Privacy Aware Learning

16 0.62099791 325 nips-2012-Stochastic optimization and sparse statistical recovery: Optimal algorithms for high dimensions

17 0.62085426 68 nips-2012-Clustering Aggregation as Maximum-Weight Independent Set

18 0.61952007 148 nips-2012-Hamming Distance Metric Learning

19 0.61905974 98 nips-2012-Dimensionality Dependent PAC-Bayes Margin Bound

20 0.61888808 69 nips-2012-Clustering Sparse Graphs