閱讀212 返回首頁    go 阿裏雲 go 技術社區[雲棲]

梯度下降法及其Python實現

梯度下降法（gradient descent），又名最速下降法（steepest descent）是求解無約束最優化問題最常用的方法，它是一種迭代方法，每一步主要的操作是求解目標函數的梯度向量，將當前位置的負梯度方向作為搜索方向（因為在該方向上目標函數下降最快，這也是最速下降法名稱的由來）。
梯度下降法特點：越接近目標值，步長越小，下降速度越慢。
直觀上來看如下圖所示：


這裏每一個圈代表一個函數梯度，最中心表示函數極值點，每次迭代根據當前位置求得的梯度（用於確定搜索方向以及與步長共同決定前進速度）和步長找到一個新的位置，這樣不斷迭代最終到達目標函數局部最優點（如果目標函數是凸函數，則到達全局最優點）。


下麵我們將通過公式來具體說明梯度下降法
下麵這個h(θ)是我們的擬合函數


也可以用向量的形式進行表示：


下麵函數是我們需要進行最優化的風險函數，其中的每一項都表示在已有的訓練集上我們的擬合函數與y之間的殘差，計算其平方損失函數作為我們構建的風險函數（參見最小二乘法及其Python實現）


這裏我們乘上1/2是為了方便後麵求偏導數時結果更加簡潔，之所以能乘上1/2是因為乘上這個係數後對求解風險函數最優值沒有影響。
我們的目標就是要最小化風險函數，使得我們的擬合函數能夠最大程度的對目標函數y進行擬合，即：


後麵的具體梯度求解都是圍繞這個目標來進行。


批量梯度下降BGD
按照傳統的思想，我們需要對上述風險函數中的每個求其偏導數，得到每個對應的梯度


這裏表示第i個樣本點的第j分量，即h(θ)中的


接下來由於我們要最小化風險函數，故按照每個參數的負梯度方向來更新每一個


這裏的α表示每一步的步長


從上麵公式可以注意到，它得到的是一個全局最優解，但是每迭代一步，都要用到訓練集所有的數據，如果m很大，那麼可想而知這種方法的迭代速度！！所以，這就引入了另外一種方法，隨機梯度下降。


隨機梯度下降SGD
因為批量梯度下降在訓練集很大的情況下迭代速度非常之慢，所以在這種情況下再使用批量梯度下降來求解風險函數的最優化問題是不具有可行性的，在此情況下，提出了——隨機梯度下降
我們將上述的風險函數改寫成以下形式：


其中，


稱為樣本點的損失函數


接下來我們對每個樣本的損失函數，對每個求其偏導數，得到每個對應的梯度


然後根據每個參數的負梯度方向來更新每一個


與批量梯度下降相比，隨機梯度下降每次迭代隻用到了一個樣本，在樣本量很大的情況下，常見的情況是隻用到了其中一部分樣本數據即可將θ迭代到最優解。因此隨機梯度下降比批量梯度下降在計算量上會大大減少。


SGD有一個缺點是，其噪音較BGD要多，使得SGD並不是每次迭代都向著整體最優化方向。而且SGD因為每次都是使用一個樣本進行迭代，因此最終求得的最優解往往不是全局最優解，而隻是局部最優解。但是大的整體的方向是向全局最優解的，最終的結果往往是在全局最優解附近。


下麵是兩種方法的圖形展示：



從上述圖形可以看出，SGD因為每次都是用一個樣本點進行梯度搜索，因此其最優化路徑看上去比較盲目（這也是隨機梯度下降名字的由來）。


對比其優劣點如下：
批量梯度下降：
優點：全局最優解；易於並行實現；總體迭代次數不多
缺點：當樣本數目很多時，訓練過程會很慢，每次迭代需要耗費大量的時間。

隨機梯度下降：
優點：訓練速度快，每次迭代計算量不大
缺點：準確度下降，並不是全局最優；不易於並行實現；總體迭代次數比較多。



============ 分割分割 =============
上麵我們講解了什麼是梯度下降法，以及如何求解梯度下降，下麵我們將通過python來實現梯度下降法。

