雷鋒網按：本文原作者袁洋，原文載于作者的知乎專欄——理論與機器學習，雷鋒網經授權發(fā)布。

本文主要介紹 SGD 算法，和兩篇分析它逃離鞍點的論文: 我與鬲融，金馳，黃芙蓉寫的 Escaping From Saddle Points – Online Stochastic Gradient for Tensor Decomposition, 以及由金馳，鬲融等人寫的最新力作：How to Escape Saddle Points Efficiently。

假如我們要優(yōu)化一個函數 ，即找到它的最小值，常用的方法叫做 Gradient Descent (GD)，也就是最速下降法。說起來很簡單, 就是每次沿著當前位置的導數方向走一小步，走啊走啊就能夠走到一個好地方了。

如上圖, 就像你下山一樣，每一步你都挑最陡的路走，如果最后你沒摔死的話，一般你很快就能夠走到山腳。用數學表示一下，就是

這里 就是第 t 步的位置， 就是導數， 是步長。所以這個算法非常簡單，就是反復做這個一行的迭代。

雖然簡單優(yōu)美，但 GD 算法至少有兩個明顯的缺陷（其實有更多啦, 但今天先講這兩個）。

首先，在使用的時候, 尤其是機器學習的應用中，我們都會面臨非常大的數據集。這個時候如果硬要算 的精確導數（也別管 是什么了，反正每個機器學習算法里面都有這么個東西），往往意味著我們要花幾個小時把整個數據集都掃描一遍，然后還只能走一小步。一般 GD 要幾千步幾萬步才能收斂，所以這樣就根本跑不完了。

其次，如果我們不小心陷入了鞍點，或者比較差的局部最優(yōu)點，GD 算法就跑不出來了，因為這些點的導數是 0。什么是鞍點：

什么是局部最優(yōu)點（下圖右邊）：

有趣的是，這兩大缺陷竟然可以用同一個方法解決，就是我們今天要談的 Stochastic Gradient Descent (SGD) 算法。

SGD 算法的表達式和 GD 差不多：

這里 就是所謂的 Stochastic Gradient，它滿足

也就是說，雖然包含一定的隨機性，但是從期望上來看，它是等于正確的導數的。用一張圖來表示，其實 SGD 就像是喝醉了酒的 GD，它依稀認得路，最后也能自己走回家，但是走得歪歪扭扭。（紅色的是 GD 的路線，偏粉紅的是 SGD 的路線）。

仔細看的話，其實 SGD 需要更多步才能夠收斂的，畢竟它喝醉了?？墒?，由于它對導數的要求非常低，可以包含大量的噪聲，只要期望正確就行（有時候期望不對都是可以的），所以導數算起來非常快。就我剛才說的機器學習的例子，比如神經網絡吧，訓練的時候都是每次只從百萬數據點里面拿 128 或者 256 個數據點，算一個不那么準的導數，然后用 SGD 走一步的。想想看，這樣每次算的時間就快了 10000 倍，就算是多走幾倍的路，算算也是挺值的了。

所以它可以完美解決 GD 的第一個問題——算得慢。這也是當初人們使用 SGD 的主要目的。而且，大家并不用擔心導數中包含的噪聲會有什么負面影響。有大量的理論工作說明，只要噪聲不離譜，其實（至少在 f 是凸函數的情況下），SGD 都能夠很好地收斂。

雖然搞理論的人這么說，但是很多完美主義者仍會惴惴不安，覺得用帶了隨機噪聲的導數來訓練自己的神經網絡不放心，一定要用最準確的導數才行。于是他們往往還會嘗試用 GD 跑一遍，和 SGD 得到的結果比較比較。

結果呢？因為我經常干這樣的事情，所以我可以負責任地告訴大家，哪怕 GD 訓練的時候有多幾百倍幾千倍的時間，最后結果往往是 SGD 得到的網絡表現要比 GD 得到的網絡要好得多！

很意外是不是？加了噪聲的算法反而更好，這簡直就像說＂讓馬路上的司機多喝點酒，交通能夠更順暢＂一樣讓人難以接受。

但事實就是如此。實踐中，人們發(fā)現，除了算得快，SGD 有非常多的優(yōu)良性質。它能夠自動逃離鞍點，自動逃離比較差的局部最優(yōu)點，而且，最后找到的答案還具有很強的一般性（generalization），即能夠在自己之前沒有見過但是服從同樣分布的數據集上表現非常好！

這是為什么呢？今天我們就簡單談談為什么它可以逃離鞍點。之后有機會我會再詳細介紹 SGD 的別的優(yōu)良性質——這些性質也是目前優(yōu)化和機器學習領域研究的熱點問題。

那么我們先理解一下，鞍點的數學表達是什么。

首先，我們考慮的情況是導數為０的點。這些點被稱為 Stationary points，即穩(wěn)定點。穩(wěn)定點的話，可以是（局部）最小值，（局部）最大值，也可以是鞍點。如何判斷呢？我們可以計算它的 Hessian 矩陣 H。

