非線性降維

非線性降維也稱作流形學習，為各種相關技術中的一種，是將高維數據投射到低維潛流形上，目的是在低維空間中實現數據可視化，或學習映射（高維到低維嵌入或反之）本身。下面介紹的技術可理解概括用於降維的線性分解法（如奇異值分解、主成分分析）。

## 非線性降維的應用

考慮以矩陣（或資料庫）表示的數據集，其中每行都代表描述某物特定實例的一組屬性（或特徵）。如果屬性的數量很大，那麼可行行空間的增長速度是指數級的（例如有$f$個屬性，每個屬性均具有$k$種可能的選擇，則所有可能的屬性為$k^f$）。維度越大，對空間進行採樣就越困難。這導致了處理高維數據的演算法時間複雜性非常高。許多機器學習演算法在處理高維數據時很吃力，而將數據縮降維會使演算法更有效率，並能幫助機器學習演算法做出更準確的預測。

人類往往難以理解高維數據。因此將數據減進行降維對於可視化非常有用。

<image>

數據的降維表示通常被稱為「內蘊變量」（intrinsic variable），即它們是數據產生的價值。例如，考慮一個包含字母「A」經過縮放和旋轉的圖像的數據集，每張圖片有32×32像素，可以表示為長度為1024的向量；每行都是1024維的空間（漢明空間）中，二維流形上的一個樣本。由於數據僅通過縮放和旋轉得到，所以內蘊維度是2；而字母「A」的形狀或外觀則不是內蘊變量（因為數據集中所有元素該特徵均相同）。非線性降維將拋棄相關資訊（字母「A」），只保留變化的資訊（縮放和旋轉）。右圖展示了該數據集的部分樣本，及通過使用非線性降維演算法（Manifold Sculpting）將數據降到二維的結果散點圖。

<image>

作為對比，右圖使用線性降維演算法PCA（主成分分析），將同樣的數據集降為二維，可以發現結果並沒有採用非線性降維演算法好。這表明從該流形上採樣得到的高維向量以一種非線性的方式變化。

非線性降維在電腦視覺領域有所應用。例如一個使用相機在封閉的靜態環境中導航的機器人，相機得到的圖像可以視為從高維空間流形採樣得到的樣本，流形的內蘊變量代表機器人的位置和朝向。

不變流形對動力系統中的模型降階具有普遍意義。特別是，若相空間中存在吸引不變流形，附近的軌跡便會匯聚其上並停留，使其稱為動力系統降維的候選流形。一般情形下不能保證存在這樣的流形，不過譜子流形理論給出了一大類動力系統中存在唯一吸引不變對象的條件。非線性降維的積極研究旨在展開與動力系統相關的觀測流形，以開發建模技術。

下面列舉了一些非線性降維技巧。

## 重要概念

### 薩蒙映射

Q11249674是最早也是最流行的非線性降維技術之一。

<image>

### 自組織映射

自組織映射（SOM，也稱作科赫寧映射，Kohonen map）及其機率變體生成拓撲圖（GTM）使用嵌入空間中的點表示，根據從嵌入空間到高位空間的非線性映射形成潛變量模型。這些技術與同樣基於機率模型的密度網路相關。

### 核主成分分析

核主成分分析可能是應用最廣泛的降維演算法。PCA首先要計算$m \times n$矩陣$\mathbf{X}$的協方差矩陣

$$C = \frac{1}{m}\sum_{i=1}^m{\mathbf{x}_i\mathbf{x}_i^\mathsf{T}}.$$

然後將數據投影到矩陣的前k個特徵向量上。相比之下，KPCA首先計算數據轉換到高維空間後的協方差矩陣

$$C = \frac{1}{m}\sum_{i=1}^m{\Phi(\mathbf{x}_i)\Phi(\mathbf{x}_i)^\mathsf{T}}.$$

然後將變換後的數據投影到矩陣的前k個特徵向量上，這一步與PCA相同。它用核技巧將大部分計算分解，這樣整個過程就可在不實際計算$\Phi(\mathbf{x})$的情況下完成。當然$\Phi$必須選擇已知的對應核，不幸的是為已知問題找到好的核並不容易，因此KPCA用標準核時對某些問題的處理並不理想。例如，在瑞士卷流形上便表現不佳。不過，可構造與數據相關的核矩陣，將某些在此類環境中表現良好的其他方案（如拉普拉斯特徵映射、LLE）視作核PCA的特例。

