下面鏈接先看

http://www.cnblogs.com/python27/p/MachineLearningWeek10.html

梯度下降（BGD）、隨機梯度下降（SGD）、Mini-batch Gradient Descent、帶Mini-batch的SGD

網絡架構（1） 

版權聲明：本文為博主原創文章，未經博主允許不得轉載。

目錄(?)[+]

一、回歸函數及目標函數

以均方誤差作為目標函數（損失函數），目的是使其值最小化，用于優化上式。

二、優化方式（Gradient Descent）

1、最速梯度下降法

也叫批量梯度下降法Batch Gradient Descent，BSD

a、對目標函數求導

b、沿導數相反方向移動theta

原因：

（1）對于目標函數，theta的移動量應當如下，其中a為步長，p為方向向量。

（2）對J（theta）做一階泰勒級數展開：

（3）上式中，ak是步長，為正數，可知要使得目標函數變小，則應當<0，并且其絕對值應當越大越好，這樣下降的速度更快。在泰勒級數中，g代表J（theta k）的梯度，所以為了使得為負并且絕對值最大，應當使theta的移動方向與梯度g相反。

2、隨機梯度下降法（stochastic gradient descent，SGD）

SGD是最速梯度下降法的變種。

使用最速梯度下降法，將進行N次迭代，直到目標函數收斂，或者到達某個既定的收斂界限。每次迭代都將對m個樣本進行計算，計算量大。

為了簡便計算，SGD每次迭代僅對一個樣本計算梯度，直到收斂。偽代碼如下（以下僅為一個loop，實際上可以有多個這樣的loop，直到收斂）：

（1）由于SGD每次迭代只使用一個訓練樣本，因此這種方法也可用作online learning。

（2）每次只使用一個樣本迭代，若遇上噪聲則容易陷入局部最優解。

3、Mini-batch Gradient Descent

（1）這是介于BSD和SGD之間的一種優化算法。每次選取一定量的訓練樣本進行迭代。

（2）從公式上似乎可以得出以下分析：速度比BSD快，比SGD慢；精度比BSD低，比SGD高。

4、帶Mini-batch的SGD

（1）選擇n個訓練樣本（n<m，m為總訓練集樣本數）

（2）在這n個樣本中進行n次迭代，每次使用1個樣本

（3）對n次迭代得出的n個gradient進行加權平均再并求和，作為這一次mini-batch下降梯度

（4）不斷在訓練集中重復以上步驟，直到收斂。

Thoughts of Algorithms

機器學習公開課筆記(10)：大規模機器學習

批梯度下降 (Batch Gradient Descent)

以線性回歸為例，用梯度下降算法進行參數更新的公式為

隨機梯度下降 (Stochastic Gradient Descent)

每次僅用一個example來更新參數θθ，仍以線性回歸為例，隨機梯度下降算法為

1. 隨機重排列整個訓練集(shuffle)

2. 重復下列過程多次(數據集較大時可以重復1~10次)

    for i = 1, ..., m {　　　θj=θj?α(hθ(x(i))?y(i))x(i)jθj=θj?α(hθ(x(i))?y(i))xj(i)    }

小批梯度下降 (Mini-Batch Gradient Descent)

介于批梯度下降和隨機梯度下降之間，批梯度處理利用全部m個example進行參數更新；隨機梯度下降只用1個example進行參數更新；而Mini梯度下降使用b(1<b<m)個example進行參數更新。仍以線性回歸為例，加入我們有m=1000個example，我們可以用每b=10個example進行參數更新，例如:

Repeat {        for i = 1, 11, 21, ..., 991 {                θj=θj?α110∑k=ii+9(hθ(x(k))?y(k))x(k)jθj=θj?α110∑k=ii+9(hθ(x(k))?y(k))xj(k)        }}

算法收斂性

