吳恩達導師Michael I.Jordan學術演講：如何有效避開鞍點（視頻+PPT）

本文經OReilly授權發布

大數據文摘字幕組作品

翻譯：Iris W、李文浩、龍牧雪

後期：龍牧雪

機器學習中，非凸優化中的一個核心問題是鞍點的逃逸問題。梯度下降法（GD，Gradient Descent）一般可以漸近地逃離鞍點，但是還有一個未解決的問題——效率，即梯度下降法是否可以加速逃離鞍點。

加州大學伯克利分校教授Michael I. Jordan（吳恩達的導師）就此做了研究，即，使用合理的擾動參數增強的梯度下降法可有效地逃離鞍點。在去年舊金山的OReilly和Intel AI Conference，他就此研究做了一次演講。

此前，大數據文摘曾發出過Michael I. Jordan在清華手寫板書的授課筆記（戳這裡獲取），非常受歡迎，這次，讓我們看看他是如何解讀自己的學術成果的。

Michael I. Jordan：如何有效避開鞍點

時長13分鐘，帶有中文字幕

點擊觀看??

https://v.qq.com/x/page/p0566lapcs5.html

暫時無法觀看的小夥伴可以下拉看文字版

關注大數據文摘公眾號，後台回復「鞍點」獲取演講PPT合集。

很榮幸來到這裡。我剛從中國飛回來，大約是昨天午夜時分，我感覺好極了。如果有一個地方人們談論AI比舊金山還多，那就是中國。這很神奇吧。與之相反，如果我去參加一個理論會議，我會做一個關於系統的演講，但我更傾向在系統會議演講中和大家探討理論研究。我認為拓展視野並意識到所有的問題是非常重要的。

我們處在一個非常經驗主義的人工智慧和機器學習的時代，比我的職業生涯中的任何時刻都更重視經驗。這很好，有很多新的探索，但是我們的理解理論遠遠落後。所以我在自己的研究中更多地關注這個問題。今天我想給大家講一些研究結果。Chi Jin主導這項研究，他是我在伯克利的研究生，還有Ronge Ge，Praneeth Netrapalli，Sham Kakade幾位學生參與了這個項目。

論文鏈接：

https://arxiv.org/abs/1703.00887

我要講的是鞍點，以及如何有效地避開它們。你們都知道局部最小值是我們的剋星，所以我一直在討論這個問題，那就是如何避免局部最小值。但問題並不明顯，有很多機器學習的問題沒有局部最小值。即使你有局部最小值，梯度下降似乎可以輕鬆迴避它們。神經網路如果足夠大的話就會有足夠的冗餘，要做到這一點並不難。達到零就是全局最優解。這就是你們在實踐中看到的。也許這並不是真正的問題。如果一個迴路的局部最大值不是問題，它的鞍點是剩下需要解決的。

鞍點在這些體系結構中大量存在，不論是在簡單的模型還是在神經網路中。它們會導致學習曲線變平。你會經常看到一個學習曲線下降很快，之後很久都是平的。這就是靠近鞍點的表現。最終你會逃離鞍點。繼續下去，你可能會碰到另一個鞍點。你會看到一個學習曲線，它這樣上升和下降。某種意義上，這不是問題，如果你最終得到正確答案。但是你可能會碰到一個鞍點並在那裡停滯很長一段時間，時間過久，以至於你都不知道在某個地方能找到更好的答案。特別是如果你沒有那麼多時間來運行你的演算法。所以你可以在多維度中理解這個。

讓我給你們看一張鞍點的圖片。在左邊我們有一個「嚴格」的鞍點。有一個負曲率的方向，這個負曲率是嚴格小於零的。在右邊，它是個非嚴格鞍點，但第二個特徵值嚴格為零。

如何逃離鞍點？如果你沿著中間部分往下走，你最終會擺脫它，但這可能需要很長時間。這只是兩個維度上，但如果你有上十萬甚至上百萬維度呢？就像現在一般的研究中一樣。在這種情況下，可能只有一條出路，其他的方向都不行，所以要找到逃逸的方向可能要花很長時間。當維度越來越大的時候，就有問題了。基於梯度下降的演算法可能會有麻煩。

如果你有一個海森矩陣，這個問題將會消失，因為你會知道所有的方向，但你必須計算一個海森矩陣的特徵向量。這兩種情況都不好，因為它太複雜了也太慢。所以，梯度方法是個問題。

