jmlr jmlr2013 jmlr2013-86 knowledge-graph by maker-knowledge-mining

86 jmlr-2013-Parallel Vector Field Embedding

Source: pdf

Author: Binbin Lin, Xiaofei He, Chiyuan Zhang, Ming Ji

Abstract: We propose a novel local isometry based dimensionality reduction method from the perspective of vector ﬁelds, which is called parallel vector ﬁeld embedding (PFE). We ﬁrst give a discussion on local isometry and global isometry to show the intrinsic connection between parallel vector ﬁelds and isometry. The problem of ﬁnding an isometry turns out to be equivalent to ﬁnding orthonormal parallel vector ﬁelds on the data manifold. Therefore, we ﬁrst ﬁnd orthonormal parallel vector ﬁelds by solving a variational problem on the manifold. Then each embedding function can be obtained by requiring its gradient ﬁeld to be as close to the corresponding parallel vector ﬁeld as possible. Theoretical results show that our method can precisely recover the manifold if it is isometric to a connected open subset of Euclidean space. Both synthetic and real data examples demonstrate the effectiveness of our method even if there is heavy noise and high curvature. Keywords: manifold learning, isometry, vector ﬁeld, covariant derivative, out-of-sample extension

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 EDU Department of Computer Science University of Illinois at Urbana Champaign Urbana, IL 61801, USA Editor: Mikhail Belkin Abstract We propose a novel local isometry based dimensionality reduction method from the perspective of vector ﬁelds, which is called parallel vector ﬁeld embedding (PFE). [sent-8, score-1.055]

2 We ﬁrst give a discussion on local isometry and global isometry to show the intrinsic connection between parallel vector ﬁelds and isometry. [sent-9, score-1.131]

3 The problem of ﬁnding an isometry turns out to be equivalent to ﬁnding orthonormal parallel vector ﬁelds on the data manifold. [sent-10, score-0.768]

4 Therefore, we ﬁrst ﬁnd orthonormal parallel vector ﬁelds by solving a variational problem on the manifold. [sent-11, score-0.425]

5 Then each embedding function can be obtained by requiring its gradient ﬁeld to be as close to the corresponding parallel vector ﬁeld as possible. [sent-12, score-0.605]

6 Keywords: manifold learning, isometry, vector ﬁeld, covariant derivative, out-of-sample extension 1. [sent-15, score-0.456]

7 However, these linear methods may fail to recover the intrinsic manifold structure when the data manifold is not a low dimensional subspace or an afﬁne manifold. [sent-27, score-0.549]

