以多臂賭博機建模的多目標互動式推薦系統

何煒俊，艾丹祥

(廣東工業大學 管理學院，廣州 510520)

E-mail ：china072547@vip.qq.com

1 引 言

推薦系統(Recommender Systems，RS)通過分析用戶記錄(User Profile)和商品屬性(Item Attribute)的關系，達到過濾冗余內容的目的，能有效應對信息過載問題.眾所周知，基于近鄰的協同過濾(Neighborhood-based Collaborative Filtering，CF)是最常見的推薦技術.該技術有兩種類型：基于用戶的方法(UserCF)和基于商品的方法(ItemCF).其核心都是根據歷史交易記錄尋找相似的用戶或商品.CF假設：用戶興趣和商品屬性都是相對靜止的.比如，用戶過去喜歡什么，將來也喜歡什么；歌曲過去很流行，將來也很流行.該假設限制了以CF為基礎的推薦模型在現實生活的高效應用：無法長期地準確匹配用戶需求和商品屬性.

在此背景下，以多臂賭博機(Multi-armed Bandits，MAB)建模的互動式推薦系統應運而生[1].MAB推薦具有以下幾個特點：1)連續互動，即用戶對推薦結果產生反饋，而系統根據反饋信息實時改進預測策略(比如，發現新興趣).此過程周而復始；2)隱式互動，即用戶很少會直接對商品評分，取而代之的是點擊、購買或訂閱等隱式行為；3)稀疏互動，即大多數用戶都不會頻繁地與系統進行互動，因此推薦次數是有限的.MAB是強化學習的經典范例，屬于開發-探索(Exploitation & Exploration，EE)策略.開發(Exploitation)是利用現有反饋信息，從已知商品中選擇期望收益最高的進行推薦；探索(Exploration)是不依賴現有反饋信息，去發現期望收益更高的未知(新)商品.然而開發和探索是相互沖突的，過度的開發會陷入局部最優解，過度的探索則會浪費有限的推薦機會.因此只有權衡開發和探索，才能獲得長期的最佳推薦效果.

現有的MAB推薦算法能有效地應對在線場景下的動態推薦問題.然而，這類研究大多以改進推薦準確性(Accuracy)為首要目標.“以預測精度為中心”的推薦模型往往會犧牲推薦結果的多樣性(Diversity)和新穎性(Novelty)[2]，Adomavicius通過定量實驗表明，過度地改進預測精度會大幅度地降低推薦多樣性和新穎性[16].這種推薦系統從越來越狹窄的范圍內挑選商品(如熱門商品)，使推薦結果的信息效用降低，很難給用戶營造新鮮的體驗感[3]，甚至還會使用戶感到厭煩[4].相反，較高的多樣性和新穎性的推薦結果能有效地提升用戶的體驗滿意度和忠誠度[5]，增加商品銷售額和銷售種類[6]，還能避免推薦系統產生過度專門化(Overspecialized)問題[7].因此，多樣性和新穎性同樣應該作為有效推薦的目標[8].

圖1 “用戶-系統”互動式推薦過程Fig.1 Interactive recommendations of users and systems

針對上述問題，本文提出一種基于MAB的多目標互動式推薦系統，旨在產生兼顧準確性、多樣性和新穎性的商品推薦列表.該推薦系統的互動推薦過程如圖1所示.首先，構建考慮推薦準確度、多樣度和新穎度的標量函數，以此挑選若干個加權期望收益較高的候選商品組成推薦列表，展示給目標用戶.之后，用戶對推薦列表做出反饋(如點擊、購買或訂閱等)，系統則根據反饋信息更新多目標推薦模型，并為用戶產生新的推薦列表.“用戶-系統”的互動式推薦過程不斷循環，使系統能夠及時適應用戶興趣和物品屬性的變化，提供兼顧準確性、多樣性和新穎性的推薦服務.

2 相關研究

2.1 多目標推薦研究

將多目標決策分析(Multiple Objective Decision Making，MODM)方法應用于推薦系統是有價值的，詳細表述參見文獻[9].厙向陽等提出一種多目標的混合推薦系統，并行混合了7種子推薦算法，再用遺傳算法挑選加權準確度、多樣度和新穎度較優的商品[10]；Chai通過結合Pareto最優法和Promethee多準則決策法，提出一種多目標免疫優化推薦算法，旨在產生準確、多樣和新穎的結果[11]；Cai提出基于適應性評估(GBFE)和分割知識挖掘(PBKM)策略的多目標推薦算法(MaOEAs)，旨在提升推薦精確率、召回率、覆蓋率、多樣度和新穎度[12]；等等.

