孫婭楠，林文斌

（西南交通大學(xué) 數(shù)學(xué)學(xué)院，四川 成都 611756）

無約束優(yōu)化問題是最優(yōu)化理論的基礎(chǔ)，通常采用迭代法求它的最優(yōu)解。經(jīng)典的數(shù)值優(yōu)化算法如梯度下降法（gradient descent method），牛頓法（Newton method）等都可求得其最優(yōu)解。梯度下降法早在1847年由大數(shù)學(xué)家Cauchy最先使用。它是最古老的一種解析方法，而其他解析方法大多承其衣缽，并構(gòu)成最優(yōu)化方法的基礎(chǔ)。梯度下降法具有儲(chǔ)存量小、結(jié)構(gòu)簡(jiǎn)單、易于實(shí)現(xiàn)的優(yōu)點(diǎn)。梯度下降法常作為機(jī)器學(xué)習(xí)領(lǐng)域內(nèi)訓(xùn)練算法的核心算法，用來遞歸性地逼近最小偏差模型，如人工神經(jīng)網(wǎng)絡(luò)與Logistic regression，廣泛應(yīng)用于數(shù)據(jù)挖掘[1]、模式識(shí)別等領(lǐng)域。

梯度下降法以負(fù)梯度方向作為極小化算法的下降方向，是無約束優(yōu)化中最簡(jiǎn)單的方法[2]。在訓(xùn)練類的算法中（如神經(jīng)網(wǎng)絡(luò)、回歸），通常使用梯度下降法最小化損失函數(shù)，這時(shí)學(xué)習(xí)率的設(shè)置對(duì)算法的性能很重要，已有許多研究致力于梯度下降法的分析與改進(jìn)。20世紀(jì)80年代，Naym Shor[3－4]研究發(fā)明了次梯度法（Subgradient Method），它是解凸優(yōu)化問題的一種迭代算法，也適用于目標(biāo)函數(shù)不可微的情形。牛頓法（Newton method）最初由艾薩克·牛頓發(fā)明，后于1690年由約瑟夫·拉弗森再次提出。Bottou L[5－6]提出在大數(shù)據(jù)處理時(shí)，使用隨機(jī)抽取的單個(gè)樣本計(jì)算近似的平均梯度值，單次迭代計(jì)算量小，效率很高，特別適合大數(shù)據(jù)機(jī)器學(xué)習(xí)。Samy Bengio、Tom Dean和Andrew Ng[7－8]在深度學(xué)習(xí)中具體給出線性回歸與邏輯回歸模型的推導(dǎo)。2016年，郭躍東和宋旭東[9]針對(duì)學(xué)習(xí)率對(duì)算法收斂速度的影響做了研究，提出了一種新的梯度下降法，通過求解線性回歸問題分析了算法性能，結(jié)果表明，改進(jìn)算法大大加快了算法的收斂速度。袁亞湘和孫文瑜[2]針對(duì)最優(yōu)化理論與方法，介紹了不同基本優(yōu)化算法的迭代步驟，給筆者提供了寫作思路。目前，梯度下降法在機(jī)器學(xué)習(xí)中的應(yīng)用研究甚少，文中通過介紹梯度下降法及其變體優(yōu)化算法的基本迭代步驟，在機(jī)器學(xué)習(xí)訓(xùn)練算法中，具體推導(dǎo)出線性回歸與Logistic regression模型，并在應(yīng)用實(shí)例中，運(yùn)用MATLAB程序?qū)崿F(xiàn)結(jié)果，分析比較在機(jī)器學(xué)習(xí)的訓(xùn)練類算法應(yīng)用中的梯度下降法與其變體的收斂速度及復(fù)雜度。

1 梯度下降法用于線性回歸模型的訓(xùn)練

1.1 線性回歸（Linear regression）基本形式

給定由n個(gè)屬性描述的示例x=（x1；x2；…；xn），線性模型試圖學(xué)得一個(gè)通過屬性的線性組合來進(jìn)行預(yù)測(cè)的函數(shù)

θ稱為參數(shù)，若x0=1，可以用向量的形式表示估計(jì)函數(shù)

