nips nips2003 nips2003-71 knowledge-graph by maker-knowledge-mining

71 nips-2003-Fast Embedding of Sparse Similarity Graphs

Source: pdf

Author: John C. Platt

Abstract: This paper applies fast sparse multidimensional scaling (MDS) to a large graph of music similarity, with 267K vertices that represent artists, albums, and tracks; and 3.22M edges that represent similarity between those entities. Once vertices are assigned locations in a Euclidean space, the locations can be used to browse music and to generate playlists. MDS on very large sparse graphs can be effectively performed by a family of algorithms called Rectangular Dijsktra (RD) MDS algorithms. These RD algorithms operate on a dense rectangular slice of the distance matrix, created by calling Dijsktra a constant number of times. Two RD algorithms are compared: Landmark MDS, which uses the Nyström approximation to perform MDS; and a new algorithm called Fast Sparse Embedding, which uses FastMap. These algorithms compare favorably to Laplacian Eigenmaps, both in terms of speed and embedding quality. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 com Abstract This paper applies fast sparse multidimensional scaling (MDS) to a large graph of music similarity, with 267K vertices that represent artists, albums, and tracks; and 3. [sent-3, score-0.731]

2 Once vertices are assigned locations in a Euclidean space, the locations can be used to browse music and to generate playlists. [sent-5, score-0.458]

3 MDS on very large sparse graphs can be effectively performed by a family of algorithms called Rectangular Dijsktra (RD) MDS algorithms. [sent-6, score-0.133]

4 These RD algorithms operate on a dense rectangular slice of the distance matrix, created by calling Dijsktra a constant number of times. [sent-7, score-0.176]

5 These algorithms compare favorably to Laplacian Eigenmaps, both in terms of speed and embedding quality. [sent-9, score-0.142]

6 1 Introduction This paper examines a general problem: given a sparse graph of similarities between a set of objects, quickly assign each object a location in a low-dimensional Euclidean space. [sent-10, score-0.295]

7 This general problem can arise in several different applications: the paper addresses a speciﬁc application to music similarity. [sent-11, score-0.362]

