MOOB：一種改進(jìn)的基于Bandit模型的推薦算法

帖　軍，孫榮苑，孫　翀，鄭　祿

(中南民族大學(xué) 計算機(jī)科學(xué)學(xué)院，武漢市430074)

目前，向用戶呈現(xiàn)個性化內(nèi)容是在線推薦服務(wù)的關(guān)鍵功能之一.在線推薦服務(wù)通常實時收集用戶的反饋來探索未知信息，以評估新內(nèi)容受歡迎程度，同時監(jiān)控其權(quán)重的變化.直觀地說，系統(tǒng)需要將更多流量分發(fā)給新內(nèi)容，以便更快地了解其價值，減少現(xiàn)有內(nèi)容的流量跟蹤.在此基礎(chǔ)上，Bandit模型被廣泛應(yīng)用于推薦系統(tǒng)，逐漸成為推薦領(lǐng)域的研究熱點.

Bandit模型，即多臂老虎機(jī)模型是一個序列化決策問題[1].每一輪游戲玩家從m個臂中選擇一個，并得到相應(yīng)的回報.玩家的目標(biāo)是n輪游戲后回報值最大化.

在實際的推薦系統(tǒng)中容易出現(xiàn)長尾現(xiàn)象，不流行的商品會被埋沒，用戶不易發(fā)現(xiàn)新商品.好的推薦系統(tǒng)不僅能夠準(zhǔn)確預(yù)測用戶的行為，而且能夠擴(kuò)展用戶的視野，幫助用戶發(fā)現(xiàn)被埋沒在長尾中的好商品.Bandit模型雖然能在一定程度上解決此問題，但是Bandit模型將累計遺憾的大小作為衡量算法優(yōu)劣的唯一指標(biāo)，在實驗過程中容易出現(xiàn)過擬合現(xiàn)象.若將Bandit模型應(yīng)用于實踐，單一的衡量指標(biāo)顯然不能避免長尾現(xiàn)象，無法提高推薦系統(tǒng)覆蓋率.

本文圍繞上述問題展開研究，基于多臂老虎機(jī)模型，提出一種既能使系統(tǒng)得到最大回報，又能提高系統(tǒng)覆蓋率的推薦算法.首先，通過用戶的歷史信息預(yù)測出能得到最大回報的物品，然后在推薦物品候選集中進(jìn)行覆蓋率計算，最后得到既能滿足用戶喜好又能拓展用戶興趣的物品.

1　相關(guān)工作

1.1　Bandit模型相關(guān)算法

在計算廣告和推薦系統(tǒng)領(lǐng)域，Bandit問題也稱為EE問題：exploit(開發(fā))-explore(探索)問題.Bandit模型相關(guān)算法根據(jù)已有的回報選擇目前為止回報最高的臂，稱之為開發(fā)；另一方面，這個目前為止回報最高的臂不一定是最優(yōu)臂，算法還需選擇那些可能回報更高的臂，收集它們的信息，稱之為探索，關(guān)鍵是保持開發(fā)和探索的平衡，使累計遺憾達(dá)到最小[2].如今有許多關(guān)于Bandit模型相關(guān)算法的研究：

第一類是ε-greedy算法.首先在(0,1)之間選一個較小的數(shù)ε；每次以概率ε隨機(jī)選擇一個臂，以1-ε的概率選擇估計回報最高的臂.當(dāng)每個臂都被選擇趨近無數(shù)次時，回報的估計值逐漸收斂至真實值.文獻(xiàn)[3]提出一種新的學(xué)習(xí)模型，其中ε與實驗次數(shù)相關(guān).Langford J提出ε-greedy算法是一種上下文有關(guān)的Bandit模型算法，在選擇時需根據(jù)上下文變量進(jìn)行預(yù)估回報值來選擇預(yù)估回報最大的臂[4].Bouneffouf D等人提出一種算法，該算法將移動上下文感知推薦系統(tǒng)(MCRS)建模為上下文有關(guān)的ε-greedy算法[5].

第二類是湯普森采樣算法，該算法假設(shè)每個臂是否產(chǎn)生收益，其背后有一個概率分布，產(chǎn)生收益的概率為p，通過不斷地試驗，估計出一個置信度較高的p的概率分布.Chapelle O和Li L證明了湯普森采樣算法在廣告選擇和新聞推薦領(lǐng)域表現(xiàn)良好[6].湯普森采樣算法中概率分布多采用貝葉斯概率分布，如文獻(xiàn)[7]介紹了一種用于管理多臂老虎機(jī)隨機(jī)概率匹配的啟發(fā)式算法，該算法觀察隨機(jī)匹配的臂，并選擇最佳貝葉斯后驗概率的臂.Kawale J等人提出一種在線矩陣分解推薦算法，該算法在一般湯普森采樣框架上增加基于Rao-Blackwellized粒子過濾器的在線貝葉斯概率分解方法[8].