給定數(shù)據(jù)集，其中xi，yi∈R。線性回歸試圖學(xué)得一個(gè)線性模型以盡可能準(zhǔn)確地預(yù)測(cè)實(shí)值輸出標(biāo)記[10]。

它的損失函數(shù)采用均方誤差的形式

其中，x（i）為樣本中的特征，y（i）為樣本中的目標(biāo)值，m為參與計(jì)算的樣本數(shù)目。通過訓(xùn)練數(shù)據(jù)集尋找參數(shù)的最優(yōu)解，即求解可以得到minJ（θ）的參數(shù)向量θ。

1.2 批量梯度下降法（Batch Gradient Descent，BGD）

批量梯度下降法是機(jī)器學(xué)習(xí)領(lǐng)域常用的一種梯度下降法，要用批量梯度下降法（BGD）求解，需要對(duì)J（θ）求偏導(dǎo)。

得到θ的更新函數(shù)

由于每次更新θ都要用到m個(gè)樣本，該算法稱為批量梯度下降法（BGD）。批量梯度下降法在更新參數(shù)時(shí)，需使用數(shù)據(jù)集中的所有樣本，時(shí)間復(fù)雜度為O（n）。

1.3 隨機(jī)梯度下降法（Stochastic Gradient Descent，SGD）

該算法是對(duì)每個(gè)隨機(jī)訓(xùn)練樣本進(jìn)行參數(shù)更新，對(duì)于大規(guī)模數(shù)據(jù)來說，隨機(jī)梯度下降法（SGD）由于單次迭代計(jì)算量小，收斂速度明顯高于其他算法，效率很高，遠(yuǎn)優(yōu)于經(jīng)典的優(yōu)化算法，如牛頓法，特別適合大數(shù)據(jù)機(jī)器學(xué)習(xí)[11]。

1.4 批量梯度下降法與隨機(jī)梯度下降法的實(shí)例分析

該例選用的數(shù)據(jù)如下

采用MATLAB實(shí)現(xiàn)結(jié)果，見表1。

表1 分別使用BGD與SGD迭代200次輸出的參數(shù)θ

比較輸出結(jié)果如圖1、圖2所示。圖2采用隨機(jī)梯度下降法（SGD）時(shí)誤差振蕩下降，說明隨機(jī)梯度下降法（SGD）噪音較多而批量梯度下降法（BGD）一直下降（如圖1）。

圖1 BGD下的損失函數(shù)與迭代次數(shù)關(guān)系圖

圖2 SGD下的損失函數(shù)與迭代次數(shù)關(guān)系圖

2 梯度下降法用于對(duì)數(shù)幾率回歸模型的訓(xùn)練

考慮二分類任務(wù)，其輸出標(biāo)記y∈{0，1}，而線性回歸模型產(chǎn)生的預(yù)測(cè)值z(mì)是實(shí)值，于是，需將實(shí)值轉(zhuǎn)換到0/1。

圖3 Sigmoid函數(shù)圖像

Logistic regression是基于對(duì)數(shù)幾率函數(shù)的一種經(jīng)典的分類方法，主要解決二分劃分問題。Sigmoid函數(shù)即形似S的函數(shù)（見圖3）。對(duì)率函數(shù)是Sigmoid函數(shù)最重要的代表。它將z值轉(zhuǎn)化為一個(gè)接近0或1的y值，并且其輸出值在z=0附近變化最陡[10]。

對(duì) g（z）求導(dǎo)得

對(duì)率函數(shù)是任意階可導(dǎo)的凸函數(shù)，有很好的數(shù)學(xué)性質(zhì)，現(xiàn)有的許多數(shù)值優(yōu)化算法都可直接用于求取最優(yōu)解[10]。

構(gòu)造擬合函數(shù) hθ（x）形式為

構(gòu)造損失函數(shù)J（θ）

在Logistic regression中，可通過“極大似然法”（maximum likelihood method）來估計(jì)參數(shù)。給定由n個(gè)屬性描述的示例 x=（x1；x2；…；xn），對(duì)率回歸模型最大化“對(duì)數(shù)似然”（log-likelihood）。Logistic regression 主要是用極大似然估計(jì)來學(xué)習(xí)的[12]。

