Deep Learning 101, Taiwan’s pioneering and highest deep learning meetup, launched on 2016/11/11 @ 83F, Taipei 101

AI是一條孤獨且充滿惶恐及未知的旅程，花俏絢麗的收費課程或活動絕非通往成功的捷徑。
衷心感謝當時來自不同單位的AI同好參與者實名分享的寶貴經驗；如欲移除資訊還請告知。
由 TonTon Huang Ph.D. 發起，及其當時任職公司(台灣雪豹科技)無償贊助場地及茶水點心。

去 YouTube 訂閱 | Facebook | 回 GitHub Pages | 到 GitHub 點星 | 網站 | 到 Hugging Face Space 按愛心

高維資料的降維演算法及視覺化 YouTube

2020/03/20 杜岳華

高維資料的降維演算法與視覺化：以 t-SNE 與 UMAP 為例

各位研究夥伴、對高維資料分析有興趣的新手朋友大家好。本次我們將深入探討高維資料處理中的兩個核心技術：降維演算法與視覺化，並特別聚焦於近年來在學術界和應用領域都非常熱門的兩種非線性降維方法：t-SNE (t-Distributed Stochastic Neighbor Embedding) 和 UMAP (Uniform Manifold Approximation and Projection)。同時，我們也會觸及這些方法與圖神經網路 (Graph Neural Network, GNN) 之間概念上的關聯。身為研究人員，我們經常面對資料維度過高的挑戰，這使得直接分析與理解資料變得異常困難 [1-3]。因此，學習如何有效地將高維資料投影到低維空間，並進行視覺化，是我們進行後續分析不可或缺的一步 [1-3].

降維 (Dimensionality Reduction) 的基礎概念

首先，什麼是降維？簡單來說，降維就是將資料從高維空間映射或轉換到低維空間的過程 [1-3]。這是一個從 \$R^D\$ 到 \$R^d\$ 的映射，其中 \$D\$ 是原始維度，而 \$d\$ 是轉換後的低維度，通常 \$d\$ 遠小於 \$D\$ [1]. 降維的主要目的是在降低資料維度的同時，盡可能地保留資料中重要的結構或資訊，例如資料點之間的距離關係、資料的聚類結構等 [2, 3]. 對於新手來說，理解降維的必要性非常關鍵：我們無法直接「看見」超過三維的資料，而降維提供了一個將複雜高維結構呈現在二維或三維空間的途徑，以便於人腦理解和視覺化分析 [2, 3].

降維演算法並沒有一套統一的標準或規範，不同的模型會採用不同的策略來實現這種映射，並選擇保留資料的特定屬性 [1-3].

根據保留的資料結構特性，降維方法大致可分為兩大類 [1-3]：

1. 線性降維 (Linear Dimensionality Reduction)：這類方法假設高維資料的重要結構可以通過線性轉換（例如投影到一個子空間）來保留。典型的線性降維演算法包括主成分分析 (PCA, Principal Component Analysis) 和線性判別分析 (LDA, Linear Discriminant Analysis) [1-3]. 線性方法相對較少 [1, 4]. PCA 尋找資料方差最大的方向進行投影，而 LDA 則在分類問題中尋找最大化類間差異、最小化類內差異的方向 [5].
2. 非線性降維 (Non-linear Dimensionality Reduction)：當資料在高維空間中呈現出複雜的非線性結構時，線性方法往往不足以捕捉其精髓。非線性降維則旨在保留這些非線性關係或資料點分佈所處的低維「流形」(Manifold) 結構 [2-4]. 近年來，非線性方法受到更多的關注 [1, 4]. 非線性降維又可細分為：
   • 保留資料整體結構 (Global Structure Preservation)：這類方法試圖在降維後的低維空間中保留資料點之間的整體距離或相對位置。多維尺度分析 (MDS, Multidimensional Scaling) 是一種例子 [1, 2, 4, 6]. 想像一個三維的 S 形資料分佈（經典的瑞士捲 Swiss Roll 資料集），保留整體結構的降維可能依然呈現出 S 形，只是維度降低了 [1, 2, 4, 6].
   • 保留資料區域性結構 (Local Structure Preservation)：這類方法更關注資料點與其近鄰點之間的關係。它不需要記住所有點之間的遠距離關係，而只需要關注每個點周圍的「鄰居是誰」[1, 2, 4, 6]. 通過學習並展開這些區域性關係，高維空間的曲面結構可以在低維空間中被「攤平」[4, 6]. 今天我們要深入探討的 t-SNE 和 UMAP 都屬於這類非線性降維方法，且特別強調保留區域性結構 [1, 2, 4, 7]. 流形學習 (Manifold Learning) 便是一類假設高維資料分佈在低維流形上並試圖學習其結構的非線性降維方法 [2-4]. 瑞士捲資料集就是用來展示流形學習如何展開這種非線性結構的經典例子 [2-5].

