高海賓

（淮南聯(lián)合大學計算機系，安徽淮南232001）

利用Bandit算法解決推薦系統(tǒng)E&E問題

高海賓

（淮南聯(lián)合大學計算機系，安徽淮南232001）

當前推薦系統(tǒng)開發(fā)應用過程中普遍存在著E&E問題，筆者指出了推薦系統(tǒng)中E&E問題的產生和分類，提出用Bandit算法解決這一問題的思路，重點探討B(tài)andit算法的數(shù)學模型和用UCB策略建立的Bandit算法模型，用MATLAB編寫了核心仿真程序，并指出了這種算法模型存在的優(yōu)點和不足.

Bandit算法；推薦系統(tǒng)；E&E問題

在當前在大數(shù)據(jù)時代，信息爆炸式的增長給用戶帶來了大量的信息，滿足了用戶在信息時代對信息的需求，但網(wǎng)上信息量的大幅增長，使得用戶在面對大量信息時無法從中獲得對自己真正有用的那部分信息，對信息的使用效率反而降低了，這就是所謂的信息超載（Information Overload）問題［1］.針對信息超載解決的辦法之一是搜索引擎，具有代表性信息檢索系統(tǒng)有谷歌和百度等，它們在幫助用戶獲取網(wǎng)絡信息方面發(fā)揮著極其重要作用［2］.但使用搜索引擎的用戶在使用同一個關鍵字搜索信息的時候，得到的結果是相同的.一方面信息及其傳播是多樣化的，另一方面用戶對信息的需求是多元化和個性化的，通過以搜索引擎為代表的信息檢索系統(tǒng)獲得的單一結果無法滿足用戶的個性化需求，無法很好的解決信息超載的問題.為了解決這個難題，推薦系統(tǒng)技術的相關研究就應運而生了.與搜索引擎相比,推薦系統(tǒng)通過研究用戶的興趣偏好，進行個性化計算，由系統(tǒng)發(fā)現(xiàn)用戶的興趣點，引導用戶發(fā)現(xiàn)自己的信息需求，根據(jù)用戶的信息需求，將用戶需求的信息、產品等主動的推薦給用戶，提高用戶得到信息的有用率［3］.

一個好的推薦系統(tǒng)不僅能為用戶提供個性化的服務，還能和用戶之間建立密切關系，讓用戶對推薦系統(tǒng)產生依賴.推薦系統(tǒng)算法的好壞能直接決定推薦系統(tǒng)的運行效率和質量，它是推薦系統(tǒng)技術中的核心部分.優(yōu)秀合理的推薦算法模型能夠從海量的用戶行為數(shù)據(jù)中,快速挖掘出用戶的興趣意向，對用戶實現(xiàn)更為精準的產品或信息的推薦,激發(fā)用戶和系統(tǒng)之間的交互行為,最終能夠實現(xiàn)推薦系統(tǒng)的利益最大化.由于推薦系統(tǒng)中普通存在著E&E問題，采用哪種更合理的算法解決是近年來討論的熱點.

1 推薦系統(tǒng)中的E&E問題

1.1 E&E問題的產生

