謝云軒

(南京航空航天大學(xué)，江蘇 南京 210000)

如今，AI技術(shù)幾乎在每個(gè)行業(yè)都顯示出其獨(dú)特的優(yōu)勢。優(yōu)勢之一便來自大數(shù)據(jù)驅(qū)動。雖然對大數(shù)據(jù)的挖掘用于研究與決策可極大地改善社會體系，但是數(shù)據(jù)的共享同時(shí)也伴隨隱私的泄露。因此必須保護(hù)那些提供個(gè)人身份信息等各種機(jī)密數(shù)據(jù)的用戶的隱私。比如當(dāng)研究機(jī)構(gòu)使用這些信息進(jìn)行模型訓(xùn)練并將模型公開時(shí)，隱私信息可能會泄露。因此，有必要在模型訓(xùn)練過程中增加隱私保護(hù)技術(shù)。

在數(shù)據(jù)挖掘的眾多方法中聚類(Clustering)是一種較流行的無監(jiān)督學(xué)習(xí)手段，其將數(shù)據(jù)集劃分為多個(gè)由相似示例組成的簇，使得同一簇內(nèi)的任何兩個(gè)示例的相似性大于不同一簇的任意兩個(gè)示例的相似性。然而，對于大規(guī)模數(shù)據(jù)或分布式存儲數(shù)據(jù)，一般的單機(jī)聚類算法無法滿足對其聚類的訓(xùn)練需求，即使可行，訓(xùn)練的時(shí)間代價(jià)也過于高昂。因此，對單機(jī)聚類算法進(jìn)行分布式改造，減少對大規(guī)模數(shù)據(jù)或分布式存儲數(shù)據(jù)訓(xùn)練的時(shí)間成本，是提高其伸縮性的有效途徑。

在分布式計(jì)算中，不同節(jié)點(diǎn)通過在迭代更新中解決本地子問題并上傳解，從而求得全局閉式解，達(dá)到整個(gè)模型的收斂。但是，不同節(jié)點(diǎn)的通信過程會帶來隱私泄露的風(fēng)險(xiǎn)。因此，在迭代通信中，需要引入隱私保護(hù)技術(shù)確保隱私?jīng)]有泄露的風(fēng)險(xiǎn)。

因而近年隱私保護(hù)理念持續(xù)受到人們的關(guān)注，其在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和深度學(xué)習(xí)等許多領(lǐng)域都得到廣泛的應(yīng)用。其中差分隱私通過混淆查詢響應(yīng)來防止對手獲得關(guān)于隱私數(shù)據(jù)的信息，可以為個(gè)體隱私提供嚴(yán)格的保證而得到廣泛研究。具體而言，差分隱私將隨機(jī)噪聲加入待通訊的數(shù)據(jù)，從而避免攻擊者執(zhí)行攻擊來推測數(shù)據(jù)集的若干敏感信息。

盡管學(xué)界已提出了極其豐碩的高性能聚類算法，比如DeepClustering等，但對大量現(xiàn)有聚類算法不做選擇地改造并不實(shí)際。因此本文將隱私保護(hù)改造局限于相對簡單但又有代表性的聚類算法，目的不是提出新的單機(jī)聚類算法，而是示范如何讓相對簡單但又有代表性的聚類算法適應(yīng)聯(lián)邦學(xué)習(xí)環(huán)境，使之發(fā)揮更大的潛能。

軟大間隔聚類(Soft Large Margin Clustering, SLMC)性能相對認(rèn)可又簡單，直接將數(shù)據(jù)映射到預(yù)定的個(gè)輸出標(biāo)記實(shí)現(xiàn)聚類。除了不同于FCM(Fuzzy C-Means)在數(shù)據(jù)空間內(nèi)的聚類之外，其作為判別型算法在標(biāo)記空間進(jìn)行聚類產(chǎn)生的良好性能和一定程度的可解釋性，并受到后續(xù)關(guān)注。因此本文選擇將其進(jìn)行隱私保護(hù)優(yōu)化。當(dāng)面對潛在的隱私泄露風(fēng)險(xiǎn)時(shí)，分布式軟大間隔聚類(Distributed Sparse SLMC, DS-SLMC)與其他分布式聚類算法一樣，遭遇了類似的瓶頸。因此引入隱私保護(hù)改造是一個(gè)自然選擇。然而，改造的挑戰(zhàn)是如何在保持原有聚類算法收斂速度和準(zhǔn)確度的同時(shí)，降低隱私泄露的風(fēng)險(xiǎn)。需要對改造后的算法進(jìn)行理論證明，看其是否符合差分隱私準(zhǔn)則，并利用實(shí)驗(yàn)進(jìn)行驗(yàn)證。

