如何在黎曼流形上避開鞍點？本文帶你了解優化背後的數學知識
- 2020 年 2 月 24 日
- 筆記
機器之心原創
作者：Joshua Chou
編輯：Joni Zhong
翻譯：魔王
在一篇名為《Escaping from saddle points on Riemannian manifolds》的論文中，來自華盛頓大學、加州大學伯克利分校的研究人員深入探索了優化問題的細節，這對理解機器學習底層的數學知識非常重要。本文是對該論文的解讀。
引言
「優化」通常是指將函數最大化或最小化，而函數的集合通常表示遵循約束條件的可選擇範圍。我們可以通過對比集合內不同的函數選擇來確定哪個函數是「最優」的。
學習是模型迭代地學習最小化某個誤差函數或者最大化某個獎勵函數的過程。拿用於分類任務的簡單線性回歸為例，誤差函數是模型輸出和數據真值輸出之間的均方差，學習過程即找出線性函數 y = a^Tx + b 的係數 a_i 和 b_i，以最小化 y（模型輸出）和 y*（真值輸出）間的誤差。例如，學習（即優化）通常使用梯度下降演算法通過反向傳播來迭代進行。在每一次迭代中，係數 a_i 和 b_i 都是（所有可能 a_i 和 b_i 值集合中的）一個選擇，演算法將學習到能夠最小化誤差函數的下一組係數。因此，模型的學習過程歸根結底還是優化問題。
論文《Escaping from saddle points on Riemannian manifolds》深入探索了優化問題的細節，這對理解機器學習的底層數學知識非常重要。
在經典的最小化任務中，基於梯度的優化方法是尋找局部極小值的最常用方法。「陷入鞍點」問題就出現在基於梯度的優化方法中。優化問題旨在尋找能使目標函數達到局部極小值的駐點，而鞍點是不能達到局部極小值的駐點。因此，了解如何識別並避開鞍點至關重要。這篇論文介紹了一種新方法，能夠針對滿足流形約束的目標函數識別並避開鞍點。
設置
該論文考慮在平滑流形 M 上最小化非凸平滑函數：
其中 M 是一個 d 維平滑流形，f 是二次可微函數，Hessian 符合 ρ-Lipschitz。為此類問題尋找全局最小值是一項挑戰，而這篇論文利用一階優化方法找出近似的二階駐點（達到局部極小值）。在抵達駐點時，作者引入一種方法來識別該駐點是鞍點還是局部極小值。此外，作者提出一種方法來避開鞍點，並嘗試將目標函數收斂至局部極小值。
隨著越來越多的應用被建模為大規模優化問題，較簡單的一階方法變得越來越重要。因此，該論文使用一階方法處理非凸問題，並查看其效果。具體而言，作者對黎曼流形上的非凸問題執行優化。
背景知識
在深入了解該論文之前，我們先要理解一些底層數學概念。理想情況下，這篇論文要求讀者對高斯幾何有基礎了解，即三維歐幾里德空間中曲線和表面的幾何。此外，微分幾何的知識也很重要。不過，我會嘗試解釋這篇論文中某些術語的意義。
每個平滑的 d 維流形 M 都局部微分同胚於 R^n。M 中每個點周圍都有一個平坦的（小型）鄰域。因此，它遵循 R^n 上的歐幾里德度量。從視覺上來看，這意味著 M 中的每個點周圍都有一個曲率為零的小型鄰域和歐幾里德度量。
接下來，我們需要了解可微流形 M 在 M 內的點 x 處的切空間 TxM。切空間是一個維度與 M 相同的向量空間。讀者需要了解這個概念：在標準 R^n 中，點 x ∈ R^n 處的切向量 v 可解釋為：對圍繞 x 局部定義的實值函數執行的一階線性可微運算。而這一點可以泛化至流形設置中。
現在我們來看黎曼流形。黎曼流形具備黎曼度量。黎曼度量為我們提供了每個切空間上的標量積，可用于衡量流形上曲線的角度和長度。它定義了距離函數，並自然而然地將流形轉換為度量空間。
假設讀者了解曲率這一概念，我們來看黎曼曲率張量（Riemann curvature tensor）和黎曼流形的截面曲率。我們可以把黎曼曲率張量理解為流形的曲率，這與我們對曲率的直觀理解是一致的。
曲率
讀者可以在標準來源中找到截面曲率的定義，其思路是向平面分配曲率。切空間中平面 p 的截面曲率與初始方向在 P 中的測地線（geodesic）所掠過表面的高斯曲率成正比。直觀上，這是一個穿過給定平面的二維切片，你需要度量其二維曲率。
符號
該論文關注平滑的 d 維黎曼流形 (M,g)，該流形使用黎曼度量 g。點 x ∈ M 的切空間是 TxM。鄰域被定義為：Bx(r) = { v ∈ TxM, ||v|| ≤ r }，即以 0 為中心、半徑 r 位於切空間 TxM 內的球。在任意點 x ∈ M，度量 g 自然地推導出切空間 < · , · > : TxM x TxM → R 上的內積。黎曼曲率張量用 R(x)[u, v] 來表示，其中 x ∈ M，u, v ∈ TxM。截面曲率是 K(x)[u, v]，x ∈ M, u, v ∈ TxM，其定義如下：
該論文用 d(x, y) 表示 M 中兩個點之間的距離（根據黎曼度量得出）。測地線 γ : R → M 是一條等速曲線，其長度等於 d(x, y)，即測地線是連接 x 和 y 的最短路徑。
指數映射 Exp_x (v) 將 v ∈ TxM 映射到 y ∈ M，則存在測地線 γ，使 γ(0) = x，γ(1) = y，(d/dt)γ(0) = v。這個概念很難理解，讀者可以按照下面的方法理解指數映射。
將指數映射看作沿著切向量 v 的方向將點 x 推動一小段距離。如果我們可以將該點沿著測地線 γ 推動 1 個距離單位，那麼我們將到達點 y。
另一個理解方式是投影。假設點 p1 的坐標為 (x_1, y_1, z_1)，z_1 = 0，即 p1 在 x-y 平面上。向 p1 添加向量 p2 (x_2, y_2, z_2)，其中 z_2 不等於 0，即 p3 = p1+p2。現在，使用投影定理，將 p3 投影回 x-y 平面得到 p4。根據投影定理，p4 與 p1 間的距離最短。測地線即球面或其他曲面或流形上兩點之間的最短路線。指數映射類似於該示例中的投影運算元。
主要演算法
在黎曼流形上執行優化的主要演算法如下所示：
演算法 1 看起來很嚇人，但是作者給出的總結對於理解該演算法機制很有用。演算法 1 按照以下步驟運行：
演算法 1 依賴流形的指數映射，對於易於計算指數映射的情況很有用（而多種常見流形的指數映射是容易計算的）。作者用可視化的方式進行了展示：
圖 1：鞍點位於球面上的函數 f。
函數 f 的定義是：f(x) = (x_1)^2 − (x_2)^2 + 4(x_3)^2，如圖 1 所示。該演算法在 x_0 處進行初始化，x_0 是鞍點。在其切空間中向 x_0 添加雜訊，然後計算指數映射，將點 x_0 映射迴流形上的點 x_1。然後演算法運行黎曼梯度下降，並在 x* 處停止，x* 即局部極小值。
主定理背後的概念
該演算法背後的思路很簡單，但底層證明較為複雜。我嘗試簡要直觀地解釋結果並提供一些見解。詳細證明及相關文獻參見原論文。
假設
該論文作出了多項假設，前兩個假設關於 f，最後一個假設關於 M：
簡要來講，利普希茨連續是連續性的定量版本。給出 x 和 y 之間的距離 d(x,y)，則利普希茨函數對 f(x) 和 f(y) 之間的距離設置定量上限。如果 C 是 f 的利普希茨值，則該距離至多為 C×d(x, y)。假設 1 和假設 2 是梯度和 Hessian 的標準利普希茨條件，即常數 β 和 ρ 分別描述梯度和 Hessian 在「最糟糕情況下」的分離情況。這些假設主要是為了確保梯度和 Hessian 可微分。
類似地，假設 3 對 M 的截面曲率設置了上限。直觀來看，該假設旨在確保指數映射不會無限增大。例如，對於點 x∈M，其切空間 TxM 和 x 周圍的曲率是極大的。TxM 中點的指數映射 Exp_x (v) 可能得到點 y∈M，y 距離 x 非常遠。這樣演算法就沒用了，因為該演算法僅希望稍微離開鞍點到達另一個點，以便避開鞍點，向另一個駐點前進。
主定理
主定理如下所示。本質上，該定理確保目標函數（向駐點收斂）的下降速率。證明策略是，經過特定次數的迭代後，當逼近鞍點時，該函數的值大概率會下降。
上圖看起來比較複雜，我們可以從中得到以下資訊：
- 大 O 符號和步長規則都與 β 相關，就此我們可以得出：梯度的利普希茨常數 β 越大，演算法收斂時間就越長。
- ρ 與參數 ϵ 直接相關，擾動後的黎曼梯度下降（perturbed Riemannian gradient descent）演算法將以 1/(2 ϵ^2) 的速率避開鞍點。
- 流形的維度是影響 ϵ 的另一個參數。我們可以看到 d 以對數的方式影響收斂速率。
該論文的證明策略是，經過特定次數的迭代後，當逼近鞍點時，該函數的值大概率會下降。作者進一步證明，完成擾動和執行演算法的 T 步後，如果迭代仍然遠離鞍點，則函數會下降。
結論
該論文研究了受限優化問題，即對滿足多個流形約束條件和一些關於 f(x) 假設的函數 f(x) 執行最小化。該研究證明，只要函數和流形具備恰當的平滑度，則擾動黎曼梯度下降演算法能夠避開鞍點。
本文為機器之心原創，轉載請聯繫本公眾號獲得授權。
