王健宗，肖京，朱星華，李澤遠

（平安科技(深圳)有限公司，廣東 深圳 518000）

大數(shù)據(jù)時代政府關于隱私保護的法律法規(guī)盛行，如《通用數(shù)據(jù)保護條例》(general data protection regulation)[1]，數(shù)據(jù)在政策的限制下分散在不同的載體/組織中，因此保護隱私的機器學習在學術界和工業(yè)界都備受重視。在實現(xiàn)隱私保護機器學習的各種技術中，聯(lián)邦學習(federated learning，F(xiàn)L)[2]受到高度重視，它最初由Google提出，目標是基于分布在每個用戶手機上的數(shù)據(jù)學習一個統(tǒng)一的模型，用戶的原始信息無需轉移到中央服務器，從而實現(xiàn)了隱私保護。經(jīng)證明，F(xiàn)L與在原始數(shù)據(jù)上學習到的傳統(tǒng)模型相比，預測能力幾乎相同[3]。

隨著互聯(lián)網(wǎng)和電子商務的迅猛發(fā)展，推薦系統(tǒng)成為企業(yè)提高市場競爭力的重要工具。其中，協(xié)同過濾 (collaborative filtering，CF) 是最著名的一種推薦算法[4]，有2種實現(xiàn)方法：一種是基于近鄰[5]，另一種是基于矩陣分解[6]。其中基于近鄰的協(xié)同過濾又分為基于用戶的協(xié)同過濾和基于物品的協(xié)同過濾，分別依據(jù)用戶消費行為上的相似性或消費產(chǎn)品間的相似性來實現(xiàn)個性化的產(chǎn)品推薦。一般來說，客戶的歷史信息越詳細，推薦結果越準確。

由于沒有足夠多的客戶數(shù)據(jù)，許多中小型公司無法獲得滿意的推薦模型。為了解決這個問題，通常采取的解決方案有：1) 請求另一家擁有龐大客戶數(shù)據(jù)庫的公司幫助；2) 與其他多家擁有相對較小客戶數(shù)據(jù)庫公司合作，共同創(chuàng)建一個大的數(shù)據(jù)庫[7]。公司間無法簡單地共享或允許彼此完全訪問其數(shù)據(jù)庫，因為這可能會造成客戶隱私數(shù)據(jù)外泄。文獻[8]表明，70%～89.5%的互聯(lián)網(wǎng)用戶認為個人隱私信息面臨泄露風險。鑒于聯(lián)邦學習處理數(shù)據(jù)孤島和隱私保護問題的有效性和實用性，與聯(lián)邦學習相結合的協(xié)同過濾推薦算法成為目前推薦系統(tǒng)領域的一個研究熱點[9]。

冷啟動是協(xié)同過濾算法應用中經(jīng)常會遇到的問題，分為新用戶冷啟動、新項目冷啟動、系統(tǒng)冷啟動等。當系統(tǒng)中有新用戶加入時，由于該用戶在系統(tǒng)中沒有歷史評分數(shù)據(jù)，不能根據(jù)傳統(tǒng)算法計算用戶間的相似度，也就無法為其進行推薦，這就是協(xié)同過濾算法的新用戶冷啟動問題[10]。在現(xiàn)有的與聯(lián)邦學習相結合的協(xié)同過濾推薦算法的研究中，對用戶冷啟動問題的研究比較少，因此對聯(lián)邦學習協(xié)同過濾算法中用戶冷啟動問題的研究具有迫切的意義。

1 相關工作

本文的研究是3個研究主題的交叉點：聯(lián)邦學習、協(xié)同過濾推薦算法中的隱私保護問題和冷啟動問題。

1.1 聯(lián)邦學習

隨著信息革命的發(fā)展，海量的數(shù)據(jù)在不斷產(chǎn)生，如何合理有效地利用這些數(shù)據(jù)成為一個熱點方向。由于隱私政策的保護，很多數(shù)據(jù)不能被輕易地獲取，數(shù)據(jù)間相互隔離，形成了一個個數(shù)據(jù)孤島。如何建立數(shù)據(jù)孤島間溝通的橋梁，打破數(shù)據(jù)之間的界限，成為一個熱點方向。谷歌研究院提出了聯(lián)邦學習的概念，即通過只在各節(jié)點間傳遞模型參數(shù)，而不分享模型間數(shù)據(jù)的方式訓練一個共享的數(shù)據(jù)模型。聯(lián)邦學習成為解決數(shù)據(jù)隱私保護的一個有利工具。聯(lián)邦學習旨在滿足數(shù)據(jù)隱私保護、數(shù)據(jù)安全和政府法規(guī)的前提下，進行數(shù)據(jù)的使用和建模。根據(jù)數(shù)據(jù)劃分的方式，聯(lián)邦學習可分為縱向聯(lián)邦學習以及橫向聯(lián)邦學習[11]。迄今為止，有許多研究致力于聯(lián)邦學習算法，以支持更多的機器學習模型，包括深度神經(jīng)網(wǎng)絡（deep neural network，DNN）[12]、梯度提升樹（gradient boosting decision tree，GBDT）[13]、邏輯回歸、支持向量機[14]。

