非线性降维 - 维基百科，自由的百科全书

非线性降维

上级分类	机器学习、​降维

非线性降维也称作流形学习，为各种相关技术中的一种，是将高维数据投射到低维潜流形上，目的是在低维空间中实现数据可视化，或学习映射（高维到低维嵌入或反之）本身。^[1][2]下面介绍的技术可理解概括用于降维的线性分解法（如奇异值分解、主成分分析）。

考虑以矩阵（或数据库）表示的数据集，其中每行都代表描述某物特定实例的一组属性（或特征）。如果属性的数量很大，那么可行行空间的增长速度是指数级的（例如有${\displaystyle f}$个属性，每个属性均具有${\displaystyle k}$种可能的选择，则所有可能的属性为${\displaystyle k^{f}}$）。维度越大，对空间进行采样就越困难。这导致了处理高维数据的算法时间复杂性非常高。许多机器学习算法在处理高维数据时很吃力，而将数据缩降维会使算法更有效率，并能帮助机器学习算法做出更准确的预测。

人类往往难以理解高维数据。因此将数据减进行降维对于可视化非常有用。

数据的降维表示通常被称为“内蕴变量”（intrinsic variable），即它们是数据产生的价值。例如，考虑一个包含字母“A”经过缩放和旋转的图像的数据集，每张图片有32×32像素，可以表示为长度为1024的向量；每行都是1024维的空间（汉明空间（英语：Hamming_space））中，二维流形上的一个样本。由于数据仅通过缩放和旋转得到，所以内蕴维度是2；而字母“A”的形状或外观则不是内蕴变量（因为数据集中所有元素该特征均相同）。非线性降维将抛弃相关信息（字母“A”），只保留变化的信息（缩放和旋转）。右图展示了该数据集的部分样本，及通过使用非线性降维算法（Manifold Sculpting）将数据降到二维的结果散点图。

作为对比，右图使用线性降维算法PCA（主成分分析），将同样的数据集降为二维，可以发现结果并没有采用非线性降维算法好。这表明从该流形上采样得到的高维向量以一种非线性的方式变化。

非线性降维在计算机视觉领域有所应用。例如一个使用相机在封闭的静态环境中导航的机器人，相机得到的图像可以视为从高维空间流形采样得到的样本，流形的内蕴变量代表机器人的位置和朝向。

不变流形对动力系统中的模型降阶具有普遍意义。特别是，若相空间中存在吸引不变流形，附近的轨迹便会汇聚其上并停留，使其称为动力系统降维的候选流形。一般情形下不能保证存在这样的流形，不过谱子流形理论给出了一大类动力系统中存在唯一吸引不变对象的条件。^[3]非线性降维的积极研究旨在展开与动力系统相关的观测流形，以开发建模技术。^[4]

下面列举了一些非线性降维技巧。

萨蒙映射（英语：Sammon mapping）是最早也是最流行的非线性降维技术之一。

自组织映射（SOM，也称作科赫宁映射，Kohonen map）及其概率变体生成拓扑图（GTM）使用嵌入空间中的点表示，根据从嵌入空间到高位空间的非线性映射形成潜变量模型。^[6]这些技术与同样基于概率模型的密度网络相关。

核主成分分析可能是应用最广泛的降维算法。^[7]PCA首先要计算${\displaystyle m\times n}$矩阵${\displaystyle \mathbf {X} }$的协方差矩阵

${\displaystyle C={\frac {1}{m}}\sum _{i=1}^{m}{\mathbf {x} _{i}\mathbf {x} _{i}^{\mathsf {T}}}.}$

然后将数据投影到矩阵的前k个特征向量上。相比之下，KPCA首先计算数据转换到高维空间后的协方差矩阵

${\displaystyle C={\frac {1}{m}}\sum _{i=1}^{m}{\Phi (\mathbf {x} _{i})\Phi (\mathbf {x} _{i})^{\mathsf {T}}}.}$

然后将变换后的数据投影到矩阵的前k个特征向量上，这一步与PCA相同。它用核技巧将大部分计算分解，这样整个过程就可在不实际计算${\displaystyle \Phi (\mathbf {x} )}$的情况下完成。当然${\displaystyle \Phi }$必须选择已知的对应核，不幸的是为已知问题找到好的核并不容易，因此KPCA用标准核时对某些问题的处理并不理想。例如，在瑞士卷流形上便表现不佳。不过，可构造与数据相关的核矩阵，将某些在此类环境中表现良好的其他方案（如拉普拉斯特征映射、LLE）视作核PCA的特例。^[8] KPCA有内部模型，因此可用于将训练时未见的点映射到其嵌入上。

