流形学习分析方法：Hessian局部线性嵌入的成果

2.4.7.1　基本思想

在前面描述的流形学习算法中，ISOMAP算法和LLE算法应用的前提是样本点均匀稠密取样，并且服从凸分布。当这些条件不满足时，比如取样样本存在孔洞的情况下，传统的ISOMAP和LLE方法就无能为力。为了处理数据采样不均匀的问题，Donoho等提出一种Hessian特征映射方法。

Hessian特征映射与拉普拉斯特征映射的理论框架非常相似，其区别在于用Hessian算子代替了拉普拉斯算子。因此，Hessian特征映射目的是找到这样一个映射，f:M→RD。其中f∈C2(M)的Hessian算子可以使用如下的局部坐标定义:

其中，m为观测流形上的一点，dm是流形M上的严格为正的概率测度，H(f)为度量流形M上函数f的平均弯曲程度，g(x)＝f(m′)是函数g:U→Rd，其中U是Rd中原点的一个邻域，m′是观测空间m的一个近邻点。

如果流形M可以表示为M＝ψ(Θ)，其中Θ是Rd中一个开连接子集，ψ是一个等度规映射ψ:Θ→RD，那么H(f)存在一个由常数函数和d维函数空间组成的d＋1维零空间。

由于Hessian特征映射是建立在Laplacian特征映射的理论框架上的映射，只是用二阶Hessian算子来代替Laplacian算子，因此，Hessian特征映射也具有计算简单等特点。但是由于涉及估计局域内的二阶Hessian算子，所以对于大样本数据，该算法应用起来很困难。

2.4.7.2　算法步骤

(1)选择近邻点

(3)估计Hessian矩阵

(4)构建二次型(www.xing528.com)

利用每一点的邻域的Hessian矩阵Hs(s＝1，…，n)构造对称矩阵H如下:

(5)计算的零空间

对H进行特征值分解，取最小的d＋1个特征值对应的特征向量u1，…，ud＋1，则H的零空间可以表示为U＝[u1，…，ud]∈Rn×d。

(6)低维嵌入

定义矩阵R＝(Rij)d×d，计算如下:

其中，J表示某个样本点的邻域。那么T＝R-1/2U就是低维嵌入结果。

2.4.7.3　算法分析

HLLE算法可以恢复出局部等距与欧氏空间中开连通子集的流形的低维嵌入。它对于数据集没有凸性的要求，例如带有“孔洞”的Swiss-roll数据集，HLLE能够很好地恢复出流形等距的生成坐标。但HLLE算法也存在一些缺点:①HLLE算法的计算复杂度较高。其中选择近邻点的计算代价是O(Dn2)，局部切空间建模的计算复杂度是O(Dk2n)，计算矩阵M的代价是O(d(d＋1)kn/2)，正交化的计算代价是O((1＋d＋d(d＋1))2kn)，构建二次型的计算复杂度是O(d(d＋1)kn/2)，计算零空间和计算低维嵌入的复杂度都是O(dn2)。从以上每一个步骤中的计算复杂度分析可以看出，算法的主要开销是选取近邻和估计Hessian矩阵；②由于算法在估计Hessian矩阵时需要计算二阶导数，所以HLLE算法对噪声比较敏感。