|
如果學(xué)習(xí)機(jī)器學(xué)習(xí)算法，你會(huì)發(fā)現(xiàn)，其實(shí)機(jī)器學(xué)習(xí)的過(guò)程大概就是定義一個(gè)模型的目標(biāo)函數(shù)J(θ)，然后通過(guò)優(yōu)化算法從數(shù)據(jù)中求取J(θ)取得極值時(shí)對(duì)應(yīng)模型參數(shù)θ的過(guò)程，而學(xué)習(xí)到的參數(shù)就對(duì)應(yīng)于機(jī)器學(xué)習(xí)到的知識(shí)。不管學(xué)習(xí)到的是好的還是無(wú)用的，我們知道這其中的動(dòng)力引擎就是優(yōu)化算法。在很多開(kāi)源軟件包中都有自己實(shí)現(xiàn)的一套優(yōu)化算法包，比如stanford-nlp，希望通過(guò)本篇簡(jiǎn)要介紹之后，對(duì)于開(kāi)源軟件包里面的優(yōu)化方法不至于太陌生。本文主要介紹三種方法，分別是梯度下降，Conjugate Gradient Method和Quasi-Newton。具體在stanford-nlp中都有對(duì)應(yīng)的實(shí)現(xiàn)，由于前兩種方法都涉及到梯度的概念，我們首先從介紹梯度開(kāi)始。 梯度(Gradient)什么是梯度，記憶中好像和高數(shù)里面的微積分有關(guān)。好，只要您也有這么一點(diǎn)印象就好辦了，我們知道微積分的鼻祖是牛頓，人家是經(jīng)典力學(xué)的奠基人，那么我們先來(lái)看看一道簡(jiǎn)單的物理問(wèn)題： 一個(gè)小球在一個(gè)平面運(yùn)動(dòng)，沿著x軸的位移隨時(shí)間的變化為：Sx=20t2，沿著y軸的位移隨時(shí)間的變化為：Sy=10+2t2，現(xiàn)在求在t0時(shí)刻小球的速度v？
大家都是為高考奮戰(zhàn)過(guò)的人，這樣的小題應(yīng)該是送分題吧。牛老師告訴我們，只要通過(guò)求各個(gè)方向的分速度，然后再合成就可以求解得出。好，現(xiàn)在我們知道各個(gè)方向的位移關(guān)于時(shí)間的變化規(guī)律，我們來(lái)求各個(gè)方向的速度。如何求速度呢，牛老師說(shuō)位移的變化率就是速度，那么我們來(lái)求在t0時(shí)刻的變化率： 
，那么此時(shí)的合成速度
，那么此時(shí)的合成速度v: 
，此時(shí)的速度方向就是總位移變化最大的方向。搬到數(shù)學(xué)中，對(duì)于一個(gè)位移函數(shù)S(x,y)，它各個(gè)維度的變化率就是其對(duì)應(yīng)的偏導(dǎo)數(shù)
，兩者組合起來(lái)的向量就是該函數(shù)的梯度，所代表的含義上面已經(jīng)說(shuō)過(guò)，其方向代表函數(shù)變化最大的方向，模為變化率的大小。如果我們分別沿著x,y兩個(gè)維度做微小的變化Δx,Δy,那么位移總體的變化將如下：
現(xiàn)在我們知道如何求取函數(shù)的梯度，而且如何利用梯度求取函數(shù)微小變化量了。 梯度下降法做機(jī)器學(xué)習(xí)(監(jiān)督學(xué)習(xí))的時(shí)候，一般情況是這樣的，有N條訓(xùn)練數(shù)據(jù)(X(i),y(i))，我們的模型會(huì)根據(jù)X預(yù)測(cè)出對(duì)應(yīng)的y，也就是： 
其中θ=[θ1,θ2,θ3,...,θn]是模型的參數(shù)。通常我們希望預(yù)測(cè)值和真實(shí)值是一致的，所以會(huì)引出一個(gè)懲罰函數(shù):
而目標(biāo)函數(shù)則是： 
，我們目的是解決下面的優(yōu)化問(wèn)題: argminθJ(θ) ，一般一組θ和N條數(shù)據(jù)會(huì)對(duì)應(yīng)一個(gè)J(θ)，也就是N維平面上的一個(gè)點(diǎn)，那么不同θ就可以得到一個(gè)N維的超平面(hyper plane)。特殊的假如N=3，我們可能的超平面就如下圖所示： 
如何找到最優(yōu)的θ呢？一個(gè)想法是這樣的：我們隨機(jī)在超平面上取一個(gè)點(diǎn)，對(duì)應(yīng)我們θ的初始值，然后每次改變一點(diǎn)Δθ，使J(θ)也改變ΔJ(θ)，只要能保證ΔJ0就一直更新θ直到J(θ)不再減少為止。具體如下：
隨機(jī)初始化θ 對(duì)于每一個(gè)θi選擇合適的Δθi，使得J(θ+Δθ)J(θ)0,如果找不到這樣的Δθ，則結(jié)束算法 對(duì)于每一個(gè)θi進(jìn)行更新：θi=θi+Δθi，回到第2步。
想法挺好的，那么如何找到所謂合適的Δθ呢？根據(jù)上一節(jié)中我們知道： 
,要如何保證ΔJ(θ)0呢？我們知道，兩個(gè)非0數(shù)相乘，要保證大于0，只要兩個(gè)數(shù)一樣即可，如果我們要保證ΔJ(θ)>0，只要另每一個(gè)θi＝J(θ)θi即可，此時(shí) 
，有人疑問(wèn)了，我們目標(biāo)可是要使ΔJ(θ)0，上面的做法剛好相反??！反應(yīng)快的人可能馬上想到了，我們只需另每一個(gè)θi＝J(θ)θi不就好了，而這樣的求取向量θ各個(gè)維度相對(duì)于J(θ)的偏導(dǎo)數(shù)實(shí)際上就是求取J(θ)的梯度！回憶上一節(jié)梯度的含義，表示J(θ)變化最大的方向，想象一個(gè)球在上面的圖中上方滾下來(lái)，而我們的做法是使他沿著最陡的方向滾。不錯(cuò)，我們找到了上述算法所說(shuō)的合適的Δθ了！其實(shí)上述的算法就是我們本文的主角——梯度下降法(gradient descent)，完整算法如下：
隨機(jī)初始化θ 求取θ的梯度θ，也就是對(duì)于每個(gè)θi求取其偏導(dǎo)數(shù)J(θ)θi，并更新θi=θiηJ(θ)θi(η>0并足夠小) 判斷θ是否為0或者足夠小，是就輸出此時(shí)的θ，否則返回第2步
上述算法的第二步中多了一個(gè)未曾介紹的η，這是步伐大小，因?yàn)榍笕∶恳粋€(gè)維度的偏導(dǎo)，只是求取了該維度上的變化率，具體要變化多大就由η控制了，η的選取更多考驗(yàn)的是你的工程能力，取太大是不可行的，這樣導(dǎo)致算法無(wú)法收斂，取太小則會(huì)導(dǎo)致訓(xùn)練時(shí)間太長(zhǎng)，有興趣的可參考An overview of gradient descent optimization algorithms這篇文章中對(duì)η選取的一些算法。如何計(jì)算J(θ)θi呢？根據(jù)定義，可如下計(jì)算： 
，由于每次計(jì)算梯度都需要用到所有N條訓(xùn)練數(shù)據(jù)，所以這種算法也叫批量梯度下降法(Batch gradient descent)。在實(shí)際情況中，有時(shí)候我們的訓(xùn)練數(shù)據(jù)數(shù)以億計(jì)，那么這樣的批量計(jì)算消耗太大了，所以我們可以近似計(jì)算梯度，也就是只取M(MN)條數(shù)據(jù)來(lái)計(jì)算梯度，這種做法是現(xiàn)在最流行的訓(xùn)練神經(jīng)網(wǎng)絡(luò)算法，叫mini-batch gradient descent。最極端的，我們只用一條訓(xùn)練數(shù)據(jù)來(lái)計(jì)算梯度，此時(shí)這樣的算法叫做隨機(jī)梯度下降法(stochastic gradient descent)，適合數(shù)據(jù)是流式數(shù)據(jù)，一次只給一條訓(xùn)練數(shù)據(jù)。 Conjugate Gradient Method 上一節(jié)中，我們介紹了一般的梯度下降法，這是很多開(kāi)源軟件包里面都會(huì)提供的一種算法?，F(xiàn)在我們來(lái)看看另外一種軟件包也經(jīng)常見(jiàn)到算法——Conjugate Gradient Descent，Jonathan在94年的時(shí)候?qū)戇^(guò)《An Introduction to the Conjugate Gradient Method Without the Agonizing Pain》詳細(xì)而直觀地介紹了CGD，確實(shí)文如其名。這里我只是簡(jiǎn)要介紹CGM到底是一個(gè)什么樣的東西，具體還需閱讀原文，強(qiáng)烈推薦??！ 最陡下降法(Steepest Descent) 上一節(jié)中，我們介紹了如何反復(fù)利用θi=θiηJ(θ)θi求得最優(yōu)的θ，但是我們說(shuō)選取η是一個(gè)藝術(shù)活，這里介紹一種η的選取方式。首先明確一點(diǎn)，我們希望每次改變θ，使得J(θ)越來(lái)越小。在梯度確定的情況下，其實(shí)ΔJ(θ)是關(guān)于η的一個(gè)函數(shù)：
，既然我們想讓J(θ)減小，那么干脆每一步都使得|ΔJ(θ)|最大好了，理論上我們可以通過(guò)求導(dǎo)求極值，令： ′(η)=0 求得此時(shí)的η，這樣每次改變J(θ)是最大的，而實(shí)際操作中，我們一般采用line search的技術(shù)來(lái)求取η，也就是固定此時(shí)的梯度θ，也就是固定方向，嘗試不同的η值，使得 J(θ?η??θ) 近似最小即可。這樣固定方向的搜索和直線搜索沒(méi)太大區(qū)別，也是名字的由來(lái)。如果J(θ)是一個(gè)二次函數(shù)也就是J(θ)=θTAθ+bTθ+c，通過(guò)運(yùn)行算法，我們可以得到一個(gè)如下的軌跡：
我們可以發(fā)現(xiàn)，每一次走的步伐和上一次都是垂直的(事實(shí)上是可以證明的，在前面我推薦的文中有詳細(xì)的證明:-))，這樣必然有很多步伐是平行的，造成同一個(gè)方向要走好幾次。研究最優(yōu)化的人野心就來(lái)了，既然同一個(gè)方向要走好幾次，能不能有什么辦法，使得同一個(gè)方向只走一次就可以了呢？ Magnus和Eduard經(jīng)過(guò)研究之后，便設(shè)計(jì)了這樣的方法——Conjugate Gradient Method。 Conjugate Gradient Method具體簡(jiǎn)明的原理還是強(qiáng)烈推薦《An Introduction to the Conjugate Gradient Method Without the Agonizing Pain》一文，我只講講它的表現(xiàn)。CG對(duì)于解決大規(guī)模線性系統(tǒng)比較奏效，比如下面形式: Ax=b ，其中A是方形對(duì)稱半正定的。對(duì)于一個(gè)n維度的二次目標(biāo)函數(shù)，我們可以抽象為： J(θ)=0.5?θTAθ+bTθ+c ，而在任意點(diǎn)θ′的梯度： J(θ)=0.5ATθ+0.5Aθ+b=Aθ+b ，此時(shí)CG的拿手形式就出現(xiàn)了，利用CGM可以保證在每個(gè)維度上只走一步，并在n步之內(nèi)使得算法收斂，也就是實(shí)現(xiàn)我們上面提到同一個(gè)方向走幾次合并為只走一次的算法，上面利用Steepest Method的優(yōu)化問(wèn)題利用CGM就變成了如下：
二維的情況下，可以保證只走兩步就達(dá)到收斂。多么神奇?。∥覀冎?，越是神奇的算法我們必須更加了解他的適用場(chǎng)景，CGM的復(fù)雜度依賴于矩陣A,對(duì)于稀疏矩陣可以很快，但是對(duì)于Dense的，如果可以有效將A分解，那么也是可以的，但是如果不能有效分解(比如內(nèi)存不足)，那么CGM就不是非常有效了。上述只是說(shuō)明CGM在線性系統(tǒng)有奏效，對(duì)于非線性系統(tǒng)，只要修改一些細(xì)節(jié)，CG同樣有效。總之一句話概括，CGM是對(duì)于n維的目標(biāo)函數(shù)可以保證走n步就能到達(dá)極值的梯度下降法。一般都有現(xiàn)成的工具庫(kù)可以使用，只要我們提供目標(biāo)函數(shù)的一次導(dǎo)函數(shù)和初始值，CGM就能幫我們找到我們想要的了！一切面紗皆在《An Introduction to the Conjugate Gradient Method Without the Agonizing Pain》文中揭開(kāi)。 Quasi-Newton Method 上一節(jié)中介紹開(kāi)源軟件包常見(jiàn)的方法Conjugate Gradient Method，這一節(jié)我們來(lái)介紹另一個(gè)常見(jiàn)的方法——Quasi-Newton Method。 Newton Method我們高中的時(shí)候數(shù)學(xué)課本上介紹過(guò)牛頓求根法，具體的做法是：對(duì)于一個(gè)連續(xù)可導(dǎo)的函數(shù)f(x)，我們?nèi)绾吻笕∷牧泓c(diǎn)呢，看看維基百科是如何展示牛老師的方法:
如圖所示，我們首先隨機(jī)初始化x0，然后每一次利用曲線在當(dāng)前xi的切線與橫軸的交點(diǎn)作為下一個(gè)嘗試點(diǎn)xi+1，具體更新公式：
，直到f(xi)≈0為止。牛老師告訴我們一個(gè)求取函數(shù)0點(diǎn)的方法，那么對(duì)于我們本篇的優(yōu)化問(wèn)題有什么幫助呢，我們知道，函數(shù)的極值在于導(dǎo)數(shù)為0的點(diǎn)取得，那么我們可以利用牛老師的方法求得導(dǎo)數(shù)為0的點(diǎn)啊。我們目的是求取J′(θ)=0對(duì)應(yīng)的θ，那么我們可以依樣畫葫蘆（假設(shè)J(θ)是二階可導(dǎo)的）按照如下更新：
其中J′′(θ)是一個(gè)矩陣：
也就是大名鼎鼎的Hession矩陣。而牛頓法更新中:
涉及到Hession矩陣的求逆過(guò)程，對(duì)于一些參數(shù)比較多的模型，這個(gè)矩陣將非常巨大，計(jì)算也極其耗時(shí)，所以這就為什么實(shí)際項(xiàng)目中很少直接使用牛老師的方法。不過(guò)之前我們介紹的方法都只利用了一階信息，牛老師的方法啟發(fā)了利用二階信息優(yōu)化方式。 L-BFGS算法上一小節(jié)中，我們介紹了牛頓法，并且指出它一個(gè)嚴(yán)重的缺陷，就是計(jì)算Hession矩陣和求逆有時(shí)候內(nèi)存和時(shí)間都不允許。那么有什么辦法可以近似利用牛頓法呢，也就是有沒(méi)有Quasi-Newton Method呢？答案是有的，BFGS算法就是一個(gè)比較著名的近似牛頓法，對(duì)于BFGS的介紹，另外有一篇博客有很好的介紹，具體參閱《Numerical Optimization: Understanding L-BFGS》，也是非常直觀簡(jiǎn)潔的介紹，還附有Java和Scala源碼，非常值得學(xué)習(xí)。
BFGS算法核心在于他利用迭代的方式近似求解Hession矩陣的逆，使得求解Hession矩陣的逆變得不再是神話。而迭代的過(guò)程步驟是無(wú)限制的，這也會(huì)導(dǎo)致內(nèi)存不足問(wèn)題，所以工程上利用有限步驟來(lái)近似BFGS求解Hession的逆，就成了Limit-BFGS算法。與很多算法一樣，這個(gè)算法名字是取4位發(fā)明者的名字首字母命名的，所以單看名字是沒(méi)有意義的:-)。
以上是幾位大佬的尊榮。利用Quasi-Newton法，在處理數(shù)據(jù)規(guī)模不大的算法模型，比如Logistic Regression，可以很快收斂，是所有優(yōu)化算法包不可或缺的利器。 參考引用
|
