一種核的上下文多臂賭博機(jī)推薦算法

王鼎，門昌騫，王文劍,2

（1.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006;2.山西大學(xué) 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，山西 太原 030006）

個(gè)性化推薦在各種系統(tǒng)中被廣泛應(yīng)用，通過為用戶提供定制化的網(wǎng)絡(luò)服務(wù)，可以很好地滿足用戶的個(gè)性化需求，從而提升用戶滿意度。盡管傳統(tǒng)推薦算法在一些領(lǐng)域已經(jīng)非常成功，但是僅適用于用戶和內(nèi)容變化小的相對(duì)靜態(tài)的場(chǎng)景[1]。例如，傳統(tǒng)協(xié)同過濾[2-3]需要在用戶和內(nèi)容有大量重疊的消費(fèi)記錄等信息的場(chǎng)景下才能應(yīng)用，而基于內(nèi)容的推薦算法[4-5]推薦傾向于過于相似的內(nèi)容，對(duì)新用戶的推薦存在困難。

現(xiàn)實(shí)生活中存在著快速變化的推薦環(huán)境，其內(nèi)容領(lǐng)域每時(shí)每刻都在發(fā)生著變化，內(nèi)容的流行程度隨著時(shí)間而變化，大量沒有任何歷史記錄的新用戶也不斷進(jìn)入推薦系統(tǒng)。在這種場(chǎng)景下推薦系統(tǒng)必須能夠快速獲得用戶的興趣偏好，才能更好地為用戶提供個(gè)性化服務(wù)?？焖佾@得用戶興趣信息和短期內(nèi)用戶體驗(yàn)是競(jìng)爭(zhēng)關(guān)系，一方面需要關(guān)注能夠提高用戶興趣的內(nèi)容，另一方面也需要探索新內(nèi)容以全面改善用戶體驗(yàn)，這就產(chǎn)生了探索-利用困境(exploration-exploitation dilemma，EE)[6]。為了實(shí)現(xiàn)用戶的長(zhǎng)期體驗(yàn)，必須平衡探索和利用的矛盾。

多臂賭博機(jī)[7-9]是平衡這一矛盾的有效模型，多臂賭博機(jī)又可以按照是否考慮狀態(tài)分為上下文無關(guān)多臂賭博機(jī)和上下文多臂賭博機(jī)[10-11]。上下文無關(guān)多臂賭博機(jī)算法主要有ε-greedy[12]、UCB1[13]、Thompson sampling[14]等。這類上下文無關(guān)的多臂賭博機(jī)算法應(yīng)用于推薦系統(tǒng)中，沒有利用用戶和內(nèi)容的上下文信息，因此導(dǎo)致推薦準(zhǔn)確性不高。

上下文多臂賭博機(jī)算法將內(nèi)容和用戶等上下文信息融入推薦決策過程，可以提高推薦準(zhǔn)確率。LinUCB (linear upper confidence bound)是一種成功應(yīng)用于雅虎新聞推薦系統(tǒng)的上下文多臂賭博機(jī)算法，可以有效提高在快速變化環(huán)境下的推薦準(zhǔn)確率[15]。但是LinUCB 算法為了簡(jiǎn)化模型和降低計(jì)算成本，假設(shè)期望收益和上下文是線性關(guān)系的。這種線性假設(shè)在現(xiàn)實(shí)中往往是不成立的，所以導(dǎo)致LinUCB 算法的推薦準(zhǔn)確率并不高。Agrawal等[16]提出的湯普森采樣算法LinTS，同樣是基于線性收益上下文賭博機(jī)模型。

