nips nips2002 nips2002-97 knowledge-graph by maker-knowledge-mining

97 nips-2002-Global Versus Local Methods in Nonlinear Dimensionality Reduction

Source: pdf

Author: Vin D. Silva, Joshua B. Tenenbaum

Abstract: Recently proposed algorithms for nonlinear dimensionality reduction fall broadly into two categories which have different advantages and disadvantages: global (Isomap [1]), and local (Locally Linear Embedding [2], Laplacian Eigenmaps [3]). We present two variants of Isomap which combine the advantages of the global approach with what have previously been exclusive advantages of local methods: computational sparsity and the ability to invert conformal maps.

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract Recently proposed algorithms for nonlinear dimensionality reduction fall broadly into two categories which have different advantages and disadvantages: global (Isomap [1]), and local (Locally Linear Embedding [2], Laplacian Eigenmaps [3]). [sent-8, score-0.312]

2 We present two variants of Isomap which combine the advantages of the global approach with what have previously been exclusive advantages of local methods: computational sparsity and the ability to invert conformal maps. [sent-9, score-0.676]

3 1 Introduction In this paper we discuss the problem of nonlinear dimensionality reduction (NLDR): the task of recovering meaningful low-dimensional structures hidden in high-dimensional data. [sent-10, score-0.133]

