流形学习通常假设观察数据分布在原始高维空间中内嵌的一个非线性低维流形上,该流形的自由度对应于数据本质的内在变化模式,通过降维将数据投影到目标低维嵌入空间(embedding space),希望在目标空间中保持原始数据的一些几何属性,如样本间距离、近邻重构关系等。
流形是一般的几何对象的总称,比如各种维数的曲线曲面等;在数学上,流形被定义为一个满足局部欧几里德属性的拓扑空间。同传统降维方法一样,流形学习通过某种显式或者隐式的映射将高维空间中的数据在低维空间中重新表示;同以往方法不同的是,流形学习中对数据分布的假设即上述观察数据采样在一个潜在的流形上,或者说对于这组数据存在一个潜在的流形。
形式上,流形学习可以看作是从一组观察数据中推导其产生式模型的过程。给定一组观察数据集合,
,式中
为样本数量,
为观察数据的维数。假设这些观察数据采样自一个本质维数
的平滑流形,那么流形学习的目标可以看作是寻找一个从观察空间到低维嵌入空间的映射:
,
,以及其一对一的逆映射:
,这一映射函数应该同时保持流形数据的全局结构与局部几何关系。在很多算法中,映射函数
往往都不具有显式的表达形式,而仅仅通过隐含映射的方式给出训练数据集合的降维结果。
非线性降维(NLDR)的历史最早可以追溯到1969年提出的经典算法Sammon's Mapping。早期的非线性降维算法包括自组织映射(self-organizing maps,SOM)、主曲线(principal curve)及其扩展、自动编码神经网络(auto-encoder neural networks)和产生式拓扑映射(generative topographic maps,GTM)等。进入20世纪90年代,随着支持向量机(support vector machine,SVM)的成功广泛应用,基于核学习的降维方法逐渐兴起,如核主成分分析(ernel principal component analysis,Kernel PCA)。
2000年左右,研究者们受认知科学领域人脑感知信息方式的启发,提出了建立在数据非线性流形分布假设基础上的流形学习框架,其标志性工作为2000年发表在《Science》杂志的ISOMAP(isometric feature mapping)、LLE(locally linear embedding)。后续的代表性工作如Laplacian Eigenmaps、Hessian LLE(HLLE)、LTSA(local tangent space alignment)、Semidefinite embedding(SDE)、Conformal eigenmaps(CE)、Diffusion maps等。总的来说,这些经典算法都可以看作是将流形学习形式化为一个优化目标函数的问题,通过该目标函数来指定需要在降维过程中保持流形数据的几何特性,采用的计算方式为非参数式的、基于谱分解低维嵌入的思想。
流形学习的另一条研究主线是参数式的、基于局部模型拟合进而完成全局对齐思想的算法,代表性工作包括全局协调算法(global coordination)、流形坐标图册算法(manifold charting)、局部线性协调算法(locally linear coordination,LLC),以及协调因子分析算法(coordinated factor analysis,CFA)。此类方法的通常做法是首先在流形的局部区域利用一些子空间学习方法(如主成分分析、因子分析)建立一组局部线性模型,然后通过最优化某个目标函数,将这些来自不同局部模型的低维表示结果综合起来得到流形数据的全局统一坐标表示,从而完成非线性降维。在模型训练阶段完成之后,算法可以学习得到参数式的映射函数,从而用于对未知测试数据从高维观察空间到低维嵌入空间的投影或者反向的虚拟样本重构等任务,解决out-of-sample难题。
此外,有一类工作从流形学习的视角出发,采用线性降维方式来获得参数式投影映射函数,主要工作包括局部保持投影(locality preserving projections,LPP)、邻域保持嵌入(neighborhood preserving embedding,NPE)、局部判别嵌入(local discriminant embedding,LDE)、无监督判别投影(unsupervised discriminant projection,UDP),以及正交邻域保持投影(orthogonal neighborhood preserving projections,ONPP)等。这些算法在保持流形数据的某些局部或者全局几何属性约束下,可以在一定程度上发现隐含在数据集中的流形结构,并在人脸识别、掌纹识别等实际问题应用中得到验证。