用于深度學(xué)習(xí)的一種改進(jìn)L-BFGS算法*

趙睿穎

（天津大學(xué)數(shù)學(xué)學(xué)院，天津 300350）

0 引言

深度學(xué)習(xí)，作為解決大規(guī)模機(jī)器學(xué)習(xí)問題的領(lǐng)先技術(shù)，在圖像分類、自然語言處理和大規(guī)模回歸任務(wù)等領(lǐng)域都有非常突出的表現(xiàn).深度學(xué)習(xí)算法通常需要解決一個(gè)高階非線性的、非凸的、無約束優(yōu)化的問題，求解其優(yōu)化問題常用的方法包括一階和二階優(yōu)化方法.其中，一階優(yōu)化方法包括隨機(jī)梯度下降法（stochastic gradient descent，SGD）［1-4］，二階優(yōu)化方法包括牛頓法、擬牛頓法［5-8］、Hessian?free 方法［9-10］和K?FAC 方法［11］等.一階優(yōu)化方法，如SGD，在計(jì)算中成本較低，但存在收斂速度較慢、需要反復(fù)地實(shí)驗(yàn)不斷調(diào)整超參數(shù)等問題；二階優(yōu)化方法，如牛頓法，使用目標(biāo)函數(shù)的Hessian 矩陣來確定搜索方向，通過加速收斂，可以減少大量的迭代次數(shù)，且不需要復(fù)雜的超參數(shù)調(diào)整，更容易得到好的訓(xùn)練結(jié)果.但是，由于深度學(xué)習(xí)中模型擁有海量的參數(shù)，Hessian 矩陣的維度過大，導(dǎo)致無法直接計(jì)算其逆矩陣.因此，在深度學(xué)習(xí)中，牛頓法并不可行，本文利用擬牛頓法進(jìn)行深度學(xué)習(xí)算法研究.

擬牛頓法是求解非線性優(yōu)化問題最有效的算法之一.牛頓法的優(yōu)點(diǎn)是收斂速度快，但需要計(jì)算二階導(dǎo)數(shù)，而且目標(biāo)函數(shù)的Hessian 矩陣可能不是正定的.為了克服牛頓法的缺點(diǎn)，提出了擬牛頓法，其基本思想是用不包含二階導(dǎo)數(shù)的矩陣近似牛頓法中的Hessian 矩陣的逆矩陣.因此，擬牛頓法只需要一階導(dǎo)數(shù)信息，這使得擬牛頓法成為一個(gè)比較受歡迎的算法.同時(shí)，擬牛頓法不需要二階導(dǎo)數(shù)的信息，有時(shí)比牛頓法優(yōu)化更為有效.由于構(gòu)造近似矩陣的方法不同，出現(xiàn)了不同的擬牛頓法.常見的擬牛頓法有BFGS算法、L?BFGS算法以及Hessian?free算法等.

L?BFGS算法是最受歡迎的擬牛頓算法之一.Liu 和Nocedal［12］是第一個(gè)提出L?BFGS算法概念的；Wang 等［13］提出了用于非凸隨機(jī)優(yōu)化的SdLBFGS算法，該算法利用了經(jīng)典L?BFGS算法的框架；Keskar和Berahas［14］提出了用于訓(xùn)練循環(huán)神經(jīng)網(wǎng)絡(luò)的adaQN算法，該算法在L?BFGS算法的基礎(chǔ)上每L（更新周期為20～60 次迭代）次更新1 次Hessian 矩陣；Rafati 和Marcia［15］將L?BFGS算法與信賴域算法以及線搜索相結(jié)合，提出了TRMinATR算法；Byrd等［16］提出了一種隨機(jī)擬牛頓方法（stochastic quasi?Newton，SQN），該方法通過對(duì)樣本進(jìn)行二次采樣，利用矩陣與向量的乘積來形成向量對(duì)（而不是使用隨機(jī)梯度之間的差），取得了比以往方法更好的結(jié)果，并證明了在強(qiáng)凸的情況下，其收斂速度是次線性的；Berahas 等［17］將上述方法與隨機(jī)方差縮減梯度方法［18］相結(jié)合，證明了算法的線性收斂性；Le 等［19］在深度學(xué)習(xí)的背景下，對(duì)現(xiàn)有的優(yōu)化算法如L?BFGS、共軛梯度法（conjugate gradient，CG）和SGD 的優(yōu)缺點(diǎn)進(jìn)行了實(shí)證研究，表明L?BFGS 和CG 在許多情況下優(yōu)于SGD；Berahas 等［20］介紹了采樣的L?BFGS（SL?BFGS），與經(jīng)典的L?BFGS 隨著迭代的進(jìn)行而順序近似Hessian 矩陣（逆矩陣）不同，SL?BFGS 是在當(dāng)前迭代點(diǎn)附近進(jìn)行隨機(jī)采樣來近似Hessian 矩陣（逆矩陣）；Rafati 等［21］介紹了一種基于L?BFGS 使用信賴域的算法（TRMinATR），作為解決深度學(xué)習(xí)中優(yōu)化問題的一種新的方法；Gower 等［22］利用文獻(xiàn)［16］中算法的框架，在優(yōu)化過程中加入塊BFGS 更新，收集曲率信息，并證明了塊BFGS 更新可以加快訓(xùn)練速度.