主曲线与流形给出了非线性降维的自然几何框架，并通过明确构建嵌入流形、使用流形上的标准几何投影进行编码，推广了PCA的几何解释。这种方法最早由Trevor Hastie (1984)提出，^[11]在1989年正式引入了这一方法。^[12]许多学者对这一想法进行了进一步探索。^[13] 如何定义流形的“简单性”取决于具体问题，常用流形的内蕴维度和/或光滑度来衡量。通常主流形定义为优化问题的解，目标函数如数据近似的质量和流形弯曲的一些惩罚项。常用的初始近似值由线性PCA和Kohonen SOM生成。

拉普拉斯特征映射用谱技术降维。^[14]这种技术依赖于一个基本假设：数据位于高维空间的低维流形之中。^[15]这种算法无法嵌入样本外的点，但基于再生核希尔伯特空间正则化的技术可以增加这种能力。^[16]这种技术也可用于其他非线性降维算法。

主成分分析等传统技术不考虑数据的内蕴几何。拉普拉斯特征映射根据数据集的邻域信息构造了图，数据点是图中的节点，连通性取决于邻点的距离（如用k邻近算法），生成的图可视作低维流形在高位空间中的离散近似。基于图的代价函数最小化确保流形上相近的点映射到低维空间也相近，从而保留了局部距离。流形上拉普拉斯-贝尔特拉米算子的特征函数可作为嵌入维度，因为在温和的条件下算子具有可数谱，是流形上平方可积函数的基础（与单位圆流形上的傅立叶级数比较）。拉普拉斯特征映射的理论化取得了部分成功，因为在某些非限制性假设下，随着点数趋向无穷多，已经证明图拉普拉斯矩阵收敛到拉普拉斯-贝尔特拉米算子。^[15]

等距特征映射^[17]是Floyd-Warshall算法与经典多维标度（MDS）的结合。经典MDS采用所有点之间的成对距离矩阵，计算每个点的位置；等距特征映射假设只知道相邻点之间的成对距离，并用Floyd–Warshall算法计算其他点的距离，这样就能有效估算出所有点之间的成对测地距离矩阵。然后等距特征映射用经典MDS计算所有点的降维位置。地标等距特征映射是这种算法的变体，用地标提高计算速度，但会牺牲一定精度。

流形学习中，输入数据被假定是从嵌入高维向量空间的低维流形中采样的。MVU背后的主要原理是利用流形的局部线性，在底流形的每点创建保留局部邻域的映射。

局部线性嵌入（LLE）与等距特征映射大约同时问世。^[18]与等距特征映射相比，LLE有几个优点，如利用系数矩阵算法时优化速度更快、很多问题上的结果更好等等。LLE也始于寻找每个点的最近邻点，接着为每个点计算一组权重，其能将点描述为邻点的线性组合。最后用基于特征向量的优化技术，求得点的低维嵌入，这样每个点仍用邻点的相同线性组合描述。LLE处理非均匀样本密度时往往效果不佳，因为没有固定单位防止权重漂移。LLE没有内蕴模型。

LLE根据点${\displaystyle X_{i}}$的邻域计算其重心坐标。原始点由邻点的权重矩阵${\displaystyle W_{ij}}$给出的线性组合构建，误差表为成本函数${\displaystyle E(W)}$。

${\displaystyle E(W)=\sum _{i}\left|\mathbf {X} _{i}-\sum _{j}{\mathbf {W} _{ij}\mathbf {X} _{j}}\right|^{2}}$

权重${\displaystyle W_{ij}}$指${\displaystyle X_{j}}$点在构建${\displaystyle X_{i}}$时的贡献量。成本函数的最小化有两条约束： (a) 数据点${\displaystyle X_{i}}$只从其邻点构建，因此若点${\displaystyle X_{j}}$不是${\displaystyle X_{i}}$的邻点，则${\displaystyle W_{ij}}$必为0； (b) 权重矩阵每行之和都为1。

${\displaystyle \sum _{j}{\mathbf {W} _{ij}}=1}$

原数据点是D维空间中收集的，算法的目标是将维度降低到d使${\displaystyle D>>d}$。在D维空间构建第i个数据点的权重${\displaystyle W_{ij}}$将用于在d维空间中构建同一点。基于这种想法，我们创建了一个保邻域映射：D维空间中的每点${\displaystyle X_{i}}$都映射到d维空间中的某点${\displaystyle Y_{i}}$，并使成本函数最小化：

${\displaystyle C(Y)=\sum _{i}\left|\mathbf {Y} _{i}-\sum _{j}{\mathbf {W} _{ij}\mathbf {Y} _{j}}\right|^{2}}$

