MapReduce框架下支持差分隱私保護(hù)的隨機(jī)梯度下降算法

俞藝涵，付鈺，吳曉平

?

MapReduce框架下支持差分隱私保護(hù)的隨機(jī)梯度下降算法

俞藝涵，付鈺，吳曉平

（海軍工程大學(xué)信息安全系，湖北 武漢 430033）

機(jī)器學(xué)習(xí)；隨機(jī)梯度下降；MapReduce；差分隱私保護(hù)；拉普拉斯機(jī)制

1 引言

機(jī)器學(xué)習(xí)（ML, machine learning）作為人工智能的核心，可以利用現(xiàn)有數(shù)據(jù)，通過(guò)歸納、綜合等方法使計(jì)算機(jī)實(shí)現(xiàn)具備自我學(xué)習(xí)與自我更新的功能。梯度下降算法是一種典型的求解無(wú)約束優(yōu)化問(wèn)題的方法，主要思想是朝著負(fù)梯度方向?qū)で竽繕?biāo)的最優(yōu)解。由于該算法具有適用性強(qiáng)、優(yōu)化效果好等優(yōu)點(diǎn)，其在機(jī)器學(xué)習(xí)中得到了普遍應(yīng)用。隨機(jī)梯度下降（SGD, stochastic gradient descent）算法作為梯度下降算法的一種，由于其在每次迭代過(guò)程中不需要遍歷所有數(shù)據(jù)，更適合運(yùn)用在大數(shù)據(jù)背景下的機(jī)器學(xué)習(xí)中，但其仍存在以下2個(gè)方面的問(wèn)題。1) 隨著大數(shù)據(jù)時(shí)代的數(shù)據(jù)量越來(lái)越大，需用分布式計(jì)算架構(gòu)來(lái)滿足隨機(jī)梯度下降算法的計(jì)算需求。而在分布式計(jì)算架構(gòu)下，隨機(jī)梯度下降算法在每個(gè)計(jì)算節(jié)點(diǎn)所用樣本的不全面性、節(jié)點(diǎn)間數(shù)據(jù)通信頻繁造成開銷過(guò)大等問(wèn)題，都會(huì)導(dǎo)致算法的收斂速度下降[1]。如何在分布式計(jì)算框架下進(jìn)行快速隨機(jī)梯度下降算法的實(shí)現(xiàn)是亟待解決的關(guān)鍵性問(wèn)題。2) 隨機(jī)梯度下降算法在幫助人們運(yùn)用機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等技術(shù)不斷探索、利用數(shù)據(jù)中有價(jià)值的信息，并以此作為評(píng)估、預(yù)測(cè)和決策等行為依據(jù)的同時(shí)，也存在著泄露數(shù)據(jù)集中敏感數(shù)據(jù)的風(fēng)險(xiǎn)，威脅數(shù)據(jù)隱私安全[2]。如何在利用大數(shù)據(jù)的同時(shí)，保證大數(shù)據(jù)中的敏感數(shù)據(jù)安全是近年來(lái)的研究熱點(diǎn)。

