延續上一篇部落格的内容，本文簡單介紹了梯度下降法、最速下降法、牛頓法、共轭方向法、拟牛頓法，這幾種方法的收斂速度。
目錄
- 梯度下降法
- 機器學習中的梯度下降法
- 最速下降法
- 二次型目标函數
- 牛頓法
- Levenberg-Marquardt 修正
- 梯度下降法和牛頓法誰快？
- 共轭方向法
- 什麼是共轭方向？
- 基本的共轭方向法
- 共轭梯度法
- 拟牛頓法
- 秩 1 修正公式
- References
- 相關部落格
經過前一篇部落格的簡單介紹，我們對導數、方向導數、梯度應該有一個較為清晰的認識。在知道梯度之後，我們就可以通過一些無限制的優化方法來求極值。
梯度下降法（Gradient descent），顧名思義，就是自變量沿着梯度向量的反方向進行移動，因為梯度的方向是上升的方向。
對于一個 \(R^m \to R\) 的函數 \(y = f(\bm x)\)，初始時 \(\bm x = \bm x^{(0)}\)，我們想要得到函數 \(y = f(\bm x)\) 的極小值點 \(\bm x^*\)，如果能夠求得 $ f(\bm x)$ 的梯度 \(\nabla f(\bm x)\)，那麼我們就可以用梯度下降法進行疊代求極小值的近似解。(還有不能求梯度的情況嗎？還真有，機器學習中如果輸入的資料有缺失，那麼 loss function 求出的梯度中仍然會含有未知數，這個時候可以用 EM 算法求解)
記自變量 \(\bm x\) 在第 \(k\) 疊代後的值為 \(\bm x^{(k)}\)，則自變量的更新公式為：
\[\bm x^{(k+1)} = \bm x^{(k)} - \alpha \cdot \nabla f(\bm x^{(k)})
\tag{1}
\]
式（1）中，\(\alpha\) 為步長，在深度學習中被稱為學習率（learning rate），控制了梯度下降速度的快慢。
梯度下降法和反向傳播算法是深度學習的基石，我們用梯度下降法更新神經網絡的參數，用反向傳播算法一層一層地将誤差由後向前傳播（就是用鍊式法則對 cost function 求偏導）。
如果我們定義 loss function 為
\[L(\bm w) = \bm g(\bm w; (\bm x, y)) = (y - \bm w^{\top} \bm x)^2
\tag{2}
那麼 cost function 就應該為
\[C(\bm w) = \frac{1}{n}\sum_{i = 1}^n L(\bm w) = \frac{1}{n} \sum_{i = 1}^n (y_i - \bm w^{\top} \bm x_i)^2
\tag{3}
其中 \(n\) 為一次性計算 loss 的樣本個數，在深度學習中常常就是一個 batch 的大小。
cost function/loss function 中，自變量是神經網絡的權重，而我們的輸入資料是已知的，這個時候我們就可以用用式（4）更新參數了：
\[\bm w^{(k+1)} = \bm w^{(k)} - \alpha \cdot \nabla C(\bm w^{(k)})
\tag{4}
如果輸入樣本 \((\bm x_i, y_i)\) 中含有未知數怎麼辦？資料缺失了怎麼辦，在深度學習中，我們可能會選擇剔除或者補全資料，然後再輸入到神經網絡中。如果不補全缺失值，對式（3）算梯度，梯度中會含有未知數，這樣式（4）沒法更新參數。
假設訓練集中含有 \(N\) 個資料樣本，我們對式（3）中的 \(n\) 取不同值（即一次性計算 loss 的樣本個數取不同值），會有不同的影響。如果 \(n = 1\)，這就是 stochastic gradient descent；如果 \(1 <n< N\)，這就是 mini-batch gradient descent；（mini-batch 的 batch size 一般不會很大。）如果 \(n = N\)，這就是 (batch) gradient descent。
最速下降法（Steepest descent）是梯度下降法的一種更具體實作形式，其理念為在每次疊代中選擇合适的步長 \(\alpha_k\)，使得目标函數值能夠得到最大程度的減少。
每一次疊代，沿梯度的反方向，我們總可以找到一個 \(\bm x^{(k+1)} = \bm x^{(k)} - \alpha_k \nabla f(\bm x^{(k)})\)，使得在這個方向上 \(f(\bm x^{(k+1)})\) 取最小值。即
\[\alpha_k = \mathop{\arg\min}_{\alpha \ge 0} f(\bm x^{(k)} - \alpha \nabla f(\bm x^{(k)}))
\tag{5}
有意思的是，最速下降法每次更新的軌迹都和上一次垂直。而且隻要梯度 \(\nabla f(\bm x^{(k)}) \not = 0\)，則 \(f(\bm x^{(k+1)}) < f(\bm x^{(k)})\)。（即梯度不等于 0 時，肯定會下降。）具體證明參見《最優化導論》 第8.2節。
圖 1 steepest descent
二次型指的是 \(\bm x^{\top} Q \bm x\)，\(Q\) 是一個對稱矩陣，\(\bm x\) 是列向量。當 \(Q\) 不是對稱矩陣時，我們可以做如下變換使其變為對稱矩陣：
\[\bm x^{\top} Q \bm x = \bm x^{\top} Q^{\top} \bm x = \bm x^{\top} ( \frac{1}{2}Q + \frac{1}{2}Q^{\top} )\bm x
當目标函數為二次型函數時，令目标函數為：
\[f(\bm x) = \frac{1}{2}\bm x^{\top} Q \bm x - \bm b^{\top} \bm x
梯度函數為：
\[\nabla f(\bm x) = Q\bm x - \bm b
為表示友善，令 \(\bm g^{(k)} = \nabla f(\bm x^{(k)})\)。
黑塞矩陣為：
\[F(\bm x) = Q = Q^{\top}
當目标函數為二次型函數時，我們可以算得每一步的步長取值為：
\[\alpha_k = \frac{\bm g^{(k) \top} \bm g^{(k)}}{\bm g^{(k) \top}Q \bm g^{(k)}}
其中，梯度為 \(\bm g^{(k)} = \nabla f(\bm x^{(k)}) = Q\bm x^{(k)} - \bm b\)。
是以當目标函數為二次型函數時，最速下降法的疊代公式為：
\[\bm x^{(k+1)} = \bm x^{(k)} - \frac{\bm g^{(k) \top} \bm g^{(k)}}{\bm g^{(k) \top}Q \bm g^{(k)}} \bm g^{(k)}
在确定搜尋方向時，梯度下降和最速下降隻用到了目标函數的一階導數（梯度），而牛頓法（Newton's method）用到了二階（偏）導數。
Newton's method (sometimes called the Newton-Raphson method) uses first and second derivatives and indeed does perform better than the steepest descent method if the initial point is close to the minimizer.
圖 2 Newton's method
牛頓法的基本思路是在每次疊代中，利用二次型函數來局部近似目标函數 \(f\)，并求解近似函數的極小點作為下一個疊代點，牛頓法自變量 \(\bm x\) 的更新公式為：
\[\bm x^{(k+1)} = \bm x^{(k)} - F(\bm x^{(k)})^{-1}\nabla f(\bm x^{(k)})
其中 \(F(\bm x^{(k)})^{-1}\) 為二階偏導數矩陣的逆（即 黑塞矩陣的逆）。（為什麼更新公式是這樣的？可以将 \(f(\bm x)\) 在 \(\bm x^{(k)}\) 處進行二階泰勒展開，然後求導。）
Newton's method has superior convergence properties if the starting point is near the solution. However, the method is not guaranteed to converge to the solution if we start far away from it (in fact, it may not even be well-defined because the Hessian may be singular).
當起始點 \(\bm x^{(0)}\) 離極值點 \(\bm x^*\) 足夠近的時候，式（6）的更新公式沒有問題。但是，當 \(\bm x^{(0)}\) 離極值點 \(\bm x^*\) 較遠時，我們并不能保證牛頓法能收斂到極值點。甚至，牛頓法可能都不是一個 descent 的方法，即可能 \(f(\bm x^{(k+1)}) \ge f(\bm x^{(k)})\)。幸運的是可以做一點修改，確定牛頓法是一個 descent 的方法。（黑塞矩陣如果不是正定的，那就要對牛頓法進行修正，如 Levenberg-Marquardt 修正。）
如果 黑塞 矩陣正定（\(F(\bm x^{(k)}) > 0\) ），并且 \(\nabla f(\bm x^{(k)}) \not = 0\)，那麼我們的搜尋的方向為
\[\bm d^{(k)} = - F(\bm x^{(k)})^{-1}\nabla f(\bm x^{(k)}) = \bm x^{(k+1)} - \bm x^{(k)}
要想從 \(\bm x^{(k)}\) 到 \(\bm x^{(k+1)}\) 是 descent direction，隻要存在一個 \(\overline \alpha > 0\)，使得所有 \(\alpha \in (0, \overline \alpha)\)，滿足 \(f(\bm x^{(k)} + \alpha \bm d^{(k)}) < f(\bm x^{(k)})\)。
此時牛頓法的更新公式為：
\[\bm x^{(k+1)} = \bm x^{(k)} - \alpha_kF(\bm x^{(k)})^{-1}\nabla f(\bm x^{(k)})
對于 \(\alpha_k\)，我們也可以在方向 \(\bm d^{(k)}\) 上進行線性搜尋，使得 \(\alpha_k = \mathop{\arg\min}_{\alpha \ge 0} f(\bm x^{(k)} - \alpha F(\bm x^{(k)})^{-1}\nabla f(\bm x^{(k)}))\)。
這個時候，梯度下降法和牛頓法除了一個黑塞矩陣外，是不是超級像了。如果黑塞矩陣不是正定的，那就要對牛頓法進行修正，如 Levenberg-Marquardt 修正。
如果 黑塞矩陣 $ F(\bm x^{(k)})$ 不正定，那麼搜尋方向 \(\bm d^{(k)} = - F(\bm x^{(k)})^{-1}\nabla f(\bm x^{(k)})\) 可能不會是下降方向。 牛頓法的 Levenberg-Marquardt 修正可以解決這個問題：
\[\bm x^{(k+1)} = \bm x^{(k)} - \alpha_k(F(\bm x^{(k)}) + \mu_k \bm I)^{-1}\nabla f(\bm x^{(k)})
其中，\(\mu_k \ge 0\)，\(\bm I\) 為機關矩陣。在該修正中， $ F(\bm x^{(k)})$ 可以不正定，但是 \(\bm G = F(\bm x^{(k)}) + \mu_k \bm I\) 需要是正定的，是以，取适當的 \(\mu_k\)，使得 \(\bm G\) 正定即可。（矩陣正定，目前僅當所有特征值大于 0。）
\(\mu_k\) 過大也不行，否則就相當于步長取了很小的值。（逆過小或者是分母過大。）
可能會有一個疑問，梯度下降法中梯度的反方向不是目前點下降最快的方向嗎，為什麼牛頓法會收斂更快，牛頓法的更新方向更好嗎？
- 牛頓法是二階收斂，梯度下降法是一階收斂，是以牛頓法就更快。
- 更通俗地，梯度下降法隻從目前位置選擇一個坡度最大的方向走一步，而牛頓法在選擇方向時，不僅會考慮坡度是否夠大，還會考慮走了一步後，坡度是否會變得更大。
- 從幾何上說，牛頓法就是用一個二次曲面去拟合目前位置的的局部曲面，而梯度下降法用的是一個平面去拟合，通常情況下，二次曲面的拟合會比平面更好，是以牛頓法選擇的下降路徑會更符合真實的最優下降路徑。
詳情參見 最優化問題中，牛頓法為什麼比梯度下降法求解需要的疊代次數更少？ -- 大餅土博。
圖 3 A comparison of gradient descent (green) and Newton's method (red) for minimizing a function (with small step sizes).
Newton's method uses curvature information (i.e. the second derivative) to take a more direct route.
共轭方向法的性能優于最速下降法，但不如牛頓法。
共轭方向法具有以下特性：
- 對于 n 維二次型問題，能夠在 n 步之内求得結果；
- 作為共轭方向法的典型代表，共轭梯度法不需要計算黑塞矩陣；
- 不需要存儲 \(n \times n\) 的矩陣，也不需要對其求逆。
考慮一個二次型函數 \(f(\bm x) = \frac{1}{2}\bm x^{\top} Q \bm x - \bm b^{\top} \bm x\)，其中 \(\bm x \in \mathbb{R}^n\)，\(Q = Q^{\top}>0\)。（這裡沒有考慮非二次型問題中的共轭方向法/共轭梯度法，有需要的直接參考 《最優化導論》 10.4 節）
設 \(Q\) 為 \(n \times n\) 的正定對稱實矩陣，對于方向 \(\bm d^{(0)},\bm d^{(1)},\bm d^{(2)},... ,\bm d^{(n-1)}\)，如果對于所有的 \(i \not = j\)，有 \(d^{(i) \top} Q d^{(j)} = 0\)，則稱它們是關于 \(Q\) 共轭的，且是線性無關的。
給定初始點 \(\bm x^{(0)}\) 和一組關于 \(Q\) 的共轭方向 \(\bm d^{(0)},\bm d^{(1)},\bm d^{(2)},... ,\bm d^{(n-1)}\)，疊代公式如下：（\(k \ge 0\) 表示疊代次數）
\[\bm g^{(k)} = \nabla f(\bm x^{(k)}) = Q\bm x^{(k)} - \bm b \\
\alpha_k = - \frac{\bm g^{(k) \top} \bm d^{(k)}}{\bm d^{(k) \top} Q \bm d^{(k)}} \\
\bm x^{(k+1)} = \bm x^{(k)} + \alpha_k \bm d^{(k)}
上式和最速下降法的公式很像，當更新方向為梯度的方向，即 \(\bm d^{(k)} = - \bm g^{(k)}\) 時，共轭方向法和最速下降法就長得一模一樣了。當然，這一般是不可能的，共轭方向法要求更新方向是共轭的。
上式中 \(\alpha_k\) 的更新公式有個負号，但這個數是個正數，将 \(\bm d^{(k)} = - \bm g^{(k)}\) 帶入就可以知道。
共轭方向法的計算效率很高，但前提是給定一組 \(Q\) 共轭方向。共轭梯度法不需要提前給定一組 \(Q\) 共轭方向，而是随着疊代的進行，逐一産生 \(Q\) 共轭方向。
作為共轭方向法的典型代表，共轭梯度法不同之處在于其 \(Q\) 共轭方向的擷取，每一次疊代，我們需要當場生成下一次疊代的方向：
\[\bm d^{(k+1)} = - \bm g^{(k+1)} + \beta_k \bm d^{(k)}, k = 0,1,2,...
按照如下方式選擇系數 \(\beta_k\)，可以使得新生成的方向 \(\bm d^{(k+1)}\) 和之前的方向 \(\bm d^{(0)}, \bm d^{(1)}, ..., \bm d^{(k)}\) \(Q\) 共轭：
\[\beta_k = \frac{\bm g^{(k+1) \top} Q \bm d^{(k)}}{\bm d^{(k) \top} Q \bm d^{(k)}}
對于初始方向 \(\bm d^{(0)}\)，直接用負梯度即可，即 \(\bm d^{(0)} = - \bm g^{(0)}\)。
牛頓法需要計算黑塞矩陣 \(F(\bm x^{(k)})\) 并且計算它的逆 \(F(\bm x ^ {(k)})^{ -1}\)，求逆并不是很簡單。
為了避免 \(F(\bm x ^ {(k)})^{ -1}\) 這種矩陣求逆運算，可以通過設計 \(F(\bm x ^ {(k)})^{ -1}\) 的近似矩陣來代替 \(F(\bm x ^ {(k)})^{ -1}\)，這就是拟牛頓法的基本思路。
在拟牛頓法中，\(F(\bm x ^ {(k)})^{ -1}\) 近似矩陣 \(\bm H_k\) 的建構隻需要用到 目标函數值 和 梯度。
拟牛頓法的更新公式為：
\[\bm x^{(k+1)} = \bm x^{(k)} - \alpha_k \bm H_k \nabla f(\bm x^{(k)})
拟牛頓法的更新方向 \(\bm d^{(k)} = -\bm H_k \nabla f(\bm x^{(k)})\)，當目标函數為二次型時，這些方向其實也是關于 \(Q\) 共轭的，即拟牛頓法也是一種共轭方向法。
拟牛頓法的關鍵在于求出 \(\bm H_{k+1}\)，給出 \(\bm H_k\)、梯度 \(f(\bm x^{(k)})\)、\(\bm d^{(k)}\)、\(\alpha_k\)，找到 \(\bm H_{k+1}\) 的遞推式，那麼在疊代過程中就不需要涉及到黑塞矩陣也不會求逆。
\(\bm H_{k+1}\) 的遞推式為：
\[\boldsymbol{H}_{k+1}=\boldsymbol{H}_{k}+\frac{\left(\Delta \boldsymbol{x}^{(k)}-\boldsymbol{H}_{k} \Delta \boldsymbol{g}^{(k)}\right)\left(\Delta \boldsymbol{x}^{(k)}-\boldsymbol{H}_{k} \Delta \boldsymbol{g}^{(k)}\right)^{\top}}{\Delta \boldsymbol{g}^{(k) \top}\left(\Delta \boldsymbol{x}^{(k)}-\boldsymbol{H}_{k} \Delta \boldsymbol{g}^{(k)}\right)}
其中，\(\Delta x^{(k)}=\alpha_{k} d^{(k)}\)，\(\Delta \boldsymbol{g}^{(k)}=\boldsymbol{g}^{(k+1)}-\boldsymbol{g}^{(k)}\)。
\(\bm H_0\) 可以取任一對稱正定實矩陣。
Edwin K. P. Chong, Stanislaw H. Zak-An Introduction to Optimization, 4th Edition
最優化問題中，牛頓法為什麼比梯度下降法求解需要的疊代次數更少？ -- 大餅土博
Newton's method in optimization - Wikipedia
【機器學習之數學】01 導數、偏導數、方向導數、梯度
【機器學習之數學】02 梯度下降法、最速下降法、牛頓法、共轭方向法、拟牛頓法
【機器學習之數學】03 有限制的非線性優化問題——拉格朗日乘子法、KKT條件、投影法
作者：wuliytTaotao
出處：https://www.cnblogs.com/wuliytTaotao/
本作品采用知識共享署名-非商業性使用-相同方式共享 4.0 國際許可協定進行許可，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接。