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

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

Source: pdf

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

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu 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. [sent-7, score-0.333]

2 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. [sent-9, score-0.882]

3 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. [sent-10, score-0.66]

4 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. [sent-11, score-0.233]

5 1 Introduction The use of Markov chain Monte Carlo methods can be extremely challenging in many modern day applications. [sent-12, score-0.095]

6 Constructing a Markov chain that adapts to the target distribution while still drawing samples from the correct stationary distribution is challenging, although much research over the last 15 years has resulted in a variety of approaches and theoretical results. [sent-15, score-0.199]

7 Adaptive MCMC for example, allows for global adaptation based on the partial or full history of a chain; this breaks its Markov property, although it has been shown that subject to some technical conditions [2,3] the resulting chain will still converge to the desired stationary distribution. [sent-16, score-0.173]

8 Most recently, advances in Riemannian Manifold MCMC allow locally changing, position speciﬁc proposals to be made based on the underlying ∗ http://www. [sent-17, score-0.22]

9 net/people/ben-calderhead 1 geometry of the target distribution [1]. [sent-19, score-0.267]

10 It is useful for inference over large numbers of strongly covarying parameters, however this methodology is still not suitable for all statistical models; in its current form it is only applicable to models that admit an analytic expression for the metric tensor. [sent-21, score-0.324]

11 In practice, there are many commonly used models for which the Expected Fisher Information is not analytically tractable, such as when a robust Student-t error model is employed to construct the likelihood. [sent-22, score-0.099]

12 In this paper we propose the use of a locally adaptive MCMC algorithm that approximates the local Riemannian geometry at each point in the target space. [sent-23, score-0.498]

13 In particular, we do so by estimating the covariance structure of the tangent vectors at a point on the Riemannian manifold induced by the statistical model. [sent-25, score-0.62]

14 Considering this geometric problem as one of inverse covariance estimation naturally leads us to the use of an 1 regularised maximum likelihood estimator. [sent-26, score-0.271]

15 This approximate inverse approach allows the required geometry to be estimated with few samples, enabling good proposals for the Markov chain while inducing a natural sparsity in the inverse metric tensor that reduces the associated computational cost. [sent-27, score-1.156]

16 We ﬁrst give a brief characterisation of current adaptive approaches to MCMC, making a distinction between locally and globally adaptive methods, since these two approaches have very different requirements in terms of proving convergence to the stationary distribution. [sent-28, score-0.461]

17 We then discuss the use of geometry in MCMC and the interpretation of such methods as being locally adaptive, before giving the necessary background on Riemannian geometry and MCMC algorithms deﬁned on induced Riemannian manifolds. [sent-29, score-0.502]

18 We focus on the manifold MALA sampler, which is derived from a Langevin diffusion process that takes into account local non-Euclidean geometry, and we discuss simpliﬁcations that may be made for computational efﬁciency. [sent-30, score-0.399]

19 Finally we present a valid MCMC algorithm that estimates the Riemannian geometry at each iteration based on covariance estimates of random vectors tangent to the manifold at the chain’s current point. [sent-31, score-0.805]

20 We demonstrate the use of 1 regularisation to calculate sparse approximate inverses of the metric tensor and investigate the sampling properties of the algorithm on an extremely challenging statistical model for which the Expected Fisher Information is analytically intractable. [sent-32, score-1.036]

21 2 Background We wish to sample from some arbitrary target density π(x) deﬁned on a continuous state space XD , which may be high-dimensional. [sent-33, score-0.128]

22 In a Bayesian con) q(x∗ ) text, we will often have a posterior distribution as our target π(x) = p(θ|y), where y is the data and θ are the parameters of a statistical model. [sent-35, score-0.102]

23 The choice of proposal distribution is the critical factor in determining how efﬁciently the Markov chain can explore the space and whether new moves will be accepted with high probability and be sufﬁciently far from the current point to keep autocorrelation of the samples to a minimum. [sent-36, score-0.363]