第三類是置信區(qū)間上界(UCB)算法.UCB算法每次選擇前根據(jù)已有的實驗結(jié)果重新估計每個臂的均值和置信區(qū)間，最后選擇置信區(qū)間上限最大的臂.Li L和Chu W等人假設(shè)一個臂被選擇之后，其獲得的回報與相關(guān)特征向量成線性關(guān)系，并據(jù)此提出LinUCB算法.LinUCB算法是一種典型的基于內(nèi)容的多臂老虎機(jī)模型，認(rèn)為老虎機(jī)的臂以特征向量表示且可被觀察[9].此后，有很多關(guān)于LinUCB算法的研究，例，Bhagat S等人將社交網(wǎng)絡(luò)關(guān)系應(yīng)用于LinUCB算法以此解決推薦系統(tǒng)中出現(xiàn)的“冷啟動”問題[10].Gentile C和 Li S等人將傳統(tǒng)的協(xié)同過濾算法與LinUCB算法相結(jié)合，將用戶和商品進(jìn)行聚類，并根據(jù)每次反饋結(jié)果調(diào)整用戶和商品聚類[11,12].

基于內(nèi)容的Bandit模型是傳統(tǒng)老虎機(jī)問題的變種.該模型認(rèn)為回報與環(huán)境相關(guān)，且將用戶和臂的信息用特征向量表示.下面以個性化新聞推薦為例用基于內(nèi)容的Bandit模型建模，在第t輪時按照以下規(guī)則.

(1)算法觀察當(dāng)前用戶ut和新聞文章集合At及其特征向量xt,a，其中a∈At.特征向量xt,a包含了用戶ut和文章a的信息，稱之為上下文.

(2)根據(jù)以前獲得的反饋，算法選擇一篇文章at∈At推薦給用戶ut，并獲得反饋pt,at，獲得的pt,at是由用戶ut和文章at共同決定.

(3)算法根據(jù)最新得到的反饋，更新下一輪選文章策略.

當(dāng)t輪推薦結(jié)束后計算算法的累計遺憾.算法在選擇物品過程中通過每次的結(jié)果估算回報，在探索的過程中是有損失的，計算算法的損失值即為累計遺憾.累計遺憾也是衡量Bandit模型算法優(yōu)劣的唯一指標(biāo).其計算的方式為每一次實驗的最大回報乘以實驗次數(shù)減去真實回報.上述例子累計遺憾計算公式為：

(1)

1.2　相關(guān)問題

美國雜志主編Chris Anderson在《長尾理論》指出，互聯(lián)網(wǎng)條件下，冷門商品的銷售總額不可忽視，主流商品代表大多數(shù)用戶的需求，長尾商品代表小部分用戶的個性化需求[13].因此，如果通過發(fā)掘長尾提高銷售額，就必須充分研究用戶興趣，這正是個性化推薦系統(tǒng)的關(guān)鍵問題.

社會學(xué)領(lǐng)域存在著名的馬太效應(yīng)，即所謂強(qiáng)者更強(qiáng)，弱者更弱的效應(yīng).如果一個系統(tǒng)擴(kuò)大熱門物品和非熱門物品之間流行度差距，那該系統(tǒng)會產(chǎn)生馬太效應(yīng).推薦系統(tǒng)的初衷是挖掘長尾中的物品.為每個用戶提供個性化推薦，消除馬太效應(yīng)，使得各種物品都能被展示給對它們感興趣的人群.

已有的Bandit模型在對用戶行為進(jìn)行預(yù)測時以累計遺憾大小為唯一指標(biāo)，這樣容易導(dǎo)致用戶只能看到自己目前比較感興趣的產(chǎn)品，用戶可能會感興趣的商品較少呈現(xiàn)給用戶.這樣的推薦系統(tǒng)顯然不能充分挖掘長尾商品，消除馬太效應(yīng)，為避免此情況的出現(xiàn)，需對現(xiàn)有Bandit模型的相關(guān)算法進(jìn)行改進(jìn).

2　算法設(shè)計

本文推薦算法的評價指標(biāo)同時考慮累計遺憾值和物品長尾的發(fā)掘能力.在LinUCB算法的基礎(chǔ)上進(jìn)行改進(jìn)，提出新的推薦算法，并詳細(xì)介紹算法流程.

