下面鏈接先看

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

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

網(wǎng)絡(luò)架構(gòu)（1） 

版權(quán)聲明：本文為博主原創(chuàng)文章，未經(jīng)博主允許不得轉(zhuǎn)載。

目錄(?)[+]

一、回歸函數(shù)及目標(biāo)函數(shù)

以均方誤差作為目標(biāo)函數(shù)（損失函數(shù)），目的是使其值最小化，用于優(yōu)化上式。

二、優(yōu)化方式（Gradient Descent）

1、最速梯度下降法

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

a、對(duì)目標(biāo)函數(shù)求導(dǎo)

b、沿導(dǎo)數(shù)相反方向移動(dòng)theta

原因：

（1）對(duì)于目標(biāo)函數(shù)，theta的移動(dòng)量應(yīng)當(dāng)如下，其中a為步長(zhǎng)，p為方向向量。

（2）對(duì)J（theta）做一階泰勒級(jí)數(shù)展開(kāi)：

（3）上式中，ak是步長(zhǎng)，為正數(shù)，可知要使得目標(biāo)函數(shù)變小，則應(yīng)當(dāng)<0，并且其絕對(duì)值應(yīng)當(dāng)越大越好，這樣下降的速度更快。在泰勒級(jí)數(shù)中，g代表J（theta k）的梯度，所以為了使得為負(fù)并且絕對(duì)值最大，應(yīng)當(dāng)使theta的移動(dòng)方向與梯度g相反。

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

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

使用最速梯度下降法，將進(jìn)行N次迭代，直到目標(biāo)函數(shù)收斂，或者到達(dá)某個(gè)既定的收斂界限。每次迭代都將對(duì)m個(gè)樣本進(jìn)行計(jì)算，計(jì)算量大。

為了簡(jiǎn)便計(jì)算，SGD每次迭代僅對(duì)一個(gè)樣本計(jì)算梯度，直到收斂。偽代碼如下（以下僅為一個(gè)loop，實(shí)際上可以有多個(gè)這樣的loop，直到收斂）：

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

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

3、Mini-batch Gradient Descent

（1）這是介于BSD和SGD之間的一種優(yōu)化算法。每次選取一定量的訓(xùn)練樣本進(jìn)行迭代。

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

4、帶Mini-batch的SGD

（1）選擇n個(gè)訓(xùn)練樣本（n<m，m為總訓(xùn)練集樣本數(shù)）

（2）在這n個(gè)樣本中進(jìn)行n次迭代，每次使用1個(gè)樣本

（3）對(duì)n次迭代得出的n個(gè)gradient進(jìn)行加權(quán)平均再并求和，作為這一次mini-batch下降梯度

（4）不斷在訓(xùn)練集中重復(fù)以上步驟，直到收斂。

Thoughts of Algorithms

機(jī)器學(xué)習(xí)公開(kāi)課筆記(10)：大規(guī)模機(jī)器學(xué)習(xí)

批梯度下降 (Batch Gradient Descent)

以線(xiàn)性回歸為例，用梯度下降算法進(jìn)行參數(shù)更新的公式為

隨機(jī)梯度下降 (Stochastic Gradient Descent)

每次僅用一個(gè)example來(lái)更新參數(shù)θθ，仍以線(xiàn)性回歸為例，隨機(jī)梯度下降算法為

1. 隨機(jī)重排列整個(gè)訓(xùn)練集(shuffle)

2. 重復(fù)下列過(guò)程多次(數(shù)據(jù)集較大時(shí)可以重復(fù)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)

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

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)        }}

算法收斂性

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

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

在線(xiàn)學(xué)習(xí) (Online Learning)

之前的算法都是有一個(gè)固定的訓(xùn)練集來(lái)訓(xùn)練模型，當(dāng)模型訓(xùn)練好后對(duì)未來(lái)的example進(jìn)行分類(lèi)、回歸等。在線(xiàn)學(xué)習(xí)則不同，它對(duì)每個(gè)新來(lái)的example進(jìn)行模型參數(shù)更新，因此不需要固定的訓(xùn)練集，參數(shù)更新的方式則是采用隨機(jī)梯度下降。在線(xiàn)學(xué)習(xí)的優(yōu)勢(shì)是模型參數(shù)可以隨用戶(hù)的偏好自適應(yīng)的進(jìn)行調(diào)整，以logistic回歸為例，在線(xiàn)學(xué)習(xí)方式如下:

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

MaPReduce和數(shù)據(jù)并行化

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

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

梯度下降之隨機(jī)梯度下降 -minibatch 與并行化方法

問(wèn)題的引入：

考慮一個(gè)典型的有監(jiān)督機(jī)器學(xué)習(xí)問(wèn)題，給定m個(gè)訓(xùn)練樣本S={x^(i),y⁽ⁱ⁾}，通過(guò)經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化來(lái)得到一組權(quán)值w，則現(xiàn)在對(duì)于整個(gè)訓(xùn)練集待優(yōu)化目標(biāo)函數(shù)為：

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

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

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