在LinUCB 算法基礎(chǔ)上，結(jié)合傳統(tǒng)推薦算法提出了很多改進(jìn)算法。文獻(xiàn)[17]結(jié)合協(xié)同過濾的思想將用戶之間的影響融合到LinUCB 算法，提出了GOB.Lin 算法。文獻(xiàn)[18]提出了利用用戶信息在線聚類算法CLUB，對(duì)用戶聚類。文獻(xiàn)[19]提出了對(duì)用戶和內(nèi)容雙聚類的COFIBA 算法。文獻(xiàn)[20]提出結(jié)合潛在因子的fatorUCB 算法。這些傳統(tǒng)推薦算法與多臂賭博機(jī)的結(jié)合可以提升推薦效果，但都屬于結(jié)合創(chuàng)新，沒有改進(jìn)線性收益的上下文多臂賭博機(jī)模型。

本文突破了LinUCB 算法線性假設(shè)的前提，提出了一種基于核方法[21]在非線性前提下計(jì)算預(yù)測(cè)收益置信區(qū)間上界的方法，從模型上改進(jìn)基于線性收益的上下文多臂賭博機(jī)，提高了算法的推薦準(zhǔn)確率。

1 背景模型

1.1 上下文多臂賭博機(jī)

推薦系統(tǒng)中EE 問題方面一個(gè)得到廣泛研究的模型就是上下文多臂賭博機(jī)模型，將該模型形式化來進(jìn)行更好的理解。上下文多臂賭博機(jī)是指面對(duì)K個(gè)臂,每輪選擇其中一個(gè)臂并獲得收益，一共進(jìn)行T輪選擇，目標(biāo)是使T輪之后總的收益更高。上下文多臂賭博機(jī)在每一輪中：

1）觀察當(dāng)前上下文信息x。上下文總結(jié)了當(dāng)前的環(huán)境，如日期、天氣、用戶等影響做出選擇的信息。

2）根據(jù)歷史記錄，算法選擇一個(gè)臂a并獲得真實(shí)收益r。預(yù)測(cè)收益由上下文信息x所決定。

3）算法根據(jù)最新得到的觀測(cè)歷史(x,a,r)，更新下一輪選擇策略。

多臂賭博機(jī)最大化總收益的優(yōu)化目標(biāo)可以等價(jià)替換為更常用的累積遺憾，表示為

式中：rt為在每一輪中實(shí)際獲得的收益；為每一輪中最佳選擇的收益。

可以很自然地將上下文多臂賭博機(jī)建模為推薦算法。以新聞推薦為例，將新聞文章庫(kù)中的文章定義為臂，通過上下文信息為用戶推薦這些臂(文章)。觀察所推薦文章的反饋，當(dāng)推薦文章被點(diǎn)擊則收益為1，否則為0。最后根據(jù)歷史收益信息，調(diào)整選擇策略。這樣一段時(shí)間后最大化上下文多臂賭博機(jī)的收益相當(dāng)于最大化點(diǎn)擊數(shù)，也就是推薦系統(tǒng)的目標(biāo)點(diǎn)擊率(click-through rate,CTR)更高。

1.2 LinUCB 算法

LinUCB 是一種上下文多臂賭博機(jī)算法，該算法基于期望收益r和上下文x是線性關(guān)系的假設(shè)，得到了線性條件下的預(yù)測(cè)收益及其置信區(qū)間的閉式解，然后利用預(yù)測(cè)收益的置信區(qū)間上界來平衡探索與利用的矛盾。LinUCB 算法的主要過程如下:

1)計(jì)算預(yù)測(cè)收益。xt,a∈Rd表示關(guān)于用戶t和內(nèi)容a的上下文特征向量，θa為內(nèi)容a的預(yù)測(cè)線性參數(shù)，則預(yù)測(cè)收益表示為

Xa是關(guān)于內(nèi)容a的上下文特征的構(gòu)造矩陣，每一行表示一個(gè)上下文xt,a,一共m行，定義如下:

Xa:=[x1,ax2,a···xm,a]T∈Rm×d

Xa中的m個(gè)上下文對(duì)應(yīng)的實(shí)際收益表示為ya。在訓(xùn)練數(shù)據(jù)(Xa,ya)上應(yīng)用嶺回歸可得到內(nèi)容a的預(yù)測(cè)線性參數(shù)為