然而，上述研究成果構建的多目標推薦系統均不具有實時性，其模型和數據源都是離線的(在推薦之前建立)，無法及時接收用戶的反饋，無法適應用戶興趣和商品屬性的動態變化.

2.2 基于多臂賭博機的推薦研究

基于MAB的推薦系統被廣泛應用于現實生活中在線或上下文敏感的推薦平臺，如電商Amazon、新聞Google News和流媒體YouTube等等.基于此，MAB推薦自然也受到眾多學者的關注.比如，成石等提出融合矩陣分解和MAB的推薦系統，分析商品實際評分和預測評分的偏差，以矩陣分解技術求得用戶和商品的屬性，并對上述的屬性使用MAB完成推薦[13]；王高智等提出基于內容和協同過濾的MAB推薦系統，綜合考慮內容和用戶相似度，結合最近鄰算法，以用戶和近鄰用戶的反饋信息進行MAB推薦[14]；Wang等提出結合MAB的互動式協同過濾推薦算法，先在離線情況下使用潛在狄利克雷(LDA)主題技術為商品聚類，然后在MAB推薦中使用粒子學習(Particle Learning)技術改進商品相似度的計算方式，使在線推薦結果更準確[15]；等等.

然而上述MBA推薦系統也存在一些缺陷，包括：1) 只關注改進推薦的準確性指標(如精確率、召回率和平均絕對誤差等)，卻未提及其他重要推薦指標(如多樣度和新穎度等)；2) 在一次推薦中，一個MAB只能動態推薦一個商品，也只能收集一個反饋信息.在現實中，用戶更愿意看到由多個推薦商品組成的推薦列表.在此背景下，Radlinski提出由多個MAB并列而成的排列多臂賭博機算法(Ranked bandits，RB)[16].

基于RB的推薦系統能夠同時推薦多個商品和接收多個反饋信息，尤其適合于網頁排序和推薦.Slivkins等發現在文本推薦中，用戶經常找不到適合自己的答案，為此整合兩大MAB模型(Ranked bandits和Lipschitz Bandits)以提高推薦文本的準確度[17].Louёdec等也發表了類似的研究成果，在一次推薦中，RB忽略了列表位置的相關性(不同位置賭博機挑選物品的過程是獨立的)，據此提出Multiple-play Bandits(MPB)推薦算法以提升推薦列表的預測準確性[18].當前的RB推薦研究同樣存在過度追求預測精度而忽視了其他重要推薦指標的不足.

綜上，本文立足于現有的MAB(包括RB)互動式推薦研究，參考已有的多目標離線推薦研究，提出一種多目標的互動式推薦系統.

3 基于多臂賭博機建立互動式推薦框架

互動式推薦模型的常見構建方法是MAB算法.在MAB推薦模型中，賭博機的m個手臂依序對應m個候選商品.區別于注重一次性收益最大化的離線推薦，MAB互動式推薦注重長期推薦的累積收益最大化.在第t次推薦中，系統以某種策略為用戶挑選商品.該商品被推薦完之后，會獲得服從某種固定概率分布的收益值(Reward).收益值可以是用戶對所推薦商品的反饋，同時也是系統對該商品獲得的獎勵/懲罰(將影響以后系統挑選該物品的概率).簡單地，若用戶點擊該商品，則收益為1；若用戶沒有點擊，則收益值為0.由于用戶興趣和物品屬性會隨時間改變，使得每個候選商品的期望收益也是動態變化的.系統需要優化推薦策略，以使長期累積收益最大化(或遺憾最小化).

每個商品的期望收益都具備3個特征[19]：1)隨機性(Stochastic)：每個商品的期望收益都是一個服從某種固定概率分布的隨機變量.不同商品的概率分布可以不同，分布形態和具體參數可以未知；2)對抗性(Adversarial)：每種商品的期望收益可以動態改變，但是所有商品的期望收益不能同時取零；3)馬爾科夫性(Markovian)：商品的期望收益變化過程是一個馬爾科夫過程.

系統挑選商品時，既要兼顧開發，也要兼顧探索，既推薦已知商品，也勘探未知(新)商品.常見的權衡開發-探索策略包括[20]：隨機法、ε-Greedy、Softmax、Upper Confidence Bound(UCB)、BayesUCB、LogUCB、LinUSB 和Thompson Sampling(TS)等.本文使用ε-Greedy方法.

基于ε-Greedy的推薦策略如下：以ε的概率探索，隨機挑選商品；或以(1-ε)的概率開發，挑選期望遺憾值最低的商品.在第t次推薦，假設最高收益值為rmax，商品i的期望收益為ri(t)，則選取i的遺憾值為[rmax-ri(t)].系統的目標是在推薦總次數T內，使累積遺憾值LT最低.

