0
雷鋒網(wǎng)按：本文原作者袁洋，原文載于作者的知乎專欄——理論與機器學習，雷鋒網(wǎng)經(jīng)授權發(fā)布。
本文主要介紹 SGD 算法，和兩篇分析它逃離鞍點的論文: 我與鬲融，金馳，黃芙蓉寫的 Escaping From Saddle Points – Online Stochastic Gradient for Tensor Decomposition, 以及由金馳，鬲融等人寫的最新力作：How to Escape Saddle Points Efficiently。
假如我們要優(yōu)化一個函數(shù) ，即找到它的最小值，常用的方法叫做 Gradient Descent (GD)，也就是最速下降法。說起來很簡單, 就是每次沿著當前位置的導數(shù)方向走一小步，走啊走啊就能夠走到一個好地方了。
如上圖, 就像你下山一樣，每一步你都挑最陡的路走，如果最后你沒摔死的話，一般你很快就能夠走到山腳。用數(shù)學表示一下，就是
這里 就是第 t 步的位置，
就是導數(shù)，
是步長。所以這個算法非常簡單，就是反復做這個一行的迭代。
雖然簡單優(yōu)美，但 GD 算法至少有兩個明顯的缺陷（其實有更多啦, 但今天先講這兩個）。
首先，在使用的時候, 尤其是機器學習的應用中，我們都會面臨非常大的數(shù)據(jù)集。這個時候如果硬要算 的精確導數(shù)（也別管
是什么了，反正每個機器學習算法里面都有這么個東西），往往意味著我們要花幾個小時把整個數(shù)據(jù)集都掃描一遍，然后還只能走一小步。一般 GD 要幾千步幾萬步才能收斂，所以這樣就根本跑不完了。
其次，如果我們不小心陷入了鞍點，或者比較差的局部最優(yōu)點，GD 算法就跑不出來了，因為這些點的導數(shù)是 0。什么是鞍點：
什么是局部最優(yōu)點（下圖右邊）：
有趣的是，這兩大缺陷竟然可以用同一個方法解決，就是我們今天要談的 Stochastic Gradient Descent (SGD) 算法。
SGD 算法的表達式和 GD 差不多：
這里 就是所謂的 Stochastic Gradient，它滿足
也就是說，雖然包含一定的隨機性，但是從期望上來看，它是等于正確的導數(shù)的。用一張圖來表示，其實 SGD 就像是喝醉了酒的 GD，它依稀認得路，最后也能自己走回家，但是走得歪歪扭扭。（紅色的是 GD 的路線，偏粉紅的是 SGD 的路線）。
仔細看的話，其實 SGD 需要更多步才能夠收斂的，畢竟它喝醉了。可是，由于它對導數(shù)的要求非常低，可以包含大量的噪聲，只要期望正確就行（有時候期望不對都是可以的），所以導數(shù)算起來非常快。就我剛才說的機器學習的例子，比如神經(jīng)網(wǎng)絡吧，訓練的時候都是每次只從百萬數(shù)據(jù)點里面拿 128 或者 256 個數(shù)據(jù)點，算一個不那么準的導數(shù)，然后用 SGD 走一步的。想想看，這樣每次算的時間就快了 10000 倍，就算是多走幾倍的路，算算也是挺值的了。
所以它可以完美解決 GD 的第一個問題——算得慢。這也是當初人們使用 SGD 的主要目的。而且，大家并不用擔心導數(shù)中包含的噪聲會有什么負面影響。有大量的理論工作說明，只要噪聲不離譜，其實（至少在 f 是凸函數(shù)的情況下），SGD 都能夠很好地收斂。
雖然搞理論的人這么說，但是很多完美主義者仍會惴惴不安，覺得用帶了隨機噪聲的導數(shù)來訓練自己的神經(jīng)網(wǎng)絡不放心，一定要用最準確的導數(shù)才行。于是他們往往還會嘗試用 GD 跑一遍，和 SGD 得到的結果比較比較。
結果呢？因為我經(jīng)常干這樣的事情，所以我可以負責任地告訴大家，哪怕 GD 訓練的時候有多幾百倍幾千倍的時間，最后結果往往是 SGD 得到的網(wǎng)絡表現(xiàn)要比 GD 得到的網(wǎng)絡要好得多！
很意外是不是？加了噪聲的算法反而更好，這簡直就像說＂讓馬路上的司機多喝點酒，交通能夠更順暢＂一樣讓人難以接受。
但事實就是如此。實踐中，人們發(fā)現(xiàn)，除了算得快，SGD 有非常多的優(yōu)良性質。它能夠自動逃離鞍點，自動逃離比較差的局部最優(yōu)點，而且，最后找到的答案還具有很強的一般性（generalization），即能夠在自己之前沒有見過但是服從同樣分布的數(shù)據(jù)集上表現(xiàn)非常好！
這是為什么呢？今天我們就簡單談談為什么它可以逃離鞍點。之后有機會我會再詳細介紹 SGD 的別的優(yōu)良性質——這些性質也是目前優(yōu)化和機器學習領域研究的熱點問題。
那么我們先理解一下，鞍點的數(shù)學表達是什么。
首先，我們考慮的情況是導數(shù)為０的點。這些點被稱為 Stationary points，即穩(wěn)定點。穩(wěn)定點的話，可以是（局部）最小值，（局部）最大值，也可以是鞍點。如何判斷呢？我們可以計算它的 Hessian 矩陣 H。
如果 H 是負定的，說明所有的特征值都是負的。這個時候，你無論往什么方向走，導數(shù)都會變負，也就是說函數(shù)值會下降。所以，這是（局部）最大值。
如果 H 是正定的，說明所有的特征值都是正的。這個時候，你無論往什么方向走，導數(shù)都會變正，也就是說函數(shù)值會上升。所以，這是（局部）最小值。
如果Ｈ既包含正的特征值，又包含負的特征值，那么這個穩(wěn)定點就是一個鞍點。具體參照之前的圖片。也就是說有些方向函數(shù)值會上升，有些方向函數(shù)值會下降。
雖然看起來上面已經(jīng)包含了所有的情況，但是其實不是的！還有一個非常重要的情況就是 H 可能包含特征值為０的情況。這種情況下面，我們無法判斷穩(wěn)定點到底屬于哪一類，往往需要參照更高維的導數(shù)才行。想想看，如果特征值是０，就說明有些方向一馬平川一望無際，函數(shù)值一直不變，那我們當然不知道是怎么回事了：）
我們今天討論的情況只包含前三種，不包含第四種．第四種被稱為退化了的情況，所以我們考慮的情況就叫做非退化情況。
在這種非退化的情況下面，我們考慮一個重要的類別，即 strict saddle 函數(shù)。這種函數(shù)有這樣的特點：對于每個點 x
要么 x 的導數(shù)比較大
要么 x 的 Hessian 矩陣包含一個負的特征值
要么 x 已經(jīng)離某一個（局部）最小值很近了
為什么我們要 x 滿足這三個情況的至少一個呢？因為
如果 x 的導數(shù)大，那么沿著這個導數(shù)一定可以大大降低函數(shù)值（我們對函數(shù)有光滑性假設）
如果 x 的 Hessian 矩陣有一個負的特征值，那么我們通過加噪聲隨機擾動，跑跑就能夠跑到這個方向上，沿著這個方向就能夠像滑滑梯一樣一路滑下去，大大降低函數(shù)值
如果 x 已經(jīng)離某一個（局部）最小值很近了，那么我們就完成任務了，畢竟這個世界上沒有十全十美的事情，離得近和精確跑到這個點也沒什么區(qū)別。
所以說，如果我們考慮的函數(shù)滿足這個 strict saddle 性質，那么 SGD 算法其實是不會被困在鞍點的．那么 strict saddle 性質是不是一個合理的性質呢？
實際上，有大量的機器學習的問題使用的函數(shù)都滿足這樣的性質。比如 Orthogonal tensor decomposition，dictionary learning, matrix completion 等等。而且，其實并不用擔心最后得到的點只是一個局部最優(yōu)，而不是全局最優(yōu)。因為實際上人們發(fā)現(xiàn)大量的機器學習問題，幾乎所有的局部最優(yōu)是幾乎一樣好的，也就是說，只要找到一個局部最優(yōu)點，其實就已經(jīng)找到了全局最優(yōu)，比如 Orthogonal tensor decomposition 就滿足這樣的性質，還有小馬哥 NIPS16 的 best student paper 證明了 matrix completion 也滿足這樣的性質。我覺得神經(jīng)網(wǎng)絡從某些角度來看，也是（幾乎）滿足的，只是不知道怎么證。
下面討論一下證明，主要討論一下第二篇。第一篇論文其實就是用數(shù)學的語言在說＂在鞍點加擾動，能夠順著負的特征值方向滑下去＂。第二篇非常有意思，我覺得值得介紹一下想法。
首先，算法上有了一些改動。算法不再是 SGD，而是跑若干步 GD，然后跑一步 SGD。當然實際上大家是不會這么用的，但是理論分析么，這么考慮沒問題。什么時候跑 SGD 呢？只有當導數(shù)比較小，而且已經(jīng)很長時間沒有跑過 SGD 的時候，才會跑一次。也就是說，只有確實陷在鞍點上了，才會隨機擾動一下下。
因為鞍點有負的特征值，所以只要擾動之后在這個方向上有那么一點點分量，就能夠一馬平川地滑下去。除非分量非常非常小的情況下才可能會繼續(xù)陷在鞍點附近。換句話說，如果加了一個隨機擾動，其實大概率情況下是能夠逃離鞍點的！
雖然這個想法也很直觀，但是要嚴格地證明很不容易，因為具體函數(shù)可能是很復雜的，Hessian 矩陣也在不斷地變化，所以要說明＂擾動之后會陷在鞍點附近的概率是小概率＂這件事情并不容易。
作者們采取了一個很巧妙的方法：對于負特征值的那個方向，任何兩個點在這兩個方向上的投影的距離只要大于 u/2，那么它們中間至少有一個點能夠通過多跑幾步 GD 逃離鞍點。也就是說，會持續(xù)陷在鞍點附近的點所在的區(qū)間至多只有 u 那么寬！通過計算寬度，我們也就可以計算出概率的上屆，說明大概率下這個 SGD+GD 算法能夠逃離鞍點了。
[原文 Figure 1 畫得很漂亮，推薦一下]
雷峰網(wǎng)版權文章，未經(jīng)授權禁止轉載。詳情見轉載須知。
