英语原文共 14 页

曲率感知流形学习

摘要：传统流形学习算法的基本假设是高维数据中隐藏的流形在全局或局部上等价于欧式几何空间。基于此假设，传统的流形学习算法将流形划分成一系列重叠的块，在局部上等价于欧式几何空间的线性子集，从而学习得到零黎曼曲率流形。在一般情况下，流形具备黎曼曲率性质，传统的流形学习恰恰忽略了这一点。本文通过改进现有算法，提出了曲率感知流形算法—CAML。该方法无需基于局部或全局假设，在局部子流形中增加流形的曲率信息，从而找到一种维数约简方法，适应于局部不符合欧式几何空间的流形结构。实验证明CAML相较于传统流形学习算法，在合成数据集的领域保留率、图像集的分类精确度方面具备一定优势。

1. 介绍

数据维数约简问题是常见机器学习问题之一，科研学者提出了许多维数约简方法。PCA，IPCA方法对具有线性结构的数据集处理效果很好，小波、傅里叶变换处理图像的结果也很好。然而这些方法皆忽略了数据的几何结构，缺乏几何上的直观解释。近年来，提出了流形理论以及其相关算法，发展形成了流形学习。现有的流形学习方法旨在找到嵌套在高维数据中能表达高维数据的几何拓扑结构的低维结构。目前，流形学习算法可大致分为两类：全局流形学习方法与局部流形学习方法。全局方法旨在保留数据全局的几何结构，著名的全局流形学习方法有：Isomap ,TCIE；局部方法旨在保持数据局部的几何结构，主要的局部流形学习方法有：LLE,LEP,LPP, LTSA, Hessian Eigemap. Isomap的主要目标是保持全部的高维数据中任意对象之间的几何结构，利用测地线距离替代欧式距离，是MDS算法的非线性拓展。LLE的主要目标是保留局部的线性结构，而LEP旨在保留数据的局部相似性。

1.1流形假设

传统的流形学习算法的基本假设是输入数据数据采样于高维欧式空间中的低维流形M。Isomap方法假设M全局上等距于变换平移后的欧式几何空间。TCLE旨在避免Isomap方法中的假设，TCIE方法假设M等距于欧式几何空间的子集。不同的局部流形学习方法保留了低维流形中不同的局部几何。LLE方法假设数据数据来源于高密度采样，局部数据之间为线性关系。LEP方法同样将领域内的数据视作采样于同一线性子空间，计算权重矩阵，采样欧式几何距离度量方法度量相邻样本之间的距离。HLLE假设M局部等价于欧式几何空间，全部数据的Hessian矩阵的平均范式暴露出null空间。LTSA方法基于局部采样PCA方法降低数据维度。因此LTSA假设局部为线性结构。PFE采用并行向量域学习低维映射，假设数据局部等距于欧式几何空间。LSML将局部流形视作线性子空间。所有上述流形学习算法假设见表1。

表1 主流流形学习算法及其假设

著者	年份	算法	流形假设
Tenenbaum et al	2000	Isomap	全局等距于欧式几何空间
Roweis et al.	2000	LLE	局部线性
Belkin et al.	2003	LEP	局部线性
Donoho et al.	2003	HLLE	局部等距欧式空间
Zhang et al.	2004	LTSA	局部线性
He et al.	2007	LPP	局部Laplacian映射
Dollar et al.	2007	LSML	局部不等距于欧式几何空间
Binbin Lin et al.	2013	PFE	局部等距于欧式几何空间

几乎所有主流流形学习算法都基于局部或全局等距于欧式几何空间的假设，然而这些假设并没有给予可靠性与有效性说明；并且没有考虑流形非等距属性与等距属性之间的差异。

1.2限制

流形学习方法已广泛应用于计算机视觉、模式识别以及机器学习领域，但仍存在一些局限和问题亟待解决。目前，主要存在的局限有以下几点：

局部线性假设：局部线性假设要求数据高密度采样以保证数据局部为线性子空间，然而实际情况中，没有足够密集的样本以保证局部线性性质。

参数敏感问题：领域数据量参数决定局部范围，由于全局等距假设，领域范围必须足够小，否则将打破局部线性的假设。