然后通過式(1)和式(2)計(jì)算得到預(yù)測(cè)收益。

2)計(jì)算預(yù)測(cè)收益的置信區(qū)間。根據(jù)文獻(xiàn)[22]可知，在線性條件下有

式(3)成立的概率至少為 1?δ,δ為任意大于0 的實(shí)數(shù)，α=1+是一個(gè)常數(shù)。實(shí)際上式(3)給出的預(yù)測(cè)收益的置信區(qū)間半徑c為

3)由式(1)和式(4)可以得到每輪的選擇策略，即對(duì)每一輪選擇置信區(qū)間上界最大的內(nèi)容at進(jìn)行推薦

最大置信區(qū)間上界是一種利用估計(jì)中的不確定性來平衡探索和利用的方法。算法對(duì)不確定性采取樂觀的態(tài)度，將對(duì)收益估計(jì)的置信區(qū)間上界作為選擇內(nèi)容的依據(jù)。這樣選擇的好處在于:如果選擇的內(nèi)容是最佳的，則成功得到了收益;如果選擇的內(nèi)容并非最佳，則進(jìn)一步消除了置信區(qū)間上界最大內(nèi)容的不確定性。最后根據(jù)所選擇內(nèi)容at的真實(shí)收益更新內(nèi)容at的線性參數(shù) θa。

LinUCB 本質(zhì)上是一種基于線性收益的上下文多臂賭博機(jī)，但是在現(xiàn)實(shí)的網(wǎng)絡(luò)服務(wù)中獲取到的數(shù)據(jù)往往并不是線性關(guān)系，所以導(dǎo)致LinUCB算法應(yīng)用于個(gè)性化推薦預(yù)測(cè)準(zhǔn)確率不高。

2 K-UCB 算法

為了解決LinUCB 算法線性假設(shè)造成的推薦準(zhǔn)確率不高，本文提出了K-UCB(kernel upper confidence bound)算法，基于核方法實(shí)現(xiàn)了在高維線性空間計(jì)算預(yù)測(cè)收益及其置信區(qū)間，從而提高了推薦準(zhǔn)確率。

2.1 算法設(shè)計(jì)

核方法是一種解決非線性問題的有效方法，其主要思想是將非線性數(shù)據(jù)向高維空間映射，使其在高維空間中轉(zhuǎn)換為線性數(shù)據(jù)，然后就可以利用成熟的線性空間知識(shí)在高維空間中解決原先的非線性問題。

在核方法思想下，將上下文特征向量x映射到合適的高維空間，在這個(gè)高維空間中預(yù)測(cè)收益和上下文特征向量是線性關(guān)系，此時(shí)可以用基于線性收益的上下文賭博機(jī)知識(shí)來解決非線性收益的問題。在高維空間中計(jì)算預(yù)測(cè)收益及其置信區(qū)間:

1)計(jì)算預(yù)測(cè)收益。假設(shè)原空間向量x映射到高維空間后表示為 φ(x)。高維空間中兩個(gè)向量的內(nèi)積可以表示為核函數(shù)k(x,x′)=φ(x)·φ(x′)。對(duì)應(yīng)原空間中構(gòu)造矩陣X，則映射后上下文特征的構(gòu)造矩陣Xφ表示為

對(duì)訓(xùn)練數(shù)據(jù)(Xφ,y)使用核嶺回歸方法,則需要預(yù)測(cè)的上下文x?的預(yù)測(cè)收益為

而K則為m個(gè)上下文特征構(gòu)成的核矩陣:

K為半正定的核矩陣，所以(K+Im)?1一定存在。

2)計(jì)算預(yù)測(cè)收益的置信區(qū)間。由于映射后高維空間滿足線性關(guān)系，則映射后高維空間與原空間是類似的，滿足:

式(6)成立的概率至少為 1?δ,δ為任意大于0 的實(shí)數(shù),α=1+是一個(gè)常數(shù)，此時(shí)同樣也有與原空間形式類似的置信區(qū)間半徑c:

