梯度下降算法研究綜述

李興怡 岳洋

摘 ?要：在機器學習領域中，梯度下降算法是一種廣泛用于求解線性和非線性模型最優解的迭代算法，它的中心思想在于通過迭代次數的遞增，調整使得損失函數最小化的權重。本文首先概述了基于多元線性模型的梯度下降算法;其次介紹了梯度下降算法三種框架，使用Python實現了自主停止訓練的BGD算法;針對梯度下降算法存在的不足，綜述了近三年算法優化的研究成果。最后，總結了本文的主要研究工作，對梯度下降優化算法的研究趨勢進行了展望。

關鍵詞：機器學習;多元線性模型;梯度下降算法;算法實現;優化算法

中圖分類號：TP181 ? ? 文獻標識碼：A

1 ? 引言（Introduction）

在求解機器學習中無約束優化問題的方法中，優化方法是必不可少的一環。傳統的方法是使用最小二乘法計算解析解，但有時面臨著模型更復雜且樣本量龐大的問題，當樣本個數大于特征個數時，問題便轉換為求解超定方程組的問題，相比使用最小二乘法求解大維數逆矩陣的方法，采用梯度迭代的梯度下降算法[1]更具備優勢。本文闡述了梯度下降算法在步進迭代過程中，梯度下降方向與學習率對算法的收斂起著至關重要的作用，前者確定了尋找最優解的方向，后者它決定了算法達到最優解所采取的每一步的大小。

考慮到存在非線性數據的可能，因此采用多項式模型更具備泛化能力。在實際應用中，可以將多項式中每個特征的冪次方定義為新特征，轉換為多元線性模型。為了簡化模型，本文將基于多元線性模型對梯度下降算法進行展開。

2 ?梯度下降算法原理與實現（Basic theory and implementation of gradient descent algorithm）

2.1 ? 梯度下降算法概念

假設多元線性回歸模型：

其中，是因變量（預測值），是特征的數量，是第個自變量（特征值），是第個模型參數（包括偏置與特征參數），是組合的轉置向量，是由（）組成的特征列向量。

針對實例，訓練模型（1）的過程就是求解直至模型（1）對訓練數據的擬合程度最佳的過程，每一次訓練都會得到擬合值和真實值的差值，即損失值，這個值用于評估模型擬合程度，值越小表示擬合程度越好。

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

其中，為學習率，也稱為尋優步長。通過公式（4）求得下一次迭代的模型參數，將結果帶入公式（1）求得下一次的預測值，這就是梯度下降算法的迭代過程。

2.2 ? 梯度下降算法框架

根據每次更新模型參數使用的樣本數量大小，梯度下降算法有三種實現框架：批量梯度下降算法、隨機梯度下降算法和小批量梯度下降算法。

批量梯度下降算法（Batch Gradient Descent， BGD）基于整批訓練數據計算每一步損失函數，相當于對公式（3）做一次性計算，記作：

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

小批量梯度下降（Mini-Batch Gradient Descent， MBGD）既不是基于完整的訓練集也不是基于單個實例，它則是折中于BGD和SGD，對于每一次迭代基于小部分隨機的實例來計算梯度：

公式（7）表示每一次迭代隨機從第個樣本開始，選取個小批量樣本計算梯度。

BGD盡管會耗費大量的時間來計算每一步，但是在模型參數空間里，它最終會停在最小值上。與之相反的是SGD，訓練速度極快，并且能迅速到達最小值附近，但卻不是最優解。如果不設置迭代次數，SGD會不停游走于最小值附近。正因為SGD隨機的性質，因此它可用于海量的訓練數據且有利于跳出局部最優，搜索全局最優。MBGD則綜合了BGD和SGD的優點，當訓練數據較大時，它不像SGD那么不穩定，會比SGD更接近最小值。

2.3 ? 梯度下降算法實現

要實現梯度下降算法，迭代次數往往很難把握，對此解決的方法是：暫且不設置迭代次數，當損失函數的改變量（即梯度的模）小于容差時中斷算法，這時梯度下降幾乎到達了最小值。相應算法流程如下：

（1）初始化模型參數，步長，容差;

（2）計算當前位置的損失函數的梯度，

（3）若，算法終止，當前為最終結果。否則轉4）;

（4）根據更新模型參數，轉（2）。

根據算法流程，使用Python編寫BGD算法如圖1所示。

為了證明所設計的算法能夠在正確的維度關系基礎上任意初始化模型特征個數、參數個數和訓練數據的維度，算法開始前導入了numpy，用于初始化模型參數theta和訓練集（x，y_real），步長alpha和容差e可根據情況自行設置。算法最后五次迭代結果如圖2所示。

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

確定學習率和選擇尋優方向是梯度下降算法研究的核心。經過近三年的相關研究，國內外已經取得大量研究成果，研究主要涵蓋以下兩個方面：（1）梯度下降算法的學習率相關研究提高了算法的收斂速度，解決了非凸目標函數陷入局部次優的問題;（2）基于動量和方差縮減的SGD相關研究解決了SGD的不穩定性。

3.1 ? 模型的目標函數問題

