壓縮降維矩陣分解算法的差分隱私推薦

楊 競，向 真，王小驥

(1. 中國電子科技集團(tuán)公司第三十研究所，四川 成都 610041；2. 93114部隊(duì)，北京 100195)

1 引言

隨著越來越多地用戶使用移動設(shè)備，利用在線商店進(jìn)行商品購買的人數(shù)也越來越多。這種數(shù)據(jù)泛濫通常意味著消費(fèi)者面臨許多選擇，這使得決策更加困難。推薦系統(tǒng)可幫助消費(fèi)者找到感興趣或者建議的項(xiàng)目[1～2]。因此，推薦系統(tǒng)在我們的日常生活中變得越來越普遍，從電影到商品的推薦。推薦系統(tǒng)可收集和挖掘用戶數(shù)據(jù)以獲得更好的用戶體驗(yàn)[3]。然而，用戶數(shù)據(jù)包括個(gè)人信息，常常會引起隱私問題。

差分隱私由于其強(qiáng)大的隱私保障能力，是解決隱私問題的常用工具。已經(jīng)有一些工作將差分隱私應(yīng)用于推薦系統(tǒng)。例如，文獻(xiàn)[4]應(yīng)用差分隱私來保護(hù)每個(gè)用戶的項(xiàng)集，但其采用隨機(jī)化算法干擾了位于預(yù)定類別內(nèi)的項(xiàng)，導(dǎo)致用戶的類別偏好可能被暴露。文獻(xiàn)[5]還提出了局部模型，其中用戶的私人數(shù)據(jù)被擾動之前提交給推薦者。文獻(xiàn)[6]提出一種RAPPor算法來收集和分析用戶數(shù)據(jù)而不侵犯隱私。RAPPor建立在隨機(jī)反應(yīng)的概念之上，它是由Warner開發(fā)的一種調(diào)查技術(shù)，用于收集敏感話題的統(tǒng)計(jì)數(shù)據(jù)。文獻(xiàn)[7]開發(fā)改進(jìn)的RAPPor實(shí)用LDP解決方案。其隨機(jī)化機(jī)制使得能夠分析分類數(shù)據(jù)和數(shù)值數(shù)據(jù)，以及基于隨機(jī)梯度下降的機(jī)器學(xué)習(xí)任務(wù)。文獻(xiàn)[8]提出一種用于差分私有矩陣分解的梯度擾動算法，以防止不可信推薦者學(xué)習(xí)任何用戶的評級或配置文件。此類文獻(xiàn)還有很多，不再贅述?，F(xiàn)有的方法均從不同的角度提出了差分隱私的改進(jìn)方案，取得了很好的效果，但是也存在不足，主要體現(xiàn)在兩個(gè)方面：①其被設(shè)計(jì)成保護(hù)用戶的評價(jià)或用戶評價(jià)的項(xiàng)目，但不能同時(shí)保護(hù)兩者。在許多情況下，用戶的項(xiàng)目集與她的評分一樣存在敏感信息，因?yàn)橥茢嘤脩魧δ男╉?xiàng)目進(jìn)行了評分可以泄露其政治觀點(diǎn)等隱私信息。②其關(guān)注于保護(hù)單個(gè)項(xiàng)目或用戶的整個(gè)項(xiàng)目及其評級中的評級值。然而，在推薦系統(tǒng)中，存在高度相關(guān)的項(xiàng)目集(例如，同一類型的電影)。掩蓋相關(guān)項(xiàng)中單個(gè)項(xiàng)的存在或不存在不足以保護(hù)用戶的敏感信息。此外，用戶通常一次上傳一組收視率。從這個(gè)意義上說，單一評級或項(xiàng)目的保護(hù)在實(shí)踐中并不適合。人們可能會試圖擴(kuò)展現(xiàn)有的方案，以便將差別隱私應(yīng)用于每個(gè)項(xiàng)目和評價(jià)。此外，這些算法中的大多數(shù)假設(shè)可信推薦場景，然而，隨著推薦服務(wù)越來越流行，許多不信任推薦者出現(xiàn)在網(wǎng)上，可能超出服務(wù)濫用用戶隱私，特別是用戶存在非對稱化時(shí)，可能存在個(gè)人數(shù)據(jù)意外泄漏問題。

