蘇 洋,張 浩,劉俊彤

(皖南醫(yī)學(xué)院 醫(yī)學(xué)信息學(xué)院,安徽 蕪湖 241002)

隨著互聯(lián)網(wǎng)的快速發(fā)展,用戶難以從海量信息中快速搜索到所需的信息,信息過載問題日益嚴(yán)重,個(gè)性化推薦系統(tǒng)[1]是一種有效的解決方法,其中協(xié)同過濾是目前使用最廣泛的一類推薦算法。通過對(duì)用戶過往數(shù)據(jù)進(jìn)行分析,得到用戶的偏好,從而對(duì)其完成推薦,具有不需要領(lǐng)域知識(shí)、工程上實(shí)現(xiàn)簡(jiǎn)單等優(yōu)點(diǎn)[2]。

推薦系統(tǒng)性能的優(yōu)劣很大程度上取決于訓(xùn)練數(shù)據(jù)質(zhì)量的高低,當(dāng)數(shù)據(jù)量較少,數(shù)據(jù)稀疏性較大時(shí),推薦系統(tǒng)的性能較差。同時(shí)現(xiàn)實(shí)情況下數(shù)據(jù)往往分屬于不同的數(shù)據(jù)持有者,數(shù)據(jù)孤島[3]現(xiàn)象十分嚴(yán)重。此外,這些數(shù)據(jù)包含了大量的用戶隱私,近年來國內(nèi)外紛紛在法律法規(guī)層面上進(jìn)行保護(hù),對(duì)于用戶數(shù)據(jù)隱私的保護(hù)日益規(guī)范[4]。因此,如何在保護(hù)數(shù)據(jù)隱私的前提下,聯(lián)合多方共同進(jìn)行推薦模型訓(xùn)練是推薦系統(tǒng)的一個(gè)研究熱點(diǎn)。聯(lián)邦推薦算法是其中的一個(gè)重要研究方向。

目前關(guān)于聯(lián)邦推薦系統(tǒng)的研究主要集中在數(shù)據(jù)隱私安全、模型聚合方式和通信方式等方面,對(duì)于博弈論在其中的研究相對(duì)較少。然而在聯(lián)合模型訓(xùn)練中,推薦的效果不僅取決于自己提供的數(shù)據(jù),很大程度上也依賴于其他客戶端提供的數(shù)據(jù),這就導(dǎo)致各客戶端在聯(lián)合訓(xùn)練中存在博弈,即期望己方提供較少的數(shù)據(jù),期望對(duì)方提供更多的數(shù)據(jù)。本文采用博弈論[15]的方法對(duì)聯(lián)邦推薦系統(tǒng)中的各客戶端之間的行為進(jìn)行分析討論。

文獻(xiàn)[16]使用博弈論對(duì)傳統(tǒng)協(xié)同過濾推薦系統(tǒng)中各用戶的評(píng)分行為進(jìn)行了分析。在該文中,用戶對(duì)體驗(yàn)過的項(xiàng)目進(jìn)行評(píng)分會(huì)產(chǎn)生相應(yīng)的代價(jià),因此用戶不會(huì)對(duì)所有項(xiàng)目都進(jìn)行評(píng)分并將數(shù)據(jù)提供給服務(wù)器,故將評(píng)分?jǐn)?shù)據(jù)提供給服務(wù)器這一行為視為用戶的策略。此外,該文認(rèn)為每個(gè)用戶對(duì)于推薦效果均有一個(gè)心理預(yù)期,當(dāng)未達(dá)到預(yù)期時(shí),傾向于提供更多的數(shù)據(jù)以使推薦效果進(jìn)一步提升;當(dāng)達(dá)到預(yù)期時(shí),傾向于不再提供更多的數(shù)據(jù)。在此基礎(chǔ)上,該文提出了一種基于用戶數(shù)據(jù)迭代更新策略的算法。