本文主要關注在縱向聯(lián)邦的場景下實現(xiàn)推薦系統(tǒng)的冷啟動問題。

1.2 推薦系統(tǒng)的隱私保護

推薦系統(tǒng)(recommendation systems, RS)收集和學習用戶對一系列項目的偏好信息，并預測用戶對新物品或項目的興趣程度，產(chǎn)生推薦列表。用戶的偏好信息可以是顯性的(基本上是通過收集用戶的評分)或隱性的(基本上是通過監(jiān)測用戶的交互記錄，如訪問過的網(wǎng)頁、購買過的軟件、閱讀過的書籍和刷過的短視頻等隱性推斷關于某物品的興趣程度)[15-17]。根據(jù)輸入數(shù)據(jù)的類型，推薦模型主要分為協(xié)同過濾式推薦系統(tǒng)[17]、基于內容的推薦系統(tǒng)[18]和基于知識的推薦系統(tǒng)[19]。在實踐中，推薦系統(tǒng)已經(jīng)被廣泛地應用于各種應用中，如電子商務[20-21]、娛樂[22-23]、新聞[24-25]和社交平臺[26-27]。

由于個人對物品的偏好往往涉及到個人的隱私信息，長期以來，推薦系統(tǒng)中如何保護隱私信息受到許多學者關注。許多研究使用差分隱私的方法保護用戶評價記錄的隱私性[1]。聯(lián)邦學習通過數(shù)據(jù)不出本地、僅傳輸用戶梯度的方式，進一步保障用戶的隱私不被竊取。聯(lián)邦推薦系統(tǒng)可以與差分隱私、多方安全計算等技術結合，靈活有效地在不泄露用戶隱私的前提下實現(xiàn)推薦系統(tǒng)性能的提升。

協(xié)同過濾是推薦系統(tǒng)中最常用、應用范圍最廣的算法之一，也是本文討論的主要算法。針對協(xié)同過濾算法中的隱私保護問題，有多種方法可以解決。如文獻[15]針對集中式數(shù)據(jù)，采用隨機擾亂技術，提出了一個保護隱私的協(xié)同過濾推薦方案；文獻[28]在差分隱私框架中提出了協(xié)同過濾算法；文獻[29]使用同態(tài)加密計算協(xié)同過濾過程的中間值，中間值解密后通過奇異值分解和因子分析產(chǎn)生推薦建議；文獻[30]提出了一種基于同態(tài)密碼的協(xié)同過濾算法；文獻[31]提出了一種新的興趣點推薦隱私保護框,在聯(lián)邦學習中采用安全聚合的策略來學習特征交互模型；文獻[32]提出了一種新的分布式矩陣分解框架用于興趣點推薦，該框架具有可擴展性，能夠保護用戶隱私。

1.3 協(xié)同過濾及其冷啟動問題

協(xié)同過濾是一種基于矩陣分解的推薦算法。在已知用戶的歷史評分矩陣R的前提下，使用較低維的用戶特征矩陣U={u1u2···uN} 和物品特征矩陣V={v1v2···vM} 的乘積UTV擬合評分矩陣。在進行推薦時，通過用戶特征和物品特征向量的內積計算出用戶對某一物品的預測評分，即用戶可能對該物品感興趣的程度。其中，用戶特征和物品特征都是通過對歷史評分的學習訓練得到的，當系統(tǒng)中添加新的用戶和新的物品時，它們的特征向量是未知的，即產(chǎn)生了初始推薦的問題，相關的算法稱為協(xié)同過濾的冷啟動。