24 There is a lot of ﬂexibility in the choice of proposal distribution, in that it may depend on the current point in a deterministic manner. [sent-37, score-0.288]

25 This is an important distinction since globally adaptive methods lose their Markov property and convergence to the stationary distribution must be proven in an alternative manner. [sent-39, score-0.237]

26 It has been shown that such chains may still be usefully employed as long as they satisfy some technical conditions, namely diminishing adaptation and bounded convergence [2]. [sent-40, score-0.125]

27 In addi2 tion, if there is more information about the target density available, then there seems little point in trying to guess the geometric structure when it may be calculated directly. [sent-42, score-0.226]

28 In this paper we focus on locally adaptive methods that employ proposals constructed deterministically from information at the current position of the Markov chain. [sent-43, score-0.409]

29 1 Locally Adaptive MCMC Many geometric-based MCMC methods may be categorised as being locally adaptive. [sent-45, score-0.117]

30 In general, we can deﬁne position-speciﬁc proposal densities based on deterministic functions that depend only on the current point. [sent-47, score-0.23]

31 This idea has been previously employed to develop approaches for sampling multimodal distributions whereby large initial jumps followed by deterministic optimisation functions were used to create mode-jumping proposal mechanisms [5]. [sent-48, score-0.353]

32 Incorporating higher order geometry often helps although at an increased computational cost. [sent-51, score-0.208]

33 Using a metric tensor instead of a Hessian matrix lends us nice properties such as invariance to reparameterisation of our statistical model, and positive-deﬁniteness is also assured. [sent-55, score-0.581]

34 Riemannian geometry has been useful in a variety of other machine learning and statistical contexts [8] however the limiting factor is usually analytic or computational tractability. [sent-56, score-0.251]

35 Much work has been done since then elucidating the relationship between statistics and Riemannian geometry, in particular examining geometric concepts such as distance, curvature and geodesics on statistical manifolds, within a ﬁeld that has become known as Information Geometry [6]. [sent-58, score-0.145]

36 We ﬁrst provide an overview of Riemannian geometry and MCMC algorithms deﬁned on Riemannian manifolds. [sent-59, score-0.208]

37 We then describe a sampling scheme that allows the local geometry to be estimated at each iteration for statistical models that do not admit an analytically tractable metric tensor. [sent-60, score-0.664]

38 1 Riemannian Geometry Informally, a manifold is an n-dimensional space that is locally Euclidean; it is locally equivalent to Rn via some smooth transformation. [sent-62, score-0.463]

39 At each point θ ∈ Rn on a Riemannian manifold M there exists a tangent space, which we denote as Tθ M . [sent-63, score-0.492]

40 We can think of this as a linear approximation to the Riemannian manifold at the point θ and this is simply a standard vector space, whose origin is the current point on the manifold and whose vectors are tangent to this point. [sent-64, score-0.857]

41 The vector space ∂ ∂ Tθ M is spanned by the differential operators ∂θ1 , . [sent-65, score-0.108]

42 , ∂θn , which act on functions deﬁning paths on the underlying manifold [9]. [sent-68, score-0.291]

43 In the context of MCMC we can consider the target density as the 3 log-likelihood of a statistical model given some data, such that at a particular point θ, the derivatives of the log-likelihood are tangent to the manifold and these are just the score vectors at θ, θ L = ∂ ∂ ∂θ1 , . [sent-69, score-0.672]

44 The tangent space at each point θ arises when we equip a differentiable manifold with an inner product at each point, which we can use to measure distance and angles between vectors. [sent-73, score-0.525]

45 This inner product is deﬁned in terms of a metric tensor, Gθ , which deﬁnes a basis on each tangent space Tθ M . [sent-74, score-0.41]

46 The tangent space is therefore a linear approximation of the manifold at a given point and it has the same dimensionality. [sent-75, score-0.492]

47 A natural inner product for this vector space is given by the covariance of the basis score vectors, since the covariance function satisﬁes the same properties as a metric tensor, namely symmetry, bilinearity and positive-deﬁniteness [9]. [sent-76, score-0.406]