(1)

算法1展示了基于多臂賭博機的互動式推薦算法.第t次推薦將承接第(t-1)次更新得到的MAB模型.圖2為其運作過程.

基于MAB的推薦模型僅使用一臺賭博機A1，所以在一個推薦流程中，只可以推薦一個商品i(t)，也只能收集一個商品的反饋信息.但在很多實際應用中，系統常常需要為用戶展示由k個商品組成的推薦列表，并能收集多個商品的反饋信息，由此發展出由多個MAB排列組成的排列(多臂)賭博機算法：在商品列表P={p1，p2，…，pk}中，賭博機Aj挑選位置為j(1≤j≤k)的推薦商品pj.

算法1.基于多臂賭博機的互動式推薦算法

輸入：一種模型A1；目標用戶u；候選商品Im

輸出：單個推薦商品i(t)

1.重復推薦t=1，2，…，T

2. 基于ε-Greedy的推薦策略挑選商品i(t)

3. 為u展示推薦i(t)，并記錄反饋：

4. 若u點擊i(t)，令rt=1；否則，令rt=0

5. 更新模型：Update MAB(u(t)，i(t)，rt，A1)

6.返回步驟2，直到完成T次推薦

圖2 基于多臂賭博機的“用戶—系統”互動式推薦流程Fig.2 Interactive recommendations between users and systems based on MAB

算法2展示了基于排列賭博機的互動式推薦算法.類似地，第t次推薦將承接第(t-1)次更新得到的RB模型.圖3為其運作過程.需要說明的是，在實際應用中用戶大多以從前到后的順序瀏覽商品列表，因此規定：當u點擊列表位置為j的商品pj時，獎勵賭博機Aj，即rjt=1.此外，位置在j之前的賭博機(A1，A2，…，Aj-1)都沒有獎勵，即rgt=0(g

算法2.基于排列賭博機的互動式推薦算法

輸入：k個賭博機A={A1，A2，…，Ak}；目標用戶u；候選商品Im

輸出：商品推薦列表P={p1，p2，…，pk}

1.重復推薦t=1，2，…，T

2. 重復j=1，2，…，k： #賭博機Aj依序挑選列表位置為j的商品；

3. 基于ε-Greedy的推薦策略挑選商品ij(t)

4. 當j>1，#判斷當前位置商品是否在靠前位置已經被推薦了(避免同一商品被重復推薦)

5. 若ij(t)∈{i1(t)，i2(t)，…，ij-1(t)}，

6.pj←挑選遺憾值次之且未被推薦的商品

7. 否則，pj←ij(t)

8. 為u展示列表P={p1，p2，…，pk}，并記錄反饋：

9. 若u點擊pj且pj==ij(t)，令rjt=1；否則，令rjt=0

10. 更新模型：Update RB(u(t)，ij(t)，rjt，A)

11. 返回步驟2，直到完成T次推薦

上述MAB(包括RB)推薦模型挑選商品的策略只考慮了預測準確性，即盡量使推薦商品被用戶點擊，而沒有考慮推薦多樣性和新穎性，下文將以此為基礎，在推薦商品過程中同時考慮多個目標：準確性、多樣性和新穎性.

圖3 基于排列賭博機的“用戶—系統”互動式推薦流程Fig.3 Interactive recommendations between users and systems based on RB

4 基于多臂賭博機的多目標互動式推薦方法

4.1 多目標函數

本方法采用標量函數(Scalarization Functions)將原多目標規劃轉化為單目標規劃問題.基于理想點法構建標量函數，以挑選出加權遺憾值最低的商品.假設所有候選商品在樣本空間內，以遺憾值高低進行排序是有意義的[21].本函數挑選的商品能夠達到帕累托最優，即不存在其他替代商品，能夠改善其中的一個目標卻不犧牲任何其他目標.

標量函數的構建過程如下：

先計算Q個目標的理想點(最高收益值)：

(2)

再計算每個商品ij的遺憾值(實際收益與最高收益的偏差)，以歐氏距離法加權求和，得到標量函數：

(3)

(4)

算法3展示了Aj為列表位置j挑選推薦商品pj的策略.

算法3.挑選商品的策略(多目標)

輸出：推薦商品pj

1.初始化：商品挑選函數SelectItem；商品遺憾數組ItemRegret[ ]

3. 重復i=1，2，…，m，#遍歷所有商品

5. OptimalItem←argmin(ItemRegret[])

6. 返回 OptimalItem }

4.2 推薦指標的計算方法

4.2.1 商品準確度

