1 問題 

1.1 某業(yè)務(wù)拉新場景—冷啟動決策問題

拉新場景是指在大流量業(yè)務(wù)場景中投放拉新業(yè)務(wù)的相關(guān)優(yōu)質(zhì)內(nèi)容，從而吸引用戶訪問，快速增加用戶量。這個拉新場景需要從4千+專輯池(每日會加入一些新的物品)中挑選出兩個專輯投放給用戶，使用這兩個專輯來吸引新用戶，從而達(dá)到拉新的目的。由于是投放給新用戶，所以沒有歷史行為數(shù)據(jù)作為依據(jù)去推測該用戶喜歡什么。能夠依賴的數(shù)據(jù)包含專輯本身的特征，如：分類信息、更新時間等，用戶的畫像數(shù)據(jù)(達(dá)芬奇畫像維護和挖掘了用戶的基本畫像數(shù)據(jù))，如：年齡、性別、地域等。開始時，我們使用傳統(tǒng)的機器學(xué)習(xí)模型，如LR、FM等，將每日拉新用戶量做到了5千-1.1萬。這里存在的問題是，傳統(tǒng)機器學(xué)習(xí)非常依賴正負(fù)樣本的標(biāo)注。對于某些新物品，如果它從來沒有被曝光，那么它永遠(yuǎn)也不可能被標(biāo)記為正樣本，這對于新物品來講是不公平的，也是推薦領(lǐng)域不愿看到的現(xiàn)象。一種比較直接的做法是，保留一股流量專門用來做新物品的探索，但是這里又會有一些新的問題產(chǎn)生，如：這股流量用多大？探索的時機該怎么把握？新物品中每一個物品曝光多少次、曝光給誰是最合適的？如何保證整體收益是最大的， 等等一系列問題，而MAB(Multi-armed bandit problem，多臂老虎機)方法正是解決這類決策問題的。所以我們嘗試使用MAB的思想來解決新用戶和新物品的推薦問題。事實證明，該方法是可靠的，使用MAB中的UCB算法之后，該拉新場景每日拉新量提高到最初base的2.3倍。

1.2 短視頻推薦結(jié)果多樣性控制

短視頻推薦場景的特點是在保質(zhì)的前提下，需要向用戶推薦有創(chuàng)意、多樣的、新鮮、熱點等不明確討厭的短視頻。從直觀的體驗結(jié)合相關(guān)流水統(tǒng)計分析來看，用戶非常反感連續(xù)推薦同一主題的短視頻，所以需要使用一定的策略來對多樣性進行控制，提高用戶體驗，盡可能把用戶留下來。在騰訊內(nèi)部某短視頻推薦場景中，我們使用MAB中的Exp3算法來進行多樣性控制。事實證明，Exp3用在探索新用戶的興趣場景下，與隨機、Thompson sampling等方法對比，視頻平均觀看時長提升了10%，對于老用戶增加了推薦結(jié)果的多樣性，視頻平均觀看時長略有提升。

2 神盾如何解決拉新場景的冷啟動問題

2.1 MAB如何解決決策問題

在說明神盾如何解決冷啟動問題前，這里先對MAB問題做一個綜述性的介紹。

什么是MAB問題？

MAB的定義非常有意思，它來源于賭徒去賭場賭博，搖老虎機的場景。一個賭徒打算去搖老虎機，走進賭場一看，一排排老虎機，外表一模一樣，但是每個老虎機吐錢的概率可不一樣，他不知道每個老虎機吐錢的概率分布是什么，那么想最大化收益該怎么辦？這就是MAB(多臂賭博機)問題。怎么解決這個問題呢？最好的辦法是有策略的試一試，越快越好，這些策略就是MAB算法。

推薦領(lǐng)域的很多問題可以轉(zhuǎn)化為MAB問題，例如：

1. 假設(shè)一個用戶對不同類別的內(nèi)容感興趣程度不同，那么我們的推薦系統(tǒng)初次見到這個用戶時，怎么快速地知道他對每類內(nèi)容的感興趣程度？這就是推薦系統(tǒng)的用戶冷啟動問題。