由于多元線性模型的損失函數是一個凸函數，不存在波峰與波谷，意味著只存在一個全局最小值，不存在局部最小值，雖然這可以解決算法容易陷入局部最小值的問題，但是機器學習中的模型種類繁多，目標函數復雜，使用梯度下降法的效果并不是很好。

在目標函數非凸的情況下，Huo，Z.等[2]首次基于非凸優化方差約簡的異步小批量梯度下降算法的收斂速度進行了理論分析。異步隨機梯度下降法（AsySGD）已廣泛應用于深度學習優化問題，并證明了其在非凸優化問題中的收斂速度為。結果表明，當問題為強凸時，采用變約簡技術的異步SGD方法具有線性收斂速度。但是，對于非凸問題，近年來對該方法的收斂速度還沒有進行分析。Huo，Z.等考慮了兩種具有變異減少的小批量梯度下降法的異步并行實現：一種是分布式內存架構，另一種是共享內存架構，并且證明了對于非凸優化問題，兩種方法均能以的速度收斂。

在模型非線性的情況下，Simon S.Du等[3]證明了訓練深度神經網絡模型能夠得到全局最小值。研究表明了對于具有殘差關聯的超參數深度神經網絡，梯度下降在多項式時間內達到零訓練損失，這依賴于由神經網絡結構所誘導出的Gram矩陣的特殊結構。這種結構證明Gram矩陣在整個訓練過程中是穩定的，這種穩定性意味著梯度下降算法的全局最優性。研究進一步將分析擴展到殘差深度卷積神經網絡，并且得到了相似的收斂結果。

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

3.2 ? 學習率問題

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

王功鵬等[5]在解決CNN中學習率設置不恰當對SGD算法的影響，提出了一種學習率自適應SGD的優化算法，該算法隨著迭代使得學習率呈現周期性的改變。研究結果表明，通過將這種自適應學習率優化算法與所選擇的激活函數相結合，可以加快神經網絡模型收斂速度，提升CNN的學習準確率。

嚴曉明[6]在使用梯度下降解決logistic回歸模型分類問題時，提出一種自適應學習率的調整方法：在不引入新模型參數的同時，根據樣本數據集分類準確率的變化對學習率進行更新。在梯度下降稍快時，增大學習率以加快收斂速率，反之則減小學習率以減少算法最優解附近的振蕩。

相比于使用固定學習率的神經網絡，朱振國等[7]提出基于權重變化的自適應學習率更新方法，改進了傳統BP神經網絡受人為因素限制的缺陷，證明了改進的神經網絡具有更快的收斂速度和更高的誤差精度。

3.3 ? 基于動量和方差縮減的SGD優化

由于SGD的振蕩性，因此目標參數會在目標函數的最小值附近游走，這樣的情況下，動量（Momentum）在隨機梯度下降距離中加入上一次迭代動量更新項，將它作為更新模型參數的下降距離，即：

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

由于每一次迭代的梯度下降非常快，在損失函數由凸轉為凹時會迅速選擇凹的路段，因此涅斯捷羅夫梯度加速（Nesterov Accelerated Gradient，NAG）在此基礎上進行了優化，它在計算模型參數梯度時，在損失函數中減去了動量項，估計了下一次參數的所在位置：

針對BP神經網絡存在的問題，景立森等[9]在NAG動量更新的基礎上，建立了一種基于黃金比例動量確定隱層神經元的加速梯度策略，并應用于MNIST手寫字體識別，取得了較好的收斂速度和預測評估結果。

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

4 ? 結論（Conclusion）

本文采用多元線性模型對梯度下降算法的原理進行了簡要的概括，對三種不同的框架設計了算法實現流程，使用Python實現了可以自主停止訓練的BGD算法。本文的重點在于分別從梯度下降算法的非凸目標函數問題、學習率問題、SGD的游走問題三個方面對梯度下降算法近三年的研究進行了綜述。最后總結了SGD優化算法的特點，可以根據模型特點參考對應的算法。由于SGD的訓練速度非常快，因此SGD改進算法是當前十分熱門的梯度下降算法優化方向，具有廣闊的研究前景。

參考文獻（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].計算機工程于設計，2018，39（2）：441-445.

[6] 嚴曉明.一種邏輯回歸學習率自適應調整方法[J].福建師范大學學報（自然科學版），2019，35（3）：24-28.

[7] 朱振國，田松祿.基于權值變化的BP神經網絡自適應學習率改進研究[J].計算機系統應用，2018，27（7）：205-210.

[8] 程禹嘉，陶蔚，劉宇翔，等.Heavy-Ball型動量方法的最優個體收斂速率[J].計算機研究與發展，2019，56（8）：1686-1694.

[9] 景立森，丁志剛，鄭樹泉，等.基于NAG的BP神經網絡的研究與改進[J].計算機應用與軟件，2018，35（11）：272-277.

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

[11] 張晉晶.基于隨機梯度下降的神經網絡權重優化算法[D].西南大學，2018：1-59.

作者簡介：

李興怡（1993-），男，碩士生.研究領域：機器學習.

岳 ? ?洋（1992-），女，碩士生.研究領域：優化方法.