針對(duì)問(wèn)題1)，國(guó)內(nèi)外學(xué)者做出了許多卓有成效的工作。文獻(xiàn)[3]運(yùn)用抽樣概率的思想，使用特殊非均勻采樣策略構(gòu)建minibatch來(lái)減少隨機(jī)梯度差異，但其本質(zhì)需要依賴樣本之間的直接關(guān)聯(lián)性；文獻(xiàn)[4]通過(guò)記錄歷史梯度，并在當(dāng)前迭代中使用自適應(yīng)平均的歷史梯度來(lái)減少迭代中隨機(jī)梯度的方差。然而，頻繁的記錄歷史梯度將給存在眾多參數(shù)的機(jī)器學(xué)習(xí)帶來(lái)額外的負(fù)擔(dān)。文獻(xiàn)[5]提出采用殘差最小化框架，修正隨機(jī)梯度方向，提高隨機(jī)梯度的穩(wěn)定性，同時(shí)采用半隨機(jī)梯度思想并提出一種分層半隨機(jī)梯度下降新方法，來(lái)提高收斂速度。由于隨機(jī)梯度下降算法不可避免地將出現(xiàn)多次更新迭代，這使MapReduce等分布式計(jì)算架構(gòu)在處理隨機(jī)梯度下降算法時(shí)，會(huì)出現(xiàn)因節(jié)點(diǎn)間的反復(fù)數(shù)據(jù)傳遞而造成的通信開銷過(guò)大的問(wèn)題。文獻(xiàn)[6]提出在每一個(gè)分布式計(jì)算節(jié)點(diǎn)上完整地執(zhí)行一遍梯度下降算法，通過(guò)平均模型合并得到最終模型。該方法減少了計(jì)算過(guò)程中的通信開銷，但每一個(gè)節(jié)點(diǎn)的數(shù)據(jù)存在局限性，沒有利用全局?jǐn)?shù)據(jù)來(lái)提高運(yùn)算性能。同時(shí)，在模型合并時(shí)，簡(jiǎn)單平均合并沒有考慮到模型之間存在的差異性，可能會(huì)降低算法的收斂速度和最終模型的可用性。文獻(xiàn)[7]利用文獻(xiàn)[8]中提出的蝴蝶狀通信機(jī)制，在每一輪迭代中，每個(gè)節(jié)點(diǎn)將迭代模型僅發(fā)送給另一個(gè)節(jié)點(diǎn)，并接受一個(gè)模型對(duì)本地模型進(jìn)行更新。這樣可使每一個(gè)節(jié)點(diǎn)能夠充分利用全局?jǐn)?shù)據(jù)來(lái)提高算法收斂速度與性能。同時(shí)，文獻(xiàn)[7]還對(duì)模型的合并方法進(jìn)行了優(yōu)化，將各個(gè)更新模型的性能作為模型合并的加權(quán)依據(jù)，由此提高了算法性能。針對(duì)問(wèn)題2)，部分學(xué)者將差分隱私（DP, differential privacy）保護(hù)引入隨機(jī)梯度下降算法中，以此來(lái)應(yīng)對(duì)大數(shù)據(jù)環(huán)境下的隱私泄露問(wèn)題。文獻(xiàn)[9]和文獻(xiàn)[10]所提方法為目前較為先進(jìn)的將差分隱私保護(hù)運(yùn)用到隨機(jī)梯度下降算法中的方法。文獻(xiàn)[9]在隨機(jī)梯度下降算法的每次迭代中加入擾動(dòng)噪聲，以此達(dá)到差分隱私保護(hù)的要求；文獻(xiàn)[10]通過(guò)子集采樣的方法來(lái)減少每次迭代的噪聲量，同時(shí)可以保證最佳收斂。但是，以上2種方法都存在私密性與效率性以及可用性之間的矛盾，即保證私密性時(shí)，算法的性能以及最終模型的可用性將下降；相反，保證效率性與可用性時(shí)，擾動(dòng)噪聲的添加可能難以保證差分隱私保護(hù)的要求。

基于此，本文提出了一種在分布式計(jì)算環(huán)境下將差分隱私保護(hù)技術(shù)應(yīng)用到隨機(jī)梯度下降算法中，同時(shí)緩解數(shù)據(jù)私密性與算法效率性矛盾的新算法。該算法通過(guò)合理的數(shù)據(jù)分配方法和模型合并策略來(lái)提高隨機(jī)梯度下降算法的收斂速度與性能，并以策略性的差分隱私保護(hù)預(yù)算分配進(jìn)行隨機(jī)噪聲添加，使隨機(jī)梯度下降算法的輸出結(jié)果滿足差分隱私。

2 差分隱私保護(hù)

差分隱私保護(hù)通常對(duì)數(shù)據(jù)進(jìn)行隨機(jī)噪聲添加和隨機(jī)響應(yīng)來(lái)達(dá)到隱私保護(hù)目的，主要的實(shí)現(xiàn)機(jī)制分別為拉普拉斯機(jī)制與指數(shù)機(jī)制。其中，拉普拉斯機(jī)制[12]適用于數(shù)值型保護(hù)，是隨機(jī)梯度下降算法中最常用的差分隱私保護(hù)機(jī)制。查詢函數(shù)的全局敏感度是決定滿足差分隱私保護(hù)的隨機(jī)噪聲大小的關(guān)鍵因素。全局敏感度定義如下。

此外，差分隱私保護(hù)存在以下2個(gè)方面的組合性質(zhì)[13]，是將差分隱私保護(hù)運(yùn)用到反復(fù)迭代過(guò)程中，證明算法滿足差分隱私保護(hù)以及合理分配差分隱私預(yù)算的基礎(chǔ)。

3 MapReduce框架下的DP-SGD算法