2. 在推薦場景中，往往會有多個算法或模型在線上做A/B Test，一般情況下我們會把流量按照一定比率來進行分配，而在不同的時間點，不同的算法線上效果往往是不一致。我們期望每時每刻都能把占比大的流量分配給效果最好的算法。有沒有比A/B Test更合適的流量分配方法來讓業(yè)務(wù)的收益最大化？

可以看到全部都屬于選擇問題。只要是關(guān)于選擇的問題，都可以轉(zhuǎn)化成MAB問題。在計算廣告和推薦系統(tǒng)領(lǐng)域，這個問題又被稱為EE問題（Exploit-Explore問題）。Exploit意思是，用戶比較確定的興趣，要盡可能的使用。Explore意思是，要不斷探索用戶新的興趣，否則很快就會越推越窄。

MAB的數(shù)學(xué)表述：

• A．設(shè)共有k個手柄（對應(yīng)拉新場景中的k個專輯）
• B．k個手柄的回報分布<D1,D2,D3……Dk>（對應(yīng)拉新中，專輯推薦帶來的新用戶量的分布情況）
• C．回報均值 u1,u2……uk（對應(yīng)每一個專輯在以前的實驗的平均收益）
• D．回報方差 v1,v2……vk（對應(yīng)每一個專輯每一次實驗收益的穩(wěn)定性）
• E．最佳手柄平均收益

• F．T輪之后的Regret值 ，使用一定的算法策略使得其T輪之后最小

Rt是后悔值，T表示實驗輪數(shù)，u*最佳手柄平均收益，ut表示t時刻，所選手柄的收益

MAB問題目前常用算法：

1. 樸素選擇算法：其思想是對于每個手柄都進行k次實驗，選擇出平均收益最高的手柄。在之后的所有手柄選擇中都選擇這個最好的。

2. Epsilon-Greedy算法(小量貪婪算法)：每一輪在選擇手柄的時候按概率p選擇Explore（探索），按概率1-p選擇Exploit（歷史經(jīng)驗）。對于Explore，隨機的從所有手柄中選擇一個；對于Exploit，從所有手柄中選擇平均收益最大的那個。

3. Softmax算法：該算法是在Epsilon-Greedy算法的基礎(chǔ)上改進的，同樣是先選擇是Explore（探索）還是Exploit（原有）。對于Exploit階段，與Epsilon-Greedy算法一致。對于Explore，并不是隨機選擇手柄，而是使用Softmax函數(shù)計算每一個手柄被選中的概率。armi表示手柄i，ui表示手柄i的平均收益，k是手柄總數(shù)。

4. UCB(Upper Confidence Bound)算法：通過實驗觀察，統(tǒng)計得到的手柄平均收益，根據(jù)中心極限定理，實驗的次數(shù)越多，統(tǒng)計概率越接近真實概率。換句話說當(dāng)實驗次數(shù)足夠多時，平均收益就代表了真實收益。UCB算法使用每一個手柄的統(tǒng)計平均收益來代替真實收益。根據(jù)手柄的收益置信區(qū)間的上界，進行排序，選擇置信區(qū)間上界最大的手柄。隨著嘗試的次數(shù)越來越多，置信區(qū)間會不斷縮窄，上界會逐漸逼近真實值。這個算法的好處是，將統(tǒng)計值的不確定因素，考慮進了算法決策中，并且不需要設(shè)定參數(shù)。在選擇手柄時，一般使用如下兩個公式進行選擇：

t表示t時刻或者t輪實驗，arm(t)表示t時刻選擇的手柄， ui均值表示手柄i在以前實驗中的平均收益，ni表示手柄i在以前實驗中被選中的次數(shù)。α是(0,1)為超參數(shù)，用以控制探索部分的影響程度。

“選擇置信區(qū)間上界最大的手柄”這句話反映了幾個意思：

如果手柄置信區(qū)間很寬（被選次數(shù)很少，還不確定），那么它會傾向于被多次選擇，這個是算法冒風(fēng)險的部分。

如果手柄置信區(qū)間很窄（被選次數(shù)很多，比較好確定其好壞了），那么均值大的傾向于被多次選擇，這個是算法保守穩(wěn)妥的部分。

UCB是一種樂觀的算法，選擇置信區(qū)間上界排序。如果是悲觀保守的做法，是選擇置信區(qū)間下界排序。

