基于動(dòng)態(tài)約束自適應(yīng)方法抵御高維鞍點(diǎn)攻擊

李德權(quán) 許 月 薛 生

1(安徽理工大學(xué)數(shù)學(xué)與大數(shù)據(jù)學(xué)院 安徽淮南 232001) 2(安徽理工大學(xué)能源與安全學(xué)院 安徽淮南 232001)dqli@aust.edu.cn)

隨著傳感器和智能設(shè)備技術(shù)的快速發(fā)展以及在實(shí)際中的廣泛運(yùn)用，協(xié)同收集來(lái)自多個(gè)信息源的大量數(shù)據(jù)成為現(xiàn)實(shí).面對(duì)具有空間分布的海量數(shù)據(jù)的處理，作為能夠從中提取有價(jià)值信息的主要有效工具，機(jī)器學(xué)習(xí)在計(jì)算機(jī)視覺(jué)、醫(yī)療保健和金融市場(chǎng)分析等廣泛領(lǐng)域的應(yīng)用取得了巨大成功.其中分布式隨機(jī)梯度下降算法(stochastic gradient descent， SGD)作為最常用的機(jī)器學(xué)習(xí)方法之一，在每步迭代中只隨機(jī)訓(xùn)練一個(gè)樣本數(shù)據(jù)，大大減少了訓(xùn)練時(shí)間，但容易受到Byzantine攻擊[1]的影響.由于系統(tǒng)故障、軟件bug[2]、數(shù)據(jù)損壞和通信延遲等原因造成的個(gè)體或機(jī)器之間共享信息錯(cuò)誤[3]，統(tǒng)稱為Byzantine攻擊.所以，在Byzantine環(huán)境下研究分布式機(jī)器學(xué)習(xí)如何高效處理共享信息的數(shù)據(jù)是極為重要的.

Byzantine彈性指的是存在Byzantine攻擊的情況下算法仍能正常執(zhí)行的彈性區(qū)間[5].文獻(xiàn)[6]分析了經(jīng)典Byzantine與高維Byzantine的區(qū)別與聯(lián)系，如圖1所示.文獻(xiàn)[6]也將Byzantine攻擊類(lèi)型分成了3種：高斯攻擊、全知型攻擊和位翻轉(zhuǎn)型攻擊.但僅僅用了SGD去解決上述3種類(lèi)型的Byzantine攻擊的優(yōu)化問(wèn)題.

Fig. 1 Two types of Byzantine圖1 Byzantine的2種不同方式

文獻(xiàn)[7]提出用自適應(yīng)方法代替?zhèn)鹘y(tǒng)的SGD來(lái)有效解決陷入鞍點(diǎn)而無(wú)法達(dá)到最優(yōu)值的困境.通過(guò)調(diào)整隨機(jī)梯度噪聲的方向，使得噪聲能在鞍點(diǎn)處是等方向的，有助于朝正確的方向快速逃離鞍點(diǎn).但自適應(yīng)方法則面臨兩大問(wèn)題：1)與SGD相比泛化能力差；2)由于不穩(wěn)定或者極端的學(xué)習(xí)率會(huì)導(dǎo)致算法不收斂.文獻(xiàn)[8]不僅驗(yàn)證了極端學(xué)習(xí)率會(huì)導(dǎo)致算法性能差，而且提出了給學(xué)習(xí)率加上動(dòng)態(tài)約束實(shí)現(xiàn)從自適應(yīng)方法到SGD平緩過(guò)渡的方法——具有動(dòng)態(tài)約束的自適應(yīng)矩估計(jì)(adaptive moment estimation with dynamic bound， ADABOUND).結(jié)果表明這2種動(dòng)態(tài)約束自適應(yīng)方法消除了自適應(yīng)方法和SGD的泛化差異，并且提高了學(xué)習(xí)速度.

為了解決在分布式高維Byzantine環(huán)境下，能最大彈性限度抵御攻擊問(wèn)題，從而高效求解優(yōu)化問(wèn)題.仿真分析了當(dāng)目標(biāo)函數(shù)陷入鞍點(diǎn)時(shí)，動(dòng)態(tài)約束自適應(yīng)相比較于自適應(yīng)和非自適應(yīng)方法逃離鞍點(diǎn)要更快，并在數(shù)據(jù)集分類(lèi)問(wèn)題上同樣進(jìn)行了比對(duì)實(shí)驗(yàn).其次，提出了一種過(guò)濾Byzantine個(gè)體的聚合規(guī)則Saddle(·)，理論證明了它是高維Byzantine彈性的.因此，在分布式高維Byzantine環(huán)境下，采用動(dòng)態(tài)約束的自適應(yīng)優(yōu)化方法結(jié)合聚合規(guī)則Saddle(·)能夠有效避免鞍點(diǎn)攻擊.

1 預(yù)備知識(shí)

判斷鞍點(diǎn)的一個(gè)充分條件是：函數(shù)在一階導(dǎo)數(shù)為0處的Hessian矩陣為不定矩陣.

定義3.嚴(yán)格鞍函數(shù).對(duì)于所有的x，滿足下列條件：

3) 點(diǎn)x位于局部極小值附近;