推薦系統(tǒng)的成功與否最直接的衡量標準就是給用戶推薦最想得到的內容，獲得用戶對展示內容的最大點擊收益.每個用戶對不同分類的內容感興趣程度是不同的，那么推薦系統(tǒng)初次見到這個用戶時，怎么快速地知道他對每個分類內容的感興趣程度，從而獲得最大的點擊收益？對于老用戶，推薦系統(tǒng)資源池有若干分類內容，怎么知道該給用戶展示哪個分類，從而獲得最大的點擊收益？顯而易見是展示其點擊效果最好的那個分類.而對于老用戶推薦系統(tǒng)把老的分類內容將不斷重復展示，而新的分類內容將缺少展示機會，也有可能永遠不會在用戶面前展現(xiàn).假設系統(tǒng)有了新的推薦策略，有沒有比更快的方法知道它和舊的策略相比，哪個推薦效果更好？是通過推薦已知收益最高的分類來保證獲得當前較高的收益，還是探索未知的分類內容，以一定的概率獲得更加優(yōu)秀的推薦分類內容，尋求獲得更高收益的可能性.這些都是在推薦系統(tǒng)最常見的E&E問題（Exploit&Explore）.一部分是探索未知內容（Explore），另一部分是利用已知內容（Exploit）.推薦系統(tǒng)在不斷利用已知分類內容展示給用戶的同時還需要不斷探索新的分類內容推薦給用戶.換句話說，成功優(yōu)秀的推薦系統(tǒng)應該能利用已知用戶的興趣，探索用戶未知的興趣，推薦資源池中用戶更感興趣的分類內容，獲得最大點擊收益.當前公認的解決這個問題的思路是推薦系統(tǒng)要花一部分精力做探索未知，花一部分精力做利用已知.至于這兩個部分所投入精力的比例是多少，才能獲得收益最大化，目前有多種算法可以解決，效果不盡相同.

1.2 推薦系統(tǒng)中E&E問題的分類

推薦系統(tǒng)常見的E&E問題主要分為幾類：（1）推薦系統(tǒng)冷啟動問題.假設一個用戶對不同類別的內容感興趣程度不同，那么推薦系統(tǒng)初次見到這個用戶時，如何快速準確的確定他對所感興趣的分類內容.如何給新注冊用戶或無歷史信息的客戶做個性化推薦，如何將新產品推薦給可能對其感興趣的用戶，如何在一個新開發(fā)的系統(tǒng)上設計個性化推薦，從而在系統(tǒng)剛發(fā)布時就讓用戶體驗到個性化推薦服務或者只有產品還沒用戶的系統(tǒng).（2）老用戶推薦分類選擇問題.假設資源池有若干分類內容，如何確定給用戶展示哪些分類，才能獲得用戶的最大點擊收益.（3）推薦策略選擇問題.如何快速的檢驗出我們有了新的推薦策略，是否比之前推薦策略具有更有效的推薦效果［4］.

1.3 E&E問題的解決思路

Exploit是基于已知最好的推薦策略，開發(fā)利用已知具有較高收益的分類.優(yōu)點在于可以充分利用已知高收益分類內容，缺點在于僅限于局部最優(yōu)，錯過潛在的具有更高分類收益的機會，屬于保守部分.Explore是不考慮曾經(jīng)的經(jīng)驗，探索潛在可能產生高回報的分類內容.優(yōu)點在于能發(fā)現(xiàn)更高收益的分類內容，缺點在于失去了對已有高收益分類內容利用機會，屬于激進部分.E&E問題的解決思路在于要找到Exploit&Explore的平衡點，以達到累計收益最大化.面對多個分類的選擇，我們選擇所產生收益和期望的最佳選擇所產生的收益之間的差值作為評估指標，定義為遺憾值R(regret)，多次選擇的遺憾值之和定義為累計遺憾，即根據(jù)累計遺憾值的多少來衡量解決E&E問題的優(yōu)劣性.

上式中，這里假設選擇每個分類的收益為伯努利回報，RT為累計遺憾值opt是第i次試驗時被選中分類的期望收益，opt是所有分類中的期望的最佳選擇分類的收益.累計遺憾值為次選擇的遺憾累計，每次選擇的遺憾值T為最優(yōu)選擇收益與本次選擇收益之差.可見定義的遺憾值R作為策略好壞的指標，通過最理想總收益與實際得到的總收益之間的差值，反應解決E&E問題的優(yōu)劣.

2 Bandit算法介紹

