Learning a Kernel Matrix for Nonlinear Dimensionaliy Reduction学习一种非线性降维的核函数矩阵.pptVIP

Learning a Kernel Matrix for Nonlinear Dimensionality Reduction By K. Weinberger, F. Sha, and L. Saul Presented by Michael Barnathan The Problem: Data lies on or near a manifold. Lower dimensionality than overall space. Locally Euclidean. Example: data on a 2D line in R3, flat area on a sphere. Goal: Learn a kernel that will let us work in the lower-dimensional space. “Unfold” the manifold. First we need to know what it is! Its dimensionality. How it can vary. 2D manifold on a sphere. (Wikipedia) Background Assumptions: Kernel Trick Mercer’s Theorem: Continuous, Symmetric, Positive Semi-Definite Kernel Functions can be represented as dot (inner) products in a high-dimensional space (Wikipedia; implied in paper). So we replace the dot product with a kernel function. Or “Gram Matrix”, Knm = φ(xn)T * φ(xm) = k(xn, xm) Kernel provides mapping into high-dimensional space. Consequence of Cover’s theorem: Nonlinear problem then becomes linear. Example: SVMs: xiT * xj - φ(xi)T * φ(xj) = k(xi, xj). Linear Dimensionality Reduction Techniques: SVD, derived techniques (PCA, ICA, etc.) remove linear correlations. This reduces the dimensionality. Now combine these! Kernel PCA for nonlinear dimensionality reduction! Map input to a higher dimension using a kernel, then use PCA. The (More Specific) Problem: Data described by a manifold. Using kernel PCA, discover the manifold. There’s only one detail missing: How do we find the appropriate kernel? This forms the basis of the paper’s approach. It is also a motivation for the paper… Motivation: Exploits properties of the data, not just its space. Relates kernel discovery to manifold learning. With the right kernel, kernel PCA will allow us to discover the manifold. So it has implications for both fields. Another paper by the same authors focuses on applicability to manifold learning; this paper focuses on kernel learning. Unlike previous methods, this approach is unsupervised; the kernel is learned automatically. Not specific to P