梯度下降算法研究綜述

李興怡 岳洋

摘 ?要：在機(jī)器學(xué)習(xí)領(lǐng)域中，梯度下降算法是一種廣泛用于求解線性和非線性模型最優(yōu)解的迭代算法，它的中心思想在于通過(guò)迭代次數(shù)的遞增，調(diào)整使得損失函數(shù)最小化的權(quán)重。本文首先概述了基于多元線性模型的梯度下降算法;其次介紹了梯度下降算法三種框架，使用Python實(shí)現(xiàn)了自主停止訓(xùn)練的BGD算法;針對(duì)梯度下降算法存在的不足，綜述了近三年算法優(yōu)化的研究成果。最后，總結(jié)了本文的主要研究工作，對(duì)梯度下降優(yōu)化算法的研究趨勢(shì)進(jìn)行了展望。

關(guān)鍵詞：機(jī)器學(xué)習(xí);多元線性模型;梯度下降算法;算法實(shí)現(xiàn);優(yōu)化算法

中圖分類(lèi)號(hào)：TP181 ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

1 ? 引言（Introduction）

在求解機(jī)器學(xué)習(xí)中無(wú)約束優(yōu)化問(wèn)題的方法中，優(yōu)化方法是必不可少的一環(huán)。傳統(tǒng)的方法是使用最小二乘法計(jì)算解析解，但有時(shí)面臨著模型更復(fù)雜且樣本量龐大的問(wèn)題，當(dāng)樣本個(gè)數(shù)大于特征個(gè)數(shù)時(shí)，問(wèn)題便轉(zhuǎn)換為求解超定方程組的問(wèn)題，相比使用最小二乘法求解大維數(shù)逆矩陣的方法，采用梯度迭代的梯度下降算法[1]更具備優(yōu)勢(shì)。本文闡述了梯度下降算法在步進(jìn)迭代過(guò)程中，梯度下降方向與學(xué)習(xí)率對(duì)算法的收斂起著至關(guān)重要的作用，前者確定了尋找最優(yōu)解的方向，后者它決定了算法達(dá)到最優(yōu)解所采取的每一步的大小。

考慮到存在非線性數(shù)據(jù)的可能，因此采用多項(xiàng)式模型更具備泛化能力。在實(shí)際應(yīng)用中，可以將多項(xiàng)式中每個(gè)特征的冪次方定義為新特征，轉(zhuǎn)換為多元線性模型。為了簡(jiǎn)化模型，本文將基于多元線性模型對(duì)梯度下降算法進(jìn)行展開(kāi)。

2 ?梯度下降算法原理與實(shí)現(xiàn)（Basic theory and implementation of gradient descent algorithm）

2.1 ? 梯度下降算法概念

假設(shè)多元線性回歸模型：

其中，是因變量（預(yù)測(cè)值），是特征的數(shù)量，是第個(gè)自變量（特征值），是第個(gè)模型參數(shù)（包括偏置與特征參數(shù)），是組合的轉(zhuǎn)置向量，是由（）組成的特征列向量。

針對(duì)實(shí)例，訓(xùn)練模型（1）的過(guò)程就是求解直至模型（1）對(duì)訓(xùn)練數(shù)據(jù)的擬合程度最佳的過(guò)程，每一次訓(xùn)練都會(huì)得到擬合值和真實(shí)值的差值，即損失值，這個(gè)值用于評(píng)估模型擬合程度，值越小表示擬合程度越好。

在多元線性回歸中，將均方誤差（Mean Square Error，MSE）作為損失函數(shù)：

其中，為學(xué)習(xí)率，也稱為尋優(yōu)步長(zhǎng)。通過(guò)公式（4）求得下一次迭代的模型參數(shù)，將結(jié)果帶入公式（1）求得下一次的預(yù)測(cè)值，這就是梯度下降算法的迭代過(guò)程。

2.2 ? 梯度下降算法框架

根據(jù)每次更新模型參數(shù)使用的樣本數(shù)量大小，梯度下降算法有三種實(shí)現(xiàn)框架：批量梯度下降算法、隨機(jī)梯度下降算法和小批量梯度下降算法。

