梯度下降（Gradient Descent）（一）

  梯度下降法（gradient descent）或最速下降法（steepest descent）是求解無限制優化問題的一種最常用的方法，實作簡單，屬于一階優化算法，也是疊代算法。

1.梯度

  在微積分中，對多元函數的參數求偏導數，把求得的各個參數的偏導數以向量的形式寫出來，就是梯度。比如函數 f(x,y) f ( x , y ) ，分别對 x,y x , y 求偏導數，求得的梯度向量就是 (∂f∂x,∂f∂y)T ( ∂ f ∂ x , ∂ f ∂ y ) T ，記為 gradf(x,y) g r a d f ( x , y ) 或 ∇f(x,y) ∇ f ( x , y ) 。在點 (x0,y0) ( x 0 , y 0 ) 處的具體梯度向量就是 (∂f∂x0,∂f∂y0)T ( ∂ f ∂ x 0 , ∂ f ∂ y 0 ) T ，或 ∇f(x0,y0) ∇ f ( x 0 , y 0 ) 。

  梯度向量的一般表示可以寫成：

∇f(x1,x2,…,xn)=(∂f∂x1,∂f∂x2,…,∂f∂xn)T ∇ f ( x 1 , x 2 , … , x n ) = ( ∂ f ∂ x 1 , ∂ f ∂ x 2 , … , ∂ f ∂ x n ) T

  從幾何意義上講，函數上某一點的梯度向量，就是函數變化增加最快的地方。具體來說，對于函數 f(x,y) f ( x , y ) ，在點 (x0,y0) ( x 0 , y 0 ) 沿着梯度向量的方向，即 (∂f∂x0,∂f∂y0)T ( ∂ f ∂ x 0 , ∂ f ∂ y 0 ) T ，是 f(x,y) f ( x , y ) 增加最快的地方。或者說沿着梯度向量的方向，更容易找到函數的極大值。反過來說，沿着梯度向量相反的方向，即 −(∂f∂x0,∂f∂y0)T − ( ∂ f ∂ x 0 , ∂ f ∂ y 0 ) T ， f(x,y) f ( x , y ) 減少最快，更容易找到函數的極小值。

2.梯度下降

  假設 f(x) f ( x ) 是 Rn R n 上具有一階連續偏導數的函數，要求解的無限制最優化問題是：

minx∈Rnf(x) m i n x ∈ R n f ( x )

x∗ x ∗ 表示目标函數的極小點。下面我們考慮采用梯度下降法來求解這個問題。

  根據上一節關于梯度的闡述，我們已經了解，負梯度方向是使函數值下降最快的方向，基于此，可以得到梯度下降法的原理：選取适當的初值 x0 x 0 ，不斷疊代，在疊代的每一步，以負梯度方向更新 x x 的值，進行目标函數的極小化，直到收斂。完整的算法描述如下：

輸入：目标函數f(x)f(x)，計算精度 ε ε ；

輸出： f(x) f ( x ) 的極小值點 x∗ x ∗ ；

(1).取初始值 x(0)∈Rn x ( 0 ) ∈ R n ，置 k=0 k = 0 ；

(2).計算 f(xk) f ( x k ) ；

(3).計算梯度 gk g k ，若 ||gk||<ε | | g k | | < ε ，停止疊代，令 x∗=x(k) x ∗ = x ( k ) ；否則，轉(4)；

(4).置 x(k+1)=x(k)−αgk x ( k + 1 ) = x ( k ) − α g k ，計算 f(x(k+1)) f ( x ( k + 1 ) ) ，當 ||f(x(k+1))−f(x(k))||<ε | | f ( x ( k + 1 ) ) − f ( x ( k ) ) | | < ε 或 ||x(k+1)−x(k)||<ε | | x ( k + 1 ) − x ( k ) | | < ε 時，停止疊代，令 x∗=x(k) x ∗ = x ( k ) ；否則，轉(3)；

其中， α α 是疊代步長，或稱學習率（learning rate），在每次疊代中， α α 是可變的。值得注意的是， α α 的取值很有講究，取值太大，容易跨過極小值點，取值太小，收斂太慢。是以，需不斷測試，直至找到一個最合适的 α α 。

  下面我們用一張圖來形象化地表述梯度下降法：

  這裡假設 f f 定義在平面上，并且函數圖像是一個碗形。藍色的曲線是等高線（水準集），即函數ff為常數的集合構成的曲線。紅色的箭頭指向該點梯度的反方向（一點處的梯度方向與通過該點的等高線垂直）。沿着梯度下降方向，将最終到達碗底，即函數 f f <script type="math/tex" id="MathJax-Element-43">f</script>的極小值點。

3.特點和問題

特點

1. 對輸入向量進行歸一化處理，可以讓梯度下降更好更快地收斂；

問題：

1. 隻有當目标函數是凸函數時，梯度下降法的解是全局最優解，一般情況下，其解不保證是全局最優解；
2. 靠近極小值時速度減慢；
3. 如何确定學習率，可以參考這篇文章；

參考文獻

[1] 《統計學習方法》

[2] https://baike.baidu.com/item/%E6%A2%AF%E5%BA%A6/13014729

[3] https://zhuanlan.zhihu.com/p/31074506

[4] http://blog.csdn.net/xiazdong/article/details/7950084

[5] https://www.cnblogs.com/pinard/p/5970503.html

[6] https://www.cnblogs.com/zhenggege/p/7210755.html

[7] https://www.zhihu.com/question/54097634

[8] https://www.cnblogs.com/keguo/p/6244253.html

[9] https://zh.wikipedia.org/wiki/%E6%A2%AF%E5%BA%A6%E4%B8%8B%E9%99%8D%E6%B3%95

以上為本文的全部參考文獻，對原作者表示感謝。