針對新用戶冷啟動問題的改進Epsilon-greedy算法

王素琴,張 洋,蔣 浩,朱登明

(1.華北電力大學 控制與計算機工程學院,北京 102206; 2.中國科學院計算技術研究所,北京 100080)

0 概述

電子商務和社交媒體網(wǎng)站通常都面臨著嚴重的信息過載問題,推薦算法是解決該問題的有效手段之一。推薦算法一般根據(jù)用戶與網(wǎng)站的交互記錄來推測用戶可能喜歡的物品或者友人(以下統(tǒng)稱為物品)。當新用戶登錄到系統(tǒng)中時,由于他們沒有或者只有少量購買記錄和瀏覽記錄,推薦系統(tǒng)很難為他們進行有效的推薦,該問題被稱為新用戶冷啟動問題[1]。

快速發(fā)展中的電子商務網(wǎng)站或者社交媒體網(wǎng)站,吸引著大量新用戶的涌入,但由于存在新用戶冷啟動問題,不能為他們提供充分的有用信息,常常導致新用戶大量流失。

為解決上述問題,有研究者提出推薦算法。傳統(tǒng)的推薦算法有協(xié)同過濾算法[2-3]、基于內(nèi)容的推薦算法[4]以及混合推薦算法[5]等。協(xié)同過濾算法基于用戶的行為記錄,計算用戶之間的相似度或者物品之間的相似度并進行推薦。但由于新用戶沒有或者只有少量的行為記錄,導致協(xié)同過濾算法難以為其進行有效推薦。基于內(nèi)容的推薦算法首先提取用戶或者物品的特征,根據(jù)用戶或者物品之間特征的相似度來進行推薦。但新用戶可能沒有任何特征或者只有少量特征可以提取,因此,基于內(nèi)容的推薦算法也難以取得良好效果?；旌贤扑]算法是指將多種推薦算法有機地結合起來進行推薦,但實際應用結果表明,混合推薦算法也不能很好地解決新用戶冷啟動問題。

目前,有很多學者對新用戶冷啟動問題進行了深入研究,提出了若干解決該問題的算法。其中,最簡單的方法是隨機推薦,當新用戶進入系統(tǒng)時,推薦算法在物品庫中隨機選擇若干個物品推薦給用戶,但這種推薦結果往往無法令用戶滿意。文獻[6-7]提出基于偏好的推薦算法,在所有用戶中查找與當前用戶偏好相近的用戶,根據(jù)領域相關度、評價相似度等對相似用戶進行篩選,得到與當前用戶相似度最高的一批用戶,根據(jù)這批用戶的偏好信息為當前用戶進行推薦。該算法相對于協(xié)同過濾算法在冷啟動問題上有一定改進,但是仍不能解決完全沒有任何信息的新用戶冷啟動問題。文獻[8]提出對已有的用戶信息或物品信息進行分類,當新用戶或新物品進入系統(tǒng)時利用貝葉斯分類方法將其歸類到相應的用戶類或物品類。這種方法在系統(tǒng)已經(jīng)獲取用戶的基礎信息或者少量的用戶交互信息時能給出較好的推薦,但是當一個完全沒有任何信息的新用戶登錄到系統(tǒng)時,這類方法不能取得較好效果。文獻[9]基于用戶的人口統(tǒng)計學信息為新用戶進行推薦,但其在未獲取新用戶的人口統(tǒng)計學信息時無法使用。

以上各種解決新用戶冷啟動問題的算法都是在已知用戶信息或者用戶與推薦系統(tǒng)有過一些交互的基礎上進行的推薦,這些算法在未獲知用戶信息、用戶與系統(tǒng)沒有交互或者交互非常少的情況下難以取得令人滿意的效果。為解決該問題,本文建立N臂老虎機(N-armed bandit)[10]和免疫反饋(Immune Feedback)[11]相結合的模型,提出一種改進的Epsilon-greedy算法EGIF為新用戶進行推薦,并根據(jù)用戶的反饋及時調(diào)整策略,以不斷改善算法的推薦效果[12]。

1 N臂老虎機模型