針對協(xié)同過濾算法中冷啟動問題，文獻[33]提出了一種基于協(xié)同矩陣分解的用戶冷啟動推薦算法，來處理用戶冷啟動問題。文獻[34]將計算相似性的不對稱方法與矩陣分解和基于典型性的協(xié)同過濾(tyco)相結合，實現(xiàn)了一種改進的電影推薦算法。然而目前對冷啟動問題的研究一般基于單方數(shù)據(jù)庫，具有一定的局限性，有少數(shù)學者對多方參與的協(xié)同過濾冷啟動問題進行了探索。文獻[35]引入聯(lián)邦多視圖矩陣分解方法，將聯(lián)邦學習框架擴展到具有多個數(shù)據(jù)源的矩陣分解。經(jīng)證明，該方法對于多數(shù)據(jù)源冷啟動推薦有較好的預測效果。

本文提出的方法聯(lián)合多方數(shù)據(jù)，打通了數(shù)據(jù)孤島，在進行隱私保護的同時，解決了協(xié)同過濾中的冷啟動問題。

2 縱向聯(lián)邦協(xié)同過濾中的冷啟動定義

在本節(jié)中，對縱向聯(lián)邦協(xié)同過濾中的冷啟動問題給出正式的公式定義。

本文考慮采用基于縱向聯(lián)邦學習的協(xié)同過濾方法。其中，聯(lián)邦協(xié)同過濾可以由多方進行聯(lián)合訓練，為了方便起見，本文均以兩方為例。假定聯(lián)邦參與公司A、B都是半誠實的，這意味著他們會遵守協(xié)議，但也會盡可能地從執(zhí)行中推斷信息。因此在本文中，由于評分屬于隱私信息，A、B雙方均不能直接交換評分。在此假定A需要解決新用戶冷啟動問題，與B聯(lián)合進行基于物品的協(xié)同過濾訓練，最終A、B均能獲得兩方物品的相似度矩陣，B通過相似度矩陣與物品評分對A物品進行評分預測，將預測值排序并返回A推薦物品id。最終，在不泄露評分信息的情況下，A獲得了針對新用戶的物品推薦順序。

如圖1，機構A為了解決本地新用戶的冷啟動問題，與機構B進行合作。假設A與B是縱向聯(lián)合，A與B共有用戶n個，已經(jīng)進行了對齊處理；共有m個物品，其中A有m′個物品，B有m?m′m?m′個物品。令評分為[vmin,vmax][vmin,vmax]中的一個整數(shù)，對于物品i(1≤i≤m)，評分向量為Vi=(v1i,v2i,···,vni) ， 其中vui(1≤u≤n) 代表用戶u對物品i的評分。假設n個用戶中，A有n′個新用戶，但對于B不為新用戶。因此A擁有評分矩陣Vui(n′+1≤u≤n,1≤i≤m′)，相應地，B機構擁有評分矩陣Vui(1≤u≤n,m′+1≤i≤m)。該研究問題是設計一個聯(lián)邦學習縱向協(xié)同過濾算法，讓A能夠在不泄露雙方信息的前提下，通過B的信息完成對新用戶u(1≤u≤n′) 的推薦。

圖1 帶有冷啟動用戶的縱向劃分Fig. 1 Vertical partition with cold start users.

3 聯(lián)邦推薦冷啟動

3.1 協(xié)同過濾冷啟動算法

根據(jù)文獻[36]提出的框架，協(xié)同過濾主要分為3個步驟：

1)物品相似度計算：根據(jù)評分信息，計算物品i與其他物品相似度；

2)鄰近樣本選擇：這一步主要是為了提高推薦算法的效率和精確度；

3)預測推薦：對用戶u的評分預測，并將排序最高的前N個推薦給用戶。

1)計算物品相似度：為了計算A方物品與B方物品的相似度，采用皮爾森相關系數(shù)進行計算，令i為A方物品，j為B方物品，則皮爾森系數(shù)為

式中：vu,i表示用戶u給物品i的評級simij代表物品i與j相似度，范圍在[?1, 1]。為了使A、B兩方能夠聯(lián)合計算，將其分為cui、cuj2個部分：

其中：

顯然，計算cui(cuj)只需要的信息，因此A、B兩方均可在本地計算cui、cuj。令Ci=計算simij即可轉為計算Ci和Cj的內積。

2)選擇近鄰：由于本文針對的是新用戶的冷啟動推薦問題，將所有物品都作為鄰近樣本，允許使用不相似的物品來進行計算，增加推薦覆蓋率。

3)預測推薦：為了對機構A的新用戶進行推薦，采用B機構里的評分信息進行預測：

式中： p redui代表用戶u對物品i的預測評分，對于A機構的新用戶，有 1 ≤u≤n′,1≤i≤m′。其中預測值計算可在B機構進行，且B機構對預測值結果排序，將排在前N個物品發(fā)送給A機構，完成對新用戶的推薦。