这个成本函数中，权重${\displaystyle W_{ij}}$是固定的，最小化在${\displaystyle Y_{i}}$上进行以优化坐标。此最小化问题可由求解稀疏N阶特征值问题（N为数据点数量）解决，其底部d个非零特征向量提供了坐标的一组正交集。一般来说，数据点是根据欧氏距离测量的K个最近邻点构建的，这时算法只有一个自由参数K，可通过交叉验证来选择。

黑塞LLE也是基于稀疏矩阵技术，^[19]结果质量往往比LLE高得多。遗憾的是，其计算复杂度非常高，不适合样本数较多的流形。黑塞LLE没有内蕴模型。

改进局部线性嵌入（MLLE）^[20]是另一种LLE变体，在每个邻域用多重权重解决权重矩阵的局部调节。大致说，多重权重是原LLE权重的局部正交投影。MLLE的创造者也是局部切空间对齐（LTSA）的作者，认识到每个权重向量的正交投影的全局优化本质上是对齐每个数据点的局部切空间时，LTSA就蕴含于MLLE的表述中。正确应用此算法的理论与经验意义深远。^[21]

局部切空间对齐（LTSA）^[22]是基于这样一种直觉：流形正确展开时，所有切超平面都会对齐。它首先计算每个点的k个最近邻域。通过计算每个局部邻域中的前d个主成分，获得每个点的切空间。然后进行优化，找到能使切空间对齐的嵌入。

最大方差展开、等距特征映射、LLE有共同的直觉：若流形被适当展开，则各点的方差会最大化。第一步是找到每个点的最近邻点；然后最大化所有非邻点间距离，约束是邻点间距不变。此算法的主要贡献在于将问题转化为半定规划问题。然而，半定规划求解器的计算成本很高。与LLE类似，最大方差展开没有内蕴模型。

自编码器是一个前馈神经网络，其训练目标为恒等映射，即从向量映射到同一个向量。用于降维时，其部分隐藏层只包含少量神经元。此时，网络必须学会用较少的维度编码向量，并同时能将将其解码。因此，网络的前半部分（编码器，Encoder）从高维空间映射到低维空间，后半部分（解码器，Decoder）从低维空间映射到高维空间。自编码器的概念由来已久，^[23]不过深度自编码器的训练到最近才由受限玻尔兹曼机和堆叠降噪自编码器成为可能。与自编码器相关的是NeuroScale算法，其使用多维标度和萨蒙映射学习高维空间到嵌入空间的非线性映射。mappings in NeuroScale中的映射基于径向基函数网络。

高斯过程潜变量模型（GPLVM）^[24]是一种概率降维方法，用高斯过程（GPs）求高维数据的低维非线性嵌入，是PCA概率公式的推广。模型以概率方式定义，并将潜变量边缘化（marginalize），用最大似然法获得参数。与核PCA类似，用核函数形成非线性映射（高斯过程形式）。不过，GPLVM中，映射是从嵌入（潜）空间到数据空间（如密度网络与GTM），而在核PCA中，映射方向正好相反。它最初是为高维空间的可视化提出的，但已被推广为构造两观测空间中间的共享流形模型。GPLVM及其许多变体都是专为人类运动建模而提出的，如后约束GPLVM、GP动态模型（GPDM）、平衡GPDM（B-GPDM）、拓扑约束GPDM等等。为在步态分析中捕捉姿态与步态流形的耦合效应，提出了多层步态-姿态联合流形。^[25]

t分布随机邻域嵌入（t-SNE）^[26]被广泛应用。它是一种随机邻域嵌入法，计算高位空间中数据点对相关的概率，然后选择产生相似分布的低维嵌入。

关系透视映射是一种多维标度算法。算法通过模拟闭流形上的多粒子动态系统，在流形上找到数据点的构型，其中数据点被映射为粒子，间距（或差异）表为排斥力。随着流形逐渐增大，多粒子系统逐渐冷却，收敛到反映数据点距离信息的构型。

关系透视映射的灵感来自物理模型，当中带正电的粒子在球表面自由移动。在库仑力的引导下，粒子的最小能量构型将反映粒子间斥力的强度。

关系透视映射是1976年提出的。^[27] 算法最初用平面环面作为像流形，后来VisuMap软件中进行了扩展，使用球面、射影空间、克莱因瓶等其他闭流形作为像流形。

传播图使用网络上的多个传播源，将节点映射为点云。^[28]在全局级联模型中，传播速度可通过阈值参数${\displaystyle t\in [0,1]}$进行调整。对${\displaystyle t=0}$，传播图等同于等距特征映射算法。

