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 杜岳華

1. 幾何深度學習的範疇與核心概念

首先，Geometric Learning (幾何深度學習) 是這個領域的直接翻譯名詞 [1-4]。它並非單指某個特定的模型，而是一個涵蓋了基於圖 (Graph) 和基於流形 (Manifold) 的深度學習方法的「架構」或「範疇」[1-4]。在討論 GDL 時，我們經常會聽到像是 Machine Learning on Graph (圖上的機器學習) 或 Machine Learning on Manifold (流形上的機器學習) 這些術語 [1, 2]。雖然廣義上 GDL 的「geometric part」主要指的是 Manifold，但在實際應用中，圖 (Graph) 常常被用來作為流形 (Manifold) 的離散近似 (Discrete Approximation) [1, 2, 5-7]。因此，圖理論 (Graph Theory) 在 GDL 中扮演著極為核心的角色 [1, 2, 5]。

2. 從圖分割問題到譜聚類：經典的圖學習模型

要理解 GDL 的基礎，我們可以從圖論中的一個經典問題——圖分割問題 (Graph Partition Problem) 開始 [1, 2, 5, 8, 9]。這個問題的目標是將圖的節點 (nodes) 分割成數個互斥的子集 [1, 2, 5, 8]。雖然任何分割方式都可以視為一個解，但通常我們會設定一些條件來定義「好的」分割，例如最小化被切割的邊的數量 (minimal cut) [1, 2, 8-10]。

然而，圖分割問題在一般情況下是一個 NP-hard 問題 [1, 2, 8, 9, 11]，這意味著在合理的時間內找到最佳解是非常困難的 [2, 8, 9]。因此，研究人員會對圖分割問題進行「鬆弛化」(Relaxation) [1, 2, 8, 9, 11]，將其轉化為一個可以在多項式時間內求解、但找到的是近似解的問題 [2, 8]。

這種鬆弛化的圖分割問題與圖聚類問題 (Graph Clustering Problem) 密切相關，進而對應到譜聚類 (Spectral Clustering) [1, 8, 11]。譜聚類是 Machine Learning on Graph 中的一個經典且重要的模型 [1, 2, 5, 8]。它的核心思想是利用圖的拉普拉斯矩陣 (Graph Laplacian) 的譜 (eigenvalues and eigenvectors) 來進行資料的降維和聚類 [1, 2, 8, 12]。

新手入門關鍵點：譜聚類流程

對於初學者來說，理解譜聚類的基本流程很有幫助 [1, 12]:

1. 建構相似度圖 (Similarity Graph): 從原始資料點出發，根據點與點之間的相似度來建構一個圖 [1, 2, 12, 13]。這一步至關重要，圖的結構直接影響後續的結果 [1, 14-17]。圖的建構方式有很多種，例如稀疏圖中的 ε-neighborhood graph 或 K-nearest neighbor graph [1, 2, 13]。邊的權重 (edge weight) 可以簡單設為二元權重 (Binary Weight) (有連線為 1，無連線為 0)，也可以使用高斯核 (Gaussian Kernel) 或高斯指數核 (GEL) 等方法計算資料點距離並正規化作為權重，距離越近權重越高，表示越相似 [1, 2, 13]. 這類加權方式也常被稱為 Metric matrix [1].
2. 計算圖拉普拉斯算子 (Graph Laplacian): 根據建構好的圖計算其圖拉普拉斯算子 [1, 2, 12, 13]。通常使用正規化的圖拉普拉斯算子，因為它與 Normalized Cut 的鬆弛問題解法直接對應 [1, 2]. 未正規化的譜聚類則對應 Ratio Cut 的鬆弛 [1, 2, 11]。
3. 特徵分解 (Eigen-decomposition): 對圖拉普拉斯算子進行特徵分解，得到特徵值和特徵向量 [1, 2, 12, 13].
4. 選取特徵向量並映射: 取出與最小的非零特徵值對應的前 K 個特徵向量 [1, 12, 13]。這些特徵向量可以被視為資料在「譜空間」(Spectral Space) 中的新表示或轉換關係 [1, 2, 12, 13]。這一步類似於主成分分析 (PCA) 的降維概念，將高維、可能非線性的資料結構映射到低維的線性空間 [1, 12].
5. 在譜空間中聚類: 在由選取特徵向量構成的譜空間中，使用傳統的聚類演算法 (例如 K-means) 對資料點進行聚類 [1, 12, 13].
6. 將結果對應回原圖: 將譜空間中的聚類結果對應回原始圖上的節點，完成圖聚類 [1, 12].

譜聚類之所以重要，是因為它揭示了圖結構如何影響數據的表示，並為後續的圖卷積神經網絡 (GCN) 奠定了數學基礎 [1, 2, 12, 16]。

3. 圖拉普拉斯算子：連接不同領域的核心

圖拉普拉斯算子 (Graph Laplacian, L) 是 GDL 中一個極為關鍵的概念 [1, 2, 12, 18]。它不僅是圖論中的一個矩陣 (定義為度矩陣 D 減去鄰接矩陣 A，即 L = D - A) [2, 12]，更在物理學和數學（特別是微分幾何）中扮演著類似的角色 [1, 2, 12, 18-21].