在第t次推薦過程中，將以商品ij在之前(t-1)次推薦過程的平均點擊通過率(Click-Through Rate，CTR)作為其準確度分數：

(5)

其中，rd(ij)為第d次推薦中ij的實際收益值(若被點擊，取1；否則，取0).例如，在u的前10次推薦服務中，若ij被點擊2次，則再在第11次推薦中，ij的準確度分數為0.2.

4.2.2 商品多樣度

這里的商品多樣度分數是指ij在集合S中的多樣度，記為div(ij|S)，用于衡量ij和S所包含商品的差異性.多樣度的計算方法借鑒文獻[23]：

(6)

(7)

其中，S為第j個位置之前的推薦商品組成的新集合；dis(ij，il)為商品ij和il的余弦距離(aq和bq為ij和il的商品屬性值，如評分、流行度等).若S為空(如j=1時)，則令div(ij|S)=1.例如，在A4挑選第4個位置的推薦商品時，S為前3個位置商品組成的集合{i1，i2，i3}，ij和i1、i2、i3的距離分別為0.90、0.91和0.92，因此div(ij|S)=0.91.

4.2.3 商品新穎度

借鑒文獻[23]的方法計算商品新穎度.對于ij，先計算其流行度pol(ij)：

(8)

其中，sel(ij)為之前的推薦過程中A挑選ij的次數.例如，有5個商品，在前10次推薦中(單次推薦兩個商品)，分別被挑選了8次、6次、2次、2次和2次.到了第11次，這5個商品的流行度分別為0.4、0.3、0.1、0.1和0.1.

對pol(ij)取對數，則新穎度分數為：

nov(ij)=-log2pol(ij)

(9)

值得注意的是，所有商品的準確度、多樣度和新穎度分數計算完成之后，都務必進行標準化處理(本方法采用Z-Score標準化)，再由分數值構成期望收益矩陣Sm*Q，其中m為商品數，Q為目標數.例如，s11，s12，s13分別為第一個候選商品的準確度、多樣度和新穎度分數.

從上述計算過程可知，一個商品如果在之前被賭博機挑選并被用戶點擊的次數多，則其后續的準確度分數會升高；然而，如果被過多的挑選，又會降低其新穎度分數.對于一些開始過時的熱門商品，容易被賭博機挑選卻不被用戶接受，就會出現準確度和新穎度分數同時下降的情形.另外，當新商品與原列表中商品的差異性較大時，則更容易被選中.這將有效避免推薦列表出現“千篇一律”的不良后果.

4.3 模型更新策略

分析狀態空間模型(State Space Model)的線性系統：

(10)

(11)

(12)

(13)

算法4.權重更新策略

值得注意的是，系統會為每個用戶存儲其獨有的權重向量(個性化的體現).對于一個特定用戶，隨著用戶與系統互動次數的增多，推薦結果越來越能夠滿足其需求.對于新用戶，系統會更注重預測準確度，旨在與用戶建立信任關系；而對于老用戶，系統會更注重多樣度和新穎度，旨在拓寬用戶視野，帶來新鮮和驚奇感，從而提升用戶體驗滿意度和忠誠度.

4.4 算法描述

算法5.基于多臂賭博機的多目標互動式推薦算法

輸出：商品推薦列表P={p1，p2，…，pk}

1.重復推薦t=1，2，…，T

2.計算商品期望收益SM*P#第4.2節

3. 依序用第j個賭博機Aj挑選列表位置為j的商品；重復j=1，2，…，k

5. 或以ε的概率探索：隨機選擇ij(t)}

6. 當j>1， #避免同一商品被重復推薦

7. 若ij(t)∈{i1(t)，i2(t)，…，ij-1(t)}，

8.pj←挑選遺憾值次之且未被推薦的商品

9. 否則，pj←ij(t)

10. 為u展示列表P={p1，p2，…，pk}，并記錄反饋：

11. 若u點擊pj且pj==ij(t)，令rjt=1；否則，令rjt=0

14.返回步驟2，直到完成T次推薦

圖4 基于多臂賭博機的多目標互動式推薦流程Fig.4 Multi-objective interactive recommendations between users and systems based on MAB

5 實驗驗證

為驗證本研究所提出的互動式推薦系統的有效性，將采用標有時間戳的離線數據進行在線模擬實驗.

5.1 數據集與評估指標

本實驗將在Hetrec2011-LastFM-2k數據集上進行，該數據為來自英國網絡電臺和音樂社區網站的真實數據，記錄用戶收聽音樂的信息，包含有1，892個用戶和17，632個商品(音樂家)，其中“用戶-商品選擇關系”占比(非零元素比例)為0.05%.