48 This squared 1 G distance is known as the ﬁrst fundamental form in Riemannian geometry [9], is invariant to reparameterisations of the coordinates, and importantly for MCMC provides a local measure of distance that takes into account the local 2nd order sensitivity of the statistical model. [sent-78, score-0.305]

49 We note that when the metric tensor is constant for all values of θ then the Riemannian manifold is equivalent to a vector space with constant inner product; further, if the metric tensor is an identity matrix then the manifold simply becomes a Euclidean space. [sent-79, score-1.691]

50 2 Manifold MCMC We consider the manifold version of the MALA sampling algorithm, which proposes moves based on a stochastic differential equation deﬁning a Langevin diffusion [4]. [sent-81, score-0.554]

51 It turns out we can also deﬁne such a diffusion on a Riemannian manifold [12], and so in a similar manner we can derive a sampling algorithm that takes the underlying geometric structure into account when making proposals. [sent-82, score-0.467]

52 We note that this deterministically deﬁnes a position-speciﬁc proposal distribution at each point on the manifold; we may categorise this as another locally adaptive MCMC method and convergence to the invariant density follows from using the standard Metropolis-Hastings ratio. [sent-87, score-0.539]

53 It may be computationally expensive to calculate the 3rd order derivatives needed for working out the rate of change of the metric tensor, and so an obvious approximation is to assume these derivatives are zero for each step. [sent-88, score-0.314]

54 In other words, for each step we can assume that the metric is locally constant. [sent-89, score-0.289]

55 Of course even if the curvature of the manifold is not constant, this simpliﬁed proposal mechanism still deﬁnes a correct MCMC method which converges to the target measure, as we accept or reject moves using a Metropolis-Hastings ratio. [sent-90, score-0.612]

56 In this context, such pre-conditioning no longer needs to be chosen arbitrarily, but rather it may be informed by the geometry of the distribution we are exploring. [sent-92, score-0.239]

57 We point out that any approximations of the metric tensor would be best employed in the simpliﬁed mMALA scheme, deﬁning the covariance of the proposal distribution, or as a ﬂat approximation to a manifold. [sent-93, score-0.826]

58 In the next section we consider the representation of the metric tensor as the covariance of the tangent vectors at each point. [sent-95, score-0.797]

59 We consider a method of estimating this such that convergence is guaranteed by extending the state-space and introducing auxiliary variables that are conditioned on the current point and we demonstrate its potential within a Riemannian geometric context. [sent-96, score-0.174]

60 4 Approximate Geometry for MCMC Proposals We ﬁrst derive an acceptance ratio on an extended state-space that enables convergence to the stationary distribution before describing the implications for developing new differential geometric MCMC methods. [sent-97, score-0.318]

61 The key point here is that we may deﬁne our proposal distribution q(x∗ |xn , dn ) in almost any deterministic manner we wish. [sent-102, score-0.346]

62 Speciﬁcally, each sampled pseudo-data can be used deterministically to give a sample of ∂L given the current θ, all of dθ which may then be used deterministically to obtain an approximation of the covariance of tangent vectors at the current point. [sent-104, score-0.486]

63 This approximation, unlike the Hessian, will always be positive deﬁnite, and gives us an approximation of the metric tensor deﬁning the local geometry. [sent-105, score-0.565]

64 Further, we may use additional deterministic procedures, given xn and dn , to construct better proposals; we consider a sparsity inducing approach in the next section. [sent-106, score-0.349]

65 We adopted the graphical lasso [15, 16], in which the maximum likelihood solution results in the matrix optimisation problem, arg min{− log det(A) + tr(AG) + γ A 0 |Aij |} (6) i=j where G is an empirical covariance matrix and γ is a regularisation parameter. [sent-108, score-0.389]

66 This convex optimisation problem aims to ﬁnd A, the regularised maximum likelihood estimate for the inverse of the covariance matrix. [sent-109, score-0.256]