本文為了提高SLMC的隱私保護(hù)能力，發(fā)展出差分隱私軟大間隔聚類(Differentially Private SLMC, DP-SLMC)。具體來說，在DS-SLMC迭代的過程中加入隨機(jī)高斯噪聲，為個(gè)體隱私提供嚴(yán)格的保證。同時(shí)通過-zCDP給出嚴(yán)格的隱私分析，證明本文提出的模型滿足差分隱私準(zhǔn)則。

本文的具體貢獻(xiàn)如下：

1)將軟大間隔聚類與聯(lián)邦學(xué)習(xí)進(jìn)行結(jié)合，通過引入隨機(jī)高斯噪聲減少不同節(jié)點(diǎn)間通訊導(dǎo)致隱私泄露的風(fēng)險(xiǎn)，從而解決不同節(jié)點(diǎn)進(jìn)行分布式機(jī)器學(xué)習(xí)中的隱私問題。

2) 我們通過(,)-DP與-zCDP之間的關(guān)系進(jìn)行理論證明，得到DP-SLMC算法的隱私保證。確保DP-SLMC算法滿足差分隱私準(zhǔn)則。

3) 利用數(shù)據(jù)集進(jìn)行了廣泛的實(shí)驗(yàn)并對其非隱私版本進(jìn)行比較，證明所提出算法的有效性。

1 相關(guān)工作

1.1 差分隱私

差分隱私定義如定義1-3所述。

(1)

其中Z()的上界為的可能性至少為1-。

(敏感度) 查詢函數(shù)()對輸入的敏感度為：

(2)

(高斯機(jī)制).對于函數(shù)而言, 高斯機(jī)制A定義為：

(,,)=()+

(3)

其中為從N(0,)的高斯分布中采樣的噪聲。高斯機(jī)制需要將其加入函數(shù)的輸出中。當(dāng)滿足式(4)時(shí)，高斯機(jī)制A滿足(,)-DP。

(4)

零集中差分隱私(zero concentrated differential privacy,-zCDP)是一個(gè)差分隱私的松弛版本，利用Rényi散度來度量隨機(jī)函數(shù)在相鄰數(shù)據(jù)集上的分布差異。-zCDP 如定義4所述。

下文的引理1-3顯示了-zCDP 與(,)-DP 的關(guān)系以及-zCDP的合成定理.

1.2 ADMM方法

在現(xiàn)有的分布式優(yōu)化方式中，交替方向乘子法(Alternating Direction Method of Multipliers, ADMM)是一種比較流行的策略。ADMM將全局問題分解為多個(gè)局部子問題，通過協(xié)調(diào)子問題的解最終得到全局問題的最終解。ADMM對輸入不敏感，還具有方法簡單、可解釋性高與收斂性易證明的優(yōu)點(diǎn)。

s.t.+=

(5)

通過優(yōu)化這個(gè)目標(biāo)函數(shù)，算法最終會收斂到某一個(gè)全局最優(yōu)化或近似最優(yōu)結(jié)果，從而解決了分布式中的一致性優(yōu)化問題。

然而，滿足差分隱私的ADMM算法大多數(shù)都是去中心化的。比如動態(tài)zCDP(dynamic zero concentrated differential privacy)在每次迭代中引入具有線性衰減方差的高斯噪聲，在加速訓(xùn)練的同時(shí)保持隱私保護(hù)的效能。K-Fed算法將聯(lián)邦學(xué)習(xí)與one-shot學(xué)習(xí)結(jié)合，只需一輪通訊即可完成K-Means算法的訓(xùn)練。L-FGADMM將節(jié)點(diǎn)分為頭尾兩組，以確保每個(gè)節(jié)點(diǎn)只與其相鄰的兩個(gè)節(jié)點(diǎn)進(jìn)行通信。此外，通過對神經(jīng)網(wǎng)絡(luò)的每一層選擇不同的通信周期，L-FGADMM也減小了模型的通信負(fù)載。

