責編 | 何永燦
推薦系統裡面有兩個經典問題：EE和冷啟動。前者涉及到平衡準確和多樣，後者涉及到產品算法運營等一系列。Bandit算法是一種簡單的在線學習算法，常常用於嘗試解決這兩個問題，本文為你介紹基礎的Bandit算法及一系列升級版，以及對推薦系統這兩個經典問題的思考。
我們會遇到很多選擇的場景。上哪個大學，學什麼專業，去哪家公司，中午吃什麼等等。這些事情，都讓選擇困難症的我們頭很大。那麼，有算法能夠很好地對付這些問題嗎？
當然有！那就是Bandit算法。
Bandit算法來源於歷史悠久的賭博學，它要解決的問題是這樣的[1]：
一個賭徒，要去搖老虎機，走進賭場一看，一排老虎機，外表一模一樣，但是每個老虎機吐錢的概率可不一樣，他不知道每個老虎機吐錢的概率分布是什麼，那麼每次該選擇哪個老虎機可以做到最大化收益呢？這就是多臂賭博機問題（Multi-armed bandit problem, K-armed bandit problem, MAB）。
圖1 MAB問題怎麼解決這個問題呢？最好的辦法是去試一試，不是盲目地試，而是有策略地快速試一試，這些策略就是Bandit算法。
這個多臂問題，推薦系統裡很多問題都與它類似：
假設一個用戶對不同類別的內容感興趣程度不同，那麼我們的推薦系統初次見到這個用戶時，怎麼快速地知道他對每類內容的感興趣程度？這就是推薦系統的冷啟動。
假設我們有若干廣告庫存，怎麼知道該給每個用戶展示哪個廣告，從而獲得最大的點擊收益？是每次都挑效果最好那個麼？那麼新廣告如何才有出頭之日？
我們的算法工程師又想出了新的模型，有沒有比A/B test更快的方法知道它和舊模型相比誰更靠譜？
如果只是推薦已知的用戶感興趣的物品，如何才能科學地冒險給他推薦一些新鮮的物品？
Bandit算法與推薦系統在推薦系統領域裡，有兩個比較經典的問題常被人提起，一個是EE問題，另一個是用戶冷啟動問題。
什麼是EE問題？又叫exploit－explore問題。exploit就是：對用戶比較確定的興趣，當然要利用開採迎合，好比說已經掙到的錢，當然要花；explore就是：光對著用戶已知的興趣使用，用戶很快會膩，所以要不斷探索用戶新的興趣才行，這就好比雖然有一點錢可以花了，但是還得繼續搬磚掙錢，不然花完了就得喝西北風。
用戶冷啟動問題，也就是面對新用戶時，如何能夠通過若干次實驗，猜出用戶的大致興趣。
我想，屏幕前的你已經想到了，推薦系統冷啟動可以用Bandit算法來解決一部分。
這兩個問題本質上都是如何選擇用戶感興趣的主題進行推薦，比較符合Bandit算法背後的MAB問題。
比如，用Bandit算法解決冷啟動的大致思路如下：用分類或者Topic來表示每個用戶興趣，也就是MAB問題中的臂（Arm），我們可以通過幾次試驗，來刻畫出新用戶心目中對每個Topic的感興趣概率。這裡，如果用戶對某個Topic感興趣（提供了顯式反饋或隱式反饋），就表示我們得到了收益，如果推給了它不感興趣的Topic，推薦系統就表示很遺憾（regret）了。如此經歷「選擇-觀察-更新-選擇」的循環，理論上是越來越逼近用戶真正感興趣的Topic的，
怎麼選擇Bandit算法？現在來介紹一下Bandit算法怎麼解決這類問題的。Bandit算法需要量化一個核心問題：錯誤的選擇到底有多大的遺憾？能不能遺憾少一些？
王家衛在《一代宗師》裡寄出一句臺詞：
人生要是無憾，那多無趣？
而我說：算法要是無憾，那應該是過擬合了。
所以說：怎麼衡量不同Bandit算法在解決多臂問題上的效果？首先介紹一個概念，叫做累積遺憾（regret）[2]：
圖2 積累遺憾這個公式就是計算Bandit算法的累積遺憾，解釋一下：
首先，這裡我們討論的每個臂的收益非0即1，也就是伯努利收益。
然後，每次選擇後，計算和最佳的選擇差了多少，然後把差距累加起來就是總的遺憾。
wB(i)是第i次試驗時被選中臂的期望收益， w*是所有臂中的最佳那個，如果上帝提前告訴你，我們當然每次試驗都選它，問題是上帝不告訴你，所以就有了Bandit算法，我們就有了這篇文章。
這個公式可以用來對比不同Bandit算法的效果：對同樣的多臂問題，用不同的Bandit算法試驗相同次數，看看誰的regret增長得慢。
那麼到底不同的Bandit算法有哪些呢？
常用Bandit算法Thompson sampling算法
Thompson sampling算法簡單實用，因為它只有一行代碼就可以實現[3]。簡單介紹一下它的原理，要點如下：
假設每個臂是否產生收益，其背後有一個概率分布，產生收益的概率為p。
我們不斷地試驗，去估計出一個置信度較高的「概率p的概率分布」就能近似解決這個問題了。
怎麼能估計「概率p的概率分布」呢？ 答案是假設概率p的概率分布符合beta(wins, lose)分布，它有兩個參數: wins, lose。
每個臂都維護一個beta分布的參數。每次試驗後，選中一個臂，搖一下，有收益則該臂的wins增加1，否則該臂的lose增加1。
每次選擇臂的方式是：用每個臂現有的beta分布產生一個隨機數b，選擇所有臂產生的隨機數中最大的那個臂去搖。
import numpy as np
import pymc
#wins 和 trials 是一個N維向量，N是賭博機的臂的個數，每個元素記錄了
choice = np.argmax(pymc.rbeta(1 + wins, 1 + trials - wins))
wins[choice] += 1
trials += 1
UCB算法
UCB算法全稱是Upper Confidence Bound（置信區間上界），它的算法步驟如下[4]：
圖3 UCB算法這個公式反映一個特點：均值越大，標準差越小，被選中的概率會越來越大，同時哪些被選次數較少的臂也會得到試驗機會。
Epsilon-Greedy算法
這是一個樸素的Bandit算法，有點類似模擬退火的思想：
選一個（0,1）之間較小的數作為epsilon；
每次以概率epsilon做一件事：所有臂中隨機選一個；
每次以概率1-epsilon 選擇截止到當前，平均收益最大的那個臂。
是不是簡單粗暴？epsilon的值可以控制對Exploit和Explore的偏好程度。越接近0，越保守，只想花錢不想掙錢。
樸素Bandit算法
最樸素的Bandit算法就是：先隨機試若干次，計算每個臂的平均收益，一直選均值最大那個臂。這個算法是人類在實際中最常採用的，不可否認，它還是比隨機亂猜要好。
以上五個算法，我們用10000次模擬試驗的方式對比了其效果如圖4，實驗代碼來源 [5]：
圖4 五種Bandit算法模擬試驗的效果圖算法效果對比一目了然：UCB算法和Thompson採樣算法顯著優秀一些。
至於你實際上要選哪一種Bandit算法，你可以選一種Bandit算法來選Bandit算法。
UCB算法在做EE（Exploit-Explore）的時候表現不錯，但它是上下文無關（context free）的Bandit算法，它只管埋頭幹活，根本不觀察一下面對的都是些什麼特點的arm，下次遇到相似特點但不一樣的arm也幫不上什麼忙。
UCB解決Multi-armed bandit問題的思路是：用置信區間。置信區間可以簡單地理解為不確定性的程度，區間越寬，越不確定，反之亦反之。
每個item的回報均值都有個置信區間，隨著試驗次數增加，置信區間會變窄（逐漸確定了到底回報豐厚還是可憐）。每次選擇前，都根據已經試驗的結果重新估計每個Item的均值及置信區間。 選擇置信區間上限最大的那個Item。
「選擇置信區間上界最大的那個Item」這句話反映了幾個意思：
如果Item置信區間很寬（被選次數很少，還不確定），那麼它會傾向於被多次選擇，這個是算法冒風險的部分；
如果Item置信區間很窄（備選次數很多，比較確定其好壞了），那麼均值大的傾向於被多次選擇，這個是算法保守穩妥的部分；
UCB是一種樂觀的算法，選擇置信區間上界排序，如果時悲觀保守的做法，是選擇置信區間下界排序。
Yahoo!的科學家們在2010年發表了一篇論文[6]，給UCB引入了特徵信息，同時還把改造後的UCB算法用在了Yahoo!的新聞推薦中，算法名叫LinUCB，劉鵬博士在《計算廣告》一書中也有介紹LinUCB在計算廣告中的應用[7]。
單純的老虎機回報情況就是老虎機自己內部決定的，而在廣告推薦領域，一個選擇的回報，是由User和Item一起決定的，如果我們能用Feature來刻畫User和Item這一對CP，在每次選擇Item之前，通過Feature預估每一個arm（item）的期望回報及置信區間，選擇的收益就可以通過Feature泛化到不同的Item上。
為UCB算法插上了特徵的翅膀，這就是LinUCB最大的特色。
圖5 應用LinUCB算法的Yahoo!首頁LinUCB算法做了一個假設：一個Item被選擇後推送給一個User，其回報和相關Feature成線性關係，這裡的「相關Feature」就是context，也是實際項目中發揮空間最大的部分。
於是試驗過程就變成：用User和Item的特徵預估回報及其置信區間，選擇置信區間上界最大的Item推薦，觀察回報後更新線性關係的參數，以此達到試驗學習的目的。
LinUCB基本算法描述如下：
圖6 LinUCB算法描述對照每一行解釋一下（編號從1開始）：
設定一個參數\alpha，這個參數決定了我們Explore的程度；
開始試驗迭代；
獲取每一個arm的特徵向量xa,t；
開始計算每一個arm的預估回報及其置信區間；
如果arm還從沒有被試驗過，那麼：
用單位矩陣初始化Aa；
用0向量初始化ba；
處理完沒被試驗過的arm；
計算線性參數\theta；
用\theta和特徵向量xa,t計算預估回報，同時加上置信區間寬度；
處理完每一個arm；
選擇第10步中最大值對應的arm，觀察真實的回報rt；
更新Aat；
更新bat；
算法結束。
注意到上面的第4步，給特徵矩陣加了一個單位矩陣，這就是嶺回歸（ridge regression），嶺回歸主要用於當樣本數小於特徵數時，對回歸參數進行修正［8］。
對於加了特徵的Bandit問題，正符合這個特點：試驗次數（樣本）少於特徵數。
每一次觀察真實回報之後，要更新的不止是嶺回歸參數，還有每個arm的回報向量ba。
詳解LinUCB的實現根據論文給出的算法描述，其實很好寫出LinUCB的代碼[9]，麻煩的只是構建特徵。
代碼如下，一些必要的注釋說明已經寫在代碼中。
class LinUCB:
def __init__(self):
self.alpha = 0.25
self.r1 = 1 # if worse -> 0.7, 0.8
self.r0 = 0 # if worse, -19, -21
# dimension of user features = d
self.d = 6
# Aa : collection of matrix to compute disjoint part for each article a, d*d
self.Aa = {}
# AaI : store the inverse of all Aa matrix
self.AaI = {}
# ba : collection of vectors to compute disjoin part, d*1
self.ba = {}
self.a_max = 0
self.theta = {}
self.x = None
self.xT = None
# linUCB
def set_articles(self, art):
# init collection of matrix/vector Aa, Ba, ba
for key in art:
self.Aa[key] = np.identity(self.d)
self.ba[key] = np.zeros((self.d, 1))
self.AaI[key] = np.identity(self.d)
self.theta[key] = np.zeros((self.d, 1))
# 這裡更新參數時沒有傳入更新哪個arm，因為在上一次recommend的時候緩存了被選的那個arm，所以此處不用傳入
# 另外，update操作不用阻塞recommend，可以異步執行
def update(self, reward):
if reward == -1:
pass
elif reward == 1 or reward == 0:
if reward == 1:
r = self.r1
else:
r = self.r0
self.Aa[self.a_max] += np.dot(self.x, self.xT)
self.ba[self.a_max] += r * self.x
self.AaI[self.a_max] = linalg.solve(self.Aa[self.a_max], np.identity(self.d))
self.theta[self.a_max] = np.dot(self.AaI[self.a_max], self.ba[self.a_max])
else:
# error
pass
# 預估每個arm的回報期望及置信區間
def recommend(self, timestamp, user_features, articles):
xaT = np.array([user_features])
xa = np.transpose(xaT)
art_max = -1
old_pa = 0
# 獲取在update階段已經更新過的AaI(求逆結果)
AaI_tmp = np.array([self.AaI[article] for article in articles])
theta_tmp = np.array([self.theta[article] for article in articles])
art_max = articles[np.argmax(np.dot(xaT, theta_tmp) + self.alpha * np.sqrt(np.dot(np.dot(xaT, AaI_tmp), xa)))]
# 緩存選擇結果，用於update
self.x = xa
self.xT = xaT
# article index with largest UCB
self.a_max = art_max
return self.a_max
怎麼構建特徵LinUCB算法有一個很重要的步驟，就是給User和Item構建特徵，也就是刻畫context。在原始論文裡，Item是文章，其中專門介紹了它們怎麼構建特徵的，也甚是精妙。容我慢慢表來。
原始用戶特徵
人口統計學：性別特徵（2類），年齡特徵（離散成10個區間）。
地域信息：遍布全球的大都市，美國各個州。
行為類別：代表用戶歷史行為的1000個類別取值。
原始文章特徵
URL類別：根據文章來源分成了幾十個類別。
編輯打標籤：編輯人工給內容從幾十個話題標籤中挑選出來的原始特徵向量都要歸一化成單位向量。
還要對原始特徵降維，以及模型要能刻畫一些非線性的關係。
用Logistic Regression去擬合用戶對文章的點擊歷史，其中的線性回歸部分為：
擬合得到參數矩陣W，可以將原始用戶特徵（1000多維）投射到文章的原始特徵空間（80多維），投射計算方式：
這是第一次降維，把原始1000多維降到80多維。
然後，用投射後的80多維特徵對用戶聚類，得到5個類簇，文章頁同樣聚類成5個簇，再加上常數1，用戶和文章各自被表示成6維向量。
Yahoo!的科學家們之所以選定為6維，因為數據表明它的效果最好[10]，並且這大大降低了計算複雜度和存儲空間。
我們實際上可以考慮三類特徵：U（用戶），A（廣告或文章），C（所在頁面的一些信息）。
前面說了，特徵構建很有發揮空間，算法工程師們盡情去揮灑汗水吧。
總結一下LinUCB算法，有以下優點：
由於加入了特徵，所以收斂比UCB更快（論文有證明）；
特徵構建是效果的關鍵，也是工程上最麻煩和值的發揮的地方；
由於參與計算的是特徵，所以可以處理動態的推薦候選池，編輯可以增刪文章；
特徵降維很有必要，關係到計算效率。
推薦系統裡面，傳統經典的算法肯定離不開協同過濾。協同過濾背後的思想簡單深刻，在萬物互聯的今天，協同過濾的威力更加強大。協同過濾看上去是一種算法，不如說是一種方法論，不是機器在給你推薦，而是「集體智慧」在給你推薦。
它的基本假設就是「物以類聚，人以群分」，你的圈子決定了你能見到的物品。這個假設很靠譜，卻隱藏了一些重要的問題：作為用戶的我們還可能看到新的東西嗎？還可能有驚喜嗎？還可能有圈子之間的更迭流動嗎？這些問題的背後其實就是在前面提到過的EE問題（Exploit & Explore）。我們關注推薦的準確率，但是我們也應該關注推薦系統的演進發展，因為「推薦系統不止眼前的Exploit，還有遠方的Explore」。
做Explore的方法有很多，Bandit算法是其中的一種流派。前面也介紹過幾種Bandit算法，基本上就是估計置信區間的做法，然後按照置信區間的上界來進行推薦，以UCB、LinUCB為代表。
作為要尋找詩和遠方的Bandit浪漫派算法，能不能和協同過濾這種正統算法結合起來呢？事實上已經有人這麼嘗試過了，叫做COFIBA算法，具體在題目為Collaborative Filtering Bandits[11]和Online Clustering of Bandits[12]）的兩篇文章中有詳細的描述，它就是Bandit和協同過濾的結合算法，兩篇文章的區別是後者只對用戶聚類（即只考慮了User-based的協同過濾），而前者採用了協同聚類（co-clustering，可以理解為item-based和user-based兩種協同方式在同時進行），後者是前者的一個特殊情況。下面詳細介紹一下這種結合算法。
Bandit結合協同過濾很多推薦場景中都有這兩個規律：
每一個推薦候選Item，都可以根據用戶對其偏好不同（payoff不同）將用戶聚類成不同的群體，一個群體來集體預測這個Item的可能的收益，這就有了協同的效果，然後再實時觀察真實反饋回來更新用戶的個人參數，這就有了Bandit的思想在裡面。
舉個例子，如果你父母給你安排了很多相親對象，要不要見面去相一下？那需要提前看看每一個相親對象的資料，每次大家都分成好幾派，有說好的，有說再看看的，也有說不行的；你自己也會是其中一派的一員，每次都是你所屬的那一派給你集體打分，因為他們是和你「三觀一致的人」，「誠不欺我」；這樣從一堆資料中挑出分數最高的那個人，你出去見TA，回來後把實際感覺說給大家聽，同時自己心裡的標準也有些調整，重新給剩下的其它對象打分，打完分再去見，周而復始……
以上就是協同過濾和Bandit結合的思想。
另外，如果要推薦的候選Item較多，還需要對Item進行聚類，這樣就不用按照每一個Item對User聚類，而是按照每一個Item的類簇對User聚類，如此以來，Item的類簇數相對於Item數要大大減少。
COFIBA算法基於這些思想，有人提出了算法COFIBA（讀作coffee bar）[13]，簡要描述如下：
在時刻t，用戶來訪問推薦系統，推薦系統需要從已有的候選池子中挑一個最佳的物品推薦給他，然後觀察他的反饋，用觀察到的反饋來更新挑選策略。 這裡的每個物品都有一個特徵向量，所以這裡的Bandit算法是context相關的。 這裡依然是用嶺回歸去擬合用戶的權重向量，用於預測用戶對每個物品的可能反饋（payoff），這一點和linUCB算法是一樣的。
圖7 COFIBA算法描述對比LinUCB算法，COFIBA算法的不同有兩個：
整體算法過程如下：
核心步驟是，針對某個用戶i，在每一輪試驗時做以下事情：
首先計算該用戶的Bandit參數W（和LinUCB相同），但是這個參數並不直接參與到Bandit的選擇決策中（和LinUCB不同），而是用來更新用戶聚類的；
遍歷候選Item，每一個Item表示成一個context向量了。
每一個Item都對應一套用戶聚類結果，所以遍歷到每一個Item時判斷當前用戶在當前Item下屬於哪個類簇，然後把對應類簇中每個用戶的M矩陣(對應LinUCB裡面的A矩陣)，b向量（payoff向量，對應linUCB裡面的b向量）聚合起來，從而針對這個類簇求解一個嶺回歸參數（類似LinUCB裡面單獨針對每個用戶所做），同時計算其payoff預測值和置信上邊界。
每個Item都得到一個payoff預測值及置信區間上界，挑出那個上邊界最大的Item推出去（和LinUCB相同）。
觀察用戶的真實反饋，然後更新用戶自己的M矩陣和b向量（更新個人的，對應類簇裡其他的不更新）。
以上是COFIBA算法的一次決策過程。在收到用戶真實反饋之後，還有兩個計算過程：
如何更新User和Item的聚類呢？見圖8：
圖8 User和Item聚類更新描述解釋一下圖8。
a. 這裡有6個User，8個Item，初始化時，User和Item的類簇個數都是1。
b1. 在某一輪試驗時，推薦系統面對的用戶是4。推薦過程就是遍歷1～8每個Item，然後看看對應每個Item時，User4在哪個類簇中，把對應類簇中的用戶聚合起來為這個Item預測payoff和CB。這裡假設最終Item5勝出，被推薦出去了。
b2. 在時刻t，Item有3個類簇，需要更新的用戶聚類是Item5對應的User4所在類簇。更新方式：看看該類簇裡面除了User4之外的用戶，對Item5的payoff是不是和user4相近，如果是，則保持原來的連接邊，否則刪除原來的連接邊。刪除邊之後重新構建聚類結果。這裡假設重新構建後原來User4所在的類簇分裂成了兩個類簇：{4,5}和{6}。
C更新完用戶類簇後，Item5對應的類簇也要更新。更新方式是：對於每一個和Item5（被推薦出的那個Item）還存在連接邊的Item j，都去構造一個User的近鄰集合N，這個集合的用戶對Item j有相近的payoff，然後看看N是不是和剛剛更新後的User4所在的類簇相同，是的話，保留Item5和Item j之間的連接邊，否則刪除。這裡假設Item 3和Item 5之間的連接邊被刪除。Item3獨立後給他初始化了一個聚類結果：所有用戶還是一個類簇。
簡單來說就是這樣：
User-based協同過濾來選擇要推薦的Item，選擇時用了LinUCB的思想；
根據用戶的反饋，調整User-based和Item-based的聚類結果；
Item-based的聚類變化又改變了User的聚類；
不斷根據用戶實時動態的反饋來劃分User-Item矩陣。
Exploit-Explore這一對矛盾一直客觀存在，Bandit算法是公認的一種比較好的解決EE問題的方案。除了Bandit算法之外，還有一些其他的explore的辦法，比如：在推薦時，隨機地去掉一些用戶歷史行為（特徵）。
解決Explore，勢必就是要冒險，勢必要走向未知，而這顯然就是會傷害用戶體驗的：明知道用戶肯定喜歡A，你還偏偏以某個小概率給推薦非A。
實際上，很少有公司會採用這些理性的辦法做Explore，反而更願意用一些盲目主觀的方式。究其原因，可能是因為：
網際網路產品生命周期短，而Explore又是為了提升長期利益的，所以沒有動力做；
用戶使用網際網路產品時間越來越碎片化，Explore的時間長，難以體現出Explore 的價值；
同質化網際網路產品多，用戶選擇多，稍有不慎，用戶用腳投票，分分鐘棄你於不顧；
已經成規模的平臺，紅利槓槓的，其實是沒有動力做Explore的。
基於這些，我們如果想在自己的推薦系統中引入Explore機制，需要注意以下幾點：
用於Explore的Item要保證其本身質量，縱使用戶不感興趣，也不至於引起其反感；
Explore本身的產品需要精心設計，讓用戶有耐心陪你玩兒；
深度思考，這樣才不會做出腦殘的產品，產品不會早早夭折，才有可能讓Explore機制有用武之地。
參考文獻：
[1] https://en.wikipedia.org/wiki/Multi-armed_bandit
[2] http://nbviewer.jupyter.org/github/CamDavidsonPilon/Probabilistic-Programming-and-Bayesian-Methods-for-Hackers/blob/master/Chapter6_Priorities/Chapter6.ipynb#
[3] https://en.wikipedia.org/wiki/Thompson_sampling
[4] http://hunch.net/~coms-4771/lecture20.pdf
[5] https://gist.github.com/anonymous/211b599b7 bef958e50af
[6] http://www.research.rutgers.edu/~lihong/pub/Li10Contextual.pdf
[7] 《計算廣告：網際網路商業變現的市場與技術》p253, 劉鵬，王超著
[8] https://en.wikipedia.org/wiki/Tikhonov_regularization
[9] https://github.com/Fengrui/HybridLinUCB-python/blob/master/policy_hybrid.py
[10] http://www.gatsby.ucl.ac.uk/~chuwei/paper/isp781-chu.pdf
[11] http://arxiv.org/abs/1401.8257
[12] http://arxiv.org/abs/1502.03473
[13] https://github.com/qw2ky/CoLinUCB_Revised/blob/master/COFIBA.py
陳開江，天農科技CTO，曾任新浪微博資深算法工程師，考拉FM算法主管，個性化導購App《Wave》和《邊逛邊聊》聯合創始人，多年推薦系統從業經歷，在算法、架構、產品方面均有豐富的實踐經驗。
本文為《程式設計師》原創文章，未經允許不得轉載，更多精彩文章請點擊「閱讀原文」訂閱《程式設計師》。
在線直播 | 人工智慧核心技術解析與應用實戰峰會由CSDN學院傾力打造，力邀一線公司技術骨幹做深度解讀。
本期直播（5月13日）邀請來自阿里巴巴、思必馳、第四範式、一點資訊、58集團、PercepIn等在AI領域有著領先技術研究的一批專家，他們將針對人臉識別、卷積神經網絡、大規模分布式機器學習系統搭建、推薦系統、自然語言處理及SLAM在機器人領域應用等熱點話題進行分享。
限時特惠：299元即可聽6位技術專家的在線分享，加微信小助手 csdncxrs 備註備註「人工智慧」拉您入群。