内容纲要

这是一篇Science2000的文章,引用量高达13698,讲的是非线性维度降维的全局几何框架。我感觉前面羞涩难懂,核心的话,直接看表格就行了。另外,还可以看这篇文章:https://blog.pluskid.org/?p=533 (居然是校友出品)

处理数据时经常会面对一些降维问题,再高维特征中找到有意义的低纬度结构。在这里,我们描述了一种解决降维问题的方法,该方法使用易于测量的局部度量信息来学习数据集的基础全局几何。和传统的PCA和MDS方法不同,我们的方法能够发现非线性自由度基于复杂的自然观察,例如人手写字体或不同视角下的人脸。我们的方法能够有效的计算全局最优解,对于一个数据流形累,能确保逐渐收敛到正确的结构。

Introduction

如图所示,输入包含不同的光照条件和姿势的人脸图片,随机的循序。这些图像可以认为是高维向量中的点,其中,每个输入维度对应着一个像素点的亮度。(就是每个图对应着高维空间,然后所有这些图又组成了一个高维空间),尽管图片的维度很高,但是这些图片有意义的结构却有着较小的独立的自由度。比如,4096维度的输入空间,所有的图片坐落于一个三维流形,或者约束的表面,这可以通过两个pose变量+一个光照角度来进行参数化。我们的目标是,给定这些无序的高维输入,找到固有的数据集的自由度。
传统的方法是PCA和MDS,简单有效,能发现线性空间上的或近线性空间的真实结构。PCA是找到一个低纬度的数据嵌入能最好的保留数据的变化。传统的MDS找到嵌入,能保留内点距离,当距离为欧氏距离时,PCA和MDS等效。然而很多数据集包含非线性结构,PCA和MDS不一定适用。这些方法都fail在人脸数据上。
这里,我们描述了一个方法,结合了两者之间的主要算法特征。图3A描述了两维的“Swiss roll”的非线性挑战:两个点用测地线距离或最短路径距离测量的话,距离很大,而如果用欧式距离测量的话,却很相近。只有测地线距离真实的反映了低维的几何,如果使用PCA或MDS的话,只能看到欧氏距离结构,因此,这不能检测内部的两个维度。
file
我们基于MDS,但是保留内部的固有几何特性。难点在于估计测地线距离,仅仅给定输入空间的距离。对于最邻近的店,输入空间距离提供一个很好的估计测地线距离。对于远离的店,测地线距离可以通过相加一系列的最邻近点的shot hops,有点像寻找最短路径。

Isomap

完整的等距特征映射,或者Isomap算法包含三个步骤,如表1所示

  1. 第一步是算出哪些点是邻近点,基于距离dx(i,j),两个简单的方法:使用固定半径链接,或者寻找它的K个最邻近点。这些邻居关系通过一个图G表达,其边的权重表示邻居之间的距离。如图3B所示。
  2. 第二部是,Isomap计算最短路径,一个简单的算法如图1所示。
  3. 最后一步是应用经典的MDS,对图的距离。在d维欧几里得空间Y中构造数据嵌入,以最好地保留流形的估计固有几何。坐标向量yi用选择减少代价函数:
    file
    其中Dy表示欧氏距离矩阵,L2表示L2范数,t操作为内积,表示距离。等式1的全局最小,通过设置坐标向量yi为矩阵的top d的特征向量。

与PCA或MDS一样,当Y的维数增加时,可以根据误差的减少来估计数据的真实维数。
就像有足够的数据可以保证PCA和MDS恢复线性流形的真实结构一样,Isomap可以渐近地保证恢复严格的非线性流形的真实尺寸和几何结构。就数据集呈现这些参数的极值或偏离均匀密度的程度而言,渐近收敛通常仍然成立,但是准确估算测地距离所需的样本大小可能不切实际地大。
Isomap的全局坐标提供了一种根据其固有的非线性自由度来分析和处理高维观测值的简单方法。

file

最后修改日期: 2020年10月28日

作者

留言

作者

另外,关于流形学习,可以看看这个报告: http://www.cad.zju.edu.cn/reports/.pdf

guodong进行回复 取消回复

发布留言必须填写的电子邮件地址不会公开。