隨機(jī)步長算法：快速全局優(yōu)化方法

高暉

摘 要：提出了一種快速全局優(yōu)化的隨機(jī)步長算法（RSSA）。采用Adam算法分幾步搜索局部最優(yōu)解。根據(jù)收斂情況調(diào)整Adam的步長。當(dāng)陷入局部最優(yōu)時(shí)，估計(jì)步長的均值和方差，并將步長調(diào)整到局部最優(yōu)范圍之外，如均值加12～36倍方差。初始步長設(shè)置為一個(gè)較小的值，隨著結(jié)果的收斂，步長逐漸減小。它保留了基于梯度的方法的優(yōu)點(diǎn)，如內(nèi)存少、數(shù)據(jù)運(yùn)算稀疏、速度快。算例結(jié)果表明，該方法適用于大數(shù)據(jù)集和高維參數(shù)空間的快速全局優(yōu)化問題。

關(guān)鍵詞： 優(yōu)化算法;隨機(jī)步長;全局優(yōu)化

一、介紹

超參數(shù)優(yōu)化算法在深度學(xué)習(xí)中具有重要意義。隨機(jī)梯度下降法（SGD）（Robbins&Monro，1951）廣泛應(yīng)用于科學(xué)和工程的許多領(lǐng)域。SGD利用梯度的一階矩來解決目標(biāo)函數(shù)的隨機(jī)噪聲問題，其效率和有效性在深度學(xué)習(xí)中得到了驗(yàn)證（Deng et al.，2013;Krizhevsky et al.，2012;Hinton&Salakhutdinov，2006;Hinton et al.，2012a;Graves et al.，2013）。Adam（Kingma&leiba，2015）是一種自適應(yīng)矩估計(jì)優(yōu)化算法，它在訓(xùn)練數(shù)據(jù)稀疏的情況下具有SGD的性能。Adam具有收斂速度快、內(nèi)存消耗少、梯度對(duì)角縮放不變性等優(yōu)點(diǎn)，適用于求解具有大規(guī)模數(shù)據(jù)和參數(shù)的優(yōu)化問題（Wilson等，2017;Liangchen Luo等，2019）。

本文提出了一種基于Adam的隨機(jī)步長調(diào)整方法，有效地解決了全局優(yōu)化問題。采用Adam算法分幾步搜索局部最優(yōu)解。根據(jù)收斂情況調(diào)整Adam的步長。當(dāng)陷入局部最優(yōu)時(shí)，估計(jì)步長的均值和方差，并將步長調(diào)整到局部最優(yōu)范圍之外，如均值加12～36倍方差。初始步長設(shè)置為一個(gè)較小的值，隨著結(jié)果的收斂，步長逐漸減小。

二、算法

實(shí)際目標(biāo)函數(shù)不僅具有隨機(jī)性，而且具有多重波動(dòng)性，使得基于梯度的方法容易陷入局部最優(yōu)。一種突破局部最優(yōu)陷阱的方法是調(diào)整步長。通過移動(dòng)平均計(jì)算，計(jì)算出陷入局部最優(yōu)的步長的平均值和均方差，然后將步長設(shè)置得足夠大，使其能夠跳出陷阱。例如，將步長設(shè)置為平均值加上12-36倍均方差的范圍，隨機(jī)值取該范圍。如果跳出局部陷阱，步長將取一個(gè)很小的值并逐漸減小。

在算法1中，f（αt） 是指使用Adam計(jì)算特定函數(shù)的響應(yīng)，輸入αt作為步長。對(duì)于不同的函數(shù)，應(yīng)根據(jù)收斂到局部最優(yōu)解的速度，在f（αt） 中設(shè)置不同的計(jì)算步驟。一般來說，步數(shù)不超過1000。

三、驗(yàn)證

為了實(shí)證評(píng)估所提出的方法，我們研究了不同的優(yōu)化方法，包括協(xié)方差矩陣自適應(yīng)進(jìn)化策略（CMA-ES;Hansen和Ostermeier，2001），ADAM。比較結(jié)果表明，RSSA算法能有效地解決全局優(yōu)化問題。