上述文獻(xiàn)大多是在理論上討論算法的可行性，且通常利用相鄰迭代點(diǎn)梯度之差，或矩陣與向量的乘積中的一種來更新向量對(duì)，缺乏在常用數(shù)據(jù)集CIFAR10 和MNIST 上的實(shí)驗(yàn)結(jié)果.本文提出了一種改進(jìn)L?BFGS算法，擬利用梯度之間的差和矩陣與向量之間乘積的線性組合來更新向量對(duì)，以實(shí)現(xiàn)更新Hessian 矩陣的逆矩陣.

1 常用擬牛頓法BFGS和L?BFGS算法

現(xiàn)有擬牛頓法大多為傳統(tǒng)擬牛頓法的變形，主要包括BFGS 和L?BFGS算法，其區(qū)別主要在于如何定義和構(gòu)造擬牛頓矩陣、計(jì)算搜索方向以及更新模型中參數(shù).

1.1 BFGS算法

BFGS算法是構(gòu)造Hessian 矩陣的近似正定矩陣常用的擬牛頓法.在深度學(xué)習(xí)中，通常需要解決的是高階非線性的、非凸的無約束優(yōu)化問題，其公式為

式中fi：Rd→R 表示第i個(gè)樣本的損失函數(shù)，w∈Rd是模型可訓(xùn)練的參數(shù)向量，d是訓(xùn)練參數(shù)的個(gè)數(shù)，是訓(xùn)練樣本集.

用于解決式（1）的擬牛頓算法，更新公式通常為：

多數(shù)“玩陰”之舉，都戴上了“惺惺相惜”的面具，令人防不勝防。黃鼠狼給雞拜年，是陰；引蛇出洞，甕中捉鱉，是陰；當(dāng)面擁抱，背后使槍，是陰；來說是非者，便是是非人，是陰；有酒有肉親兄弟，急難何曾見一人，是陰；借噓寒問暖之際煽陰風(fēng)點(diǎn)鬼火，更是陰……被“陰”者當(dāng)初以為遇到知己，不勝感激涕零，托付重任、傾吐衷腸、一瀉胸中塊壘；豈知一旦利害攸關(guān)，“知音”原形畢露：“跳踉大，斷其喉，盡其肉，乃去?！薄藭r(shí)方知被“玩”、被“陰”，木已成舟，悔之晚矣。另一邊廂，“玩陰”者鳴鑼收兵，彈冠相慶。

式 中，Bk為Hessi an 矩陣?2f(wk)的近似；Hk為Hes?sian 矩陣的逆

的近似；gk：=?f(wk)；αk為步長.一般情況下，N和d都是非常大的數(shù)字.因此，直接計(jì)算真正的Hessian 矩陣是不切實(shí)際的.擬牛頓法利用目標(biāo)函數(shù)值和一階導(dǎo)數(shù)的信息，構(gòu)造合適的Hk來逼近真正的Hessian 矩陣的逆矩陣，使得不需要計(jì)算真正的Hessian 矩陣，既減少了計(jì)算復(fù)雜度，又保持了牛頓法收斂速度快的優(yōu)點(diǎn).

擬牛頓法中的一個(gè)重要問題是構(gòu)造合適的Hk，需要滿足下列條件：

1）Hk滿足擬牛頓方程：Bk+1sk=yk或Hk+1yk=sk；

2）Hk是正定對(duì)稱矩陣；

3）由Hk到Hk+1的更新是低秩更新.

BFGS 方法是擬牛頓方法的一種，在BFGS 方法中，Bk更新公式為

式中sk=wk+1?wk，yk=gk+1?gk.通過利用Sherman?Morrison?Woodbury 公式，可以得到更新公式

1.2 L?BFGS算 法

2 改進(jìn)L?BFGS算法