4 An example might be a set of pixel images of an individual’s face observed under different pose and lighting conditions; the task is to identify the underlying variables (pose angles, direction of light, etc. [sent-11, score-0.242]

5 In many cases of interest, the observed data are found to lie on an embedded submanifold of the high-dimensional space. [sent-13, score-0.146]

6 Classical techniques for manifold learning, such as principal components analysis (PCA) or multidimensional scaling (MDS), are designed to operate when the submanifold is embedded linearly, or almost linearly, in the observation space. [sent-16, score-0.265]

7 However, such algorithms often fail when nonlinear structure cannot simply be regarded as a perturbation from a linear approximation; as in the Swiss roll of Figure 3. [sent-19, score-0.162]

8 In such cases, iterative approaches tend to get stuck at locally optimal solutions that may grossly misrepresent the true geometry of the situation. [sent-20, score-0.102]

9 These methods combine the advantages of PCA and MDS—computational efﬁciency; few free parameters; non-iterative global optimisation of a natural cost function—with the ability to recover the intrinsic geometric structure of a broad class of nonlinear data manifolds. [sent-22, score-0.274]

10 Local approaches (LLE [2], Laplacian Eigenmaps [3]) attempt to preserve the local geometry of the data; essentially, they seek to map nearby points on the manifold to nearby points in the low-dimensional representation. [sent-24, score-0.492]

11 Global approaches (Isomap [1]) attempt to preserve geometry at all scales, mapping nearby points on the manifold to nearby points in low-dimensional space, and faraway points to faraway points. [sent-25, score-0.591]

12 The principal advantages of the global approach are that it tends to give a more faithful representation of the data’s global structure, and that its metric-preserving properties are better understood theoretically. [sent-26, score-0.282]

13 In this paper we show how the global geometric approach, as implemented in Isomap, can be extended in both of these directions. [sent-28, score-0.119]

14 The results are computational efﬁciency and representational capacity equal to or in excess of existing local approaches (LLE, Laplacian Eigenmaps), but with the greater stability and theoretical tractability of the global approach. [sent-29, score-0.127]

15 Most of the work focuses on a small subset of the data, called the landmark points. [sent-33, score-0.24]

16 In Section 2, we describe a perspective on manifold learning in which C-Isomap appears as the natural generalisation of Isomap. [sent-35, score-0.115]

17 In Section 3 we derive L-Isomap from a landmark version of classical MDS. [sent-36, score-0.274]

18 1 Manifold learning and geometric invariants We can view the problem of manifold learning as an attempt to invert a generative model for a set of observations. [sent-38, score-0.193]

19 The object of space manifold learning is to recover and based on a given set of observed data in . [sent-40, score-0.183]

20 Hidden data are generated randomly in , and are then mapped by to become the observed data, so . [sent-42, score-0.083]

21 " ¥ ¨ ¦ © §¥ ¢ £ ¤¢ ¥ The problem as stated is ill-posed: some restriction is needed on if we are to relate the observed geometry of the data to the structure of the hidden variables and itself. [sent-46, score-0.134]

22 The ﬁrst is that is an isometric embedding in the sense of Riemannian geometry; so preserves inﬁnitesmal lengths and angles. [sent-48, score-0.345]

23 The second possibility is that is a conformal embedding; it preserves angles but not lengths. [sent-49, score-0.4]

24 The class of conformal embeddings includes all isometric embeddings as well as many other families of maps, including stereographic projections such as the Mercator projection. [sent-51, score-0.551]

25 # 4$3 ¥ ¥ # ¥ @ ( A 1 9#87 5 6# ¥ 1 0#B7 ( One approach to solving a manifold learning problem is to identify which aspects of the geometry of are invariant under the mapping . [sent-53, score-0.215]

26 For example, if is an isometric embedding then by deﬁnition inﬁnitesimal distances are preserved. [sent-54, score-0.366]

27 The length of a path in is deﬁned by integrating the inﬁnitesimal distance metric along the path. [sent-56, score-0.14]

28 If are two points in , then the shortest path between and lying inside is the same length as the shortest path ¥ ¥ EC FD# E ¥ # 1 )¥ ( 1 )¥ ( 1 )¥ ( between and along . [sent-58, score-0.223]

29 The conclusion is that is isometric with , regarded as metric spaces under geodesic distance. [sent-60, score-0.284]

30 Isomap exploits this idea by constructing the geodesic metric for approximately as a matrix, using the observed data alone. [sent-61, score-0.185]

31 1 )¥ ( 1 E )¥ ( 1 9#)¥ ( To solve the conformal embedding problem, we need to identify an observable geometric invariant of conformal maps. [sent-62, score-1.009]

32 Since conformal maps are locally isometric up to a scale factor , it is natural to try to estimate at each point in the observed data. [sent-63, score-0.586]

33 By rescaling, we can then restore the original metric structure of the data and proceed as in Isomap. [sent-64, score-0.088]

34 We can do this by noting that a conformal map rescales local volumes in by a factor . [sent-65, score-0.445]

35 Hence if the hidden data are sampled uniformly in , the local density of the observed data will be . [sent-66, score-0.194]

36 It follows that the conformal factor can be estimated in terms of the observed local data density, provided that the original sampling is uniform. [sent-67, score-0.48]

37 Determine a neighbourhood graph of the observed data in a suitable way. [sent-73, score-0.182]

38 Compute shortest paths in the graph for all pairs of data points. [sent-78, score-0.108]

39 Apply MDS to the resulting shortest-path distance matrix ding of the data in Euclidean space, approximating . [sent-81, score-0.076]

40 The premise is that local metric information (in this case, lengths of edges in the neighbourhood graph) is regarded as a trustworthy guide to the local metric structure in the original (latent) space. [sent-82, score-0.398]

41 The shortest-paths computation then gives an estimate of the global metric structure, which can be fed into MDS to produce the required embedding. [sent-83, score-0.133]

42 ¥ ¦ It is known that Step 2 converges on the true geodesic structure of the manifold given sufﬁcient data, and thus Isomap yields a faithful low-dimensional Euclidean embedding whenever the function is an isometry. [sent-84, score-0.487]

43 Let be a -smooth isometric embedding of that region in . [sent-87, score-0.335]

44 Given , for a suitable choice of neighbourhood size parameter or , we have ¢ £ ¢ § ! [sent-88, score-0.108]

45 ¥ & '¡ $ recovered distance original distance $ %! [sent-89, score-0.096]

46 formula is taken to hold for all pairs of points simultaneously. [sent-92, score-0.108]

47 Compute shortest paths in the graph for all pairs of data points. [sent-95, score-0.108]

48 The point is that the rescaling factor is an asymptotically accurate approximation to the conformal scaling factor in the neighbourhood of and . [sent-100, score-0.56]

49 Let be sampled uniformly from a bounded convex region in . [sent-102, score-0.104]

50 Let be a -smooth conformal embedding of that region in . [sent-103, score-0.594]

51 Given , for a suitable choice of neighbourhood size parameter , we have recovered distance original distance with probability at least , provided that the sample size is sufﬁciently large. [sent-104, score-0.204]

52 Qualitatively, we expect to require a larger sample size for C-Isomap since it depends on two approximations—local data density and geodesic distance—rather than one. [sent-109, score-0.112]

53 In the special case where the conformal embedding is actually an isometry, it is therefore preferable to use Isomap rather than C-Isomap. [sent-110, score-0.569]

54 For the conformal ﬁshbowl (column 1), 2000 points were generated randomly and then projected stereographically (hence conformally uniformly in a circular disk mapped) onto a sphere. [sent-116, score-0.574]

55 There is no metrically faithful way of embedding a curved ﬁshbowl inside a Euclidean plane, so classical MDS and Isomap cannot succeed. [sent-118, score-0.322]

56 As predicted, C-Isomap does recover the original disk structure of (as does LLE). [sent-119, score-0.086]

57 Contrast with the uniform ﬁshbowl (column 2), with data points sampled using a uniform measure on the ﬁshbowl itself. [sent-120, score-0.155]

58 In this situation C-Isomap behaves like Isomap, since the rescaling factor is approximately constant; hence it is unable to ﬁnd a topologically faithful 2-dimensional representation. [sent-121, score-0.149]

59 The offset ﬁshbowl (column 3) is a perturbed version of the conformal ﬁshbowl; points are sampled in using a shallow Gaussian offset from center, then stereographically projected onto a sphere. [sent-122, score-0.573]

60 LLE, in contrast, produces topological errors and metric distortion in both cases where the data are not uniformly sampled in (columns 2 and 3). [sent-124, score-0.201]

61 © § ¡ © § ¨¡ Face images: Artiﬁcial images of a face were rendered as pixel images and rasterized into 16384-dimensional vectors. [sent-125, score-0.205]

62 The images varied randomly and independently in two parameters: left-right pose angle and distance from camera . [sent-126, score-0.158]

63 There is a natural family of conformal transformations for this data manifold, if we ignore perspective distor, for , which has the effect of shrinking tions in the closest images: namely or magnifying the apparent size of images by a constant factor. [sent-127, score-0.42]

64 We generated 2000 face images in this way, spanning the range indicated by Figure 2. [sent-129, score-0.126]

65 All four algorithms returned a two-dimensional embedding of the data. [sent-130, score-0.204]

66 Isomap returns an embedding which narrows predictably as the face gets further away. [sent-132, score-0.275]

67 Figure 2: A set of 2000 face images were randomly generated, varying independently in two parameters: distance and left-right pose. [sent-138, score-0.199]

68 3 Isomap with landmark points The Isomap algorithm has two computational bottlenecks. [sent-140, score-0.313]

69 Using Floyd’s algorithm this is ; this can be improved to by implementing Dijkstra’s algorithm with Fibonacci heaps ( is the neighbourhood size). [sent-142, score-0.108]

70 We designate of the data points to be landmark points, where . [sent-147, score-0.313]

71 Instead of computing , we compute the matrix of distances from each data point to the landmark points only. [sent-148, score-0.397]

72 Using a new procedure LMDS (Landmark MDS), we ﬁnd a Euclidean embedding of the data using instead of . [sent-149, score-0.204]

73 The ﬁrst step is to apply classical MDS to the landmark points only, embedding them faithfully in . [sent-153, score-0.551]

74 Each remaining point can now be located in by using its known distances from the landmark points as constraints. [sent-154, score-0.369]

75 If and the landmarks are in general position, then there are enough constraints to locate uniquely. [sent-156, score-0.229]

76 The landmark points may be chosen randomly, with taken to be sufﬁciently larger than the minimum to ensure stability. [sent-157, score-0.313]

77 1 The Landmark MDS algorithm LMDS begins by applying classical MDS [9,10] to the landmarks-only distance matrix . [sent-161, score-0.11]

78 The ﬁrst step is to construct an “inner-product” matrix ; here is the matrix of squared distances and is the “centering” matrix . [sent-163, score-0.14]

79 Write for the positive eigenvalues (labelled so that ), and for the corresponding eigenvectors (written as column vectors); non-positive eigenvalues are ignored. [sent-165, score-0.086]

80 Then for the required optimal -dimensional embedding vectors are given as the columns of the matrix: & )( D $A A ! [sent-166, score-0.204]

81 If has no negative eigenvalues, then the dimensional embedding is perfect; otherwise there is no exact Euclidean embedding. [sent-179, score-0.204]

82 Let denote the column vector of squared distances between a data point and the landmark points. [sent-181, score-0.324]

83 The embedding vector is related linearly to by the formula: ! [sent-182, score-0.204]

84 If is a landmark point, then the embedding given by LMDS is consistent with the original MDS embedding. [sent-196, score-0.444]

85 If the distance matrix can be represented exactly by a Euclidean conﬁg, and if the landmarks are chosen so that their afﬁne span in that uration in conﬁguration is -dimensional (i. [sent-198, score-0.305]

86 "¢ A good way to satisfy the afﬁne span condition is to pick landmarks randomly, plus a few extra for stability. [sent-202, score-0.229]

87 If is very small, then all the landmarks lie close to a hyperplane and LMDS performs poorly with noisy data. [sent-205, score-0.251]

88 In practice, choosing a few extra landmark points gives satisfactory results. [sent-206, score-0.313]

89 2000 points were generated uniformly in a rectangle (top left) and mapped into a Swiss roll conﬁguration in . [sent-213, score-0.203]

90 Ordinary Isomap recovers the rectangular structure correctly provided that the neighbourhood parameter is not too large (in this case works). [sent-214, score-0.134]

91 For each , we chose landmark points at random; even down to 4 landmarks the embedding closely approximates the (non-landmark) Isomap embedding. [sent-216, score-0.746]

92 The conﬁguration of three landmarks was chosen especially to illustrate the afﬁne distortion that may arise if the landmarks lie close to a subspace (in this case, a line). [sent-217, score-0.504]

93 For three landmarks chosen at random, results are generally much better. [sent-218, score-0.229]

94 § § § 4 Conclusion Local approaches to nonlinear dimensionality reduction such as LLE or Laplacian Eigenmaps have two principal advantages over a global approach such as Isomap: they tolerate a certain amount of curvature and they lead naturally to a sparse eigenvalue problem. [sent-222, score-0.35]

95 However, neither curvature tolerance nor computational sparsity are explicitly part of the formulation of the local approaches; these features emerge as byproducts of the goal of trying to preserve only the data’s local geometric structure. [sent-223, score-0.319]

96 The conformal invariance of LLE can fail in sometimes surprising ways, and the computational sparsity is not tunable independently of the topological sparsity of the manifold. [sent-225, score-0.501]

97 In contrast, we have presented two extensions to Isomap that are explicitly designed to remove a well-characterized form of curvature and to exploit the computational sparsity intrinsic to low-dimensional manifolds. [sent-226, score-0.086]

98 The authors wish to thank Thomas Vetter for providing the range and texture maps for the synthetic face; and Lauren Schmidt for her help in rendering the actual images using Curious Labs’ “Poser” software. [sent-229, score-0.082]

99 C (2000) A global geometric framework for nonlinear dimensionality reduction. [sent-234, score-0.211]

100 (2002) Laplacian eigenmaps and spectral techniques for embedding and clustering. [sent-242, score-0.326]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('isomap', 0.511), ('conformal', 0.365), ('lle', 0.257), ('landmark', 0.24), ('mds', 0.232), ('landmarks', 0.229), ('embedding', 0.204), ('lmds', 0.203), ('shbowl', 0.141), ('eigenmaps', 0.122), ('manifold', 0.115), ('neighbourhood', 0.108), ('isometric', 0.106), ('geodesic', 0.088), ('laplacian', 0.081), ('euclidean', 0.075), ('points', 0.073), ('geometry', 0.073), ('global', 0.071), ('face', 0.071), ('roll', 0.064), ('metric', 0.062), ('silva', 0.062), ('distances', 0.056), ('local', 0.056), ('images', 0.055), ('faithful', 0.054), ('swiss', 0.054), ('fishbowl', 0.053), ('submanifold', 0.053), ('advantages', 0.052), ('sparsity', 0.05), ('distance', 0.048), ('dimensionality', 0.048), ('geometric', 0.048), ('nitesimal', 0.045), ('shortest', 0.045), ('guration', 0.045), ('nonlinear', 0.044), ('uniformly', 0.043), ('tenenbaum', 0.042), ('reduction', 0.041), ('byproducts', 0.041), ('faraway', 0.041), ('pqqq', 0.041), ('stereographically', 0.041), ('embeddings', 0.04), ('graph', 0.039), ('rescaling', 0.039), ('sampled', 0.036), ('curvature', 0.036), ('topological', 0.036), ('embedded', 0.036), ('nldr', 0.035), ('dijkstra', 0.035), ('observed', 0.035), ('nearby', 0.035), ('formula', 0.035), ('preserves', 0.035), ('principal', 0.034), ('classical', 0.034), ('recover', 0.033), ('xe', 0.032), ('topologically', 0.032), ('pca', 0.032), ('sparseness', 0.032), ('preserve', 0.032), ('invert', 0.03), ('curved', 0.03), ('gtm', 0.03), ('pose', 0.03), ('path', 0.03), ('eigenvalues', 0.029), ('offset', 0.029), ('locally', 0.029), ('regarded', 0.028), ('af', 0.028), ('langford', 0.028), ('matrix', 0.028), ('column', 0.028), ('maps', 0.027), ('self', 0.027), ('disk', 0.027), ('multidimensional', 0.027), ('identify', 0.027), ('cox', 0.026), ('structure', 0.026), ('randomly', 0.025), ('region', 0.025), ('factor', 0.024), ('eigenvalue', 0.024), ('pixel', 0.024), ('distortion', 0.024), ('paths', 0.024), ('ss', 0.024), ('density', 0.024), ('uniform', 0.023), ('ciency', 0.023), ('mapped', 0.023), ('lie', 0.022)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0 97 nips-2002-Global Versus Local Methods in Nonlinear Dimensionality Reduction

Author: Vin D. Silva, Joshua B. Tenenbaum

2 0.22126231 36 nips-2002-Automatic Alignment of Local Representations

Author: Yee W. Teh, Sam T. Roweis

Abstract: We present an automatic alignment procedure which maps the disparate internal representations learned by several local dimensionality reduction experts into a single, coherent global coordinate system for the original data space. Our algorithm can be applied to any set of experts, each of which produces a low-dimensional local representation of a highdimensional input. Unlike recent efforts to coordinate such models by modifying their objective functions [1, 2], our algorithm is invoked after training and applies an efﬁcient eigensolver to post-process the trained models. The post-processing has no local optima and the size of the system it must solve scales with the number of local models rather than the number of original data points, making it more efﬁcient than model-free algorithms such as Isomap [3] or LLE [4]. 1 Introduction: Local vs. Global Dimensionality Reduction Beyond density modelling, an important goal of unsupervised learning is to discover compact, informative representations of high-dimensional data. If the data lie on a smooth low dimensional manifold, then an excellent encoding is the coordinates internal to that manifold. The process of determining such coordinates is dimensionality reduction. Linear dimensionality reduction methods such as principal component analysis and factor analysis are easy to train but cannot capture the structure of curved manifolds. Mixtures of these simple unsupervised models [5, 6, 7, 8] have been used to perform local dimensionality reduction, and can provide good density models for curved manifolds, but unfortunately such mixtures cannot do dimensionality reduction. They do not describe a single, coherent low-dimensional coordinate system for the data since there is no pressure for the local coordinates of each component to agree. Roweis et al [1] recently proposed a model which performs global coordination of local coordinate systems in a mixture of factor analyzers (MFA). Their model is trained by maximizing the likelihood of the data, with an additional variational penalty term to encourage the internal coordinates of the factor analyzers to agree. While their model can trade off modelling the data and having consistent local coordinate systems, it requires a user given trade-off parameter, training is quite inefﬁcient (although [2] describes an improved training algorithm for a more constrained model), and it has quite serious local minima problems (methods like LLE [4] or Isomap [3] have to be used for initialization). In this paper we describe a novel, automatic way to align the hidden representations used by each component of a mixture of dimensionality reducers into a single global representation of the data throughout space. Given an already trained mixture, the alignment is achieved by applying an eigensolver to a matrix constructed from the internal representations of the mixture components. Our method is efﬁcient, simple to implement, and has no local optima in its optimization nor any learning rates or annealing schedules. 2 The Locally Linear Coordination Algorithm H 9¥ EI¡ CD66B9 ©9B 766 % G F 5 #

3 0.21475179 49 nips-2002-Charting a Manifold

Author: Matthew Brand

Abstract: We construct a nonlinear mapping from a high-dimensional sample space to a low-dimensional vector space, effectively recovering a Cartesian coordinate system for the manifold from which the data is sampled. The mapping preserves local geometric relations in the manifold and is pseudo-invertible. We show how to estimate the intrinsic dimensionality of the manifold from samples, decompose the sample data into locally linear low-dimensional patches, merge these patches into a single lowdimensional coordinate system, and compute forward and reverse mappings between the sample and coordinate spaces. The objective functions are convex and their solutions are given in closed form. 1 Nonlinear dimensionality reduction (NLDR) by charting Charting is the problem of assigning a low-dimensional coordinate system to data points in a high-dimensional sample space. It is presumed that the data lies on or near a lowdimensional manifold embedded in the sample space, and that there exists a 1-to-1 smooth nonlinear transform between the manifold and a low-dimensional vector space. The datamodeler’s goal is to estimate smooth continuous mappings between the sample and coordinate spaces. Often this analysis will shed light on the intrinsic variables of the datagenerating phenomenon, for example, revealing perceptual or conﬁguration spaces. Our goal is to ﬁnd a mapping—expressed as a kernel-based mixture of linear projections— that minimizes information loss about the density and relative locations of sample points. This constraint is expressed in a posterior that combines a standard gaussian mixture model (GMM) likelihood function with a prior that penalizes uncertainty due to inconsistent projections in the mixture. Section 3 develops a special case where this posterior is unimodal and maximizable in closed form, yielding a GMM whose covariances reveal a patchwork of overlapping locally linear subspaces that cover the manifold. Section 4 shows that for this (or any) GMM and a choice of reduced dimension d, there is a unique, closed-form solution for a minimally distorting merger of the subspaces into a d-dimensional coordinate space, as well as an reverse mapping deﬁning the surface of the manifold in the sample space. The intrinsic dimensionality d of the data manifold can be estimated from the growth process of point-to-point distances. In analogy to differential geometry, we call the subspaces “charts” and their merger the “connection.” Section 5 considers example problems where these methods are used to untie knots, unroll and untwist sheets, and visualize video data. 1.1 Background Topology-neutral NLDR algorithms can be divided into those that compute mappings, and those that directly compute low-dimensional embeddings. The ﬁ has its roots in mapeld ping algorithms: DeMers and Cottrell [3] proposed using auto-encoding neural networks with a hidden layer “ bottleneck,” effectively casting dimensionality reduction as a compression problem. Hastie deﬁ principal curves [5] as nonparametric 1 D curves that pass ned through the center of “ nearby” data points. A rich literature has grown up around properly regularizing this approach and extending it to surfaces. Smola and colleagues [10] analyzed the NLDR problem in the broader framework of regularized quantization methods. More recent advances aim for embeddings: Gomes and Mojsilovic [4] treat manifold completion as an anisotropic diffusion problem, iteratively expanding points until they connect to their neighbors. The I SO M AP algorithm [12] represents remote distances as sums of a trusted set of distances between immediate neighbors, then uses multidimensional scaling to compute a low-dimensional embedding that minimally distorts all distances. The locally linear embedding algorithm (LLE) [9] represents each point as a weighted combination of a trusted set of nearest neighbors, then computes a minimally distorting low-dimensional barycentric embedding. They have complementary strengths: I SO M AP handles holes well but can fail if the data hull is nonconvex [12]; and vice versa for LLE [9]. Both offer embeddings without mappings. It has been noted that trusted-set methods are vulnerable to noise because they consider the subset of point-to-point relationships that has the lowest signal-to-noise ratio; small changes to the trusted set can induce large changes in the set of constraints on the embedding, making solutions unstable [1]. In a return to mapping, Roweis and colleagues [8] proposed global coordination— learning a mixture of locally linear projections from sample to coordinate space. They constructed a posterior that penalizes distortions in the mapping, and gave a expectation-maximization (EM) training rule. Innovative use of variational methods highlighted the difﬁ culty of even hill-climbing their multimodal posterior. Like [2, 7, 6, 8], the method we develop below is a decomposition of the manifold into locally linear neighborhoods. It bears closest relation to global coordination [8], although by a different construction of the problem, we avoid hill-climbing a spiky posterior and instead develop a closed-form solution. 2 Estimating locally linear scale and intrinsic dimensionality . We begin with matrix of sample points Y = [y1 , · · · , yN ], yn ∈ RD populating a Ddimensional sample space, and a conjecture that these points are samples from a manifold M of intrinsic dimensionality d < D. We seek a mapping onto a vector space . G(Y) → X = [x1 , · · · , xN ], xn ∈ Rd and 1-to-1 reverse mapping G−1 (X) → Y such that local relations between nearby points are preserved (this will be formalized below). The map G should be non-catastrophic, that is, without folds: Parallel lines on the manifold in RD should map to continuous smooth non-intersecting curves in Rd . This guarantees that linear operations on X such as interpolation will have reasonable analogues on Y. Smoothness means that at some scale r the mapping from a neighborhood on M to Rd is effectively linear. Consider a ball of radius r centered on a data point and containing n(r) data points. The count n(r) grows as rd , but only at the locally linear scale; the grow rate is inﬂated by isotropic noise at smaller scales and by embedding curvature at larger scales. . To estimate r, we look at how the r-ball grows as points are added to it, tracking c(r) = d d log n(r) log r. At noise scales, c(r) ≈ 1/D < 1/d, because noise has distributed points in all directions with equal probability. At the scale at which curvature becomes signiﬁ cant, c(r) < 1/d, because the manifold is no longer perpendicular to the surface of the ball, so the ball does not have to grow as fast to accommodate new points. At the locally linear scale, the process peaks at c(r) = 1/d, because points are distributed only in the directions of the manifold’s local tangent space. The maximum of c(r) therefore gives an estimate of both the scale and the local dimensionality of the manifold (see ﬁ gure 1), provided that the ball hasn’t expanded to a manifold boundary— boundaries have lower dimension than Scale behavior of a 1D manifold in 2-space Point−count growth process on a 2D manifold in 3−space 1 10 radial growth process 1D hypothesis 2D hypothesis 3D hypothesis radius (log scale) samples noise scale locally linear scale curvature scale 0 10 2 1 10 2 10 #points (log scale) 3 10 Figure 1: Point growth processes. L EFT: At the locally linear scale, the number of points in an r-ball grows as rd ; at noise and curvature scales it grows faster. R IGHT: Using the point-count growth process to ﬁ the intrinsic dimensionality of a 2D manifold nonlinearly nd embedded in 3-space (see ﬁ gure 2). Lines of slope 1/3 , 1/2 , and 1 are ﬁ tted to sections of the log r/ log nr curve. For neighborhoods of radius r ≈ 1 with roughly n ≈ 10 points, the slope peaks at 1/2 indicating a dimensionality of d = 2. Below that, the data appears 3 D because it is dominated by noise (except for n ≤ D points); above, the data appears >2 D because of manifold curvature. As the r-ball expands to cover the entire data-set the dimensionality appears to drop to 1 as the process begins to track the 1D edges of the 2D sheet. the manifold. For low-dimensional manifolds such as sheets, the boundary submanifolds (edges and corners) are very small relative to the full manifold, so the boundary effect is typically limited to a small rise in c(r) as r approaches the scale of the entire data set. In practice, our code simply expands an r-ball at every point and looks for the ﬁ peak in rst c(r), averaged over many nearby r-balls. One can estimate d and r globally or per-point. 3 Charting the data In the charting step we ﬁ a soft partitioning of the data into locally linear low-dimensional nd neighborhoods, as a prelude to computing the connection that gives the global lowdimensional embedding. To minimize information loss in the connection, we require that the data points project into a subspace associated with each neighborhood with (1) minimal loss of local variance and (2) maximal agreement of the projections of nearby points into nearby neighborhoods. Criterion (1) is served by maximizing the likelihood function of a Gaussian mixture model (GMM) density ﬁ tted to the data: . p(yi |µ, Σ) = ∑ j p(yi |µ j , Σ j ) p j = ∑ j N (yi ; µ j , Σ j ) p j . (1) Each gaussian component deﬁ a local neighborhood centered around µ j with axes denes ﬁ ned by the eigenvectors of Σ j . The amount of data variance along each axis is indicated by the eigenvalues of Σ j ; if the data manifold is locally linear in the vicinity of the µ j , all but the d dominant eigenvalues will be near-zero, implying that the associated eigenvectors constitute the optimal variance-preserving local coordinate system. To some degree likelihood maximization will naturally realize this property: It requires that the GMM components shrink in volume to ﬁ the data as tightly as possible, which is best achieved by t positioning the components so that they “ pancake” onto locally ﬂat collections of datapoints. However, this state of affairs is easily violated by degenerate (zero-variance) GMM components or components ﬁ tted to overly small enough locales where the data density off the manifold is comparable to density on the manifold (e.g., at the noise scale). Consequently a prior is needed. Criterion (2) implies that neighboring partitions should have dominant axes that span similar subspaces, since disagreement (large subspace angles) would lead to inconsistent projections of a point and therefore uncertainty about its location in a low-dimensional coordinate space. The principal insight is that criterion (2) is exactly the cost of coding the location of a point in one neighborhood when it is generated by another neighborhood— the cross-entropy between the gaussian models deﬁ ning the two neighborhoods: D(N1 N2 ) = = dy N (y; µ1 ,Σ1 ) log N (y; µ1 ,Σ1 ) N (y; µ2 ,Σ2 ) (log |Σ−1 Σ2 | + trace(Σ−1 Σ1 ) + (µ2 −µ1 ) Σ−1 (µ2 −µ1 ) − D)/2. (2) 1 2 2 Roughly speaking, the terms in (2) measure differences in size, orientation, and position, respectively, of two coordinate frames located at the means µ1 , µ2 with axes speciﬁ by ed the eigenvectors of Σ1 , Σ2 . All three terms decline to zero as the overlap between the two frames is maximized. To maximize consistency between adjacent neighborhoods, we form . the prior p(µ, Σ) = exp[− ∑i= j mi (µ j )D(Ni N j )], where mi (µ j ) is a measure of co-locality. Unlike global coordination [8], we are not asking that the dominant axes in neighboring charts are aligned— only that they span nearly the same subspace. This is a much easier objective to satisfy, and it contains a useful special case where the posterior p(µ, Σ|Y) ∝ ∑i p(yi |µ, Σ)p(µ, Σ) is unimodal and can be maximized in closed form: Let us associate a gaussian neighborhood with each data-point, setting µi = yi ; take all neighborhoods to be a priori equally probable, setting pi = 1/N; and let the co-locality measure be determined from some local kernel. For example, in this paper we use mi (µ j ) ∝ N (µ j ; µi , σ2 ), with the scale parameter σ specifying the expected size of a neighborhood on the manifold in sample space. A reasonable choice is σ = r/2, so that 2erf(2) > 99.5% of the density of mi (µ j ) is contained in the area around yi where the manifold is expected to be locally linear. With uniform pi and µi , mi (µ j ) and ﬁ xed, the MAP estimates of the GMM covariances are Σi = ∑ mi (µ j ) (y j − µi )(y j − µi ) + (µ j − µi )(µ j − µi ) + Σ j j ∑ mi (µ j ) (3) . j Note that each covariance Σi is dependent on all other Σ j . The MAP estimators for all covariances can be arranged into a set of fully constrained linear equations and solved exactly for their mutually optimal values. This key step brings nonlocal information about the manifold’s shape into the local description of each neighborhood, ensuring that adjoining neighborhoods have similar covariances and small angles between their respective subspaces. Even if a local subset of data points are dense in a direction perpendicular to the manifold, the prior encourages the local chart to orient parallel to the manifold as part of a globally optimal solution, protecting against a pathology noted in [8]. Equation (3) is easily adapted to give a reduced number of charts and/or charts centered on local centroids. 4 Connecting the charts We now build a connection for set of charts speciﬁ as an arbitrary nondegenerate GMM. A ed GMM gives a soft partitioning of the dataset into neighborhoods of mean µk and covariance Σk . The optimal variance-preserving low-dimensional coordinate system for each neighborhood derives from its weighted principal component analysis, which is exactly speciﬁ ed by the eigenvectors of its covariance matrix: Eigendecompose Vk Λk Vk ← Σk with eigen. values in descending order on the diagonal of Λk and let Wk = [Id , 0]Vk be the operator . th projecting points into the k local chart, such that local chart coordinate uki = Wk (yi − µk ) . and Uk = [uk1 , · · · , ukN ] holds the local coordinates of all points. Our goal is to sew together all charts into a globally consistent low-dimensional coordinate system. For each chart there will be a low-dimensional afﬁ transform Gk ∈ R(d+1)×d ne that projects Uk into the global coordinate space. Summing over all charts, the weighted average of the projections of point yi into the low-dimensional vector space is W j (y − µ j ) 1 . x|y = ∑ G j j p j|y (y) . xi |yi = ∑ G j ⇒ u ji 1 j p j|y (yi ), (4) where pk|y (y) ∝ pk N (y; µk , Σk ), ∑k pk|y (y) = 1 is the probability that chart k generates point y. As pointed out in [8], if a point has nonzero probabilities in two charts, then there should be afﬁ transforms of those two charts that map the point to the same place in a ne global coordinate space. We set this up as a weighted least-squares problem: . G = [G1 , · · · , GK ] = arg min uki 1 ∑ pk|y (yi )p j|y (yi ) Gk Gk ,G j i −Gj u ji 1 2 . (5) F Equation (5) generates a homogeneous set of equations that determines a solution up to an afﬁ transform of G. There are two solution methods. First, let us temporarily anchor one ne neighborhood at the origin to ﬁ this indeterminacy. This adds the constraint G1 = [I, 0] . x . To solve, deﬁ indicator matrix Fk = [0, · · · , 0, I, 0, · · · , 0] with the identity mane . trix occupying the kth block, such that Gk = GFk . Let the diagonal of Pk = diag([pk|y (y1 ), · · · , pk|y (yN )]) record the per-point posteriors of chart k. The squared error of the connection is then a sum of of all patch-to-anchor and patch-to-patch inconsistencies: . E =∑ (GUk − k U1 0 2 )Pk P1 F + ∑ (GU j − GUk )P j Pk j=k 2 F ; . Uk = Fk Uk 1 . (6) Setting dE /dG = 0 and solving to minimize convex E gives −1 G = ∑ Uk P2 k k ∑ j=k P2 j Uk − ∑ ∑ Uk P2 P2 k 1 Uk P2 P2 U j k j k j=k U1 0 . (7) We now remove the dependence on a reference neighborhood G1 by rewriting equation 5, G = arg min ∑ j=k (GU j − GUk )P j Pk G 2 F = GQ 2 F = trace(GQQ G ) , (8) . where Q = ∑ j=k U j − Uk P j Pk . If we require that GG = I to prevent degenerate solutions, then equation (8) is solved (up to rotation in coordinate space) by setting G to the eigenvectors associated with the smallest eigenvalues of QQ . The eigenvectors can be computed efﬁ ciently without explicitly forming QQ ; other numerical efﬁ ciencies obtain by zeroing any vanishingly small probabilities in each Pk , yielding a sparse eigenproblem. A more interesting strategy is to numerically condition the problem by calculating the trailing eigenvectors of QQ + 1. It can be shown that this maximizes the posterior 2 p(G|Q) ∝ p(Q|G)p(G) ∝ e− GQ F e− G1 , where the prior p(G) favors a mapping G whose unit-norm rows are also zero-mean. This maximizes variance in each row of G and thereby spreads the projected points broadly and evenly over coordinate space. The solutions for MAP charts (equation (5)) and connection (equation (8)) can be applied to any well-ﬁ tted mixture of gaussians/factors1 /PCAs density model; thus large eigenproblems can be avoided by connecting just a small number of charts that cover the data. 1 We thank reviewers for calling our attention to Teh & Roweis ([11]— in this volume), which shows how to connect a set of given local dimensionality reducers in a generalized eigenvalue problem that is related to equation (8). LLE, n=5 charting (projection onto coordinate space) charting best Isomap LLE, n=6 LLE, n=7 LLE, n=8 random subset of local charts XYZ view LLE, n=9 LLE, n=10 XZ view data (linked) embedding, XY view XY view original data reconstruction (back−projected coordinate grid) best LLE (regularized) Figure 2: The twisted curl problem. L EFT: Comparison of charting, I SO M AP, & LLE. 400 points are randomly sampled from the manifold with noise. Charting is the only method that recovers the original space without catastrophes (folding), albeit with some shear. R IGHT: The manifold is regularly sampled (with noise) to illustrate the forward and backward projections. Samples are shown linked into lines to help visualize the manifold structure. Coordinate axes of a random selection of charts are shown as bold lines. Connecting subsets of charts such as this will also give good mappings. The upper right quadrant shows various LLE results. At bottom we show the charting solution and the reconstructed (back-projected) manifold, which smooths out the noise. Once the connection is solved, equation (4) gives the forward projection of any point y down into coordinate space. There are several numerically distinct candidates for the backprojection: posterior mean, mode, or exact inverse. In general, there may not be a unique posterior mode and the exact inverse is not solvable in closed form (this is also true of [8]). Note that chart-wise projection deﬁ a complementary density in coordinate space nes px|k (x) = N (x; Gk 0 1 , Gk [Id , 0]Λk [Id , 0] 0 0 0 Gk ). (9) Let p(y|x, k), used to map x into subspace k on the surface of the manifold, be a Dirac delta function whose mean is a linear function of x. Then the posterior mean back-projection is obtained by integrating out uncertainty over which chart generates x: y|x = ∑ pk|x (x) k µk + Wk Gk I 0 + x − Gk 0 1 , (10) where (·)+ denotes pseudo-inverse. In general, a back-projecting map should not reconstruct the original points. Instead, equation (10) generates a surface that passes through the weighted average of the µi of all the neighborhoods in which yi has nonzero probability, much like a principal curve passes through the center of each local group of points. 5 Experiments Synthetic examples: 400 2 D points were randomly sampled from a 2 D square and embedded in 3 D via a curl and twist, then contaminated with gaussian noise. Even if noiselessly sampled, this manifold cannot be “ unrolled” without distortion. In addition, the outer curl is sampled much less densely than the inner curl. With an order of magnitude fewer points, higher noise levels, no possibility of an isometric mapping, and uneven sampling, this is arguably a much more challenging problem than the “ swiss roll” and “ s-curve” problems featured in [12, 9, 8, 1]. Figure 2LEFT contrasts the (unique) output of charting and the best outputs obtained from I SO M AP and LLE (considering all neighborhood sizes between 2 and 20 points). I SO M AP and LLE show catastrophic folding; we had to change LLE’s b. data, yz view c. local charts d. 2D embedding e. 1D embedding 1D ordinate a. data, xy view true manifold arc length Figure 3: Untying a trefoil knot ( ) by charting. 900 noisy samples from a 3 D-embedded 1 D manifold are shown as connected dots in front (a) and side (b) views. A subset of charts is shown in (c). Solving for the 2 D connection gives the “ unknot” in (d). After removing some points to cut the knot, charting gives a 1 D embedding which we plot against true manifold arc length in (e); monotonicity (modulo noise) indicates correctness. Three principal degrees of freedom recovered from raw jittered images pose scale expression images synthesized via backprojection of straight lines in coordinate space Figure 4: Modeling the manifold of facial images from raw video. Each row contains images synthesized by back-projecting an axis-parallel straight line in coordinate space onto the manifold in image space. Blurry images correspond to points on the manifold whose neighborhoods contain few if any nearby data points. regularization in order to coax out nondegenerate (>1 D) solutions. Although charting is not designed for isometry, after afﬁ transform the forward-projected points disagree with ne the original points with an RMS error of only 1.0429, lower than the best LLE (3.1423) or best I SO M AP (1.1424, not shown). Figure 2RIGHT shows the same problem where points are sampled regularly from a grid, with noise added before and after embedding. Figure 3 shows a similar treatment of a 1 D line that was threaded into a 3 D trefoil knot, contaminated with gaussian noise, and then “ untied” via charting. Video: We obtained a 1965-frame video sequence (courtesy S. Roweis and B. Frey) of 20 × 28-pixel images in which B.F. strikes a variety of poses and expressions. The video is heavily contaminated with synthetic camera jitters. We used raw images, though image processing could have removed this and other uninteresting sources of variation. We took a 500-frame subsequence and left-right mirrored it to obtain 1000 points in 20 × 28 = 560D image space. The point-growth process peaked just above d = 3 dimensions. We solved for 25 charts, each centered on a random point, and a 3D connection. The recovered degrees of freedom— recognizable as pose, scale, and expression— are visualized in ﬁ gure 4. original data stereographic map to 3D fishbowl charting Figure 5: Flattening a ﬁ shbowl. From the left: Original 2000×2D points; their stereographic mapping to a 3D ﬁ shbowl; its 2D embedding recovered using 500 charts; and the stereographic map. Fewer charts lead to isometric mappings that fold the bowl (not shown). Conformality: Some manifolds can be ﬂattened conformally (preserving local angles) but not isometrically. Figure 5 shows that if the data is ﬁ nely charted, the connection behaves more conformally than isometrically. This problem was suggested by J. Tenenbaum. 6 Discussion Charting breaks kernel-based NLDR into two subproblems: (1) Finding a set of datacovering locally linear neighborhoods (“ charts” ) such that adjoining neighborhoods span maximally similar subspaces, and (2) computing a minimal-distortion merger (“ connection” ) of all charts. The solution to (1) is optimal w.r.t. the estimated scale of local linearity r; the solution to (2) is optimal w.r.t. the solution to (1) and the desired dimensionality d. Both problems have Bayesian settings. By ofﬂoading the nonlinearity onto the kernels, we obtain least-squares problems and closed form solutions. This scheme is also attractive because large eigenproblems can be avoided by using a reduced set of charts. The dependence on r, like trusted-set methods, is a potential source of solution instability. In practice the point-growth estimate seems fairly robust to data perturbations (to be expected if the data density changes slowly over a manifold of integral Hausdorff dimension), while the use of a soft neighborhood partitioning appears to make charting solutions reasonably stable to variations in r. Eigenvalue stability analyses may prove useful here. Ultimately, we would prefer to integrate r out. In contrast, use of d appears to be a virtue: Unlike other eigenvector-based methods, the best d-dimensional embedding is not merely a linear projection of the best d + 1-dimensional embedding; a unique distortion is found for each value of d that maximizes the information content of its embedding. Why does charting performs well on datasets where the signal-to-noise ratio confounds recent state-of-the-art methods? Two reasons may be adduced: (1) Nonlocal information is used to construct both the system of local charts and their global connection. (2) The mapping only preserves the component of local point-to-point distances that project onto the manifold; relationships perpendicular to the manifold are discarded. Thus charting uses global shape information to suppress noise in the constraints that determine the mapping. Acknowledgments Thanks to J. Buhmann, S. Makar, S. Roweis, J. Tenenbaum, and anonymous reviewers for insightful comments and suggested “ challenge” problems. References [1] M. Balasubramanian and E. L. Schwartz. The IsoMap algorithm and topological stability. Science, 295(5552):7, January 2002. [2] C. Bregler and S. Omohundro. Nonlinear image interpolation using manifold learning. In NIPS–7, 1995. [3] D. DeMers and G. Cottrell. Nonlinear dimensionality reduction. In NIPS–5, 1993. [4] J. Gomes and A. Mojsilovic. A variational approach to recovering a manifold from sample points. In ECCV, 2002. [5] T. Hastie and W. Stuetzle. Principal curves. J. Am. Statistical Assoc, 84(406):502–516, 1989. [6] G. Hinton, P. Dayan, and M. Revow. Modeling the manifolds of handwritten digits. IEEE Trans. Neural Networks, 8, 1997. [7] N. Kambhatla and T. Leen. Dimensionality reduction by local principal component analysis. Neural Computation, 9, 1997. [8] S. Roweis, L. Saul, and G. Hinton. Global coordination of linear models. In NIPS–13, 2002. [9] S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290:2323–2326, December 22 2000. [10] A. Smola, S. Mika, B. Schölkopf, and R. Williamson. Regularized principal manifolds. Machine Learning, 1999. [11] Y. W. Teh and S. T. Roweis. Automatic alignment of hidden representations. In NIPS–15, 2003. [12] J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290:2319–2323, December 22 2000.

4 0.12440532 34 nips-2002-Artefactual Structure from Least-Squares Multidimensional Scaling

Author: Nicholas P. Hughes, David Lowe

Abstract: We consider the problem of illusory or artefactual structure from the visualisation of high-dimensional structureless data. In particular we examine the role of the distance metric in the use of topographic mappings based on the statistical ﬁeld of multidimensional scaling. We show that the use of a squared Euclidean metric (i.e. the SS TRESS measure) gives rise to an annular structure when the input data is drawn from a highdimensional isotropic distribution, and we provide a theoretical justiﬁcation for this observation.

5 0.12366261 98 nips-2002-Going Metric: Denoising Pairwise Data

Author: Volker Roth, Julian Laub, Klaus-Robert Müller, Joachim M. Buhmann

Abstract: Pairwise data in empirical sciences typically violate metricity, either due to noise or due to fallible estimates, and therefore are hard to analyze by conventional machine learning technology. In this paper we therefore study ways to work around this problem. First, we present an alternative embedding to multi-dimensional scaling (MDS) that allows us to apply a variety of classical machine learning and signal processing algorithms. The class of pairwise grouping algorithms which share the shift-invariance property is statistically invariant under this embedding procedure, leading to identical assignments of objects to clusters. Based on this new vectorial representation, denoising methods are applied in a second step. Both steps provide a theoretically well controlled setup to translate from pairwise data to the respective denoised metric representation. We demonstrate the practical usefulness of our theoretical reasoning by discovering structure in protein sequence data bases, visibly improving performance upon existing automatic methods. 1

6 0.10773071 70 nips-2002-Distance Metric Learning with Application to Clustering with Side-Information

7 0.09363845 190 nips-2002-Stochastic Neighbor Embedding

8 0.089800172 19 nips-2002-Adapting Codes and Embeddings for Polychotomies

9 0.082166538 113 nips-2002-Information Diffusion Kernels

10 0.073815465 138 nips-2002-Manifold Parzen Windows

11 0.065123111 117 nips-2002-Intrinsic Dimension Estimation Using Packing Numbers

12 0.049619138 24 nips-2002-Adaptive Scaling for Feature Selection in SVMs

13 0.046048831 87 nips-2002-Fast Transformation-Invariant Factor Analysis

14 0.04497163 80 nips-2002-Exact MAP Estimates by (Hyper)tree Agreement

15 0.044829689 115 nips-2002-Informed Projections

16 0.043785397 10 nips-2002-A Model for Learning Variance Components of Natural Images

17 0.043058731 82 nips-2002-Exponential Family PCA for Belief Compression in POMDPs

18 0.043056723 124 nips-2002-Learning Graphical Models with Mercer Kernels

19 0.042310502 169 nips-2002-Real-Time Particle Filters

20 0.041239277 27 nips-2002-An Impossibility Theorem for Clustering

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.15), (1, -0.047), (2, -0.02), (3, 0.069), (4, -0.077), (5, 0.046), (6, -0.004), (7, -0.06), (8, -0.107), (9, 0.262), (10, 0.098), (11, 0.002), (12, -0.004), (13, -0.118), (14, 0.091), (15, 0.311), (16, -0.167), (17, 0.198), (18, 0.057), (19, -0.146), (20, -0.059), (21, 0.026), (22, -0.028), (23, -0.097), (24, -0.024), (25, -0.014), (26, 0.035), (27, 0.034), (28, -0.059), (29, -0.091), (30, 0.029), (31, 0.01), (32, 0.02), (33, 0.088), (34, 0.047), (35, 0.014), (36, 0.052), (37, 0.014), (38, -0.062), (39, -0.015), (40, -0.012), (41, -0.062), (42, -0.077), (43, 0.038), (44, 0.012), (45, -0.066), (46, -0.005), (47, 0.065), (48, -0.078), (49, 0.034)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.96601325 97 nips-2002-Global Versus Local Methods in Nonlinear Dimensionality Reduction

Author: Vin D. Silva, Joshua B. Tenenbaum

2 0.85220063 49 nips-2002-Charting a Manifold

Author: Matthew Brand

3 0.77051157 36 nips-2002-Automatic Alignment of Local Representations

Author: Yee W. Teh, Sam T. Roweis

4 0.66130877 117 nips-2002-Intrinsic Dimension Estimation Using Packing Numbers

Author: Balázs Kégl

Abstract: We propose a new algorithm to estimate the intrinsic dimension of data sets. The method is based on geometric properties of the data and requires neither parametric assumptions on the data generating model nor input parameters to set. The method is compared to a similar, widelyused algorithm from the same family of geometric techniques. Experiments show that our method is more robust in terms of the data generating distribution and more reliable in the presence of noise. 1

5 0.63004243 34 nips-2002-Artefactual Structure from Least-Squares Multidimensional Scaling

Author: Nicholas P. Hughes, David Lowe

6 0.55565482 138 nips-2002-Manifold Parzen Windows

7 0.55260217 190 nips-2002-Stochastic Neighbor Embedding

8 0.46483761 70 nips-2002-Distance Metric Learning with Application to Clustering with Side-Information

9 0.41000316 98 nips-2002-Going Metric: Denoising Pairwise Data

10 0.30362138 113 nips-2002-Information Diffusion Kernels

11 0.28206259 87 nips-2002-Fast Transformation-Invariant Factor Analysis

12 0.25740841 19 nips-2002-Adapting Codes and Embeddings for Polychotomies

13 0.24352981 115 nips-2002-Informed Projections

14 0.24070482 124 nips-2002-Learning Graphical Models with Mercer Kernels

15 0.23744182 63 nips-2002-Critical Lines in Symmetry of Mixture Models and its Application to Component Splitting

16 0.23547964 203 nips-2002-Using Tarjan's Red Rule for Fast Dependency Tree Construction

17 0.21813183 18 nips-2002-Adaptation and Unsupervised Learning

18 0.2179182 80 nips-2002-Exact MAP Estimates by (Hyper)tree Agreement

19 0.2136872 127 nips-2002-Learning Sparse Topographic Representations with Products of Student-t Distributions

20 0.19810759 84 nips-2002-Fast Exact Inference with a Factored Model for Natural Language Parsing

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(14, 0.012), (42, 0.062), (54, 0.603), (55, 0.032), (67, 0.014), (68, 0.037), (74, 0.054), (92, 0.02), (98, 0.055)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.99672312 36 nips-2002-Automatic Alignment of Local Representations

Author: Yee W. Teh, Sam T. Roweis

2 0.99592376 121 nips-2002-Knowledge-Based Support Vector Machine Classifiers

Author: Glenn M. Fung, Olvi L. Mangasarian, Jude W. Shavlik

Abstract: Prior knowledge in the form of multiple polyhedral sets, each belonging to one of two categories, is introduced into a reformulation of a linear support vector machine classifier. The resulting formulation leads to a linear program that can be solved efficiently. Real world examples, from DNA sequencing and breast cancer prognosis, demonstrate the effectiveness of the proposed method. Numerical results show improvement in test set accuracy after the incorporation of prior knowledge into ordinary, data-based linear support vector machine classifiers. One experiment also shows that a linear classifier, based solely on prior knowledge, far outperforms the direct application of prior knowledge rules to classify data. Keywords: use and refinement of prior knowledge, support vector machines, linear programming 1

same-paper 3 0.99447459 97 nips-2002-Global Versus Local Methods in Nonlinear Dimensionality Reduction

Author: Vin D. Silva, Joshua B. Tenenbaum

4 0.99211574 77 nips-2002-Effective Dimension and Generalization of Kernel Learning

Author: Tong Zhang

Abstract: We investigate the generalization performance of some learning problems in Hilbert function Spaces. We introduce a concept of scalesensitive effective data dimension, and show that it characterizes the convergence rate of the underlying learning problem. Using this concept, we can naturally extend results for parametric estimation problems in ﬁnite dimensional spaces to non-parametric kernel learning methods. We derive upper bounds on the generalization performance and show that the resulting convergent rates are optimal under various circumstances.

5 0.96880627 104 nips-2002-How the Poverty of the Stimulus Solves the Poverty of the Stimulus

Author: Willem H. Zuidema

Abstract: Language acquisition is a special kind of learning problem because the outcome of learning of one generation is the input for the next. That makes it possible for languages to adapt to the particularities of the learner. In this paper, I show that this type of language change has important consequences for models of the evolution and acquisition of syntax. 1 The Language Acquisition Problem For both artificial systems and non-human animals, learning the syntax of natural languages is a notoriously hard problem. All healthy human infants, in contrast, learn any of the approximately 6000 human languages rapidly, accurately and spontaneously. Any explanation of how they accomplish this difficult task must specify the (innate) inductive bias that human infants bring to bear, and the input data that is available to them. Traditionally, the inductive bias is termed - somewhat unfortunately -

6 0.96466631 67 nips-2002-Discriminative Binaural Sound Localization

7 0.92004436 156 nips-2002-On the Complexity of Learning the Kernel Matrix

8 0.887878 113 nips-2002-Information Diffusion Kernels

9 0.88320512 34 nips-2002-Artefactual Structure from Least-Squares Multidimensional Scaling

10 0.88081098 119 nips-2002-Kernel Dependency Estimation

11 0.87582564 190 nips-2002-Stochastic Neighbor Embedding

12 0.86184883 106 nips-2002-Hyperkernels

13 0.8612659 60 nips-2002-Convergence Properties of Some Spike-Triggered Analysis Techniques

14 0.86096585 70 nips-2002-Distance Metric Learning with Application to Clustering with Side-Information

15 0.85268104 117 nips-2002-Intrinsic Dimension Estimation Using Packing Numbers

16 0.84603363 49 nips-2002-Charting a Manifold

17 0.84525353 80 nips-2002-Exact MAP Estimates by (Hyper)tree Agreement

18 0.84388876 120 nips-2002-Kernel Design Using Boosting

19 0.83885318 64 nips-2002-Data-Dependent Bounds for Bayesian Mixture Methods

20 0.83029616 63 nips-2002-Critical Lines in Symmetry of Mixture Models and its Application to Component Splitting