维基百科

非线性降维

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

左上：由螺旋带（又称瑞士卷）中的1000个点组成的3维数据集，中间有矩形孔。右上：用于生成3维数据集的原始2维数据集。左下和右下：分别使用模块化数据处理（Modular Data Processing）工具箱实现的LLE（邻近线性嵌入）和黑塞LLE，对流形进行的2维复原。

非线性降维的应用 编辑

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

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


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

 
使用线性降维算法PCA产生的二维散点图，数据分布并不那么有条理

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

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

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

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

重要概念 编辑

萨蒙映射 编辑

萨蒙映射是最早也是最流行的非线性降维技术之一。

 
1维SOM的主曲线近似图（红色方格折线，20个节点）。第一主成分表为蓝色直线。数据点为灰色圆圈。对PCA，此例中的未解释方差比是23.23%，而SOM则是6.86%。[5]

自组织映射 编辑

主条目：自组织映射

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

核主成分分析 编辑

核主成分分析可能是应用最广泛的降维算法。[7]PCA首先要计算 矩阵 的协方差矩阵

 

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

 

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

主曲线与流形 编辑

 
主曲线的应用：生活质量指数。[9]点代表联合国171个国家在4维空间中的数据，由4项指标构成：人均GDP、预期寿命、婴儿死亡率、结核病发病率。不同样式与颜色对应不同的地理位置。红色粗线是主曲线（principal curve），与数据集近似，用弹性映射法绘制。[10]

主曲线与流形给出了非线性降维的自然几何框架，并通过明确构建嵌入流形、使用流形上的标准几何投影进行编码，推广了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背后的主要原理是利用流形的局部线性，在底流形的每点创建保留局部邻域的映射。

局部线性嵌入 编辑

主条目：局部线性嵌入


自编码器 编辑

主条目：自编码器

自编码器是一个前馈神经网络，其训练目标为恒等映射，即从一个向量映射到同一个向量。用于降维时，其部分隐藏层只包含少量神经元。此时，网络必须学会用较少的维度编码向量，并同时能将将其解码。因此，网络的前半部分（编码器，Encoder）从高维空间映射到低维空间，后半部分（解码器，Decoder）从低维空间映射到高维空间。

核方法的主成分分析 编辑

主条目：核主成分分析

核主成分分析（Kernel Principal Component Analysis，KPCA）是最常用的降维算法之一。[18]PCA首先计算 矩阵 的协方差矩阵：

 

然后将数据投影到协方差矩阵的前k个特征向量上。而KPCA首先将数据变换到更高维的空间，然后计算变换后数据的的协方差矩阵：

 

然后和PCA一样，将数据投影到协方差矩阵的前k个特征向量上。该方法使用了核方法来避免大量的运算，整个过程可以在没有实际计算 的情况下执行（当然， 必须被选择）。不幸的是，为特定问题选择一个合适的核函数并不容易，在使用普通核函数时，KPCA的表现不一定好；例如在瑞士卷流形（Swiss roll manifold）上的表现不佳。有部分方法通过构造依赖于数据的核矩阵达成较好的表现（例如 Laplacian Eigenmaps），该类方法可以看作KPCA的特殊情况。[19]

KPCA有一个内部模型，因此它可以用来将不在训练集中的点映射到嵌入。



参见 编辑