在這個領域還有很多有待證明的東西，這些是最近的結果。對於連續時間上的梯度流，梯度下降將會逐漸避開鞍點。逐漸（asymptotic）意味著要耗費很長的時間來避開鞍點，特別是在高維情況下。所以你需要考慮這個問題。

梯度下降可以用指數時間來逃離鞍點，這是另一個新結果。我們都喜歡隨機評級，因為每次迭代都很簡單。有一篇重要的論文證明在多項式時間內你會逃離鞍點，這是最近的工作。多項式級的複雜度是不好的。這對理論學家來說是好事，但這對實際的操作是不利的。所以這是一個開放問題，我們能否證明一個更強的定理，來理解為什麼梯度下降通常是好用的。

我們來回憶一下梯度下降是什麼。現在我們來討論一個凸問題，是一個類似碗的形狀。我們希望尋找f(x)的最小值。這是梯度下降方程。可以證明它是收斂於全局最優解的，以1/k的速率，對於平滑函數。最重要的是，達到最優所需的迭代的次數是獨立於維度的。這是一個驚人的數學事實。也許並不是所有人都這樣認為，但事實的確如此。這意味著你可以運行無限維度的梯度下降，仍然不會減慢它的速度。計算梯度可能需要與維度數量成正比的時間，但只是線性的在維數中。但這是針對凸問題。

針對一個非凸的例子，我們不討論最終值。我們將梯度設置為0，你可以證明你會得到一個駐點。但它可以是局部極小值或局部最大值或鞍點。當前最讓我們困擾的是鞍點，我們到達和逃脫鞍點的速度。

現在最流行深層神經網路，在某種意義上是非凸的。但是實際操作中有很多重要的問題，這些問題都沒有虛假的局部最小值，這很好。它們有一個全局最優值。所有的鞍點都是嚴格鞍。也就是說，你可以漏出，找到一個有負曲率的方向。

所以對於非凸問題，如果我們可以解決基於梯度方法的收斂問題，就是作為鞍點條件的一個函數，你就可以為所有這些問題求得全局的收斂速度，這是我們今天要做的。但是如果你喜歡神經網路，那麼你就得注意了。

讓我們看下一般非凸性問題。這是Nesterov提出的定理。在一階駐點，假設我們有一個具有利普希茨梯度的函數。如果你懂些數學知識你會發現，梯度在x1和x2之間變化不大。一階駐點不意味著梯度完全等於零，而是漸進收斂的，相當於我們在零點周圍放了一個半徑為埃普西隆的小球。問題是擊中那個球需要多長的時間。

對於任意的埃普西隆，這就給了我們一個達到最優值的收斂速度，這個速率是由Nesterov得出的，他證明收斂速度正比於1/e的平方。這是一個很好的速率，它不是非常快但是已經足夠好了，但這裡的關鍵在於公式中維度不是必須的，它是獨立於維度的，這是梯度下降一個有意思的特性。

讓我們來談談這次演講的主要內容，那麼二階駐點有怎樣的性質呢？我們對鞍點尤其感興趣，但我們同時也很關注局部最小值，我們稍微增加光滑度，可以證明一個定理，我們引入海森-利普希茨性質，很明顯二階駐點是一階駐點的擴展，這個梯度同樣趨近零且不等於零，同時海森矩陣的最小特徵值不嚴格大於等於零。我們給自己放鬆了一個小區間，從而又得到了一個收斂速度，所以可以看看我們達到二階駐點速度有多快。這就是我們的演算法，我們將其命名為擾動梯度下降。它其實就是一般的梯度下降演算法，但是偶爾我們會增加一點隨機噪音。

當梯度很小的時候我們會加入雜訊。這一步操作頻率很低，大概每t個時間步進行一次，t是一個超參數，在這個定理中，我們通過從一個球狀區域中隨機採樣實現雜訊的注入，我們也可以做其他分析，但是這裡簡化了。這不是傳統意義上的隨機梯度，而是每一步都注入雜訊的隨機梯度。以上就是我們得出下面定理的背景知識。這個定理非常美妙，所以我認為這個演算法也是很值得仔細研究的。

這就是我們的主要成果，即使我設置了這些約束，我們仍然可以得到一個正比於1/e平方的收斂速度，和梯度下降的性能是一樣的，維度依賴也被消除了一點。這是一個標準的學術界的小技巧。這和之前梯度下降的性質是一樣的，除了這裡的大O里有一個跟d相關的因子，但它不是d的多項式，它是對數多項式，是對數的四次方。所以對我來說這給出了一個解釋，就是為什麼擾動梯度下降演算法能高效解決高維問題。維度的對數不算大問題，這是一個很小的數字，你可以通過高速計算機處理它。