本文針對(duì)數(shù)據(jù)分布于各客戶端的情況,提出了一種基于均衡學(xué)習(xí)的聯(lián)邦推薦算法(federated recommendation algorithm based on equilibrium learning,FRER)。將各客戶端進(jìn)行本地模型訓(xùn)練時(shí)提供的數(shù)據(jù)量作為用戶策略,由于在聯(lián)邦學(xué)習(xí)訓(xùn)練過程中,各客戶端無法得知其他客戶端采取的行動(dòng),將各客戶端之間的交互建模為不完全信息博弈。同時(shí),本文假定各客戶端對(duì)于推薦效果有一個(gè)預(yù)期,當(dāng)最終的推薦效果高于預(yù)期時(shí),達(dá)到滿足狀態(tài)。因此，本文采用滿足均衡(satisfaction equilibrium)的概念來分析該博弈的均衡。為使該博弈能夠達(dá)到均衡狀態(tài),本文采用均衡學(xué)習(xí)方式對(duì)策略進(jìn)行調(diào)整,在每一輪訓(xùn)練中,各客戶端根據(jù)上一輪訓(xùn)練時(shí)是否達(dá)到滿足狀態(tài),動(dòng)態(tài)調(diào)整進(jìn)行本地模型訓(xùn)練時(shí)的數(shù)據(jù)量。為驗(yàn)證所提算法的有效性和可行性,本文進(jìn)行了算法收斂性的理論分析,并通過一系列仿真實(shí)驗(yàn)對(duì)理論分析的結(jié)果進(jìn)行了驗(yàn)證。

1 博弈模型

1.1 場(chǎng)景描述

將評(píng)分矩陣Rl×m分解成Pl×k和Qk×m,其中:Pl×k為用戶隱向量矩陣;Qk×m為項(xiàng)目隱向量矩陣;k為隱向量維數(shù)。對(duì)于某一個(gè)用戶評(píng)分rui,可以用(1)式進(jìn)行評(píng)分預(yù)測(cè)。

(1)

(2)

bu←bu+γ(eui-λbu)

(3)

bi←bi+γ(eui-λbi)

(4)

pu←pu+γ(euiqi-λpu)

(5)

qi←qi+γ(euipu-λqi)

(6)

(7)

在上述計(jì)算中,各客戶端利用數(shù)據(jù)在本地進(jìn)行模型訓(xùn)練,計(jì)算出用戶隱向量和用戶偏好偏置,將項(xiàng)目隱向量和項(xiàng)目偏置上傳至服務(wù)端進(jìn)行模型參數(shù)聚合,從而在保證數(shù)據(jù)隱私的前提下,完成聯(lián)合建模。本文規(guī)定,每輪迭代之后,各客戶端會(huì)計(jì)算當(dāng)前模型是否達(dá)到期望的推薦效果,即是否達(dá)到滿足,并根據(jù)計(jì)算結(jié)果,選擇下一輪迭代時(shí)提供的數(shù)據(jù)量。

1.2 滿足均衡博弈

(8)

(9)

本文用gi(M)表示上一時(shí)刻訓(xùn)練結(jié)束后客戶端ci的模型推薦效果,M表示本地模型,當(dāng)gi(M)≥Γi時(shí),表示客戶端ci達(dá)到滿足狀態(tài)。然而gi(M)只是從單個(gè)客戶端方面對(duì)模型性能進(jìn)行了描述,不能很好體現(xiàn)模型性能與其他客戶端之間的聯(lián)系,因此通過引入數(shù)據(jù)完整度θ和映射函數(shù)f,可將gi(M)改寫為f(θi,θ-i;pi)。f(θi,θ-i;pi)表示以θi和θ-i作為輸入,以pi為參數(shù),可以更直接地表示客戶端ci的推薦效果不僅與自己提供的數(shù)據(jù)有關(guān),也和其他客戶端提供的數(shù)據(jù)密切相關(guān),同時(shí)自身提供的數(shù)據(jù)量也會(huì)影響其他客戶端提供的數(shù)據(jù)量。為此,定義函數(shù)ψi(θ-i)為客戶端ci在θ-i狀態(tài)下選擇θi的關(guān)系?；诖?本文用(11)式定義所建立的博弈模型。

ψi(θ-i)={θi∈Αi:fi(θi,θ-i)≥Γi}

(10)

G=〈C,{Αi}i∈C,{ψi}i∈C〉

(11)

2 基于均衡學(xué)習(xí)的聯(lián)邦推薦算法

在上文建立的博弈模型中,直接分析該博弈的均衡是很困難的。一種可行的方法是設(shè)計(jì)某種行為規(guī)則,讓客戶端在迭代交互的過程中依據(jù)該規(guī)則不斷調(diào)整自己的策略,最終學(xué)習(xí)到一種均衡策略。

