Learning Eigenfunctions Links Spectral Embedding and Kernel PCA
Yoshua Bengio, Olivier Delalleau, Nicolas Le Roux et al. · Neural Computation · 2004
In this letter, we show a direct relation between spectral embedding methods and kernel principal components analysis and how both are special cases of a more general learning problem: learning the principal eigenfunctions of an operator defined from a kernel and the unknown data-generating density. Whereas spectral embedding methods provided only coordinates for the training points, the analysis justifies a simple extension to out-of-sample examples (the Nyström formula) for multidimensional scaling (MDS), spectral clustering, Laplacian eigenmaps, locally linear embedding (LLE), and Isomap. The analysis provides, for all such spectral embedding methods, the definition of a loss function, whose empirical average is minimized by the traditional algorithms. The asymptotic expected value of that loss defines a generalization performance and clarifies what these algorithms are trying to learn. Experiments with LLE, Isomap, spectral clustering, and MDS show that this out-of-sample embedding formula generalizes well, with a level of error comparable to the effect of small perturbations of the training set on the embedding.
Cited by 345 works. doi:10.1162/0899766041732396
Authors
References
- Nonlinear Dimensionality Reduction by Locally Linear Embedding
- A Global Geometric Framework for Nonlinear Dimensionality Reduction
- Advances in kernel methods: support vector learning
- Nonlinear Component Analysis as a Kernel Eigenvalue Problem
- Spectral Graph Theory
- On Spectral Clustering: Analysis and an algorithm
- Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
- Normalized cuts and image segmentation
- Segmentation using eigenvectors: a unifying view
- Introductory functional analysis with applications