5. Thompson sampling：該算法跟UCB類似，Thompson sampling算法根據(jù)手柄的真實收益的概率分布來確定所選手柄。假設(shè)每個臂是否產(chǎn)生收益，其背后有一個概率分布，產(chǎn)生收益的概率為p。不斷地試驗，去估計出一個置信度較高的概率p的概率分布就能近似解決這個問題了。 假設(shè)概率p的概率分布符合beta(wins, lose)分布，它有兩個參數(shù): wins, lose。每個臂都維護一個beta分布的參數(shù)。每次試驗后，選中一個臂，搖一下，有收益則該臂的wins增加1，否則該臂的lose增加1。每次選擇臂的方式是：用每個臂現(xiàn)有的beta分布產(chǎn)生一個隨機數(shù)b，選擇所有臂產(chǎn)生的隨機數(shù)中最大的那個臂去搖。

以上算法優(yōu)缺點：

1. 樸素選擇算法需要為每一個手柄準(zhǔn)備合適次數(shù)的實驗，用以計算每個手柄的平均收益，并不適合物品快速迭代的場景，同時會浪費大量流量。

2. Epsilon-Greedy算法與Softmax算法有一個很明顯的缺陷是它們只關(guān)心回報是多少，并不關(guān)心每個手柄被拉下了多少次。這就意味著，這些算法不再會選中初始回報特別低的手柄，即使這個手柄的只被測試了一次。而UCB算法，不僅關(guān)注回報，同樣會關(guān)注每個手柄被探索的次數(shù)。Epsilon-Greedy and Softmax的特點，默認(rèn)選擇當(dāng)前已知的回報率最高的手柄，偶爾選擇那些沒有最高回報的手柄。

3. Thompson sampling。UCB算法部分使用概率分布（僅置信區(qū)間上界）來量化不確定性。而Thompson sampling基于貝葉斯思想，全部用概率分布來表達(dá)不確定性。相比于UCB算法，Thompson sampling，UCB采用確定的選擇策略，可能導(dǎo)致每次返回結(jié)果相同（不是推薦想要的），Thompson Sampling則是隨機化策略。Thompson sampling實現(xiàn)相對更簡單，UCB計算量更大（可能需要離線/異步計算）。在計算機廣告、文章推薦領(lǐng)域，效果與UCB不相上下。

LinUCB算法：

以上介紹的MAB算法都沒有充分利用上下文信息，這里所說的上下文信息包括用戶、物品以及其他相關(guān)環(huán)境相關(guān)的特征。而LinUCB算法是在UCB算法的基礎(chǔ)上使用用戶、物品以及其他相關(guān)環(huán)境相關(guān)的特征來進行UCB打分。LinUCB算法做了一個假設(shè)：一個Item被選擇后推送給一個User，其回報和相關(guān)Feature成線性關(guān)系，這里的“相關(guān)Feature”就是上下文信息。于是預(yù)測過程就變成：用User和Item的特征預(yù)估回報及其置信區(qū)間，選擇置信區(qū)間上界最大的Item推薦，然后依據(jù)實際回報來更新線性關(guān)系的參數(shù)。

相關(guān)論文中(見附件)提出兩種計算辦法，這里將論文中算法偽代碼貼出來，方便大家閱讀，詳情請查閱附件論文。

2.2 神盾推薦如何使用UCB來解決拉新場景推薦問題

神盾在UCB算法的基礎(chǔ)上，嘗試為其添加上下文環(huán)境信息，該環(huán)境信息主要包括用戶畫像、物品畫像、環(huán)境信息（時刻，節(jié)假日，網(wǎng)絡(luò)環(huán)境）等，因此將其命名為PUCB(Portrait Upper Confidence Bound)。該算法包括兩部分，第一部分使用用戶已有的行為數(shù)據(jù)生成物品在某些畫像特征下的UCB得分(該分?jǐn)?shù)綜合考慮物品的歷史平均收益和潛在收益)。第二部分使用預(yù)訓(xùn)練好的分類器，在對user-item pair打分時，將原有特征值替換為UCB打分，然后計算最終的打分。

UCB打分

數(shù)據(jù)準(zhǔn)備階段

圖 1 神盾PUCB-數(shù)據(jù)準(zhǔn)備階段示意圖

