參考https://blog.csdn.net/weixin_39445556/article/details/84502260

本章我們來學(xué)習(xí)L-BFGS算法.L-BFGS是機(jī)器學(xué)習(xí)中解決函數(shù)最優(yōu)化問題比較常用的手段,本文主要包括以下六部分:

? ? ? ? ? ? ? ?1-L-BFGS算法簡介

? ? ? ? ? ? ? ?2-牛頓法求根問題

? ? ? ? ? ? ? ?3-牛頓法求函數(shù)的駐點(diǎn)

? ? ? ? ? ? ? ?4-牛頓法求駐點(diǎn)的本質(zhì)

? ? ? ? ? ? ? ?5-BFGS算法

? ? ? ? ? ? ? ?6-L-BFGS算法

1-L-BFGS算法簡介

? ? ? ? ?我們知道算法在計(jì)算機(jī)中運(yùn)行的時候是需要很大的內(nèi)存空間的.就像我們解決函數(shù)最優(yōu)化問題常用的梯度下降,它背后的原理就是依據(jù)了泰勒一次展開式.泰勒展開式展開的次數(shù)越多,結(jié)果越精確,沒有使用三階四階或者更高階展開式的原因就是目前硬件內(nèi)存不足以存儲計(jì)算過程中演變出來更復(fù)雜體積更龐大的矩陣.L-BFGS算法翻譯過來就是有限內(nèi)存中進(jìn)行BFGS算法,L是limited memory的意思.

? ? ? ? ?那算法為什么叫BFGS呢,請看下圖:

?

上圖中從左到右依次是Broyden,Fletcher,Goldfarb,Shanno.四位數(shù)學(xué)家名字的首字母是BFGS,所以算法的名字就叫做BFGS算法.接下來我們就一起來學(xué)習(xí)BFGS算法的內(nèi)容.

? ? ? ? ?學(xué)習(xí)BFGS必須要先了解牛頓法的求根問題.

2-牛頓法求根問題

? ? ? ? 牛頓發(fā)現(xiàn),一個函數(shù)的跟從物理的角度就可以根據(jù)函數(shù)圖像迭代求得.牛頓法求根的思路是:

? ? ? ? a.在X軸上隨機(jī)一點(diǎn),經(jīng)過做X軸的垂線,得到垂線與函數(shù)圖像的交點(diǎn).

? ? ? ? b.通過做函數(shù)的切線,得到切線與X軸的交點(diǎn).

? ? ? ? c.迭代a/b兩步.

? ? ? ? 下面附上一張動圖方便理解:

?

通過圖片我們可以看到.在X軸上取的點(diǎn)會隨著迭代次數(shù)的增加而越來越接近函數(shù)的根.經(jīng)過無限多次的迭代,就等于函數(shù)的根.但牛頓法在實(shí)際應(yīng)用的時候我們不會讓算法就這么迭代下去,所以當(dāng)和相同或者兩個值的差小于一個閾值的時候,就是函數(shù)的根.

? ? ? ? 那么問題來了,怎么樣找到的導(dǎo)函數(shù)與X軸的交點(diǎn).請看下圖:

?

?(公式一).

公式一變換一下得到:(公式二 ),同理可以得出每一次迭代的表達(dá)式都是(公式三).

? ? ? ? 所以,根據(jù)牛頓法求根的思路,我們可以總結(jié)(模仿)一下使用牛頓法求根的步驟:

? ? ? ? a.已知函數(shù)的情況下,隨機(jī)產(chǎn)生點(diǎn).

? ? ? ? b.由已知的點(diǎn)按照的公式進(jìn)行k次迭代.

? ? ? ? c.如果與上一次的迭代結(jié)果相同或者相差結(jié)果小于一個閾值時,本次結(jié)果就是函數(shù)的根.

以上為牛頓法的求根的思路.

3-牛頓法求函數(shù)的駐點(diǎn)

? ? ? ? ?我們知道,機(jī)器學(xué)習(xí)過程中的函數(shù)最優(yōu)化問題,大部分優(yōu)化的都是目標(biāo)函數(shù)的導(dǎo)函數(shù),我們要求得導(dǎo)函數(shù)為零時的點(diǎn)或近似點(diǎn)來作為機(jī)器學(xué)習(xí)算法表現(xiàn)最好的點(diǎn).現(xiàn)在我們知道了牛頓求根法,那把牛頓求根法的函數(shù)換成咱們要優(yōu)化的導(dǎo)函數(shù)不就行了么.要求的的導(dǎo)函數(shù)為零的點(diǎn)叫做駐點(diǎn).所以用牛頓法求函數(shù)駐點(diǎn)同求函數(shù)的根是沒有任何區(qū)別的.只是公式二中的變?yōu)榱?原來的變成了一階導(dǎo)函數(shù)的導(dǎo)函數(shù)也就是二階導(dǎo)函數(shù),求的迭代公式如下:

? ? ? ??? ? (公式四)

? ? ? ? 這樣,我們通過幾何直覺,得到了求解函數(shù)根的辦法,那這么厲害的一個想法,有沒有什么理論依據(jù)作為支撐呢?當(dāng)然有了,要不我也不這么問.

?

4-牛頓法求駐點(diǎn)的本質(zhì)

? ? ? ? 牛頓法求駐點(diǎn)的本質(zhì)其實(shí)是二階泰勒展開.我們來看二階泰勒展開式:

? ? ? ??

? ? ? ??是我們要求解的原函數(shù)的近似式.當(dāng)我們要對原函數(shù)求解時,可以直接求得的導(dǎo)函數(shù)?令時的結(jié)果就是原函數(shù)的解.所以對求導(dǎo),消去常數(shù)項(xiàng)后得到公式如下:

? ? ? ??

? ? ? ? ?經(jīng)過變換后所得的公式就是上邊的公式四.所以,牛頓法求駐點(diǎn)的本質(zhì)就是對函數(shù)進(jìn)行二階泰勒展開后變換所得到的結(jié)果.

? ? ? ? ?在一元函數(shù)求解的問題中,我們可以很愉快的使用牛頓法求駐點(diǎn),但我們知道,在機(jī)器學(xué)習(xí)的優(yōu)化問題中,我們要優(yōu)化的都是多元函數(shù),所以x往往不是一個實(shí)數(shù),而是一個向量.所以將牛頓求根法利用到機(jī)器學(xué)習(xí)中時,x是一個向量,也是一個向量,但是對求導(dǎo)以后得到的是一個矩陣,叫做Hessian矩陣.等價公式如下:

? ? ? ??

? ? ? ? 公式中,為公式四種的,代表二階導(dǎo)函數(shù)的倒數(shù).

? ? ? ? 當(dāng)x的維度特別多的時候,我們想求得是非常困難的.而牛頓法求駐點(diǎn)又是一個迭代算法,所以這個困難我們還要面臨無限多次,導(dǎo)致了牛頓法求駐點(diǎn)在機(jī)器學(xué)習(xí)中無法使用.有沒有什么解決辦法呢?請看博客開頭的照片,四位數(shù)學(xué)家在向你微笑....

?

5-BFGS算法

? ? ? ? ? BFGS算法是通過迭代來逼近的算法.逼近的方式如下:

? ? ? ? ?? ? ? ?(公式五)

? ? ? ? ?公式五中的?就是.,.? 是原函數(shù)的導(dǎo)函數(shù).

? ? ? ? ?的迭代公式復(fù)雜無比,還好我們不用記住它.BFGS是通過迭代來逼近矩陣,第一步的D矩陣是單位矩陣.

? ? ? ? ?我們要通過牛頓求駐點(diǎn)法和BFGS算法來求得一個函數(shù)的根,兩個算法都需要迭代,所以我們干脆讓他倆一起迭代就好了.兩個算法都是慢慢逼近函數(shù)根,所以經(jīng)過k次迭代以后,所得到的解就是機(jī)器學(xué)習(xí)中目標(biāo)函數(shù)導(dǎo)函數(shù)的根.這種兩個算法共同迭代的計(jì)算方式,我們稱之為On The Fly.個人翻譯:讓子彈飛~

? ? ? ? ? 回顧一下梯度下降的表達(dá)式?,在BFGS算法迭代的第一步,單位矩陣與梯度g相乘,就等于梯度g,形式上同梯度下降的表達(dá)式是相同的.所以BFGS算法可以理解為從梯度下降逐步轉(zhuǎn)換為牛頓法求函數(shù)解的一個算法.

? ? ? ? ?雖然我們使用了BFGS算法來利用單位矩陣逐步逼近H矩陣,但是每次計(jì)算的時候都要存儲D矩陣,D矩陣有多大呢.假設(shè)我們的數(shù)據(jù)集有十萬個維度(不算特別大),那么每次迭代所要存儲D矩陣的結(jié)果是74.5GB.我們無法保存如此巨大的矩陣內(nèi)容,如何解決呢?

? ? ? ?? 使用L-BFGS算法.

6-L-BFGS算法:

? ? ? ? ?我們每一次對D矩陣的迭代,都是通過迭代計(jì)算和得到的.既然存不下D矩陣,那么我們存儲下所有的和,想要得到就用單位矩陣同存儲下的和到和計(jì)算就可以了.這樣一個時間換空間的辦法可以讓我們在數(shù)據(jù)集有10000個維度的情況下,由存儲10000 x 10000的矩陣變?yōu)榱舜鎯κ畟€1?x 10000的10個向量,有效節(jié)省了內(nèi)存空間.

? ? ? ? 但是,僅僅是這樣還是不夠的,因?yàn)楫?dāng)?shù)螖?shù)非常大的時候,我們的內(nèi)存同樣存不下.這個時候只能丟掉一些存不下的數(shù)據(jù).假設(shè)我們設(shè)置的存儲向量數(shù)為100,當(dāng)s和y迭代超過100時,就會扔掉第一個s和y,存儲到和到,每多一次迭代就對應(yīng)的扔掉最前邊的s和y.這樣雖然損失了精度,但確可以保證使用有限的內(nèi)存將函數(shù)的解通過BFGS算法求得到.

? ? ? ? 所以L-BFGS算法可以理解為對BFGS算法的又一次近似..

到這里,L-BFGS算法的邏輯和由來就已經(jīng)講解完畢了文章中唯一沒有講到的地方就是BFGS算法的推導(dǎo)過程,因?yàn)橥茖?dǎo)過程比較長而且不是我們學(xué)習(xí)的重點(diǎn).如果大家有興趣的話可以去百度BFGS算法推導(dǎo)過程.

參考https://blog.csdn.net/weixin_39445556/article/details/84502260