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

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

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

現(xiàn)實生活中存在著快速變化的推薦環(huán)境，其內(nèi)容領(lǐng)域每時每刻都在發(fā)生著變化，內(nèi)容的流行程度隨著時間而變化，大量沒有任何歷史記錄的新用戶也不斷進(jìn)入推薦系統(tǒng)。在這種場景下推薦系統(tǒng)必須能夠快速獲得用戶的興趣偏好，才能更好地為用戶提供個性化服務(wù)?？焖佾@得用戶興趣信息和短期內(nèi)用戶體驗是競爭關(guān)系，一方面需要關(guān)注能夠提高用戶興趣的內(nèi)容，另一方面也需要探索新內(nèi)容以全面改善用戶體驗，這就產(chǎn)生了探索-利用困境(exploration-exploitation dilemma，EE)[6]。為了實現(xià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 算法為了簡化模型和降低計算成本，假設(shè)期望收益和上下文是線性關(guān)系的。這種線性假設(shè)在現(xiàn)實中往往是不成立的，所以導(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，對用戶聚類。文獻(xiàn)[19]提出了對用戶和內(nèi)容雙聚類的COFIBA 算法。文獻(xiàn)[20]提出結(jié)合潛在因子的fatorUCB 算法。這些傳統(tǒng)推薦算法與多臂賭博機(jī)的結(jié)合可以提升推薦效果，但都屬于結(jié)合創(chuàng)新，沒有改進(jìn)線性收益的上下文多臂賭博機(jī)模型。

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

1 背景模型

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

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

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

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

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

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

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

可以很自然地將上下文多臂賭博機(jī)建模為推薦算法。以新聞推薦為例，將新聞文章庫中的文章定義為臂，通過上下文信息為用戶推薦這些臂(文章)。觀察所推薦文章的反饋，當(dāng)推薦文章被點(diǎn)擊則收益為1，否則為0。最后根據(jù)歷史收益信息，調(diào)整選擇策略。這樣一段時間后最大化上下文多臂賭博機(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ù)測收益及其置信區(qū)間的閉式解，然后利用預(yù)測收益的置信區(qū)間上界來平衡探索與利用的矛盾。LinUCB 算法的主要過程如下:

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

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

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

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

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

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

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

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

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

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

2 K-UCB 算法

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

2.1 算法設(shè)計

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

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

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

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

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

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

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

式(6)成立的概率至少為 1?δ,δ為任意大于0 的實數(shù),α=1+是一個常數(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)計算逆矩陣。核函數(shù)形式的預(yù)測收益式(5)及其置信區(qū)間式(10)中都有(K+Im)?1這一項，將該逆矩陣記為Vm。Vm大小為m×m，直接求逆矩陣復(fù)雜度為O(m3)，當(dāng)m很大時代價很大，算法失去實際意義。為解決這個問題，本文將矩陣求逆修改為迭代計算方式。根據(jù)文獻(xiàn)[23]可知，實對稱矩陣有求逆迭代算法。實對稱矩陣Wn如式(11)所示：

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

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

K+I也是實對稱矩陣，形式為

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

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

2.2 算法流程

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

3 實驗與結(jié)果

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

3.1 算法對比

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

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

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

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

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

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

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

式中：θ是20 維單位向量；η(0,1)為噪聲項。圖1為LinUCB 和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í)輪次增多逐漸增長緩慢，但是LinUCB 收斂速度優(yōu)于K-UCB算法。在r2(x)和r3(x)非線性收益下，LinUCB 算法效果不佳，累積遺憾不會隨著學(xué)習(xí)輪次增多而降低增長速度。而K-UCB 算法表現(xiàn)良好，隨著學(xué)習(xí)輪次增多，累積遺憾增長放緩，該實驗表明在非線性收益數(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ù)據(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ù)記錄一個由4 個部分組成的完整的事件，分別是推薦的文章id，用戶的點(diǎn)擊反饋以及用戶和文章的6 維特征。用戶和文章的6 維特征向量都是原始特征（如用戶對應(yīng)的性別、年齡、地理和行為等特征，文章對應(yīng)的分類、主題等特征）通過降維和雙線性模型聯(lián)合分析構(gòu)建的。

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

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

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

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

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

如圖2 所示，3 個算法在學(xué)習(xí)桶和部署桶都是大致中間高兩邊低。這是因為當(dāng)參數(shù)ε或者α過小時，沒有足夠的探索，算法無法識別出好的文章，導(dǎo)致點(diǎn)擊量較少。另一方面，當(dāng)參數(shù)太大時，算法會過度探索，從而浪費(fèi)了一些增加點(diǎn)擊次數(shù)的機(jī)會。從圖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ù)組合下所得到的相對點(diǎn)擊率結(jié)果。其中 α為平衡探索利用程度的參數(shù)，線性核具體表示為

k(x,x′)=xTx′

多項式核具體表示為

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

高斯核具體表示為

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

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

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

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

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

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

4 結(jié)束語

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