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

俞藝涵，付鈺，吳曉平

?

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

俞藝涵，付鈺，吳曉平

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

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

1 引言

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

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

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

2 差分隱私保護

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

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

3 MapReduce框架下的DP-SGD算法

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

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

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

3.1 算法設計

3.2 隱私預算及隱私性分析

3.3 效率性及可靠性分析

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

2) 閾值函數()

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

5) 算法終止參數、final、max、

4 算法效率及可用性實驗

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

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

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

4.1 算法運行效率實驗

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

圖2 算法運行時間

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

圖3 運行時間差值隨數據量變化情況

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

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

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

圖5 各算法運行時間對比

4.2 算法可用性實驗

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

5 結束語

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

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

付鈺（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)