67 Importantly, the optimisation algorithm we employ is deterministic given our tangent vectors, and therefore does not affect the validity of our MCMC algorithm; indeed we note that we may use any deterministic sparse matrix inverse estimation approaches within this MCMC algorithm. [sent-110, score-0.458]

68 The use of the 1 regularisation promotes sparsity [23]; larger values for the regularisation parameter matrix Λ results in a solution that is more sparse, on the other hand when Λ approaches zero, the solution converges to the inverse of G (assuming it exists). [sent-111, score-0.515]

69 It is also worth noting that the 1 regularisation helps to recover a sparse structure in a high dimensional setting where the number of samples is less than the number of parameters [17]. [sent-112, score-0.245]

70 We used no penalisation for the diagonal and uniform regularisation parameter value for the off-diagonal elements. [sent-114, score-0.204]

71 The motivation for not penalising the diagonal is that it has been shown in the covariance estimation setting that the true inverse is approached as the number of samples is increased [18], and the structure is learned more accurately [19]. [sent-115, score-0.163]

72 The simple regularisation structure allowed code simpliﬁcation and reduction in memory use. [sent-116, score-0.204]

73 In the current context, the use of this approach allows us to obtain sparse approximations to the inverse metric tensor, which may then be used in an MCMC proposal. [sent-119, score-0.4]

74 Indeed, even if we have access to an analytic metric tensor we need not use the full inverse for our proposals; we could still obtain an approximate sparse representation, which may be beneﬁcial computationally. [sent-120, score-0.719]

75 the metric tensor varied too much as the MCMC sampler took large steps across the manifold. [sent-123, score-0.569]

76 Here the dimension is p = 25, and the regularisation parameter γ is 0. [sent-125, score-0.204]

77 4 biologically motivated robust Student-t likelihood, which renders the metric tensor analytically intractable. [sent-146, score-0.605]

78 We examine the efﬁciency of our MCMC method with approximate metric on a well studied toy example, the Fitzhugh-Nagumo model, before examining a realistic, nonlinear and highly challenging example describing enzymatic circadian control in the plant Arabidopsis thaliana [22]. [sent-147, score-0.511]

79 1 Nonlinear Ordinary Differential Equations Statistical modelling using systems of nonlinear ordinary differential equations plays a vital role in unravelling the structure and behaviour of biological processes at a molecular level. [sent-149, score-0.241]

80 This presents a problem for standard manifold MCMC algorithms as it makes the metric tensor analytically intractable. [sent-152, score-0.896]

81 We employed a Student-t likelihood with scaling parameter v = 3, and compared M-H and MALA (both employing scaled isotropic covariances), and simpliﬁed mMALA with approximate metric. [sent-158, score-0.093]

82 As such we consider another larger model that describes the enzymatic control of the circadian networks in Arabidopsis thaliana [21]. [sent-163, score-0.21]

83 We consider 7 Table 2: Comparison of pseudodata sample size on the quality of metric tensor estimation, and hence on sampling efﬁciency, using the circadian network example model, with 10 runs and 10,000 posterior samples. [sent-165, score-0.74]

84 26 Table 3: Summary of results for the circadian network model with 10 runs of each parameter sampling scheme and 10,000 posterior samples. [sent-182, score-0.19]

85 8 inferring the 6 rate parameters that control production and decay of proteins in the nucleus and cytoplasm (see [22] for the equations and full details of the model), again employing a Student-t likelihood for which the Expected Fisher Information is analytically intractable. [sent-200, score-0.124]

86 We ﬁrst investigated the effect that the tangent vector sample size for covariance estimation has on the sampling efﬁciency of simpliﬁed mMALA. [sent-203, score-0.314]

87 The results in Table 2 show that there is a threshold above which a more accurate estimate of the metric tensor does not result in additional sampling advantage. [sent-204, score-0.593]