一臺老虎機有多個拉桿,拉動每個拉桿可能獲得0個或1個金幣,這個回報是隨機的。如果拉動拉桿的次數(shù)有限,那么如何在老虎機上獲得最大回報(即最多的金幣數(shù)),就是所謂的N臂老虎機問題。

為了獲得最大回報,賭徒應該盡快找出回報率最高的拉桿。最簡單的方法是給每個拉桿相同的嘗試次數(shù)(如10次),統(tǒng)計每個拉桿返回的金幣個數(shù),找到返回金幣數(shù)最多的拉桿,以后一直選擇這個拉桿以期獲得最大回報。但這個策略存在一定缺陷:1)回報率低的老虎機可能在10次內(nèi)返回比回報率高的拉桿更多的金幣;2)如果拉桿較多,給每個拉桿10次實驗機會無疑會造成很大的浪費。

目前,解決N臂老虎機問題的算法大致分3類:

1)無指導“探索”算法,如Epsilon-greedy[13]、Epoch-greedy[14]等,這類算法每次以Epsilon的概率在N臂老虎機中隨機選擇一個拉桿,否則就選擇目前為止平均收益最大的那個拉桿。

2)有指導“探索”算法,如UCB(Upper Confidence Bound)[15]、EXP4[16]等,這類算法每次選擇置信上限最高的那個拉桿。

3)概率匹配算法,如Thompson sampling[17]等,這類算法假設每個拉桿產(chǎn)生收益的概率p符合beta分布,通過實驗不斷調(diào)整beta分布的參數(shù),每次選擇拉桿的方式為:用每個拉桿現(xiàn)有的beta分布產(chǎn)生一個隨機數(shù),選擇所產(chǎn)生的隨機數(shù)最大的那個拉桿。

在這些解決N臂老虎機問題的算法中,Epsilon-greedy算法和UCB算法在實際應用中表現(xiàn)較優(yōu)秀。

1.1 Epsilon-greedy算法

Epsilon-greedy算法是一種解決N臂老虎機問題的簡單算法。greedy算法總是選擇在當前時刻算法認為最好的動作。Epsilon-greedy算法和greedy算法非常相似,它一般會選擇最好的動作,也可能去“探索”其他可行的動作。Epsilon-greedy算法每次以Epsilon的概率去“探索”(在所有拉桿中隨機選擇一個拉桿),以1-Epsilon的概率去“發(fā)現(xiàn)”(選擇之前“探索”到的回報率最高的那個拉桿)。

在Epsilon-greedy算法中,比較關鍵的問題是如何確定Epsilon的值。如果Epsilon的值較大,會增加探索的概率,這雖能夠加快算法的收斂,但往往不能很好地利用已經(jīng)探索到的成果,導致結果較差;如果Epsilon的值較小,模型的穩(wěn)定性更好,但會使算法的收斂速度降低。

1.2 UCB算法

UCB算法在每輪選擇置信上限J(t)最大的拉桿,J(t)計算公式如下:

(1)

(2)

其中,μi為實際觀測到的老虎機返回金幣的概率,c(g)為返回金幣個數(shù),c(t)為全部嘗試次數(shù),ni為t輪內(nèi)嘗試拉動第i個拉桿的次數(shù)。

UCB算法將“探索”和“發(fā)現(xiàn)”2個過程融合到一個公式中,能夠讓拉動次數(shù)較少的拉桿有更多被嘗試的機會。

1.3 N臂老虎機模型在推薦算法中的應用

N臂老虎機問題是優(yōu)化一個同時玩多個老虎機的賭徒的收入統(tǒng)計問題[18-19]。文獻[20]基于內(nèi)容的N臂老虎機模型提出LinRel算法,文獻[21]提出LinUCB算法,改進了LinRel算法并用基于內(nèi)容的N臂老虎機模型在新聞文本推薦中對用戶反饋進行建模。N臂老虎機模型應用于推薦算法時,將N臂老虎機的拉桿定義為將要推薦給用戶的物品,將拉動拉桿的動作定義為給用戶進行推薦,將拉桿返回的獎勵定義為用戶點擊了為其推薦的物品。

