Laplacian Eigenmaps for Dimensionality Reduction and Data Representation Neural Computation June 2003 15 6 1373 1396 Presentation for CSE291 sp07 M Belkin1 P Niyogi2 1 University 2 University of Chicago Department of Mathematics of Chicago Departments of Computer Science and Statistics 5 10 07 M Belkin P Niyogi Laplacian eigs for dim reduction 5 10 07 CSE291 1 24 Outline 1 Introduction Motivation The Algorithm 2 Explaining The Algorithm The optimization Continuous Manifolds The Heat Kernel 3 Results The Swiss roll Syntactic structure of words M Belkin P Niyogi Laplacian eigs for dim reduction 5 10 07 CSE291 2 24 Outline 1 Introduction Motivation The Algorithm 2 Explaining The Algorithm The optimization Continuous Manifolds The Heat Kernel 3 Results The Swiss roll Syntactic structure of words M Belkin P Niyogi Laplacian eigs for dim reduction 5 10 07 CSE291 3 24 The problem In AI information retrieval and data mining we get Intrinsically Low m dimensional data lying in high N dimensional space Recovering the initial dimensionality results Smaller data sets I I Faster computations Reduce the space needed More meaningful representations much more M Belkin P Niyogi Laplacian eigs for dim reduction 5 10 07 CSE291 4 24 Non Linearity PCA MDS and their variations create linear embeddings of the data For non linear structures their linear embeddings fail IsoMAP LLE and Laplacian eigenmaps partially solve this problem The heart of these approaches is some kind of non linear method IsoMAP Adjacency Graph of Neighbor nodes edges LLE Each node is expressed by a limited number of neighbor nodes In Laplacian Eigenmaps Adjacency Graphs of Neighbor nodes edges M Belkin P Niyogi Laplacian eigs for dim reduction 5 10 07 CSE291 5 24 Outline 1 Introduction Motivation The Algorithm 2 Explaining The Algorithm The optimization Continuous Manifolds The Heat Kernel 3 Results The Swiss roll Syntactic structure of words M Belkin P Niyogi Laplacian eigs for dim reduction 5 10 07 CSE291 6 24 Step 1 Construct the Graph We construct the Adjacency Graph A putting i j edges if xi xj are close Close may mean neighborhoods xi xj 2 n nearest neighbors Combination of the above at most n nearest neighbors with xi xj 2 M Belkin P Niyogi Laplacian eigs for dim reduction 5 10 07 CSE291 7 24 Step 2 Choose the Weights The edges have weights that can be Simple minded 1 if connected 0 else Heat Kernel Wij e xi xj 2 t We note the with t we get the simple minded approach The second method includes more information in our model M Belkin P Niyogi Laplacian eigs for dim reduction 5 10 07 CSE291 8 24 Step 3 The Laplacian eigenvalues Let A be the Adjacency matrix and D the degree matrix of the graph We introduce the Laplacian matrix L A D and we solve the generalized eigenvector problem Lf Df We sort the eigenvectors according to their eigenvalues 0 0 1 2 k 1 We leave out f0 and use the first m eigenvectors for embedding in m dimensional Euclidian space xi f1 i fm i M Belkin P Niyogi Laplacian eigs for dim reduction 5 10 07 CSE291 9 24 A quick overview There are several efficient approximate techniques for finding the nearest neighbors The algorithm consists of a few local computations and one sparse eigenvalue problem It is a member of the IsoMap LLE family of algorithms As LLE and IsoMap does not give good results for non convex manifolds M Belkin P Niyogi Laplacian eigs for dim reduction 5 10 07 CSE291 10 24 Outline 1 Introduction Motivation The Algorithm 2 Explaining The Algorithm The optimization Continuous Manifolds The Heat Kernel 3 Results The Swiss roll Syntactic structure of words M Belkin P Niyogi Laplacian eigs for dim reduction 5 10 07 CSE291 11 24 Our minimization problem for 1 Dimension Let y y1 y2 yn T be our mapping We would like to minimize X yi yj 2 Wij ij under appropriate constraints P P 2 2 2 ij yi yj Wij ij yi yj 2yi yj Wij P 2 P 2 P T i yi Dii j yj Djj 2 ij yi yj Wij 2y Ly So we need to find argminy y T Ly M Belkin P Niyogi Laplacian eigs for dim reduction 5 10 07 CSE291 12 24 Our Constraints The constraint y T Dy 1 removes an arbitrary scaling factor in the embedding argminy y T Ly y T Dy 1 is exactly the generalized eigenvalue problem Ly Dy The additional constraint y T D1 0 the solution 1 with 0 0 So the final problem is argminy y t Ly y T Dy 1 y T D1 0 The general problem for m dimensions is similar and gives exactly the first m smallest eigenvalues M Belkin P Niyogi Laplacian eigs for dim reduction 5 10 07 CSE291 13 24 Sum Up So each eigenvector is a function from nodes to R in a way that close by points are assigned close by values The eigenvalue of each eigenfunction gives a measure of how close by are the values of close by points By using the first m eigenfunctions for determining our m dimensions we have our solution M Belkin P Niyogi Laplacian eigs for dim reduction 5 10 07 CSE291 14 24 Outline 1 Introduction Motivation The Algorithm 2 Explaining The Algorithm The optimization Continuous Manifolds The Heat Kernel 3 Results The Swiss roll Syntactic structure of words M Belkin P Niyogi Laplacian eigs for dim reduction 5 10 07 CSE291 15 24 Continuous Manifolds When we are using continuous spaces the Graph Laplacian becomes the Laplace Beltrami Operator More on this by Nakul And our optimization problem is finding functions f that map the R manifold points to R in a way that M 5 f x 2 is minimum Intuitively minimizing the gradient minimizes the values assigned to close by points M Belkin P Niyogi Laplacian eigs for dim reduction 5 10 07 CSE291 16 24 Heat Kernels Continuous manifolds give the idea for the Heat Kernel That is assigning weights Wij e xi xj 2 t The heat function is a solution for the Laplace Beltrami Operator and as a result by assigning the weights according to it we get better approximation of the ideal infinite points case M Belkin P Niyogi Laplacian eigs for dim reduction 5 10 07 CSE291 17 24 Outline 1 Introduction Motivation The Algorithm 2 Explaining The Algorithm The optimization Continuous Manifolds The Heat Kernel 3 Results The Swiss roll Syntactic structure of words M Belkin P Niyogi Laplacian eigs for dim reduction 5 10 07 CSE291 18 24 One more Swiss roll M Belkin P Niyogi Laplacian eigs for dim reduction 5 10 07 CSE291 19 24 Unfolding the Swiss roll the parameters t N N number of nearest neighbors t the heat kernel parameter M Belkin P Niyogi Laplacian eigs for dim reduction 5 10 07 CSE291 20 24 Outline 1 Introduction Motivation The Algorithm 2 Explaining The Algorithm The
View Full Document
Unlocking...