88 Table 3 shows the time normalised statistical efﬁciency for each of the sampling methods; this time we also compare an Adaptive MCMC algorithm [2] with M-H, MALA, and simpliﬁed mMALA with approximate geometry. [sent-206, score-0.129]

89 Both the M-H and MALA algorithms fail to explore the target distribution and have severe difﬁculties with the extreme scalings and nonlinear correlation structure present in the manifold. [sent-207, score-0.126]

90 7 Conclusions The use of Riemannian geometry can be very useful for enabling efﬁcient sampling from arbitrary probability densities. [sent-209, score-0.263]

91 The metric tensor may be used for creating position-speciﬁc proposal mechanisms that allow MCMC methods to automatically adapt to the local correlation structure induced by the sensitivities of the parameters of a statistical model. [sent-210, score-0.844]

92 The metric tensor may conveniently be deﬁned as the Expected Fisher Information, however this quantity is often either difﬁcult or impossible to compute analytically. [sent-211, score-0.569]

93 We have presented a sampling scheme that approximates the Expected Fisher Information by estimating the covariance structure of the tangent vectors at each point on the manifold. [sent-212, score-0.371]

94 By considering this problem as one of inverse covariance estimation, this naturally led us to consider the use of 1 regularisation to improve the estimation procedure. [sent-213, score-0.367]

95 This had the added beneﬁt of inducing sparsity into the metric tensor, which may offer computational advantages when proposing MCMC moves across the manifold. [sent-214, score-0.344]

96 For future work it will be exciting to investigate the potential impact of approximate, sparse metric tensors for high dimensional problems. [sent-215, score-0.271]

97 Tibshirani, Sparse inverse covariance estimation with the graphical lasso, Biostatistics, 9(3):432-441, 2008 [16] O. [sent-267, score-0.163]

98 Zhu, Sparse permutation invariant covariance estimation, Electronic Journal of Statistics, 2:494-515, 2008 [19] J. [sent-282, score-0.085]

99 Turner, Modelling genetic networks with noisy and varied experimental data: the circadian clock in Arabidopsis thaliana, J. [sent-293, score-0.105]

100 Girolami, Statistical analysis of nonlinear dynamical systems using differential geometric sampling methods, Journal of the Royal Society Interface Focus, 1(6), 2011 [23] R. [sent-298, score-0.271]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('riemannian', 0.36), ('tensor', 0.335), ('mcmc', 0.321), ('manifold', 0.291), ('geometry', 0.208), ('regularisation', 0.204), ('metric', 0.203), ('mala', 0.184), ('tangent', 0.174), ('mmala', 0.167), ('proposal', 0.144), ('langevin', 0.128), ('xn', 0.114), ('differential', 0.108), ('dn', 0.105), ('circadian', 0.105), ('ess', 0.102), ('proposals', 0.098), ('calderhead', 0.092), ('adaptive', 0.091), ('locally', 0.086), ('fisher', 0.085), ('covariance', 0.085), ('inverse', 0.078), ('stationary', 0.075), ('geometric', 0.071), ('analytically', 0.067), ('chain', 0.065), ('thaliana', 0.063), ('target', 0.059), ('optimisation', 0.056), ('arabidopsis', 0.055), ('sampling', 0.055), ('deterministically', 0.051), ('moves', 0.05), ('diffusion', 0.05), ('current', 0.047), ('simpli', 0.045), ('hamiltonian', 0.044), ('lasso', 0.044), ('statistical', 0.043), ('globally', 0.042), ('categorise', 0.042), ('enzymatic', 0.042), ('lassofast', 0.042), ('pseudodata', 0.042), ('sparse', 0.041), ('sustik', 0.041), ('metropolis', 0.041), ('derivatives', 0.04), ('deterministic', 0.039), ('molecular', 0.038), ('density', 0.038), ('accept', 0.037), ('regularised', 0.037), ('riemann', 0.037), ('nonlinear', 0.037), ('position', 0.036), ('carlo', 0.036), ('monte', 0.035), ('austin', 0.035), ('acceptance', 0.035), ('sensitivities', 0.034), ('adaptation', 0.033), ('ciency', 0.033), ('inner', 0.033), ('employed', 0.032), ('atlab', 0.032), ('jeffreys', 0.032), ('ordinary', 0.031), ('inducing', 0.031), ('admit', 0.031), ('approximate', 0.031), ('sampler', 0.031), ('curvature', 0.031), ('markov', 0.031), ('may', 0.031), ('challenging', 0.03), ('niteness', 0.03), ('scalings', 0.03), ('autocorrelation', 0.03), ('diffusions', 0.03), ('employing', 0.03), ('scheme', 0.03), ('hessian', 0.03), ('sparsity', 0.029), ('girolami', 0.029), ('brownian', 0.029), ('convergence', 0.029), ('zn', 0.028), ('reversible', 0.028), ('local', 0.027), ('point', 0.027), ('tensors', 0.027), ('inverses', 0.027), ('ben', 0.027), ('ning', 0.027), ('equations', 0.027), ('mechanisms', 0.027), ('speed', 0.026)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999988 318 nips-2012-Sparse Approximate Manifolds for Differential Geometric MCMC

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

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

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

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

