- 梯度下降法(Gradient descent)是一個一階最優化算法,通常也稱為最速下降法。 要使用梯度下降法找到一個函數的局部極小值,必須向函數上目前點對應梯度(或者是近似梯度)的反方向的規定步長距離點進行疊代搜尋。如果相反地向梯度正方向疊代進行搜尋,則會接近函數的局部極大值點;這個過程則被稱為梯度上升法。
- 本文将從最優化問題談起,回顧導數與梯度的概念,引出梯度下降的資料推導;概括三種梯度下降方法的優缺點,并用Python實作梯度下降(附源碼)。
1 最優化問題
- 最優化問題是求解函數極值的問題,包括極大值和極小值。
- 微積分為我們求函數的極值提供了一個統一的思路:找函數的導數等于0的點,因為在極值點處,導數必定為0。這樣,隻要函數的可導的,我們就可以用這個萬能的方法解決問題,幸運的是,在實際應用中我們遇到的函數基本上都是可導的。
- 機器學習之類的實際應用中,我們一般将最優化問題統一表述為求解函數的極小值問題,即:
\[min_xf(x)
\]
- 其中\(x\)稱為優化變量,\(f\)稱為目标函數。極大值問題可以轉換成極小值問題來求解,隻需要将目标函數加上負号即可:
\[min_x{-f(x)}
2 導數與梯度
- 梯度是多元函數對各個自變量偏導數形成的向量。多元函數的梯度表示:
\[\nabla f(x) = \left( \frac{\partial f}{\partial x_1},...,\frac{\partial f}{\partial x_n} \right)^T
- 如果Hessian矩陣正定,函數有極小值;如果Hessian矩陣負定,函數有極大值;如果Hessian矩陣不定,則需要進一步讨論。
- 如果二階導數大于0,函數有極小值;如果二階導數小于0,函數有極大值;如果二階導數等于0,情況不定。
問題:為何不直接求導,令導數等于零去求解?
- 直接求函數的導數,有的函數的導數方程組很難求解,比如下面的方程:
\[f(x,y) = x^5 + e^{x}{y}- y^3 + 10y^2 - 100\sin(xy)-2x^2
3 梯度下降的推導過程
- 回顧一下泰勒展開式
\[f(x) = \frac{f(x_0)}{0!} + \frac{f'(x_0)}{1!}(x-x_0) + \frac{f''(x_0)}{2!}(x-x_0)^2 + ... + \frac{f^{(n)}(x_0)}{n!}(x-x_0)^n + R_n(x)
- 多元函數\(f(x)\)在x處的泰勒展開:
\[f(x + \Delta x) = f(x) + f'(x)\Delta x + \frac{1}{2}f''(x) \Delta x^2 + ...
3.1 數學推導
目标是求多元函數\(f(x)\)的極小值。梯度下降法是通過不斷疊代得到函數極小值,即如能保證\(f(x +\Delta x)\)比\(f(x)\)小,則不斷疊代,最終能得到極小值。想象你在山頂往山腳走,如果每一步到的位置比之前的位置低,就能走到山腳。問題是像哪個方向走,能最快到山腳呢?
由泰勒展開式得:
\[f(x + \Delta x) - f(x) = (\nabla f(x))^T \Delta x + o(\Delta x)
如果\(\Delta x\)足夠小,可以忽略\(o(\Delta x)\),則有:
\[f(x + \Delta x) - f(x) \approx (\nabla f(x))^T \Delta x
于是隻有:
\[(\nabla f(x))^T \Delta x < 0
能使
\[f(x + \Delta x) < f(x)
因為\(\nabla f(x)\)與\(\Delta x\)均為向量,于是有:
\[(\nabla f(x))^T \Delta x = \| \nabla f(x)\|\|\Delta x\|cos\theta
其中,\(\theta\)是向量\(\nabla f(x)\)與\(\Delta x\)的夾角,\(\| \nabla f(x)\|\)與\(\|\Delta x\|\)是向量對應的模。可見隻有當
\[cos\theta < 0
才能使得
又因
\[cos\theta \ge -1
可見,隻有當
\[cos\theta = -1
即\(\theta = \pi\)時,函數數值降低最快。此時梯度和\(\Delta x\)反向,即夾角為180度。是以當向量\(\Delta x\)的模大小一定時,取
\[\Delta x = -\alpha \nabla f(x)
即在梯度相反的方向函數值下降的最快。此時函數的下降值為:
\[(\nabla f(x))^T \Delta x = -\| \nabla f(x)\|\|\Delta x\| = - \alpha \| \nabla f(x)\|^2
隻要梯度不為\(0\),往梯度的反方向走函數值一定是下降的。直接用可能會有問題,因為\(x+\Delta x\)可能會超出\(x\)的鄰域範圍之外,此時是不能忽略泰勒展開中的二次及以上的項的,是以步伐不能太大。
一般設:
其中\(\alpha\)為一個接近于\(0\)的正數,稱為步長,由人工設定,用于保證\(x+\Delta x\)在x的鄰域内,進而可以忽略泰勒展開中二次及更高的項,則有:
\[(\nabla f(x))^T \Delta x = -\| \nabla f(x)\|\|\Delta x\| = - \alpha \| \nabla f(x)\|^2 < 0
此時,\(x\)的疊代公式是:
\[x_{k+1} = x_k - \alpha \nabla f(x_k)
隻要沒有到達梯度為\(0\)的點,則函數值會沿着序列\(x_{k}\)遞減,最終會收斂到梯度為\(0\)的點,這就是梯度下降法。
疊代終止的條件是函數的梯度值為\(0\)(實際實作時是接近于\(0\)),此時認為已經達到極值點。注意我們找到的是梯度為\(0\)的點,這不一定就是極值點,後面會說明。
4 實作的細節
-
初始值的設定
一般的,對于不帶限制條件的優化問題,我們可以将初始值設定為0,或者設定為随機數,對于神經網絡的訓練,一般設定為随機數,這對算法的收斂至關重要。
-
學習率的設定
學習率設定為多少,也是實作時需要考慮的問題。最簡單的,我們可以将學習率設定為一個很小的正數,如0.001。另外,可以采用更複雜的政策,在疊代的過程中動态的調整學習率的值。比如前1萬次疊代為0.001,接下來1萬次疊代時設定為0.0001。
5 存在的問題
- 局部極小值
- 梯度下降可能在局部最小的點收斂。
- 鞍點
- 鞍點是指梯度為0,Hessian矩陣既不是正定也不是負定,即不定的點。如函數\(x^2-y^2\)在\((0,0)\)點梯度為0,但顯然不是局部最小的點,也不是全局最小的點。
6 三種梯度下降的實作
- 批量梯度下降法:Batch Gradient Descent,簡稱BGD。求解梯度的過程中用了全量資料。
- 全局最優解;易于并行實作。
- 計算代價大,資料量大時,訓練過程慢。
- 随機梯度下降法:Stochastic Gradient Descent,簡稱SGD。依次選擇單個樣本計算梯度。
- 優點:訓練速度快;
- 缺點:準确度下降,并不是全局最優;不易于并行實作。
- 小批量梯度下降法:Mini-batch Gradient Descent,簡稱MBGD。每次更新參數時使用b個樣本。(b一般為10)。
- 兩種方法的性能之間取得一個折中。
7 用梯度下降法求解多項式極值
7.1 題目
\(argmin\frac{1}{2}[(x_{1}+x_{2}-4)^2 + (2x_{1}+3x_{2}-7)^2 + (4x_{1}+x_{2}-9)^2]\)
7.2 python解題
以下隻是為了示範計算過程,便于了解梯度下降,代碼僅供參考。更好的代碼我将在以後的文章中給出。
# 原函數
def argminf(x1, x2):
r = ((x1+x2-4)**2 + (2*x1+3*x2 - 7)**2 + (4*x1+x2-9)**2)*0.5
return r
# 全量計算一階偏導的值
def deriv_x(x1, x2):
r1 = (x1+x2-4) + (2*x1+3*x2-7)*2 + (4*x1+x2-9)*4
r2 = (x1+x2-4) + (2*x1+3*x2-7)*3 + (4*x1+x2-9)
return r1, r2
# 梯度下降算法
def gradient_decs(n):
alpha = 0.01 # 學習率
x1, x2 = 0, 0 # 初始值
y1 = argminf(x1, x2)
for i in range(n):
deriv1, deriv2 = deriv_x(x1, x2)
x1 = x1 - alpha * deriv1
x2 = x2 - alpha * deriv2
y2 = argminf(x1, x2)
if y1 - y2 < 1e-6:
return x1, x2, y2
if y2 < y1:
y1 = y2
return x1, x2, y2
# 疊代1000次結果
gradient_decs(1000)
# (1.9987027392533656, 1.092923742270406, 0.4545566995437954)
參考文獻
- 《機器學習與應用》
- https://zh.wikipedia.org/wiki/梯度下降法
作者:ZingpLiu
出處:http://www.cnblogs.com/zingp/
本文版權歸作者和部落格園共有,歡迎轉載,但未經作者同意必須保留此段聲明,且在文章頁面明顯位置給出原文連接配接。