局部短路问题：如果高维数据中隐藏的低维流形复杂度高，局部欧氏距离将远小于本质空间的几何距离，造成局部短路问题。

维度预估问题：由于将高维数据的局部空间简单视作切空间，隐藏的流形空间维度无法准确预测。

由于现有流形学习算法往往基于局部或全局假设，造成上述问题，所以设计新算法消除上述假设，避免上述问题极为必要。

1.3问题描述

输入数据,，N为数据样本点个数，D为原始数据维度。假设数据隐藏低维流形M，M可视作的子流形。流形学习的主要目的是学习高维空间映射到低维流形的映射方法:

其中,，d为低维空间维度。基于局部等距假设，隐藏映射f需满足：

(2)

其中,处同一领域内。

对于一般的流形，往往满足不了局部等距条件，比如球形。本文基于M非局部等距的条件，寻找流形中隐藏的本质低维空间。现有的所有流形学习算法旨在寻找流形空间的本质低维流形M，本文的目标是无需局部等距假设，学习公式（1）中的映射函数f，以达到数据降维作用。

1. 几何背景

在此部分，通过分析流形的局部假设原理，作出局部假设的几何解释，揭露传统流形学习算法潜在的局限性。

2.1局部等距

定义在曲面M所有切平面上的内积集合称为M的黎曼度规g。在每个切平面中，黎曼度规是一个标量内积。如果流形局部等价于欧式空间，那么黎曼流形是平坦的空间。领域样本的距离等价于欧式距离，在此情况下，黎曼流形为平坦空间。

基于局部等距假设下，流形子空间M的曲率张量为0。就一般情况而言，流形子空间高度曲折，不等价于欧式空间。在这些情况下，传统的流形学习算法不能准确揭露流形子空间的本质结构。因此，通过分析基于局部等距假设的流形学习方法，发现现有的这些流形学习方法的局限，关键在于：未考虑流形子空间的M的曲率张量。

目前已有国内外学者对数据样本的内在曲率进行了研究.K.I.Kim等人提出在Laplace矩阵基础上增添曲率信息，对Laplace进行重构。目前该思想只应用于半监督式学习的回归方法。然而，非监督式流形学习尚未涉及该方法。利用Ricci流技术对相异于欧式空间的数据点进行了矫正。该方法只考虑了边的曲率信息，忽略了边与边之间的曲率信息。本文提出了一种全面的方法基于曲率感知的流形学习方法来突破上述局限。

2.2黎曼子流形

在黎曼几何中，由两种基本形式决定了子流形M的几何结构。而黎曼度规 g 可以看作是计算 M 的固有几何结构的第一种基本形式，如测地线距离、面积、体积等。第二种基本形式 ，其细节将在下面介绍，可以用来揭示与其环绕空间相关的子流形 M 的外部结构，如曲率、扭转等。利用第二中基本形式，我们能找到其环绕空间的子流形 M 曲线。对于黎曼流形而言，扭转率为零。

2.3第二个基本形式

表示D维黎曼流形，是隐藏的d维流形。任意点其环绕的切平面分成两个互交的线性子空间[17]，是黎曼流形M在p点的切平面。本文将黎曼流形视作整个空间的黎曼子流形，黎曼度规g定义在整个空间上。定义在黎曼流形上的黎曼曲率是一个四阶张量。曲率算子是由流形向量场上的二阶导数表示的，其中方向导数被定义为黎曼连接nabla;。在黎曼子流形中，黎曼曲率张量借助表示为 B (二阶张量) 的第二基本形式计算子流形，并由四阶张量表示为 (X，Y，Z, w)，其中 X、 Y 、 Z 、 W 是 M 的向量场。

在黎曼子流形中，一个主要的任务是比较 M 的 黎曼曲率和环绕空间的黎曼曲率。根据曲率的定义，定义子空间M的黎曼连接nabla;与环绕黎曼空间的黎曼链接的关系为：

Y= （3）

为了计算第二基本形式的标量值，本文构建了环绕流形空间在点P处的的局部自然坐标系。利用,为参数，利用的二阶导数，计算Hessian矩阵。因此，为计算黎曼流形曲率，我们只需计算映射f的Hessian矩阵。在下一部分，本文将给出具体的计算方法。

