雷鋒網(wǎng)按：本文原作者袁洋，原文載于作者的知乎專欄——理論與機(jī)器學(xué)習(xí)，雷鋒網(wǎng)經(jīng)授權(quán)發(fā)布。

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

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

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

這里 就是第 t 步的位置， 就是導(dǎo)數(shù)， 是步長(zhǎng)。所以這個(gè)算法非常簡(jiǎn)單，就是反復(fù)做這個(gè)一行的迭代。

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

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

其次，如果我們不小心陷入了鞍點(diǎn)，或者比較差的局部最優(yōu)點(diǎn)，GD 算法就跑不出來了，因?yàn)檫@些點(diǎn)的導(dǎo)數(shù)是 0。什么是鞍點(diǎn)：

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

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

SGD 算法的表達(dá)式和 GD 差不多：

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

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

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

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

雖然搞理論的人這么說，但是很多完美主義者仍會(huì)惴惴不安，覺得用帶了隨機(jī)噪聲的導(dǎo)數(shù)來訓(xùn)練自己的神經(jīng)網(wǎng)絡(luò)不放心，一定要用最準(zhǔn)確的導(dǎo)數(shù)才行。于是他們往往還會(huì)嘗試用 GD 跑一遍，和 SGD 得到的結(jié)果比較比較。

結(jié)果呢？因?yàn)槲医?jīng)常干這樣的事情，所以我可以負(fù)責(zé)任地告訴大家，哪怕 GD 訓(xùn)練的時(shí)候有多幾百倍幾千倍的時(shí)間，最后結(jié)果往往是 SGD 得到的網(wǎng)絡(luò)表現(xiàn)要比 GD 得到的網(wǎng)絡(luò)要好得多！

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

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

這是為什么呢？今天我們就簡(jiǎn)單談?wù)劄槭裁此梢蕴与x鞍點(diǎn)。之后有機(jī)會(huì)我會(huì)再詳細(xì)介紹 SGD 的別的優(yōu)良性質(zhì)——這些性質(zhì)也是目前優(yōu)化和機(jī)器學(xué)習(xí)領(lǐng)域研究的熱點(diǎn)問題。

那么我們先理解一下，鞍點(diǎn)的數(shù)學(xué)表達(dá)是什么。

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

• 如果 H 是負(fù)定的，說明所有的特征值都是負(fù)的。這個(gè)時(shí)候，你無論往什么方向走，導(dǎo)數(shù)都會(huì)變負(fù)，也就是說函數(shù)值會(huì)下降。所以，這是（局部）最大值。

• 如果 H 是正定的，說明所有的特征值都是正的。這個(gè)時(shí)候，你無論往什么方向走，導(dǎo)數(shù)都會(huì)變正，也就是說函數(shù)值會(huì)上升。所以，這是（局部）最小值。

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

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

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

在這種非退化的情況下面，我們考慮一個(gè)重要的類別，即 strict saddle 函數(shù)。這種函數(shù)有這樣的特點(diǎn)：對(duì)于每個(gè)點(diǎn) x

• 要么 x 的導(dǎo)數(shù)比較大

• 要么 x 的 Hessian 矩陣包含一個(gè)負(fù)的特征值

• 要么 x 已經(jīng)離某一個(gè)（局部）最小值很近了

為什么我們要 x 滿足這三個(gè)情況的至少一個(gè)呢？因?yàn)?/p>

• 如果 x 的導(dǎo)數(shù)大，那么沿著這個(gè)導(dǎo)數(shù)一定可以大大降低函數(shù)值（我們對(duì)函數(shù)有光滑性假設(shè)）

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

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

所以說，如果我們考慮的函數(shù)滿足這個(gè) strict saddle 性質(zhì)，那么 SGD 算法其實(shí)是不會(huì)被困在鞍點(diǎn)的．那么 strict saddle 性質(zhì)是不是一個(gè)合理的性質(zhì)呢？

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

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

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

因?yàn)榘包c(diǎn)有負(fù)的特征值，所以只要擾動(dòng)之后在這個(gè)方向上有那么一點(diǎn)點(diǎn)分量，就能夠一馬平川地滑下去。除非分量非常非常小的情況下才可能會(huì)繼續(xù)陷在鞍點(diǎn)附近。換句話說，如果加了一個(gè)隨機(jī)擾動(dòng)，其實(shí)大概率情況下是能夠逃離鞍點(diǎn)的！

雖然這個(gè)想法也很直觀，但是要嚴(yán)格地證明很不容易，因?yàn)榫唧w函數(shù)可能是很復(fù)雜的，Hessian 矩陣也在不斷地變化，所以要說明＂擾動(dòng)之后會(huì)陷在鞍點(diǎn)附近的概率是小概率＂這件事情并不容易。

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

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

雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。