則函數(shù)f(x)是嚴(yán)格鞍函數(shù)[11-12].

2) 對(duì)于指數(shù)r=2,3,…,r1+r2+…+rn-q=r，E[Aggr]r≤c1E[G]r1+c2E[G]r2+…+cn-qE[G]rn-q，其中c1,c2,…,cn-q為線性組合的相關(guān)系數(shù).

聚合規(guī)則Aggr(·)指的是滿足規(guī)則Aggr(·)的被認(rèn)為是非Byzantine個(gè)體共享的真實(shí)信息，相反則被認(rèn)為是Byzantine個(gè)體共享的虛假信息，需要被過(guò)濾掉.

Reddi等人[13]提出深度學(xué)習(xí)[14]優(yōu)化方法的一般框架(包括自適應(yīng)和非自適應(yīng)方法)：

②m|t=φt((g1,g2,…,gn)t)和v|t=Φt((g1,g2,…,gn)t);

其中，g|t為f(x|t)梯度，α為深度學(xué)習(xí)步長(zhǎng)，t為迭代時(shí)間，x|t為第t步迭代的解(x1,x2,…,xn)t，β1和β2分別對(duì)應(yīng)一階梯度和二階梯度移動(dòng)平均的指數(shù)，φt和Φt在自適應(yīng)和非自適應(yīng)中分別對(duì)應(yīng)如表1所示的值.

Table 1 Adaptive and Non-adaptive Corresponding Values表1 自適應(yīng)和非自適應(yīng)對(duì)應(yīng)值

2 優(yōu)化方法與模型建立

2.1 動(dòng)態(tài)約束自適應(yīng)方法

通過(guò)上述分析，自適應(yīng)方法易受極端學(xué)習(xí)率影響.為有效克服這一困難，動(dòng)態(tài)約束自適應(yīng)的算法思想是[8]：通過(guò)給梯度加一個(gè)閾值區(qū)間，并且上下閾值都隨時(shí)間變化最后收斂到SGD的學(xué)習(xí)率，從而實(shí)現(xiàn)自適應(yīng)方法向SGD的平緩過(guò)渡.

2.2 鞍點(diǎn)攻擊與聚合規(guī)則Saddle(·)

定義5.鞍點(diǎn)攻擊類(lèi)型為

其中，(gi)j表示第j維第i個(gè)個(gè)體的梯度值，j∈[d].i∈B時(shí)，同時(shí)滿足Hessian矩陣是不定的.鞍點(diǎn)攻擊影響梯度，從而影響學(xué)習(xí)率，導(dǎo)致目標(biāo)函數(shù)不收斂,所以需要尋求一種聚合規(guī)則過(guò)濾Byzantine個(gè)體.下面提出的聚合規(guī)則[15]可以過(guò)濾高維鞍點(diǎn)個(gè)體，實(shí)現(xiàn)抵御攻擊的目的.

定義6.聚合規(guī)則Saddle(·)為

定理1.噪聲梯度下降法能夠在多項(xiàng)式時(shí)間內(nèi)找到嚴(yán)格鞍函數(shù)的局部最小值點(diǎn)[10].

定理1驗(yàn)證了聚合規(guī)則Saddle(·)是能在有限時(shí)間內(nèi)找到函數(shù)最優(yōu)值，即逃離了鞍點(diǎn).為了驗(yàn)證聚合規(guī)則Saddle(·)更具有一般性，下面證明它是高維Byzantine彈性的.

3 聚合規(guī)則Saddle(·)

證明.

根據(jù)Jensen不等式,

以上驗(yàn)證了聚合規(guī)則Saddle(·)滿足高維Byzantine彈性的條件1).

根據(jù)等價(jià)范數(shù)的定義：有限維空間上的任何2個(gè)范數(shù)必是等價(jià)的.存在常數(shù)c1，使得

其中，r1+r2+…+rm-q=r.所以驗(yàn)證了聚合規(guī)則Saddle(·)滿足高維Byzantine彈性的條件2).

以上證明了聚合規(guī)則Saddle(·)是更具有一般性的高維Byzantine彈性，即過(guò)濾鞍點(diǎn)的聚合規(guī)則是泛化的.

證畢.

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

4.1 動(dòng)態(tài)約束自適應(yīng)方法與其他優(yōu)化算法的比較

以凸函數(shù)：

為例，其中b1，b2為隨機(jī)系數(shù).由鞍點(diǎn)判定條件知，函數(shù)ft(x1,x2)的Hessian矩陣是不定的，所以該函數(shù)存在鞍點(diǎn).通過(guò)不斷對(duì)(x1,x2)進(jìn)行梯度更新，最終找到目標(biāo)函數(shù)的最優(yōu)值.因?yàn)椴煌膬?yōu)化方法對(duì)梯度更改規(guī)則不同(即學(xué)習(xí)率不同)，所以達(dá)到目標(biāo)函數(shù)最優(yōu)值的快慢不同.

