Learning eigenfunctions links spectral embedding and kernel PCA
Learning eigenfunctions links spectral embedding and kernel PCA
复制标题
DOI：
10.1162/0899766041732396
复制
发表时间：
2004-10-01
影响因子：
2.9
通讯作者：
Ouimet, M
中科院分区：
文献类型：
--
作者：
Bengio, Y;Delalleau, O;Ouimet, M
在这封信中，我们展示了谱嵌入方法和核主成分分析之间的直接关系，以及两者如何成为更一般的学习问题的特殊情况：学习从核和未知数据生成密度定义的算子的主特征函数。虽然谱嵌入方法仅提供训练点的坐标，但分析证明了对样本外示例（Nystrom 公式）的简单扩展，用于多维缩放 (MDS)、谱聚类、拉普拉斯特征图、局部线性嵌入 (LLE) 和 Isomap。该分析为所有此类谱嵌入方法提供了损失函数的定义，其经验平均值通过传统算法最小化。该损失的渐近期望值定义了泛化性能，并阐明了这些算法试图学习的内容。 LLE、Isomap、谱聚类和 MDS 的实验表明，这种样本外嵌入公式具有良好的泛化性，其误差水平与训练集的小扰动对嵌入的影响相当。
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 Nystrom 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.