結(jié)合聯(lián)邦推薦系統(tǒng)的工作原理,本文設(shè)計(jì)了一種學(xué)習(xí)算法,該算法允許客戶端以逐漸增加訓(xùn)練數(shù)據(jù)的方式尋找均衡策略。本節(jié)首先介紹算法的基本流程,然后對(duì)算法的收斂性進(jìn)行分析。

2.1 均衡學(xué)習(xí)算法

在無線通信網(wǎng)絡(luò)中,文獻(xiàn)[18]針對(duì)服務(wù)質(zhì)量(quality of service,QoS)問題,設(shè)計(jì)了一種基于滿足均衡算法的迭代方法。本文將這種方式應(yīng)用于聯(lián)邦推薦系統(tǒng)之中。

在聯(lián)邦推薦系統(tǒng)中,客戶端與服務(wù)器端的交互是長(zhǎng)期的,客戶端不斷向服務(wù)器端提供本地模型的參數(shù),服務(wù)器端則進(jìn)行模型參數(shù)聚合不斷調(diào)整全局模型并反饋給各客戶端。本文中,客戶端根據(jù)當(dāng)前推薦效果動(dòng)態(tài)調(diào)整本地模型訓(xùn)練的數(shù)據(jù),客戶端與服務(wù)器端的交互如圖1所示。

圖1 客戶端與服務(wù)器端交互示意圖

各客戶端在與服務(wù)器迭代交互的過程中按如下規(guī)則行動(dòng):

初始時(shí)刻(t=0),客戶端選擇部分本地?cái)?shù)據(jù)進(jìn)行模型訓(xùn)練,參與聯(lián)合建模。當(dāng)服務(wù)器端完成模型參數(shù)聚合,并回傳給各客戶端后,各客戶端計(jì)算當(dāng)前模型的推薦效果是否已達(dá)到預(yù)期,以變量vi(t-1)表示，即

(12)

(13)

(14)

當(dāng)所有客戶端完成數(shù)據(jù)選擇、本地模型訓(xùn)練后,服務(wù)器端對(duì)bi、qi進(jìn)行聚合并回傳給各客戶端進(jìn)行推薦性能測(cè)試,之后再進(jìn)入下一輪迭代。若經(jīng)過ns(ns>0)次迭代之后,對(duì)于期望的推薦效果Γ,所有客戶端都得到了滿足,則迭代終止,稱學(xué)習(xí)過程收斂于滿足均衡。將上述行為規(guī)則歸納為算法1,描述如下：

Input:Mclients, ServerS

S:initializebi,qi

while iteration conditions true do

for each clientm∈Mdo

ift=0 do

initialize train data

else

calculategi(M(t-1))&vi(t-1) using eq.12

update train data using eqs.8,13-14

endif

updatebu,bi,pu,qiusing eqs.3-6

transferbi,qitoS

endfor

S:updatebi,qiusing eq.7

endwhile

returnbu,bi,pu,qi

2.2 收斂性分析

隨著迭代的進(jìn)行,可以看出模型訓(xùn)練的數(shù)據(jù)量必然呈現(xiàn)出增長(zhǎng)的趨勢(shì),最終可以使所有客戶端均達(dá)到滿足狀態(tài)(即?ci∈C,ci=Ps),使算法完成收斂,3.2節(jié)給出了實(shí)驗(yàn)驗(yàn)證。

3 實(shí)驗(yàn)仿真

為了驗(yàn)證算法1的可行性,本文使用Movielens數(shù)據(jù)集進(jìn)行一系列仿真實(shí)驗(yàn)。本節(jié)首先對(duì)實(shí)驗(yàn)所用的數(shù)據(jù)集以及仿真參數(shù)的設(shè)置進(jìn)行說明,然后對(duì)不同參數(shù)設(shè)置下的仿真結(jié)果進(jìn)行分析, 最后對(duì)算法收斂條件進(jìn)行驗(yàn)證。

3.1 數(shù)據(jù)集和參數(shù)設(shè)置