KPCA有內部模型，因此可用於將訓練時未見的點映射到其嵌入上。

### 主曲線與流形

<image>

主曲線與流形給出了非線性降維的自然幾何框架，並通過明確構建嵌入流形、使用流形上的標準幾何投影進行編碼，推廣了PCA的幾何解釋。這種方法最早由Trevor Hastie (1984)提出，在1989年正式引入了這一方法。許多學者對這一想法進行了進一步探索。

如何定義流形的「簡單性」取決於具體問題，常用流形的內蘊維度和/或光滑度來衡量。通常主流形定義為優化問題的解，目標函數如數據近似的質量和流形彎曲的一些懲罰項。常用的初始近似值由線性PCA和Kohonen SOM生成。

### 拉普拉斯特徵映射

拉普拉斯特徵映射用譜技術降維。這種技術依賴於一個基本假設：數據位於高維空間的低維流形之中。這種演算法無法嵌入樣本外的點，但基於再生核希爾伯特空間正則化的技術可以增加這種能力。這種技術也可用於其他非線性降維演算法。

主成分分析等傳統技術不考慮數據的內蘊幾何。拉普拉斯特徵映射根據數據集的鄰域資訊構造了圖，數據點是圖中的節點，連通性取決於鄰點的距離（如用k鄰近演算法），生成的圖可視作低維流形在高位空間中的離散近似。基於圖的代價函數最小化確保流形上相近的點映射到低維空間也相近，從而保留了局部距離。流形上拉普拉斯-貝爾特拉米算子的特徵函數可作為嵌入維度，因為在溫和的條件下算子具有可數譜，是流形上平方可積函數的基礎（與單位圓流形上的傅立葉級數比較）。拉普拉斯特徵映射的理論化取得了部分成功，因為在某些非限制性假設下，隨著點數趨向無窮多，已經證明圖拉普拉斯矩陣收斂到拉普拉斯-貝爾特拉米算子。

### 等距特徵映射

等距特徵映射是Floyd-Warshall演算法與經典多維標度（MDS）的結合。經典MDS採用所有點之間的成對距離矩陣，計算每個點的位置；等距特徵映射假設只知道相鄰點之間的成對距離，並用Floyd–Warshall演算法計算其他點的距離，這樣就能有效估算出所有點之間的成對測地距離矩陣。然後等距特徵映射用經典MDS計算所有點的降維位置。地標等距特徵映射是這種演算法的變體，用地標提高計算速度，但會犧牲一定精度。

流形學習中，輸入數據被假定是從嵌入高維向量空間的低維流形中採樣的。MVU背後的主要原理是利用流形的局部線性，在底流形的每點創建保留局部鄰域的映射。

### 局部線性嵌入

局部線性嵌入（LLE）與等距特徵映射大約同時問世。與等距特徵映射相比，LLE有幾個優點，如利用係數矩陣演算法時優化速度更快、很多問題上的結果更好等等。LLE也始於尋找每個點的最近鄰點，接著為每個點計算一組權重，其能將點描述為鄰點的線性組合。最後用基於特徵向量的優化技術，求得點的低維嵌入，這樣每個點仍用鄰點的相同線性組合描述。LLE處理非均勻樣本密度時往往效果不佳，因為沒有固定單位防止權重漂移。LLE沒有內蘊模型。

LLE根據點$X_i$的鄰域計算其重心坐標。原始點由鄰點的權重矩陣$W_{ij}$給出的線性組合構建，誤差表為成本函數$E(W)$。

$$E(W) = \sum_i \left|\mathbf{X}_i - \sum_j {\mathbf{W}_{ij}\mathbf{X}_j}\right|^2$$

權重$W_{ij}$指$X_j$點在構建$X_i$時的貢獻量。成本函數的最小化有兩條約束：

(a) 數據點$X_i$只從其鄰點構建，因此若點$X_j$不是$X_i$的鄰點，則$W_{ij}$必為0。

(b) 權重矩陣每行之和都為1。

$$\sum_j {\mathbf{W}_{ij}} = 1$$

