View Full Document

5 views

Unformatted text preview:

Manifold Learning ISOMAP and LLE Demonstration by Nik Melchior Comparison of methods Shamelessly stolen from Todd Wittman http www math umn edu wittman mani Hessian LLE Donoho Grimes Summary Build graph from K Nearest Neighbors Estimate tangent Hessians Compute embedding based on Hessians f X Basis null Hf x dx Basis X Predictions Specifically set up to handle non convexity Slower than LLE Laplacian Will perform poorly in sparse regions Only method with convergence guarantees Laplacian Eigenmap Belkin Nyogi Summary Build graph from K Nearest Neighbors Construct weighted adjacency matrix with Gaussian kernel Compute embedding from normalized Laplacian 2 minimize f dx subject to f 1 Predictions Assumes each point lies in the convex hull of its neighbors So it might have trouble at the boundary Will have difficulty with non uniform sampling Diffusion Map Coifman Lafon Summary 2 x y Find Gaussian kernel K x y exp Normalize kernel K x y where p x K x y P y dy Apply weighted graph Laplacian A x y K x y p x p y K x y where d x y K x y P y dy d x y Compute SVD of A Predictions Doesn t seem to infer geometry directly Need to set parameters alpha and sigma KNN Diffusion Mauro Summary Build graph from K nearest neighbors Run Diffusion Map on graph Predictions Should infer geometry better than Diffusion Map Now we have to set the parameters alpha sigma and K Manifold Geometry First let s try to unroll the Swiss Roll We should see a plane Hessian LLE is pretty slow MDS is very slow and ISOMAP is extremely slow MDS and PCA don t can t unroll Swiss Roll use no manifold information LLE and Laplacian can t handle this data Diffusion Maps could not unroll Swiss Roll for any value of Sigma Non Convexity Can we handle a data set with a hole Swiss Hole Can we still unroll the Swiss Roll when it has a hole in the middle Only Hessian LLE can handle non convexity ISOMAP LLE and Laplacian find the hole but the set is distorted Manifold Geometry Twin Peaks fold up the corners of a plane LLE



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view melchior_isomap_demo and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view melchior_isomap_demo and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?