Movielens數(shù)據(jù)集是推薦系統(tǒng)中的經(jīng)典數(shù)據(jù)集,由明尼蘇達(dá)大學(xué)搜集整理而成,本文選用了MovieLens 1M Dataset①http://files.grouplens.org/datasets/movielens/ml-1m.zip進(jìn)行實(shí)驗(yàn)仿真,包含了6 040名用戶對(duì)3 952部電影的1 000 209條匿名評(píng)價(jià)。本文刪除了評(píng)價(jià)數(shù)目低于100的用戶數(shù)據(jù),最終得到了2 945名用戶對(duì)3 670部電影的847 302條評(píng)分?jǐn)?shù)據(jù),數(shù)據(jù)稀疏度為7.84%。

本文采用橫向聯(lián)邦學(xué)習(xí)架構(gòu),假定這些數(shù)據(jù)分布于5個(gè)客戶端,故將數(shù)據(jù)從用戶角度隨機(jī)劃分成5份,并將其中90%的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù),10%的數(shù)據(jù)作為測(cè)試數(shù)據(jù),劃分后各客戶端擁有的數(shù)據(jù)量見表1所列。

使用平均絕對(duì)誤差(mean absolute error,MAE)作為模型性能評(píng)價(jià)指標(biāo)[19],用lMAE表示,即

(15)

表1 各客戶端數(shù)據(jù)分布

圖2 不同數(shù)據(jù)完整度下模型性能

(16)

(17)

各客戶端對(duì)于η可能有不同的期望,本文考慮以下3種情況:

(1) 各客戶端有較高期望。?ci∈C,η=0.85。

(2) 各客戶端期望一般。?ci∈C,η=0.5。

(3) 各客戶端期望不一。{c1,c2,η=0.85;c3,c4,c5,η=0.5。

不同情況下根據(jù)(17)式計(jì)算出具體的Γi，見表2所列。

表2 不同情況下各客戶端Γi值

客戶端對(duì)數(shù)據(jù)的重視程度α、獲取數(shù)據(jù)的代價(jià)φ、達(dá)到滿足狀態(tài)后維持?jǐn)?shù)據(jù)不變的概率σ都會(huì)直接影響算法1的性能,為盡可能地做出全面分析驗(yàn)證,本文對(duì)以上3個(gè)參數(shù)取值如下:α∈{1.5,2};φ∈{1,2};σ∈{0.9,1}。

除η、α、φ、σ外,本文還有以下參數(shù)設(shè)定:初始時(shí)刻,各客戶端參與訓(xùn)練的數(shù)據(jù)完整度θ=0.25;客戶端進(jìn)行本地模型訓(xùn)練時(shí),隱因子維度為100、學(xué)習(xí)率γ=0.005、正則化系數(shù)λ=0.02;當(dāng)客戶端達(dá)到滿足狀態(tài)后仍愿意提供更多數(shù)據(jù)的因子k=5。

3.2 仿真實(shí)驗(yàn)結(jié)果

為驗(yàn)證不同η下算法1的性能,本文設(shè)定α=2、φ=1、σ=0.9,實(shí)驗(yàn)結(jié)果見表3所列,可見3種情況下,算法均完成了收斂。

當(dāng)各客戶端均有較高期望時(shí),算法收斂較慢,同時(shí)需要提供更多的數(shù)據(jù)才能達(dá)到均衡狀態(tài)。以客戶端c1為例,當(dāng)η=0.85時(shí),其在第23輪訓(xùn)練結(jié)束時(shí)達(dá)到滿足狀態(tài),數(shù)據(jù)完整度為89.71%,而當(dāng)其將期望降低,η=0.5時(shí),在第13輪就達(dá)到了滿足狀態(tài),同時(shí)只提供了73.61%的數(shù)據(jù)。

當(dāng)各客戶端期望不一時(shí),相比于期望較低的客戶端,期望較高的客戶端的收斂速度明顯較慢,同時(shí)需要提供更多的數(shù)據(jù)。以客戶端c2和客戶端c3為對(duì)比,c2在第29輪達(dá)到滿足,c3在第4輪就已達(dá)到滿足。同時(shí)對(duì)于c2來說,mix環(huán)境下需要提供更多的數(shù)據(jù),當(dāng)η均為0.85時(shí),c2在mix環(huán)境下需要多提供5.77%的數(shù)據(jù),而c3在η均取0.5的情況下,數(shù)據(jù)量減少12.95%。這說明在混合環(huán)境下,對(duì)于期望較高的客戶端,為了達(dá)到預(yù)期效果,需要付出等多的代價(jià),而期望較低的客戶端在期望較高客戶端提供更多數(shù)據(jù)的情況下,只需提供較少數(shù)據(jù)就可以實(shí)現(xiàn)預(yù)期。