1.3 分布式軟大間隔聚類

軟大間隔聚類(SLMC)由Chen于2013年提出。該模型將大間隔聚類(Maximum Margin Clustering, MMC)與軟聚類結(jié)合，在輸出空間進(jìn)行聚類，而不是在數(shù)據(jù)空間中尋找一組聚類中心。具體來說，SLMC將簇中心錨定為個(gè)輸出標(biāo)記的預(yù)定義編碼，計(jì)算決策函數(shù)和輸出空間中數(shù)據(jù)的軟隸屬度。它兼有大間隔聚類和軟聚類的優(yōu)點(diǎn)，一方面具有尋求簇間最大間隔的決策函數(shù)，另一方面通過引入軟學(xué)習(xí)原理，使每個(gè)實(shí)例都屬于具有相應(yīng)軟隸屬度的多個(gè)簇/聚類，并可通過軟隸屬度反映屬于單個(gè)簇的程度，從而具有較強(qiáng)的聚類能力。

對SLMC結(jié)合ADMM進(jìn)行分布式改造之后，優(yōu)化問題表示如下。

‖+‖‖

0≤,≤1,?=1，…，,=1，…，,

=1，…，

(6)

其中決策函數(shù)為：

(7)

該算法通過引入RBF核的顯式特征映射近似，在不降低精度的前提下降低了時(shí)間復(fù)雜度。具體而言，該算法用傅立葉變換的蒙特卡羅逼近RBF核的特征映射。特征映射的方式如式(8)所述。

(8)

為RBF核對應(yīng)高斯分布中隨機(jī)抽樣的向量。顯然，這種近似的精度會隨著樣本數(shù)量的增加而增加。在訓(xùn)練中，將會根據(jù)具體場景考慮精度與復(fù)雜度的權(quán)衡來選擇一個(gè)適當(dāng)?shù)摹?/p>

對其增廣拉格朗日優(yōu)化格式實(shí)現(xiàn)采用交替迭代策略求解，可得迭代更新式：

)-1

(9)

(10)

(11)

(12)

為了防止分母為0，故在分母處添加非負(fù)小量數(shù)。

(13)

然而，目前還沒有關(guān)于差分隱私中心化SLMC算法的研究工作。因此，本文重點(diǎn)關(guān)注中心化差分隱私ADMM算法并提出了具有隱私保證的差分隱私軟大間隔聚類算法。

2 差分隱私軟大間隔聚類

2.1 差分隱私軟大間隔聚類

算法1 隱私保護(hù)軟大間隔聚類算法輸入:λ、ρ,停止參數(shù)εs、εr,,節(jié)點(diǎn)數(shù)M、映射特征維度D、輸入數(shù)據(jù)X;輸出:軟隸屬度矩陣Um;Each learner constructs random feature map Rm(x) with the same seed.Initialize Um by FCM,k=0.Upload Um+ξk+1mto the central server where ξk+1m～N(0,σ2Im+1D).Update Zk+1 in the central server by (11).Update θ^k+lm in parallel by (9).Update Uk+lm in parallel by (10).Update αk+lm in parallel by (13).k=k+1.If not obtaining convergence then go 3.10. Output Um at each learner.

2.2 隱私保護(hù)分析

證明：根據(jù)式(6)可得：

(14)

(15)

(16)

(17)

DP-SLMC的隱私保護(hù)效用如定理1所示。

(18)

(19)

可得：

(20)

由于在整個(gè)迭代過程中每一輪都在更新與上傳系數(shù)矩陣，因此需要計(jì)算迭代過程中隱私損失的總和。

(21)

對于所有節(jié)點(diǎn), DP-SLMC被(,)-DP限制的總隱私損失為：

(22)

3 實(shí)驗(yàn)部分

本節(jié)將會通過 UCI 數(shù)據(jù)集來對本文提出的算法進(jìn)行實(shí)驗(yàn)，探究其性能。第3.1節(jié)中說明實(shí)驗(yàn)相關(guān)設(shè)置。第3.2節(jié)引入本次實(shí)驗(yàn)的對比指標(biāo)。最后進(jìn)行實(shí)驗(yàn)并對實(shí)驗(yàn)結(jié)果進(jìn)行分析，驗(yàn)證該方法的有效性。

3.1 實(shí)驗(yàn)設(shè)置