為了提升推薦效率，需要選取互動實驗之前的部分歷史數據進行預處理，為每個用戶存儲適當大小的候選商品Im.采用基于用戶的協同過濾算法[20]進行Top-N過濾，只有排名前100的商品才可進入互動式環節.

模擬Last.FM網站中的用戶—系統互動過程：在當次推薦t，用戶點擊展示的音樂家，系統根據用戶反饋改進下次推薦(t-1)的推薦模型(算法5).在預處理時間點后的數據，只有427個用戶有超過40次的元組<用戶，音樂家>.為這里的427個用戶分別模擬40次互動式推薦實驗.

將推薦實驗獲得的含有多個商品的推薦列表作為評估對象，從準確度、多樣度和新穎度3個方面構建推薦效果的評估指標.

受限于實驗數據的數據結構，在一個時間戳中，用戶只選擇推薦列表R中的一個商品.因此，在當次推薦中，只要用戶點擊R，則視R為推薦成功.區別于離線推薦，在線推薦最常用的準確度評估方法是點擊率，即平均CTR(R)：

(14)

其中，rd(R)為在第d次推薦中，用戶對R的反饋(點擊，取1；否則，取0).

列表多樣度div(R)：

(15)

其中，d(ij，il)為商品ij和il的距離，見式(6).

列表新穎度nov(R)：

(16)

其中，sel(i)為在過去，商品i被點擊的次數.

5.2 對比模型

將本方法模型和現有的部分經典MAB推薦方法模型的推薦效果進行對比：

1) 排列多臂賭博機模型(RB[16])：由多個MAB并列而成的列表推薦算法(算法2)，該模型只關注推薦的準確性.

2) 上邊界多臂賭博機模型(UCB[25])：從置信區間的角度權衡“開發-探索”，無需人為設定探索參數.一個UCB只能推薦一個商品，因此參考RB的設計思路，并列多個UCB才能產生商品推薦列表.該模型只關注推薦得準確性.

3) 本方法模型(MOMAB)：探索參數ε取0.2時[26]，能夠較好地權衡“開發-探索”沖突.

4) 固定權重模型：為了驗證MOMAB模型權重更新策略的有效性，構建固定權重的參照模型，即保持標量函數中的權重一直不變(去除算法4)，除此之外的其他操作與MOMAB模型完全相同.根據權重選取的不同，可分為：

5.3 結果分析

本方法模型MOMAB與RB模型、UCB模型和固定權重模型的推薦效果評估對比如圖5、圖6、圖7所示.

圖5、圖6和圖7分別為在40次的“用戶-系統”互動推薦中(T=40)，各模型的推薦列表(商品數k=5)在準確度、多樣度和新穎度指標的表現情況.按照由優到劣的順序，準確度的表現為：UCB、MOMAB、RB、M2、M1、M3和M4；多樣度的表現為：M3、M4、MOMAB、M1、M2、RB和UCB；新穎度的表現為：M4、MOMAB、M3、M1、M2、RB和UCB.

6 結束語

針對許多現有推薦技術面臨的兩大挑戰(缺乏實時性；缺乏多樣性和新穎性)，本文提出一種以多臂賭博機建模的多目標互動式推薦系統.其主要創新點為：1)多目標推薦.采用理想點法構建多目標規劃模型，并將其轉換成單目標規劃問題，同時優化推薦準確性、多樣性和新穎性；2)具有實時性.實際應用中，“用戶興趣是變化的”、“潮流是變化的”“商品是有生命周期的”、“季節效應”等時間效應因素，影響著用戶對推薦商品的體驗滿意度.本方法參考卡爾曼濾波器，給出權重迭代策略，能根據用戶的反饋，優化各目標權重，實時調整推薦策略，適應用戶不斷變化的需求(用戶獨一無二的反饋信息決定了推薦的個性化).

關于未來的研究方向：1)同時優化更多的重要推薦指標，比如：覆蓋率、驚喜性和效用性.在現實中，合理又綜合地評估推薦系統優劣是困難的.許多推薦目標是對立沖突的，但又是至關重要的；2)考慮推薦列表不同位置的影響.顯然，在一個界面中，相對于靠后顯示的推薦商品，靠前顯示的往往更容易被用戶點擊.所以，靠前的位置可以適當增加多樣性和新穎性的權重；3)更進一步MAB的開發-探索沖突.如前所述，只有同時兼顧開發和探索的推薦方案，才能在強化學習過程中實現長期的累計收益最大化.本研究僅嘗試了較為簡單的ε-Greedy方法.事實上，還可以更多地嘗試更先進的權衡EE方法(見第3節).