3.2 安全內積

文獻[37]提出了一種基于第3方的一種安全內積計算協(xié)議。

為了計算Ci與Cj的內積 ＜Ci,Cj>，加入一個第3方，在不泄露各方數(shù)據(jù)下進行數(shù)據(jù)的匯總，如算法1所示。

算法1安全內積算法＜Ci,Cj>

多方A、B以及第3方T；

輸入A:Ci； B:Cj；

輸出A:rA； B:rB，且有rA+rB=＜Ci,Cj>。

1) T方隨機產(chǎn)生2個隨機向量x,y，以及一個隨機數(shù)r，且令z=＜x,y>?r，將 (x,r) 傳給A， (y,z) 傳給B；

2) A將Ci+x傳給B；

3) B將Cj?y傳給A；

4) A計算可公開信息rA=＜Ci,Cj?y>?r；

5) B計算可公開信息rB=＜Ci+x,Cj>?z。

由于rA及rB里面各包含2個隨機項，對Ci及Cj的隱私信息均進行了保護，因此不會泄露各方的隱私數(shù)據(jù)，最終A, B雙方均可利用公開的rA、rB進行內積 ＜Ci,Cj> 的計算，達到了隱私保護的作用，流程如圖2所示。

圖2 安全內積流程Fig. 2 Overview of secure inner product.

3.3 聯(lián)邦協(xié)同過濾冷啟動算法

為了使A、B雙方能夠在數(shù)據(jù)不泄露的情況下進行新用戶的推薦，將協(xié)同過濾與安全內積相結合，構建聯(lián)邦學習協(xié)同過濾冷啟動解決算法?？蚣軆热萑鐖D3所示，由受信任的第3方T以及A、B兩方構成。如前文所述，假設A、B兩方都是半誠實的，同時第3方T也不與A、B兩方勾結。

圖3 聯(lián)邦協(xié)同過濾冷啟動框架Fig. 3 Overview of federated learning system for cold start in collaborative filtering

聯(lián)邦協(xié)同過濾冷啟動算法的主要步驟包括：

1) 基于安全內積算法，A、B端根據(jù)式(1)、(2)在本地分別計算Ci(1≤i≤m′)，Cj(m′+1≤i≤m)；

2) 第3方T隨機產(chǎn)生2個隨機向量x、y以及一個隨機數(shù)r，且令z=＜x,y>?r，將 (x,r) 傳給A，(y,z)傳給B；

3) A將Ci+x(1≤i≤m′) 傳給B；B將Cj?y(m′+1≤j≤m)傳給A；

4) A分別計算rA(i,j)=＜Ci,Cj?y>?r(1≤i≤m′,m′+1≤j≤m) 傳輸給T；同理B相應計算rB(i,j) 傳輸給T；

5) T計算 simij=rA(i,j)+rB(i,j)，并構建相應的相似矩陣Wij(由 s imi,j元素構成)分發(fā)給A、B雙方；

6) B根據(jù)Wij相似矩陣以及本地用戶u∈[1,n′] 對物品j∈[m′+1,m] 的評分信息，由式(3)對 p redui,u∈[1,n′],i∈[1,m′] 進行預測，并對預測結果進行排序，最終將預測值最高的前N個物品ID發(fā)送給A，完成用戶冷啟動推薦過程。

由圖3中可看出，每一方并不能直接收到對方的原始評分，且由于增加了隨機項，不能從中間結果進行對原數(shù)據(jù)的反推，因此達到了隱私保護的作用。

4 實驗與結果

4.1 度量標準

本文采用Top-N推薦，采用2種不同的評估方法進行模型評價。

1) 閾值擊中評價

推薦評估指標采用精確率Precision、查全率Recall以及F1?score。

式中：Ru是B方基于相似矩陣以及用戶u的評分信息進行對A方的推薦列表；Tu是新用戶u對于A中物品的非空且評分大于閾值c的用戶行為列表。

2) 留一法 (leave-one-out)評價

對于測試集里的每個用戶，都保留其最新一條評分信息進行驗證。由于在評價過程中對每個用戶都進行排序比較耗時，所以本位采用了常用的策略[35-36]，即對于每個用戶隨機抽取30個沒有評分的物品，并且對其評分預測排序。在此設定推薦個數(shù)為10，將該30個物品與最新評分物品的預測評分進行排序，若最新評分物品排在前10則視為擊中。評估指標采用命中率 (hit ratio,HR)[37]以及歸一化折現(xiàn)累計增益(normalized discounted cumulative gain，NDCG)來判斷排序列表的性能。HR直觀地衡量測試物品是否在前10，而NDCG根據(jù)擊中的位置進行評估。