表3 不同η取值下算法仿真實(shí)驗(yàn)結(jié)果

σ也是影響算法性能的重要因素,客戶端c2在η=0.85、α=2、φ=1下,σ分別取0.9和1.0情況下的仿真實(shí)驗(yàn)結(jié)果如圖3所示,從圖3可以看出，2種情況下均達(dá)到了滿足狀態(tài)。與σ=1相比,σ=0.9時(shí),客戶端c2較快達(dá)到滿足狀態(tài),同時(shí),在滿足后,客戶端仍有可能提供更多的數(shù)據(jù),這會(huì)導(dǎo)致最終模型性能更好。當(dāng)σ=1時(shí),客戶端達(dá)到滿足時(shí),則不會(huì)再提供更多的數(shù)據(jù),當(dāng)所有客戶端均達(dá)到滿足狀態(tài)時(shí),即使隨著迭代的繼續(xù)進(jìn)行,整個(gè)模型性能仍將不再變化。此外,從圖3a可以看出,當(dāng)客戶端提供較少數(shù)據(jù)時(shí),其在后續(xù)迭代中傾向于提供更多數(shù)據(jù),然而當(dāng)數(shù)據(jù)量較大時(shí),則會(huì)傾向于維持現(xiàn)有數(shù)據(jù)量。

客戶端對(duì)數(shù)據(jù)的重視程度α、獲取數(shù)據(jù)的代價(jià)φ同樣也是影響算法的因素,本文也進(jìn)行了相實(shí)驗(yàn)驗(yàn)證?？蛻舳薱2在η=0.85、σ=0.9、φ=1下,α分別取1.5和1情況下的仿真實(shí)驗(yàn)結(jié)果如圖4所示。客戶端c2在η=0.85、σ=0.9、α=1下,φ分別取2和1情況下的仿真實(shí)驗(yàn)結(jié)果如圖5所示。從圖4、圖5可以看出，當(dāng)客戶端對(duì)數(shù)據(jù)越重視(即α、φ取值越大)的情況下,模型最終的性能要遜于對(duì)數(shù)據(jù)不那么重視的情況(即α、φ取值越小)。

圖3 客戶端c2在不同σ下模型性能

圖4 客戶端c2在不同α下模型性能

上述仿真實(shí)驗(yàn)測(cè)試了算法在不同情形下的運(yùn)行狀況,算法均在有限迭代次數(shù)內(nèi)完成了收斂,表明算法具有較好的可行性和適用性。

圖5 客戶端c2在不同φ下模型性能

4 結(jié) 論

聯(lián)邦推薦系統(tǒng)中,各客戶端相互協(xié)作共同訓(xùn)練推薦模型,然而由于數(shù)據(jù)獲取需要付出一定的代價(jià)且出于對(duì)自身數(shù)據(jù)安全的保護(hù),在能達(dá)到預(yù)期推薦效果的前提下,客戶端傾向于盡可能少地提供自身數(shù)據(jù),這使得在聯(lián)合模型訓(xùn)練過程中,各客戶端之間存在著博弈行為。本文利用博弈論相關(guān)概念對(duì)這一行為進(jìn)行了分析將其建模為不完全信息博弈,并使用滿足均衡解釋該博弈,提出了一種基于均衡學(xué)習(xí)的迭代算法FRER進(jìn)行求解。FRER允許各客戶端在訓(xùn)練過程中可以根據(jù)上一輪訓(xùn)練結(jié)束后的推薦模型效果來動(dòng)態(tài)地調(diào)整參與模型訓(xùn)練的數(shù)據(jù),通過理論分析和仿真實(shí)驗(yàn)均表明了算法的可行性。

后續(xù)工作可將激勵(lì)機(jī)制應(yīng)用到聯(lián)邦推薦系統(tǒng)中,刺激客戶端提供更多的數(shù)據(jù)以使模型的性能進(jìn)一步提升。將深度推薦學(xué)習(xí)算法應(yīng)用到FRER中也是未來的一個(gè)重要研究點(diǎn)。