在BFGS算法中仍然有一些缺陷，如當(dāng)優(yōu)化問題規(guī)模很大時(shí)，矩陣的存儲(chǔ)和計(jì)算將變得不可行.為了解決這個(gè)問題，就有了L?BFGS算法，但其依然有一些不足，如利用全批量數(shù)據(jù)來計(jì)算梯度.為了進(jìn)一步節(jié)省計(jì)算訓(xùn)練時(shí)間、花費(fèi)以及提高算法的精度，本節(jié)提出了一種改進(jìn)L?BFGS算法.利用L?BFGS算法的框架，改變向量對(duì)的更新規(guī)則，利用相鄰迭代點(diǎn)梯度之差，矩陣與向量之間的乘積的線性組合來更新向量對(duì).

改進(jìn)L?BFGS算法中，利用小批量數(shù)據(jù)而不是全批量數(shù)據(jù)來計(jì)算梯度，即

式中，S?{1，2，3，…，N}是從訓(xùn)練樣本中隨機(jī)選擇的子集，定義a? ||S.改進(jìn)方法的具體內(nèi)容與步驟如下：

（1）用代替yk（yk=gk+1?gk)更新BFGS 公式.式中+(1 ?θk)Mk sk，sk=wk+1?wk；Mk為如下定義的對(duì)角矩陣

其中，(yk?1)i表示向量yk?1的第i個(gè)分量.

θk的取值如下：

此時(shí)，更新公式為

（2）當(dāng)直接沿著迭代方向pk進(jìn)行更新時(shí)，算法在幾個(gè)epoch 后停止運(yùn)行，方法不穩(wěn)定，精度波動(dòng)較大，因此，對(duì)迭代方向單位化使改進(jìn)算法更加穩(wěn)定.

與L?BFGS算法相比，改進(jìn)L?BFGS算法有2 個(gè)關(guān)鍵的區(qū)別特征：（1）向量對(duì)的創(chuàng)建方式；（2）迭代方向的單位化.首先，該方法構(gòu)造的逆Hessian 矩陣的近似矩陣能更好地利用目標(biāo)函數(shù)的當(dāng)前曲率信息；其次，更新向量對(duì)時(shí)，不僅利用了梯度之間的差，還利用了連續(xù)迭代的迭代點(diǎn)之間的差；再次，利用迭代方向單位化，使改進(jìn)算法具有更好的穩(wěn)定性；最后，改進(jìn)L?BFGS算法不需要直接存儲(chǔ)和計(jì)算Bk，只需要存儲(chǔ)2 個(gè)m×d的矩陣，節(jié)省了大量的存儲(chǔ)空間和計(jì)算費(fèi)用.因此，與BFGS算法相比，改進(jìn)L?BFGS算法大大減少了計(jì)算復(fù)雜度以及計(jì)算費(fèi)用.

3 實(shí)驗(yàn)結(jié)果

為了將改進(jìn)L?BFGS算法與現(xiàn)有的流行算法（SGD、AdaGrad 和L?BFGS算法）進(jìn)行比較，本文采用Li 和Liu［24］使用的卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，給出了在MNIST［25］和CIFAR10 數(shù)據(jù)集［26］上的實(shí)驗(yàn)結(jié)果.MNIST 數(shù)據(jù)集包含70 000 個(gè)手寫數(shù)字樣本，其中60 000 個(gè)樣本用作訓(xùn)練集，10 000 個(gè)樣本用作測(cè)試集，數(shù)字范圍為0～9，圖像包括描述其預(yù)期分類的標(biāo)簽；CIFAR 10數(shù)據(jù)集共有60 000張圖像，其中50 000張圖像用于訓(xùn)練，10 000 張圖像用于測(cè)試，所有圖像分為10 類，每類包含圖像6 000 張.數(shù)據(jù)集一共分為5 個(gè)訓(xùn)練批次和1 個(gè)測(cè)試批次，每個(gè)批次圖像10 000 張，測(cè)試批次包含從每類中隨機(jī)選擇的1 000 張圖像，剩下的圖像隨機(jī)排列組成了訓(xùn)練批次，因此，有的訓(xùn)練批次某一類的圖像可能多于另一類的圖像，但總的來看，訓(xùn)練集每一類都有5 000張圖像.