批量梯度下降算法（Batch Gradient Descent， BGD）基于整批訓(xùn)練數(shù)據(jù)計(jì)算每一步損失函數(shù)，相當(dāng)于對(duì)公式（3）做一次性計(jì)算，記作：

相比于BGD的損失函數(shù)總是緩慢降低至最小值，SGD的梯度方向是反復(fù)振蕩的，從全局上看，隨著迭代次數(shù)的增加，它還是會(huì)接近最小值。

小批量梯度下降（Mini-Batch Gradient Descent， MBGD）既不是基于完整的訓(xùn)練集也不是基于單個(gè)實(shí)例，它則是折中于BGD和SGD，對(duì)于每一次迭代基于小部分隨機(jī)的實(shí)例來(lái)計(jì)算梯度：

公式（7）表示每一次迭代隨機(jī)從第個(gè)樣本開(kāi)始，選取個(gè)小批量樣本計(jì)算梯度。

BGD盡管會(huì)耗費(fèi)大量的時(shí)間來(lái)計(jì)算每一步，但是在模型參數(shù)空間里，它最終會(huì)停在最小值上。與之相反的是SGD，訓(xùn)練速度極快，并且能迅速到達(dá)最小值附近，但卻不是最優(yōu)解。如果不設(shè)置迭代次數(shù)，SGD會(huì)不停游走于最小值附近。正因?yàn)镾GD隨機(jī)的性質(zhì)，因此它可用于海量的訓(xùn)練數(shù)據(jù)且有利于跳出局部最優(yōu)，搜索全局最優(yōu)。MBGD則綜合了BGD和SGD的優(yōu)點(diǎn)，當(dāng)訓(xùn)練數(shù)據(jù)較大時(shí)，它不像SGD那么不穩(wěn)定，會(huì)比SGD更接近最小值。

2.3 ? 梯度下降算法實(shí)現(xiàn)

要實(shí)現(xiàn)梯度下降算法，迭代次數(shù)往往很難把握，對(duì)此解決的方法是：暫且不設(shè)置迭代次數(shù)，當(dāng)損失函數(shù)的改變量（即梯度的模）小于容差時(shí)中斷算法，這時(shí)梯度下降幾乎到達(dá)了最小值。相應(yīng)算法流程如下：

（1）初始化模型參數(shù)，步長(zhǎng)，容差;

（2）計(jì)算當(dāng)前位置的損失函數(shù)的梯度，

（3）若，算法終止，當(dāng)前為最終結(jié)果。否則轉(zhuǎn)4）;

（4）根據(jù)更新模型參數(shù)，轉(zhuǎn)（2）。

根據(jù)算法流程，使用Python編寫(xiě)B(tài)GD算法如圖1所示。

為了證明所設(shè)計(jì)的算法能夠在正確的維度關(guān)系基礎(chǔ)上任意初始化模型特征個(gè)數(shù)、參數(shù)個(gè)數(shù)和訓(xùn)練數(shù)據(jù)的維度，算法開(kāi)始前導(dǎo)入了numpy，用于初始化模型參數(shù)theta和訓(xùn)練集（x，y_real），步長(zhǎng)alpha和容差e可根據(jù)情況自行設(shè)置。算法最后五次迭代結(jié)果如圖2所示。

3 ?梯度下降算法研究進(jìn)展（Research advances of gradient descent algorithm）

確定學(xué)習(xí)率和選擇尋優(yōu)方向是梯度下降算法研究的核心。經(jīng)過(guò)近三年的相關(guān)研究，國(guó)內(nèi)外已經(jīng)取得大量研究成果，研究主要涵蓋以下兩個(gè)方面：（1）梯度下降算法的學(xué)習(xí)率相關(guān)研究提高了算法的收斂速度，解決了非凸目標(biāo)函數(shù)陷入局部次優(yōu)的問(wèn)題;（2）基于動(dòng)量和方差縮減的SGD相關(guān)研究解決了SGD的不穩(wěn)定性。

3.1 ? 模型的目標(biāo)函數(shù)問(wèn)題

