算法優(yōu)化的方法：避開鞍點

　凸函數(shù)比較簡單——它們通常只有一個局部最小值。非凸函數(shù)則更加復雜。在這篇文章中，我們將討論不同類型的臨界點（ critical points） ，當你在尋找凸路徑（ convex path ）的時候可能會遇到。特別是，基于梯度下降的簡單啟發(fā)式學習方法，在很多情形下會致使你在多項式時間內陷入局部最小值（ local minimum ） 。
　　臨界點類型
　　
　　為了最小化函數(shù)f:Rn→R，最流行的方法就是往負梯度方向前進?f（x）（為了簡便起見，我們假定談及的所有函數(shù)都是可微的），即：
　　y=x?η?f（x），
　　其中η表示步長。這就是梯度下降算法（gradient descentalgorithm）。
　　每當梯度?f（x）不等于零的時候，只要我們選擇一個足夠小的步長η，算法就可以保證目標函數(shù)向局部最優(yōu)解前進。當梯度?f（x）等零向量時，該點稱為臨界點（ critical point），此時梯度下降算法就會陷入局部最優(yōu)解。對于（強）凸函數(shù)，它只有一個臨界點（critical point），也是全局最小值點（global minimum）。
　　然而，對于非凸函數(shù)，僅僅考慮梯度等于零向量遠遠不夠。來看一個簡單的實例：
　　y=x12?x22.
　　當x=（0，0）時，梯度為零向量，很明顯此點并不是局部最小值點，因為當x=（0，?）時函數(shù)值更小。在這種情況下，（0，0）點叫作該函數(shù)的鞍點（saddle point）。
　　為了區(qū)分這種情況，我們需要考慮二階導數(shù)?2f（x）——一個n×n的矩陣（通常稱作Hessian矩陣），第i，j項等于
　　
　　。當Hessian矩陣正定時（即對任意的u≠0，有u??2f（x）u 》 0恒成立），對于任何方向向量u，通過二階泰勒展開式
　　
　　，可知x必定是一個局部最小值點。同樣，當Hessian矩陣負定時，此點是一個局部最大值點；當Hessian矩陣同時具有正負特征值時，此點便是鞍點。
　　對于許多問題，包括 learning deep nets，幾乎所有的局部最優(yōu)解都有與全局最優(yōu)解（global optimum）非常相似的函數(shù)值，因此能夠找到一個局部最小值就足夠好了。然而，尋找一個局部最小值也屬于NP-hard問題（參見 Anandkumar，GE 2006中的討論一節(jié)）。實踐當中，許多流行的優(yōu)化技術都是基于一階導的優(yōu)化算法：它們只觀察梯度信息，并沒有明確計算Hessian矩陣。這樣的算法可能會陷入鞍點之中。
　　在文章的剩下部分，我們首先會介紹，收斂于鞍點的可能性是很大的，因為大多數(shù)自然目標函數(shù)都有指數(shù)級的鞍點。然后，我們會討論如何對算法進行優(yōu)化，讓它能夠嘗試去避開鞍點。
　　對稱與鞍點
　　許多學習問題都可以被抽象為尋找k個不同的分量（比如特征，中心…）。例如，在 聚類問題中，有n個點，我們想要尋找k個簇，使得各個點到離它們最近的簇的距離之和最小。又如在一個兩層的 神經網(wǎng)絡中，我們試圖在中間層尋找一個含有k個不同神經元的網(wǎng)絡。在我 先前的文章中談到過張量分解（tensor decomposition），其本質上也是尋找k個不同的秩為1的分量。
　　解決此類問題的一種流行方法是設計一個目標函數(shù)：設x1，x2，…，xK∈Rn表示所求的中心（centers），讓目標函數(shù)f（x1，…，x）來衡量函數(shù)解的可行性。當向量x1，x2，…，xK是我們需要的k的分量時，此函數(shù)值會達到最小。
　　這種問題在本質上是非凸的自然原因是轉置對稱性（permutation symmetry）。例如，如果我們將第一個和第二個分量的順序交換，目標函數(shù)相當于：f（x1，x2，…，xk）= f（x1，x2，…，xk）。
　　然而，如果我們取平均值，我們需要求解的是
　　
　　，兩者是不等價的！如果原來的解是最優(yōu)解，這種均值情況很可能不是最優(yōu)。因此，這種目標函數(shù)不是凸函數(shù)，因為對于凸函數(shù)而言，最優(yōu)解的均值仍然是最優(yōu)。
　　
　　所有相似解的排列有指數(shù)級的全局最優(yōu)解。鞍點自然會在連接這些孤立的局部最小值點上出現(xiàn)。下面的圖展示了函數(shù)y = x14?2x12+ X22：在兩個對稱的局部最小點（?1，0）和（1，0）之間，點（0，0）是一個鞍點。