在物理學中，連續空間的拉普拉斯算子用於描述像熱傳導過程 (Heat Diffusion Process) 這樣的擴散現象 [1, 2, 20, 22, 23]。有趣的是，通過從牛頓冷卻定律 (Newton’s law of cooling) 出發，推導圖上的熱擴散公式，你會發現它的數學形式與圖拉普拉斯算子密切相關 [1, 22, 23]. 這表明圖拉普拉斯算子是連續空間拉普拉斯算子在離散空間 (圖) 上的自然類比，能夠捕捉圖上的擴散或平滑性質 [1, 19, 23].

在數學的微分幾何 (Differential Geometry) 中，拉普拉斯算子是在流形 (Manifold) 上定義的重要微分算子 [1, 2, 6, 18, 20, 21]. 流形是一種在局部看起來像歐幾里得空間 (Euclidean space)，但在整體上可能有複雜彎曲的幾何對象 (例如地球表面) [1, 2, 18, 21]. 在流形上一點的鄰居可以通過其切空間 (Tangent Space) 來近似為歐幾里得空間 [1, 2, 18, 21]. 微分幾何定義了流形上的導數、梯度 (Gradient)、散度 (Divergence) 和拉普拉斯算子 [1, 2, 6, 18, 21]. 正如前面提到的，圖可以視為流形的一種離散近似 [1, 2, 6, 7]。研究人員發現在圖上也可以定義類比於連續空間的微分算子，例如 Graph Gradient、Graph Divergence 和 Graph Laplacian [1, 6, 7]. Graph Gradient 可以定義為相鄰節點訊號的差異 [1, 6, 7]. Graph Divergence 則考慮邊上的訊號乘以邊權重並求和 [1, 7]. 通過組合 Graph Gradient 和 Graph Divergence，可以定義出 Graph Laplacian [1, 7].

Graph Laplacian 編碼了圖的拓撲結構資訊，其特徵值和特徵向量提供了分析圖結構和節點訊號的重要工具，例如作為圖傅立葉變換 (Graph Fourier Transform) 的基礎 [12]. 它在連接圖論、物理學和微分幾何的過程中，凸顯了圖結構所攜帶的豐富幾何訊息 [1, 2, 7, 12, 18-21, 24].

4. 圖卷積與譜聚類的聯繫

圖卷積層 (Graph Convolutional Layer) 是圖神經網絡 (GNNs) 中的核心計算單元 [1, 2]. 譜聚類建立的是從圖到譜空間的單向轉換關係 [1, 16]. 圖卷積更進一步，它在譜空間中對映射後的特徵向量乘以一個權重，這個權重可以類比於傳統卷積神經網絡中的卷積濾波器 (Filter)，然後再將結果轉換回原始圖空間 [1, 2, 16]. 這種操作結合了節點自身的特徵以及其鄰居節點的特徵，並利用圖的連接結構來聚合資訊，實現了在不規則圖結構上的「卷積」效果 [2, 12].

5. 圖作為幾何結構的重要性

為什麼要在深度學習中引入圖的概念？因為圖可以有效地建模數據點之間的複雜關係和結構 [3, 14]. 許多現實世界的數據本身就具有非網格化的結構，例如社交網絡中的用戶關係、分子結構中的原子和化學鍵、推薦系統中的用戶與物品互動 [14, 22, 25].

圖不僅是一種資料結構，它本身就可以被視為一種幾何結構 [1, 15]. 在 GNN 中，訊號或特徵 (Feature) 通常是放在節點 (Nodes) 上 [1, 16, 24]. 即使節點的特徵和數量保持不變，但如果圖的拓撲結構 (Topology) 不同 (即節點之間的連接方式不同)，計算出來的結果 (例如圖拉普拉斯的特徵值分佈) 也會不同 [1, 16, 26]. 這強烈表明，圖的連接方式對於模型結果至關重要，因為它編碼了數據空間的幾何訊息 (geometry information) [1, 15-17, 23, 26]. 你可以把圖想成是建模原始數據空間 (dataspace) 的一種方式，通過圖的拓撲結構，我們可以提取並利用這些數據空間的幾何資訊 [1, 7, 15, 17, 23].

UMAP (Uniform Manifold Approximation and Projection) 這個降維演算法也印證了圖結構的重要性 [1, 12, 20, 26]. UMAP 在其計算過程中也會先建構一個圖 (通常是 K-nearest neighbor graph)，並計算邊權重來表示相似度 [1, 12, 26]. 接著，它會利用圖結構和類似於譜分解的結果來進行初始化 (initialization) [1, 12, 26]. UMAP 的研究者認為，圖在其中扮演著骨架的角色，幫助保留數據的整體結構，而不同於僅僅記憶鄰居之間相對關係的 Neighbour Embedding 算法 (如 t-SNE)，後者可能導致整體結構失真 [1, 12, 23, 26].

6. 排列不變性問題 (Permutation Invariance Problem)