4 0.21003848 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

5 0.14357777 179 nips-2012-Learning Manifolds with K-Means and K-Flats

Author: Guillermo Canas, Tomaso Poggio, Lorenzo Rosasco

Abstract: We study the problem of estimating a manifold from random samples. In particular, we consider piecewise constant and piecewise linear estimators induced by k-means and k-ﬂats, and analyze their performance. We extend previous results for k-means in two separate directions. First, we provide new results for k-means reconstruction on manifolds and, secondly, we prove reconstruction bounds for higher-order approximation (k-ﬂats), for which no known results were previously available. While the results for k-means are novel, some of the technical tools are well-established in the literature. In the case of k-ﬂats, both the results and the mathematical tools are new. 1

6 0.13553545 336 nips-2012-The Coloured Noise Expansion and Parameter Estimation of Diffusion Processes

7 0.11847179 82 nips-2012-Continuous Relaxations for Discrete Hamiltonian Monte Carlo

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

9 0.11062238 349 nips-2012-Training sparse natural image models with a fast Gibbs sampler of an extended state space

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

11 0.10260695 272 nips-2012-Practical Bayesian Optimization of Machine Learning Algorithms

12 0.097366564 107 nips-2012-Effective Split-Merge Monte Carlo Methods for Nonparametric Models of Sequential Data

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

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

15 0.085131675 326 nips-2012-Structure estimation for discrete graphical models: Generalized covariance matrices and their inverses

16 0.084598228 205 nips-2012-MCMC for continuous-time discrete-state systems

17 0.082170472 164 nips-2012-Iterative Thresholding Algorithm for Sparse Inverse Covariance Estimation

18 0.081484586 126 nips-2012-FastEx: Hash Clustering with Exponential Families

19 0.079165041 129 nips-2012-Fast Variational Inference in the Conjugate Exponential Family

20 0.078277841 184 nips-2012-Learning Probability Measures with respect to Optimal Transport Metrics

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.206), (1, 0.057), (2, 0.019), (3, -0.067), (4, -0.079), (5, 0.022), (6, -0.009), (7, 0.042), (8, 0.077), (9, -0.103), (10, -0.035), (11, -0.274), (12, 0.003), (13, -0.118), (14, -0.179), (15, 0.11), (16, -0.034), (17, 0.033), (18, 0.351), (19, 0.07), (20, 0.208), (21, -0.036), (22, -0.028), (23, 0.02), (24, 0.014), (25, -0.007), (26, 0.018), (27, -0.015), (28, -0.107), (29, -0.1), (30, -0.041), (31, 0.032), (32, -0.063), (33, 0.072), (34, 0.02), (35, -0.053), (36, 0.051), (37, 0.03), (38, -0.036), (39, -0.13), (40, 0.158), (41, -0.013), (42, -0.02), (43, -0.049), (44, -0.107), (45, -0.153), (46, -0.055), (47, -0.028), (48, 0.019), (49, -0.042)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.95787692 318 nips-2012-Sparse Approximate Manifolds for Differential Geometric MCMC

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