在為用戶推薦物品時,每次為用戶推薦一個物品后收集用戶對此物品的評分。根據(jù)已知的用戶評分決定下一輪應該推薦的物品。此時,可以繼續(xù)推薦用戶之前評分最高的物品,也可以隨機選擇一個物品推薦給用戶,前者稱為“發(fā)現(xiàn)”,后者稱為“探索”。

N臂老虎機模型能夠根據(jù)用戶的在線反饋為新用戶進行合理的推薦,同時由于老虎機模型中存在的“探索”部分,能夠提高推薦結果的多樣性[22]。

2 免疫反饋模型

免疫系統(tǒng)是人類和脊椎動物所擁有的防御系統(tǒng),是由許多執(zhí)行免疫功能的免疫器官、免疫細胞和免疫分子等組成的復雜自適應系統(tǒng)。免疫系統(tǒng)使機體免受病原體、有害物質(zhì)以及癌細胞等致病因子的侵害。在免疫系統(tǒng)中,有一種免疫反饋機制同時完成2項任務:1)對出現(xiàn)的抗原快速反應;2)使免疫系統(tǒng)快速達到穩(wěn)定平衡。

免疫反饋機制的原理如圖1所示,人體的免疫細胞大致分為T細胞和B細胞2種。T細胞的主要功能是吞噬入侵的抗原,B細胞的主要功能是產(chǎn)生多種抗體,用抗體來中和入侵的抗原。當抗原物質(zhì)(細菌、病毒)入侵人體后,會同時刺激輔助T細胞和抑制T細胞。一方面,輔助T細胞能夠協(xié)助B細胞產(chǎn)生抗體,促進Killer T細胞的生成;另一方面,抑制T細胞也會抑制B細胞產(chǎn)生抗體,抑制Killer T細胞的生成。通過免疫系統(tǒng)中輔助T細胞和抑制T細胞之間的相互作用,使免疫系統(tǒng)實時的處在抗原和抗體的動態(tài)平衡中。這種動態(tài)平衡使得免疫系統(tǒng)能夠?qū)θ肭值目乖龀隹焖俜磻?并且能使免疫系統(tǒng)迅速達到平衡。

圖1 免疫反饋機制原理

研究人員借鑒免疫反饋思想來加速神經(jīng)網(wǎng)絡算法的收斂速度[23-24]。本文將免疫反饋模型應用于Epsilon-greedy算法,使Epsilon-greedy算法能夠更快收斂,從而更好地為新用戶進行推薦。

輔助T細胞對B細胞的刺激定義為:

Thelp(k)=K1ε(k)

(3)

其中,K1為T細胞對B細胞的刺激程度, ε(k)為第k代B細胞的數(shù)量。

抑制T細胞對B細胞的抑制定義為:

Tsup(k)=K2{Tkill(k-d)-Tkill(k-d-1)}2ε(k)

(4)

其中,K2為抑制因子,d為超參數(shù),表示第d代,Tkill(k-d)和Tkill(k-d-1)分別為第k-d代和第k-d-1代Killer T細胞數(shù)量。

Killer T細胞接受到的總刺激為:

TKiller(k)=Thelp(k)-Tsup(k)

(5)

若以Δreward作為抗原,Epsilon-greedy算法中的Epsilon參數(shù)值作為抗體,則有如下關系式[21]:

Epsilon(k)=Kp[1-γ{Epsilon(k-d)-

Epsilon(k-d-1)}2]Δreward

(6)

其中,Kp=K1,γ=K2/K1。參數(shù)Kp控制免疫系統(tǒng)對抗原的反應速度,參數(shù)γ控制免疫系統(tǒng)的穩(wěn)定性。Epsilon(k)為第k次對用戶推薦時Epsilon的值,reward為用戶對推薦物品的喜好程度,其計算參考式(7)。

(7)

其中,click(k)是用戶的點擊率,recommended(k)是為用戶推薦物品的總數(shù)。Δreward的計算如式(8)。

Δreward=reward(k)-reward(k-d)

(8)

3 EGIF算法

本文提出的EGIF算法將Epsilon-greedy算法和免疫反饋模型相結合,用以解決新用戶冷啟動問題。