t-SNE (t-Distributed Stochastic Neighbor Embedding) 詳解

t-SNE 是一種強大的非線性降維演算法，尤其擅長將高維資料點之間的相似度轉換為聯合機率，並在低維空間中找到相應的嵌入，以最小化兩者之間的差異 [1, 2, 7]. 它的主要應用場景是高維資料的視覺化，特別是揭示資料的聚類結構 [1, 2, 7]. 從 MNIST 手寫數字資料集的降維結果圖中，我們可以清楚地看到不同數字類別的點在高維空間中可能混雜在一起，但在經過 t-SNE 降維到二維後，不同類別的點能有效地形成獨立的簇群，這極大地提高了資料的可視性和分類器的效能 [6, 8]. 這也說明了在深度學習興起之前，傳統機器學習模型在圖像或 NLP 任務上表現不佳，部分原因在於前期的特徵提取（廣義上也可視為一種降維）效果不夠理想 [6, 8].

t-SNE 的核心思想是 保留資料點與其鄰居之間的機率分佈 [1, 2, 7]. 這意味著它關注的是「一個資料點有多大機率是另一個資料點的鄰居」[9].

t-SNE 的前身是 SNE (Stochastic Neighbor Embedding) [1, 8]. SNE 的做法是：

1. 在高維空間中，對於每一對資料點 \$x_i\$ 和 \$x_j\$，計算它們之間的歐式距離 [1, 2, 10].
2. 將這個距離通過一個高斯分佈轉換為一個條件機率 \$p_{j|i}\$，表示在以 \$x_i\$ 為中心的高斯分佈下，\$x_j\$ 是 \$x_i\$ 鄰居的機率 [1, 2, 7, 8].
3. 對這些條件機率進行正規化，得到高維空間中表示鄰居關係的機率分佈 \$P\$ [1, 2, 7, 10]. SNE 使用正規化的高斯分佈 [10].
4. 在低維空間中隨機初始化對應的點 \$y_i\$ 和 \$y_j\$ [1, 2, 10-13].
5. 在低維空間中，同樣計算 \$y_i\$ 和 \$y_j\$ 之間的距離，並通過高斯分佈轉換為條件機率 \$q_{j|i}\$ [1, 8].
6. 目標是調整低維空間點的位置，使得高維機率分佈 \$P\$ 和低維機率分佈 \$Q\$ 盡可能相似。SNE 使用 Kullback-Leibler (KL) divergence 作為損失函數來衡量 \$P\$ 和 \$Q\$ 之間的差異，並通過梯度下降來最小化這個損失 [1, 2, 7, 9, 10]. KL divergence \$(P || Q)\$ 衡量的是從分佈 \$Q\$ 去近似分佈 \$P\$ 時所損失的資訊量，最小化 KL divergence 意味著讓 \$Q\$ 盡量「像」\$P\$ [1, 2, 7, 9, 13].

然而，SNE 存在一個嚴重的問題，稱為 crowding problem [1, 2, 7, 9, 14]. 這是因為高維空間中的距離分佈和低維空間中的距離分佈存在差異。在高維中距離稍遠的點，其機率 \$p_{j|i}\$ 由於指數衰減會非常小。當這些點被映射到低維空間時，由於維度減少，它們之間的距離差異不足以使得 \$q_{j|i}\$ 也變得同樣小，這些點很容易在低維空間中擠作一團，難以區分 [1, 2, 7, 9]. 對新手來說，想像把一個有很多點的球壓縮成一個平面，高維中分散在球表面上的點在壓平後都可能擠在中心附近，這就是 crowding problem [9].

為了解決 crowding problem，t-SNE 引入了 t 分佈 (t-distribution) 來計算低維空間的相似度 [1, 2, 7, 14]. t 分佈相較於高斯分佈，具有較「胖的尾巴」(heavy tail) [1, 2, 7, 14, 15]. 這意味著在 t 分佈下，即使兩個點在低維空間中距離較遠，它們之間的機率值仍然比高斯分佈下大 [1, 15]. 利用 t 分佈的這一特性，t-SNE 能夠有效地將高維空間中距離中等的點在低維空間中拉得更開，從而緩解擁擠問題 [1, 2, 7, 14, 15].