批梯度處理能夠保證算法收斂到最小值(如果選擇的學習速率αα合適的話），可以plot代價函數J(θ)J(θ)隨迭代次數的曲線，如果曲線是總是下降的，則能夠收斂，反之需要調整學習速率。

隨機梯度下降并不能保證算法收斂到最小值，最終結果可能是在最小值附近來回游走，為了觀察其收斂特性，可以plot每100(1000)次迭代時100個example代價函數函數cost(θ,(x(i),y(i)))cost(θ,(x(i),y(i)))的平均值，如果是下降趨勢，則可以收斂，否則可能需要調整增大或者減小平均的example數（將100改為1000或者10等），減小或者增大學習速率。

在線學習 (Online Learning)

之前的算法都是有一個固定的訓練集來訓練模型，當模型訓練好后對未來的example進行分類、回歸等。在線學習則不同，它對每個新來的example進行模型參數更新，因此不需要固定的訓練集，參數更新的方式則是采用隨機梯度下降。在線學習的優勢是模型參數可以隨用戶的偏好自適應的進行調整，以logistic回歸為例，在線學習方式如下:

Repeat forever {        1. 獲取當前example (x, y)        2. 使用(x,y)進行參數更新：θj=θj?α(hθ(x)?y)xjθj=θj?α(hθ(x)?y)xj}

MaPReduce和數據并行化

這部分內容Andrew Ng講得不多，可以認為僅僅講了多個機器的求和問題，比如如何求解1+2+3+...+1000？Map過程：四個機器分別計算1+2+...+250，251+252+...+500, 501+502...+750，751+752+...+1000，然后Reduce過程：將四個機器求和的結果sum1,sum2,sum3,sum4匯總到一臺機器上，計算sum1+sum2+sum3+sum4。

==============================================

梯度下降之隨機梯度下降 -minibatch 與并行化方法

問題的引入：

考慮一個典型的有監督機器學習問題，給定m個訓練樣本S={x^(i),y⁽ⁱ⁾}，通過經驗風險最小化來得到一組權值w，則現在對于整個訓練集待優化目標函數為：

其中為單個訓練樣本（x^(i),y⁽ⁱ⁾）的損失函數，單個樣本的損失表示如下：

引入L2正則，即在損失函數中引入，那么最終的損失為：

注意單個樣本引入損失為（并不用除以m）：

正則化的解釋

這里的正則化項可以防止過擬合，注意是在整體的損失函數中引入正則項，一般的引入正則化的形式如下：

其中L(w)為整體損失，這里其實有：

這里的 C即可代表，比如以下兩種不同的正則方式：

下面給一個二維的示例圖：我們將模型空間限制在w的一個L1-ball 中。為了便于可視化，我們考慮兩維的情況，在(w1, w2)平面上可以畫出目標函數的等高線，而約束條件則成為平面上半徑為C的一個 norm ball 。等高線與 norm ball 首次相交的地方就是最優解

可以看到，L1-ball 與L2-ball 的不同就在于L1在和每個坐標軸相交的地方都有“角”出現，而目標函數的測地線除非位置擺得非常好，大部分時候都會在角的地方相交。注意到在角的位置就會產生稀疏性，例如圖中的相交點就有w1=0，而更高維的時候（想象一下三維的L1-ball 是什么樣的？）除了角點以外，還有很多邊的輪廓也是既有很大的概率成為第一次相交的地方，又會產生稀疏性，相比之下，L2-ball 就沒有這樣的性質，因為沒有角，所以第一次相交的地方出現在具有稀疏性的位置的概率就變得非常小了。

因此，一句話總結就是：L1會趨向于產生少量的特征，而其他的特征都是0，而L2會選擇更多的特征，這些特征都會接近于0。Lasso在特征選擇時候非常有用，而Ridge就只是一種規則化而已。

Batch Gradient Descent

有了以上基本的優化公式，就可以用Gradient Descent 來對公式進行求解，假設w的維度為n，首先來看標準的Batch Gradient Descent算法：

repeat until convergency{

　　for j=1;j<n ; j++:

}

 這里的批梯度下降算法是每次迭代都遍歷所有樣本，由所有樣本共同決定最優的方向。

stochastic Gradient Descent

隨機梯度下降就是每次從所有訓練樣例中抽取一個樣本進行更新，這樣每次都不用遍歷所有數據集，迭代速度會很快，但是會增加很多迭代次數，因為每次選取的方向不一定是最優的方向.

repeat until convergency{

　　random choice j from all m training example：

}

mini-batch Gradient Descent

這是介于以上兩種方法的折中，每次隨機選取大小為b的mini-batch(b<m), b通常取10，或者(2...100),這樣既節省了計算整個批量的時間，同時用mini-batch計算的方向也會更加準確。

repeat until convergency{

　　for j=1;j<n ; j+=b:

}

最后看并行化的SGD：

若最后的v達到收斂條件則結束執行，否則回到第一個for循環繼續執行，該方法同樣適用于minibatch gradient descent。

=============================================

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

梯度下降（1） 

最優化（1） 

版權聲明：本文為博主原創文章，未經博主允許不得轉載。

梯度下降（GD）是最小化風險函數、損失函數的一種常用方法，隨機梯度下降和批量梯度下降是兩種迭代求解思路，下面從公式和實現的角度對兩者進行分析，如有哪個方面寫的不對，希望網友糾正。

下面的h(x)是要擬合的函數，J(theta)損失函數，theta是參數，要迭代求解的值，theta求解出來了那最終要擬合的函數h(theta)就出來了。其中m是訓練集的記錄條數，j是參數的個數。

1、批量梯度下降的求解思路如下：

（1）將J(theta)對theta求偏導，得到每個theta對應的的梯度

（2）由于是要最小化風險函數，所以按每個參數theta的梯度負方向，來更新每個theta

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

2、隨機梯度下降的求解思路如下：

（1）上面的風險函數可以寫成如下這種形式，損失函數對應的是訓練集中每個樣本的粒度，而上面批量梯度下降對應的是所有的訓練樣本：

（2）每個樣本的損失函數，對theta求偏導得到對應梯度，來更新theta

（3）隨機梯度下降是通過每個樣本來迭代更新一次，如果樣本量很大的情況（例如幾十萬），那么可能只用其中幾萬條或者幾千條的樣本，就已經將theta迭代到最優解了，對比上面的批量梯度下降，迭代一次需要用到十幾萬訓練樣本，一次迭代不可能最優，如果迭代10次的話就需要遍歷訓練樣本10次。但是，SGD伴隨的一個問題是噪音較BGD要多，使得SGD并不是每次迭代都向著整體最優化方向。

3、對于上面的linear regression問題，與批量梯度下降對比，隨機梯度下降求解的會是最優解嗎？

（1）批量梯度下降---最小化所有訓練樣本的損失函數，使得最終求解的是全局的最優解，即求解的參數是使得風險函數最小。

（2）隨機梯度下降---最小化每條樣本的損失函數，雖然不是每次迭代得到的損失函數都向著全局最優方向， 但是大的整體的方向是向全局最優解的，最終的結果往往是在全局最優解附近。

4、梯度下降用來求最優解，哪些問題可以求得全局最優？哪些問題可能局部最優解？

對于上面的linear regression問題，最優化問題對theta的分布是unimodal，即從圖形上面看只有一個peak，所以梯度下降最終求得的是全局最優解。然而對于multimodal的問題，因為存在多個peak值，很有可能梯度下降的最終結果是局部最優。

5、隨機梯度和批量梯度的實現差別

以前一篇博文中NMF實現為例，列出兩者的實現差別（注：其實對應Python的代碼要直觀的多，以后要練習多寫python?。?/p>