本文所提算法的功能是在MapReduce分布式計(jì)算框架下，實(shí)現(xiàn)對(duì)隨機(jī)梯度下降算法提供有效的差分隱私保護(hù)，并保證算法具有較高的效率性。即保證當(dāng)數(shù)據(jù)集中改變?nèi)魏我粋€(gè)記錄時(shí)，隨機(jī)梯度下降算法所得到目標(biāo)模型的變化不會(huì)泄露數(shù)據(jù)集的隱私信息。也就是說(shuō)，擁有豐富背景知識(shí)的攻擊者無(wú)法通過(guò)手頭上與目標(biāo)數(shù)據(jù)集高度相似（極端情況下只相差一條記錄）的數(shù)據(jù)集，通過(guò)目標(biāo)模型的建立得到數(shù)據(jù)集中單個(gè)數(shù)據(jù)的隱私信息。

現(xiàn)有的差分隱私保護(hù)隨機(jī)梯度下降算法[9,10]存在的最主要問(wèn)題是算法效率性較低，其主要原因是隨機(jī)梯度下降算法需要通過(guò)反復(fù)迭代來(lái)使目標(biāo)模型收斂，而算法的反復(fù)迭代將造成在MapReduce等分布式計(jì)算框架計(jì)算過(guò)程中，產(chǎn)生大量節(jié)點(diǎn)之間的通信開銷；而在每輪迭代中，添加隨機(jī)噪聲也不利于目標(biāo)模型的收斂。因此，本文對(duì)MapReduce框架下的DP-SGD算法進(jìn)行設(shè)計(jì)，采取了改進(jìn)的數(shù)據(jù)分發(fā)與模型合并方案以及隨機(jī)噪聲的添加方法。算法主要符號(hào)說(shuō)明如表1所示。

表1 DP-SGD算法設(shè)計(jì)符號(hào)說(shuō)明

3.1 算法設(shè)計(jì)

3.2 隱私預(yù)算及隱私性分析

3.3 效率性及可靠性分析

本文所提MapReduce框架下的DP-SGD算法通過(guò)關(guān)鍵參數(shù)的設(shè)置，對(duì)隱私預(yù)算、計(jì)算資源進(jìn)行合理規(guī)劃，并優(yōu)化了數(shù)據(jù)分配以及模型合并的方法。

2) 閾值函數(shù)()

圖1 MapReduce 框架下的 DP-SGD 算法流程

5) 算法終止參數(shù)、final、max、

4 算法效率及可用性實(shí)驗(yàn)

本文所提算法主要是對(duì)MapReduce計(jì)算環(huán)境下的隨機(jī)梯度下降算法進(jìn)行優(yōu)化，并提供差分隱私保護(hù)。算法的隱私性已得到證明，為此，在實(shí)驗(yàn)中主要對(duì)算法的效率性與可用性進(jìn)行實(shí)驗(yàn)。

實(shí)驗(yàn)中的分布式計(jì)算平臺(tái)由5臺(tái)IBM X系列機(jī)架式服務(wù)器組成，每臺(tái)服務(wù)器配置如下：3.30 GHz CPU，2.99 GB內(nèi)存，Ubuntu12.04操作系統(tǒng)，并部署Hadoop0.20.2。算法由Java軟件進(jìn)行開發(fā)。

實(shí)驗(yàn)選擇MNIST手寫圖像數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集。MNIST是由Google實(shí)驗(yàn)室和紐約大學(xué)柯朗研究所建立的手寫數(shù)字?jǐn)?shù)據(jù)庫(kù)，包含60 000張訓(xùn)練圖像和10 000張測(cè)試圖像。實(shí)驗(yàn)分別采用文獻(xiàn)[9]中的SCS13算法、文獻(xiàn)[10]中的BST14算法以及本文所提算法建立相同邏輯回歸模型，對(duì)MNIST數(shù)據(jù)集進(jìn)行手寫數(shù)字分類實(shí)驗(yàn)。

4.1 算法運(yùn)行效率實(shí)驗(yàn)