曲线成分分析（CCA）在输出空间中寻找点的构型，尽可能保留原始距离，并关注输出空间中的小距离（与萨蒙映射相反，后者关注原空间的小距离）^[29]

注意CCA作为一种迭代学习算法，实际上是先关注大距离（与萨蒙映射类似），逐渐转向小距离。若要在两者间做出妥协，小距离信息将覆盖大距离信息。

CCA的压力函数与右Bregman散度之和有关。^[30]

CDA^[29]训练一个自组织神经网络来拟合流形，并力求在其嵌入中保留测地距离。它基于曲线成分分析（推广了萨蒙映射），但使用测地距离。

微分同胚降维或Diffeomap^[31]学习光滑的微分同胚映射，将数据转移到低维线性子空间。此方法求解光滑的时间索引向量场，这样以数据点为起点的向量场流将以低维线性子空间为终点，从而试图在正、逆映射下保留逐对差。

流形对齐利用的假设是：相似过程产生的数据集将共享相似的底流形表示。学习从原空间到共享流形的投影，可以恢复对应关系，并可将知识在领域间转移。大多数流形对齐技术只考虑两个数据集，不过遮盖奶奶可推广到任意多的初数据集。^[32]

扩散映射利用热扩散与随机游走（马尔可夫链）之间的关系；流形上的扩散算子类似于对图上的函数进行操作的马尔可夫转移矩阵，图的节点从流形中采样而来。^[33]具体说，将数据集表为${\displaystyle \mathbf {X} =[x_{1},x_{2},\ldots ,x_{n}]\in \Omega \subset \mathbf {R^{D}} }$。扩散映射的基本假设是高维数据位于${\displaystyle \mathbf {d} }$维流形上。令X表示数据集，${\displaystyle \mu }$表示X上的数据点分布，定义核代表X中点的某种相似性（affinity）。核${\displaystyle {\mathit {k}}}$具有如下性质^[34]

${\displaystyle k(x,y)=k(y,x),}$

k对称

${\displaystyle k(x,y)\geq 0\qquad \forall x,y,k}$

k是保正的

因此可将单个数据点视作图的节点，核k则定义了图上的某种亲和性（affinity）。由于核对称，图在构造上也是对称的。从这里不难看出，通过元组${\displaystyle (\mathbf {X} ,\ \mathbf {k} )}$可以构造可逆马尔可夫链。这种技术在很多领域都有应用，称作图拉普拉斯（graph Laplacian）。

例如，图${\displaystyle \mathbf {K} =(X,\ E)}$可由高斯核构造。

${\displaystyle K_{ij}={\begin{cases}e^{-\|x_{i}-x_{j}\|_{2}^{2}/\sigma ^{2}}&{\text{if }}x_{i}\sim x_{j}\\0&{\text{otherwise}}\end{cases}}}$

上式中，${\displaystyle x_{i}\sim x_{j}}$表示${\displaystyle x_{i}}$是${\displaystyle x_{j}}$的最近邻点。更严谨地说，测地距离应用来实际测量流形上的距离。由于不能获得流形的精确结构，对于最近邻点，测地距可用欧氏距离近似表示。${\displaystyle \sigma }$的选择可以调节相邻的概念：若${\displaystyle \|x_{i}-x_{j}\|_{2}\gg \sigma }$，则${\displaystyle K_{ij}=0}$；若${\displaystyle \|x_{i}-x_{j}\|_{2}\ll \sigma }$，则${\displaystyle K_{ij}=1}$。前者意味着几乎没有发生扩散，后者则意味着扩散基本完成。选择${\displaystyle \sigma }$的不同策略可参看^[35]。

要忠实表示马尔可夫矩阵，K必须被相应的度数矩阵D归一化：

${\displaystyle P=D^{-1}K.}$

现在P表示马尔可夫链。${\displaystyle P(x_{i},x_{j})}$是在一个时间步内从${\displaystyle x_{i}}$转移到${\displaystyle x_{j}}$的概率。同样，在t时间步内从${\displaystyle x_{i}}$转移到${\displaystyle x_{j}}$的概率表为${\displaystyle P^{t}(x_{i},x_{j})}$，其中${\displaystyle P^{t}}$是矩阵P的t次幂。

马尔可夫矩阵P构成了数据集X的某种局部集合概念。扩散映射与主成分分析的主要区别在于，前者只考虑数据的局部特征，而不考虑整个数据集的相关性。

K定义了数据集上的随机游走，这是说核捕捉到了数据集的某些局部几何特征。马尔可夫链定义了通过核值传播的快慢方向：游走在时间上向前传播时，局部几何信息会以与动力系统的局部变换（由微分方程定义）相同的方式聚集起来。^[34]扩散的隐喻来自族扩散距离${\displaystyle \{D_{t}\}_{t\in N}}$