該階段的目的是確保使用用戶行為數(shù)據(jù)和畫像特征數(shù)據(jù)生成所需時間窗口下的【畫像，物品ID，行為統(tǒng)計數(shù)】。這部分神盾在實現(xiàn)時，考慮了一些容錯機制，如：當(dāng)歷史時刻數(shù)據(jù)不存在時，是否可以根據(jù)已有時刻的行為數(shù)據(jù)和已有時刻的【畫像，物品ID，行為統(tǒng)計數(shù)】統(tǒng)計數(shù)據(jù)來重新生成等等。

統(tǒng)計打分階段

使用公式6，基于時間窗口內(nèi)的數(shù)據(jù)，采用一定的衰減策略來計算ucb分。對某一物品某種畫像進行ucb打分。其中i表示物品ID，j表示畫像特征MD5編碼，cij 表示t時刻j特征編碼的物品i的點擊量，Cij 表示歷史時刻j特征編碼的物品i的點擊量，λ表示新行為對得分的影響程度，λ越大表示最新行為越大，反之亦然，eij表示t時刻j特征編碼的物品i的曝光量，Eij表示歷史時刻j特征編碼的物品i的曝光量，e為無意義初始值防止分母為0，Thj表示當(dāng)前時刻j特征編碼的物品總的曝光次數(shù)，Taj表示歷史時刻和當(dāng)前時刻所有專輯j特征編碼的物品總的曝光數(shù)，α表示bonus項用于探索物品的權(quán)重，α越大越容易出新物品。

是否需要對Cij，Eij，Taj全部進行衰減，如下公式為計算歷史數(shù)據(jù)的公式。d(t)表示t時刻的統(tǒng)計量，d’(i)表示i時刻的實際統(tǒng)計量，f(|t-i|)表示時間衰減函數(shù)，θ表示時間衰減參數(shù)，新時刻行為的影響越大，就應(yīng)該跳大θ，反之亦然。

偽代碼如下：

doStatistic()

Input: 歷史時刻物品-畫像曝光點擊統(tǒng)計數(shù)據(jù)hisFirstItemPortraitStatis

(t-w+1, t)時刻物品-畫像曝光點擊統(tǒng)計數(shù)據(jù)otherItemPortraitStatis

isUseDefaultValue歷史時刻數(shù)據(jù)是否使用默認(rèn)值

toolItemID池子所有物品ID

Output: itemPortraitUCBScore  ItemID，畫像MD5的ucb得分

1 if  isUseDefaultValue  then

2 向hisFirstItemPortraitStatis補充缺失的物品曝光和點擊數(shù)據(jù)（使用默認(rèn)值）

3 hisRDD，realRDD←對hisFirstItemPortraitStatis，otherItemPortraitStatis分組合并統(tǒng)計

4 itemPortraitUCBScore  ← 使用上述公式計算ucb得分

5 return itemPortraitUCBScore

分類器糅合UCB打分

經(jīng)過上述處理之后，我們會得到圖2所示信息，其中owner列為特征值，primary_key為歷史實時行為標(biāo)記，secondary_key為物品ID，value為統(tǒng)計到的次數(shù)。

圖 2 PUCB算法中間統(tǒng)計結(jié)果-示例圖

換句話說，經(jīng)過上述處理，我們將原始的特征抽象為UCB得分，接下來需要做的事情是使用一定的策略將不同維度的信息糅合起來。論文中使用了嶺回歸的方式來為每一個特征維度計算權(quán)重，神盾這里設(shè)計的比較靈活，可以使用任意一種分類器（如:LR、FM等）來糅合最終的結(jié)果，需要注意的是該分類器所使用的特征應(yīng)該跟計算UCB打分的特征體系一致。

3.1 exp3多樣性保證

Exp3(Exponential-weight algorithm for Exploration and Exploitation)算法是2001年提出來的一種解決MAB問題的算法。它的核心思想是維護一組臂的權(quán)重信息，然后使用數(shù)學(xué)方法得到一組臂的概率分布，接著每次擲骰子去選擇臂，根據(jù)選擇后觀察到的收益情況去調(diào)整臂的權(quán)重，如此迭代下去。論文中證明了使用這種策略能夠保證后悔值的在一定可以接受的范圍內(nèi)，從而保證了結(jié)果不會是最壞的一種情況。

Exp3算法偽代碼如下：