本文的目標(biāo)是通過保證每個(gè)用戶的強(qiáng)隱私性，建立一個(gè)解決現(xiàn)有文獻(xiàn)局限性的推薦系統(tǒng)。在協(xié)同過濾技術(shù)中使用矩陣分解進(jìn)行推薦。我們發(fā)展了新的用于矩陣分解的差分隱私梯度下降算法。通過采用Nguyen等人建議的最新LDP梯度擾動解決方案來保護(hù)用戶的私有數(shù)據(jù)，包括項(xiàng)目、評級和配置文件。驗(yàn)證了矩陣因式分解算法的最終項(xiàng)目配置文件在用戶或不在用戶之間沒有顯著差異，從而保證每個(gè)用戶的隱私，并通過采用隨機(jī)投影降維技術(shù)，減小了大量項(xiàng)目引起的攝動誤差，該解決方案將保護(hù)用戶的項(xiàng)和評級放在一起，保證每個(gè)用戶隱私，并保持推薦質(zhì)量。

2 問題描述

2.1 算法框架

圖1 所提差分隱私推薦系統(tǒng)概述

由于各個(gè)用戶的梯度包括關(guān)于評級rij和用戶配置文件ui的信息，所以需要在每次迭代中保護(hù)用戶的梯度。因此，所提隨機(jī)擾動算法被設(shè)計(jì)為在每次迭代中滿足ε/k-LDP，以保護(hù)由項(xiàng)、評級和用戶簡檔組成的整個(gè)數(shù)據(jù)。在局部隱私模型中，評價(jià)模型中的M不能先驗(yàn)地知道，除非用戶公開他們評級的項(xiàng)目的數(shù)量。因此，本文采用n代替M來改進(jìn)所提梯度下降算法。所有參數(shù)，即n、γt、λu、λv、d和k由推薦者給出。隱私預(yù)算ε也由推薦者給出。

2.2 矩陣分解

假設(shè)n個(gè)用戶對m項(xiàng)的子集(例如，電影)進(jìn)行評級。利用M?{1，…，n}×{1，…，m}表示已生成評級的用戶/項(xiàng)對，m是項(xiàng)目的數(shù)量。令M=|M|是總評級數(shù)。利用rij表示由用戶i生成的項(xiàng)目j的評級。在實(shí)際設(shè)置中，提供的評級是稀疏的，因此M比nm小得多，而n和m都大。對于給定評級{rij：(i，j)∈M}，推薦系統(tǒng)可預(yù)測未被用戶評定的項(xiàng)目的評級。矩陣分解用于計(jì)算用戶配置文件ui∈Rd，1≤j≤n，以及項(xiàng)目的配置文件vj∈Rd，1≤j≤m，d是潛在因素?cái)?shù)。可通過最小化已知評級集上正則均方誤差獲得

(1)

(2)

式中，γt>0是迭代t的學(xué)習(xí)率，U是用戶配置文件矩陣，其第i行是ui，V是項(xiàng)目輪廓矩陣，其第j行是vj。?uiφ(U，V)和?vjφ(U，V)分別是ui和vj的梯度，可計(jì)算為

(3)

式中，?uiφ(U，V)和?vjφ(U，V)特征是用戶配置文件ui應(yīng)該改變以減少均方誤差。學(xué)習(xí)率γt是一個(gè)常數(shù)，通常被設(shè)置為O(1/t)。

3 基于服務(wù)器隨機(jī)擾動的差分隱私矩陣分解

3.1 項(xiàng)目保護(hù)和評價(jià)

