機器之心原創

作者：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 非常遠。這樣算法就沒用了，因為該算法僅希望稍微離開鞍點到達另一個點，以便避開鞍點，向另一個駐點前進。主定理主定理如下所示。本質上，該定理确保目标函數（向駐點收斂）的下降速率。證明策略是，經過特定次數的疊代後，當逼近鞍點時，該函數的值大概率會下降。

上圖看起來比較複雜，我們可以從中得到以下信息：

1. 大 O 符号和步長規則都與 β 相關，就此我們可以得出：梯度的利普希茨常數 β 越大，算法收斂時間就越長。
2. ρ 與參數 ϵ 直接相關，擾動後的黎曼梯度下降（perturbed Riemannian gradient descent）算法将以 1/(2 ϵ^2) 的速率避開鞍點。
3. 流形的維度是影響 ϵ 的另一個參數。我們可以看到 d 以對數的方式影響收斂速率。

該論文的證明策略是，經過特定次數的疊代後，當逼近鞍點時，該函數的值大概率會下降。作者進一步證明，完成擾動和執行算法的 T 步後，如果疊代仍然遠離鞍點，則函數會下降。結論該論文研究了受限優化問題，即對滿足多個流形約束條件和一些關于 f(x) 假設的函數 f(x) 執行最小化。該研究證明，隻要函數和流形具備恰當的平滑度，則擾動黎曼梯度下降算法能夠避開鞍點。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!