需要將式(7)變?yōu)楹撕瘮?shù)的形式，利用Sherman-Morrison-Woodbury 公式,Sherman-Morrison-Woodbury 公式描述如下:A∈Rn×n為 R域上非奇異矩陣，U,V∈Rn×k，若A+UVT非奇異，則有

式(8)提供了將式(7)變?yōu)楹撕瘮?shù)形式的一種途徑，使式(8)中A=Id,U=,V=Xφ，那么有

將式(9)代入式(7)可以得到核函數(shù)形式的置信區(qū)間半徑為

3)計(jì)算逆矩陣。核函數(shù)形式的預(yù)測(cè)收益式(5)及其置信區(qū)間式(10)中都有(K+Im)?1這一項(xiàng)，將該逆矩陣記為Vm。Vm大小為m×m，直接求逆矩陣復(fù)雜度為O(m3)，當(dāng)m很大時(shí)代價(jià)很大，算法失去實(shí)際意義。為解決這個(gè)問題，本文將矩陣求逆修改為迭代計(jì)算方式。根據(jù)文獻(xiàn)[23]可知，實(shí)對(duì)稱矩陣有求逆迭代算法。實(shí)對(duì)稱矩陣Wn如式(11)所示：

式中：Wn∈Rn×n，Wn?1∈R(n?1)×(n?1)均為實(shí)對(duì)稱矩陣；e為n?1維向量，eT是其轉(zhuǎn)置；p是常數(shù)。Wn的逆矩陣可以通過迭代計(jì)算，即

式(12)可由塊矩陣求逆定理證明。

K+I也是實(shí)對(duì)稱矩陣，形式為

滿足式(11)的定義,可以得到其逆矩陣V的迭代計(jì)算方法:

這樣就可以通過式(13)不斷迭代來計(jì)算逆矩陣，減少了該算法的計(jì)算成本。

2.2 算法流程

K-UCB 算法需要輸入超參數(shù) α、β的值，其中α控制探索與利用的平衡，β是核函數(shù)的參數(shù)。為需要推薦的每個(gè)用戶計(jì)算內(nèi)容池At中每個(gè)內(nèi)容預(yù)測(cè)收益的置信區(qū)間上界，選擇置信區(qū)間上界最大的內(nèi)容進(jìn)行推薦，并獲得點(diǎn)擊反饋，根據(jù)歷史收益情況，更新選擇策略。

3 實(shí)驗(yàn)與結(jié)果

在本節(jié)中首先介紹了各個(gè)對(duì)比算法的設(shè)置，并使用這些算法在合成數(shù)據(jù)和真實(shí)場(chǎng)景數(shù)據(jù)集(雅虎新聞數(shù)據(jù)集)上進(jìn)行實(shí)驗(yàn)。

3.1 算法對(duì)比

1）Random：隨機(jī)策略總是以相等的概率選擇一個(gè)內(nèi)容。這個(gè)算法不需要參數(shù)，也不會(huì)隨著時(shí)間學(xué)習(xí)。在本文中隨機(jī)策略用來衡量其他算法的提升。

2）ε-greedy[12]：該算法統(tǒng)計(jì)每個(gè)內(nèi)容的收益，以 ε概率隨機(jī)選擇候選內(nèi)容，以1?ε概率選擇收益最高的內(nèi)容。參數(shù) ε控制探索程度。

3）UCB1[13]：該算法統(tǒng)計(jì)每個(gè)內(nèi)容的收益，并估計(jì)收益的置信區(qū)間，置信區(qū)間為c=，式中t為內(nèi)容的歷史總推薦次數(shù)，t越大內(nèi)容的收益信息越明確，置信區(qū)間會(huì)越小，參數(shù) α控制探索程度。

