Learning a kernel matrix for nonlinear dimensionality reduction
Kilian Q. Weinberger, Fei Sha, Lawrence K. Saul · 2004
We investigate how to learn a kernel matrix for high dimensional data that lies on or near a low dimensional manifold. Noting that the kernel matrix implicitly maps the data into a nonlinear feature space, we show how to discover a mapping that "unfolds" the underlying manifold from which the data was sampled. The kernel matrix is constructed by maximizing the variance in feature space subject to local constraints that preserve the angles and distances between nearest neighbors. The main optimization involves an instance of semidefinite programming---a fundamentally different computation than previous algorithms for manifold learning, such as Isomap and locally linear embedding. The optimized kernels perform better than polynomial and Gaussian kernels for problems in manifold learning, but worse for problems in large margin classification. We explain these results in terms of the geometric properties of different kernels and comment on various interpretations of other manifold learning algorithms as kernel methods.
Cited by 517 works. doi:10.1145/1015330.1015345
Authors
References
- Nonlinear Dimensionality Reduction by Locally Linear Embedding
- A Global Geometric Framework for Nonlinear Dimensionality Reduction
- Principal Component Analysis
- Learning with Kernels
- Advances in kernel methods: support vector learning
- Nonlinear Component Analysis as a Kernel Eigenvalue Problem
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
- Semidefinite Programming
- A database for handwritten text recognition research