流形学习

维数约简 解决办法：选取尽可能多的, 可能有用的特征, 然后根据需要进行特征约简. 增加特征数 增加信息量 提高准确性 维数灾难 增加训练分类器的难度 维数灾难 解决办法：选取尽可能多的, 可能有用的特征, 然后根据需要进行特征约简.

特征约简 特征选择 特征约简 特征抽取 试验数据分析，数据可视化（通常为2维或3维）等也需要维数约简 依据某一标准选择性质最突出的特征 经已有特征的某种变换获取约简特征 特征抽取 试验数据分析，数据可视化（通常为2维或3维）等也需要维数约简 中国科学院自动化研究所

Outline 线性维数约简方法 流形和维数约简 几种流形学习算法简介：LLE, Isomap, Laplacian Eigenmap 流形学习问题的简单探讨 中国科学院自动化研究所

线性约简方法 通过特征的线性组合来降维. 本质上是把数据投影到低维线性子空间. 线性方法相对比较简单且容易计算. 两种经典且广泛使用的线性变换的方法: 主成分分析 (PCA); 多重判别分析 (MDA).

主成分分析 ( PCA ) PCA的目的：寻找能够表示采样数据的最好的投影子空间. Principal component

主成分分析 PCA对于椭球状分布的样本集有很好的效果, 学习所得的主方向就是椭球的主轴方向.

线性判别分析(LDA) LDA是一种监督的维数约简方法. LDA的思想: 寻找最能把两类样本分开的投影直线. Best projection direction for classification

线性判别分析(LDA) LDA的求解: 经过推导把原问题转化为关于样本集总类内散布矩阵和总类间散布矩阵的广义特征值问题.

多重判别分析(MDA) MDA把LDA推广到多类的情况. 对于c-类问题, MDA把样本投影到 c-1 维子空间.

线性方法的缺点 线性方法对于很多数据不能进行有效的处理. 现实中数据的有用特性往往不是特征的线性组合.

流形学习和维数约简 流形是线性子空间的一种非线性推广. 流形是一个局部可坐标化的拓扑空间. 流形学习是一种非线性的维数约简方法.

流形学习的可行性 1 许多高维采样数据都是由少数几个隐含变量所决定的, 如人脸采样由光线亮度, 人离相机的距离, 人的头部姿势, 人的脸部肌肉等因素决定. 2 从认知心理学的角度, 心理学家认为人的认知过程是基于认知流形和拓扑连续性的.

流形学习问题 设 是一个低维流形, 是一个光滑嵌入,其中 D>d . 数据集 是随机生成的, 且经过 f 映射为观察空间的数据, 流形学习就是在给定观察样本集 的条件下重构 f 和 .

几种流形学习算法 局部线性嵌入(LLE). S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, vol. 290, pp. 2323--2326, 2000. 等距映射(Isomap). J.B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, vol. 290, pp. 2319--2323, 2000. 拉普拉斯特征映射(Laplacian Eigenmap). M. Belkin, P. Niyogi, Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation, Vol. 15, Issue 6, pp. 1373 –1396, 2003 .

局部线性嵌入 (LLE) 前提假设：采样数据所在的低维流形在局部是线性的,即每个采样点可以用它的近邻点线性表示. 学习目标：在低维空间中保持每个邻域中的权值不变, 即假设嵌入映射在局部是线性的条件下, 最小化重构误差. 求解方法：特征值分解.

LLE算法 1 计算每一个点 的近邻点, 一般采用K 近邻或者 邻域. 3 保持权值 不变, 求 在低维空间的象 , 使得低维重构误差最小.

LLE算法示意图

LLE算法的求解 1 计算每一个点 的近邻点. 2 对于点 和它的近邻点的权值 , 1 计算每一个点 的近邻点. 2 对于点 和它的近邻点的权值 , 3 令 , 低维嵌入是 M 的最小的第 2到第 d＋1 个特征向量.

LLE算法的例子(1)

LLE算法的例子(2)

LLE算法的优点 LLE算法可以学习任意维的局部线性的低维流形. LLE算法中的待定参数很少, K 和 d.

LLE算法的缺点 LLE算法要求所学习的流形只能是不闭合的且在局部是线性的. LLE算法要求样本在流形上是稠密采样的. LLE算法中的参数 K, d 有过多的选择. LLE算法对样本中的噪音很敏感.