由于多元線性模型的損失函數(shù)是一個(gè)凸函數(shù)，不存在波峰與波谷，意味著只存在一個(gè)全局最小值，不存在局部最小值，雖然這可以解決算法容易陷入局部最小值的問(wèn)題，但是機(jī)器學(xué)習(xí)中的模型種類(lèi)繁多，目標(biāo)函數(shù)復(fù)雜，使用梯度下降法的效果并不是很好。

在目標(biāo)函數(shù)非凸的情況下，Huo，Z.等[2]首次基于非凸優(yōu)化方差約簡(jiǎn)的異步小批量梯度下降算法的收斂速度進(jìn)行了理論分析。異步隨機(jī)梯度下降法（AsySGD）已廣泛應(yīng)用于深度學(xué)習(xí)優(yōu)化問(wèn)題，并證明了其在非凸優(yōu)化問(wèn)題中的收斂速度為。結(jié)果表明，當(dāng)問(wèn)題為強(qiáng)凸時(shí)，采用變約簡(jiǎn)技術(shù)的異步SGD方法具有線性收斂速度。但是，對(duì)于非凸問(wèn)題，近年來(lái)對(duì)該方法的收斂速度還沒(méi)有進(jìn)行分析。Huo，Z.等考慮了兩種具有變異減少的小批量梯度下降法的異步并行實(shí)現(xiàn)：一種是分布式內(nèi)存架構(gòu)，另一種是共享內(nèi)存架構(gòu)，并且證明了對(duì)于非凸優(yōu)化問(wèn)題，兩種方法均能以的速度收斂。

在模型非線性的情況下，Simon S.Du等[3]證明了訓(xùn)練深度神經(jīng)網(wǎng)絡(luò)模型能夠得到全局最小值。研究表明了對(duì)于具有殘差關(guān)聯(lián)的超參數(shù)深度神經(jīng)網(wǎng)絡(luò)，梯度下降在多項(xiàng)式時(shí)間內(nèi)達(dá)到零訓(xùn)練損失，這依賴于由神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)所誘導(dǎo)出的Gram矩陣的特殊結(jié)構(gòu)。這種結(jié)構(gòu)證明Gram矩陣在整個(gè)訓(xùn)練過(guò)程中是穩(wěn)定的，這種穩(wěn)定性意味著梯度下降算法的全局最優(yōu)性。研究進(jìn)一步將分析擴(kuò)展到殘差深度卷積神經(jīng)網(wǎng)絡(luò)，并且得到了相似的收斂結(jié)果。

此外，J.Flieg等[4]提出了一些一階光滑多目標(biāo)優(yōu)化方法，并證明了這些方法在某種形式上具有一階臨界全局收斂性。分析了光滑無(wú)約束多目標(biāo)優(yōu)化問(wèn)題的梯度下降收斂速度，并用于非凸、凸、強(qiáng)凸向量函數(shù)。這些全局速率與單目標(biāo)優(yōu)化中的梯度下降率相同，并且適用于最壞復(fù)雜度界限的情況。

3.2 ? 學(xué)習(xí)率問(wèn)題

從前面算法的介紹可以得知：如果學(xué)習(xí)率太低，算法需要經(jīng)過(guò)大量的迭代后才能收斂，這將會(huì)耗費(fèi)大量的時(shí)間;反之，算法可能會(huì)陷入局部而無(wú)法搜索到全局最小值，甚至搜索結(jié)果會(huì)大于初始值，必然導(dǎo)致算法發(fā)散。另外，模型參數(shù)的每個(gè)更新都設(shè)置同一個(gè)學(xué)習(xí)率也不利于搜索全局最優(yōu)。當(dāng)前的解決思路之一通過(guò)制定學(xué)習(xí)率規(guī)劃（Learning Rate Schedules）：算法開(kāi)始的學(xué)習(xí)率較大，這有助于跳出局部最優(yōu)，后來(lái)在每次迭代中逐漸減小，慢慢搜索全局最小值。但是更多的研究聚焦在學(xué)習(xí)率自適應(yīng)性的問(wèn)題上。

