當一個最佳化問題其中的 cost function F(x) 或是約束條件包含非線性方程式時，便無法用上一篇
文章中提到的方法來解決。這種問題稱為非線性最佳化 Nonlinear Optimization 問題，接下來幾篇文章會簡介一些解決 Nonlinear Optimization 的演算法。
Nonlinear Optimization 問題簡介
我們想要最小化一個函數 \(F(x_1, x_2,...,x_n)\)，從微積分課中我們知道要找到一組 \(x^*\) 使得 F 對於所有 x 的偏微分等於零，也就是 \(\partial F / \partial x_i = 0\)。在最佳化問題中我們通常假設 F 函數平滑且可微分，因此我們能從泰勒展開式出發來解最佳化問題：
\[
F(x + \Delta x)\approx F(x) + (\Delta x)^T \triangledown F + \frac{1}{2}(\Delta x)^T H (\Delta x)
\]
其中\( \triangledown F\) 為梯度 gradient：
\[
\triangledown F \equiv F'(x) =\begin{bmatrix}
\frac{\partial F}{x_1}
\\
\vdots
\\
\frac{\partial F}{x_n}
\end{bmatrix}
\]
H 為 Hessian matrix：
\[
H\equiv F''(x)=
\begin{bmatrix}
\frac{\partial^2 F}{\partial x_i \partial x_j}
\end{bmatrix}
\]
梯度下降法 Gradient Descent
梯度下降法的精神就是每次都往降低梯度最陡的方向走進而走到函數的極小值。有一個問題是為什麼一定得往最陡的方向走，往其他任何可以降低梯度的方向走無法達成目的嗎？這個問題等到下面解釋完牛頓法後再來討論。 Gradient Descent 的式子為：
\[
x_{k+1} = x_k - s_k \triangledown F(x_k)
\]
其中 \(\triangledown F(x_k)\) 就是 gradient，\(s_k\) 代表每次一步要走多遠，也就是機器學習中常看到的 learning rate。
牛頓法 Newton's method
上面提到最小化一個函數的目標是找到一組 \(x^*\) 使得 F 對於所有 x 的偏微分等於零，也就是 \(\triangledown F = 0\)。牛頓法的精神是針對目前的點 \(x_k\) 以及目前的梯度 \(\triangledown F(x_k)\) ，想要找到 \(x_{k+1}\) 使得 \(\triangledown F(x_{k+1}) = 0\)，而從泰勒展開式我們可以得到以下式子：
\[
\triangledown F(x_{k+1}) \approx \triangledown F(x_{k}) + H(x_k)(x_{k+1} - x_k) = 0
\]
上式中 H 為 Hessian matrix，可以看作是梯度函數 \( \triangledown F\) 的微分。（註：也就是說 Hessian matrix 為梯度函數 \( \triangledown F\) 的 Jacobian [1]。）
從上式可以推導至：
\[
\Delta x = (x_{k+1} - x_k) = -H(x_k)^{-1}\triangledown F(x_{k})
\]
也就是說牛頓法就是利用以下式子一直更新 x：
\[
x_{k+1} = x_k - H(x_k)^{-1}\triangledown F(x_{k})
\]
梯度下降法與牛頓法的比較
牛頓法的收斂速度比較快
梯度下降法的式子是將 \(s_k\) 乘以 \(\triangledown F(x_k)\)，而牛頓法是將 \(H^{-1}\) 乘以 \(\triangledown F(x_k)\)。可以看出來兩者 x 的移動方向不同，梯度下降法是沿著 \(\triangledown F(x_k)\) 更新 x 的值，而牛頓法是沿著 \(H(x_k)^{-1}\triangledown F(x_{k})\) 的方向更新。從物理直覺上來說，梯度下降法是一階收斂，只考慮目前所在位置找到最陡的地方走一步，而牛頓法是二階收斂，同時還會考慮走了一步之後坡度是否會變得更大，因此牛頓法的收斂速度會比梯度下降法還要快。
大部分機器學習演算法都是使用梯度下降法
雖然牛頓法的收斂速度比較快，但是由於要計算 Hessian matrix 的反矩陣，其時間與空間的計算複雜度比梯度下降法大得多。因此實務上大家都採用梯度下降法，或是想辦法近似 Hessian matrix 的反矩陣，我們在下一篇文章會介紹這類型的演算法。
參考資料
[1]
https://en.wikipedia.org/wiki/Jacobian_matrix_and_determinant
沒有留言:
張貼留言