梯度下降法(Gradient Descent户敬,GD)是一種常用的求解
無(wú)約束最優(yōu)化問(wèn)題
的方法际长,在最優(yōu)化熙参、統(tǒng)計(jì)學(xué)以及機(jī)器學(xué)習(xí)等領(lǐng)域有著廣泛的應(yīng)用馍迄。本文將深入淺出的為讀者介紹梯度下降法的原理福也。
1.問(wèn)題明確
同大家一樣,作者在剛聽(tīng)聞梯度下降法
這個(gè)專(zhuān)業(yè)名詞的時(shí)候也是心中一緊攀圈,發(fā)出奪命三連問(wèn):這是啥暴凑?這能干啥?這咋用白咐础现喳?上面已經(jīng)提到梯度下降法適用于求解無(wú)約束最優(yōu)化問(wèn)題,那么什么是無(wú)約束最優(yōu)化問(wèn)題呢犬辰?——不要怕嗦篱,我們先來(lái)看幾個(gè)你絕對(duì)能看懂的例子(當(dāng)然前提你得有一些統(tǒng)計(jì)學(xué)
和運(yùn)籌學(xué)
基礎(chǔ)昂,小白先去補(bǔ)課;戏臁):
- 形象的例子
引自Udacity:Gradient Descent - Problem of Hiking Down a Mountain
假設(shè)這樣一個(gè)場(chǎng)景:一個(gè)人需要從山的某處開(kāi)始下山灸促,盡快到達(dá)山底。在下山之前他需要確認(rèn)兩件事:
- 下山的方向
- 下山的距離
這是因?yàn)橄律降穆酚泻芏嗪眩仨毨靡恍┬畔⒃≡裕业綇脑撎庨_(kāi)始最陡峭的方向下山,這樣可以保證他盡快到達(dá)山底轿偎。此外典鸡,這座山最陡峭的方向并不是一成不變的,每當(dāng)走過(guò)一段規(guī)定的距離坏晦,他必須停下來(lái)萝玷,重新利用現(xiàn)有信息找到新的最陡峭的方向嫁乘。通過(guò)反復(fù)進(jìn)行該過(guò)程,最終抵達(dá)山底球碉。
這一過(guò)程形象的描述了梯度下降法求解無(wú)約束最優(yōu)化問(wèn)題的過(guò)程蜓斧,下面我們將例子里的關(guān)鍵信息與梯度下降法中的關(guān)鍵信息對(duì)應(yīng)起來(lái):山代表了需要優(yōu)化的函數(shù)表達(dá)式;山的最低點(diǎn)就是該函數(shù)的最優(yōu)值汁尺,也就是我們的目標(biāo);每次下山的距離代表后面要解釋的學(xué)習(xí)率多律;尋找方向利用的信息即為樣本數(shù)據(jù)痴突;最陡峭的下山方向則與函數(shù)表達(dá)式梯度的方向有關(guān),之所以要尋找最陡峭的方向狼荞,是為了滿(mǎn)足最快到達(dá)山底的限制條件辽装;細(xì)心的讀者可能已經(jīng)發(fā)現(xiàn)上面還有一處加粗的詞組:某處——代表了我們給優(yōu)化函數(shù)設(shè)置的初始值,算法后面正是利用這個(gè)初始值進(jìn)行不斷的迭代求出最優(yōu)解相味。
看到這里大家應(yīng)該會(huì)發(fā)現(xiàn)這樣一個(gè)問(wèn)題:在選擇每次行動(dòng)的距離時(shí)拾积,如果所選擇的距離過(guò)大,則有可能偏離最陡峭的方向丰涉,甚至已經(jīng)到達(dá)了最低點(diǎn)卻沒(méi)有停下來(lái)拓巧,從而跨過(guò)最低點(diǎn)而不自知,一直無(wú)法到達(dá)山底一死;如果距離過(guò)小肛度,則需要頻繁尋找最陡峭的方向,會(huì)非常耗時(shí)投慈。要知道承耿,每次尋找最陡峭的方向是非常復(fù)雜的!同樣的伪煤,梯度下降法也會(huì)面臨這個(gè)問(wèn)題加袋,因此需要我們找到最佳的學(xué)習(xí)率,在不偏離方向的同時(shí)耗時(shí)最短抱既。
- 統(tǒng)計(jì)學(xué)
經(jīng)典的回歸分析思想是尋找一個(gè)回歸方程式(也就是自變量x的線(xiàn)性組合)职烧,能夠最小化平方損失函數(shù):
上式可以看作一個(gè)典型的無(wú)約束最優(yōu)化問(wèn)題,自變量x與因變量y均由數(shù)據(jù)給出防泵,n為樣本個(gè)數(shù)阳堕,為待估參數(shù)(既回歸系數(shù))。最小二乘法是求解回歸系數(shù)最常用的方法之一择克,系數(shù)的解析解為(矩陣表達(dá)):
注意恬总,在上面的表達(dá)式中需要對(duì)矩陣求逆,而只有當(dāng)一個(gè)矩陣是非奇異矩陣(既可逆矩陣)時(shí)才存在逆運(yùn)算肚邢。當(dāng)矩陣是奇異矩陣壹堰,常規(guī)的最小二乘法便會(huì)失效拭卿。另外要說(shuō)的是,一般情況下我們所用的數(shù)據(jù)都不是嚴(yán)格的方陣贱纠,讀者還應(yīng)掌握更為一般化的廣義逆矩陣
(也稱(chēng)為偽逆)概念峻厚。然而,即使有了廣義逆矩陣谆焊,當(dāng)自變量x的個(gè)數(shù)(既所選特征的個(gè)數(shù))大于樣本個(gè)數(shù)n時(shí)惠桃,最小二乘法仍會(huì)失效。
這時(shí)辖试,梯度下降法是一個(gè)不錯(cuò)的求解策略辜王。
- 機(jī)器學(xué)習(xí)
眾所周知,感知機(jī)(Perceptron)是支持向量機(jī)與神經(jīng)網(wǎng)絡(luò)等機(jī)器學(xué)習(xí)方法的基礎(chǔ)罐孝。對(duì)于分類(lèi)問(wèn)題呐馆,其基本學(xué)習(xí)策略是尋找一條分類(lèi)直線(xiàn)(高維數(shù)據(jù)時(shí)為超平面):,最小化誤分類(lèi)點(diǎn)到該分類(lèi)直線(xiàn)(超平面)之間的距離之和:
忽略后莲兢,便得到感知機(jī)的損失函數(shù):
上式中M為誤分類(lèi)點(diǎn)的集合汹来,自變量x與分類(lèi)標(biāo)簽y均由數(shù)據(jù)給出,w與b為分類(lèi)直線(xiàn)(超平面)中的待估參數(shù)改艇。
顯然最小化該損失函數(shù)也是一個(gè)無(wú)約束最優(yōu)化問(wèn)題收班,可以用梯度下降法進(jìn)行求解。
看過(guò)上面幾個(gè)例子谒兄,我們將其歸納為一般的問(wèn)題進(jìn)行描述:首先闺阱,找到一個(gè)連續(xù)可微的函數(shù)作為待優(yōu)化的函數(shù),利用梯度下降法進(jìn)行參數(shù)迭代估計(jì)舵变,使可微函數(shù)在估計(jì)的參數(shù)處最優(yōu)值達(dá)到最小酣溃。
2.概念理解
- 微分
我們所要優(yōu)化的函數(shù)必須是一個(gè)連續(xù)可微
的函數(shù),可微纪隙,既可微分赊豌,意思是在函數(shù)的任意定義域上導(dǎo)數(shù)存在。如果導(dǎo)數(shù)存在且是連續(xù)函數(shù)绵咱,則原函數(shù)是連續(xù)可微的碘饼。在中學(xué)時(shí)我們便知道,函數(shù)的導(dǎo)數(shù)(近似于函數(shù)的微分)可以有以下兩種理解:
- 函數(shù)在某點(diǎn)切線(xiàn)的斜率即為函數(shù)在該點(diǎn)處導(dǎo)數(shù)值悲伶。
- 函數(shù)在某點(diǎn)的導(dǎo)數(shù)值反映函數(shù)在該處的變化率艾恼,導(dǎo)數(shù)值越大,原函數(shù)函數(shù)值變化越快麸锉。
以上兩個(gè)解釋可以讓我們對(duì)梯度下降法理解得更直觀(guān)形象钠绍,下面我們一起來(lái)看幾個(gè)連續(xù)可微函數(shù)求微分的例子:
上面這兩個(gè)例子高中生都會(huì),下面看看多元連續(xù)可微函數(shù)求微分的例子:
- 梯度
學(xué)習(xí)梯度下降算法花沉,不知道什么是梯度可不行柳爽!
以二元函數(shù)為例媳握,假設(shè)其對(duì)每個(gè)變量都具有連續(xù)的一階偏導(dǎo)數(shù)和,則這兩個(gè)偏導(dǎo)數(shù)構(gòu)成的向量即為該二元函數(shù)的梯度向量磷脯,一般記作蛾找,其中讀作“Nabla”。根據(jù)這個(gè)概念赵誓,我們來(lái)看幾個(gè)多元函數(shù)求梯度的例子:
注意打毛,上面兩個(gè)例子中的。
在一元函數(shù)中俩功,梯度其實(shí)就是微分幻枉,既函數(shù)的變化率,而在多元函數(shù)中绑雄,梯度變?yōu)榱讼蛄空勾牵瑯颖硎竞瘮?shù)變化的方向奥邮,從幾何意義來(lái)講万牺,梯度的方向表示的是函數(shù)增加最快的方向,這正是我們下山要找的“最陡峭的方向”的反方向洽腺!因此后面要講到的迭代公式中脚粟,梯度前面的符號(hào)為“-”,代表梯度方向的反方向蘸朋。在多元函數(shù)中核无,梯度向量的模
(一般指二模)表示函數(shù)變化率,同樣的藕坯,模數(shù)值越大团南,變化率越快。
- 學(xué)習(xí)率
學(xué)習(xí)率也被稱(chēng)為迭代的步長(zhǎng)炼彪,優(yōu)化函數(shù)的梯度一般是不斷變化的(梯度的方向隨梯度的變化而變化)吐根,因此需要一個(gè)適當(dāng)?shù)膶W(xué)習(xí)率約束著每次下降的距離不會(huì)太多也不會(huì)太少。讀者可參考上面講過(guò)的下山例子中下山距離的講解辐马,此處不再贅述拷橘。
3.梯度下降算法原理
在清楚我們要解決的問(wèn)題并明白梯度的概念后,下面開(kāi)始正式介紹梯度下降算法喜爷。根據(jù)計(jì)算梯度時(shí)所用數(shù)據(jù)量不同冗疮,可以分為三種基本方法:批量梯度下降法
(Batch Gradient Descent, BGD)、小批量梯度下降法
(Mini-batch Gradient Descent, MBGD)以及隨機(jī)梯度下降法
(Stochastic Gradient Descent, SGD)檩帐。
這里首先給出梯度下降法的一般求解框架:
給定待優(yōu)化連續(xù)可微函數(shù)术幔、學(xué)習(xí)率以及一組初始值
計(jì)算待優(yōu)化函數(shù)梯度:
更新迭代公式:
計(jì)算處函數(shù)梯度
計(jì)算梯度向量的模來(lái)判斷算法是否收斂:
若收斂,算法停止湃密,否則根據(jù)迭代公式繼續(xù)迭代
注意:以上敘述只是給出了一個(gè)梯度下降算法的一般框架特愿,實(shí)際應(yīng)用過(guò)程中仲墨,還應(yīng)靈活變換該框架使其符合實(shí)際。例如揍障,可以更改迭代公式(例如學(xué)習(xí)率前面的符號(hào)目养,因?yàn)槿绻髆ax的話(huà),梯度的方向即為函數(shù)值上升最快的方向毒嫡,此時(shí)符號(hào)應(yīng)為“+”)癌蚁,還可以用其他指標(biāo)(例如KL散度、迭代前后優(yōu)化函數(shù)值的變化程度等)判斷算法的收斂性等等兜畸。
在下面的介紹中努释,為了便于理解,我們均假設(shè)待優(yōu)化函數(shù)為二模損失函數(shù):
其中咬摇,n為樣本個(gè)數(shù)伐蒂,也可以理解為參與計(jì)算的樣本個(gè)數(shù);是一個(gè)常數(shù)肛鹏,為了求偏導(dǎo)數(shù)時(shí)與平方抵消方便逸邦,不影響計(jì)算復(fù)雜度與計(jì)算結(jié)果;與為第i個(gè)樣本在扰;缕减,x的下標(biāo)表示第i個(gè)樣本的各個(gè)分量。
- 批量梯度下降法
批量梯度下降法在計(jì)算優(yōu)化函數(shù)的梯度時(shí)利用全部樣本數(shù)據(jù):
梯度計(jì)算公式:
這里可以清楚地看到芒珠,批量梯度下降法計(jì)算梯度時(shí)桥狡,使用全部樣本數(shù)據(jù),分別計(jì)算梯度后除以樣本個(gè)數(shù)(取平均)作為一次迭代使用的梯度向量皱卓。
迭代公式為:
偽代碼如下:
for i in range(max_iters):
grad = evaluate_gradient(loss_functiion, data, initial_params)
params = params - learning_rate * grad
- 隨機(jī)梯度下降法
隨機(jī)梯度下降法在計(jì)算優(yōu)化函數(shù)的梯度時(shí)利用隨機(jī)選擇的一個(gè)樣本數(shù)據(jù):
梯度計(jì)算公式:
SGD只是用一個(gè)樣本數(shù)據(jù)參與梯度計(jì)算裹芝,因此省略了求和以及求平均的過(guò)程,降低了計(jì)算復(fù)雜度娜汁,因此提升了計(jì)算速度嫂易。
迭代公式為:
偽代碼如下:
for i in range(max_iters):
np.random.shuffle(data)
for sample in data:
grad = evaluate_gradient(loss_functiion, sample, initial_params)
params = params - learning_rate * grad
- 小批量梯度下降法
小批量梯度下降法在計(jì)算優(yōu)化函數(shù)的梯度時(shí)利用隨機(jī)選擇的一部分樣本數(shù)據(jù):
梯度計(jì)算公式:
小批量梯度下降法使用一部份樣本數(shù)據(jù)(上式中為k個(gè))參與計(jì)算,既降低了計(jì)算復(fù)雜度存炮,又保證了解的收斂性炬搭。
迭代公式為:
偽代碼如下(假設(shè)每次選取50個(gè)樣本參與計(jì)算):
for i in range(max_iters):
np.random.shuffle(data)
for batch in get batches(data, batch_size=50):
grad = evaluate_gradient(loss_functiion, batch, initial_params)
params = params - learning_rate * grad
三種方法優(yōu)缺點(diǎn)對(duì)比:
BGD(批量) | SGD(隨機(jī)) | MBGD(小批量) | |
---|---|---|---|
優(yōu)點(diǎn) | 非凸函數(shù)可保證收斂至全局最優(yōu)解 | 計(jì)算速度快 | 計(jì)算速度快,收斂穩(wěn)定 |
缺點(diǎn) | 計(jì)算速度緩慢穆桂,不允許新樣本中途進(jìn)入 | 計(jì)算結(jié)果不易收斂宫盔,可能會(huì)陷入局部最優(yōu)解中 | — |
其實(shí),已經(jīng)有研究發(fā)現(xiàn)享完,當(dāng)逐漸減小SGD方法使用的學(xué)習(xí)率時(shí)灼芭,可以保證SGD解的收斂性旷档,但不一定保證收斂至全局最優(yōu)解治拿。此外,許多深度學(xué)習(xí)方法所使用的求解算法都是基于MBGD的,該方法一個(gè)算不上缺點(diǎn)的“缺點(diǎn)”就是需要找到合適的參與梯度計(jì)算的樣本規(guī)模靶端,對(duì)于超過(guò)2000個(gè)樣本的較大數(shù)據(jù)集而言衅檀,參與計(jì)算的樣本規(guī)模建議值為至蛾方。下面這張圖形象的顯示了三種梯度下降算法的收斂過(guò)程:
- 簡(jiǎn)單實(shí)例
求:
函數(shù)的極小值點(diǎn)艰争。
解:
設(shè)初始點(diǎn)為,學(xué)習(xí)率設(shè)為猜旬。
初始點(diǎn)處梯度為脆栋,因此更新迭代公式帶入原函數(shù)中,得:
洒擦,此時(shí)為函數(shù)極小點(diǎn)椿争,因此:
,一次迭代結(jié)束熟嫩。
再將作為初始點(diǎn)秦踪,重復(fù)上面的迭代步驟,得到:掸茅。
根據(jù)規(guī)律顯然可知椅邓,。
容易看出倦蚪,本例中目標(biāo)函數(shù)是三維空間中的橢圓拋物面希坚,其投影至二維空間上的等高線(xiàn)是一簇橢圓(如下圖所示)边苹。的極小點(diǎn)就是這簇橢圓的中心陵且。我們求得的迭代公式是逐漸趨近于?的,算法正確有效个束。
至此慕购,梯度下降法的原理部分就結(jié)束了。作者感覺(jué)本篇應(yīng)該是全網(wǎng)最清楚明白的講解之一了茬底,為了了解了大家的疑問(wèn)沪悲,在動(dòng)筆前參看了許多優(yōu)秀的博文以及留言,最終形成此文阱表。希望能對(duì)熱愛(ài)學(xué)習(xí)的你有所幫助殿如!
后續(xù)還有機(jī)器學(xué)習(xí)算法:梯度下降法的代碼篇(Python & R)以及拓展篇,敬請(qǐng)期待最爬!