王功鵬等[5]在解決CNN中學(xué)習(xí)率設(shè)置不恰當(dāng)對(duì)SGD算法的影響，提出了一種學(xué)習(xí)率自適應(yīng)SGD的優(yōu)化算法，該算法隨著迭代使得學(xué)習(xí)率呈現(xiàn)周期性的改變。研究結(jié)果表明，通過(guò)將這種自適應(yīng)學(xué)習(xí)率優(yōu)化算法與所選擇的激活函數(shù)相結(jié)合，可以加快神經(jīng)網(wǎng)絡(luò)模型收斂速度，提升CNN的學(xué)習(xí)準(zhǔn)確率。

嚴(yán)曉明[6]在使用梯度下降解決logistic回歸模型分類(lèi)問(wèn)題時(shí)，提出一種自適應(yīng)學(xué)習(xí)率的調(diào)整方法：在不引入新模型參數(shù)的同時(shí)，根據(jù)樣本數(shù)據(jù)集分類(lèi)準(zhǔn)確率的變化對(duì)學(xué)習(xí)率進(jìn)行更新。在梯度下降稍快時(shí)，增大學(xué)習(xí)率以加快收斂速率，反之則減小學(xué)習(xí)率以減少算法最優(yōu)解附近的振蕩。

相比于使用固定學(xué)習(xí)率的神經(jīng)網(wǎng)絡(luò)，朱振國(guó)等[7]提出基于權(quán)重變化的自適應(yīng)學(xué)習(xí)率更新方法，改進(jìn)了傳統(tǒng)BP神經(jīng)網(wǎng)絡(luò)受人為因素限制的缺陷，證明了改進(jìn)的神經(jīng)網(wǎng)絡(luò)具有更快的收斂速度和更高的誤差精度。

3.3 ? 基于動(dòng)量和方差縮減的SGD優(yōu)化

由于SGD的振蕩性，因此目標(biāo)參數(shù)會(huì)在目標(biāo)函數(shù)的最小值附近游走，這樣的情況下，動(dòng)量（Momentum）在隨機(jī)梯度下降距離中加入上一次迭代動(dòng)量更新項(xiàng)，將它作為更新模型參數(shù)的下降距離，即：

其中，為動(dòng)量超參數(shù)。這意味著在更新模型參數(shù)累積了前面所有的動(dòng)量，對(duì)于當(dāng)前梯度方向與上一次梯度方向一致的參數(shù)，下降速度越來(lái)越快，反之則速度減慢，因此動(dòng)量可以加快收斂速度并減少振蕩。對(duì)于目標(biāo)函數(shù)非光滑優(yōu)化問(wèn)題，程禹嘉等[8]通過(guò)靈活設(shè)置步長(zhǎng)，證明了由Polyak提出的Heavy-ball型動(dòng)量方法具有最優(yōu)的單個(gè)收斂速率，從而證明了Heavy-ball型動(dòng)量方法可以將投影子梯度方法的個(gè)體收斂速率提高至最優(yōu)。

由于每一次迭代的梯度下降非?？?，在損失函數(shù)由凸轉(zhuǎn)為凹時(shí)會(huì)迅速選擇凹的路段，因此涅斯捷羅夫梯度加速（Nesterov Accelerated Gradient，NAG）在此基礎(chǔ)上進(jìn)行了優(yōu)化，它在計(jì)算模型參數(shù)梯度時(shí)，在損失函數(shù)中減去了動(dòng)量項(xiàng)，估計(jì)了下一次參數(shù)的所在位置：

針對(duì)BP神經(jīng)網(wǎng)絡(luò)存在的問(wèn)題，景立森等[9]在NAG動(dòng)量更新的基礎(chǔ)上，建立了一種基于黃金比例動(dòng)量確定隱層神經(jīng)元的加速梯度策略，并應(yīng)用于MNIST手寫(xiě)字體識(shí)別，取得了較好的收斂速度和預(yù)測(cè)評(píng)估結(jié)果。

改進(jìn)的隨機(jī)方差消減梯度法（Stochastic Variance Reduction Gradient，SVRG）可以解決SGD因受到噪聲干擾只能達(dá)到次線性收斂率問(wèn)題，王建飛等[10]設(shè)計(jì)了一種基于SVRG算法思想的分布式實(shí)現(xiàn)算法topkSVRG：在每次迭代時(shí)，收斂速率隨著參數(shù)k的遞增而增加，k的減小可以保證算法收斂。研究理論分析了算法的線性收斂性，并通過(guò)實(shí)驗(yàn)對(duì)相關(guān)算法的進(jìn)行比較，證明topkSVRG算法有良好的高精度收斂性。張晉晶[11]提出了移動(dòng)隨機(jī)方差消減算法，將梯度移動(dòng)的平均值作為平均梯度，該算法在學(xué)習(xí)率很大的情況下，依然能夠保證分類(lèi)的準(zhǔn)確率。