4.2 數(shù)據(jù)集

本文實驗采用GroupLens提供的網(wǎng)絡開源數(shù)據(jù)集MovieLens 1M為例，整個數(shù)據(jù)集包括了6 040個電影用戶對3 706部電影的1 000 209條評分，評分范圍為1～5。由于本文針對基于物品協(xié)同過濾的冷啟動問題，因此只取數(shù)據(jù)集中的用戶?電影評分集作為實驗數(shù)據(jù)。

該評分數(shù)據(jù)集均對用戶及電影進行了ID處理，因此在進行計算過程中用戶ID及電影ID不視為隱私數(shù)據(jù)。同時有較多數(shù)的電影只被極少數(shù)的用戶進行評分，該部分電影對新用戶的推薦起較少的作用，因此將用戶評分率低于10%的電影進行刪除，處理后的用戶?電影數(shù)據(jù)維度為6 040 498。

為了衡量冷啟動推薦的效果，將用戶分割為2部分，新老用戶比例為2：8，在新用戶與老用戶中的數(shù)據(jù)進行了縱向分割，隨機分成A、 B 2個部分，并且通過改變A、B的分配比例P∈(0.1,0.9)進行多組實驗。評估時，將A中已有的新用戶評分行為與相應的推薦作比較。

4.3 驗證

第1個實驗是通過變化A、 B間分配比例P的取值來觀察當聯(lián)合多方數(shù)據(jù)訓練模型時，取何值效果會比較理想。第2個實驗中，將該算法和一個基于物品平均評分的無偏差推薦基線算法進行評估指標的比較。

1) 不同B機構比例的實驗結果

令P代表B數(shù)據(jù)量在總數(shù)據(jù)量中的占比，當P越大時，代表B所擁有的信息越多。由于在實際場景中，兩方機構所含有的物品特征不全是一致的，A可能會與規(guī)模較大的機構合作，也可能會與規(guī)模較小的機構合作。

從表1中可以看出當B的占比越大，無論閾值c取3或4(當用戶評分＞=閾值時，才算擊中)，對于A機構的冷啟動推薦效果都更好，這與直觀相符合，當外部提供的信息越多，對自身的幫助會越大。對于HR及NDCG，也可以看到隨著B的占比上升，總體趨勢也為上升。閾值c為4時召回率均大于閾值為3，這說明本文的方法對于高評分物品推薦的效果較好。

表1 取不同P的實驗結果Table 1 Results change population distribution

2) 基準算法與本文算法的結果對比

為驗證方法可行性，采用一個基準算法來作對比。采用的基準算法為只取A方的數(shù)據(jù)對各個物品評分取平均，并將其平均分排序最高的前N個對新用戶進行無偏差的推薦。本文以A、B機構均占50%，即P=0.5 為例，實驗結果如表2、3。

表2 閾值擊中評價Table 2 Hit rate with different threshold

從表2結果可以發(fā)現(xiàn)，當閾值取3以及取4時，本文算法均比基準算法有一定的提高。當閾值取3，可以看到無論是精確度還是查全率都有一定的提升，其中F1值較基準算法提升了約7%。當閾值取4時，F(xiàn)1值較基準算法提升了約6%。

表3 留一法評價Table 3 Leave-one-out evaluation

從表3中可以看到留一法的評估結果，相較基準算法，本文算法的擊中率(HR)有較大的提升，約12.5%，但NDCG的提升效果較小，約9.6%。說明該算法對于推薦的擊中效果有較大的提升，而對于擊中的位置提升的效果較小。

5 結束語

本文首先介紹了基于物品的協(xié)同過濾算法以及安全內積算法，并針對新用戶的冷啟動問題，提出了一種基于聯(lián)邦學習的協(xié)同過濾冷啟動解決算法。該算法針對某一方的新用戶冷啟動問題，通過與其他方數(shù)據(jù)進行聯(lián)合，在不泄露信息的情況下進行相似矩陣的計算，最終解決冷啟動問題。實驗結果表明，本文提出的聯(lián)邦學習冷啟動方法在準確度均有一定的提升，同時實驗證明當聯(lián)合規(guī)模較大的數(shù)據(jù)進行聯(lián)合訓練時，對于本地的推薦效果會有較大的提升。該方法不僅提供了一種解決協(xié)同過濾冷啟動的方法，也在運用聯(lián)邦學習解決冷啟動的方向帶來了一定的啟發(fā)。