維基百科

非線性降維

非線性降維也稱作流形學習，是各種相關技術中的一種，是將高維數據投射到低維潛流形上，目的是在低維空間中實現數據可視化，或學習映射（高維到低維嵌入或反之）本身。[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"