t-SNE 的一個重要參數是 perplexity [1, 2, 5, 7, 14-16]. Perplexity 可以被粗略地理解為每個資料點周圍的「有效鄰居數量」[5]. 它間接影響了高維空間中高斯分佈的標準差 \$S\$ [1, 2, 5, 10, 15]. 高的 perplexity 值對應較大的 \$S\$，使得每個點會考慮更多的鄰居，這可能導致降維結果呈現為一個大的、擁擠的團塊 [1, 5, 15, 16]. 低的 perplexity 值對應較小的 \$S\$，每個點只考慮很少的鄰居，這可能導致資料點分散成多個小團塊甚至碎片化 [1, 5, 15, 16]. 對新手來說，調整 perplexity 可能比較困難，需要根據資料集的大小和特性進行嘗試 [1, 5, 13-17].

在數學細節上，t-SNE 在高維空間使用正規化高斯分佈計算 \$p_{ij}\$, 在低維空間使用正規化 t 分佈計算 \$q_{ij}\$, 並使用 KL Divergence \$(P || Q)\$ 作為損失函數 [1, 2, 10, 18]. 初始化通常採用隨機初始化 [1, 2, 11-13]. 此外，t-SNE 會將非對稱的條件機率 \$p_{j|i}\$ 和 \$p_{i|j}\$ 結合成對稱的聯合機率 \$p_{ij}\$，以表示 \$i\$ 和 \$j\$ 互為鄰居的機率，從而建構一個無方向性的鄰居關係 [1, 16].

總結來說，t-SNE 是一個強大的視覺化工具，通過匹配高低維空間的鄰居機率分佈，特別有效地展示資料的局部聚類結構 [1, 2, 6, 7].

UMAP (Uniform Manifold Approximation and Projection) 詳解

UMAP 是另一種近年來非常流行的非線性降維演算法，它通常比 t-SNE 運行得更快，並且在某些情況下能更好地保留資料的整體結構 [1, 2, 18]. UMAP 的設計基於流形學習和拓撲資料分析的一些理論概念 [18, 19]. UMAP 假設高維資料均勻分佈在一個低維流形上，並希望這個流形是局部連通的 [1, 2, 18-20].

UMAP 的核心思想是 通過建構圖 (Constructing Graph) 來近似資料點在高維空間中的流形結構，並在低維空間中建立一個相似的圖，然後最小化兩個圖結構的差異 [1, 2, 10, 16, 18].

UMAP 在計算資料點之間的關係時，融合了鄰居概念和機率概念 [1, 18, 20]. 它首先使用 K-Nearest Neighbors (KNN) 的方法來確定每個點的鄰居 [1, 2, 17, 18]. K 是 UMAP 的一個重要參數，指定了每個點需要尋找多少個最近的鄰居 [2, 5, 13, 17, 18, 21].

與 t-SNE 類似，UMAP 也將距離轉換為機率來表示鄰居關係，但在高維空間的機率計算上有所不同 [1, 2, 10, 18]. UMAP 使用一個修正後的高斯分佈，它在計算點 \$i\$ 與點 \$j\$ 之間的距離時，會減去點 \$i\$ 到其最近鄰居的距離 [1, 2, 18, 20]. 這樣做的目的是 確保每個點到其最近鄰居的機率連接強度（similarity）接近 1，並從最近鄰居開始向外計算機率 [1, 18, 20, 22]. 這有助於讓資料點之間在低維空間中保持連接，符合其對流形局部連通性的假設 [1, 2, 10, 18, 20].

UMAP 將點對之間的機率結合（類似於 t-SNE 的聯合機率）時，使用了 probabilistic union 的概念，這有助於構建一個無方向性且局部連通的圖 [1, 22]. 數學上，這是基於集合的 union 運算推廣而來 [22].

在低維空間，UMAP 也使用 t 分佈來計算相似度，但與 t-SNE 不同的是，UMAP 使用的是非正規化的 t 分佈 [1, 2, 10, 18].

UMAP 使用 Binary Cross-Entropy Loss 作為損失函數來最小化高低維空間機率分佈之間的差異 [1, 2, 10, 13, 18]. 雖然損失函數不同，但從數學上看，在給定高維資料及其機率分佈 P 的情況下，最小化 Cross-Entropy Loss 實際上等價於最小化 P 與 Q 之間的 KL Divergence（僅差一個常數項，即 P 的 entropy）[1, 2, 13]. 因此，在優化目標上，兩者有著相似的核心思想，都是讓低維分佈 Q 盡量逼近高維分佈 P [1, 2, 13].