2.1　問題描述

在1.1節(jié)提到Bandit模型的評價指標(biāo)即累計遺憾值，根據(jù)1.2節(jié)對Bandit模型問題的分析，單一的評價指標(biāo)累計遺憾不能完全衡量算法優(yōu)劣，要改善這種現(xiàn)狀需提出新的評價指標(biāo)，參數(shù)含義如表1所示.

表1　參數(shù)含義

覆蓋率用來描述一個推薦系統(tǒng)對物品長尾的發(fā)掘能力，有不同的定義方法，最簡單的定義為推薦的物品占總物品集合的比例.假設(shè)系統(tǒng)的用戶集合為U，推薦系統(tǒng)給每個用戶推薦一個長度為N的物品列表R(u)?{πu1,…,πut}.推薦系統(tǒng)的覆蓋率可通過下面公式計算：

(2)

覆蓋率為100%的系統(tǒng)可以有無數(shù)的物品流行度分布，如果所有物品都被推薦過，且推薦次數(shù)相近，那么物品流行度均勻，推薦系統(tǒng)挖掘長尾能力強(qiáng).因此可通過研究物品在推薦列表中出現(xiàn)次數(shù)的分布描述推薦系統(tǒng)挖掘長尾的能力，在信息論和經(jīng)濟(jì)學(xué)中有一個著名的指標(biāo)來描述流行度分布，即基尼系數(shù)：

(3)

這里aj是按照物品流行度pop從小到大排序的物品列表中第j個物品.若物品流行度均勻，基尼系數(shù)小，若系統(tǒng)物品流行度分配不均，基尼系數(shù)大.

為達(dá)到推薦系統(tǒng)在保證預(yù)測精準(zhǔn)度的情況下提高對長尾商品的挖掘能力的目的，需算法保證累計遺憾值和基尼系數(shù)達(dá)到最小，即選擇預(yù)測收益最大和基尼系數(shù)最小的物品.用公式(4)和公式(5)表示：

(4)

(5)

2.2　MOOB算法

本文在基于內(nèi)容的Bandit模型的基礎(chǔ)上提出了一種新的多目標(biāo)優(yōu)化Bandit(MOOB)算法，算法流程圖見圖1.MOOB算法假設(shè)預(yù)期估計所獲收益與物品的特征向量呈線性相關(guān)，沿用2.1的參數(shù)，在第t輪為

pt,at=wTa,t-1xa,t.

(6)

(7)

計算得到的pt,at只是一個對所獲收益的估計，估計總是不準(zhǔn)確的，如能給估計誤差一個合理估計，就能控制風(fēng)險.在選擇物品的過程中不僅要選擇預(yù)估收益大的物品，還要選擇預(yù)估誤差范圍大的物品，所以選擇物品的方式為：

(8)

算出所有物品的ka,t值之后，對所有的ka,t由大到小排序，取出前K個物品作為候選集，計算候選集中物品的基尼系數(shù)，最后選擇基尼系數(shù)最小的物品推薦給用戶，并觀察本輪用戶對此物品的評分來更新線性關(guān)系參數(shù)ωa,t.算法1中以偽代碼的形式描述了學(xué)習(xí)算法MOOB.

Algorithm1MOOB(α)Input：α∈R+這個參數(shù)決定開發(fā)的程度；Init：ba=0∈Rd分析變換的向量；Aa，0=I∈Rd×d逆相關(guān)矩陣；a=1，…，m；Output：at推薦給用戶的物品fort=1，2，3，…，Tdo　Setωa，t-1=A-1a，t-1ba，t-1，a=1，…，m；　Receiveat∈V，andgetcontextxa，t　forallat∈VdoIfaisnewthenAa←Idba←0d×1endifwa←A-1abapt，at=wTaxa，t+αxTA-1axlogt+1()　endfor　Selecttheitems，whichcorrespondtothetopKlargervaluesinstep10，toformcandidatesetsN　forallat∈NdoGa，t=1n-1∑nj=12j-n-1()rt-1，a　endfor　Chooseat=argmina∈NGa，t，andobserveareal-valuedpayoffrtAa，t←Aat，t-1+xa，txTa，tba，t←ba，t-1+rtxa，tendfor

算法在每次實驗時需動態(tài)更新Aa,t其所需時間復(fù)雜度為O(d2)，而且算法第12步需要選擇K個預(yù)測回報最大的臂，所以算法在第t次的運算所需時間為O(d2+nlogK).