早期的研究中就將拉普拉斯機(jī)制應(yīng)用于梯度，以保護(hù)用戶的收視率。在他們的算法中，推薦者要求評分項(xiàng)目j的用戶以私有的方式提交他們的梯度。因此，聚合器可以了解用戶是否具有評級項(xiàng)目j。在本節(jié)中，我們提出了一個(gè)簡單的解決方案來克服現(xiàn)有工作中的問題。

如果用戶i對項(xiàng)目j進(jìn)行評價(jià)，則令yij為1，否則設(shè)定yij為0。對于(i，j)?M，令rij=0。

(4)

因此公式(3)中?vjφ(U，V)梯度形式可改寫為

(5)

(6)

(7)

(8)

服務(wù)器利用噪聲梯度的平均值更新項(xiàng)目配置文件vj，即

(9)

3.2 用戶隱私的服務(wù)器梯度擾動

為了減少V估計(jì)中的誤差，采用隨機(jī)化方法。特別地，該方法考慮這樣的場景，其中每個(gè)用戶都有一個(gè)要由服務(wù)器收集的多維元組，并且要求用戶在提交元組時(shí)隨機(jī)選擇一個(gè)維度，并在所選維度上提交其元組值的擾動版本，同時(shí)忽略所有其他維度。由服務(wù)器收集的擾動值可以用于估計(jì)每個(gè)維度上的所有用戶值的平均值，并且估計(jì)誤差顯著小于每個(gè)用戶在所有維度上提交其值的情況。算法1給出基于服務(wù)器隨機(jī)擾動的矩陣分解算法。

算法1：差分隱私梯度下降

輸入：預(yù)定義迭代數(shù)k與隱私參數(shù)ε；

輸出：項(xiàng)目配置矩陣V∈km×d；

1) 初始化U、V以及迭代計(jì)數(shù)器iter=0；

2)whileiter≤kdo

4)fori=1tondo

6) 在{1，2，…，m}中對j進(jìn)行采樣；

7) 在{1，2，…，d}中對l進(jìn)行采樣；

9)if(xi)j，l?[-1，1]，將(xi)j，l映射到[-1，1]區(qū)間；

13)endif

15)endfor

18)fori=1tondo

19)ui=ui-γt·{?ui+2λuui}；

20)endfor

21)endwhlie

22)returnV

3.3 通過降維實(shí)現(xiàn)精度提升

(10)

(11)

對于任意的a，b∈Rm，存在

(12)

(13)

對于給定的{ui∈d，1≤i≤n}，可得更新公式

Bt=Bt-1-γt·{?Bψ(Ut-1，Bt-1)+2λvBt-1}

(14)

(15)

(16)

算法1：基于降維的差分隱私梯度下降

輸入：正整數(shù)q，預(yù)定義迭代數(shù)k與隱私參數(shù)ε；

輸出：項(xiàng)目配置矩陣V∈Rm×d；

1) 初始化U、V以及迭代計(jì)數(shù)器iter=0；

2)whileiter≤kdo

4)fori=1tondo

8) 在{1，2，…，m}中對j進(jìn)行采樣；

9) 在{1，2，…，d}中對l進(jìn)行采樣；

10)if(xi)j，l?[-1，1]，將(xi)j，l映射到[-1，1]區(qū)間；

14)endif

16)endfor

18)fori=1tondo

20)endfor

21)endwhlie

22)returnV

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

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

本節(jié)實(shí)驗(yàn)選取的硬件配置為：英特爾i5-6400K 3.2GHz，內(nèi)存為8GHx，系統(tǒng)是win8旗艦版。為驗(yàn)證本文算法的有效性，這里選取文獻(xiàn)[14]的LAP和文獻(xiàn)[15]的NOE兩種算法作為對比算法，其中LAP算法采用的是拉普拉斯噪聲攝動算法。本文算去的實(shí)驗(yàn)對象是表1數(shù)據(jù)。

