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

楊 競，向 真，王小驥

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

1 引言

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

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

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

2 問題描述

2.1 算法框架

圖1 所提差分隱私推薦系統概述

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

2.2 矩陣分解

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

(1)

(2)

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

(3)

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

3 基于服務器隨機擾動的差分隱私矩陣分解

3.1 項目保護和評價

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

如果用戶i對項目j進行評價，則令yij為1，否則設定yij為0。對于(i，j)?M，令rij=0。

(4)

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

(5)

(6)

(7)

(8)

服務器利用噪聲梯度的平均值更新項目配置文件vj，即

(9)

3.2 用戶隱私的服務器梯度擾動

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

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

輸入：預定義迭代數k與隱私參數ε；

輸出：項目配置矩陣V∈km×d；

1) 初始化U、V以及迭代計數器iter=0；

2)whileiter≤kdo

4)fori=1tondo

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

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

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

13)endif

15)endfor

18)fori=1tondo

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

20)endfor

21)endwhlie

22)returnV

3.3 通過降維實現精度提升

(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：基于降維的差分隱私梯度下降

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

輸出：項目配置矩陣V∈Rm×d；

1) 初始化U、V以及迭代計數器iter=0；

2)whileiter≤kdo

4)fori=1tondo

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

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

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

14)endif

16)endfor

18)fori=1tondo

20)endfor

21)endwhlie

22)returnV

4 實驗分析

4.1 實驗設置

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

表1 選取的數據集

表1中的有關參數，參數U是實驗對象中設定的用戶數量，參數E1是實驗對象中用戶之間的關系數量，參數E2是實驗對象中用戶和項目之間的關系數量，參數Item是實驗對象中的項目的數量。

為了驗證三種對比算法的差分隱私推薦結果可用性，選取的實驗評價指標是NDCG指標，定義形式如下

(17)

式中，參數項NDCG(k，u)是實驗對象中用戶u對差分隱私項目k進行可用性推薦的評估指標，定義形式為

(18)

式中，參數項index(Ii)是差分隱私項目Ii在(k)數據集中的位置索引。同時，為了評估Flixster數據集和Last.fm兩個數據集的差分隱私推薦相似性，這里選取近鄰關系指標

(19)

(20)

式中，參數項Γ(u)是同數據集中用戶u的關系近鄰集。

4.2 可用性度量評價

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

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

圖2 實驗集(Last.fm)上的NDCG指標變化情況

圖3 實驗集(Flixster)上的NDCG指標變化情況

根據圖2～圖3實驗結果可知，當實驗參數隱私預算ε在區間[0.1，1.0]變化時，指標NDCG的取值從大到小的趨勢進行變化，主要原因是算法中因為隱私預算ε取值越大，其在算法實現過程中所需要的拉普拉斯噪音的取值越小，但是本文算法因為采用了用戶隱私的服務器梯度擾動，因此其所得到的NDCG指標取值大約是文獻[14]算法的3倍，是文獻[15]的2倍。

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

圖4 實驗集(Last.fm)上的NDCG指標變化情況

圖5 實驗集(Flixster)上的NDCG指標變化情況

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

4.3 算法對比測試

這里仍然選取文獻[14～15]作為對比計算方法，對比指標對象見表1。選取算法計算時間和隱私數據恢復精度作為對比指標，驗證算法的數據推薦質量，實驗結果見表2所示。

表2 算法對比測試

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

5 結束語

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