8 In the case of music similarity, a set of musical entities (i. [sent-12, score-0.552]

9 Human editors have already supplied a graph of similarities, e. [sent-15, score-0.15]

10 There are three good reasons to embed a musical similarity graph: 1. [sent-18, score-0.27]

11 Visualization — If a user’s musical collection is placed in two dimensions, it can be easily visualized on a display. [sent-19, score-0.147]

12 Interpolation — Given a graph of similarities, it is simple to ﬁnd music that “sounds like” other music. [sent-22, score-0.47]

13 However, once music is embedded in a lowdimensional space, new user interfaces are enabled. [sent-23, score-0.429]

14 For example, a user can specify a playlist by starting at song A and ending at song B, with the songs in the playlist smoothly interpolating between A and B. [sent-24, score-0.502]

15 Compression — In order to estimate “sounds like” directly from a graph of music similarities, the user must have access to the graph of all known music. [sent-26, score-0.621]

16 However, once all of the musical entities are embedded, the coordinates for the music in a user’s collection can be shipped down to the user’s computer. [sent-27, score-0.575]

17 It is important to have algorithms that exploit the sparseness of similarity graphs because large-scale databases of similarities are very often sparse. [sent-29, score-0.204]

18 Human editors cannot create a dense N × N matrix of music similarity for large values of N. [sent-30, score-0.591]

19 Furthermore, humans are poor at accurately estimating large distances between entities (e. [sent-32, score-0.167]

20 ) Hence, there is a deﬁnite need for an scalable embedding algorithm that can handle a sparse graph of similarities, generalizing to similarities not seen in the training set. [sent-35, score-0.474]

21 1 Structure of Paper The paper describes three existing approaches to the sparse embedding problem in section 2 and section 3 describes a new algorithm for solving the problem. [sent-37, score-0.25]

22 2 goes into further detail on the application of embedding musical similarity into a low-dimensional Euclidean space. [sent-40, score-0.389]

23 2 Methods for Sparse Embedding Multidimensional scaling (MDS) [4] is an established branch of statistics that deals with embedding objects in a low-dimensional Euclidean space based on a matrix of similarities. [sent-41, score-0.177]

24 More speciﬁcally, MDS algorithms take a matrix of dissimilarities δrs and ﬁnd vectors xr whose inter-vector distances drs are well matched to δrs . [sent-42, score-0.307]

25 A common ﬂexible algorithm is called ALSCAL [13], which encourages the inter-vector distances to be near some ideal values: 2 2 min ∑(drs − dˆrs )2 , (1) xr rs where dˆ are derived from the dissimilarities δrs , typically through a linear relationship. [sent-43, score-0.296]

26 There are three existing approaches for applying MDS to large sparse dissimilarity matrices: 1. [sent-44, score-0.194]

27 Apply an MDS algorithm to the sparse graph directly. [sent-45, score-0.216]

28 For example, ALSCAL can operate on a sparse matrix by ignoring missing terms in its cost function (1). [sent-47, score-0.166]

29 1, ALSCAL cannot reconstruct the position of known data points given a sparse matrix of dissimilarities. [sent-49, score-0.143]

30 Use a graph algorithm to generate a full matrix of dissimilarities. [sent-51, score-0.143]

31 The Isomap algorithm [14] ﬁnds an embedding of a sparse set of dissimilarities into a lowdimensional Euclidean space. [sent-52, score-0.365]

32 Isomap ﬁrst applies Floyd’s shortest path algorithm [9] to ﬁnd the shortest distance between any two points in the graph, and then uses these N × N distances as input to a full MDS algorithm. [sent-53, score-0.28]

33 For generalizing musical artist similarity, [7] also computes an N × N matrix of distances between all artists in a set, based on the shortest distance through a graph. [sent-56, score-0.755]

34 The sparse graph in [7] was generated by human editors at the All Music Guide. [sent-57, score-0.258]

35 [7] shows that human perception of artist similarity is well modeled by generalizing using the shortest graph distance. [sent-58, score-0.48]

36 Similar to [14], [7] projects the N × N set of artist distances into a Euclidean space by a full MDS algorithm. [sent-59, score-0.304]

37 For ﬁnding all of the minimum distances, Floyd’s algorithm operates on a dense matrix of distances and has computational complexity O(N 3 ). [sent-63, score-0.238]

38 A better choice is to run Dijkstra’s algorithm [6], which ﬁnds the minimum distances from a single vertex to all other vertices in the graph. [sent-64, score-0.22]

39 Running a standard MDS algorithm on a full N × N matrix of distances requires O(N 2 Kd) computation, where K is the number of iterations of the MDS algorithm and d is the dimensionality of the embedding. [sent-67, score-0.159]

40 Use a graph algorithm to generate a thin dense rectangle of distances. [sent-70, score-0.188]

41 One natural way to reduce the complexity of the graph traversal part of Isomap is to not run Dijkstra’s algorithm N times. [sent-71, score-0.135]

42 RD algorithms operate on a dense rectangle of distances, ﬁlled in by Dijkstra’s algorithm. [sent-74, score-0.103]

43 [2] show that LMDS is the Nyström approximation [1] combined with classical MDS [4] operating on the rectangular distance matrix. [sent-77, score-0.101]

44 LMDS operates on a number of rows proportional to the embedding dimensionality, d. [sent-79, score-0.142]

45 The embedding coordinate for the mth point is thus 1 xm = ∑ Mi j (A j − D jm ), (2) 2 j √ where Mi j = vT / λi , A j is the average distance in the jth row of the rectangular distance i matrix and D jm is the distance between the mth point and the jth point ( j ∈ [1. [sent-83, score-0.474]

46 FastMap iterates over the dimensions of the projection, ﬁxing the position of all vertices in each dimension in turn. [sent-90, score-0.153]

47 Two vertices (xa , xb ) are chosen and the dissimilarity from these two vertices to all other vertices i are computed: (δai , δbi ). [sent-93, score-0.374]

48 During the ﬁrst iteration (dimension), the distances (dai , dbi ) are set equal to the dissimilarities. [sent-95, score-0.157]

49 The 2N distances can determine the location of the vertices along the dimension up to a shift, through use of the law of cosines: xi = 2 2 dai − dbi . [sent-96, score-0.339]

50 2dab (3) For each subsequent dimension, two new vertices are chosen and new dissimilarities (δai , δbi ) are computed by Dijkstra’s algorithm. [sent-97, score-0.187]

51 The subsequent dimensions are assumed to be orthogonal to previous ones, so the distances for dimension N are computed from the dissimilarities via: 2 2 δai = dai + N−1 N−1 n=1 n=1 2 2 ∑ (xan − xin )2 ⇒ dai = δai − ∑ (xan − xin )2 . [sent-98, score-0.452]

52 (4) Thus, each dimension accounts for a fraction of the dissimilarity matrix, analogous to PCA. [sent-99, score-0.115]

53 Note that, except for dab , all other distances are needed as distance squared, so only one square root for each dimension is required. [sent-100, score-0.199]

54 The distances produced by Dijkstra’s algorithm are the minimum graph distances modiﬁed by equation (4) in order to reﬂect the projection used so far. [sent-101, score-0.394]

55 5 2 4 6 8 10 Figure 1: Reconstructing a grid of points directly from a sparse distance matrix. [sent-118, score-0.176]

56 An MDS algorithm needs to be tested on distance matrices that are computed from distances between real points, in order to verify that the algorithm quickly produces sensible results. [sent-120, score-0.17]

57 When the dissimilarity matrix is very sparse, there are not enough constraints on the ﬁnal solution, so ALSCAL gets stuck in a local minimum. [sent-127, score-0.151]

58 These results show that FSE (and other RD MDS algorithms) are preferable to using sparse MDS algorithms. [sent-129, score-0.108]

59 2 Application: Generalizing Music Similarity This section presents the results of using RD MDS algorithms to project a large music dissimilarity graph into low-dimensional Euclidean space. [sent-132, score-0.556]

60 This projection enables visualization and interpolation over music collections. [sent-133, score-0.515]

61 The dissimilarity graph was derived from a music metadata database. [sent-134, score-0.605]

62 Each track has subjective metadata assigned to it by human editors: style (speciﬁc style), subgenre (more general style), vocal code (gender of singer), and mood. [sent-136, score-0.217]

63 The database contains which tracks occur on which albums and which artists created those albums. [sent-138, score-0.297]

64 Relationship Between Entities Two tracks have same style, vocal code, mood Two tracks have same style Two tracks have same subgenre Track is on album Album is by artist Edge Distance in Graph 1 2 4 1 2 Table 1: Mapping of relationship to edge distance. [sent-139, score-0.564]

65 A sparse similarity graph was extracted from the metadata database according to Table 1. [sent-140, score-0.365]

66 Every track, album, and artist are represented by a vertex in the graph. [sent-141, score-0.18]

67 Every track was connected to all albums it appeared on, while each album was connected to its artist. [sent-142, score-0.216]

68 The track similarity edges were sampled randomly, to provide an average of 7 links of edges of distance 1, 2, and 4. [sent-143, score-0.249]

69 RD MDS enabled this experiment: the full distance matrix would have taken days to compute with 267K calls to Dijkstra. [sent-146, score-0.105]

70 Also, the graph distances were derived after some tuning (not on the test set): the speed of RD MDS enabled this tuning. [sent-147, score-0.256]

71 One advantage of the music application is that the quality of the embedding can be tested externally. [sent-148, score-0.504]

72 A test set of 50 playlists, with 444 pairs of sequential songs was gathered from real users who listened to these playlists. [sent-149, score-0.154]

73 An embedding is considered good if sequential songs in the playlists are frequently closer to each other than random songs in the database. [sent-150, score-0.591]

74 Table 2 shows the quality of the embedding as a fraction of random songs that are closer than sequential songs. [sent-151, score-0.296]

75 The lower the fraction, the better the embedding, because the embedding more accurately reﬂects users’ ideas of music similarity. [sent-152, score-0.504]

76 This fraction is computed by treating the pairwise distances as scores from a classiﬁer, computing an ROC curve, then computing 1. [sent-153, score-0.124]

77 4 Table 2: Speed and accuracy of music embedding for various algorithms. [sent-167, score-0.504]

78 A Laplacian Eigenmap applied to the entire sparse similarity matrix was much slower than either of the RD MDS algorithms, and did not perform as well for this problem. [sent-174, score-0.243]

79 A Gaussian kernel with σ = 2 was used to convert distances to similarities for the Laplacian Eigenmap. [sent-175, score-0.203]

80 5 Figure 2: LMDS Projection of the entire music dissimilarity graph into 2D. [sent-184, score-0.556]

81 First, the top two dimensions are plotted to form a visualization of music space. [sent-187, score-0.449]

82 2, which shows the coordinates of 23 artists that occur near the center of the space. [sent-189, score-0.154]

83 The playlists interpolate between the ﬁrst and last songs. [sent-195, score-0.164]

84 The main application for the music graph projection is the generation of playlists. [sent-196, score-0.534]

85 There are several different possible objectives for music playlists: background listening, dance mixes, music discovery. [sent-197, score-0.724]

86 One of the criteria for playlists is that they play similar music together (i. [sent-198, score-0.553]

87 The goal for this paper is to generate playlists for background listening. [sent-201, score-0.164]

88 Therefore, the only criterion we use for generation is smoothness and playlists are generated by linear interpolation in the embedding space. [sent-202, score-0.388]

89 However, smoothness is not the only possible playlist generation mode: other criteria can be added (such as matching beats or artist self-avoidance or minimum distance between songs). [sent-203, score-0.361]

90 Such criteria are a matter of subjective musical taste and are beyond the scope of this paper. [sent-205, score-0.174]

91 Table 3 shows two background-listening playlists formed by interpolating in the projected space. [sent-206, score-0.22]

92 The playlists were drawn from a collection of 3920 songs. [sent-207, score-0.164]

93 Unlike the image interpolation in [14], not every point in the 20-dimensional space has a valid song attached to it. [sent-208, score-0.124]

94 5 Discussion and Conclusions Music playlist generation and browsing can utilize a large sparse similarity graph designed by editors. [sent-213, score-0.424]

95 In order to allow tractable computations on this graph, its vertices can be projected into a low-dimensional space. [sent-214, score-0.124]

96 Music similarity graphs are amongst the largest graphs ever to be embedded. [sent-216, score-0.15]

97 Rectangular Dijkstra MDS algorithms can be used to efﬁciently embed these large sparse graphs. [sent-217, score-0.131]

98 Using LMDS, a music graph with 267K vertices and 3. [sent-221, score-0.566]

99 The quest for ground truth in musical artist similarity. [sent-274, score-0.327]

100 Learning a gaussian process prior for automatically generating music playlists. [sent-309, score-0.362]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('mds', 0.389), ('music', 0.362), ('lmds', 0.295), ('fse', 0.229), ('dijkstra', 0.196), ('artist', 0.18), ('playlists', 0.164), ('alscal', 0.147), ('mclachlan', 0.147), ('musical', 0.147), ('sarah', 0.147), ('embedding', 0.142), ('artists', 0.131), ('beatles', 0.131), ('songs', 0.131), ('distances', 0.124), ('alanis', 0.115), ('hendrix', 0.115), ('jimi', 0.115), ('graph', 0.108), ('sparse', 0.108), ('similarity', 0.1), ('albums', 0.098), ('nystr', 0.098), ('vertices', 0.096), ('dissimilarities', 0.091), ('dissimilarity', 0.086), ('rd', 0.085), ('doors', 0.082), ('playlist', 0.082), ('stevens', 0.082), ('similarities', 0.079), ('song', 0.068), ('tracks', 0.068), ('album', 0.065), ('blondie', 0.065), ('fastmap', 0.065), ('visualization', 0.059), ('rs', 0.057), ('dai', 0.057), ('interpolation', 0.056), ('shortest', 0.055), ('rectangular', 0.055), ('style', 0.054), ('track', 0.053), ('dense', 0.052), ('laplacian', 0.049), ('fiona', 0.049), ('metadata', 0.049), ('cat', 0.048), ('distance', 0.046), ('euclidean', 0.044), ('entities', 0.043), ('isomap', 0.043), ('user', 0.043), ('apple', 0.043), ('editors', 0.042), ('projection', 0.038), ('generalizing', 0.037), ('matrix', 0.035), ('multidimensional', 0.034), ('dbi', 0.033), ('dijsktra', 0.033), ('drs', 0.033), ('floyd', 0.033), ('subgenre', 0.033), ('tori', 0.033), ('xan', 0.033), ('xin', 0.033), ('eigenmaps', 0.031), ('stuck', 0.03), ('dimension', 0.029), ('interpolating', 0.028), ('jm', 0.028), ('reconstructs', 0.028), ('vocal', 0.028), ('projected', 0.028), ('rectangle', 0.028), ('dimensions', 0.028), ('complexity', 0.027), ('criteria', 0.027), ('amos', 0.026), ('eigenmap', 0.026), ('generation', 0.026), ('graphs', 0.025), ('edges', 0.025), ('roc', 0.025), ('enabled', 0.024), ('platt', 0.024), ('xr', 0.024), ('mth', 0.024), ('eigenproblem', 0.024), ('lowdimensional', 0.024), ('fast', 0.023), ('sequential', 0.023), ('coordinates', 0.023), ('landmark', 0.023), ('embed', 0.023), ('operate', 0.023), ('grid', 0.022)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999934 71 nips-2003-Fast Embedding of Sparse Similarity Graphs

Author: John C. Platt

2 0.20945694 150 nips-2003-Out-of-Sample Extensions for LLE, Isomap, MDS, Eigenmaps, and Spectral Clustering

Author: Yoshua Bengio, Jean-françcois Paiement, Pascal Vincent, Olivier Delalleau, Nicolas L. Roux, Marie Ouimet

Abstract: Several unsupervised learning algorithms based on an eigendecomposition provide either an embedding or a clustering only for given training points, with no straightforward extension for out-of-sample examples short of recomputing eigenvectors. This paper provides a uniﬁed framework for extending Local Linear Embedding (LLE), Isomap, Laplacian Eigenmaps, Multi-Dimensional Scaling (for dimensionality reduction) as well as for Spectral Clustering. This framework is based on seeing these algorithms as learning eigenfunctions of a data-dependent kernel. Numerical experiments show that the generalizations performed have a level of error comparable to the variability of the embedding algorithms due to the choice of training data. 1

3 0.11234441 108 nips-2003-Learning a Distance Metric from Relative Comparisons

Author: Matthew Schultz, Thorsten Joachims

Abstract: This paper presents a method for learning a distance metric from relative comparison such as “A is closer to B than A is to C”. Taking a Support Vector Machine (SVM) approach, we develop an algorithm that provides a ﬂexible way of describing qualitative training data as a set of constraints. We show that such constraints lead to a convex quadratic programming problem that can be solved by adapting standard methods for SVM training. We empirically evaluate the performance and the modelling ﬂexibility of the algorithm on a collection of text documents. 1

4 0.098894067 128 nips-2003-Minimax Embeddings

Author: Matthew Brand

Abstract: Spectral methods for nonlinear dimensionality reduction (NLDR) impose a neighborhood graph on point data and compute eigenfunctions of a quadratic form generated from the graph. We introduce a more general and more robust formulation of NLDR based on the singular value decomposition (SVD). In this framework, most spectral NLDR principles can be recovered by taking a subset of the constraints in a quadratic form built from local nullspaces on the manifold. The minimax formulation also opens up an interesting class of methods in which the graph is “decorated” with information at the vertices, offering discrete or continuous maps, reduced computational complexity, and immunity to some solution instabilities of eigenfunction approaches. Apropos, we show almost all NLDR methods based on eigenvalue decompositions (EVD) have a solution instability that increases faster than problem size. This pathology can be observed (and corrected via the minimax formulation) in problems as small as N < 100 points. 1 Nonlinear dimensionality reduction (NLDR) . Spectral NLDR methods are graph embedding problems where a set of N points X = [x1 , · · · , xN ] ∈ RD×N sampled from a low-dimensional manifold in a ambient space RD is reparameterized by imposing a neighborhood graph G on X and embedding the graph with minimal distortion in a “parameterization” space Rd , d < D. Typically the graph is sparse and local, with edges connecting points to their immediate neighbors. The embedding must keep these edges short or preserve their length (for isometry) or angles (for conformality). The graph-embedding problem was ﬁrst introduced as a least-squares problem by Tutte [1], and as an eigenvalue problem by Fiedler [2]. The use of sparse graphs to generate metrics for least-squares problems has been studied intensely in the following three decades (see [3]). Modern NLDR methods use graph constraints to generate a metric in a space of embeddings RN . Eigenvalue decomposition (EVD) gives the directions of least or greatest variance under this metric. Typically a subset of d extremal eigenvectors gives the embedding of N points in Rd parameterization space. This includes the IsoMap family [4], the locally linear embedding (LLE) family [5,6], and Laplacian methods [7,8]. Using similar methods, the Automatic Alignment [6] and Charting [9] algorithms embed local subspaces instead of points, and by combining subspace projections thus obtain continuous maps between RD and Rd . This paper introduces a general algebraic framework for computing optimal embeddings directly from graph constraints. The aforementioned methods can can be recovered as special cases. The framework also suggests some new methods with very attractive properties, including continuous maps, reduced computational complexity, and control over the degree of conformality/isometry in the desired map. It also eliminates a solution instability that is intrinsic to EVD-based approaches. A perturbational analysis quantiﬁes the instability. 2 Minimax theorem for graph embeddings We begin with neighborhood graph speciﬁed by a nondiagonal weighted adjacency matrix M ∈ RN×N that has the data-reproducing property XM = X (this can be relaxed to XM ≈ X in practice). The graph-embedding and NLDR literatures offer various constructions of M, each appropriate to different sets of assumptions about the original embedding and its sampling X (e.g., isometry, local linearity, noiseless samples, regular sampling, etc.). Typically Mi j = 0 if points i, j are nearby on the intrinsic manifold and |Mi j | is small or zero otherwise. Each point is taken to be a linear or convex combination of its neighbors, and thus M speciﬁes manifold connectivity in the sense that any nondegenerate embedding Y that satisﬁes YM ≈ Y with small residual YM − Y F will preserve this connectivity and the structure of local neighborhoods. For example, in barycentric embeddings, each point is the average of its neighbors and thus Mi j = 1/k if vertex i is connected to vertex j (of degree k). We will also consider three optional constraints on the embedding : 1. A null-space restriction, where the solution must be outside to the column-space of C ∈ RN×M , M < N. For example, it is common to stipulate that the solution Y be centered, i.e., YC = 0 for C = 1, the constant vector. 2. A basis restriction, where the solution must be a linear combination of the rows of basis Z ∈ RK×N , K ≤ N. This can be thought of as information placed at the vertices of the graph that serves as example inputs for a target NLDR function. We will use this to construct dimension-reducing radial basis function networks. 3. A metric Σ ∈ RN×N that determines how error is distributed over the points. For example, it might be important that boundary points have less error. We assume that Σ is symmetric positive deﬁnite and has factorization Σ = AA (e.g., A could be a Cholesky factor of Σ). In most settings, the optional matrices will default to the identity matrix. In this context, we deﬁne the per-dimension embedding error of row-vector yi ∈ rows(Y) to be . EM (yi ) = max yi ∈range(Z),, K∈RM×N (yi (M + CD) − yi )A yi A (1) where D is a matrix constructed by an adversary to maximize the error. The optimizing yi is a vector inside the subspace spanned by the rows of Z and outside the subspace spanned by the columns of C, for which the reconstruction residual yi M−yi has smallest norm w.r.t. the metric Σ. The following theorem identiﬁes the optimal embedding Y for any choice of M, Z, C, Σ: Minimax solution: Let Q ∈ SK×P be a column-orthonormal basis of the null-space of the rows of ZC, with P = K − rank(C). Let B ∈ RP×P be a square factor satisfying B B = Q ZΣZ Q, e.g., a Cholesky factor (or the “R” factor in QR-decomposition of (Q ZA) ). Compute the left singular vectors U ∈ SN×N of Udiag(s)V = B− Q Z(I − M)A, with . singular values s = [s1 , · · · , sP ] ordered s1 ≤ s2 ≤ · · · ≤ s p . Using the leading columns U1:d of U, set Y = U1:d B− Q Z. Theorem 1. Y is the optimal (minimax) embedding in Rd with error [s1 , · · · , sd ] 2 : . Y = U1:d B− Q Z = arg min ∑ EM (yi )2 with EM (yi ) = si . Y∈Rd×N y ∈rows(Y) i (2) Appendix A develops the proof and other error measures that are minimized. Local NLDR techniques are easily expressed in this framework. When Z = A = I, C = [], and M reproduces X through linear combinations with M 1 = 1, we recover LLE [5]. When Z = I, C = [], I − M is the normalized graph Laplacian, and A is a diagonal matrix of vertex degrees, we recover Laplacian eigenmaps [7]. When further Z = X we recover locally preserving projections [8]. 3 Analysis and generalization of charting The minimax construction of charting [9] takes some development, but offers an interesting insight into the above-mentioned methods. Recall that charting ﬁrst solves for a set of local afﬁne subspace axes S1 ∈ RD×d , S2 , · · · at offsets µ1 ∈ RD , µ2 , · · · that best cover the data and vary smoothly over the manifold. Each subspace offers a chart—a local parameterization of the data by projection onto the local axes. Charting then constructs a weighted mixture of afﬁne projections that merges the charts into a global parameterization. If the data manifold is curved, each projection will assign a point a slightly different embedding, so the error is measured as the variance of these proposed embeddings about their mean. This maximizes consistency and tends to produce isometric embeddings; [9] discusses ways to explicitly optimize the isometry of the embedding. Under the assumption of isometry, the charting error is equivalent to the sumsquared displacements of an embedded point relative to its immediate neighbors (summed over all neighborhoods). To construct the same error criteria in the minimax setting, let xi−k , · · · , xi , · · · , xi+k denote points in the ith neighborhood and let the columns of Vi ∈ R(2k+1)×d be an orthonormal basis of rows of the local parameterization Si [xi−k , · · · , xi , · · · , xi+k ]. Then a nonzero reparameterization will satisfy [yi−k , · · · , yi , · · · , yi+k ]Vi Vi = [yi−k , · · · , yi , · · · , yi+k ] if and only if it preserves the relative position of the points in the local parameterization. Conversely, any relative displacements of the points are isolated by the formula [yi−k , · · · , yi , · · · , yi+k ](I − Vi Vi ). Minimizing the Frobenius norm of this expression is thus equivalent to minimizing the local error in charting. We sum these constraints over all neighborhoods to obtain the constraint matrix M = I − ∑i Fi (I − Vi Vi )Fi , where (Fi )k j = 1 iff the jth point of the ith neighborhood is the kth point of the dataset. Because Vi Vi and (I − Vi Vi ) are complementary, it follows that the error criterion of any local NLDR method (e.g., LLE, Laplacian eigenmaps, etc.) must measure the projection of the embedding onto some subspace of (I − Vi Vi ). To construct a continuous map, charting uses an overcomplete radial basis function (RBF) representation Z = [z(x1 ), z(x2 ), · · · z(xN )], where z(x) is a vector that stacks z1 (x), z2 (x), etc., and pm (x) . Km (x − µm ) , zm (x) = 1 ∑m pm (x) −1 . pm (x) = N (x|µm , Σm ) ∝ e−(x−µm ) Σm (x−µm )/2 (3) (4) and Km is any local linear dimensionality reducer, typically Sm itself. Each column of Z contains many “views” of the same point that are combined to give its low-dimensional embedding. Finally, we set C = 1, which forces the embedding of the full data to be centered. Applying the minimax solution to these constraints yields the RBF network mixing ma. trix, f (x) = U1:d B− Q z(x). Theorem 1 guarantees that the resulting embedding is leastsquares optimal w.r.t. Z, M, C, A at the datapoints f (xi ), and because f (·) is an afﬁne transform of z(·) it smoothly interpolates the embedding between points. There are some interesting variants: Kernel embeddings of the twisted swiss roll generalized EVD minimax SVD UR corner detail LL corner detail Fig. 1. Minimax and generalized EVD solution for kernel eigenmap of a non-developable swiss roll. Points are connected into a grid which ideally should be regular. The EVD solution shows substantial degradation. Insets detail corners where the EVD solution crosses itself repeatedly. The border compression is characteristic of Laplacian constraints. One-shot charting: If we set the local dimensionality reducers to the identity matrix (all Km = I), then the minimax method jointly optimizes the local dimensionality reduction to charts and the global coordination of the charts (under any choice of M). This requires that rows(Z) ≤ N for a fully determined solution. Discrete isometric charting: If Z = I then we directly obtain a discrete isometric embedding of the data, rather than a continuous map, making this a local equivalent of IsoMap. Reduced basis charting: Let Z be constructed using just a small number of kernels randomly placed on the data manifold, such that rows(Z) N. Then the size of the SVD problem is substantially reduced. 4 Numerical advantage of minimax method Note that the minimax method projects the constraint matrix M into a subspace derived from C and Z and decomposes it there. This suppresses unwanted degrees of freedom (DOFs) admitted by the problem constraints, for example the trivial R0 embedding where all points are mapped to a single point yi = N −1/2 . The R0 embedding serves as a translational DOF in the solution. LLE- and eigenmap-based methods construct M to have a constant null-space so that the translational DOF will be isolated in the EVD as null eigenvalue paired to a constant eigenvector, which is then discarded. However, section 4.1 shows that this construction makes the EVD increasingly unstable as problem size grows and/or the data becomes increasing amenable to low-residual embeddings, ultimately causing solution collapse. As the next paragraph demonstrates, the problem is exacerbated when embedding w.r.t. a basis Z (via the equivalent generalized eigenproblem), partly because the eigenvector associated with the unwanted DOF can have arbitrary structure. In all cases the problem can be averted by using the minimax formulation with C = 1 to suppress the DOF. A 2D plane was embedded in 3D with a curl, a twist, and 2.5% Gaussian noise, then regularly sampled at 900 points. We computed a kernelized Laplacian eigenmap using 70 random points as RBF centers, i.e., a continous map using M derived from the graph Laplacian and Z constructed as above. The map was computed both via the minimax (SVD) method and via the equivalent generalized eigenproblem, where the translational degree of freedom must be removed by discarding an eigenvector from the solution. The two solutions are algebraically equivalent in every other regard. A variety of eigensolvers were tried; we took −5 excess energy x 10 Eigen spectrum compared to minimax spectrum 15 10 5 0 −5 Eigen spectrum compared to minimax spectrum 2 15 deviation excess energy x 10 10 5 100 200 eigenvalue Error in null embedding −5 x 10 0 −2 −4 −6 −8 0 100 −5 eigenvalue Error in null embedding 200 100 200 300 400 500 point 600 700 800 900 Fig. 2. Excess energy in the eigenspectrum indicates that the translational DOF has contam2 inated many eigenvectors. If the EVD had successfully isolated the unwanted DOF, then its 0 remaining eigenvalues should be identical to those derived from the minimax solution. The −2 −4 graph at left shows the difference in the eigenspectra. The graph at right shows the EVD −6 solution’s deviation from the translational vector y0 = 1 · N −1/2 ≈ .03333. If the numer−8 ics were100 200 the line would be ﬂat, but in practice the deviation is signiﬁcant enough perfect 300 400 500 600 700 800 900 point (roughly 1% of the diameter of the embedding) to noticably perturb points in ﬁgure 1. deviation x 10 the best result. Figure 1 shows that the EVD solution exhibits many defects, particularly a folding-over of the manifold at the top and bottom edges and at the corners. Figure 2 shows that the noisiness of the EVD solution is due largely to mutual contamination of numerically unstable eigenvectors. 4.1 Numerical instability of eigen-methods The following theorem uses tools of matrix perturbation theory to show that as the problem size increases, the desired and unwanted eigenvectors become increasingly wobbly and gradually contaminate each other, leading to degraded solutions. More precisely, the low-order eigenvalues are ill-conditioned and exhibit multiplicities that may be true (due to noiseless samples from low-curvature manifolds) or false (due to numerical noise). Although in many cases some post-hoc algebra can “ﬁlter” the unwanted components out of the contaminated eigensolution, it is not hard to construct cases where the eigenvectors cannot be cleanly separated. The minimax formulation is immune to this problem because it explicitly suppresses the gratuitous component(s) before matrix decomposition. Theorem 2. For any ﬁnite numerical precision, as the number of points N increases, the Frobenius norm of numerical noise in the null eigenvector v0 can grow as O(N 3/2 ), and the eigenvalue problem can approach a false multiplicity at a rate as fast as O(N 3/2 ), at which point the eigenvectors of interest—embedding and translational—are mutually contaminated and/or have an indeterminate eigenvalue ordering. Please see appendix B for the proof. This theorem essentially lower-bounds an upperbound on error; examples can be constructed in which the problem is worse. For example, it can be shown analytically that when embedding points drawn from the simple curve xi = [a, cos πa] , a ∈ [0, 1] with K = 2 neighbors, instabilities cannot be bounded better than O(N 5/2 ); empirically we see eigenvector mixing with N < 100 points and we see it grow at the rate ≈ O(N 4 )—in many different eigensolvers. At very large scales, more pernicious instabilities set in. E.g., by N = 20000 points, the solution begins to fold over. Although algebraic multiplicity and instability of the eigenproblem is conceptually a minor oversight in the algorithmic realizations of eigenfunction embeddings, as theorem 2 shows, the consequences are eventually fatal. 5 Summary One of the most appealing aspects of the spectral NLDR literature is that algorithms are usually motivated from analyses of linear operators on smooth differentiable manifolds, e.g., [7]. Understandably, these analysis rely on assumptions (e.g., smoothness or isometry or noiseless sampling) that make it difﬁcult to predict what algorithmic realizations will do when real, noisy data violates these assumptions. The minimax embedding theorem provides a complete algebraic characterization of this discrete NLDR problem, and provides a solution that recovers numerically robustiﬁed versions of almost all known algorithms. It offers a principled way of constructing new algorithms with clear optimality properties and good numerical conditioning—notably the construction of a continuous NLDR map (an RBF network) in a one-shot optimization ( SVD ). We have also shown how to cast several local NLDR principles in this framework, and upgrade these methods to give continuous maps. Working in the opposite direction, we sketched the minimax formulation of isometric charting and showed that its constraint matrix contains a superset of all the algebraic constraints used in local NLDR techniques. References 1. W.T. Tutte. How to draw a graph. Proc. London Mathematical Society, 13:743–768, 1963. 2. Miroslav Fiedler. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech. Math. Journal, 25:619–633, 1975. 3. Fan R.K. Chung. Spectral graph theory, volume 92 of CBMS Regional Conference Series in Mathematics. American Mathematical Society, 1997. 4. Joshua B. Tenenbaum, Vin de Silva, and John C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290:2319–2323, December 22 2000. 5. Sam T. Roweis and Lawrence K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290:2323–2326, December 22 2000. 6. Yee Whye Teh and Sam T. Roweis. Automatic alignment of hidden representations. In Proc. NIPS-15, 2003. 7. Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. volume 14 of Advances in Neural Information Processing Systems, 2002. 8. Xiafei He and Partha Niyogi. Locality preserving projections. Technical Report TR-2002-09, University of Chicago Computer Science, October 2002. 9. Matthew Brand. Charting a manifold. volume 15 of Advances in Neural Information Processing Systems, 2003. 10. G.W. Stewart and Ji-Guang Sun. Matrix perturbation theory. Academic Press, 1990. A Proof of minimax embedding theorem (1) The burden of this proof is carried by supporting lemmas, below. To emphasize the proof strategy, we give the proof ﬁrst; supporting lemmas follow. Proof. Setting yi = li Z, we will solve for li ∈ columns(L). Writing the error in terms of li , EM (li ) = max K∈RM×N li Z(I − M − CK)A li Z(I − M)A − li ZCKA = max . M×N li ZA li ZA K∈R (5) The term li ZCKA produces inﬁnite error unless li ZC = 0, so we accept this as a constraint and seek li Z(I − M)A min . (6) li ZA li ZC=0 By lemma 1, that orthogonality is satisﬁed by solving the problem in the space orthogonal . to ZC; the basis for this space is given by columns of Q = null((ZC) ). By lemma 2, the denominator of the error speciﬁes the metric in solution space to be ZAA Z ; when the problem is projected into the space orthogonal to ZC it becomes Q (ZAA Z )Q. Nesting the “orthogonally-constrained-SVD” construction of lemma 1 inside the “SVD-under-a-metric” lemma 2, we obtain a solution that uses the correct metric in the orthogonal space: B B = Q ZAA Z Q − Udiag(s)V = B (7) {Q(Z(I − M)A)} (8) L = QB−1 U (9) where braces indicate the nesting of lemmas. By the “best-projection” lemma (#3), if we order the singular values by ascending magnitude, L1:d = arg min J∈RN×d ∑ji ∈cols(J) ( j Z(I − M)A / j )2 ZΣZ The proof is completed by making the substitutions L Z → Y and x A → x Σ = AA ), and leaving off the ﬁnal square root operation to obtain (Y )1:d = arg min ∑ji ∈cols(J) j (I − M) Σ / j J∈RN×d (10) Σ (for 2 Σ . (11) Lemma 1. Orthogonally constrained SVD: The left singular vectors L of matrix M under . SVD the constraint U C = 0 are calculated as Q = null(C ), Udiag(s)V ← Q M, L = QU. Proof. First observe that L is orthogonal to C: By deﬁnition, the null-space basis satisﬁes Q C = 0, thus L C = U Q C = 0. Let J be an orthonormal basis for C, with J J = I and Q J = 0. Then Ldiag(s)V = QQ M = (I − JJ )M, the orthogonal projector of C applied to M, proving that the SVD captures the component of M that is orthogonal to C. Lemma 2. SVD with respect to a metric: The vectors li ∈ L, vi ∈ V that diagonalize matrix M with respect to positive deﬁnite column-space metric Σ are calculated as B B ← Σ, SVD . Udiag(s)V ← B− M, L = B−1 U satisfy li M / li Σ = si and extremize this form for the extremal singular values smin , smax . Proof. By construction, L and V diagonalize M: L MV = (B−1 U) MV = U (B− M)V = diag(s) (12) B− and diag(s)V = M. Forming the gram matrices of both sides of the last line, we obtain the identity Vdiag(s)2 V = M B−1 B− M = M Σ−1 M, which demonstrates that si ∈ s are the singular values of M w.r.t. column-space metric Σ. Finally, L is orthonormal w.r.t. the metric Σ, because L 2 = L ΣL = U B− B BB−1 U = I. Consequently, Σ l M / l Σ = l M /1 = si vi and by the Courant-Hilbert theorem, smax = max l M / l Σ ; = si . smin = min l M / l Σ . l l (13) (14) Lemma 3. Best projection: Taking L and s from lemma 2, let the columns of L and elements of s be sorted so that s1 ≥ s2 ≥ · · · ≥ sN . Then for any dimensionality 1 ≤ d ≤ N, . L1:d = [l1 , · · · , ld ] = arg max J M (J ΣJ)−1 (15) J∈RN×d = arg max F (16) ∑ji ∈cols(J) ( j M / j Σ )2 (17) J∈RN×d |J ΣJ=I = arg max J∈RN×d J M with the optimum value of all right hand sides being (∑d s2 )1/2 . If the sort order is rei=1 i versed, the minimum of this form is obtained. Proof. By the Eckart-Young-Mirsky theorem, if U MV = diag(s) with singular values . sorted in descending order, then U1:d = [u1 , · · · , ud ] = arg maxU∈SN×d U M F . We ﬁrst extend this to a non-orthonogonal basis J under a Mahalonobis norm: maxJ∈RN×d J M (J J)−1 = maxU∈SN×d U M F (18) because J M 2 (J J)−1 = trace(M J(J J)−1 J M) = trace(M JJ+ (JJ+ ) M) = (JJ+ )M 2 = UU M 2 = U M 2 since JJ+ is a (symmetric) orthogonal proF F F jector having binary eigenvalues λ ∈ {0, 1} and therefore it is the gram of an thin orthogonal matrix. We then impose a metric Σ on the column-space of J to obtain the ﬁrst criterion (equation 15), which asks what maximizes variance in J M while minimizing the norm of J w.r.t. metric Σ. Here it sufﬁces to substitute in the leading (resp., trailing) columns of L and verify that the norm is maximized (resp., minimized). Expanding, L1:d M 2 ΣL )−1 = trace((L1:d M) (L1:d ΣL1:d )−1 (L1:d M)) = (L 1:d 1:d trace((L1:d M) I(L1:d M)) = trace((diag(s1:d )V1:d ) (diag(s1:d )V1:d )) = s1:d 2 . Again, by the Eckart-Young-Mirsky theorem, these are the maximal variance-preserving projections, so the ﬁrst criterion is indeed maximized by setting J to the columns in L corresponding to the largest values in s. Criterion #2 restates the ﬁrst criterion with the set of candidates for J restricted to (the hyperelliptical manifold of) matrices that reduce the metric on the norm to the identity matrix (thereby recovering the Frobenius norm). Criterion #3 criterion merely expands the above trace by individual singular values. Note that the numerator and denominator can have different metrics because they are norms in different spaces, possibly of different dimension. Finally, that the trailing d eigenvectors minimize these criteria follows directly from the fact that leading N − d singular values account for the maximal part of the variance. B Proof of instability theorem (2) Proof. When generated from a sparse graph with average degree K, weighted connectivity matrix W is sparse and has O(NK) entries. Since the graph vertices represent samples from a smooth manifold, increasing the sampling density N does not change the distribution of magnitudes in W. Consider a perturbation of the nonzero values in W, e.g., W → W + E due to numerical noise E created by ﬁnite machine precision. By the weak law of large √ numbers, the Frobenius norm of the sparse perturbation grows as E F ∼ O( N). However the t th -smallest nonzero eigenvalue λt (W) grows as λt (W) = vt Wvt ∼ O(N −1 ), because elements of corresponding eigenvector vt grow as O(N −1/2 ) and only K of those elements are multiplied by nonzero values to form each element of Wvt . In sum, the perturbation E F grows while the eigenvalue λt (W) shrinks. In linear embedding algorithms, . the eigengap of interest is λgap = λ1 − λ0 . The tail eigenvalue λ0 = 0 by construction but it is possible that λ0 > 0 with numerical error, thus λgap ≤ λ1 . Combining these facts, the ratio between the perturbation and the eigengap grows as E F /λgap ∼ O(N 3/2 ) or faster. Now consider the shifted eigenproblem I − W with leading (maximal) eigenvalues 1 − λ0 ≥ 1 − λ1 ≥ · · · and unchanged eigenvectors. From matrix perturbation the. ory [10, thm. V.2.8], when W is perturbed to W = W + E, the change in the lead√ ing eigenvalue from 1 − λ0 to 1 − λ0 is bounded as |λ0 − λ0 | ≤ 2 E F and similarly √ √ 1 − λ1 ≤ 1 − λ1 + 2 E F . Thus λgap ≥ λgap − 2 E F . Since E F /λgap ∼ O(N 3/2 ), the right hand side of the gap bound goes negative at a supralinear rate, implying that the eigenvalue ordering eventually becomes unstable with the possibility of the ﬁrst and second eigenvalue/vector pairs being swapped. Mutual contamination of the eigenvectors happens well before: Under general (dense) conditions, the change in the eigenvector v0 is bounded E F as v0 − v0 ≤ |λ −λ4 |−√2 E [10, thm. V.2.8]. (This bound is often tight enough to serve F 0 1 as a good approximation.) Specializing this to the sparse embedding matrix, we ﬁnd that √ √ O( N) O( N) the bound weakens to v0 − 1 · N −1/2 ∼ O(N −1 )−O(√N) > O(N −1 ) = O(N 3/2 ).

5 0.078747861 46 nips-2003-Clustering with the Connectivity Kernel

Author: Bernd Fischer, Volker Roth, Joachim M. Buhmann

Abstract: Clustering aims at extracting hidden structure in dataset. While the problem of ﬁnding compact clusters has been widely studied in the literature, extracting arbitrarily formed elongated structures is considered a much harder problem. In this paper we present a novel clustering algorithm which tackles the problem by a two step procedure: ﬁrst the data are transformed in such a way that elongated structures become compact ones. In a second step, these new objects are clustered by optimizing a compactness-based criterion. The advantages of the method over related approaches are threefold: (i) robustness properties of compactness-based criteria naturally transfer to the problem of extracting elongated structures, leading to a model which is highly robust against outlier objects; (ii) the transformed distances induce a Mercer kernel which allows us to formulate a polynomial approximation scheme to the generally N Phard clustering problem; (iii) the new method does not contain free kernel parameters in contrast to methods like spectral clustering or mean-shift clustering. 1

6 0.0755715 107 nips-2003-Learning Spectral Clustering

7 0.063060135 126 nips-2003-Measure Based Regularization

8 0.050748724 120 nips-2003-Locality Preserving Projections

9 0.046893742 160 nips-2003-Prediction on Spike Data Using Kernel Algorithms

10 0.046238139 149 nips-2003-Optimal Manifold Representation of Data: An Information Theoretic Approach

11 0.042429823 121 nips-2003-Log-Linear Models for Label Ranking

12 0.041960169 179 nips-2003-Sparse Representation and Its Applications in Blind Source Separation

13 0.040013477 50 nips-2003-Denoising and Untangling Graphs Using Degree Priors

14 0.0391412 30 nips-2003-Approximability of Probability Distributions

15 0.038878284 70 nips-2003-Fast Algorithms for Large-State-Space HMMs with Applications to Web Usage Analysis

16 0.036783721 73 nips-2003-Feature Selection in Clustering Problems

17 0.03390795 168 nips-2003-Salient Boundary Detection using Ratio Contour

18 0.033401206 138 nips-2003-Non-linear CCA and PCA by Alignment of Local Models

19 0.032282446 85 nips-2003-Human and Ideal Observers for Detecting Image Curves

20 0.03217908 136 nips-2003-New Algorithms for Efficient High Dimensional Non-parametric Classification

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.123), (1, -0.075), (2, -0.019), (3, 0.047), (4, -0.066), (5, 0.086), (6, -0.06), (7, 0.017), (8, 0.073), (9, -0.124), (10, 0.1), (11, -0.033), (12, 0.118), (13, -0.067), (14, -0.017), (15, -0.054), (16, 0.007), (17, 0.003), (18, -0.022), (19, 0.069), (20, 0.042), (21, -0.121), (22, 0.011), (23, -0.069), (24, -0.097), (25, -0.094), (26, -0.133), (27, 0.013), (28, 0.219), (29, 0.158), (30, -0.034), (31, -0.029), (32, -0.075), (33, 0.026), (34, -0.084), (35, 0.018), (36, 0.037), (37, -0.053), (38, 0.034), (39, 0.114), (40, 0.117), (41, -0.07), (42, 0.067), (43, -0.119), (44, -0.08), (45, -0.017), (46, 0.152), (47, -0.007), (48, -0.025), (49, 0.118)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.95375347 71 nips-2003-Fast Embedding of Sparse Similarity Graphs

Author: John C. Platt

2 0.67151773 150 nips-2003-Out-of-Sample Extensions for LLE, Isomap, MDS, Eigenmaps, and Spectral Clustering

Author: Yoshua Bengio, Jean-françcois Paiement, Pascal Vincent, Olivier Delalleau, Nicolas L. Roux, Marie Ouimet

3 0.64543867 108 nips-2003-Learning a Distance Metric from Relative Comparisons

Author: Matthew Schultz, Thorsten Joachims

4 0.52762884 128 nips-2003-Minimax Embeddings

Author: Matthew Brand

5 0.3890186 46 nips-2003-Clustering with the Connectivity Kernel

Author: Bernd Fischer, Volker Roth, Joachim M. Buhmann

6 0.38771573 120 nips-2003-Locality Preserving Projections

7 0.36580825 126 nips-2003-Measure Based Regularization

8 0.35839409 107 nips-2003-Learning Spectral Clustering

9 0.27562124 168 nips-2003-Salient Boundary Detection using Ratio Contour

10 0.2660796 70 nips-2003-Fast Algorithms for Large-State-Space HMMs with Applications to Web Usage Analysis

11 0.26227826 30 nips-2003-Approximability of Probability Distributions

12 0.24982768 179 nips-2003-Sparse Representation and Its Applications in Blind Source Separation

13 0.2492898 83 nips-2003-Hierarchical Topic Models and the Nested Chinese Restaurant Process

14 0.22942889 118 nips-2003-Link Prediction in Relational Data

15 0.22121964 99 nips-2003-Kernels for Structured Natural Language Data

16 0.21837309 178 nips-2003-Sparse Greedy Minimax Probability Machine Classification

17 0.21717851 22 nips-2003-An Improved Scheme for Detection and Labelling in Johansson Displays

18 0.20158178 117 nips-2003-Linear Response for Approximate Inference

19 0.19567823 85 nips-2003-Human and Ideal Observers for Detecting Image Curves

20 0.19048443 152 nips-2003-Pairwise Clustering and Graphical Models

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.031), (11, 0.025), (30, 0.506), (35, 0.036), (53, 0.066), (69, 0.013), (71, 0.054), (76, 0.046), (78, 0.023), (85, 0.04), (91, 0.06)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.95458174 157 nips-2003-Plasticity Kernels and Temporal Statistics

Author: Peter Dayan, Michael Häusser, Michael London

Abstract: Computational mysteries surround the kernels relating the magnitude and sign of changes in efficacy as a function of the time difference between pre- and post-synaptic activity at a synapse. One important idea34 is that kernels result from filtering, ie an attempt by synapses to eliminate noise corrupting learning. This idea has hitherto been applied to trace learning rules; we apply it to experimentally-defined kernels, using it to reverse-engineer assumed signal statistics. We also extend it to consider the additional goal for filtering of weighting learning according to statistical surprise, as in the Z-score transform. This provides a fresh view of observed kernels and can lead to different, and more natural, signal statistics.

2 0.90064418 62 nips-2003-Envelope-based Planning in Relational MDPs

Author: Natalia H. Gardiol, Leslie P. Kaelbling

Abstract: A mobile robot acting in the world is faced with a large amount of sensory data and uncertainty in its action outcomes. Indeed, almost all interesting sequential decision-making domains involve large state spaces and large, stochastic action sets. We investigate a way to act intelligently as quickly as possible in domains where ﬁnding a complete policy would take a hopelessly long time. This approach, Relational Envelopebased Planning (REBP) tackles large, noisy problems along two axes. First, describing a domain as a relational MDP (instead of as an atomic or propositionally-factored MDP) allows problem structure and dynamics to be captured compactly with a small set of probabilistic, relational rules. Second, an envelope-based approach to planning lets an agent begin acting quickly within a restricted part of the full state space and to judiciously expand its envelope as resources permit. 1

same-paper 3 0.87506342 71 nips-2003-Fast Embedding of Sparse Similarity Graphs

Author: John C. Platt

4 0.85528141 144 nips-2003-One Microphone Blind Dereverberation Based on Quasi-periodicity of Speech Signals

Author: Tomohiro Nakatani, Masato Miyoshi, Keisuke Kinoshita

Abstract: Speech dereverberation is desirable with a view to achieving, for example, robust speech recognition in the real world. However, it is still a challenging problem, especially when using a single microphone. Although blind equalization techniques have been exploited, they cannot deal with speech signals appropriately because their assumptions are not satisﬁed by speech signals. We propose a new dereverberation principle based on an inherent property of speech signals, namely quasi-periodicity. The present methods learn the dereverberation ﬁlter from a lot of speech data with no prior knowledge of the data, and can achieve high quality speech dereverberation especially when the reverberation time is long. 1

5 0.4993394 34 nips-2003-Approximate Policy Iteration with a Policy Language Bias

Author: Alan Fern, Sungwook Yoon, Robert Givan

Abstract: We explore approximate policy iteration, replacing the usual costfunction learning step with a learning step in policy space. We give policy-language biases that enable solution of very large relational Markov decision processes (MDPs) that no previous technique can solve. In particular, we induce high-quality domain-speciﬁc planners for classical planning domains (both deterministic and stochastic variants) by solving such domains as extremely large MDPs. 1

6 0.49002415 162 nips-2003-Probabilistic Inference of Speech Signals from Phaseless Spectrograms

7 0.40799281 5 nips-2003-A Classification-based Cocktail-party Processor

8 0.37943864 15 nips-2003-A Probabilistic Model of Auditory Space Representation in the Barn Owl

9 0.37777767 159 nips-2003-Predicting Speech Intelligibility from a Population of Neurons

10 0.35987535 20 nips-2003-All learning is Local: Multi-agent Learning in Global Reward Games

11 0.34756252 50 nips-2003-Denoising and Untangling Graphs Using Degree Priors

12 0.33749664 128 nips-2003-Minimax Embeddings

13 0.33344311 184 nips-2003-The Diffusion-Limited Biochemical Signal-Relay Channel

14 0.32573715 27 nips-2003-Analytical Solution of Spike-timing Dependent Plasticity Based on Synaptic Biophysics

15 0.32373488 115 nips-2003-Linear Dependent Dimensionality Reduction

16 0.3204838 119 nips-2003-Local Phase Coherence and the Perception of Blur

17 0.31614196 76 nips-2003-GPPS: A Gaussian Process Positioning System for Cellular Networks

18 0.31323689 80 nips-2003-Generalised Propagation for Fast Fourier Transforms with Partial or Missing Data

19 0.31268397 116 nips-2003-Linear Program Approximations for Factored Continuous-State Markov Decision Processes

20 0.31217945 123 nips-2003-Markov Models for Automated ECG Interval Analysis