在處理圖結構數據時，一個重要的挑戰是排列不變性 (Permutation Invariance) 或等變性 (Equivariance) 問題 [1, 2, 12, 14, 15, 20, 27, 28]. 同一個圖，即使節點的排列順序不同，其拓撲結構是相同的 [1, 14, 27]. 一個理想的 Graph Learning 模型應該對輸入圖的節點順序變化不敏感 [15]. 也就是說，只要圖的拓撲結構和節點特徵不變，模型的輸出結果應該是一樣的 (儘管對應的順序可能會不同) [1, 27].

這個問題與圖同構問題 (Graph Isomorphism) 有關 [14, 15, 28]，判斷兩個圖是否同構本身也是一個 NP-hard 問題 [14, 15, 28]. 這給基於圖的深度學習模型帶來了挑戰：如何設計模型，使其在處理具有相同拓撲但節點排列不同或特徵不同的圖時，能夠產生一致或有意義的結果？通常需要設計特定的層或操作 (如基於鄰居聚合、共享權重等) 來實現這種不變性或等變性 [15].

7. 應用案例：從形狀對應到推薦系統

Geometric Deep Learning 在處理具有結構化數據的任務中展現出巨大潛力 [1, 2, 12, 19, 20, 22, 25].

一個有趣的應用案例是形狀對應問題 (Shape Correspondence Problem) [1, 2, 12, 14, 20, 28, 29]. 當同一個物體 (例如一個人) 擺出不同的姿勢時，我們可以將不同姿勢下的物體視為不同的圖或底層流形的不同表現 [1, 12, 14, 17, 30]. 在這些圖上定義節點訊號 (例如顏色或紋理) [1, 14, 17]. 目標是找到不同姿勢下同一物體上對應位置之間的對應關係 (correspondence) [1, 12, 14, 28, 29]. GNN 模型可以接收不同姿勢的圖和特徵作為輸入，並預測在一個參考圖上的對應位置 [1, 12, 28, 29]. 這有助於區分物體本身的內在特性 (intrinsic) 與外部變化 (extrinsic，如姿勢) [1, 12, 29, 31]. 這類問題與傳統基於表面相似度的方法不同，後者判斷兩個物體有多像，而形狀對應問題旨在建立不同物體上的對應關係，從而判斷這兩個物體是否是同一個 [1, 14, 29].

另一個廣泛的應用是推薦系統 (Recommendation System) [1, 2, 12, 20, 22]. 推薦系統常常面臨矩陣補全問題 (Matrix Completion Problem) [1, 2, 20, 22, 30]，例如填補用戶對電影評分的稀疏矩陣 [1, 22, 30]. 傳統方法包括協同過濾 (Collaborative Filtering) 和內容過濾 (Content Filtering) [1, 2, 20, 22, 30]. GDL 的思路是將用戶與物品之間的互動建模為圖 (例如二分圖)，並在矩陣分解等過程中，同時考慮物品相似度圖和用戶相似度圖的幾何結構 [1, 2, 22, 27, 30]. 這也是一種形式的 GNN 模型應用，需要利用圖結構信息（如圖拉普拉斯算子）來提升推薦效果 [1, 2, 27].

此外，GDL 的應用還包括分子結構分析和藥物發現 (Molecular Structure Analysis and Drug Discovery) (將分子表示為圖) [2, 20, 22, 24, 25], 社交網絡分析 (Social Network Analysis) [22], 點雲處理 (Point Cloud Processing) [22], 物理模擬與科學計算 (Physics Simulation and Scientific Computing) [22] 等等 [25]. 這些領域的共同點在於數據具有非歐幾里得結構，而 GDL 能夠有效地處理這些結構化的數據 [25].

8. 可解釋性 (Interpretability)

將圖結構納入深度學習模型中，在某些情況下可以增強模型的可解釋性 (Interpretability) [1, 2, 4, 12, 27]. 對於規模較小或結構相對簡單的圖，其拓撲結構是直觀且易於理解的 [1, 12, 27]. 利用圖的這種可解釋性，我們可以更好地理解模型為何做出某些預測或決策 [1, 12, 27]. 然而，當圖變得非常龐大和複雜時，其可解釋性也會隨之減弱 [1, 12, 27]. 這是一個在實際應用中需要權衡的問題。

總之，幾何深度學習為處理非歐幾里得結構數據提供了一個強大的框架 [1, 3, 25]. 通過結合圖論、微分幾何和深度學習的概念，它能夠有效地捕捉並利用數據中的結構資訊，從而解決許多傳統深度學習模型難以處理的問題 [1, 3, 19, 25]. 譜聚類、圖拉普拉斯算子、圖卷積以及流形離散近似的概念構成了這個領域的基石，而形狀對應、推薦系統等應用則展示了其廣闊的應用前景 [1, 2, 12, 18, 19, 22, 25]. 雖然存在排列不變性等挑戰，但 GDL 無疑是當前機器學習領域一個非常活躍且重要的研究方向 [2, 15].

希望這些詳細的介紹和入門重點，能幫助大家更好地理解幾何深度學習的核心概念和價值。