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