原數據點是D維空間中收集的，演算法的目標是將維度降低到d使$D>>d$。在D維空間構建第i個數據點的權重$W_{ij}$將用於在d維空間中構建同一點。基於這種想法，我們創建了一個保鄰域映射：D維空間中的每點$X_i$都映射到d維空間中的某點$Y_i$，並使成本函數最小化：

$$C(Y) = \sum_i \left|\mathbf{Y}_i - \sum_j {\mathbf{W}_{ij}\mathbf{Y}_j}\right|^{2}$$

這個成本函數中，權重$W_{ij}$是固定的，最小化在$Y_i$上進行以優化坐標。此最小化問題可由求解稀疏N階特徵值問題（N為數據點數量）解決，其底部d個非零特徵向量提供了坐標的一組正交集。一般來說，數據點是根據歐氏距離測量的K個最近鄰點構建的，這時演算法只有一個自由參數K，可通過交叉驗證來選擇。

#### 黑塞局部線性嵌入（Hesian LLE）

黑塞LLE也是基於稀疏矩陣技術，結果質量往往比LLE高得多。遺憾的是，其計算複雜度非常高，不適合樣本數較多的流形。黑塞LLE沒有內蘊模型。

#### 改進局部線性嵌入（MLLE）

改進局部線性嵌入（MLLE）是另一種LLE變體，在每個鄰域用多重權重解決權重矩陣的局部調節。大致說，多重權重是原LLE權重的局部正交投影。MLLE的創造者也是局部切空間對齊（LTSA）的作者，認識到每個權重向量的正交投影的全局優化本質上是對齊每個數據點的局部切空間時，LTSA就蘊含於MLLE的表述中。正確應用此演算法的理論與經驗意義深遠。

### 局部切空間對齊

局部切空間對齊（LTSA）是基於這樣一種直覺：流形正確展開時，所有切超平面都會對齊。它首先計算每個點的k個最近鄰域。通過計算每個局部鄰域中的前d個主成分，獲得每個點的切空間。然後進行優化，找到能使切空間對齊的嵌入。

### 最大方差展開

最大方差展開、等距特徵映射、LLE有共同的直覺：若流形被適當展開，則各點的方差會最大化。第一步是找到每個點的最近鄰點；然後最大化所有非鄰點間距離，約束是鄰點間距不變。此演算法的主要貢獻在於將問題轉化為半定規劃問題。然而，半定規劃求解器的計算成本很高。與LLE類似，最大方差展開沒有內蘊模型。

### 自編碼器

自編碼器是一個前饋神經網絡，其訓練目標為恆等映射，即從向量映射到同一個向量。用於降維時，其部分隱藏層只包含少量神經元。此時，網路必須學會用較少的維度編碼向量，並同時能將將其解碼。因此，網路的前半部分（編碼器，Encoder）從高維空間映射到低維空間，後半部分（解碼器，Decoder）從低維空間映射到高維空間。自編碼器的概念由來已久，不過深度自編碼器的訓練到最近才由受限玻爾茲曼機和堆疊降噪自編碼器成為可能。與自編碼器相關的是NeuroScale演算法，其使用多維標度和薩蒙映射學習高維空間到嵌入空間的非線性映射。mappings in NeuroScale中的映射基於徑向基函數網路。

### 高斯過程潛變量模型

高斯過程潛變量模型（GPLVM）是一種機率降維方法，用高斯過程（GPs）求高維數據的低維非線性嵌入，是PCA機率公式的推廣。模型以機率方式定義，並將潛變量邊緣化（marginalize），用最大似然法獲得參數。與核PCA類似，用核函數形成非線性映射（高斯過程形式）。不過，GPLVM中，映射是從嵌入（潛）空間到數據空間（如密度網路與GTM），而在核PCA中，映射方向正好相反。它最初是為高維空間的可視化提出的，但已被推廣為構造兩觀測空間中間的共享流形模型。GPLVM及其許多變體都是專為人類運動建模而提出的，如後約束GPLVM、GP動態模型（GPDM）、平衡GPDM（B-GPDM）、拓撲約束GPDM等等。為在步態分析中捕捉姿態與步態流形的耦合效應，提出了多層步態-姿態聯合流形。

### t分布隨機鄰域嵌入