[python] view plain copy
  1. # _*_ coding: utf-8 _*_  
  2. # 作者: yhao  
  3. # 博客: https://blog.csdn.net/yhao2014  
  4. # 郵箱: yanhao07@sina.com  
  5.   
  6. # 訓練集  
  7. # 每個樣本點有3個分量 (x0,x1,x2)  
  8. x = [(1, 0., 3), (1, 1., 3), (1, 2., 3), (1, 3., 2), (1, 4., 4)]  
  9. # y[i] 樣本點對應的輸出  
  10. y = [95.364, 97.217205, 75.195834, 60.105519, 49.342380]  
  11.   
  12. # 迭代閥值，當兩次迭代損失函數之差小於該閥值時停止迭代  
  13. epsilon = 0.0001  
  14.   
  15. # 學習率  
  16. alpha = 0.01  
  17. diff = [0, 0]  
  18. max_itor = 1000  
  19. error1 = 0  
  20. error0 = 0  
  21. cnt = 0  
  22. m = len(x)  
  23.   
  24.   
  25. # 初始化參數  
  26. theta0 = 0  
  27. theta1 = 0  
  28. theta2 = 0  
  29.   
  30. while True:  
  31.     cnt += 1  
  32.   
  33.     # 參數迭代計算  
  34.     for i in range(m):  
  35.         # 擬合函數為 y = theta0 * x[0] + theta1 * x[1] +theta2 * x[2]  
  36.         # 計算殘差  
  37.         diff[0] = (theta0 + theta1 * x[i][1] + theta2 * x[i][2]) - y[i]  
  38.   
  39.         # 梯度 = diff[0] * x[i][j]  
  40.         theta0 -= alpha * diff[0] * x[i][0]  
  41.         theta1 -= alpha * diff[0] * x[i][1]  
  42.         theta2 -= alpha * diff[0] * x[i][2]  
  43.   
  44.     # 計算損失函數  
  45.     error1 = 0  
  46.     for lp in range(len(x)):  
  47.         error1 += (y[lp]-(theta0 + theta1 * x[lp][1] + theta2 * x[lp][2]))**2/2  
  48.   
  49.     if abs(error1-error0) < epsilon:  
  50.         break  
  51.     else:  
  52.         error0 = error1  
  53.   
  54.     print ' theta0 : %f, theta1 : %f, theta2 : %f, error1 : %f' % (theta0, theta1, theta2, error1)  
  55. print 'Done: theta0 : %f, theta1 : %f, theta2 : %f' % (theta0, theta1, theta2)  
  56. print '迭代次數: %d' % cnt  

結果（截取部分）：
[plain] view plain copy
  1.  theta0 : 2.782632, theta1 : 3.207850, theta2 : 7.998823, error1 : 7.508687  
  2.  theta0 : 4.254302, theta1 : 3.809652, theta2 : 11.972218, error1 : 813.550287  
  3.  theta0 : 5.154766, theta1 : 3.351648, theta2 : 14.188535, error1 : 1686.507256  
  4.  theta0 : 5.800348, theta1 : 2.489862, theta2 : 15.617995, error1 : 2086.492788  
  5.  theta0 : 6.326710, theta1 : 1.500854, theta2 : 16.676947, error1 : 2204.562407  
  6.  theta0 : 6.792409, theta1 : 0.499552, theta2 : 17.545335, error1 : 2194.779569  
  7.  theta0 : 74.892395, theta1 : -13.494257, theta2 : 8.587471, error1 : 87.700881  
  8.  theta0 : 74.942294, theta1 : -13.493667, theta2 : 8.571632, error1 : 87.372640  
  9.  theta0 : 74.992087, theta1 : -13.493079, theta2 : 8.555828, error1 : 87.045719  
  10.  theta0 : 75.041771, theta1 : -13.492491, theta2 : 8.540057, error1 : 86.720115  
  11.  theta0 : 75.091349, theta1 : -13.491905, theta2 : 8.524321, error1 : 86.395820  
  12.  theta0 : 75.140820, theta1 : -13.491320, theta2 : 8.508618, error1 : 86.072830  
  13.  theta0 : 75.190184, theta1 : -13.490736, theta2 : 8.492950, error1 : 85.751139  
  14.  theta0 : 75.239442, theta1 : -13.490154, theta2 : 8.477315, error1 : 85.430741  
  15.  theta0 : 97.986390, theta1 : -13.221172, theta2 : 1.257259, error1 : 1.553781  
  16.  theta0 : 97.986505, theta1 : -13.221170, theta2 : 1.257223, error1 : 1.553680  
  17.  theta0 : 97.986620, theta1 : -13.221169, theta2 : 1.257186, error1 : 1.553579  
  18.  theta0 : 97.986735, theta1 : -13.221167, theta2 : 1.257150, error1 : 1.553479  
  19.  theta0 : 97.986849, theta1 : -13.221166, theta2 : 1.257113, error1 : 1.553379  
  20.  theta0 : 97.986963, theta1 : -13.221165, theta2 : 1.257077, error1 : 1.553278  
  21. Done: theta0 : 97.987078, theta1 : -13.221163, theta2 : 1.257041  
  22. 迭代次數: 3443  

可以看到最後收斂到穩定的參數值。

注意：這裏在選取alpha和epsilon時需要謹慎選擇，可能不適的值會導致最後無法收斂。


參考文檔：

隨機梯度下降（Stochastic gradient descent）和 批量梯度下降（Batch gradient descent ）的公式對比、實現對比

隨機梯度下降法

python實現梯度下降算法

最後更新：2017-08-13 22:38:33

  上一篇：go  MaxCompute SQL引用第三方Base64JAR實現編解碼
  下一篇：go  時間序列數據的存儲和計算 - 開源時序數據庫解析（三）