• 如果 H 是負定的，說明所有的特征值都是負的。這個時候，你無論往什么方向走，導數都會變負，也就是說函數值會下降。所以，這是（局部）最大值。

• 如果 H 是正定的，說明所有的特征值都是正的。這個時候，你無論往什么方向走，導數都會變正，也就是說函數值會上升。所以，這是（局部）最小值。

• 如果Ｈ既包含正的特征值，又包含負的特征值，那么這個穩(wěn)定點就是一個鞍點。具體參照之前的圖片。也就是說有些方向函數值會上升，有些方向函數值會下降。

• 雖然看起來上面已經包含了所有的情況，但是其實不是的！還有一個非常重要的情況就是 H 可能包含特征值為０的情況。這種情況下面，我們無法判斷穩(wěn)定點到底屬于哪一類，往往需要參照更高維的導數才行。想想看，如果特征值是０，就說明有些方向一馬平川一望無際，函數值一直不變，那我們當然不知道是怎么回事了：）

我們今天討論的情況只包含前三種，不包含第四種．第四種被稱為退化了的情況，所以我們考慮的情況就叫做非退化情況。

在這種非退化的情況下面，我們考慮一個重要的類別，即 strict saddle 函數。這種函數有這樣的特點：對于每個點 x

• 要么 x 的導數比較大

• 要么 x 的 Hessian 矩陣包含一個負的特征值

• 要么 x 已經離某一個（局部）最小值很近了

為什么我們要 x 滿足這三個情況的至少一個呢？因為

• 如果 x 的導數大，那么沿著這個導數一定可以大大降低函數值（我們對函數有光滑性假設）

• 如果 x 的 Hessian 矩陣有一個負的特征值，那么我們通過加噪聲隨機擾動，跑跑就能夠跑到這個方向上，沿著這個方向就能夠像滑滑梯一樣一路滑下去，大大降低函數值

• 如果 x 已經離某一個（局部）最小值很近了，那么我們就完成任務了，畢竟這個世界上沒有十全十美的事情，離得近和精確跑到這個點也沒什么區(qū)別。

所以說，如果我們考慮的函數滿足這個 strict saddle 性質，那么 SGD 算法其實是不會被困在鞍點的．那么 strict saddle 性質是不是一個合理的性質呢？

實際上，有大量的機器學習的問題使用的函數都滿足這樣的性質。比如 Orthogonal tensor decomposition，dictionary learning, matrix completion 等等。而且，其實并不用擔心最后得到的點只是一個局部最優(yōu)，而不是全局最優(yōu)。因為實際上人們發(fā)現大量的機器學習問題，幾乎所有的局部最優(yōu)是幾乎一樣好的，也就是說，只要找到一個局部最優(yōu)點，其實就已經找到了全局最優(yōu)，比如 Orthogonal tensor decomposition 就滿足這樣的性質，還有小馬哥 NIPS16 的 best student paper 證明了 matrix completion 也滿足這樣的性質。我覺得神經網絡從某些角度來看，也是（幾乎）滿足的，只是不知道怎么證。

下面討論一下證明，主要討論一下第二篇。第一篇論文其實就是用數學的語言在說＂在鞍點加擾動，能夠順著負的特征值方向滑下去＂。第二篇非常有意思，我覺得值得介紹一下想法。

首先，算法上有了一些改動。算法不再是 SGD，而是跑若干步 GD，然后跑一步 SGD。當然實際上大家是不會這么用的，但是理論分析么，這么考慮沒問題。什么時候跑 SGD 呢？只有當導數比較小，而且已經很長時間沒有跑過 SGD 的時候，才會跑一次。也就是說，只有確實陷在鞍點上了，才會隨機擾動一下下。

因為鞍點有負的特征值，所以只要擾動之后在這個方向上有那么一點點分量，就能夠一馬平川地滑下去。除非分量非常非常小的情況下才可能會繼續(xù)陷在鞍點附近。換句話說，如果加了一個隨機擾動，其實大概率情況下是能夠逃離鞍點的！

雖然這個想法也很直觀，但是要嚴格地證明很不容易，因為具體函數可能是很復雜的，Hessian 矩陣也在不斷地變化，所以要說明＂擾動之后會陷在鞍點附近的概率是小概率＂這件事情并不容易。

作者們采取了一個很巧妙的方法：對于負特征值的那個方向，任何兩個點在這兩個方向上的投影的距離只要大于 u/2，那么它們中間至少有一個點能夠通過多跑幾步 GD 逃離鞍點。也就是說，會持續(xù)陷在鞍點附近的點所在的區(qū)間至多只有 u 那么寬！通過計算寬度，我們也就可以計算出概率的上屆，說明大概率下這個 SGD+GD 算法能夠逃離鞍點了。

[原文 Figure 1 畫得很漂亮，推薦一下]

雷峰網版權文章，未經授權禁止轉載。詳情見轉載須知。