4）Thompson sampling[14]：該算法假設(shè)每個(gè)內(nèi)容都服從一個(gè)收益分布估計(jì),每輪從估計(jì)的分布采樣，選取采樣值最大的內(nèi)容推薦，最后根據(jù)收益情況更新內(nèi)容的收益分布。這里采用Beta 分布作為先驗(yàn)分布。

5）LinUCB[15]：算法在UCB1 基礎(chǔ)上加入上下文，基于線性收益假設(shè)預(yù)測(cè)收益及其置信區(qū)間。參數(shù) α控制探索程度。

3.2 合成數(shù)據(jù)集

為了測(cè)試K-UCB 的性能，合成了3 組不同的上下文多臂賭博機(jī)數(shù)據(jù)。每組設(shè)置K=4 個(gè)臂，進(jìn)行T=15 000 輪實(shí)驗(yàn)，每一輪中臂的上下文xt,k是隨機(jī)采樣產(chǎn)生的20 維單位向量。設(shè)置3 組不同收益，由以下函數(shù)產(chǎn)生:

式中：θ是20 維單位向量；η(0,1)為噪聲項(xiàng)。圖1為L(zhǎng)inUCB 和K-UCB 算法在3 組不同收益函數(shù)r1(x)、r2(x)和r3(x)下累積遺憾隨學(xué)習(xí)輪次的變化曲線,且LinUCB 和K-UCB 算法參數(shù)都經(jīng)過調(diào)優(yōu)。如圖1(a)所示，在r1(x)線性收益條件下，K-UCB和LinUCB 算法累積遺憾隨著學(xué)習(xí)輪次增多逐漸增長(zhǎng)緩慢，但是LinUCB 收斂速度優(yōu)于K-UCB算法。在r2(x)和r3(x)非線性收益下，LinUCB 算法效果不佳，累積遺憾不會(huì)隨著學(xué)習(xí)輪次增多而降低增長(zhǎng)速度。而K-UCB 算法表現(xiàn)良好，隨著學(xué)習(xí)輪次增多，累積遺憾增長(zhǎng)放緩，該實(shí)驗(yàn)表明在非線性收益數(shù)據(jù)下K-UCB 較LinUCB 累積遺憾更低，性能更好。

圖1 LinUCB 和K-UCB 算法在不同收益假設(shè)上的比較Fig.1 Comparison of LinUCB and K-UCB on different reward hypothesis

3.3 Yahoo News 數(shù)據(jù)集

真實(shí)場(chǎng)景數(shù)據(jù)采用雅虎新聞數(shù)據(jù)集R6A -Yahoo! Front Page Today Module User Click Log Dataset[24]。該數(shù)據(jù)集收集了從2009 年5 月1 日到10 日的訪問流量數(shù)據(jù)約3 600 萬條。

如表1 所示，每一條數(shù)據(jù)記錄一個(gè)由4 個(gè)部分組成的完整的事件，分別是推薦的文章id，用戶的點(diǎn)擊反饋以及用戶和文章的6 維特征。用戶和文章的6 維特征向量都是原始特征（如用戶對(duì)應(yīng)的性別、年齡、地理和行為等特征，文章對(duì)應(yīng)的分類、主題等特征）通過降維和雙線性模型聯(lián)合分析構(gòu)建的。

表1 雅虎新聞數(shù)據(jù)集Table 1 Yahoo! News dataset

當(dāng)算法選擇的文章與記錄數(shù)據(jù)不同時(shí)，無法觀測(cè)到所選擇文章的收益。本文采用文獻(xiàn)[25]提出的離線評(píng)估方法，這種方法被證明是無偏的估計(jì)。在這種評(píng)估方法下，給定當(dāng)前日志記錄，如果算法選擇了與日志記錄相同的內(nèi)容,則該事件被保留，即添加到歷史記錄中,同時(shí)更新總推薦次數(shù)N和總收益R。如果算法選擇了一個(gè)不同于日志記錄的內(nèi)容，那么該事件將完全被忽略，算法將繼續(xù)處理下一個(gè)事件而不改變其狀態(tài)?；谶@種拒絕采樣的評(píng)估方法，將實(shí)際點(diǎn)擊次數(shù)與推薦總次數(shù)的比值(R/N)定義為文章點(diǎn)擊率。點(diǎn)擊率是推薦算法的最常用指標(biāo)，點(diǎn)擊率越高意味著累積遺憾越小。

