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