算法運(yùn)行時(shí)間如圖2所示，可以發(fā)現(xiàn)A算法由于隨機(jī)噪聲的添加，運(yùn)行時(shí)間較B算法有明顯增加，且隨著數(shù)據(jù)量的增大，運(yùn)行時(shí)間的增量也隨之增加。這是由于數(shù)據(jù)量的增加要求目標(biāo)模型需要更多的迭代更新次數(shù)才能達(dá)到算法完成的標(biāo)準(zhǔn)，而每次模型迭代更新時(shí)卻需要加入阻礙模型收斂的隨機(jī)噪聲引起的。同時(shí)，每輪迭代中，都會(huì)有一部分Map節(jié)點(diǎn)與Reduce節(jié)點(diǎn)之間、Reduce節(jié)點(diǎn)與主節(jié)點(diǎn)之間以及子節(jié)點(diǎn)與主節(jié)點(diǎn)之間的數(shù)據(jù)傳遞所造成的額外通信開銷，這也導(dǎo)致了算法運(yùn)行時(shí)間的增加。

圖2 算法運(yùn)行時(shí)間

運(yùn)行時(shí)間差值隨數(shù)據(jù)變化情況如圖3所示。由圖3(a)可以看出，當(dāng)系統(tǒng)啟動(dòng)4個(gè)子節(jié)點(diǎn)時(shí)A算法和B算法的運(yùn)行時(shí)間比啟動(dòng)一個(gè)子節(jié)點(diǎn)時(shí)有顯著減少，且隨著數(shù)據(jù)量的增加，運(yùn)行時(shí)間的減少量也在增加；由圖3(b)可以看出，A算法相對(duì)于B算法在系統(tǒng)啟動(dòng)4個(gè)子節(jié)點(diǎn)時(shí)小于系統(tǒng)僅啟動(dòng)一個(gè)子節(jié)點(diǎn)時(shí)的運(yùn)行時(shí)間增量（由于添加隨機(jī)噪聲造成的增量）。

圖3 運(yùn)行時(shí)間差值隨數(shù)據(jù)量變化情況

由此可以認(rèn)為，本文所提算法能夠使需要反復(fù)迭代的隨機(jī)梯度下降算法在提供差分隱私保護(hù)的同時(shí)，在MapReduce框架下進(jìn)行高效率的計(jì)算，并能夠隨計(jì)算節(jié)點(diǎn)的增加而提高算法的運(yùn)行效率。同時(shí)，本文所提算法與SCS13算法和BST14算法在噪聲添加方面采取了不同策略，如圖4所示。

圖4 各算法隨機(jī)噪聲添加位置示意

各算法運(yùn)行時(shí)間對(duì)比如圖5所示。由圖5可知，本文所提算法在耗時(shí)上對(duì)比SCS13算法和BST14算法具有明顯優(yōu)勢(shì)，且數(shù)據(jù)量越大優(yōu)勢(shì)越明顯。

圖5 各算法運(yùn)行時(shí)間對(duì)比

4.2 算法可用性實(shí)驗(yàn)

圖6 各算法分類準(zhǔn)確性隨隱私預(yù)算變化情況

5 結(jié)束語(yǔ)

本文在MapReduce計(jì)算框架下，提出了一種能同時(shí)滿足效率性與私密性的差分隱私—隨機(jī)梯度下降新算法DP-SGD。該算法通過(guò)合理的計(jì)算資源分配與隨機(jī)噪聲添加策略，在滿足差分隱私保護(hù)要求的同時(shí)，緩解了隨機(jī)梯度下降算法因反復(fù)迭代在分布式計(jì)算框架下的通信開銷，提高了算法的計(jì)算效率并保證了數(shù)據(jù)的可用性。下一步可進(jìn)行以下2個(gè)方面工作：1) 在本文所提算法基礎(chǔ)上，對(duì)算法中的參數(shù)設(shè)置方案進(jìn)一步優(yōu)化，分析各個(gè)參數(shù)在對(duì)算法效率性影響上的內(nèi)在關(guān)系，進(jìn)一步提高算法的效率；2) 研究算法中為滿足差分隱私保護(hù)所需隨機(jī)噪聲量的最小值與數(shù)據(jù)量、迭代次數(shù)和目標(biāo)模型合并方法之間的關(guān)系，減少因隨機(jī)噪聲的添加帶來(lái)的算法在效率性與可用性上的負(fù)面影響。

[1] WU F, LI F G, KUMAR A, et al. Bolt-on differential privacy for scalable stochastic gradient descent-based analytics[C]//The 2017 ACM International Conference on Management of Data. 2017: 1307-1322.

[2] ABADI M, CHU A, GOODFELLOW I, et al. Deep learning with differential privacy[C]//The 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016:308-318.

[3] ZHAO P, ZHANG T. Stochastic optimization with importance sampling[J]. Eprint Arxiv, 2015:1-9.