Bandit算法來源于經(jīng)典的N臂賭博機問題，有N個賭博機并排放在賭徒面前，每一輪賭徒通過拉動一臺賭博機的臂來進行選擇,同時記錄這臺賭博機帶來的收益.假設各個賭博機得到收益均不是完全相同的,經(jīng)過多輪操作后,可以得到出各個賭博機收益的部分統(tǒng)計信息,然后根據(jù)統(tǒng)計信息選擇那個看起來收益最高的賭博機，拉動它的臂，最終使賭徒得到最大的收益.即是一個賭徒需要在一排賭博機前決定選擇拉動哪一臺賭博機的臂，并且決定每個臂需要被選擇多少次的問題.假設每臺賭博機提供的收益是與它自身的收益隨機分布的函數(shù)相關的.賭徒的目標是最大限度地通過選擇的序列，使得獲得的收益最大化.機器學習里又把它稱為做“多臂老虎機”(multi-armed bandit)問題.需要一種算法能精確地計算哪個賭博機應該多次選擇，哪個應該少選擇，并告訴賭徒下一把應該去選擇哪一個.Bandit算法的框架包含兩個部分，一是探索未知，拉動未知收益的臂，嘗試尋找更大收益的臂（Explore），二是利用已知收益的統(tǒng)計信息，拉動收益最大的臂（Exploit）.

3 利用Bandit算法解決E&E問題

3.1 Bandit算法模型

有N個賭博機并排放在我們面前,我們首先給它們編號1，2，…，N.賭博機的多個臂的收益可以看做是一組真實的隨機分布 B=｛R1，...，RK｝，K∈Z，Z代表賭博機集合,K代表臂桿.u1，...，uk代表每個臂的平均收益，賭徒每一輪拉下一個臂，并得到一次收益，i是試驗的輪數(shù).輪之后的后悔度為，可用如下公式表示［5］：

其中w*是前T輪最大收益的平均數(shù)，w*=max｛ uk｝，wB(i)是第i次試驗時被選中臂的期望收益.一個零后悔度的策略會使得RT在無限次選擇臂桿后以概率1趨近與0，趨近于最優(yōu)策略.在解決這個問題的時候，需要在探索新臂以獲得更多關于當前已經(jīng)選擇臂的收益的信息，即探索和選擇已有收益最高的臂來獲取最大利益之中進行權衡.每次選擇后，和本該最佳的選擇差了多少，然后把每次差距累加起來就是總的遺憾.這個公式也可以用來對比使用不同策略的Bandit算法的效果.對同樣的多臂問題，用不同的策略的算法試驗相同次數(shù)，看看誰的regret增長得慢.

目前流行的幾種Bandit算法，大多采用的是UCB策略，即估計置信區(qū)間的做法，然后按照置信區(qū)間的上界來進行推薦，因此一些學者把這類Bandit算法稱之為UCB算法.

3.2 Bandit算法中的UCB策略

假設面對固定的N個分類內容，沒有任何用戶的歷史行為和行為預測，每一個分類內容的收益情況完全不知道，每次試驗要選擇其中一個，如何在這個選擇過程中最大化收益？論文討論采用UCB策略即用置信區(qū)間解決這個問題.使用置信區(qū)間來度量估計的不確定性和置信性.置信區(qū)間可以簡單地理解為不確定性的程度，區(qū)間越寬，越不確定，反之區(qū)間越窄，確定性越高.每個分類內容的回報均值都有個置信區(qū)間，隨著試驗次數(shù)增加，置信區(qū)間會逐漸變窄，也就確定了到底收益多還是少.UCB是一種樂觀的策略，選擇置信區(qū)間上界排序，如果是悲觀保守的做法，是選擇置信區(qū)間下界排序.這里采用分類收益的置信上限作為收益預估值，其基本思想是：每次選擇前，都根據(jù)已經(jīng)試驗的結果重新估計每個分類的均值及置信區(qū)間.如果某些分類的置信區(qū)間很寬，說明它被選次數(shù)很少，不確定性高，那么它會傾向于被多次選擇.選擇置信區(qū)間上限最大的那個分類，置信區(qū)間較寬的那些分類傾向于被多次選擇，這就是算法激進的部分（explore）.對某些分類嘗試的次數(shù)越多，對該分類收益估計的置信區(qū)間就會越窄.估計的不確定性降低，說明被選次數(shù)很多，比較容易確定其好壞了，那些均值更大的分類傾向于被多次選擇，這是算法保守的部分（exploit）.算法大致過程可以描述為，先對每一個臂都試一遍之后，每次選擇分類期望Z值最大的那個臂，分類期望是這個臂到目前的收益均值和標準差之和，其計算分類期望的公式如下：