多维尺度变换(MDS) MDS 是一种非监督的维数约简方法.

MDS的准则函数

MDS的示意图

MDS的失效

等距映射(Isomap)的基本思想 建立在多维尺度变换(MDS)的基础上, 力求保持数据点的内在几何性质, 即保持两点间的测地距离.

Isomap的前提假设 1 高维数据所在的低维流形与欧氏空间的一个子集是整体等距的. 2 与数据所在的流形等距的欧氏空间的子集是一个凸集.

Isomap算法的核心 估计两点间的测地距离: 1 离得很近的点间的测地距离用欧氏距离代替. 2 离得较远的点间的测地距离用最短路径来逼近.

测地距离估计

Isomap算法 1 计算每个点的近邻点 (用K近邻或 邻域). 2 在样本集上定义一个赋权无向图 如果 和 互为近邻点, 则边的权值为 2 在样本集上定义一个赋权无向图 如果 和 互为近邻点, 则边的权值为 3 计算图中两点间的最短距离, 记所得的距离矩阵 . 4 用MDS求低维嵌入流形 , 令低维嵌入是 的第2小到第 d＋1小的特征值所对应的特征向量.

Isomap 算法的例子(1)

Isomap 算法的例子(2)

Isomap算法的特点 Isomap是非线性的, 适用于学习内部平坦的低维流形,不适于学习有较大内在曲率的流形 . Isomap算法中有两个待定参数K, d . Isomap算法计算图上两点间的最短距离, 执行起来比较慢 .

图上的拉普拉斯算子 其中 T 是对角矩阵,对角线的元素为 , 则称 L 为图 G 上的拉普拉斯算子. 设 G 是一个图, v 是它的顶点, 是v 的自由度, w(u,v)是连接顶点u,v 的边的权值,令 其中 T 是对角矩阵,对角线的元素为 , 则称 L 为图 G 上的拉普拉斯算子.

拉普拉斯特征映射(Laplacian Eigenmap) 基本思想：在高维空间中离得很近的点投影到低维空间中的象也应该离得很近. 求解方法：求解图拉普拉斯算子的广义特征值问题.

Laplacian Eigenmap 算法 1 从样本点构建一个近邻图, 图的顶点为样本点, 离得很近两点用边相连 (K近邻或 邻域). 2 给每条边赋予权值 如果第 个点和第 j 个点不相连，权值为0，否则 ; 3 计算图拉普拉斯算子的广义特征向量, 求得低维嵌入.令D为对角矩阵 L是近邻图上的拉普拉斯算子, 求解广义特征值问题 . 中国科学院自动化研究所

Laplacian Eigenmap算法的例子(1)

Laplacian Eigenmap算法例子(2) 300 most frequent words of the Brown corpus represented in the spectral domain

Laplacian Eigenmap算法例子(2) The first is exclusively infinitives of verbs, the second contains prepositions and the third mostly modal and auxiliary verbs. We see that syntactic structure is well-preserved.

Laplacian Eigenmap算法的特点 算法是局部的非线性方法. 算法与谱图理论有很紧密的联系. 算法中有两个参数 k,d. 算法通过求解稀疏矩阵的特征值问题解析地求出整体最优解. 算法使原空间中离得很近的点在低维空间也离得很近, 可以用于聚类.

有效的原因 它们都是非参数的方法, 不需要对流形的很多的参数假设. LLE, Isomap, Laplacian Eigenmap 有效的原因 它们都是非参数的方法, 不需要对流形的很多的参数假设. 它们是非线性的方法, 都基于流形的内在几何结构, 更能体现现实中数据的本质. 它们的求解简单, 都转化为求解特征值问题, 而不需要用迭代算法.

流形学习问题探讨 对嵌入映射或者低维流形作出某种特定的假设, 或者以保持高维数据的某种性质不变为目标. 将问题转化为求解优化问题. 提供有效的解法.

流形学习问题探讨 为流形学习提供更为坚实和易于接受的认知基础. 如何确定低维目标空间的维数. 当采样数据很稀疏时, 怎样进行有效的学习. 将统计学习理论引入流形学习对其泛化性能进行研究.

流形学习问题探讨 流形学习作为一种非线性降维或数据可视化的方法已经在图像处理如人脸图像,手写数字图像, 语言处理方面得了利用. 将其作为一种监督的学习方法用于模式识别, 虽然有研究者涉足, 但是目前在这方面的工作还很有限.