2 0.80829805 9 nips-2012-A Geometric take on Metric Learning

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

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

Author: Suvrit Sra

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

Author: Michael Collins, Shay B. Cohen

5 0.54002434 225 nips-2012-Multi-task Vector Field Learning

Author: Binbin Lin, Sen Yang, Chiyuan Zhang, Jieping Ye, Xiaofei He

Abstract: Multi-task learning (MTL) aims to improve generalization performance by learning multiple related tasks simultaneously and identifying the shared information among tasks. Most of existing MTL methods focus on learning linear models under the supervised setting. We propose a novel semi-supervised and nonlinear approach for MTL using vector ﬁelds. A vector ﬁeld is a smooth mapping from the manifold to the tangent spaces which can be viewed as a directional derivative of functions on the manifold. We argue that vector ﬁelds provide a natural way to exploit the geometric structure of data as well as the shared differential structure of tasks, both of which are crucial for semi-supervised multi-task learning. In this paper, we develop multi-task vector ﬁeld learning (MTVFL) which learns the predictor functions and the vector ﬁelds simultaneously. MTVFL has the following key properties. (1) The vector ﬁelds MTVFL learns are close to the gradient ﬁelds of the predictor functions. (2) Within each task, the vector ﬁeld is required to be as parallel as possible which is expected to span a low dimensional subspace. (3) The vector ﬁelds from all tasks share a low dimensional subspace. We formalize our idea in a regularization framework and also provide a convex relaxation method to solve the original non-convex problem. The experimental results on synthetic and real data demonstrate the effectiveness of our proposed approach. 1

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

7 0.45959446 301 nips-2012-Scaled Gradients on Grassmann Manifolds for Matrix Completion

8 0.44683662 179 nips-2012-Learning Manifolds with K-Means and K-Flats

9 0.42867848 205 nips-2012-MCMC for continuous-time discrete-state systems

10 0.3964335 336 nips-2012-The Coloured Noise Expansion and Parameter Estimation of Diffusion Processes

11 0.38982758 82 nips-2012-Continuous Relaxations for Discrete Hamiltonian Monte Carlo

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

13 0.37337926 22 nips-2012-A latent factor model for highly multi-relational data

14 0.36599213 349 nips-2012-Training sparse natural image models with a fast Gibbs sampler of an extended state space

15 0.33731893 254 nips-2012-On the Sample Complexity of Robust PCA

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

17 0.32661712 184 nips-2012-Learning Probability Measures with respect to Optimal Transport Metrics

18 0.32524443 177 nips-2012-Learning Invariant Representations of Molecules for Atomization Energy Prediction

19 0.32144496 242 nips-2012-Non-linear Metric Learning

20 0.31324714 118 nips-2012-Entangled Monte Carlo

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.037), (21, 0.044), (38, 0.105), (42, 0.025), (43, 0.105), (54, 0.038), (55, 0.033), (72, 0.072), (74, 0.062), (76, 0.211), (80, 0.09), (92, 0.068)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.93633962 257 nips-2012-One Permutation Hashing

Author: Ping Li, Art Owen, Cun-hui Zhang

Abstract: Minwise hashing is a standard procedure in the context of search, for efﬁciently estimating set similarities in massive binary data such as text. Recently, b-bit minwise hashing has been applied to large-scale learning and sublinear time nearneighbor search. The major drawback of minwise hashing is the expensive preprocessing, as the method requires applying (e.g.,) k = 200 to 500 permutations on the data. This paper presents a simple solution called one permutation hashing. Conceptually, given a binary data matrix, we permute the columns once and divide the permuted columns evenly into k bins; and we store, for each data vector, the smallest nonzero location in each bin. The probability analysis illustrates that this one permutation scheme should perform similarly to the original (k-permutation) minwise hashing. Our experiments with training SVM and logistic regression conﬁrm that one permutation hashing can achieve similar (or even better) accuracies compared to the k-permutation scheme. See more details in arXiv:1208.1259.