UMAP 在初始化低維空間點的位置時，採用了一種與 t-SNE 不同的策略：它使用基於 圖拉普拉斯算子 (Graph Laplacian) 的特徵向量 (Eigenvectors) 進行初始化 [2, 10, 12, 13, 18, 21]. 圖拉普拉斯算子是一種用於描述圖結構的矩陣，其特徵向量包含了圖的結構信息 [5]. 使用這些特徵向量作為初始值有兩個主要優勢：第一，它可以 幫助演算法更快地收斂，相比隨機初始化，收斂路徑更有效率 [2, 13, 18, 21]. 第二，這種初始化方式 有助於保留圖的整體結構資訊，為低維嵌入提供一個更好的全局起點，使得 UMAP 在保留資料整體連通性方面通常表現更好 [2, 10, 13, 18, 21]. UMAP 的作者在 SciPy 2018 會議上曾詳細解釋這一點 [12, 19].

UMAP 的一個關鍵參數是 K (nearest neighbor 數量) [2, 5, 13, 17, 18, 21]. 它通過 K 值來確定高維空間中高斯分佈的標準差 \$S\$ [13, 17, 21]. 相較於 t-SNE 的 perplexity，UMAP 的 K 值通常被認為更容易調整，因為 K 的意義更加直觀（即考慮多少個最近的鄰居）[2, 5, 13, 18, 21].

UMAP 的一些巧妙設計（如距離修正、Graph Laplacian 初始化）使其在處理大型資料集時通常比 t-SNE 更快，並且在保留資料整體連通性和結構方面展現出優勢 [1, 2, 10, 11, 21]. 然而，最近的研究也指出，UMAP 對於保留資料的整體結構並非完全保證，特別是如果使用隨機初始化，也可能出現資料破碎的情況，這點與使用 PCA 初始化可以改善 t-SNE 整體結構保留的效果有所呼應 [12, 23, 24].

t-SNE 與 UMAP 的比較總結

基於上述討論，我們可以對 t-SNE 和 UMAP 進行一個詳細的比較：

對於新手來說，通常建議先嘗試 UMAP，因為它速度較快且參數相對易調，且能較好地處理資料的整體結構 [2, 11, 13, 18, 21]. 如果特別需要強調資料的局部聚類結構，t-SNE 仍是一個不錯的選擇 [2, 7].

降維中的圖構建 (Graph Construction) 概念

無論是 t-SNE 還是 UMAP，在處理資料點之間的關係時，都或多或少地隱含或顯式地構建了一個「圖」(Graph) 來表示這些關係 [1, 2, 16, 18, 23, 25]. 這個圖由資料點作為「節點」(Nodes)，資料點之間的關係作為「邊」(Edges) [5]. 如何定義這些邊（即哪些點是鄰居）以及邊的強度（關係有多緊密）是圖構建的核心問題 [1, 23, 25].

構建圖的拓撲結構通常有兩種主要方法 [1, 23, 25]:

1. 離散方法 (Discrete Approach)：這種方法決定了點之間是否存在連邊（鄰居關係），關係是二元的（0 或 1）。這類方法通常用於構建稀疏圖 (sparse graph)，因為每個點只與少數點相連 [1, 23, 25]. 例子包括：
   • S-neighborhood (Radius Neighborhood)：定義一個距離半徑 \$epsilon\$，在半徑內的點互為鄰居 [1, 19, 23, 25].
   • K-Nearest Neighbor (K-NN)：對於每個點，找到離它最近的 K 個點作為其鄰居 [1, 17, 18, 23, 25]. UMAP 顯式地使用了 KNN [1, 2, 17, 18].
2. 連續方法 (Continuous Approach)：這種方法使用一個連續數值來量化點之間的關係強度（例如距離或機率），而非簡單的連接或不連接 [1, 23, 25]. 這類方法通常會構建密集圖 (dense graph)，因為原則上每個點與所有其他點都有一個關係值 [1, 23, 25]. t-SNE 和 UMAP 都將點之間的距離轉換為機率來表示鄰居關係強度，這可以視為一種連續的方法 [1, 2, 7, 10, 18, 23].