與Bandit算法中應用的其他策略相比，這種策略的好處在于：考慮了收益均值的不確定性，讓新的分類更快得到嘗試機會.將探索和開發(fā)融為一體的UCB策略不需要任何參數(shù)，因此不需要考慮如何驗證參數(shù)的問題.UCB策略很好的解決了Exploit&Explore之間平衡的問題，不會顧此失彼，比較成功的融合在一起.

3.3 Bandit算法的程序設計

利用Matlab軟件進行算法仿真程序設計，由于篇幅原因，僅選取部分核心代碼如下：

4 結語

E&E這個問題的本質就是尋找最優(yōu)的分類和獲得最大收益之間的平衡問題，所以它出現(xiàn)的領域就是這種尋找最優(yōu)和獲得最大收益矛盾的地方.這一對矛盾在推薦系統(tǒng)中一直客觀存在，解決Explore肯定要放棄一部分既得收益，而要走向未知，尋找更優(yōu).這顯然就存在一定的冒險性，會傷害用戶體驗的，甚至會損失一部分用戶，在已經(jīng)知道用戶喜歡某個分類的前提下，仍然以小概率給用戶推薦另一個分類.本文討論的使用UCB策略實現(xiàn)的Bandit算法能較好的解決這對矛盾，但也存在一定的缺點.比如它需要首先嘗試一遍所有分類，因此當分類資源數(shù)量很大時耗時耗力，另外初始階段各個分類選擇次數(shù)都比較少，導致得到的收益波動較大，以至于經(jīng)常選中實際比較差的分類等，還需要在Bandit算法解決E&E問題上進行更多的實驗和改進.

［1］楊娟.多通路主題模型和雙矩陣分解推薦算法[D].蘇州：蘇州大學，2013.

［2］孫才奇.基于信任網(wǎng)絡的情境感知推薦算法的研究[D].沈陽：東北大學，2015.

［3］王國霞.個性化推薦系統(tǒng)隱私保護策略研究進展[J].計算機應用研究，2012，29（6）：2003.

［4］佚名.推薦系統(tǒng)的 EE 問題及 Bandit算法[EB/OL].（2016-12-15）[2017-02-11].http://x-algo.cn/index.php/2016/12/15/ee-problem-and-bandit-algorithm-for-recommender-systems/.

［5］Vermorel J，Mohri M.Multi-armed Bandit Algorithms and Empirical Evaluation[C].European Conference on Machine Learning，2005，3720：437-448.

［6］刑無刀.專治療選擇困難癥——bandit算法[EB/OL].[2017-02-05].https://zhuanlan.zhihu.com/p/21388070?refer=resyschina.

Bandit Algorithm Solves the Recommended System E&E Problem

GAO Hai-bin
（Department of Computer Science,Huainan Union University,Huainan 232001,Anhui,China）

At present,the E&E problem is prevalent in the development and application of the current recommendation system.Firstly,the generation and classification of E&E problem in the recommendation system are introduced.Then,the idea of using Bandit algorithm to solve this problem is put forward.This paper introduces the mathematic model of Bandit algorithm and the Bandit algorithm model established by UCB strategy,and prepares the program with MATLAB.Finally,the merits and shortcomings of this algorithm model are pointed out.

Bandit algorithm；recommended system；E&E

TP391.1

A

1007-5348（2017）09-0022-05

2017-05-26

安徽省高等學校省級自然科學研究項目（KJ2017A585）.

高海賓（1979-），男 ，安徽淮北人，淮南聯(lián)合大學計算機系講師，碩士；研究方向：軟件技術.

（責任編輯：歐 愷）