8 , 2000), locally linear embedding (LLE, Roweis and Saul, 2000), Laplacian eigenmaps (LE, Belkin and Niyogi, 2001), Hessian eigenmaps (HLLE, Donoho and Grimes, 2003) and diffusion maps (Coifman and Lafon, 2006; Lafon and Lee, 2006; Nadler et al. [sent-30, score-0.392]

9 Isomap generalizes MDS to the nonlinear manifold case which tries to preserve pairwise geodesic distances on the data manifold. [sent-32, score-0.385]

10 Isomap is an instance of global isometry based dimensionality reduction techniques, which tries to preserve the distance function or the metric of the manifold globally. [sent-34, score-0.832]

11 HLLE is based on local isometry criterion, which successfully overcomes this problem. [sent-36, score-0.382]

12 MVU can be thought of as an instance of local isometry with additional consideration that the distances between two points that are not neighbors are maximized. [sent-47, score-0.429]

13 Tangent space based methods have also received considerable interest recently, such as local tangent space alignment (LTSA, Zhang and Zha, 2004), manifold charting (Brand, 2003), Riemannian Manifold Learning (RML, Lin and Zha, 2008) and locally smooth manifold learning (LSML, Doll´ r et al. [sent-48, score-0.781]

14 LSML tries to learn smooth tangent spaces of the manifold by proposing a smoothness regularization term of tangent spaces. [sent-54, score-0.742]

15 Vector diffusion maps (VDM, Singer and Wu, 2011) is a much recent work which considers the tangent spaces structure of the manifold to deﬁne and preserve the vector diffusion distance. [sent-55, score-0.725]

16 In this paper, we propose a novel dimensionality reduction method, called parallel vector ﬁeld embedding (PFE), from the perspective of vector ﬁelds. [sent-56, score-0.673]

17 We ﬁrst give a discussion on local isometry and global isometry to show the intrinsic connection between parallel vector ﬁelds and isometry. [sent-58, score-1.131]

18 The problem of ﬁnding an isometry turns out to be equivalent to ﬁnding orthonormal parallel vector ﬁelds on the data manifold. [sent-59, score-0.768]

19 Therefore, we ﬁrst ﬁnd orthonormal parallel vector ﬁelds by minimizing the covariant derivative of a vector ﬁeld. [sent-60, score-0.659]

20 We then ﬁnd an embedding function whose gradient ﬁeld is as close to the parallel ﬁeld as possible. [sent-61, score-0.56]

21 Naturally, the corresponding embedding consisted 2946 PARALLEL V ECTOR F IELD E MBEDDING of embedding functions preserves the metric of the manifold. [sent-63, score-0.526]

22 Our theoretical study shows that, if the manifold is isometric to a connected open subset of Euclidean space, our method can faithfully recover the metric structure of the manifold. [sent-67, score-0.388]

23 The organization of the paper is as follows: In the next section, we provide a description of the dimensionality reduction problem from the perspectives of isometry and vector ﬁelds. [sent-68, score-0.464]

24 A Riemannian metric is a Euclidean inner product g p on each of the tangent space Tp M , where p is a point on the manifold M . [sent-74, score-0.511]

25 In this paper, we only consider manifolds that are diffeomorphic to an open connected subset of Euclidean space like semi-sphere, swiss roll, swiss roll with hole, and so on. [sent-91, score-0.548]

26 1 Local Isometry and Global Isometry With the assumption that the manifold is diffeomorphic to an open subset of Rd , the goal of dimensionality reduction is to preserve the intrinsic geometry of the manifold as much as possible. [sent-93, score-0.711]

27 Here we consider two kinds of isometry, that are, 2947 L IN , H E , Z HANG AND J I local isometry and global isometry. [sent-96, score-0.436]

28 1 In the following we give the deﬁnitions and properties of local isometry and global isometry. [sent-97, score-0.436]

29 For a map between manifolds F : M → N , F is called local isometry if h(dFp (v), dFp (v)) = g(v, v) for all p ∈ M , v ∈ Tp M . [sent-99, score-0.47]

30 Intuitively, local isometry preserves the metric of the manifold locally. [sent-110, score-0.7]

31 If the local isometry F is also a diffeomorphism, then it becomes global isometry. [sent-111, score-0.436]

32 Deﬁnition 3 (Global Isometry, Lee, 2003) A map F : M → N is called global isometry between manifolds if it is a diffeomorphism and also a local isometry. [sent-112, score-0.596]

33 This is because that, although local isometry maps geodesics to geodesics, the shortest geodesic between two points on M may not be the shortest geodesic on N . [sent-121, score-0.578]

34 On the other hand, based on our assumption that the manifold M is diffeomorphic to an open subset of Rd , it sufﬁces to ﬁnd a local isometry which is also a diffeomorphism, according to Deﬁnition 3. [sent-130, score-0.684]

35 In many differential geometry textbooks, global isometry is often referred to as isometry or Riemannian isometry. [sent-132, score-0.78]

36 2948 PARALLEL V ECTOR F IELD E MBEDDING Figure 1: Local isometry but not global isometry. [sent-133, score-0.397]

37 2 Gradient Fields and Local Isometry Our analysis has shown that ﬁnding a global isometry is equivalent to ﬁnding a local isometry which is also a diffeomorphism. [sent-138, score-0.779]

38 , fd ) : M → Rd , there is a deep connection between local isometry and the differential dF = (d f1 , . [sent-142, score-0.484]

39 For the relationship between local isometry and differential, we have the following proposition: Proposition 2 Consider a map F : M ⊂ Rm → Rd . [sent-148, score-0.433]

40 Since we use the induced metric for the manifold M , the computation of inner product in tangent space is the same as the standard inner product in Euclidean space. [sent-168, score-0.511]

41 This proposition indicates that ﬁnding a local isometry F is equivalent to ﬁnding d orthonormal differentials d fi , i = 1, . [sent-175, score-0.596]

42 Parallel Field Embedding In this section, we introduce our parallel ﬁeld embedding (PFE) algorithm for dimensionality reduction. [sent-183, score-0.549]

43 We ﬁrst try to ﬁnd orthonormal parallel vector ﬁelds on the manifold. [sent-191, score-0.425]

44 In Theorem 2, we show that if the manifold can be isometrically embedded into the Euclidean space, then there exist orthonormal parallel ﬁelds and each parallel ﬁeld is exactly a gradient ﬁeld. [sent-193, score-1.028]

45 We will also discuss the relationship among local isometry, global isometry and parallel ﬁelds. [sent-197, score-0.71]

46 Deﬁnition 4 (Parallel Field, Petersen, 1998) A vector ﬁeld X on manifold M is a parallel vector ﬁeld (or parallel ﬁeld) if ∇X ≡ 0, where ∇ is the covariant derivative on the manifold M . [sent-198, score-1.343]

47 Given a point p on the manifold and a vector v p on the tangent space Tp M , then ∇v p X is a vector at point p which measures how the vector ﬁeld X changes along the direction v p at point p. [sent-200, score-0.619]

48 For parallel ﬁelds, we also have the following proposition: Proposition 3 Let V and W be parallel ﬁelds on M associated with the metric g. [sent-203, score-0.575]

49 This corollary tells us if we want to check the orthogonality of the parallel ﬁelds at every point, it sufﬁces to compute the integral of the inner product of the parallel ﬁelds. [sent-221, score-0.572]

50 Also we have the following corollary: Corollary 2 Let V be a parallel vector ﬁeld on M , then ∀p ∈ M , Vp = constant where Vp represents the vector at p of the vector ﬁeld V . [sent-223, score-0.409]

51 Since every tangent vector of a parallel ﬁeld has a constant length, we can perform normalization 2951 L IN , H E , Z HANG AND J I of the parallel ﬁeld simply as dividing every tangent vector of the parallel ﬁeld by a same length. [sent-225, score-1.364]

52 According to these results, ﬁnding orthonormal parallel ﬁelds becomes much easier: we ﬁrst ﬁnd orthogonal parallel ﬁelds on the manifold one by one by requiring that the integral of the inner product of two parallel ﬁelds is zero. [sent-226, score-1.233]

53 Before presenting our main result, we still need to introduce some concepts and properties on the relationship between isometry and parallel ﬁelds. [sent-228, score-0.617]

54 Next we show that the differential of an isometry preserves covariant derivative. [sent-246, score-0.569]

55 More importantly, we show that an isometry preserves parallelism, that is, its differential carries a parallel vector ﬁeld to another parallel vector ﬁeld. [sent-248, score-1.054]

56 dF is an isometric isomorphism on the space of parallel ﬁelds. [sent-252, score-0.419]

57 Proof Let Y be a parallel ﬁeld on M , we show that dF(Y ) is also a parallel ﬁeld. [sent-253, score-0.548]

58 Combining these two facts, dF is an isometric isomorphism on the space of parallel ﬁelds. [sent-264, score-0.419]

59 Now we show that the gradient ﬁelds of a local isometry are also parallel ﬁelds. [sent-265, score-0.709]

60 Proof According to the property of local isometry, for very point p ∈ M , there is a neighborhood U ⊂ M of p such that F|U : U → F(U) is a global isometry of U onto an open subset F(U) of Rd (please see Lee, 2003, pg. [sent-273, score-0.436]

61 This proposition tells us that the gradient ﬁeld of a local isometry is also a parallel ﬁeld. [sent-289, score-0.737]

62 Since it is usually not easy to ﬁnd a global isometry directly, in this paper, we try to ﬁnd a set of orthonormal parallel ﬁelds ﬁrst, and then ﬁnd an embedding function whose gradient ﬁeld is equal to the parallel ﬁeld. [sent-290, score-1.337]

63 As we discussed in Section 2, the gradient ﬁelds of the isometry have to be orthonormal parallel ﬁelds. [sent-312, score-0.776]

64 Then the covariant derivative along the direction dγ(t) |t=0 dt can be computed by projecting dV |t=0 to the tangent space Tx M at x. [sent-318, score-0.415]

65 After ﬁnding the parallel vector ﬁelds Vi on M , the embedding function can be obtained by minimizing the following objective function: Φ( f ) = M ∇ f −V 2 dx. [sent-342, score-0.552]

66 If there exist a global isometry ϕ : M → D ⊂ Rd , where D is an open connected subset of Rd , then there is an orthonormal basis {Vi }d of the parallel ﬁelds on M , and embedding function fi : M → R whose i=1 gradient ﬁeld satisﬁes ∇ fi = Vi , i = 1, . [sent-346, score-1.223]

67 According to Proposition 5, we know that a global isometry preserves parallelism, that is, its differential carries a parallel vector ﬁeld to another parallel vector ﬁeld. [sent-358, score-1.108]

68 Thus for a global isometry ϕ, dϕ maps parallel ﬁelds to parallel ﬁelds and dϕ is an isometric isomorphism, so is dϕ−1 . [sent-359, score-1.088]

69 Thus the space of parallel ﬁelds on M is isomorphic to the space of parallel ﬁelds on D. [sent-360, score-0.548]

70 Therefore there exists an orthonormal basis {Vi }d of the space of the parallel ﬁelds on M . [sent-361, score-0.38]

71 Next we show that such F is a global isometry on M . [sent-385, score-0.397]

72 Thus F is a local isometry according to Proposition 2. [sent-394, score-0.382]

73 Since F is a local isometry and a diffeomorphism, it is a global isometry. [sent-417, score-0.436]

74 The ﬁrst variation is the choice of the orthonormal basis of parallel ﬁelds. [sent-424, score-0.38]

75 Thus the space of global isometry on M is actually O(d) × Rd . [sent-426, score-0.397]

76 When there is no isometry between the manifold M and Rd , our approach can still ﬁnd a reasonably good embedding function. [sent-429, score-0.834]

77 It would be important to note that, in such cases, the isometric embedding or nearly isometric embedding does not exist. [sent-435, score-0.672]

78 The implementation includes two steps, ﬁrst we estimate parallel vector ﬁelds on manifold from random points, and then we reconstruct embedding functions by requiring that the gradient ﬁelds are as close to the parallel ﬁelds as possible. [sent-439, score-1.137]

79 After ﬁnding d orthonormal vector ﬁelds and the corresponding embedding function fi , the ﬁnal map F is given by F = ( f1 , . [sent-446, score-0.515]

80 According to the deﬁnition of vector ﬁelds, Vxi should be a tangent vector in the tangent space Txi M . [sent-472, score-0.542]

81 Thus it can be represented by local coordinates of the tangent space, (5) Vxi = Ti vi , T where vi ∈ Rd . [sent-473, score-0.42]

82 Then the covariant derivative of vector ﬁeld V along ei j is given by (please see Figure 3) ∇ei j V dV |t=0 ) dt V (γ(t)) −V (γ(0)) = Pi lim t→0 t (Vx j −Vxi ) = Pi di j √ wi j (PiVx j −Vxi ), ≈ = Pi ( √ where di j ≈ 1/ wi j approximates the geodesic distance di j of xi and x j . [sent-486, score-0.461]

83 Recall Corollary 2 tells us for any point p ∈ M , the tangent vector Vp of a parallel ﬁeld V has a constant length. [sent-529, score-0.545]

84 2 E MBEDDING Once the parallel vector ﬁelds Vi are obtained, the embedding functions fi : M → R can be constructed by requiring their gradient ﬁelds to be as close to Vi as possible. [sent-543, score-0.685]

85 Recall that, if the manifold is isometric to Euclidean space, then the vector ﬁeld computed via Equation (1) is also a gradient ﬁeld. [sent-544, score-0.459]

86 However, if the manifold is not isometric to Euclidean space, V may not be a gradient ﬁeld. [sent-545, score-0.414]

87 The exponential map expx : Tx M → M maps the tangent space Tx M to the manifold M . [sent-550, score-0.617]

88 , vn+n′ , where Vo denotes the tangent vectors on the n n+1 o n 1 original training points and Vn denotes the tangent vectors on new points. [sent-638, score-0.476]

89 The idea of computing the covariant derivative is to ﬁnd a way to compute the difference between vectors on different tangent spaces. [sent-693, score-0.415]

90 VDM proposed an intrinsic way to compute covariant derivative using the concept of parallel transport. [sent-694, score-0.496]

91 They ﬁrst transported the vectors to the same tangent space using the parallel transport, and then compute the difference of vectors on the tangent space. [sent-695, score-0.726]

92 The way of ﬁnding the parallel transport between two points is to compute the orthogonal transformation between two corresponding tangent spaces. [sent-696, score-0.573]

93 The data set contains 2000 points sampled from a swiss roll with a hole, which is a 2D manifold embedded in R3 . [sent-711, score-0.608]

94 On the other hand, the swiss roll is a ﬂat manifold with zero-curvature everywhere and thus can be isometrically embedded in R2 . [sent-714, score-0.61]

95 A local isometry preserving embedding is considered faithful and thus would get a low R-score. [sent-787, score-0.615]

96 MVU unfolds the manifold correctly, but does not preserve the isometry well. [sent-809, score-0.643]

97 6 Classiﬁcation after Embedding In many scenarios, calculating the low-dimensional embedding of the data manifold is not the ﬁnal step. [sent-985, score-0.491]

98 Conclusion We have introduced a novel local isometry based dimensionality reduction method from the perspective of vector ﬁeld. [sent-1059, score-0.503]

99 If the manifold is isometric to Euclidean space, then the obtained vector ﬁeld is parallel. [sent-1072, score-0.406]

100 Local procrustes for manifold embedding: a measure of embedding quality and embedding algorithms. [sent-1165, score-0.724]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('isometry', 0.343), ('pfe', 0.34), ('parallel', 0.274), ('manifold', 0.258), ('embedding', 0.233), ('tangent', 0.226), ('elds', 0.21), ('swiss', 0.178), ('df', 0.176), ('covariant', 0.153), ('eld', 0.152), ('ector', 0.144), ('ield', 0.144), ('mbedding', 0.144), ('rc', 0.118), ('roll', 0.111), ('hlle', 0.109), ('orthonormal', 0.106), ('isomap', 0.106), ('isometric', 0.103), ('vxi', 0.102), ('mvu', 0.098), ('lle', 0.096), ('dfp', 0.095), ('vdm', 0.093), ('fi', 0.08), ('tx', 0.078), ('txi', 0.076), ('diffeomorphism', 0.072), ('laplacian', 0.071), ('hang', 0.066), ('fd', 0.062), ('vi', 0.059), ('diffusion', 0.057), ('global', 0.054), ('gradient', 0.053), ('geodesic', 0.053), ('pi', 0.052), ('hs', 0.051), ('petersen', 0.051), ('map', 0.051), ('xi', 0.05), ('wi', 0.049), ('euclidean', 0.049), ('tp', 0.048), ('vector', 0.045), ('riemannian', 0.045), ('rd', 0.045), ('face', 0.044), ('sd', 0.044), ('diffeomorphic', 0.044), ('le', 0.044), ('expx', 0.042), ('tit', 0.042), ('isomorphism', 0.042), ('preserve', 0.042), ('dimensionality', 0.042), ('differential', 0.04), ('maps', 0.04), ('hole', 0.039), ('local', 0.039), ('coordinates', 0.037), ('vt', 0.037), ('embedded', 0.037), ('manifolds', 0.037), ('please', 0.037), ('derivative', 0.036), ('hessian', 0.035), ('reduction', 0.034), ('bnn', 0.034), ('gx', 0.034), ('goldberg', 0.034), ('preserves', 0.033), ('intrinsic', 0.033), ('tries', 0.032), ('eigenmaps', 0.031), ('vp', 0.029), ('nearest', 0.029), ('proposition', 0.028), ('geometrical', 0.028), ('rm', 0.027), ('metric', 0.027), ('topology', 0.027), ('tensor', 0.027), ('pose', 0.027), ('geodesics', 0.026), ('isometrically', 0.026), ('transport', 0.026), ('belkin', 0.026), ('ei', 0.026), ('bno', 0.025), ('defant', 0.025), ('expxi', 0.025), ('equation', 0.025), ('points', 0.024), ('vn', 0.024), ('integral', 0.024), ('orthogonal', 0.023), ('pca', 0.023), ('neighbors', 0.023)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.9999997 86 jmlr-2013-Parallel Vector Field Embedding

Author: Binbin Lin, Xiaofei He, Chiyuan Zhang, Ming Ji

2 0.28458217 34 jmlr-2013-Distance Preserving Embeddings for General n-Dimensional Manifolds

Author: Nakul Verma

Abstract: Low dimensional embeddings of manifold data have gained popularity in the last decade. However, a systematic ﬁnite sample analysis of manifold embedding algorithms largely eludes researchers. Here we present two algorithms that embed a general n-dimensional manifold into Rd (where d only depends on some key manifold properties such as its intrinsic dimension, volume and curvature) that guarantee to approximately preserve all interpoint geodesic distances. Keywords: manifold learning, isometric embeddings, non-linear dimensionality reduction, Nash’s embedding theorem

3 0.21497381 69 jmlr-2013-Manifold Regularization and Semi-supervised Learning: Some Theoretical Analyses

Author: Partha Niyogi

Abstract: Manifold regularization (Belkin et al., 2006) is a geometrically motivated framework for machine learning within which several semi-supervised algorithms have been constructed. Here we try to provide some theoretical understanding of this approach. Our main result is to expose the natural structure of a class of problems on which manifold regularization methods are helpful. We show that for such problems, no supervised learner can learn effectively. On the other hand, a manifold based learner (that knows the manifold or “learns” it from unlabeled examples) can learn with relatively few labeled examples. Our analysis follows a minimax style with an emphasis on ﬁnite sample results (in terms of n: the number of labeled examples). These results allow us to properly interpret manifold regularization and related spectral and geometric algorithms in terms of their potential use in semi-supervised learning. Keywords: semi-supervised learning, manifold regularization, graph Laplacian, minimax rates

4 0.18603145 77 jmlr-2013-On the Convergence of Maximum Variance Unfolding

Author: Ery Arias-Castro, Bruno Pelletier

Abstract: Maximum Variance Unfolding is one of the main methods for (nonlinear) dimensionality reduction. We study its large sample limit, providing speciﬁc rates of convergence under standard assumptions. We ﬁnd that it is consistent when the underlying submanifold is isometric to a convex subset, and we provide some simple examples where it fails to be consistent. Keywords: maximum variance unfolding, isometric embedding, U-processes, empirical processes, proximity graphs.

5 0.12390742 59 jmlr-2013-Large-scale SVD and Manifold Learning

Author: Ameet Talwalkar, Sanjiv Kumar, Mehryar Mohri, Henry Rowley

Abstract: This paper examines the efﬁcacy of sampling-based low-rank approximation techniques when applied to large dense kernel matrices. We analyze two common approximate singular value decomposition techniques, namely the Nystr¨ m and Column sampling methods. We present a theoretical o comparison between these two methods, provide novel insights regarding their suitability for various tasks and present experimental results that support our theory. Our results illustrate the relative strengths of each method. We next examine the performance of these two techniques on the largescale task of extracting low-dimensional manifold structure given millions of high-dimensional face images. We address the computational challenges of non-linear dimensionality reduction via Isomap and Laplacian Eigenmaps, using a graph containing about 18 million nodes and 65 million edges. We present extensive experiments on learning low-dimensional embeddings for two large face data sets: CMU-PIE (35 thousand faces) and a web data set (18 million faces). Our comparisons show that the Nystr¨ m approximation is superior to the Column sampling method for this o task. Furthermore, approximate Isomap tends to perform better than Laplacian Eigenmaps on both clustering and classiﬁcation with the labeled CMU-PIE data set. Keywords: low-rank approximation, manifold learning, large-scale matrix factorization

6 0.11368141 96 jmlr-2013-Regularization-Free Principal Curve Estimation

7 0.11258279 10 jmlr-2013-Algorithms and Hardness Results for Parallel Large Margin Learning

8 0.10630911 112 jmlr-2013-Tapkee: An Efficient Dimension Reduction Library

9 0.081904665 90 jmlr-2013-Quasi-Newton Method: A New Direction

10 0.066324912 32 jmlr-2013-Differential Privacy for Functions and Functional Data

11 0.060904138 109 jmlr-2013-Stress Functions for Nonlinear Dimension Reduction, Proximity Analysis, and Graph Drawing

12 0.045606069 72 jmlr-2013-Multi-Stage Multi-Task Feature Learning

13 0.0441061 23 jmlr-2013-Cluster Analysis: Unsupervised Learning via Supervised Learning with a Non-convex Penalty

14 0.042847097 99 jmlr-2013-Semi-Supervised Learning Using Greedy Max-Cut

15 0.040227719 101 jmlr-2013-Sparse Activity and Sparse Connectivity in Supervised Learning

16 0.039736938 28 jmlr-2013-Construction of Approximation Spaces for Reinforcement Learning

17 0.037495419 70 jmlr-2013-Maximum Volume Clustering: A New Discriminative Clustering Approach

18 0.036548916 117 jmlr-2013-Universal Consistency of Localized Versions of Regularized Kernel Methods

19 0.035801154 108 jmlr-2013-Stochastic Variational Inference

20 0.03452431 120 jmlr-2013-Variational Algorithms for Marginal MAP

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.244), (1, 0.195), (2, 0.078), (3, -0.494), (4, -0.189), (5, 0.035), (6, -0.002), (7, -0.052), (8, -0.077), (9, -0.014), (10, -0.24), (11, 0.03), (12, -0.138), (13, -0.003), (14, 0.097), (15, -0.13), (16, 0.035), (17, 0.041), (18, -0.031), (19, -0.005), (20, 0.041), (21, 0.109), (22, 0.027), (23, 0.009), (24, -0.017), (25, 0.004), (26, -0.087), (27, 0.075), (28, -0.021), (29, -0.064), (30, 0.012), (31, -0.002), (32, 0.038), (33, 0.016), (34, -0.03), (35, 0.101), (36, 0.059), (37, -0.019), (38, 0.053), (39, 0.037), (40, 0.036), (41, -0.041), (42, -0.029), (43, -0.031), (44, -0.022), (45, 0.007), (46, -0.035), (47, -0.005), (48, 0.021), (49, -0.025)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.96544701 86 jmlr-2013-Parallel Vector Field Embedding

Author: Binbin Lin, Xiaofei He, Chiyuan Zhang, Ming Ji

2 0.8423968 34 jmlr-2013-Distance Preserving Embeddings for General n-Dimensional Manifolds

Author: Nakul Verma

3 0.68652356 69 jmlr-2013-Manifold Regularization and Semi-supervised Learning: Some Theoretical Analyses

Author: Partha Niyogi

4 0.53453386 77 jmlr-2013-On the Convergence of Maximum Variance Unfolding

Author: Ery Arias-Castro, Bruno Pelletier

5 0.43965939 112 jmlr-2013-Tapkee: An Efficient Dimension Reduction Library

Author: Sergey Lisitsyn, Christian Widmer, Fernando J. Iglesias Garcia

Abstract: We present Tapkee, a C++ template library that provides efﬁcient implementations of more than 20 widely used dimensionality reduction techniques ranging from Locally Linear Embedding (Roweis and Saul, 2000) and Isomap (de Silva and Tenenbaum, 2002) to the recently introduced BarnesHut-SNE (van der Maaten, 2013). Our library was designed with a focus on performance and ﬂexibility. For performance, we combine efﬁcient multi-core algorithms, modern data structures and state-of-the-art low-level libraries. To achieve ﬂexibility, we designed a clean interface for applying methods to user data and provide a callback API that facilitates integration with the library. The library is freely available as open-source software and is distributed under the permissive BSD 3-clause license. We encourage the integration of Tapkee into other open-source toolboxes and libraries. For example, Tapkee has been integrated into the codebase of the Shogun toolbox (Sonnenburg et al., 2010), giving us access to a rich set of kernels, distance measures and bindings to common programming languages including Python, Octave, Matlab, R, Java, C#, Ruby, Perl and Lua. Source code, examples and documentation are available at http://tapkee.lisitsyn.me. Keywords: dimensionality reduction, machine learning, C++, open source software

6 0.34517133 59 jmlr-2013-Large-scale SVD and Manifold Learning

7 0.33455232 96 jmlr-2013-Regularization-Free Principal Curve Estimation

8 0.3049635 109 jmlr-2013-Stress Functions for Nonlinear Dimension Reduction, Proximity Analysis, and Graph Drawing

9 0.29402635 90 jmlr-2013-Quasi-Newton Method: A New Direction

10 0.28599936 10 jmlr-2013-Algorithms and Hardness Results for Parallel Large Margin Learning

11 0.20670962 101 jmlr-2013-Sparse Activity and Sparse Connectivity in Supervised Learning

12 0.19755298 32 jmlr-2013-Differential Privacy for Functions and Functional Data

13 0.19293682 51 jmlr-2013-Greedy Sparsity-Constrained Optimization

14 0.19146153 72 jmlr-2013-Multi-Stage Multi-Task Feature Learning

15 0.18075176 44 jmlr-2013-Finding Optimal Bayesian Networks Using Precedence Constraints

16 0.1783157 23 jmlr-2013-Cluster Analysis: Unsupervised Learning via Supervised Learning with a Non-convex Penalty

17 0.17772859 25 jmlr-2013-Communication-Efficient Algorithms for Statistical Optimization

18 0.16653298 37 jmlr-2013-Divvy: Fast and Intuitive Exploratory Data Analysis

19 0.16239119 70 jmlr-2013-Maximum Volume Clustering: A New Discriminative Clustering Approach

20 0.15850081 5 jmlr-2013-A Near-Optimal Algorithm for Differentially-Private Principal Components

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.035), (5, 0.087), (6, 0.032), (10, 0.126), (20, 0.018), (23, 0.028), (46, 0.334), (53, 0.018), (68, 0.023), (70, 0.011), (75, 0.082), (85, 0.025), (87, 0.07)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.73886442 86 jmlr-2013-Parallel Vector Field Embedding

Author: Binbin Lin, Xiaofei He, Chiyuan Zhang, Ming Ji

2 0.67246717 18 jmlr-2013-Beyond Fano's Inequality: Bounds on the Optimal F-Score, BER, and Cost-Sensitive Risk and Their Implications

Author: Ming-Jie Zhao, Narayanan Edakunni, Adam Pocock, Gavin Brown

Abstract: Fano’s inequality lower bounds the probability of transmission error through a communication channel. Applied to classiﬁcation problems, it provides a lower bound on the Bayes error rate and motivates the widely used Infomax principle. In modern machine learning, we are often interested in more than just the error rate. In medical diagnosis, different errors incur different cost; hence, the overall risk is cost-sensitive. Two other popular criteria are balanced error rate (BER) and F-score. In this work, we focus on the two-class problem and use a general deﬁnition of conditional entropy (including Shannon’s as a special case) to derive upper/lower bounds on the optimal F-score, BER and cost-sensitive risk, extending Fano’s result. As a consequence, we show that Infomax is not suitable for optimizing F-score or cost-sensitive risk, in that it can potentially lead to low F-score and high risk. For cost-sensitive risk, we propose a new conditional entropy formulation which avoids this inconsistency. In addition, we consider the common practice of using a threshold on the posterior probability to tune performance of a classiﬁer. As is widely known, a threshold of 0.5, where the posteriors cross, minimizes error rate—we derive similar optimal thresholds for F-score and BER. Keywords: balanced error rate, F-score (Fβ -measure), cost-sensitive risk, conditional entropy, lower/upper bound

3 0.48428696 77 jmlr-2013-On the Convergence of Maximum Variance Unfolding

Author: Ery Arias-Castro, Bruno Pelletier

4 0.44086939 70 jmlr-2013-Maximum Volume Clustering: A New Discriminative Clustering Approach

Author: Gang Niu, Bo Dai, Lin Shang, Masashi Sugiyama

Abstract: The large volume principle proposed by Vladimir Vapnik, which advocates that hypotheses lying in an equivalence class with a larger volume are more preferable, is a useful alternative to the large margin principle. In this paper, we introduce a new discriminative clustering model based on the large volume principle called maximum volume clustering (MVC), and then propose two approximation schemes to solve this MVC model: A soft-label MVC method using sequential quadratic programming and a hard-label MVC method using semi-deﬁnite programming, respectively. The proposed MVC is theoretically advantageous for three reasons. The optimization involved in hardlabel MVC is convex, and under mild conditions, the optimization involved in soft-label MVC is akin to a convex one in terms of the resulting clusters. Secondly, the soft-label MVC method pos∗. A preliminary and shorter version has appeared in Proceedings of 14th International Conference on Artiﬁcial Intelligence and Statistics (Niu et al., 2011). The preliminary work was done when GN was studying at Department of Computer Science and Technology, Nanjing University, and BD was studying at Institute of Automation, Chinese Academy of Sciences. A Matlab implementation of maximum volume clustering is available from http://sugiyama-www.cs.titech.ac.jp/∼gang/software.html. c 2013 Gang Niu, Bo Dai, Lin Shang and Masashi Sugiyama. N IU , DAI , S HANG AND S UGIYAMA sesses a clustering error bound. Thirdly, MVC includes the optimization problems of a spectral clustering, two relaxed k-means clustering and an information-maximization clustering as special limit cases when its regularization parameter goes to inﬁnity. Experiments on several artiﬁcial and benchmark data sets demonstrate that the proposed MVC compares favorably with state-of-the-art clustering methods. Keywords: discriminative clustering, large volume principle, sequential quadratic programming, semi-deﬁnite programming, ﬁnite sample stability, clustering error

5 0.43914661 16 jmlr-2013-Bayesian Nonparametric Hidden Semi-Markov Models

Author: Matthew J. Johnson, Alan S. Willsky

Abstract: There is much interest in the Hierarchical Dirichlet Process Hidden Markov Model (HDP-HMM) as a natural Bayesian nonparametric extension of the ubiquitous Hidden Markov Model for learning from sequential and time-series data. However, in many settings the HDP-HMM’s strict Markovian constraints are undesirable, particularly if we wish to learn or encode non-geometric state durations. We can extend the HDP-HMM to capture such structure by drawing upon explicit-duration semi-Markov modeling, which has been developed mainly in the parametric non-Bayesian setting, to allow construction of highly interpretable models that admit natural prior information on state durations. In this paper we introduce the explicit-duration Hierarchical Dirichlet Process Hidden semiMarkov Model (HDP-HSMM) and develop sampling algorithms for efﬁcient posterior inference. The methods we introduce also provide new methods for sampling inference in the ﬁnite Bayesian HSMM. Our modular Gibbs sampling methods can be embedded in samplers for larger hierarchical Bayesian models, adding semi-Markov chain modeling as another tool in the Bayesian inference toolbox. We demonstrate the utility of the HDP-HSMM and our inference methods on both synthetic and real experiments. Keywords: Bayesian nonparametrics, time series, semi-Markov, sampling algorithms, Hierarchical Dirichlet Process Hidden Markov Model

6 0.43773532 3 jmlr-2013-A Framework for Evaluating Approximation Methods for Gaussian Process Regression

7 0.43758985 59 jmlr-2013-Large-scale SVD and Manifold Learning

8 0.43217972 46 jmlr-2013-GURLS: A Least Squares Library for Supervised Learning

9 0.43092453 28 jmlr-2013-Construction of Approximation Spaces for Reinforcement Learning

10 0.43021438 52 jmlr-2013-How to Solve Classification and Regression Problems on High-Dimensional Data with a Supervised Extension of Slow Feature Analysis

11 0.428987 23 jmlr-2013-Cluster Analysis: Unsupervised Learning via Supervised Learning with a Non-convex Penalty

12 0.42751735 116 jmlr-2013-Truncated Power Method for Sparse Eigenvalue Problems

13 0.42570606 96 jmlr-2013-Regularization-Free Principal Curve Estimation

14 0.42476633 50 jmlr-2013-Greedy Feature Selection for Subspace Clustering

15 0.42391545 5 jmlr-2013-A Near-Optimal Algorithm for Differentially-Private Principal Components

16 0.41966829 75 jmlr-2013-Nested Expectation Propagation for Gaussian Process Classification with a Multinomial Probit Likelihood

17 0.41942647 47 jmlr-2013-Gaussian Kullback-Leibler Approximate Inference

18 0.41931874 69 jmlr-2013-Manifold Regularization and Semi-supervised Learning: Some Theoretical Analyses

19 0.41845617 74 jmlr-2013-Multivariate Convex Regression with Adaptive Partitioning

20 0.41645136 22 jmlr-2013-Classifying With Confidence From Incomplete Information