表1 選取的數(shù)據(jù)集

表1中的有關(guān)參數(shù)，參數(shù)U是實(shí)驗(yàn)對象中設(shè)定的用戶數(shù)量，參數(shù)E1是實(shí)驗(yàn)對象中用戶之間的關(guān)系數(shù)量，參數(shù)E2是實(shí)驗(yàn)對象中用戶和項(xiàng)目之間的關(guān)系數(shù)量，參數(shù)Item是實(shí)驗(yàn)對象中的項(xiàng)目的數(shù)量。

為了驗(yàn)證三種對比算法的差分隱私推薦結(jié)果可用性，選取的實(shí)驗(yàn)評價(jià)指標(biāo)是NDCG指標(biāo)，定義形式如下

(17)

式中，參數(shù)項(xiàng)NDCG(k，u)是實(shí)驗(yàn)對象中用戶u對差分隱私項(xiàng)目k進(jìn)行可用性推薦的評估指標(biāo)，定義形式為

(18)

式中，參數(shù)項(xiàng)index(Ii)是差分隱私項(xiàng)目Ii在(k)數(shù)據(jù)集中的位置索引。同時(shí)，為了評估Flixster數(shù)據(jù)集和Last.fm兩個(gè)數(shù)據(jù)集的差分隱私推薦相似性，這里選取近鄰關(guān)系指標(biāo)

(19)

(20)

式中，參數(shù)項(xiàng)Γ(u)是同數(shù)據(jù)集中用戶u的關(guān)系近鄰集。

4.2 可用性度量評價(jià)

采用表1中所示的兩種實(shí)驗(yàn)數(shù)據(jù)集，實(shí)驗(yàn)過程中通過設(shè)定不同的項(xiàng)目推薦數(shù)k以及隱私預(yù)算ε，來獲得不同大小的可用性推薦的評估指標(biāo)NDCG(k，u)，其中參數(shù)ε={0.1，0.4，0.7，1.0}，k={10，40，70，100}。參數(shù)實(shí)驗(yàn)如下：

1)隱私預(yù)算ε影響實(shí)驗(yàn)：本實(shí)驗(yàn)中設(shè)定數(shù)據(jù)集中差分隱私的推薦數(shù)量是k=40，實(shí)驗(yàn)過程中選擇改變隱私預(yù)算ε，分別采用Jaccard度量指標(biāo)對算法的有效性進(jìn)行驗(yàn)證。則對比算法在選取實(shí)驗(yàn)集上的NDCG評估指標(biāo)見圖2～3所示。

圖2 實(shí)驗(yàn)集(Last.fm)上的NDCG指標(biāo)變化情況

圖3 實(shí)驗(yàn)集(Flixster)上的NDCG指標(biāo)變化情況

根據(jù)圖2～圖3實(shí)驗(yàn)結(jié)果可知，當(dāng)實(shí)驗(yàn)參數(shù)隱私預(yù)算ε在區(qū)間[0.1，1.0]變化時(shí)，指標(biāo)NDCG的取值從大到小的趨勢進(jìn)行變化，主要原因是算法中因?yàn)殡[私預(yù)算ε取值越大，其在算法實(shí)現(xiàn)過程中所需要的拉普拉斯噪音的取值越小，但是本文算法因?yàn)椴捎昧擞脩綦[私的服務(wù)器梯度擾動，因此其所得到的NDCG指標(biāo)取值大約是文獻(xiàn)[14]算法的3倍，是文獻(xiàn)[15]的2倍。

2)參數(shù)m變化影響實(shí)驗(yàn)。本部分實(shí)驗(yàn)環(huán)節(jié)中，設(shè)定隱私預(yù)算為固定值，即ε=0.4，對于不同取值的差分隱私推薦數(shù)量m，選取Jaccard度量指標(biāo)對算法的有效性進(jìn)行驗(yàn)證。則對比算法在選取實(shí)驗(yàn)集上的NDCG評估指標(biāo)見圖4～5所示。