推薦系統(tǒng)通常在小部分流量中學(xué)習(xí)，然后將學(xué)習(xí)到的知識(shí)應(yīng)用到其余的大部分流量中，所以本實(shí)驗(yàn)將數(shù)據(jù)分為學(xué)習(xí)桶和部署桶進(jìn)行，學(xué)習(xí)桶分配20%的隨機(jī)流量數(shù)據(jù)，部署桶分配80%的隨機(jī)流量數(shù)據(jù)。數(shù)據(jù)更多的部署桶模擬真實(shí)的部署環(huán)境，其點(diǎn)擊率數(shù)據(jù)更為重要，但學(xué)習(xí)桶中點(diǎn)擊率高意味著學(xué)習(xí)效率更快，所以實(shí)驗(yàn)給出了兩個(gè)桶中的點(diǎn)擊率數(shù)據(jù)。

實(shí)驗(yàn)分為3 步：①確定3 種對(duì)比算法(ε-greedy、UCB1 和LinUCB)的最佳參數(shù)；②確定K-UCB 的核函數(shù)選擇和參數(shù)選擇；③將所有對(duì)比算法均在最優(yōu)條件下進(jìn)行比較。

1)尋找ε-greedy、UCB1 和LinUCB 的最佳參數(shù)設(shè)置，圖2 為3 個(gè)算法在不同參數(shù)下的性能折線圖。

如圖2 所示，3 個(gè)算法在學(xué)習(xí)桶和部署桶都是大致中間高兩邊低。這是因?yàn)楫?dāng)參數(shù)ε或者α過小時(shí)，沒有足夠的探索，算法無法識(shí)別出好的文章，導(dǎo)致點(diǎn)擊量較少。另一方面，當(dāng)參數(shù)太大時(shí)，算法會(huì)過度探索，從而浪費(fèi)了一些增加點(diǎn)擊次數(shù)的機(jī)會(huì)。從圖2 中可以看到，ε-greedy、UCB1和LinUCB 的最佳參數(shù)分別為0.2、0.1 和0.3。

圖2 算法在不同參數(shù)下的點(diǎn)擊率提升倍數(shù)Fig.2 CTR lift of the algorithms under different parameters

2)表2 為不同的核函數(shù)在最佳參數(shù)組合下所得到的相對(duì)點(diǎn)擊率結(jié)果。其中 α為平衡探索利用程度的參數(shù)，線性核具體表示為

k(x,x′)=xTx′

多項(xiàng)式核具體表示為

k(x,x)=(g·xTx+c)d

高斯核具體表示為

k(x,x′)=exp(?β·||x?x′||2)

從表2 可以看出，雅虎新聞數(shù)據(jù)集在線性核函數(shù)時(shí)表現(xiàn)不佳，表明數(shù)據(jù)在原始空間是線性不可分的。在多項(xiàng)式核函數(shù)時(shí)點(diǎn)擊率較線性核有提升，較高斯核效果略差。所以K-UCB 算法選擇高斯核函數(shù)進(jìn)行雅虎新聞數(shù)據(jù)集的實(shí)驗(yàn)。

表2 核函數(shù)選擇Table 2 Kernel function selection

以高斯核函數(shù)為例說明具體參數(shù)選擇方法，設(shè)置30 組(α,β)參數(shù)組合進(jìn)行網(wǎng)格搜索，表3 和表4分別為在學(xué)習(xí)桶和部署桶中30 組不同參數(shù)組合下K-UCB 算法的點(diǎn)擊率提升倍數(shù)。