4 ? 結(jié)論（Conclusion）

本文采用多元線性模型對(duì)梯度下降算法的原理進(jìn)行了簡(jiǎn)要的概括，對(duì)三種不同的框架設(shè)計(jì)了算法實(shí)現(xiàn)流程，使用Python實(shí)現(xiàn)了可以自主停止訓(xùn)練的BGD算法。本文的重點(diǎn)在于分別從梯度下降算法的非凸目標(biāo)函數(shù)問(wèn)題、學(xué)習(xí)率問(wèn)題、SGD的游走問(wèn)題三個(gè)方面對(duì)梯度下降算法近三年的研究進(jìn)行了綜述。最后總結(jié)了SGD優(yōu)化算法的特點(diǎn)，可以根據(jù)模型特點(diǎn)參考對(duì)應(yīng)的算法。由于SGD的訓(xùn)練速度非常快，因此SGD改進(jìn)算法是當(dāng)前十分熱門(mén)的梯度下降算法優(yōu)化方向，具有廣闊的研究前景。

參考文獻(xiàn)（References）

[1] Sebastian Ruder.An overview of gradient descent optimization algorithms[EB/OL].http：//128.84.21.199/pdf/1609.04747.pdf，2017-6-15.

[2] Huo，Z.，Huang，H.Asynchronous mini-batch gradient descent with variance reduction for non-convex optimization[J].USA：THIRTY-FIRST AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE，2017：2043-2049.

[3] Simon S.Du，Jason D.Lee，Haochuan Li，et al.Gradient Descent Finds Global Minima of Deep Neural Networks[EB/OL].http：//arxiv.org/pdf/1811.03804.pdf，2019-3-28.

[4] J.Fliege，A.I.F.Vaz，L.N.Vicente（2019）Complexity of gradient descent for multiobjective optimization[J].Optimization Method and Software，2019，34（5）：949-959.

[5] 王功鵬，段萌，牛常勇.基于卷積神經(jīng)網(wǎng)絡(luò)的隨機(jī)梯度下降算法[J].計(jì)算機(jī)工程于設(shè)計(jì)，2018，39（2）：441-445.

[6] 嚴(yán)曉明.一種邏輯回歸學(xué)習(xí)率自適應(yīng)調(diào)整方法[J].福建師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2019，35（3）：24-28.

[7] 朱振國(guó)，田松祿.基于權(quán)值變化的BP神經(jīng)網(wǎng)絡(luò)自適應(yīng)學(xué)習(xí)率改進(jìn)研究[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2018，27（7）：205-210.

[8] 程禹嘉，陶蔚，劉宇翔，等.Heavy-Ball型動(dòng)量方法的最優(yōu)個(gè)體收斂速率[J].計(jì)算機(jī)研究與發(fā)展，2019，56（8）：1686-1694.

[9] 景立森，丁志剛，鄭樹(shù)泉，等.基于NAG的BP神經(jīng)網(wǎng)絡(luò)的研究與改進(jìn)[J].計(jì)算機(jī)應(yīng)用與軟件，2018，35（11）：272-277.

[10] 王建飛，亢良伊，劉杰，等.分布式隨機(jī)方差消減梯度下降算法topkSVRG[J].計(jì)算機(jī)科學(xué)與探索，2018，12（07）：1047-1054.

[11] 張晉晶.基于隨機(jī)梯度下降的神經(jīng)網(wǎng)絡(luò)權(quán)重優(yōu)化算法[D].西南大學(xué)，2018：1-59.

作者簡(jiǎn)介：

李興怡（1993-），男，碩士生.研究領(lǐng)域：機(jī)器學(xué)習(xí).

岳 ? ?洋（1992-），女，碩士生.研究領(lǐng)域：優(yōu)化方法.