t分布隨機鄰域嵌入（t-SNE）被廣泛應用。它是一種隨機鄰域嵌入法，計算高位空間中數據點對相關的機率，然後選擇產生相似分布的低維嵌入。

## 其他演算法

### 關係透視映射

關係透視映射是一種多維標度演算法。演算法通過模擬閉流形上的多粒子動態系統，在流形上找到數據點的構型，其中數據點被映射為粒子，間距（或差異）表為排斥力。隨著流形逐漸增大，多粒子系統逐漸冷卻，收斂到反映數據點距離資訊的構型。

關係透視映射的靈感來自物理模型，當中帶正電的粒子在球表面自由移動。在庫侖力的引導下，粒子的最小能量構型將反映粒子間斥力的強度。

關係透視映射是1976年提出的。

演算法最初用平面環面作為像流形，後來 VisuMap 軟體中進行了擴展，使用球面、射影空間、克萊因瓶等其他閉流形作為像流形。

### 傳播圖

傳播圖使用網路上的多個傳播源，將節點映射為點雲。在全局級聯模型中，傳播速度可通過閾值參數$t \in [0,1]$進行調整。對$t=0$，傳播圖等同於等距特徵映射演算法。

### 曲線成分分析

曲線成分分析（CCA）在輸出空間中尋找點的構型，儘可能保留原始距離，並關注輸出空間中的小距離（與薩蒙映射相反，後者關注原空間的小距離）

注意CCA作為一種迭代學習演算法，實際上是先關注大距離（與薩蒙映射類似），逐漸轉向小距離。若要在兩者間做出妥協，小距離資訊將覆蓋大距離資訊。

CCA的壓力函數與右Bregman散度之和有關。

### 曲線距離分析

CDA訓練一個自組織神經網路來擬合流形，並力求在其嵌入中保留測地距離。它基於曲線成分分析（推廣了薩蒙映射），但使用測地距離。

### 微分同胚降維

微分同胚降維或Diffeomap學習光滑的微分同胚映射，將數據轉移到低維線性子空間。此方法求解光滑的時間索引向量場，這樣以數據點為起點的向量場流將以低維線性子空間為終點，從而試圖在正、逆映射下保留逐對差。

### 流形對齊

流形對齊利用的假設是：相似過程產生的數據集將共享相似的底流形表示。學習從原空間到共享流形的投影，可以恢復對應關係，並可將知識在領域間轉移。大多數流形對齊技術只考慮兩個數據集，不過遮蓋奶奶可推廣到任意多的初數據集。

### 擴散映射

擴散映射利用熱擴散與隨機遊走（馬爾可夫鏈）之間的關係；流形上的擴散算子類似於對圖上的函數進行操作的馬爾可夫轉移矩陣，圖的節點從流形中採樣而來。具體說，將數據集表為$\mathbf{X} = [x_1,x_2,\ldots,x_n] \in \Omega \subset \mathbf {R^D}$。擴散映射的基本假設是高維數據位於$\mathbf{d}$維流形上。令X表示數據集，$\mu$表示X上的數據點分布，定義核代表X中點的某種相似性（affinity）。核$\mathit{k}$具有如下性質

$$k(x,y) = k(y,x),$$

k對稱

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

k是保正的

因此可將單個數據點視作圖的節點，核k則定義了圖上的某種親和性（affinity）。由於核對稱，圖在構造上也是對稱的。從這裡不難看出，通過元組$(\mathbf{X},\ \mathbf{k})$可以構造可逆馬爾可夫鏈。這種技術在很多領域都有應用，稱作圖拉普拉斯（graph Laplacian）。

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

$$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}$$

上式中，$x_i \sim x_j$表示$x_i$是$x_j$的最近鄰點。更嚴謹地說，測地距離應用來實際測量流形上的距離。由於不能獲得流形的精確結構，對於最近鄰點，測地距可用歐氏距離近似表示。$\sigma$的選擇可以調節相鄰的概念：若$\|x_i - x_j\|_2 \gg \sigma$，則$K_{ij} = 0$；若$\|x_i - x_j\|_2 \ll \sigma$，則$K_{ij} = 1$。前者意味著幾乎沒有發生擴散，後者則意味著擴散基本完成。選擇$\sigma$的不同策略可參看。

要忠實表示馬爾可夫矩陣，K必須被相應的度數矩陣D歸一化：

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