將給用戶推薦的N個物品定義為N臂老虎機的N個拉桿,每次為用戶進行推薦相當于一次拉動老虎機拉桿的動作,每次推薦后用戶是否點擊了所推薦的物品相當于用戶在拉動某一個拉桿時是否獲得了獎勵。

Epsilon-greedy算法以Epsilon的概率去隨機“探索”用戶的潛在偏好,并為用戶推薦物品,以1-Epsilon的概率去利用已經(jīng)“探索”到的用戶偏好來為用戶推薦物品。傳統(tǒng)的Epsilon-greedy算法的Epsilon參數(shù)值是固定不變的,如果Epsilon取值較小,算法在短時間內(nèi)不容易“探索”到用戶的潛在興趣,導致算法的收斂速度較慢,隨著時間的推移,在“探索”到用戶的興趣后,能以很大的概率去利用已經(jīng)“探索”到的用戶興趣并進行推薦,從而取得較好的推薦效果。如果Epsilon取值較大,雖然算法能夠更快的收斂,在較短時間內(nèi)“探索”到用戶的興趣,但是在“探索”到用戶興趣后仍然保持很大的概率去“探索”,而不是根據(jù)已經(jīng)“探索”到的用戶興趣進行推薦,這會導致算法的推薦效果較差。不同Epsilon值的平均推薦回報率如圖2所示。

圖2 不同Epsilon值的平均回報率

在免疫反饋系統(tǒng)中,當抗原入侵機體后,在抗原的刺激下抗體數(shù)量迅速上升。隨著抗體數(shù)量的增多,抗體會抑制自身的增長使抗體數(shù)量迅速下降,以便免疫系統(tǒng)保持平衡。本文利用免疫反饋模型來動態(tài)調(diào)整Epsilon參數(shù)的值,使算法既能很快收斂,又能實現(xiàn)很好的推薦效果。根據(jù)式(6),在用戶剛進入系統(tǒng)時,Epsilon的值會迅速升高,以盡快“探索”用戶的偏好。隨著用戶與系統(tǒng)交互次數(shù)的增多,Epsilon的值會迅速降低,以便更好地利用已“探索”到的用戶偏好進行推薦。本文EGIF算法具體描述如下:

1.begin

2.初始化拉桿的回報分布為用戶隨機推薦物品

3.k=0

4.while true do

5.begin

6.if 用戶點擊了推薦物品 then

7.返回1

8.else 返回0

9.記錄推薦物品、用戶是否點擊物品及點擊次數(shù)

10.根據(jù)式(7)計算reward(k)

11.根據(jù)式(8)計算Δreward

12.根據(jù)式(6)計算Epsilon

13.r←0到1之間的隨機數(shù)

14.if r>Epsilon then

15.隨機推薦物品

16.else 推薦點擊次數(shù)最多的物品

17.更新拉桿的回報分布

18.k++

19.end

20.end

4 實驗結果及分析

EGIF算法需要實時分析和選擇將要推薦給用戶的物品,這意味著算法的行為要依賴于其看到的數(shù)據(jù),算法所看到的數(shù)據(jù)又依賴于算法的行為。算法數(shù)據(jù)和算法行為的關系如圖3所示。

圖3 算法數(shù)據(jù)與算法行為間的關系

因此,EGIF算法是一種在線算法,算法的測試需要在真實的系統(tǒng)中根據(jù)用戶反饋來進行,但是在真實系統(tǒng)中進行測試的風險很高。為解決這一問題,本文采用蒙特卡羅模擬方法[25]進行測試。該方法能夠提供實時的模擬數(shù)據(jù)供算法分析,從而對算法進行評測。

本文的實驗環(huán)境為:Intel Core i5 CPU,2.7 GHz主頻,Windows 7操作系統(tǒng),4 GB內(nèi)存,編程語言為Python。在實驗中,N臂老虎機的拉桿為伯努利拉桿,共設置5個不同的拉桿,每個拉桿返回獎勵的概率分別為0.1、0.2、0.3、0.5、0.9。實驗共進行5 000個epoch模擬,每個epoch按順序拉動500次拉桿,記錄每個拉桿返回的reward值以及總reward值。