本節(jié)將與未做隱私保護(hù)的分布式SLMC進(jìn)行對比分析，進(jìn)行性能比較。

我們對待對比的算法執(zhí)行了20次獨(dú)立實(shí)驗(yàn)，在每次實(shí)驗(yàn)中使用最優(yōu)的核與參數(shù)設(shè)置，并最終記錄這些實(shí)驗(yàn)結(jié)果的平均值。所有的實(shí)驗(yàn)都是在一臺具有英特爾(R)核心(TM)四核處理器(i7CPU@3.6GHz)和16.0GB內(nèi)存的64位機(jī)器上進(jìn)行的。表2描述了實(shí)驗(yàn)數(shù)據(jù)集的屬性。

表2 數(shù)據(jù)集屬性

3.2 評估指標(biāo)

雖然本文提出的是無監(jiān)督分布式聚類算法，但在訓(xùn)練時(shí)可通過帶類別標(biāo)簽的數(shù)據(jù)集進(jìn)行訓(xùn)練。具體來說，在訓(xùn)練時(shí)將類別信息剔除，然后將聚類的結(jié)果與真實(shí)標(biāo)簽相比較。因此可采用聚類準(zhǔn)確度(Clustering Accuracy, CA)來對算法進(jìn)行性能評價(jià)。

(23)

代表第聚類標(biāo)簽，而代表真實(shí)標(biāo)簽。(,)則代表屬于真實(shí)類別而被預(yù)測為類別的數(shù)據(jù)個(gè)數(shù)。我們通過比較預(yù)測聚類的標(biāo)簽與真實(shí)標(biāo)簽的方式，來確定聚類的準(zhǔn)確度。顯然這個(gè)數(shù)值是越大越好。

此外，由于本文提出的是聯(lián)邦聚類算法，因此也將與未進(jìn)行隱私保護(hù)的分布式軟大間隔聚類(DS-SLMC)進(jìn)行收斂速度的對比。

3.3 實(shí)驗(yàn)分析

圖1顯示了DP-SLMC算法與DS-SLMC算法目標(biāo)函數(shù)值的對比。DP-SLMC與DS-SLMC的收斂曲線基本吻合，證明二者收斂速度并無太大差異。這個(gè)符合我們的直覺，即對交換變量加入符合差分隱私要求的噪聲對收斂過程與函數(shù)值影響較小。這個(gè)實(shí)驗(yàn)證明即使加入噪聲，只要控制噪聲的大小，噪聲本身對模型的收斂無法造成較大的干擾。

(a) Dry Bean

DP-SLMC在不同隱私預(yù)算下的目標(biāo)函數(shù)值與準(zhǔn)確度對比如圖2所示。在隱私預(yù)算較小的情況下，由于加入的噪聲過多，DP-SLMC的目標(biāo)函數(shù)值與準(zhǔn)確度相比，DS-SLMC算法表現(xiàn)不佳。但隨著隱私預(yù)算的增加，加入的噪聲逐漸減少，DP-SLMC的目標(biāo)函數(shù)值與準(zhǔn)確度越來越接近DS-SLMC算法。這個(gè)實(shí)驗(yàn)說明，保證差分隱私的前提下，只要給予足量的隱私預(yù)算，噪聲本身對算法的準(zhǔn)確度無法造成較大的干擾。在實(shí)際應(yīng)用場景中，可通過準(zhǔn)確率與隱私保護(hù)需求的權(quán)衡來決定隱私預(yù)算的大小，從而讓算法最大限度地滿足需求。

(a) Dry Bean

4 結(jié) 論

提出了一種聯(lián)邦軟大間隔聚類算法，將原聚類算法與隱私保護(hù)進(jìn)行結(jié)合。為了實(shí)現(xiàn)這個(gè)目標(biāo)，我們將原始的聚類問題中容易發(fā)生隱私泄露的通信環(huán)節(jié)加噪，使其滿足差分隱私準(zhǔn)則，從而達(dá)到隱私保護(hù)效果。而實(shí)驗(yàn)結(jié)果也表明本文提出的算法在降低隱私泄漏風(fēng)險(xiǎn)的前提下，依舊有貼近原聚類算法的性能與較快的收斂速度。此外，我們也通過實(shí)驗(yàn)驗(yàn)證DP-SLMC在不同數(shù)據(jù)集上都擁有良好的聚類性能。