隨機梯度下降演算法求函數極值

❶ 梯度下降法是什麼

梯度下降是通過迭代搜索一個函數極小值的優化演算法。使用梯度下降，尋找一個函數的局部極小值的過程起始於一個隨機點，並向該函數在當前點梯度（或近似梯度）的反方向移動。梯度下降演算法是一種非常經典的求極小值的演算法。

比如邏輯回歸可以用梯度下降進行優化，因為這兩個演算法的損失函數都是嚴格意義上的凸函數，即存在全局唯一極小值，較小的學習率和足夠的迭代次數，一定可以達到最小值附近，滿足精度要求是完全沒有問題的。並且隨著特徵數目的增多，梯度下降的效率將遠高於去解析標准方程的逆矩陣。

常用的梯度下降法有3種不同的形式：

（1）批量梯度下降法，簡稱BGD，使用所有樣本，比較耗時。

（2）隨機梯度下降法，簡稱SGD，隨機選擇一個樣本，簡單高效。

（3）小批量梯度下降法，簡稱MBGD，使用少量的樣本，這是一個折中的辦法。

機梯度下降法優點：

1、更容易跳出局部最優解。

2、具有更快的運行速度。

❷ 隨機梯度下降演算法

以線性回歸為例：
預測函數為：

代價函數：

重復：{

}

當數據量過大時，梯度下降的演算法會變得很慢，因為要對所有的數據進行求和。因為每次重復梯度下降都是所有數據全部求和，所以梯度下降演算法又稱之為 批量梯度下降（Batch Gradient Descent）

隨機梯度下降在每一次迭代中，不用考慮全部的樣本，只需要考慮一個訓練樣本。

針對一個樣本，它的代價函數：

而針對所有樣本的代價函數可以看作是對每個樣本代價函數的平均：

隨機梯度下降演算法如下：
第一步，先隨機打亂訓練集樣本。
第二步，進行梯度下降：
重復 {
循環所有樣本 for i=1,2,3,...,m {

}
}

一開始隨機打亂數據是為了對樣本集的訪問是隨機的，會讓梯度下降的速度快一點。

該演算法一次訓練一個樣本，對它的代價函數進行一小步梯度下降，修改參數 ，使得它對該樣本的擬合會好一點；然後再對下一個樣本進行運算，直到掃描完所有的訓練樣本，最後外部在迭代這個過程。

跟批量梯度下降演算法不同的是，隨機梯度下降不需要等到所有樣本求和來得到梯度項，而是在對每個樣本就可以求出梯度項，在對每個樣本掃描的過程中就已經在優化參數了。

在梯度下降過程中，批量梯度下降的過程趨向於一條直線，直接收斂到全局最小值；而隨機梯度下降不太可能收斂到全局最小值，而是隨機地在其周圍震盪，但通常會很接近最小值。

隨機梯度下降通常需要經過1-10次外部循環才能接近全局最小值。

在批量梯度下降中，要判斷是否收斂，需要在每一次迭代演算法後計算 的值，根據值的變化來判斷收斂。
在執行隨機梯度下降時，不需要計算所有的樣本的代價函數，只用在對某個樣本進行梯度下降前計算該樣本的代價函數 ，為了判斷是否收斂，可以計算多次迭代後 的平均值，例如1000次迭代，在每次更新 前，計算最後1000次的的cost的平均值。

選擇每隔多少次計算成本函數對梯度下降的過程也有影響：

上圖中藍色曲線是每1000次迭代，紅色的是每隔5000次迭代。
因為隨機梯度下降時會出現震盪，當迭代次數少時發現下降的曲線起伏很多，而迭代次數變大時，曲線就會變得平滑許多。缺點是每隔5000個計算，會增加計算成本。

增加迭代次數可以判斷演算法是否正確：

上圖藍色的是1000個迭代次數，通過這條曲線，不能很好的判斷成本函數是否在下降，這時就需要添加迭代次數，當增加到5000次，則可以通過平滑的曲線判斷，當下滑曲線是紅色的時，說明演算法是有效的，代價函數值在下降；當是紫色的曲線時，可以看到是一個平坦的線，這時判斷演算法可能出現問題了。

在隨機梯度下降中，學習率 也會影響演算法，當學習率減小時，下降曲線的震盪就會變小，而且會收斂到一個更好的解：

當看到曲線是上升的時候，可以嘗試減小學習率看看效果。

在隨機梯度下降中，如果想要收斂到全劇最小值，需要隨著時間的變化減小學習率 的值：

學習率等於一個常數除以迭代次數加另一個常數，隨著迭代次數增大，學習率會減小；但這會造成常數1和常數2的選擇問題。

❸ 隨機梯度下降法原理和步驟

隨機梯度下降主要用來求解類似於如下求和形式的優化問題：
[公式]
梯度下降法：
[公式]
當[公式]很大時，每次迭代計算所有的[公式]會非常耗時。
隨機梯度下降的想法就是每次在[公式]中random選取一個計算代替如上的[公式]，以這個隨機選取的方向作為下降的方向。
[公式][公式]
由於[公式], 當選取step size [公式]時，演算法在期望的意義下收斂。
注意到在[公式] 靠近極小值點[公式]時，[公式]，這導致隨機梯度下降法精度低。由於方差的存在，要使得演算法收斂，就需要[公式]隨[公式]逐漸減小。因此導致函數即使在強凸且光滑的條件下，收斂速度也只有[公式]. 後來提出的變種SAG，SVRG，SDCA都是在降方差，為了保證在[公式]時，方差趨於0。以上提到的幾種變種都能達到線性收斂速度。