由算法1中的偽代碼和圖1算法流程圖可知，本文提出的MOOB算法綜合考慮了累計遺憾值和基尼系數(shù).在保證用戶對推薦結(jié)果滿意度的基礎(chǔ)上能有效避免馬太效應(yīng).下面將通過對實驗結(jié)果進(jìn)行分析來驗證算法相關(guān)性能.

圖1　MOOB算法流程圖Fig.1　MOOB algorithm flow chart

3　實驗與分析

3.1　實驗數(shù)據(jù)及環(huán)境

實驗采用YaHoo新聞推薦的數(shù)據(jù)集完成.該數(shù)據(jù)集是由“ICML 2012 Exploration and Exploitation 3 Challenge”提取出來.每個用戶都由一個136維的二進(jìn)制特征向量表示，本文把這個特征向量用來表示用戶的身份.在去除空用戶之后，提取出來8575683條記錄分別對應(yīng)于n=864753個不同的用戶.不同的新聞項目的整體數(shù)量是5425即m=5425.回報值rt的值為0或1，當(dāng)?shù)卿浵到y(tǒng)的用戶在第t輪點擊了某條新聞，則rt=1，若沒有點擊，則rt=0.通過濾除反饋稀疏的用戶，提取出兩個數(shù)據(jù)集一部分作為訓(xùn)練集，一部分作為測試集.在訓(xùn)練集上應(yīng)用用戶興趣模型，在測試集上進(jìn)行預(yù)測；然后使用累計遺憾值及基尼系數(shù)指標(biāo)評測算法在測試集上的預(yù)測結(jié)果.

實驗采用的硬件環(huán)境為Intel(R)Core i5-3470(主頻3.20GHz)，RAM為8GB；實驗采取的仿真工具為python3.5(matplotlib+numpy+scipy).

3.2　評價指標(biāo)

為測試本文算法結(jié)果，選取了三個常用的性能指標(biāo).第一個指標(biāo)是累計遺憾值，累計遺憾可以對比不同Bandit模型算法的效果；對同一多臂問題用不同Bandit模型算法實驗相同次數(shù)，觀察哪種Bandit模型算法遺憾值增長緩慢，具體計算方法見公式(1).第二個指標(biāo)是參數(shù)預(yù)估誤差，訓(xùn)練集的絕對誤差和測試集的訓(xùn)練誤差也是常用的指標(biāo)之一，很多Bandit模型算法追求遺憾值最小，容易造成過擬合現(xiàn)象.通過對比訓(xùn)練集和測試集的誤差來判斷算法的過擬合現(xiàn)象是否嚴(yán)重.第三個指標(biāo)用于衡量推薦結(jié)果是否具有馬太效應(yīng)，這里采用基尼系數(shù)這一指標(biāo)，具體計算方法見公式(3).

3.3　實驗結(jié)果及分析

實驗將MOOB算法和一些最先進(jìn)的LinUCB算法進(jìn)行比較，主要有以下幾種算法：

(1)LinUCB-ONE是UCB算法的單一實例，過去幾年在研究界受到了很多關(guān)注.LinUCB-ONE在所有用戶中分配一個LinUCB的單個實例從而產(chǎn)生對所有用戶的相同預(yù)測；

(2)LinUCB-IND是一組獨立的UCB實例，為每個用戶提供完全個性化的推薦；

(3)LinUCB-V也是UCB的單一實例，但是其約束條件更復(fù)雜.該算法是“ICML 2012 Exploration and Exploitation 3 Challenge”的贏家.

本次實驗抽取40個用戶，1000篇文章作為訓(xùn)練集，所有算法的α取值均為0.2.首先，在圖2中比較了MOOB算法和LinUCB-ONE、LinUCB-IND、LinUCB-V算法在同樣條件下的隨著實驗迭代次數(shù)的增加累計遺憾的變化.

圖2　YaHoo數(shù)據(jù)集上累計遺憾結(jié)果比較圖Fig.2　Comparison of cumulative regret results on the YaHoo data set

由圖2可見，MOOB算法在隨著實驗次數(shù)的增加其累計遺憾值逐漸趨于平穩(wěn).由于MOOB算法在考慮累計遺憾的同時考慮了推薦的多樣性，所以累計遺憾值略高于LinUCB-V和LinUCB-ONE算法.但是對比和LinUCB-IND算法其累計遺憾值有很大優(yōu)化.

圖3　YaHoo數(shù)據(jù)集上參數(shù)預(yù)估誤差結(jié)果比較圖Fig.3　Comparison results of parameter prediction error results on YaHoo data set