same-paper 2 0.92393643 318 nips-2012-Sparse Approximate Manifolds for Differential Geometric MCMC

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

3 0.91821271 107 nips-2012-Effective Split-Merge Monte Carlo Methods for Nonparametric Models of Sequential Data

Author: Michael C. Hughes, Erik B. Sudderth, Emily B. Fox

Abstract: Applications of Bayesian nonparametric methods require learning and inference algorithms which efﬁciently explore models of unbounded complexity. We develop new Markov chain Monte Carlo methods for the beta process hidden Markov model (BP-HMM), enabling discovery of shared activity patterns in large video and motion capture databases. By introducing split-merge moves based on sequential allocation, we allow large global changes in the shared feature structure. We also develop data-driven reversible jump moves which more reliably discover rare or unique behaviors. Our proposals apply to any choice of conjugate likelihood for observed data, and we show success with multinomial, Gaussian, and autoregressive emission models. Together, these innovations allow tractable analysis of hundreds of time series, where previous inference required clever initialization and lengthy burn-in periods for just six sequences. 1

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

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

5 0.90649122 101 nips-2012-Discriminatively Trained Sparse Code Gradients for Contour Detection

Author: Ren Xiaofeng, Liefeng Bo

Abstract: Finding contours in natural images is a fundamental problem that serves as the basis of many tasks such as image segmentation and object recognition. At the core of contour detection technologies are a set of hand-designed gradient features, used by most approaches including the state-of-the-art Global Pb (gPb) operator. In this work, we show that contour detection accuracy can be significantly improved by computing Sparse Code Gradients (SCG), which measure contrast using patch representations automatically learned through sparse coding. We use K-SVD for dictionary learning and Orthogonal Matching Pursuit for computing sparse codes on oriented local neighborhoods, and apply multi-scale pooling and power transforms before classifying them with linear SVMs. By extracting rich representations from pixels and avoiding collapsing them prematurely, Sparse Code Gradients effectively learn how to measure local contrasts and ﬁnd contours. We improve the F-measure metric on the BSDS500 benchmark to 0.74 (up from 0.71 of gPb contours). Moreover, our learning approach can easily adapt to novel sensor data such as Kinect-style RGB-D cameras: Sparse Code Gradients on depth maps and surface normals lead to promising contour detection using depth and depth+color, as veriﬁed on the NYU Depth Dataset. 1

6 0.9001646 250 nips-2012-On-line Reinforcement Learning Using Incremental Kernel-Based Stochastic Factorization

7 0.88921952 329 nips-2012-Super-Bit Locality-Sensitive Hashing

8 0.88883448 90 nips-2012-Deep Learning of Invariant Features via Simulated Fixations in Video

9 0.88641685 209 nips-2012-Max-Margin Structured Output Regression for Spatio-Temporal Action Localization

10 0.88428235 54 nips-2012-Bayesian Probabilistic Co-Subspace Addition

11 0.88371634 188 nips-2012-Learning from Distributions via Support Measure Machines

12 0.87866527 41 nips-2012-Ancestor Sampling for Particle Gibbs

13 0.87792766 336 nips-2012-The Coloured Noise Expansion and Parameter Estimation of Diffusion Processes

14 0.87605405 203 nips-2012-Locating Changes in Highly Dependent Data with Unknown Number of Change Points

15 0.87604654 163 nips-2012-Isotropic Hashing

16 0.87354439 197 nips-2012-Learning with Recursive Perceptual Representations

17 0.87332553 74 nips-2012-Collaborative Gaussian Processes for Preference Learning

18 0.87314308 321 nips-2012-Spectral learning of linear dynamics from generalised-linear observations with application to neural population data

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

20 0.87299412 144 nips-2012-Gradient-based kernel method for feature extraction and variable selection