Manifold learning, the heat equation and spectral clusteringMikhail BelkinDept. of Computer Science and Engineering, Dept. of Statistics Ohio State UniversityCollaborators: Partha Niyogi, Hariharan Narayanan, JianSun, Yusu Wang, Xueyuan ZhouUbiquity of manifolds In many domains data explicitly lies on a manifold. For all sources of high-dimensional data, true dimensionality is much lower than the number of features. Much of the data is highly nonlinear. In high dimension can trust local but not global distances. Manifolds (Riemannian manifolds with a measure + noise) provide a natural mathematical language for thinking about high-dimensional data.From data to graphs to manifoldsHow to extract manifold structure from data? Construct a graph to “represent” the underlying space. Properties of the graph should reflect properties of the manifold.Learning on manifoldsSimple intuition:Good (plausible) classification function.Bad (implausible) classification function.Good functions have low “checkerboardedness”.How to measure?But remember we are dealing with data.Easy enough: graph Laplacian.Smoothness on manifolds(Note: this condition not quite strong enough for regularization, but close – more later.)Laplace operatorFundamental mathematical object. Heat, wave, Schroedingerequations. Fourier Analysis.What is Laplace operator on a circle?Laplace-Beltrami operatorLaplace-Beltrami operatorNice math, but how to compute from data? Answer: the heat equation.Laplace operatorLaplace-Beltrami operatorThe heat equation has a similar form on manifolds. However do not know distances and the heat kernel. Turns out (by careful analysis using differential geometry) thatthese issues do not affect algorithms.AlgorithmAlgorithmReconstructing eigenfunctions of Laplace-Beltrami operator from sampled data (Laplacian Eigenmaps, Belkin, Niyogi 2001).1. Construct a data-dependent weighted graph.2. Compute the bottom eigenvectors of the Laplacian matrix. Theoretical guarantees as data goes to infinite (using data-dependent t).Out-of-sample extension?Non-probabilistic data, such as meshes. Mesh K, triangle t.Belkin, Sun, Wang 07,09Mesh LaplaciansSurface S. Mesh Kε .Theorem:Can be extended to arbitrary point clouds. Idea – only need a mesh locally.Constructing data-dependent basesSome applications: Data representation/visualization. Semi-supervised learning. Isometry-invariant representations. Symmetry detection.Ovsyannikov, Sun, Guibas, 200916• In SSL, the more unlabeled data, the better results we expect• However...Less unlabeled dataMore unlabeled data“Indicator” functions of labeled points.The more unlabeled data we have, the less stable the classifier gets, and the worse the results become. Laplacian is not powerful enough (has to do with properties of Sobolevspaces). However can use iterated Laplacian. (Recent work with X. Zhou)Caution about using using Laplacian for regularizationConnections: Locally Linear Embeddings (Roweis, Saul, 2000)Connections: Locally Linear Embeddings (Roweis, Saul, 2000) Convergence to the Laplacian in the “limit”. (But the algorithm does not actually allow that).Connections: Diffusion Maps (Coifman, Lafon, 2005)Spectral clusteringSpectral clusteringSpectral clustering : continuous viewSpectral clustering and volumes of cutsFinal remarksLaplacian and the heat equation are a key bridge between data, algorithms and classical mathematics. Data analysis --- Differential Geometry --- Differential Equations ---Functional Analysis --- Numerical methods ---
View Full Document
Unlocking...