?是一個超參數(shù)，值域為[0,1]，可以采用固定值，在實驗輪數(shù)確定的情況下，建議使用公式9來計算?，其中K為臂的個數(shù)，T為實驗的輪數(shù)。

首先為每一個臂初始化權(quán)重為1，然后使用算法1步驟中的公式計算每一個臂的概率，該公式保證了所有臂的概率和為1，接著隨機出一個[0,1]之間的值，觀察該值落在哪個臂中，選擇之后觀察該臂的收益情況，使用公式11計算其預(yù)估收益。

使用公式12來更新權(quán)重。

該算法在計算臂的概率時，雖然有可能趨向于0，但是不會等于0，所以對于任意一個臂，都有機會被選中，只是收益高的臂更容易被選中，收益低的臂更不容易被選中。

3.2 神盾推薦如何應(yīng)用exp3來做多樣性控制

圖 3 神盾Exp3算法流程

1. 首先規(guī)劃Exp3的臂策略，最簡單的臂策略為不同的召回策略，復(fù)雜一些可以按照一定的業(yè)務(wù)規(guī)則來對物品進行重分桶，如：在短視頻推薦中按照物品類別信息（游戲、風(fēng)景、美女等）構(gòu)建了20+個臂。

2. 在tesla(騰訊內(nèi)部集群任務(wù)調(diào)度系統(tǒng))上配置Spark Streaming任務(wù)，這個任務(wù)的目的是分鐘級消費TDBank業(yè)務(wù)數(shù)據(jù)，按照業(yè)務(wù)規(guī)則構(gòu)建正負(fù)反饋數(shù)據(jù)，然后使用一定的更新策略來更新權(quán)重。神盾推薦在這里設(shè)計了三種權(quán)重更新策略。

a.原版算法更新策略，使用每條反饋數(shù)據(jù)來更新。這里存在的問題是由于TDBank數(shù)據(jù)收集，近線訓(xùn)練和線上服務(wù)鏈條較長，近線訓(xùn)練的結(jié)果不能非常實時的推送到線上去，存在一定的誤差。

b.小batch更新策略，收集一段時間的數(shù)據(jù)（神盾使用1分鐘的數(shù)據(jù)）對每個臂的收益值做歸一化，然后更新算法參數(shù)。與a相比，優(yōu)點是權(quán)重更新更加穩(wěn)定，缺點是收斂速度相對比a緩慢。

c.在b的基礎(chǔ)上引入窗口概念，會周期性的使用初始值來重置算法參數(shù)。

其他：在實際推薦業(yè)務(wù)場景中可以依照實際的應(yīng)用情況，對正負(fù)反饋構(gòu)建，權(quán)重更新策略，為每位用戶構(gòu)建Exp3選擇器等。

3. 推送計算參數(shù)到Kafka Server，更新R2線上算法參數(shù)。

4. 神盾推薦在短視頻推薦上應(yīng)用Exp3的結(jié)構(gòu)如下圖所示，可以看到exp3被應(yīng)用在ReRank層，每一個臂都可能被搖到，同時從數(shù)學(xué)角度保證整體選擇的收益肯定遠(yuǎn)高于最壞情況，進而在保證多樣性的同時，整體收益高于最壞收益。

圖 4 神盾推薦短視頻推薦上Exp3算法結(jié)構(gòu)示意圖

 4 總結(jié)

綜合上述場景的實際應(yīng)用情況，說明在面臨用戶或物品冷啟動的情況時，值得使用PUCB的方法進行嘗試，而內(nèi)容類對多樣性有要求的場景，可以嘗試使用Exp3來解決。

本文所述MAB方法的經(jīng)驗來自組內(nèi)所有同事在實際業(yè)務(wù)中的總結(jié)。歡迎大家交流討論！

參考資料：

exp3數(shù)學(xué)推導(dǎo)： https:///2013/11/08/adversarial-bandits-and-the-exp3-algorithm/

Python版demo：https://github.com/j2kun/exp3

https://zhuanlan.zhihu.com/p/21388070

http://blog.csdn.net/scythe666/article/details/74857425

http:///index.php/2016/12/15/ee-problem-and-bandit-algorithm-for-recommender-systems/

Adversarial Bandits and the Exp3 Algorithm

來源：騰訊QQ大數(shù)據(jù)