這是一個出人意料的結果。我們再來總結一下，這是經典梯度下降演算法的研究成果，這是擾動梯度下降的結果，公式是一樣的，這裡我們沒有寫出那個關於d的對數的四次方的因子，現在我很懷疑四次方是不是最終的答案，我猜接下來的一兩年里會取得新進展，使得對數的階數降下來，達到一階對數或者二階對數，但是現在我們只能證明出對數的4次方這個結果。

這裡簡要地介紹一下此前的工作，最近的很多研究都是2014年 2015年 2016年做出的，並且到今天依舊十分熱門。如果你了解海森矩陣的話，在幻燈片的底部你可以看到一些經典的結果，在小維度問題中，不包括現代機器學習中的神經網路，你可能想要計算海森矩陣，然後計算它的特徵向量 它會告訴你脫離的方向，在這種情況下可以達到多快呢，最快速度可以達到1/e的1.5次方，只比埃普西隆的平方好一點點，不是特別好，所以這並不值得，你可以把這個結果先記下來。

在幻燈片頂部，你可以看到一系列引出我們這個結果的工作，Ge et al.證明收斂速度是維度的多項式複雜度，很美妙的結果，改變了我們一直認為指數級是最優結果的看法。Levy後來又將這個結果提升為d的三次方，更加精確，但仍然不是很令人滿意，當d達到100或者1000的話這個結果還是不夠好。然後我們的工作將它降到了對數級，所以我打算向你們展示，我不會在這裡證明它，論文中詳細證明了，你們可以去看看論文，對於數學功底很好的人我想說這實際上是一個非常有意思的理論，它運用了概率論，尤其是隨機擴散過程，所以實際上包含了一些微分幾何的東西，用概率理論證明。

這裡我只給你們一個概念，大家都知道鞍點周圍有一個餅狀區域，如果你進入了這個區域情況就會變得很糟糕，你會被困在裡面，你將會在鞍點上停留很長時間，這個時候有一些隨機擾動的話就可以把你踢出去，你想確保你不會一而再再而三地陷入困境，這個理論就是關於如何去遠離這個餅狀區域。

我們都知道餅狀區域的存在，並且我們可以分析它，但是為了得到一個更快的收斂速度，人們會用一個更加扁平的餅狀區域代替原先的，但扁平化會使得原先的區域變得更廣更大，它覆蓋了整個原先的餅狀區域，但現在變得很大。這就給出了多項式d的三次方的收斂速度，所以你不能這樣做，你不能用一個扁平的餅狀區域來代替它，你要用真正的餅狀區域，但這就涉及到一些很深奧的微分幾何，所以我們轉而使用擴散過程。

這個過程是指你從兩個點開始，這兩個點中間的距離正好是餅狀區域的寬度，只要這兩個點在餅狀曲面上位置任意，你會問，他們要多久才能分開，這是一種證明風格，用到了幾個內部隨機過程參數以及微分幾何，所以如果你真的想要去解釋這些東西的話，你肯定會用到這些數學知識。傳統意義上的應用優化理論還不夠，你需要用到高維幾何。我們雖然知道這一點，但我認為這是我們想要繼續深入所必須的一種觀念之一。

我來總結一下，如果我們不知道這個區域的形狀應該怎麼做。對我們來說，理解它是很重要的，但是我們已經證明了它很薄，我認為還需要進一步的研究，如果我們想把這個對數階數降到平方或者更低的話，或許我們需要更高深的微分幾何知識以及分析，但是我認為想到新的思路不會很困難。

擾動梯度下降，它確實能夠脫離鞍點，高效性只是它的一方面，所以這有些振奮人心，你不需要去計算二階信息，所以我們這種基於梯度的方法是很優秀的。現在我們分析下擾動版本 ，如果你分析隨機梯度會怎麼樣，你們對於加速演算法以及諸如此類的演算法有什麼看法，如果你們希望了解更多的話，這裡有一篇博客是我的學生Chi Jin和我在一周之前寫的，你可以就此繼續研究。非常感謝。

博客鏈接：

http://www.offconvex.org/2017/07/19/saddle-efficiency/

關注大數據文摘微信公眾號，後台回復「鞍點」獲取演講PPT合集

沒聽夠？參加今年北京的OReilly和Intel AI Conference還不晚~

本周五（3月9號）結束早鳥票優惠，掃碼使用大數據文摘專屬8折優惠碼WENZHAI報名，享受折上折??