利用Rastrigin函數(shù)對(duì)該方法進(jìn)行了評(píng)價(jià)。所有結(jié)果均在內(nèi)存為8Gb的戴爾i7計(jì)算機(jī)上進(jìn)行了模擬。利用RSSA求解Rastrigin問題的最大參數(shù)維數(shù)可達(dá)1億。相比之下，CMA-ES的最大參數(shù)維數(shù)可以達(dá)到10000。

對(duì)于1000-D Rastrigin問題，種群規(guī)模設(shè)為101的CMA-ES在2100代時(shí)用1058秒得到適應(yīng)值-1464.57，如圖1所示，ADAM在幾個(gè)步驟中落入陷阱。RSSA得到了百萬D Rastrigin問題的適應(yīng)值為0.0的全局最優(yōu)解，如圖2和圖3所示。進(jìn)行了10次運(yùn)行，平均尋優(yōu)時(shí)間為300.4秒，最快的一次用了11次迭代，耗時(shí)34秒，最慢的一次用了380次迭代，耗時(shí)1289秒。

四、結(jié)論

提出了一種基于Adam的隨機(jī)步長調(diào)整優(yōu)化算法。我們的方法是針對(duì)大數(shù)據(jù)集和高維參數(shù)空間的全局優(yōu)化。該方法保留了Adam快速收斂到局部最優(yōu)解的優(yōu)點(diǎn)，具有快速找到全局最優(yōu)解的特點(diǎn)。該方法實(shí)現(xiàn)簡單，占用內(nèi)存少。通過實(shí)驗(yàn)驗(yàn)證了全局最優(yōu)收斂速度的分析?？傊?，我們發(fā)現(xiàn)RRAS是健壯的，非常適合人工智能優(yōu)化。

參考文獻(xiàn)：

[1]Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics， 22（3）：400–407， 1951.

[2]Deng， Li， Li， Jinyu， Huang， Jui-Ting， Yao， Kaisheng， Yu， Dong， Seide， Frank， Seltzer， Michael， Zweig， Geoff， He， Xiaodong， Williams， Jason， et al. Recent advances in deep learning for speech research at microsoft. ICASSP 2013， 2013.

[3]Krizhevsky， Alex， Sutskever， Ilya， and Hinton， Geoffrey E. Imagenet classifification with deep convolutional neural networks. In Advances in neural information processing systems， pp. 1097–1105， 2012.

[4]Hinton， G.E. and Salakhutdinov， R.R. Reducing the dimensionality of data with neural networks. Science， 313 （5786）：504–507， 2006.

[5]Hinton， Geoffrey， Deng， Li， Yu， Dong， Dahl， George E， Mohamed， Abdel-rahman， Jaitly， Navdeep， Senior， Andrew， Vanhoucke， Vincent， Nguyen， Patrick， Sainath， Tara N， et al. Deep neural networks for acoustic modeling in speech recognition： The shared views of four research groups. Signal Processing Magazine， IEEE， 29（6）：82–97， 2012a.

[6]Graves， Alex， Mohamed， Abdel-rahman， and Hinton， Geoffrey. Speech recognition with deep recurrent neural networks. In Acoustics， Speech and Signal Processing （ICASSP）， 2013 IEEE International Conference on，pp. 6645–6649. IEEE， 2013.

[7]Diederik P Kingma and Jimmy Lei Ba. Adam： A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations （ICLR）， 2015.

[8]Ashia C Wilson， Rebecca Roelofs， Mitchell Stern， Nati Srebro， and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems 30 （NIPS）， pp. 4148–4158， 2017.

[9]Liangchen Luo， Wenhao Huang， Qi Zeng， Zaiqing Nie， and Xu Sun. Learning personalized end-to-end goal-oriented dialog. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence （AAAI）， 2019.