[4] SCHMIDT M, ROUX N L, BACH F. Erratum to: minimizing finite sums with the stochastic average gradient[J]. Mathematical Programming, 2016, 162(5): 1.

[5] MU Y, LIU W, LIU X, et al. Stochastic gradient made stable: a manifold propagation approach for large-scale optimization[J]. IEEE Transactions on Knowledge & Data Engineering, 2015, 29(2): 458-471.

[6] ZINKEVICH M, WEIMER M, SMOLA A J, et al. Parallelized stochastic gradient descent[C]//The Conference on Neural Information Processing Systems. 2011:2595-2603.

[7] 陳振宏, 蘭艷艷, 郭嘉豐,等. 基于差異合并的分布式隨機(jī)梯度下降算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2015, 38(10):2054-2063.

CHEN Z H,LAN Y Y,GUO J F, et al.Distributed stochastic gradient descent with discriminative aggregating[J].Chinese Journal of Computers, 2015, 38(10):2054-2063.

[8] ZHAO H, CANNY J F. Communication-efficient distributed stochastic gradient descent with butterfly mixing[D]. Berkeley, USA: University of California, 2012.

[9] SONG S, CHAUDHURI K, SARWATE A D. Stochastic gradient descent with differentially private updates[C]//Global conference on Signal and Information Processing (GlobalSIP).2013: 245-248.

[10] BASSILY R, THAKURTA A. Private empirical risk minimization: Efficient algorithms and tight error bounds[C]//2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS).2014: 464-473.

[11] DWORK C, MCSHERRY F, NISSIM K. Calibrating noise to sensitivity in private data analysis[J]. The VLDB Endowment, 2006, 7(8):637-648.

[12] DWORK C, ROTH A. The Algorithmic foundations of differential privacy[M]. Now Publishers Inc, 2014.

[13] CHAUDHURI K, MONTELEONI C, SARWATE A D. Differentially private empirical risk minimization[J]. Journal of Machine Learning Research, 2009, 12(2):1069-1109.

[14] 何賢芒, 王曉陽(yáng), 陳華輝,等. 差分隱私保護(hù)參數(shù)的選取研究[J]. 通信學(xué)報(bào), 2015, 36(12):124-130.

HE X M,WANG X Y, CHEN H H, et al. Study on choosing the parameterin differential privacy[J].Journal on Communications, 2015, 36(12):124-130.

[15] MCSHERRY F D. Privacy integrated queries: an extensible platform for privacy-preserving data analysis[J].Communication of the ACM, 2010, 53(9):89-97.

Stochastic gradient descent algorithm preserving differential privacy in MapReduce framework

YU Yihan, FU Yu, WU Xiaoping

Department of Information Security, Naval University of Engineering, Wuhan 430033, China

Aiming at the contradiction between the efficiency and privacy of stochastic gradient descent algorithm in distributed computing environment, a stochastic gradient descent algorithm preserving differential privacy based on MapReduce was proposed. Based on the computing framework of MapReduce, the data were allocated randomly to each Map node and the Map tasks were started independently to execute the stochastic gradient descent algorithm. The Reduce tasks were appointed to update the model when the sub-target update models were meeting the update requirements, and to add Laplace random noise to achieve differential privacy protection. Based on the combinatorial features of differential privacy, the results of the algorithm is proved to be able to fulfill ε-differentially private. The experimental results show that the algorithm has obvious efficiency advantage and good data availability.

machine learning, stochastic gradient descent, MapReduce, differential privacy preserving, Laplace mechanism

TP301

A

10.11959/j.issn.1000-436x.2018013

俞藝涵（1992-），男，浙江金華人，海軍工程大學(xué)博士生，主要研究方向?yàn)樾畔⑾到y(tǒng)安全、隱私保護(hù)等。

付鈺（1982-），女，湖北武漢人，博士，海軍工程大學(xué)副教授、碩士生導(dǎo)師，主要研究方向?yàn)樾畔踩L(fēng)險(xiǎn)評(píng)估等。

吳曉平（1961-），男，山西新絳人，博士，海軍工程大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)樾畔踩?、密碼學(xué)等。

2017-06-19；

2017-12-19

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61100042）；國(guó)家社科基金資助項(xiàng)目（No.15GJ003-201）

: The National Natural Science Foundation of China (No.61100042), The National Social Science Foundation of China (No.15GJ003-201)