單個(gè)樣本的后驗(yàn)概率為

整個(gè)樣本的后驗(yàn)概率為

其中，

即令每個(gè)樣本屬于其真實(shí)標(biāo)記的概率越大越好。

最大化式（13），等價(jià)于最小化

式（14）是關(guān)于θ的高階可導(dǎo)連續(xù)凸函數(shù)，根據(jù)凸優(yōu)化理論，梯度下降法（gradient descent method）、牛頓法（Newton method）等經(jīng)典的數(shù)值優(yōu)化算法均可求得其最優(yōu)解。

梯度下降法更新參數(shù)θ使得損失函數(shù)最小

由BGD的迭代公式

當(dāng)樣本集m數(shù)據(jù)量很大時(shí)，批量梯度下降算法（BGD）的復(fù)雜度很高，迭代的收斂速度很慢。所以，為了減少?gòu)?fù)雜度，更偏向地選用隨機(jī)梯度下降法（SGD）。

3 算例分析

3.1 梯度下降法求解線性回歸模型

該例選擇的數(shù)據(jù)集是某地的房屋價(jià)格，輸入數(shù)據(jù)x（i）是生活面積和房間數(shù)量，輸出數(shù)據(jù)y（i）為價(jià)格，共m=47個(gè)訓(xùn)練樣本。

由式（5）可知，梯度下降算法的每次迭代都受到學(xué)習(xí)率（learning rate）的影響。如果學(xué)習(xí)速度太小，則所需的迭代次數(shù)太多；如果學(xué)習(xí)率過大，那么有可能會(huì)錯(cuò)過局部最小值，導(dǎo)致無法收斂，通常在0.001≤α≤10中選擇合適的學(xué)習(xí)率α。

該例選定初始學(xué)習(xí)率α=0.01，通過MATLAB實(shí)現(xiàn)梯度下降法更新參數(shù)θ，觀察損失函數(shù)J（θ）變化，相應(yīng)地調(diào)整α的值， 分別為 0.01，0.03，0.1，0.3，1，1.3 比較不同的學(xué)習(xí)率（learning rate）下的 J（θ）收斂速度。 在不同的學(xué)習(xí)率（learning rate）下分別進(jìn)行50次迭代，每次迭代時(shí)，計(jì)算并保存J（θ）的值。在最后一次迭代時(shí)，返回輸出J（θ）關(guān)于迭代次數(shù)的曲線。

由圖4所示可知，損失函數(shù)J（θ）在梯度下降法不同的學(xué)習(xí)率下收斂速度不同：當(dāng)α很小為0.01時(shí)，損失函數(shù)J（θ）收斂很慢；當(dāng)α＝1時(shí)，損失函數(shù)J（θ）收斂很快，為最佳學(xué)習(xí)率。在最佳學(xué)習(xí)率α＝1下MATLAB輸出結(jié)果為θ0＝430 413， θ1＝110 631， θ2＝－6 649。

圖4 損失函數(shù)關(guān)于迭代次數(shù)的曲線圖

3.2 牛頓法求解Logistic regression模型

Newton法迭代格式

高維下Newton法的更新公式

在Logistic regression中，

上式為向量形式，其中 x（i）∈Rn+1，x（i）（x（i））T∈R（n+1）×（n+1）。 hθ（x（i）），y（i）是標(biāo)量。

現(xiàn)假設(shè)有數(shù)據(jù)集代表了40個(gè)錄取與40個(gè)未被錄取的學(xué)生，數(shù)據(jù)集選自斯坦福大學(xué)Deep learning[7]，每（xi，yi）個(gè)樣本分別代表學(xué)生在兩次考試中的成績(jī)與是否被錄取標(biāo)簽。

目標(biāo)：建立Logistic regression，判斷某高校會(huì)錄取一學(xué)生的概率，分類標(biāo)準(zhǔn)為學(xué)生在兩次考試中的成績(jī)。

Problem：