圖4 實(shí)驗(yàn)集(Last.fm)上的NDCG指標(biāo)變化情況

圖5 實(shí)驗(yàn)集(Flixster)上的NDCG指標(biāo)變化情況

根據(jù)圖4～5實(shí)驗(yàn)結(jié)果可知，當(dāng)差分隱私推薦項(xiàng)目個(gè)數(shù)由10個(gè)逐漸增加到100個(gè)時(shí)，集中對比算法的NDCG指標(biāo)均呈現(xiàn)出單調(diào)遞增的趨勢，當(dāng)時(shí)相對來講，本文算法在選取的實(shí)驗(yàn)數(shù)據(jù)集上的NDCG指標(biāo)均保持在90%以上，對比算法中文獻(xiàn)[14]算法可保持在80%以上，而文獻(xiàn)[15]算法僅維持在不到60%的水平，主要原因在于本文算法在針對實(shí)驗(yàn)數(shù)據(jù)集的項(xiàng)目用戶之間具有較低的噪音。

4.3 算法對比測試

這里仍然選取文獻(xiàn)[14～15]作為對比計(jì)算方法，對比指標(biāo)對象見表1。選取算法計(jì)算時(shí)間和隱私數(shù)據(jù)恢復(fù)精度作為對比指標(biāo)，驗(yàn)證算法的數(shù)據(jù)推薦質(zhì)量，實(shí)驗(yàn)結(jié)果見表2所示。

表2 算法對比測試

為了更加穩(wěn)定的評估算法的性能，這里選取實(shí)驗(yàn)運(yùn)行10次的平均計(jì)算指標(biāo)作為對比結(jié)果。根據(jù)表2所示實(shí)驗(yàn)結(jié)果可知，在計(jì)算時(shí)間實(shí)驗(yàn)對比指標(biāo)上，本文算法在Last.fm測試集上的差分隱私推薦時(shí)間是2.35s左右，而對比算法文獻(xiàn)[14]算法為5.69s，文獻(xiàn)[15]算法為52.6s，本文算法相對于文獻(xiàn)[14～15]兩種算法計(jì)算時(shí)間分別提升58.70%和69.91%。而在推薦精度指標(biāo)上，本文算法的推薦精度為98.76，比文獻(xiàn)[14～15]兩種算法高6.18%和10.25%，這表明本文算法在Last.fm測試集上的差分隱私推薦效率和推薦質(zhì)量均要優(yōu)于選取的文獻(xiàn)[14～15]兩種對比算法。同時(shí)，在Flixster測試集上本文算法也要優(yōu)于文獻(xiàn)[14～15]兩種對比算法，呈現(xiàn)出相似性能表現(xiàn)。

5 結(jié)束語

與現(xiàn)有的差分隱私矩陣因式分解相比，本文的工作創(chuàng)新如下：①可獲得更大程度的隱私權(quán)保證，所提矩陣分解算法可保證每個(gè)用戶的隱私，這是比現(xiàn)有算法更強(qiáng)的隱私保證。②極大地提高了推薦精度。LDP在用戶數(shù)據(jù)上的直接應(yīng)用引起一個(gè)大的攝動誤差，該誤差隨著項(xiàng)目的數(shù)量呈現(xiàn)線性增長。這里采用隨機(jī)投影進(jìn)行降維，并采用最新的隨機(jī)化算法來減少加入到梯度中的噪聲量。此外，我們還通過穩(wěn)定噪聲梯度來減少迭代造成的精度損失。③大大降低了通信成本。每個(gè)用戶在每次迭代中只向服務(wù)器發(fā)送一個(gè)比特，而現(xiàn)有的工作要求每個(gè)用戶發(fā)送其長度與由其評定的項(xiàng)目數(shù)量成比例的數(shù)據(jù)。同時(shí)，通過降維減少了從服務(wù)器到用戶的通信開銷。