由圖3可以看到在相同的實驗條件下，MOOB算法在所有算法中下降最快并且預(yù)估誤差最小.同時可以觀察到LinUCB-V算法雖然在累計遺憾這一指標(biāo)上表現(xiàn)良好，但是它的預(yù)估誤差在四種算法中是最大的，這表示LinUCB-V算法在一定程度上出現(xiàn)了過擬合現(xiàn)象.

圖4　YaHoo數(shù)據(jù)集上基尼系數(shù)結(jié)果比較圖Fig.4　Comparison of Gini Index Results on YaHoo Data Set

由圖4可見四種算法的基尼系數(shù)隨著實驗次數(shù)的增加均呈上升趨勢.MOOB算法在實驗次數(shù)較少時其趨勢跟其他三種算法差別并不明顯，在實驗次數(shù)達(dá)到100之后，其上升趨勢明顯緩于其他算法.此圖也表明：MOOB算法在解決長尾問題上比其他算法更具優(yōu)勢.

4　結(jié)語

本文提出的一種基于Bandit模型的推薦算法MOOB，是對傳統(tǒng)的LinUCB算法進(jìn)行改進(jìn)，使推薦系統(tǒng)的預(yù)測準(zhǔn)確率和覆蓋率都有進(jìn)一步的改進(jìn).通過YaHoo數(shù)據(jù)集的實驗，對所提出算法的性能進(jìn)行了比較和分析.實驗結(jié)果表明：MOOB算法能在用戶滿意度較高的情況下，保證推薦系統(tǒng)物品的流行度較平均，同時有效地避免馬太效應(yīng)，并提高推薦系統(tǒng)對長尾物品的挖掘能力.目前論文沒有對用戶進(jìn)行分類研究，下一步研究工作將根據(jù)用戶的歷史行為進(jìn)行分類，針對不同類別用戶使用不同算法進(jìn)行個性化推薦.

[1]Li L, Chu W, Langford J, et al. Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms[C]// ACM. International Conference on Web Search and Data Mining.HongKong: ACM, 2011:297-306.

[2]Jones P W. Bandit Problems, Sequential Allocation of Experiments[J]. Journal of the Operational Research Society, 1987, 38(8): 773-774.

[3]Bresler G, Chen G H, Shah D. A Latent Source Model for Online Collaborative Filtering[C]//NIPS. Advances in Neural Information Processing Systems. Montreal: NIPS, 2014: 3347-3355.

[4]Langford J, Zhang T. The epoch-greedy algorithm for multi-armed bandits with side information[C]//NIPS. Advances in Neural Information Processing Systems. Vancouver: NIPS, 2008: 817-824.

[5]Bouneffouf D, Bouzeghoub A, Gan?arski A L. Exploration/exploitation trade-off in mobile context-aware recommender systems[C]//IJCAI. Australasian Joint Conference on Artificial Intelligence. Berlin: Springer, 2012: 591-601.

[6]Chapelle O, Li L. An empirical evaluation ofthompson sampling[C]//NIPS. Advances in Neural Information Processing Systems.Granada: NIPS, 2011: 2249-2257.

[7]Scott S L. A modern Bayesian look at the multi‐armed bandit[J]. Applied Stochastic Models in Business and Industry, 2010, 26(6): 639-658.

[8]Kawale J, Bui H H, Kveton B, et al. Efficient Thompson Sampling for Online Matrix-FactorizationRecommendation[C]//NIPS. Advances in Neural Information Processing Systems. Montreal: NIPS, 2015: 1297-1305.

[9]Li L, Chu W, Langford J, et al. A contextual-bandit approach to personalized news article recommendation[C]//ACM.The 19th international conference on World wide web.North Carolina: ACM, 2010: 661-670.

[10]V Caron S, Bhagat S. Mixing bandits: A recipe for improved cold-start recommendations in a social network[C]//ACM. The 7th Workshop on Social Network Mining and Analysis.Chicago: ACM, 2013: 11.

[11]Gentile C, Li S, Zappella G. Online clustering of bandits[C]//ICML. The 31st International Conference on Machine Learning. Beijing: ICML, 2014: 757-765.

[12]Li S, Karatzoglou A, Gentile C. Collaborative filtering bandits[C]//ACM. The 39th International ACM SIGIR conference on Research and Development in Information Retrieval.Pisa: ACM, 2016: 539-548.

[13]Anderson C. The long tail: Why the future of business is selling less of more[M].USA: Hyperion, 2006.