正則化的解釋

這里的正則化項(xiàng)可以防止過(guò)擬合，注意是在整體的損失函數(shù)中引入正則項(xiàng)，一般的引入正則化的形式如下：

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

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

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

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

因此，一句話(huà)總結(jié)就是：L1會(huì)趨向于產(chǎn)生少量的特征，而其他的特征都是0，而L2會(huì)選擇更多的特征，這些特征都會(huì)接近于0。Lasso在特征選擇時(shí)候非常有用，而Ridge就只是一種規(guī)則化而已。

Batch Gradient Descent

有了以上基本的優(yōu)化公式，就可以用Gradient Descent 來(lái)對(duì)公式進(jìn)行求解，假設(shè)w的維度為n，首先來(lái)看標(biāo)準(zhǔn)的Batch Gradient Descent算法：

repeat until convergency{

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

}

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

stochastic Gradient Descent

隨機(jī)梯度下降就是每次從所有訓(xùn)練樣例中抽取一個(gè)樣本進(jìn)行更新，這樣每次都不用遍歷所有數(shù)據(jù)集，迭代速度會(huì)很快，但是會(huì)增加很多迭代次數(shù)，因?yàn)槊看芜x取的方向不一定是最優(yōu)的方向.

repeat until convergency{

　　random choice j from all m training example：

}

mini-batch Gradient Descent

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

repeat until convergency{

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

}

最后看并行化的SGD：

若最后的v達(dá)到收斂條件則結(jié)束執(zhí)行，否則回到第一個(gè)for循環(huán)繼續(xù)執(zhí)行，該方法同樣適用于minibatch gradient descent。

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

隨機(jī)梯度下降（Stochastic gradient descent）和 批量梯度下降（Batch gradient descent ）的公式對(duì)比、實(shí)現(xiàn)對(duì)比

梯度下降（1） 

最優(yōu)化（1） 

版權(quán)聲明：本文為博主原創(chuàng)文章，未經(jīng)博主允許不得轉(zhuǎn)載。

梯度下降（GD）是最小化風(fēng)險(xiǎn)函數(shù)、損失函數(shù)的一種常用方法，隨機(jī)梯度下降和批量梯度下降是兩種迭代求解思路，下面從公式和實(shí)現(xiàn)的角度對(duì)兩者進(jìn)行分析，如有哪個(gè)方面寫(xiě)的不對(duì)，希望網(wǎng)友糾正。

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

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

（1）將J(theta)對(duì)theta求偏導(dǎo)，得到每個(gè)theta對(duì)應(yīng)的的梯度

（2）由于是要最小化風(fēng)險(xiǎn)函數(shù)，所以按每個(gè)參數(shù)theta的梯度負(fù)方向，來(lái)更新每個(gè)theta

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

2、隨機(jī)梯度下降的求解思路如下：

（1）上面的風(fēng)險(xiǎn)函數(shù)可以寫(xiě)成如下這種形式，損失函數(shù)對(duì)應(yīng)的是訓(xùn)練集中每個(gè)樣本的粒度，而上面批量梯度下降對(duì)應(yīng)的是所有的訓(xùn)練樣本：

（2）每個(gè)樣本的損失函數(shù)，對(duì)theta求偏導(dǎo)得到對(duì)應(yīng)梯度，來(lái)更新theta

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

3、對(duì)于上面的linear regression問(wèn)題，與批量梯度下降對(duì)比，隨機(jī)梯度下降求解的會(huì)是最優(yōu)解嗎？

（1）批量梯度下降---最小化所有訓(xùn)練樣本的損失函數(shù)，使得最終求解的是全局的最優(yōu)解，即求解的參數(shù)是使得風(fēng)險(xiǎn)函數(shù)最小。

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

4、梯度下降用來(lái)求最優(yōu)解，哪些問(wèn)題可以求得全局最優(yōu)？哪些問(wèn)題可能局部最優(yōu)解？

對(duì)于上面的linear regression問(wèn)題，最優(yōu)化問(wèn)題對(duì)theta的分布是unimodal，即從圖形上面看只有一個(gè)peak，所以梯度下降最終求得的是全局最優(yōu)解。然而對(duì)于multimodal的問(wèn)題，因?yàn)榇嬖诙鄠€(gè)peak值，很有可能梯度下降的最終結(jié)果是局部最優(yōu)。

5、隨機(jī)梯度和批量梯度的實(shí)現(xiàn)差別

以前一篇博文中NMF實(shí)現(xiàn)為例，列出兩者的實(shí)現(xiàn)差別（注：其實(shí)對(duì)應(yīng)Python的代碼要直觀(guān)的多，以后要練習(xí)多寫(xiě)python！）