基于上下文感知的湯普森采樣推薦算法研究

鄭操

（四川大學計算機學院，成都610065）

0 引言

伴隨著互聯網不斷的發展，普通用戶可以接觸到的信息產生了翻天覆地的變化，人們可以通過不同渠道獲取大量的信息，隨著數據量的日益增長，我們已經不再僅僅關注基本需求的滿足，而是更加注重個性化需求。同樣，在推薦系統中如何更好的在用戶和信息之間扮演好橋梁作用也變得越來越重要，人與人之間存在很多個體性的差異，人們對于同一個事物的口味和偏好也往往不同，在這其中，個性化推薦就起到了十分重要的作用。

個性化推薦中，十分重要的一點在于如何發掘用戶和信息之間的聯系，或者說如何發掘用戶的興趣和偏好，由此我們需要一種策略來對用戶的興趣和偏好進行學習，通過用戶的行為對用戶的特征進行擬合，在推薦系統中常常采用探索與利用框架來描述這一問題，我們既需要通過對用戶已知的歷史行為來向用戶進行推薦，又需要嘗試新的方式，探索用戶可能存在的潛在偏好。例如某個用戶喜歡牛奶和茶，在用戶的歷史行為中發現存在用戶購買牛奶的信息，于是我們可以利用這個歷史行為給用戶進行推薦，但由于沒有購買茶的歷史行為，因此無法利用已有的經驗向用戶推薦茶，所以有時候也需要跳出用戶的歷史行為，探索用戶潛在的興趣和偏好。

1 算法模型

對于某一個用戶，系統存在若干類物品可以推薦，用戶對這些物品的偏好是不同的，每類物品都有相對應的上下文信息，用戶的偏好未知，現在需要制定一個策略使得在一定輪次的推薦內，用戶的滿意度越高越好。對于這個問題，本文采用了Bandit 算法框架，并且利用上下文信息以及湯普森采樣以及粒子學習來選取每一輪實驗所推薦的物品，用正態高斯函數來擬合用戶的特征，然后觀察每一輪實驗的結果，用戶對本輪推薦的滿意程度，通過不斷的實驗對正態高斯函數的參數進行迭代訓練，使得其能更好地表示用戶的特征信息，從而使得推薦的效果隨著實驗次數增加越來越好。

本文通過概率分布采樣的方式來表現不確定性，a*()t 代表第t 輪實驗中回報期望最高的那一項，μ代表用戶的采樣信息，利用回報期望最高項進行推薦，觀察實際的真實回報ra(t)。然后對用戶特征的高斯函數參數進行更新：

本文還采用了粒子學習（Particle Learning），即一個用戶的特征由多個粒子來表示，每個粒子都有各自的參數，用來儲存用戶的特征以及狀態信息，每次會從粒子中選擇回報期望最高的那組粒子代表用戶的特征參數，并從該粒子對應的正態高斯分布中進行采樣。

為了對不同算法的有效性進行評價，本文采用了探索與利用問題中最常用累積遺憾（Accumulated Re?gret）和累積回報作為評價指標，首先我們先定義在一個時間輪次上的遺憾R(t)：

其中ra*(t)表示在本輪實驗中可能取得的最高回報。我們將所有輪次的遺憾累積起來就可以得到累積遺憾的定義：

如果在一個輪次的實驗中實際產生的回報和最大可能的回報越接近，那么這個輪次的遺憾就會越小，所以遺憾越小就能表示用戶的滿意度越高，推薦的效果越好，于是我們的目標就是使得算法模型所產生的累積遺憾盡可能越小越好，或者累積回報越大越好。

2 對比模型

LinUCB[1]是一種基于置信區間上界（Upper Confi?dence Bound）的算法，傳統的UCB 算法一般都沒有考慮到推薦情境中的上下文信息，忽略了待推薦事物本身蘊含的各種特征信息，這樣就會導致在實驗早期輪次的回報較低，算法的收斂速度慢，而LinUCB 是在UCB 算法的基礎上加入了上下文信息，考慮到了不同用戶在在不同情境下對事物的接受程度可能不同，所以可以加快系統參數學習的速率，非常適合個性化推薦。

PTS[2]是基于湯普森采樣的一種算法，它的特點是利用正態分布來擬合事物和用戶的特征信息，在每一輪實驗中分別進行采樣，將采樣得到的特征向量作為本輪實驗的事物特征和用戶特征，由于采樣本身就是一個隨機的過程，所以是通過采樣的方式實現探索與利用的平衡。

還有一種通過矩陣分解的算法UCB-PMF[3]，這種算法是通過對UCB 算法進行了改進，假設每輪實驗的回報可以通過正態分布進行擬合，利用這個分布的參數進行調節。

3 實驗

本文實驗的數據來自HetRec 國際推薦系統信息異質性與融合研討會上發布的公開數據集Delicious 和LastFM，Delicious 數據集記錄的是用戶在該網站上收藏的書簽以及相應的標記信息，LastFM 數據集則是用戶收聽音樂家、歌手的相關記錄，以及一些好友關系等信息。我們會對這兩個數據集進行數據預處理，提取出對應的特征向量并且保留前25 個主要的特征。我們設定在一次實驗中，利用LastFM 數據集給用戶進行推薦，如果用戶曾經收聽過這個音樂家的作品，那么本次實驗回報為1，否則為0。同樣在Delicious 數據集中，如果用戶收藏過對應的網址，那么回報為1，否則為0。

實驗采用的是一種在線學習的方法，每一次實驗都會迭代算法的參數，使得算法參數能更好地擬合用戶的歷史行為，觀察每次實驗的回報，計算累積遺憾，通過和對比算法進行實驗結果的比較來分析模型的有效性。圖1-2 分別為Delicious 數據集和LastFM 數據集對應累積回報實驗對比結果。

圖1 Delicious數據集實驗輪次和累積回報關系圖

圖2 LastFM數據集實驗輪次和累積回報關系圖

我們從圖中可以得出TSbaseContext 算法的累積回報無論是在Delicious 數據集還是LastFM 數據集上都是最高的，這說明利用上下文信息和湯普森采樣以及加入粒子學習可以有效地提升推薦算法的有效性，能更快地訓練模型參數，對于其他的算法而言，LinUCB算法表現僅次于TSbaseContext 算法，因為LinUCB 算法也考慮到了上下文特征，但由于參數學習沒有TS?baseContext 算法快，導致在初期的實驗輪次，TSbaseC?ontext 算法的累積遺憾一直低于LinUCB，另外兩個模型雖然考慮到了特征因素，但是沒有利用到上下文信息的影響。本文的采用的模型不僅利用采樣以及粒子學習的方式擬合用戶的特征信息，還充分考慮到了場景中物品的上下文信息，在這兩者基礎上構建的模型可以比較好地在探索和利用之間找到一個合適的平衡點，使得算法具有比較好的性能。

4 結語

本文采用了上下文特征和湯普森采樣以及粒子學習構建的推薦算法模型，在兩個真實數據集Delicious和LastFM 上進行了有效性驗證，并且根據累積回報作為算法性能的評價指標和其他幾個對比算法進行了比較分析，實驗結果表明該模型可以比較好地擬合用戶的偏好，提高推薦的效率。