MapReduce框架下支持差分隱私保護的隨機梯度下降算法

俞藝涵，付鈺，吳曉平

?

MapReduce框架下支持差分隱私保護的隨機梯度下降算法

俞藝涵，付鈺，吳曉平

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

機器學習；隨機梯度下降；MapReduce；差分隱私保護；拉普拉斯機制

1 引言

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

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

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

2 差分隱私保護

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

此外，差分隱私保護存在以下2個方面的組合性質[13]，是將差分隱私保護運用到反復迭代過程中，證明算法滿足差分隱私保護以及合理分配差分隱私預算的基礎。

3 MapReduce框架下的DP-SGD算法

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

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

表1 DP-SGD算法設計符號說明

3.1 算法設計

3.2 隱私預算及隱私性分析

3.3 效率性及可靠性分析

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

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

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

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

4 算法效率及可用性實驗

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

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

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

4.1 算法運行效率實驗

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

圖2 算法運行時間

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

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

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

圖4 各算法隨機噪聲添加位置示意

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

圖5 各算法運行時間對比

4.2 算法可用性實驗

圖6 各算法分類準確性隨隱私預算變化情況

5 結束語

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

[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]. 計算機學報, 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] 何賢芒, 王曉陽, 陳華輝,等. 差分隱私保護參數(shù)的選取研究[J]. 通信學報, 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-），男，浙江金華人，海軍工程大學博士生，主要研究方向為信息系統(tǒng)安全、隱私保護等。

付鈺（1982-），女，湖北武漢人，博士，海軍工程大學副教授、碩士生導師，主要研究方向為信息安全風險評估等。

吳曉平（1961-），男，山西新絳人，博士，海軍工程大學教授、博士生導師，主要研究方向為信息安全、密碼學等。

2017-06-19；

2017-12-19

國家自然科學基金資助項目（No.61100042）；國家社科基金資助項目（No.15GJ003-201）

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