表3 學(xué)習(xí)桶中網(wǎng)格搜索K-UCB 參數(shù)結(jié)果Table 3 Grid search results of K-UCB in Learning Bucket

表4 部署桶中網(wǎng)格搜索K-UCB 參數(shù)結(jié)果Table 4 Grid search results of K-UCB in Deploying Bucket

從表3 和表4 中可以看到，當(dāng) α過大過小時(shí)點(diǎn)擊率都不高，這與1）的原理和結(jié)果相似。β是高斯核函數(shù)控制分類能力的參數(shù)，調(diào)整 β也是尋找合適高維空間的過程。當(dāng) β過小和過大時(shí)，點(diǎn)擊率提升都不高，說明沒有找到合適的特征高維空間。在 β=0.1這一列點(diǎn)擊率大致較其他 β取值高，說明找到了一個(gè)合適的特征高維空間。通過網(wǎng)格化搜索，在表中找到了最佳的參數(shù)組合，即α=0.2，β=0.1，這個(gè)參數(shù)下學(xué)習(xí)桶和部署桶中點(diǎn)擊率提升都最大。

通過2）找到了K-UCB 算法在雅虎新聞數(shù)據(jù)集上的最佳核函數(shù)和最佳參數(shù)，使用這組參數(shù)與其他算法進(jìn)行比較。

3)對(duì)比不同算法在最佳參數(shù)下的點(diǎn)擊率。如圖3 和圖4 分別為學(xué)習(xí)桶和部署桶中各個(gè)對(duì)比算法的點(diǎn)擊率隨迭代輪次的變化曲線。

圖3 算法在學(xué)習(xí)桶中的點(diǎn)擊率Fig.3 CTRs of various algorithms in Learning Bucket

圖4 算法在部署桶中的點(diǎn)擊率Fig.4 CTRs of various algorithms in Deploying Bucket

從圖3 和圖4 中可以看到，Random 策略下點(diǎn)擊率最低，這個(gè)策略達(dá)到穩(wěn)定后點(diǎn)擊率基本不會(huì)變化。去除輪次較小時(shí)的隨機(jī)波動(dòng)干擾，上下文無關(guān)的多臂賭博機(jī)算法(ε-greedy、Thompson sampling 和UCB1)點(diǎn)擊率曲線明顯低于上下文多臂賭博機(jī)算法(LinUCB 和K-UCB),這說明利用上下文信息可以明顯提高點(diǎn)擊率，因此在推薦系統(tǒng)中應(yīng)該盡可能利用上下文信息提高推薦準(zhǔn)確率，從而更好地滿足用戶的個(gè)性化需求。學(xué)習(xí)桶和部署桶中K-UCB 算法的點(diǎn)擊率曲線都高于LinUCB 算法，尤其在部署桶中K-UCB 算法較LinUCB 算法點(diǎn)擊率提升了約8%，證明了本文所提出算法的有效性。

該實(shí)驗(yàn)表明K-UCB 算法比其他基于多臂賭博機(jī)的推薦算法更適應(yīng)真實(shí)的非線性數(shù)據(jù)場(chǎng)景下的個(gè)性化推薦。

4 結(jié)束語

本文提出了一種LinUCB 改進(jìn)算法K-UCB，通過核方法將非線性問題轉(zhuǎn)化為線性問題。在合成數(shù)據(jù)集上驗(yàn)證了K-UCB 可以有效降低非線性環(huán)境下的累積遺憾，在雅虎新聞數(shù)據(jù)集上相比于基于線性收益的LinUCB 算法，點(diǎn)擊率最高提升了8%。將線性收益假設(shè)轉(zhuǎn)變?yōu)楦话愕氖找婕僭O(shè)，可以提高上下文多臂賭博機(jī)的推薦準(zhǔn)確率。多臂賭博機(jī)適應(yīng)動(dòng)態(tài)推薦環(huán)境的特性，可以改善傳統(tǒng)推薦算法，這也是未來可以進(jìn)一步研究的方向。