值得注意的是，無論是離散還是連續的圖構建方法，通常都需要先計算資料點之間的距離來確定鄰居或關係強度 [1, 23, 25]. 最常用的是歐式距離 [1, 2, 10].

UMAP 在其計算流程中明確包含建構圖的步驟 [1, 2, 16, 18], 而 t-SNE 雖然沒有顯式地建構一個傳統意義上的鄰接矩陣，但其基於機率分佈的鄰居關係概念，本質上也定義了一種圖結構 [1, 2, 7]. UMAP 的設計強調構建一個連通的圖，這也是它保留整體結構的一種方式 [1, 2, 10, 18].

降維與圖神經網路 (Graph Neural Network, GNN) 的關聯

理解了降維演算法如何利用「圖」的概念來處理資料點之間的關係後，我們自然會聯想到另一類近年來非常流行的模型：圖神經網路 (GNN) [1, 2, 5, 24]. GNN 是專門設計用於處理圖結構資料的神經網路模型 [5, 24].

從研究角度來看，降維方法（特別是 UMAP 這類基於圖的方法）與 GNN 在概念上存在有趣的相似性，但也存在核心差異 [1, 2, 5, 24, 26].

• 降維（透過圖）的工作流程：這類降維方法（例如 UMAP）從高維資料點的特徵向量出發 [1, 2, 24, 26]. 它首先根據這些特徵資訊（通常是通過計算距離、尋找鄰居）來自己構建一個圖，這個圖表示了資料點之間的關聯性 [1, 2, 24, 26]. 然後，這個演算法利用這個構建好的圖結構來轉換資料點的特徵，最終將其投影到低維空間 [1, 2, 24, 26]. 簡而言之，是「從特徵建構圖，再利用圖來轉換並降維特徵」[1, 2, 24, 26].
• GNN Layer 的工作流程：一個基本的 GNN 層接收兩個輸入：一個是資料點（圖的節點）的特徵向量，另一個是 一個給定的圖結構（通常是鄰接矩陣 Adjacency Matrix） [1, 2, 5, 24, 26]. GNN 層通過聚合每個節點鄰居的特徵信息，並結合自身的特徵，通過神經網路進行非線性轉換，生成該節點新的特徵表示 [1, 2, 5, 24, 26]. 這個過程是「圖是已知輸入，利用圖來轉換節點特徵」[1, 2, 5, 24, 26]. GNN 的目標不一定是降維，它可以將特徵轉換到維度不變或改變的空間 [2, 5, 26].

兩者的核心區別在於圖的來源：降維方法（如 UMAP）的特點是「自己構建圖」；而 GNN 的典型設定是「圖是給定的」[1, 2, 24, 26].

這引出了一個自然而然的問題：我們能否將降維方法（如 UMAP 或通過其他方式）從資料特徵中構建出來的圖，直接用作 GNN 的輸入 Adjacency Matrix 呢？答案是 肯定的，這是可行的 [1, 2, 5, 24, 26]. GNN 本身對其輸入圖的來源沒有嚴格限制，只要這個圖能夠合理地表達資料點之間的關聯性即可 [1, 2, 5, 24, 26]. 這種結合的可能性非常有趣，例如可以嘗試用更適合特定資料特性的圖構建方式來替代 GNN 預設的圖結構，或者利用降維方法構建的圖來為 GNN 提供更豐富的結構信息 [1, 24, 26].

總結

高維資料的降維與視覺化是資料科學與機器學習領域重要的前處理步驟 [1-3]. 非線性降維方法如 t-SNE 和 UMAP 在處理具有複雜結構的資料時展現出強大的能力，尤其在生物資訊等領域應用廣泛 [1, 2, 12, 16]. t-SNE 擅長捕捉局部簇狀結構 [1, 2, 7], 而 UMAP 則在速度和保留整體連通性方面通常更具優勢 [1, 2, 11, 18]. 這些基於「圖」概念的降維方法，與處理圖結構資料的 GNNs 在核心操作上有相似之處，都在利用點與點之間的關聯來轉換特徵 [1, 2, 5, 24]. 雖然圖的來源是兩者的主要區別，但將降維方法構建的圖用於 GNN 的輸入，也為探索更有效的圖表示學習提供了新的思路 [1, 2, 5, 24, 26]. 對於剛入門的學習者來說，掌握這兩種經典的降維方法，並理解它們與圖結構、機率分佈以及 GNN 之間的聯繫，將對理解和處理實際高維資料帶來極大的幫助 [1-3].