${\displaystyle D_{t}^{2}(x,y)=\|p_{t}(x,\cdot )-p_{t}(y,\cdot )\|^{2}}$

对固定的t值，${\displaystyle D_{t}}$根据路径连通性定义了数据集中任意两点的距离：x和y间相连的路径越多，${\displaystyle D_{t}(x,y)}$值就越小，反之亦然。由于${\displaystyle D_{t}(x,y)}$的量设计长度为t的所有路径综合，因此${\displaystyle D_{t}}$比测地距更能抵御噪声。${\displaystyle D_{t}}$在计算距离时考虑x、y点之间的所有关系，是比欧氏距离、甚至测地距离更好的邻近度概念。

局部多维标度在局部进行多维标度，再用凸优化将所有小块拼接在一起。^[36]

非线性PCA（NLPCA）用反向传播算法训练多层感知机（MLP），使其与流形相匹配。^[37]不同于只更新权重的典型MLP，NLPCA同时会更新权重和输入：权重和输入都被视作潜值。训练后，潜输入是观测向量的低维表示，MLP从低维表示映射到高维观测空间。

数据驱动的高维缩放（DD-HDS）^[38]与萨蒙映射与曲线成分分析密切相关，不同之处在于：(1) DD-HDS会关注原空间与输出空间中的小距离，同时惩罚假邻域与撕裂；(2) DD-HDS通过距离分布调整权函数，以考虑度量集中现象。

流形雕刻（manifold sculpting）^[39]用分级优化寻找嵌入。与其他算法类似，它也会计算k个最近邻点，并试图求出能保留局部邻域关系的嵌入。流形雕刻可以缓慢地将方差从高维缩放出来，同时调整低维的点，以保留其关系。若缩放率很小，则就能找到很精确的嵌入。流形雕刻与其他算法相比，在解决部分问题时表现出更高的经验精度，还可完善其他流形学习算法的结果。不过，除非哦用非常慢的缩放速率，否则展开某些流形时会非常吃力。流形雕刻没有内蕴模型。

RankVisu^[40]设计的目的是保留邻域的秩，而非距离，因此特别适用于对保距困难的任务。事实上，邻域秩的信息量比距离小（秩可从距离中推导出来，反之则不行），因此保留邻域秩是更容易的。

拓扑约束等距嵌（TCIE）^[41]是一种基于滤去与欧氏度量不一致的测地线后近似测地距的算法。TCIE用加权最小二乘MDS获得更精确的映射，只在纠正等距特征映射用于非凸数据时产生的扭曲。TCIE算法首先检测数据中可能存在的边界点，并在计算测地距时标出不一致的测地线，以便在之后的加权压力最大化中基于较小的权重。

均匀流形近似与投影（UMAP）^[42]从外观上看与t-SNE很像，但它嘉定数据均匀分布在局部连通的黎曼流形上，且黎曼度量是局部常或近似局部常的。^[43]

基于近似矩阵的方法是指数据以相似性矩阵或距离矩阵的形式呈现给算法。这些方法都属于度量多维缩放（metric multidimensional scaling），主要差别在于如何计算近似，如等距特征映射、局部线性嵌入、最大方差展开、萨蒙映射（实际上不是映射）等等，都属于度量多维缩放。

• 流形假设
• 谱子流形
• 塔肯斯定理
• 惠特尼嵌入定理
• 生长自组织映射 (GSOM)
• 線性判別分析
• 弹性映射^[44]
• 表征学习
• 逐对距离法
• 自组织映射 (SOM)

• Murphy, Kevin P. Manifold Learning. Probabilistic Machine Learning. MIT Press. 2022: 682–699. ISBN 978-0-262-04682-4. 

• Isomap
• Generative Topographic Mapping
• Mike Tipping's Thesis （页面存档备份，存于互联网档案馆）
• Gaussian Process Latent Variable Model
• Locally Linear Embedding （页面存档备份，存于互联网档案馆）
• Relational Perspective Map （页面存档备份，存于互联网档案馆）
• Waffles （页面存档备份，存于互联网档案馆） is an open source C++ library containing implementations of LLE, Manifold Sculpting, and some other manifold learning algorithms.
• Efficient Dimensionality Reduction Toolkit homepage^{[永久失效連結]}
• DD-HDS homepage
• RankVisu homepage
• Short review of Diffusion Maps
• Nonlinear PCA by autoencoder neural networks （页面存档备份，存于互联网档案馆）