引用 编辑

  1. ^ Lawrence, Neil D. A unifying probabilistic perspective for spectral dimensionality reduction: insights and new models. Journal of Machine Learning Research. 2012, 13 (May): 1609–38. Bibcode:2010arXiv1010.4830L. arXiv:1010.4830  . 
  2. ^ Lee, John A.; Verleysen, Michel. Nonlinear Dimensionality Reduction. Springer. 2007. ISBN 978-0-387-39350-6. 
  3. ^ Haller, George; Ponsioen, Sten. Nonlinear normal modes and spectral submanifolds: Existence, uniqueness and use in model reduction. Nonlinear Dynamics. 2016, 86 (3): 1493–1534. S2CID 44074026. arXiv:1602.00560  . doi:10.1007/s11071-016-2974-z. 
  4. ^ Gashler, M.; Martinez, T. Temporal Nonlinear Dimensionality Reduction (PDF). Proceedings of the International Joint Conference on Neural Networks IJCNN'11: 1959–66. 2011. 
  5. ^ The illustration is prepared using free software: Mirkes, E.M. Principal Component Analysis and Self-Organizing Maps: applet. University of Leicester. 2011. 
  6. ^ Yin, Hujun. 3. Learning Nonlinear Principal Manifolds by Self-Organising Maps. Gorban, A.N.; Kégl, B.; Wunsch, D.C.; Zinovyev, A. (编). Principal Manifolds for Data Visualization and Dimension Reduction. Lecture Notes in Computer Science and Engineering 58. Springer. 2007: 68–95. ISBN 978-3-540-73749-0. 
  7. ^ Schölkopf, B.; Smola, A.; Müller, K.-R. Nonlinear Component Analysis as a Kernel Eigenvalue Problem. Neural Computation (MIT Press). 1998, 10 (5): 1299–1319. S2CID 6674407. doi:10.1162/089976698300017467. 
  8. ^ Ham, Jihun; Lee, Daniel D.; Mika, Sebastian; Schölkopf, Bernhard. A kernel view of the dimensionality reduction of manifolds. Proceedings of the 21st International Conference on Machine Learning, Banff, Canada, 2004. doi:10.1145/1015330.1015417. 
  9. ^ Gorban, A. N.; Zinovyev, A. Principal manifolds and graphs in practice: from molecular biology to dynamical systems. International Journal of Neural Systems. 2010, 20 (3): 219–232. PMID 20556849. S2CID 2170982. arXiv:1001.1122  . doi:10.1142/S0129065710002383. 
  10. ^ A. Zinovyev, ViDaExpert - Multidimensional Data Visualization Tool Institut Curie, Paris.
  11. ^ Hastie, T. Principal Curves and Surfaces (PDF) (学位论文). Stanford Linear Accelerator Center, Stanford University. November 1984. （原始内容存档 (PDF)于2019-08-02）. 
  12. ^ Hastie, T.; Stuetzle, W. Principal Curves (PDF). Journal of the American Statistical Association. June 1989, 84 (406): 502–6. doi:10.1080/01621459.1989.10478797. 
  13. ^ Gorban, A. N.; Kégl, B.; Wunsch, D. C.; Zinovyev, A. (编). Principal Manifolds for Data Visualisation and Dimension Reduction. Lecture Notes in Computer Science and Engineering (LNCSE) 58. Springer. 2007. ISBN 978-3-540-73749-0. 
  14. ^ Belkin, Mikhail; Niyogi, Partha. Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering (PDF). Advances in Neural Information Processing Systems (MIT Press). 2001, 14: 586–691. ISBN 0-262-27173-7. OCLC 52710683. 
  15. ^ 15.0 15.1 Belkin, Mikhail. Problems of Learning on Manifolds (学位论文). Department of Mathematics, The University of Chicago. August 2003.  Matlab code for Laplacian Eigenmaps can be found in algorithms at Ohio-state.edu
  16. ^ Bengio, Yoshua; Paiement, Jean-Francois; Vincent, Pascal; Delalleau, Olivier; Le Roux, Nicolas; Ouimet, Marie. Out-of-Sample Extensions for LLE, Isomap, MDS, Eigenmaps, and Spectral Clustering (PDF). Advances in Neural Information Processing Systems 16. MIT Press. 2004. ISBN 0-262-20152-6. 
  17. ^ Tenenbaum, J B.; de Silva, V.; Langford, J.C. A Global Geometric Framework for Nonlinear Dimensionality Reduction (PDF). Science. 2000, 290 (5500): 2319–23. Bibcode:2000Sci...290.2319T. PMID 11125149. S2CID 221338160. doi:10.1126/science.290.5500.2319. 
  18. ^ B. Schölkopf, A. Smola, K.-R. Müller, Nonlinear Component Analysis as a Kernel Eigenvalue Problem. Neural Computation 10(5):1299-1319, 1998, MIT Press Cambridge, MA, USA, doi:10.1162/089976698300017467
  19. ^ Jihun Ham, Daniel D. Lee, Sebastian Mika, Bernhard Schölkopf. A kernel view of the dimensionality reduction of manifolds. Proceedings of the 21st International Conference on Machine Learning, Banff, Canada, 2004. doi:10.1145/1015330.1015417
  20. ^ ELastic MAPs. [2016-05-30]. （原始内容存档于2011-07-20）. 

外部链接 编辑

取自“https://zh.100ke.info/w/index.php?title=非线性降维&oldid=82925000”