現在P表示馬爾可夫鏈。$P(x_i,x_j)$是在一個時間步內從$x_i$轉移到$x_j$的機率。同樣，在t時間步內從$x_i$轉移到$x_j$的機率表為$P^t (x_i,x_j)$，其中$P^t$是矩陣P的t次冪。

馬爾可夫矩陣P構成了數據集X的某種局部集合概念。擴散映射與主成分分析的主要區別在於，前者只考慮數據的局部特徵，而不考慮整個數據集的相關性。

K定義了數據集上的隨機遊走，這是說核捕捉到了數據集的某些局部幾何特徵。馬爾可夫鏈定義了通過核值傳播的快慢方向：遊走在時間上向前傳播時，局部幾何資訊會以與動力系統的局部變換（由微分方程定義）相同的方式聚集起來。擴散的隱喻來自族擴散距離$\{ D_t \}_{ t \in N}$

$$D_t^2(x,y) = \|p_t(x,\cdot) - p_t(y,\cdot)\|^2$$

對固定的t值，$D_t$根據路徑連通性定義了數據集中任意兩點的距離：x和y間相連的路徑越多，$D_t(x,y)$值就越小，反之亦然。由於$D_t(x,y)$的量設計長度為t的所有路徑綜合，因此$D_t$比測地距更能抵禦噪聲。$D_t$在計算距離時考慮x、y點之間的所有關係，是比歐氏距離、甚至測地距離更好的鄰近度概念。

### 局部多維標度

局部多維標度在局部進行多維標度，再用凸優化將所有小塊拼接在一起。

### 非線性PCA

非線性PCA（NLPCA）用反向傳播算法訓練多層感知機（MLP），使其與流形相匹配。不同於只更新權重的典型MLP，NLPCA同時會更新權重和輸入：權重和輸入都被視作潛值。訓練後，潛輸入是觀測向量的低維表示，MLP從低維表示映射到高維觀測空間。

### 數據驅動的高維縮放

數據驅動的高維縮放（DD-HDS）與薩蒙映射與曲線成分分析密切相關，不同之處在於：(1) DD-HDS會關注原空間與輸出空間中的小距離，同時懲罰假鄰域與撕裂；(2) DD-HDS通過距離分布調整權函數，以考慮度量集中現象。

### 流形雕刻

流形雕刻（manifold sculpting）用分級優化尋找嵌入。與其他演算法類似，它也會計算k個最近鄰點，並試圖求出能保留局部鄰域關係的嵌入。流形雕刻可以緩慢地將方差從高維縮放出來，同時調整低維的點，以保留其關係。若縮放率很小，則就能找到很精確的嵌入。流形雕刻與其他演算法相比，在解決部分問題時表現出更高的經驗精度，還可完善其他流形學習演算法的結果。不過，除非哦用非常慢的縮放速率，否則展開某些流形時會非常吃力。流形雕刻沒有內蘊模型。

### RankVisu

RankVisu設計的目的是保留鄰域的秩，而非距離，因此特別適用於對保距困難的任務。事實上，鄰域秩的資訊量比距離小（秩可從距離中推導出來，反之則不行），因此保留鄰域秩是更容易的。

### 拓撲約束等距嵌入

拓撲約束等距嵌（TCIE）是一種基於濾去與歐氏度量不一致的測地線後近似測地距的演算法。TCIE用加權最小二乘MDS獲得更精確的映射，只在糾正等距特徵映射用於非凸數據時產生的扭曲。TCIE演算法首先檢測數據中可能存在的邊界點，並在計算測地距時標出不一致的測地線，以便在之後的加權壓力最大化中基於較小的權重。

### 均勻流形近似與投影

均勻流形近似與投影（UMAP）從外觀上看與t-SNE很像，但它嘉定數據均勻分布在局部連通的黎曼流形上，且黎曼度量是局部常或近似局部常的。

## 基於近似矩陣的方法

基於近似矩陣的方法是指數據以相似性矩陣或距離矩陣的形式呈現給演算法。這些方法都屬於度量多維縮放（metric multidimensional scaling），主要差別在於如何計算近似，如等距特徵映射、局部線性嵌入、最大方差展開、薩蒙映射（實際上不是映射）等等，都屬於度量多維縮放。

## 外部連結

- 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