SGDM、AdaGrad、L?BFGS 和改進(jìn)L?BFGS算法在CIFAR10 和MNIST 數(shù)據(jù)集上的測(cè)試精度和訓(xùn)練損失如圖1所示.在CIFAR10數(shù)據(jù)集上，當(dāng)訓(xùn)練100個(gè)迭代周期時(shí)，SGDM、AdaGrad、L?BFGS 和改進(jìn)L?BFGS算法的測(cè)試精度分別是62%、64%、63%和66%，訓(xùn)練損失分別是0.001 4、0.001 2、0.001 3 和0.001 1；與其他3 種算法相比，改進(jìn)L?BFGS算法測(cè)試精度最高，最終能達(dá)到66%的測(cè)試精度，且損失最低.在MNIST 數(shù)據(jù)集上，當(dāng)訓(xùn)練100 個(gè)迭代周期時(shí)，SGDM、AdaGrad、L?BFGS 和改進(jìn)L?BFGS算法的測(cè)試精度分別是92%、86%、None 和95%，其中None 指無數(shù)據(jù)，訓(xùn)練損失分別是0.31、0.58、None 和0.20；與其他3 種算法相比，改進(jìn)L?BFGS算法的測(cè)試效果最優(yōu)，能夠以最快的速度達(dá)到最高的測(cè)試精度，且其損失始終處于一個(gè)比較低的水平.在運(yùn)行10 余個(gè)迭代周期之后，SGDM算法能達(dá)到比改進(jìn)算法更低的訓(xùn)練損失.在前25 個(gè)迭代周期，與改進(jìn)L?BFGS算法相比，L?BFGS算法的測(cè)試精度較優(yōu)，且訓(xùn)練損失較低，實(shí)驗(yàn)效果較佳；但在運(yùn)行25個(gè)迭代周期之后，該算法停止，L?BFGS算法在Li 和Liu［24］的研究中也有類似的情況.

圖1 4 種算法在2 種數(shù)據(jù)集上的測(cè)試精度和訓(xùn)練損失

超參數(shù)存儲(chǔ)向量對(duì)數(shù)m和批量b對(duì)改進(jìn)L?BFGS算法精度的影響如圖2 所示.當(dāng)m=50 和100時(shí)，算法的表現(xiàn)效果相當(dāng)；當(dāng)m=150 時(shí)，其表現(xiàn)略優(yōu)于前2 種情況，且能達(dá)到最高精度66%.當(dāng)b=64 和256 時(shí)，算法的表現(xiàn)相當(dāng)；當(dāng)b=128 時(shí)，其表現(xiàn)明顯差于其他2 種情況.

圖2 不同大小超參數(shù)對(duì)改進(jìn)L?BFGS算法的影響

4 討論

由圖1 可知，改進(jìn)L?BFGS算法在CIFAR10 數(shù)據(jù)集上的測(cè)試精度始終高于其他3 種算法，說明了算法的高效性.改進(jìn)L?BFGS算法在CIFAR10 數(shù)據(jù)集上的訓(xùn)練損失始終處于一個(gè)較低的水平，與SGDM、L?BFGS算法相比，波動(dòng)較小，更加穩(wěn)定.雖然在前25 個(gè)迭代周期內(nèi)，L?BFGS算法在MNIST 數(shù)據(jù)集上的測(cè)試精度高于改進(jìn)L?BFGS算法，但在運(yùn)行25 個(gè)迭代周期后，算法停止.改進(jìn)L?BFGS算法在MNIST數(shù)據(jù)集上的訓(xùn)練損失始終低于SGDM 和L?BFGS算法，也再一次說明了算法的穩(wěn)定性.綜上，改進(jìn)L?BFGS算法比原L?BFGS算法更加高效及穩(wěn)定.圖2展示了不同的超參數(shù)時(shí)，所得結(jié)果相差了4%的精度，為了使算法更加高效，在實(shí)驗(yàn)的過程中要選擇合適的超參數(shù).在本文實(shí)驗(yàn)過程中，當(dāng)選擇pk而不進(jìn)行單位化來迭代時(shí)，算法在運(yùn)行幾個(gè)迭代后停止運(yùn)行，遂采取了對(duì)迭代方向單位化.

5 結(jié)束語

本文提出了一種基于L?BFGS算法的改進(jìn)優(yōu)化算法，作為訓(xùn)練深層神經(jīng)網(wǎng)絡(luò)的一個(gè)新穎的擬牛頓算法.與已有的擬牛頓算法不同，改進(jìn)L?BFGS算法利用連續(xù)迭代的梯度之差以及矩陣與向量乘積的線性組合更新向量對(duì)，并單位化迭代方向，使得該算法具有更好的實(shí)驗(yàn)表現(xiàn).本研究主要是利用數(shù)值實(shí)驗(yàn)來說明算法的有效性.因此，未來可以利用理論來證明算法的收斂性，討論算法的理論收斂性分析以及迭代方向單位化的理論必要性.