梯度下降or擬牛頓法？

01-04

為什麼在神經網路的訓練中，很多人都採用類似與sgd，rmsprop，adgrad等優化方法。而在訓練邏輯回歸等模型的時候採用各種擬牛頓的方法？為什麼他們不在神經網路中也使用擬牛頓法？

在大規模數據中，能夠使用的擬牛頓法也就只有L-BFGS。其他方法均需要維持一個完整的approximated Hessian matrix或者它的逆矩陣，在大規模數據中顯然不現實。

雖然也有工作在神經網路中使用L-BFGS的，但主流還是SGD。雖然我個人非常喜歡L-BFGS這個演算法（我是做optimization的），但這個演算法在神經網路中使用有幾個這樣的問題（在機器學習中都用的是它的隨機版本stochastic L-BFGS，我下面也說的是這個）：

1. 收斂速度雖然很快，但只有在迭代點足夠靠近最優值點時才會體現出優勢。在大部分機器學習應用中，對最優值精度要求並不高，比如 $10^{-3}$ 甚至 $10^{-2}$ 這個量級一般就足夠了。在這個精度，與SGD相比，L-BFGS帶來的加速效果很有可能還不如額外計算帶來的overhead大。

2. 很難調參。SGD只有一個步長參數，步長只要夠小就一定能收斂，而且現在有一些自動調整步長的方法，不需要怎麼調參也能跑的還不錯。但用過stochastic L-BFGS的就知道，先不說收斂不收斂，參數稍微設偏大或者偏小一點都很容易在計算時溢出。在傳統的BFGS中，有一個定理是說經過若干步迭代後，取1的固定步長一定能保證收斂。但非常不幸的是，stochastic版本沒有這個性質，參數一大堆，還基本只能靠手調。

3. Logistic regression是convex的，神經網路是non-convex的。SGD在兩種情況下都能保證收斂（雖然在後一種只能保證收斂到一個stationary point，並不一定是局部最優值點）。但是，L-BFGS在non-convex下是有可能不收斂的。

神經網路優化問題有三個特點：大數據（樣本多），高維問題（參數極多），非凸

牛頓和擬牛頓法在凸優化情形下，如果迭代點離全局最優很近時，收斂速率快於gd。

然而：

大數據帶來的問題：因為數據量大，從計算上來說不可能每一次迭代都使用全部樣本計算優化演算法所需的統計量（梯度，Hessian等等），因此只能基於batch來計算，從而引入了雜訊（sgd）。梯度的估計本身已經帶了雜訊，利用有雜訊的梯度和歷史梯度用近似公式逼近Hessian（L-BFGS），則雜訊很可能更大，而且微分本身時放大雜訊的。所以即使多花費了計算量，擬牛頓的效果未必會更好。
高維帶來的問題：因為參數極多，所以Hessian陣也會非常巨大，無法顯式計算和存儲，因此牛頓法幾乎不可行，只能嘗試用L-BFGS。在文本應用中，第一層embedding的參數量佔整體參數量的絕大多數，因此第一層參數的計算速度與空間消耗幾乎決定了整體消耗。由於文本輸入是高維稀疏的，因此在每一個batch下第一層的梯度也是稀疏的（只有該樣本出現的字（詞）所連接的那些權值的梯度是非零的），因此sgd每一步迭代不需要把第一層所有的參數的梯度進行通信，而只需要通信極小部分的非零的梯度，這樣稀疏更新會大大加快計算速度（通信量大大減小，因此通信速度增加）。而牛頓法或者擬牛頓法 $p=-H^{-1}g$ ，本質上是使用幾乎稠密的矩陣 $H^{-1}$ （Hessian或其近似），對梯度的各維度信息進行混合、整定，因此實際的更新 $p$ 幾乎不稀疏，無法使用稀疏更新，會大大減慢計算速度。從直觀上講，sgd相當於樣本里出現的每個字或詞，其信息只利用在與該字或詞直接相關的網路參數的更新。因此如果一個字或詞始終沒出現，那麼其對應的網路就完全沒有學習任何東西，其權值在最後還是等於初始化後的值。牛頓法或擬牛頓法的思路則是不同字詞之間是存在關聯的，一個字或詞的信息，應該同時分享並貢獻到其他字詞的參數的更新。這個在小數據低維問題時能更好的利用數據，但是在大數據的情形下，基本每個字詞都會有足夠的樣本來貢獻信息，而過數據的速度則可能成了影響效果的瓶頸。例如如果sgd比牛頓快十倍，那麼sgd能在同樣的時間內見到十倍於牛頓的數據，那麼這些多出來的新鮮的信息往往就能帶來更大的收益。
非凸帶來的問題：非凸情形下，牛頓或擬牛頓法會被鞍點吸引。或者更直接的說，由於非凸， $H$ 非正定，導致 $-H^{-1}g$ 不再是下降方向（ $-g^TH^{-1}g ot<0$ ），每一步迭代反倒可能不降反升。當然，我們可以通過對一些維度做修正（Hessian modification），但是在高維情形，鞍點數量極多，而且 $H$ 本身是帶雜訊的估計，因此修正未必是可行之路。

但是sgd本身也不是完美的。sgd的更新公式是 $p=-alpha g$ ，步長是按同一scale統一作用在各維度上的。但是在實際問題中，各維度本身的scale是不一樣的（想像一下一個很扁的橢圓等高面），因此需要分維度作整定，這就導致了adagrad,adadelta,rmsprop,adam等一系列adaptive learning rate方法，其本質都是 $p=-D^{-1}g$ ，其中 $D$ 是一個對角矩陣，並且 $D_{ii}$ 嘗試逼近 $sqrt{partial^2f/partial x_i^2}$ （或其類似物），即根號下第i個方向的曲率。這幾種方法差別基本在於利用歷史梯度估計曲率的公式設計。那麼對問題（1）來說，更好的估計使得這種二階導信息帶的雜訊更少，而且某一方向即使估計差了，其影響也只限在那一維，影響較小。對問題（2），由於只多估計了一個對角線的參數，所以相對sgd只是放大了一倍，實際中完全可以承受。對問題（3），由於保證了對角元都為正，所以是下降方向。所以實踐中往往即不使用LBFGS，也不使用sgd，而是使用adaptive learning rate系列方法。據我的實驗經驗，adam和adadelta效果最好。

神經網路的優化方法還有很大的探索空間，尤其現在seq2seq的一系列複雜模型（NTM, attention等），其計算複雜度越來越高，對優化方法的要求也越來越高，還有待更具突破性的優化方法的出現。