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

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

（1.山西大學 計算機與信息技術學院，山西 太原 030006;2.山西大學 計算智能與中文信息處理教育部重點實驗室，山西 太原 030006）

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

現實生活中存在著快速變化的推薦環境，其內容領域每時每刻都在發生著變化，內容的流行程度隨著時間而變化，大量沒有任何歷史記錄的新用戶也不斷進入推薦系統。在這種場景下推薦系統必須能夠快速獲得用戶的興趣偏好，才能更好地為用戶提供個性化服務。快速獲得用戶興趣信息和短期內用戶體驗是競爭關系，一方面需要關注能夠提高用戶興趣的內容，另一方面也需要探索新內容以全面改善用戶體驗，這就產生了探索-利用困境(exploration-exploitation dilemma，EE)[6]。為了實現用戶的長期體驗，必須平衡探索和利用的矛盾。

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

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

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

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

1 背景模型

1.1 上下文多臂賭博機

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

1）觀察當前上下文信息x。上下文總結了當前的環境，如日期、天氣、用戶等影響做出選擇的信息。

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

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

多臂賭博機最大化總收益的優化目標可以等價替換為更常用的累積遺憾，表示為

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

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

1.2 LinUCB 算法

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

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

Xa是關于內容a的上下文特征的構造矩陣，每一行表示一個上下文xt,a,一共m行，定義如下:

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

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

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

2)計算預測收益的置信區間。根據文獻[22]可知，在線性條件下有

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

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

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

LinUCB 本質上是一種基于線性收益的上下文多臂賭博機，但是在現實的網絡服務中獲取到的數據往往并不是線性關系，所以導致LinUCB算法應用于個性化推薦預測準確率不高。

2 K-UCB 算法

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

2.1 算法設計

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

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

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

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

而K則為m個上下文特征構成的核矩陣:

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

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

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

需要將式(7)變為核函數的形式，利用Sherman-Morrison-Woodbury 公式,Sherman-Morrison-Woodbury 公式描述如下:A∈Rn×n為 R域上非奇異矩陣，U,V∈Rn×k，若A+UVT非奇異，則有

式(8)提供了將式(7)變為核函數形式的一種途徑，使式(8)中A=Id,U=,V=Xφ，那么有

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

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

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

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

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

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

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

2.2 算法流程

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

3 實驗與結果

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

3.1 算法對比

1）Random：隨機策略總是以相等的概率選擇一個內容。這個算法不需要參數，也不會隨著時間學習。在本文中隨機策略用來衡量其他算法的提升。

2）ε-greedy[12]：該算法統計每個內容的收益，以 ε概率隨機選擇候選內容，以1?ε概率選擇收益最高的內容。參數 ε控制探索程度。

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

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

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

3.2 合成數據集

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

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

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

3.3 Yahoo News 數據集

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

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

表1 雅虎新聞數據集Table 1 Yahoo! News dataset

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

推薦系統通常在小部分流量中學習，然后將學習到的知識應用到其余的大部分流量中，所以本實驗將數據分為學習桶和部署桶進行，學習桶分配20%的隨機流量數據，部署桶分配80%的隨機流量數據。數據更多的部署桶模擬真實的部署環境，其點擊率數據更為重要，但學習桶中點擊率高意味著學習效率更快，所以實驗給出了兩個桶中的點擊率數據。

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

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

如圖2 所示，3 個算法在學習桶和部署桶都是大致中間高兩邊低。這是因為當參數ε或者α過小時，沒有足夠的探索，算法無法識別出好的文章，導致點擊量較少。另一方面，當參數太大時，算法會過度探索，從而浪費了一些增加點擊次數的機會。從圖2 中可以看到，ε-greedy、UCB1和LinUCB 的最佳參數分別為0.2、0.1 和0.3。

圖2 算法在不同參數下的點擊率提升倍數Fig.2 CTR lift of the algorithms under different parameters

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

k(x,x′)=xTx′

多項式核具體表示為

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

高斯核具體表示為

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

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

表2 核函數選擇Table 2 Kernel function selection

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

表3 學習桶中網格搜索K-UCB 參數結果Table 3 Grid search results of K-UCB in Learning Bucket

表4 部署桶中網格搜索K-UCB 參數結果Table 4 Grid search results of K-UCB in Deploying Bucket

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

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

3)對比不同算法在最佳參數下的點擊率。如圖3 和圖4 分別為學習桶和部署桶中各個對比算法的點擊率隨迭代輪次的變化曲線。

圖3 算法在學習桶中的點擊率Fig.3 CTRs of various algorithms in Learning Bucket

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

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

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

4 結束語

本文提出了一種LinUCB 改進算法K-UCB，通過核方法將非線性問題轉化為線性問題。在合成數據集上驗證了K-UCB 可以有效降低非線性環境下的累積遺憾，在雅虎新聞數據集上相比于基于線性收益的LinUCB 算法，點擊率最高提升了8%。將線性收益假設轉變為更一般的收益假設，可以提高上下文多臂賭博機的推薦準確率。多臂賭博機適應動態推薦環境的特性，可以改善傳統推薦算法，這也是未來可以進一步研究的方向。