1. 曲率感知流形学习

本文只考虑基于局部等距假设的流形学习算法，如LLE，LE，LTSA等。曲率感知流形学习算法主要思想包含三部分，分别是：流形学习，曲率计算，曲率感知的流形学习。

3.1流形学习

在第一步中，传统的MAL算法基于环绕空间中的欧几里德度量，在每个输入点上划分局部领域。通常，有两种常用的方法,一种是选择以为中心的ε-球，然后将该球中所有点的集合视为的邻居。另一种方法是使用K近邻方法找到每个输入数据点的邻居。对于这两种方法，ε和K是对实验的尺寸减小结果高度敏感的参数。

在第二步中，传统的MAL算法旨在在每个局部片中构造权重矩阵，以表示子流形M的局部几何结构。不同的MAL算法产生不同的权重矩阵。

第三步是重建一组低维表示其中对应于。在一些标准化限制下[22],Y通过最小化误差函数得到：

（4）

其中LLE，LTSA，HLLE算法中，满足。

正如我们已经指出的那样，由于这些传统的流形学习算法的假设是嵌入的流形与欧几里德空间等距，所以任何两个邻域点之间的相似性显然会被高估。因此，我们的方法建议在流形学习上添加局部曲率信息。

3.2曲率估计

在连续流形中，如果存在锥形点，则此时的黎曼曲率趋于无穷大。 在这一点上流形会爆炸，我们称这一点为奇点。如上所述，我们在本文中涉及的子流形的黎曼曲率是嵌入映射的Hessian矩阵。 因此，基于这种方法，奇点不会出现在我们提出的方法中。 Hessian矩阵是关于所有的二阶导数的方阵，是标量值函数，也即嵌入映射的变量，它表示该函数的凹度，凸度和局部曲率。假设是参数d的多变量函数，Hessian矩阵H可表示为：

(5)

在每个领域中，我们选取一组局部正交坐标系{}。实际上，我们采用PCA方法计算局部坐标系。通过Gram-Schmidt正交方法计算相应的法向空间的法线坐标。在新的坐标系中可以表示成.为原流形空间中的样本点。

3.3曲率感知流形学习

在LTSA 中，作者在理论上分析了重建误差，并得出误差受子流形M曲率的影响很大。 如果子流形在高维环境空间中高度弯曲，则重建误差会非常高。 众所周知，准确确定局部切空间取决于几个因素：嵌入在Hessian矩阵中的曲率信息、局部采样密度和数据点的噪声水平。 因此，对于LTSA，有必要在降维期间分析子流形的曲率信息，但是目前还没有在这方面进行进一步的研究。

我们建议设计一种新的算法，通过添加曲率信息来改进传统的流形学习算法。 本文重点研究了LLE和LEP两种算法，并对这两种改进算法CA-LLE和CA-LEP进行了详细的理论分析。 对于局部结构保留方法，我们只需将子流形M划分为一组局部领域，其中是的领域。通过将原始输入数据点xi分别投影到该局部多项式向量空间，我们得到相应的投影系数，在处的局部曲率隐藏在矩阵中。

CAML算法步骤

1.输入一组数据点。 该步骤与传统流形学习算法的第一步相同。 如我们所知，对于每个i，是基于欧几里德度量的k近邻集，并且子流形M被划分为领域集。

2.本文不同于传统流形学习方法将局部领域投影到局部切平面，而是将局部领域投影到二阶多项式空间中，利用公式7获取新的局部坐标系，，在处的局部曲率隐藏在矩阵中。

3．为每个领域的权重矩阵增加曲率信息，使用局部坐标系，针对LEP算法和LLE算法，分别利用公式（6）（7）为权重矩阵中每个元素增添曲率信息。

4．重构完权重矩阵W后，使用该权重矩阵表示低维欧式空间中的样本，其中Y通过最小化损失函数得出，这一步骤同传统流形学习中的第三步。

算法1 曲率感知流形学习

输入：训练数据集,领域集合大小K

输出：

资料编号：[3570]