將EGIF算法應用于推薦系統(tǒng),令用戶點擊算法推薦的物品的概率為p,沒有點擊算法推薦的物品的概率為1-p。每個拉桿的回報率各不相同,例如,拉桿1的回報率為0.1,代表拉動拉桿10次,會有一次返回的獎勵為1,其余時候返回的獎勵為0。回報率表示推薦系統(tǒng)中用戶對每件物品的偏好程度。

在實驗中,對EGIF算法進行測試并返回一個測試結果數(shù)據(jù)集,以說明每次模擬時算法選擇了哪個拉桿以及算法在每一個時間點的表現(xiàn)。由于每次模擬都根據(jù)隨機數(shù)生成,實驗結果的噪聲很大,因此需要進行多次模擬。EGIF算法和固定Epsilon的Epsilon-greedy算法的平均獎勵指標實驗結果如圖4所示,其中,Epsilon-greedy算法的Epsilon超參數(shù)值分別選取0.1、0.3、0.5、0.7和0.9。從圖4可以看出,用戶與系統(tǒng)交互約5次時,EGIF算法在平均獎勵上已經(jīng)超出了固定Epsilon的Epsilon-greedy算法,表明EGIF算法能夠在極短的時間內(nèi)找到用戶的偏好,為用戶進行更好的推薦。從圖4還能看出,不僅是在極短的時間內(nèi)EGIF算法能夠找到用戶的偏好,在以后更長的時間里,EGIF算法能夠維持在0.85的平均獎勵,而固定Epsilon的Epsilon-greedy算法在與用戶交互100次時也只能達到0.8的平均獎勵。綜上,與固定Epsilon的Epsilon-greedy算法相比,EGIF算法不僅能更好地解決新用戶冷啟動問題,而且能夠在較長的時期內(nèi)維持較佳的推薦效果。

圖4 2種算法平均獎勵比較

圖5、圖6所示分別為EGIF算法和固定Epsilon的Epsilon-greedy算法的獎勵總和以及選擇到最好拉桿的概率結果。從圖5、圖6可以看出,相對于固定Epsilon的Epsilon-greedy算法,本文EGIF算法性能更優(yōu)。

圖5 2種算法獎勵總和比較

圖6 2種算法選擇到最好拉桿的概率比較

EGIF算法在平均獎勵指標上與Softmax算法、Annelealing算法以及UCB算法的比較如圖7所示。從圖7可以看出,EGIF算法在用戶與系統(tǒng)交互的前20次中,雖然平均獎勵值有所波動,但是該值幾乎一直高于Softmax算法和Anneleanling算法,而UCB算法波動劇烈,平均獎勵結果非常不穩(wěn)定。EGIF算法在平均獎勵方面之所以有一定的波動,是因為免疫反饋模型會根據(jù)算法平均獎勵的變化動態(tài)地調(diào)整Epsilon參數(shù)的值,以使算法能夠快速收斂。

圖7 4種算法平均獎勵對比

圖8、圖9所示分別為EGIF算法、Softmax算法、Annelealing算法以及UCB算法在獎勵總和指標和選擇到最好拉桿概率指標上的比較結果。從圖8、圖9可以看出,EGIF算法在這2個指標上的表現(xiàn)都優(yōu)于對比算法。

圖8 4種算法獎勵總和對比

圖9 4種算法選擇到最好拉桿的概率對比

5 結束語

本文將Epsilon-greedy算法和免疫反饋模型相結合,提出一種解決新用戶冷啟動問題的EGIF算法。在傳統(tǒng)的Epsilon-greedy算法中利用免疫反饋模型動態(tài)調(diào)整Epsilon的參數(shù)值,以解決傳統(tǒng)Epsilon-greedy算法不能快速收斂的問題。實驗結果表明,EGIF算法能夠在新用戶進入系統(tǒng)時迅速找到用戶的偏好,為新用戶進行更好的推薦。在解決N臂老虎機問題的諸多算法中,除Epsilon-greedy算法外,其他算法也存在“探索”和“發(fā)現(xiàn)”問題,本文僅對Epsilon-greedy算法和免疫反饋模型相結合進行了研究。下一步考慮將免疫反饋模型與其他算法相結合,以進一步提高本文推薦算法的性能。