更多深度文章，請關注：https://yq.aliyun.com/cloud
hackerearth，一家來自印度的創業公司，旨在幫助開發者通過線上程式設計競賽獲得工作機會。和github類似，它提供一個多種程式設計語言的代碼交流平台。而hackerearth blog 上多刊登一些跟大資料、人工智能、機器學習、算法及程式設計競賽相關的博文。
梯度下降法 (gradient descent algorithm，gd) 是為目标函數j(θ)，如代價函數(cost function), 求解全局最小值（global minimum）的一種疊代算法。本文會詳細讨論按照準确性和耗費時間（accuracy and time consuming factor）将梯度下降法進行分類。這個算法在機器學習中被廣泛用來最小化目标函數，如下圖所示。
α表示學習速率（learning
rate）。
在本文中，考慮使用<b>線性回歸</b>（linear
regression）作為算法執行個體，當然梯度下降法也可以應用到其他算法，如邏輯斯蒂回歸（logistic
regression）和
神經網絡（neural
networks）。線上性回歸中，我們使用如下拟合函數（hypothesis
function）:
其中，
是參數，
<b>代價函數</b>(普通的最小平方差，ordinary
least square error)如下所示：
代價函數的梯度（gradient of cost function）：
參數與代價函數關系如下圖所示：
下面的僞代碼能夠解釋其詳細原理：
1. 初始化參數值
2. 疊代更新這些參數使目标函數j(θ)不斷變小。
基于如何使用資料計算代價函數的導數，梯度下降法可以被定義為不同的形式（various
variants）。确切地說，根據<b>使用資料量的大小</b>（the amount of data），<b>時間複雜度</b>（time complexity）和<b>算法的準确率</b>（accuracy of the algorithm），梯度下降法可分為：
1.
gradient descent, bgd）；
2.
<b>随機梯度下降法</b>（stochastic gradient descent, sgd）；
3.
<b>小批量梯度下降法</b>（mini-batch gradient descent, mbgd）。
這是梯度下降法的基本類型，這種方法<b>使用整個資料集（</b>the complete dataset<b>）去計算代價函數的梯度</b>。每次使用全部資料計算梯度去更新參數，<b>批量梯度下降法會很慢</b>，并且很難處理不能載入記憶體（don’t
fit in memory）的資料集。在随機初始化參數後，按如下方式計算代價函數的梯度：
其中，m是訓練樣本（training
examples）的數量。
note:
1. 如果訓練集有3億條資料，你需要從硬碟讀取全部資料到記憶體中；
2. 每次一次計算完求和後，就進行參數更新；
3. 然後重複上面每一步；
4. 這意味着<b>需要較長的時間才能收斂</b>；
5. 特别是因為磁盤輸入/輸出（disk
i/o）是系統典型瓶頸，是以這種方法會不可避免地需要大量的讀取。
上圖是每次疊代後的等高線圖，每個不同顔色的線表示代價函數不同的值。運用梯度下降會快速收斂到圓心，即唯一的一個全局最小值。
<b>批量梯度下降法不适合大資料集</b>。下面的python代碼實作了批量梯度下降法：
批量梯度下降法被證明是一個較慢的算法，是以，我們可以選擇随機梯度下降法達到更快的計算。随機梯度下降法的第一步是随機化整個資料集。在每次疊代僅選擇一個訓練樣本去計算代價函數的梯度，然後更新參數。即使是大規模資料集，随機梯度下降法也會很快收斂。<b>随機梯度下降法得到結果的準确性可能不會是最好的，但是計算結果的速度很快</b>。在随機化初始參數之後，使用如下方法計算代價函數的梯度：
這裡m表示訓練樣本的數量。
如下為随機梯度下降法的僞碼：
1. 進入内循環（inner loop）;
2. 第一步：挑選第一個訓練樣本并更新參數，然後使用第二個執行個體；
3. 第二步：選第二個訓練樣本，繼續更新參數；
4. 然後進行第三步…直到第n步；
5. 直到達到全局最小值
如下圖所示，随機梯度下降法不像批量梯度下降法那樣收斂，而是<b>遊走到接近全局最小值的區域終止</b>。
小批量梯度下降法是最廣泛使用的一種算法，該算法每次使用m個訓練樣本（稱之為一批）進行訓練，能夠更快得出準确的答案。<b>小批量梯度下降法不是使用完整資料集，在每次疊代中僅使用</b><b>m</b><b>個訓練樣本去計算代價函數的梯度</b>。一般小批量梯度下降法所選取的樣本數量在50到256個之間，視具體應用而定。
1.這種方法減少了參數更新時的變化，能夠更加穩定地收斂。
2.同時，也能利用高度優化的矩陣，進行高效的梯度計算。
随機初始化參數後，按如下僞碼計算代價函數的梯度：
這裡b表示一批訓練樣本的個數，m是訓練樣本的總數。
<b>notes:</b>
1. 實作該算法時，<b>同時更新參數</b>。
3. 檢查梯度下降法的工作過程。畫出疊代次數與每次疊代後代價函數值的關系圖，這能夠幫助你了解梯度下降法是否取得了好的效果。每次疊代後j(θ)應該降低，多次疊代後應該趨于收斂。
4. 不同的學習速率在梯度下降法中的效果
以上為譯文
文章原标題《3 types of gradient descent
algorithms for small & large data sets》，由hackerearth blog釋出。
譯者：李烽 ；審校：段志成-海棠