純乾貨｜機器學習中梯度下降法的分類及對比分析（附源碼）

分類＼科技
時間＼2017-04-10

更多深度文章，請關注：https://yq.aliyun.com/cloud

HackerEarth，一家來自印度的創業公司，旨在幫助開發者通過線上程式設計競賽獲得工作機會。和Github類似，它提供一個多種程式設計語言的代碼交流平臺。而HackerEarth blog 上多刊登一些跟大資料、人工智慧、機器學習、演算法及程式設計競賽相關的博文。

引言

梯度下降法 (Gradient Descent Algorithm，GD) 是為目標函數J(θ)，如代價函數(cost function), 求解全域最小值（Global Minimum）的一種反覆運算演算法。本文會詳細討論按照準確性和耗費時間（accuracy and time consuming factor）將梯度下降法進行分類。這個演算法在機器學習中被廣泛用來最小化目標函數，

如下圖所示。

為什麼使用梯度下降法

我們使用梯度下降法最小化目標函數

J(θ)。在使用梯度下降法時，首先初始化參數值，然後一直改變這些值，直到得到全域最小值。其中，我們計算在每次反覆運算時計算代價函數的導數，

然後使用如下公式同時更新參數值：

α表示學習速率（learning rate）。

在本文中，考慮使用線性回歸（linear regression）作為演算法實例，當然梯度下降法也可以應用到其他演算法，如邏輯斯蒂回歸（Logistic regression）和神經網路（Neural networks）。在線性回歸中，我們使用如下擬合函數（hypothesis function）:

其中，

是參數，

是輸入特徵。為了求解線性回歸模型，需要找到合適的參數使擬合函數能夠更好地適合模型，然後使用梯度下降最小化代價函數

J(θ)

。

代價函數(普通的最小平方差，

ordinary least square error)如下所示：

代價函數的梯度（Gradient of Cost function）：

參數與代價函數關係如下圖所示：

梯度下降法的工作原理

下面的偽代碼能夠解釋其詳細原理：

1.初始化參數值

2.反覆運算更新這些參數使目標函數J(θ)不斷變小。

梯度下降法的類型

基於如何使用資料計算代價函數的導數，

梯度下降法可以被定義為不同的形式（various variants）。確切地說，根據使用資料量的大小（the amount of data），時間複雜度（time complexity）和演算法的準確率（accuracy of the algorithm），梯度下降法可分為：

1.批量梯度下降法

（Batch Gradient Descent, BGD）；

2.隨機梯度下降法（Stochastic Gradient Descent, SGD）；

3.小批量梯度下降法（Mini-Batch Gradient Descent, MBGD）。

批量梯度下降法原理

這是梯度下降法的基本類型，這種方法使用整個資料集（the complete dataset）去計算代價函數的梯度。每次使用全部資料計算梯度去更新參數，批量梯度下降法會很慢，

並且很難處理不能載入記憶體（don’t fit in memory）的資料集。在隨機初始化參數後，按如下方式計算代價函數的梯度：

其中，m是訓練樣本（training examples）的數量。

Note:

1. 如果訓練集有3億條資料，你需要從硬碟讀取全部資料到記憶體中；

2. 每次一次計算完求和後，就進行參數更新；

3. 然後重複上面每一步；

4. 這意味著需要較長的時間才能收斂；

5. 特別是因為磁片輸入/輸出（disk I/O）是系統典型瓶頸，所以這種方法會不可避免地需要大量的讀取。

上圖是每次反覆運算後的等高線圖，每個不同顏色的線表示代價函數不同的值。運用梯度下降會快速收斂到圓心，即唯一的一個全域最小值。

批量梯度下降法不適合大資料集。下面的Python代碼實現了批量梯度下降法：

1. import numpy as np隨機梯度下降法原理

批量梯度下降法被證明是一個較慢的演算法，所以，我們可以選擇隨機梯度下降法達到更快的計算。隨機梯度下降法的第一步是隨機化整個資料集。在每次反覆運算僅選擇一個訓練樣本去計算代價函數的梯度，然後更新參數。即使是大規模資料集，隨機梯度下降法也會很快收斂。隨機梯度下降法得到結果的準確性可能不會是最好的，但是計算結果的速度很快。在隨機化初始參數之後，使用如下方法計算代價函數的梯度：

這裡m表示訓練樣本的數量。

如下為隨機梯度下降法的虛擬碼：

1. 進入內迴圈（inner loop）;

2. 第一步：挑選第一個訓練樣本並更新參數，然後使用第二個實例；

3. 第二步：選第二個訓練樣本，繼續更新參數；

4. 然後進行第三步…直到第n步；

5. 直到達到全域最小值

如下圖所示，隨機梯度下降法不像批量梯度下降法那樣收斂，而是遊走到接近全域最小值的區域終止。

小批量梯度下降法原理

小批量梯度下降法是最廣泛使用的一種演算法，該演算法每次使用m個訓練樣本（稱之為一批）進行訓練，能夠更快得出準確的答案。小批量梯度下降法不是使用完整資料集，在每次反覆運算中僅使用m個訓練樣本去計算代價函數的梯度。一般小批量梯度下降法所選取的樣本數量在50到256個之間，視具體應用而定。

1.這種方法減少了參數更新時的變化，能夠更加穩定地收斂。

2.同時，也能利用高度優化的矩陣，進行高效的梯度計算。

隨機初始化參數後，按如下虛擬碼計算代價函數的梯度：

這裡b表示一批訓練樣本的個數，m是訓練樣本的總數。

Notes:

1. 實現該演算法時，同時更新參數。

2. 學習速率

α（也稱之為步長）。如果

α過大，演算法可能不會收斂；如果α比較小，就會很容易收斂。

3. 檢查梯度下降法的工作過程。畫出反覆運算次數與每次反覆運算後代價函數值的關係圖，這能夠幫助你瞭解梯度下降法是否取得了好的效果。每次反覆運算後J(θ)應該降低，多次反覆運算後應該趨於收斂。

4. 不同的學習速率在梯度下降法中的效果

總結

本文詳細介紹了不同類型的

梯度下降法。這些演算法已經被廣泛應用於神經網路。下面的圖詳細展示了3種梯度下降法的比較。

以上為譯文

本文由北郵@愛可哥-愛生活老師推薦，阿裡云云棲社區組織翻譯。

文章原標題《3 Types of Gradient Descent Algorithms for Small & Large Data Sets》，由HackerEarth blog發佈。

譯者：李烽；審校：段志成-海棠