如圖2(a)所示，動(dòng)態(tài)約束自適應(yīng)(ADABOUND)方法相比較于自適應(yīng)梯度算法(adaptive gradient， ADAGRAD)、平方根改進(jìn)算法(root mean square prop， RMSPROP)、ADAM和SGD逃離鞍點(diǎn)的速度明顯比較快.圖2(b)表示動(dòng)態(tài)約束自適應(yīng)的上下閾值隨時(shí)間變化，最后都收斂到與SGD學(xué)習(xí)率一致，實(shí)現(xiàn)了自適應(yīng)到非自適應(yīng)的平緩過(guò)渡.

Fig. 2 Comparison of the optimization methods used to escape from saddle point圖2 優(yōu)化方法用于逃離鞍點(diǎn)的快慢比較

不僅如此，在隨機(jī)生成的(50 000×30)數(shù)據(jù)集中，分別用不同的優(yōu)化方法將該數(shù)據(jù)集分成10個(gè)類(lèi).邏輯回歸用以解決該分類(lèi)問(wèn)題，對(duì)于輸入的x|t，其對(duì)應(yīng)的類(lèi)標(biāo)簽為y|t，我們的目標(biāo)是訓(xùn)練分類(lèi)模型y|t=wx|t+b的參數(shù)w和b，使得屬于當(dāng)前類(lèi)的概率最大.下面實(shí)驗(yàn)通過(guò)比較錯(cuò)誤率(error rate)與誤差(error)來(lái)分析方法的優(yōu)劣.

Fig. 3 Performance comparison of data set classification by different optimization methods圖3 不同優(yōu)化方法分類(lèi)的性能比較

4.2 Byzantine環(huán)境下的動(dòng)態(tài)約束自適應(yīng)

根據(jù)2.2節(jié)提出的鞍點(diǎn)攻擊，該攻擊方式會(huì)影響梯度，所以對(duì)于基于梯度的優(yōu)化方法就會(huì)有一定程度的影響.為了證明動(dòng)態(tài)約束自適應(yīng)能控制極端梯度的影響，在Byzantine和非Byzantine環(huán)境下做了動(dòng)態(tài)約束自適應(yīng)受環(huán)境影響程度的對(duì)比實(shí)驗(yàn).并且與文獻(xiàn)[6]作比對(duì)實(shí)驗(yàn)，觀察SGD受Byzantine攻擊的影響大小.

Fig. 4 Performance comparison of optimization methods in Byzantine and non-Byzantine environments圖4 Byzantine和非Byzantine環(huán)境下的性能比較

如圖4(a)(b)，動(dòng)態(tài)約束自適應(yīng)方法相比較于SGD在Byzantine環(huán)境下不會(huì)受很大的影響.因?yàn)榻?jīng)過(guò)梯度裁剪的自適應(yīng)，不會(huì)因?yàn)樘荻鹊暮龃蠛鲂《鴮?dǎo)致不收斂.圖4(c)表示從誤差角度分析，在Byzantine和非Byzantine環(huán)境下動(dòng)態(tài)約束自適應(yīng)受影響的情況.

4.3 分布式高維Byzantine環(huán)境下的動(dòng)態(tài)約束自適應(yīng)

第3節(jié)已經(jīng)驗(yàn)證了聚合規(guī)則Saddle(·)具有高維Byzantine彈性，所以在分布式環(huán)境下鞍點(diǎn)攻擊的是任意維的個(gè)體.不同個(gè)體對(duì)應(yīng)不同的工作機(jī)器，分布式計(jì)算模型參數(shù)，然后它們向主機(jī)發(fā)送局部模型參數(shù)[16].所以在分布式環(huán)境下研究鞍點(diǎn)攻擊，通過(guò)觀察不同個(gè)體總數(shù)目的錯(cuò)誤率.

如圖5所示，不同個(gè)體總數(shù)目下動(dòng)態(tài)約束自適應(yīng)方法的分類(lèi)效果不一樣[17].由于高維Byzantine在每一維的隨機(jī)性較大，所以這也是影響圖5結(jié)果的直接原因.

5 總結(jié)與展望

結(jié)合文獻(xiàn)[8]提出的動(dòng)態(tài)約束自適應(yīng)并應(yīng)用于分布式Byzantine環(huán)境，本文主要提出一種具有高維Byzantine彈性的聚合規(guī)則Saddle(·)，可有效過(guò)濾鞍點(diǎn)攻擊的個(gè)體，從而實(shí)現(xiàn)在確保算法收斂的情況下抵御鞍點(diǎn)攻擊的目的.針對(duì)數(shù)據(jù)集分類(lèi)結(jié)果的錯(cuò)誤率和誤差2個(gè)重要指標(biāo)，通過(guò)大量數(shù)值仿真比較分析動(dòng)態(tài)約束自適應(yīng)與自適應(yīng)和非自適應(yīng)方法的優(yōu)劣性.結(jié)果表明：結(jié)合聚合規(guī)則Saddle(·)的動(dòng)態(tài)約束自適應(yīng)在分布式Byzantine環(huán)境下受鞍點(diǎn)攻擊的影響較小.

下一步工作希望能夠給出不同個(gè)體總數(shù)所對(duì)應(yīng)不同錯(cuò)誤率大小的理論解釋，并且能夠更大限度地降低錯(cuò)誤率.