（?。﹨?shù)θ在Newton法第幾次迭代收斂。

（ⅱ）若有一學(xué)生的第一次考試成績(jī)是20，第二次成績(jī)是80。求他不被該學(xué)校錄取的概率。

該例采用Newton法最小化損失函數(shù)，為了方便計(jì)算迭代次數(shù)置 θ＝0，每次迭代后計(jì)算 J（θ）并作圖。

MATLAB繪制決策邊界 （Decision boundary）（如圖5所示）：P（y＝1|x；θ）＝g（θTx）＝0.5 i.e.θTx＝0。

對(duì)于上述問題，MATLAB編程實(shí)現(xiàn)結(jié)果（見表2）：這位第一次考試成績(jī)是20，第二次成績(jī)是80的學(xué)生，不被該學(xué)校錄取的概率為 0.668 0。 θ1＝－16.378 7，θ2＝0.148 3，θ3＝0.158 9。

圖5 數(shù)據(jù)集樣本分布圖

表2 損失函數(shù)值

由圖6所示可知：Newton法在迭代5次左右收斂，且收斂速度較快。

4 結(jié)語

在機(jī)器學(xué)習(xí)的訓(xùn)練算法中，Newton法雖然收斂速度較快，但求解高階導(dǎo)數(shù)與Hesse陣時(shí)復(fù)雜度較高，通常使用梯度下降法最小化損失函數(shù)。當(dāng)數(shù)據(jù)集樣本量較小時(shí)，使用隨機(jī)梯度下降法（SGD）噪聲點(diǎn)較多；當(dāng)樣本量很大時(shí)，采用隨機(jī)梯度下降法（SGD）更新參數(shù)通常只需一個(gè)小的迭代次數(shù)，就可以達(dá)到相對(duì)較優(yōu)的擬合效果。因此，在實(shí)際的應(yīng)用中，需根據(jù)不同的數(shù)據(jù)集采用不同的梯度下降法。

圖6 損失函數(shù)與迭代次數(shù)關(guān)系圖

[1]CHEN X W，LIN X.Big data deep learning：challenges and perspectives[J].Access，IEEE，2014（2）：514-525.

[2]袁亞湘，孫文瑜.最優(yōu)化理論與方法[M].北京：科學(xué)出版社，1997：108-121.

[3]SHOR N Z，KIWIEL K C，RUSZCAYNSKI A.Minimization Methods for Non-Differentiable Functions[M].Berlin－Heidelberg－New York－Tokyo：Springer－Verlag，1985：885-888.

[4]SHOR N Z.Minimization Methods for Non-Differentiable Functions[M].Volume 3.Science&Business Media：Springer，2012：93-146.

[5]BOTTOU L，BOUSQUET O.Learning Using Large Datasets[M].Amsterdam：Mining Massive Data Sets for Security，2008.

[6]BOTTOU L.Large-Scale Machine Learning with Stochastic Gradient Descent[M].HD：Physica-Verlag，2010：177－186.

[7]SAMY BENGIO，TOM DEAN，ANDREW NG.Deep Learning－Exercise：Linear Regression[EB/OL].[2016-03-30].http：//openclassroom.stanford.edu/Main Folder/Document Page.php?course=Deep Learning&doc=exercises/ex2/ex2.html.

[8]SAMY BENGIO，TOM DEAN，ANDREW NG.Deep Learning－Exercise：Logistic Regression[EB/OL].[2016-03-30].http：//openclassroom.stanford.edu/Main Folder/Document Page.php?course=Deep Learning&doc=exercises/ex4/ex4.html.

[9]郭躍東，宋旭東.梯度下降法的分析和改進(jìn)[J].科技展望，2016，15：115-117.

[10]周志華.機(jī)器學(xué)習(xí)[M].北京：清華大學(xué)出版社，2016：53-60.

[11]汪寶彬，戴濟(jì)能.隨機(jī)梯度下降法的收斂速度[J].數(shù)學(xué)雜志，2012（1）：74-78.

[12]李航.統(tǒng)計(jì)學(xué)習(xí)方法[M].北京：清華大學(xué)出版社，2012：78-93.