。今天的文章就來介紹一種結合上下文信息的Bandit方法，LinUCB，它是Contextual bandits算法框架的一種。

本文的原文是雅虎的新聞推薦算法，里面公式是真的挺多的，而且涉及到了兩種linUCB算法，本文只介紹第一種方法。感興趣的同學可以閱讀原文。

LinUCB淺析

這里只簡單介紹一下LinUCB算法的流程，真的是淺析，淺析！

在推薦系統中，通常把待推薦的商品作為MAB問題的arm。UCB是context-free類的算法，沒有充分利用推薦場景的上下文信息，為所有用戶的選擇展現商品的策略都是相同的，忽略了用戶作為一個個活生生的個性本身的興趣點、偏好、購買力等因素，因而，同一個商品在不同的用戶、不同的情景下接受程度是不同的。故在實際的推薦系統中，context-free的MAB算法基本都不會被采用。

與context-free MAB算法對應的是Contextual Bandit算法，顧名思義，這類算法在實現E&E時考慮了上下文信息，因而更加適合實際的個性化推薦場景。

在LinUCB中，每一個arm維護一組參數，用戶和每一個arm的組合可以形成一個上下文特征（上下文特征的特征維度為d），那么對于一個用戶來說，在每個arm上所能夠獲得的期望收益如下：

對于一個老虎機來說，假設手機到了m次反饋，特征向量可以寫作Da(維度為md)，假設我們收到的反饋為Ca(維度為m1)，那么通過求解下面的loss，我們可以得到當前每個老虎機的參數的最優解：

這其實就是嶺回歸嘛，我們很容易得到最優解為：

既然是UCB方法的擴展，我們除了得到期望值外，我們還需要一個置信上界，但是，我們沒法繼續用Chernoff-Hoeffding Bound的定理來量化這個上界，幸運的是，這個上界已經被人找到了：

因此，我們推薦的item就能夠確定了：

可以看到，我們在計算參數及最后推薦結果的時候，用到了以下幾部分的信息：上下文特征x，用戶的反饋c。而這些信息都是可以每次都存儲下來的，因此在收集到了一定的信息之后，參數都可以動態更新，因此我們說LinUCB是一種在線學習方法。

什么是在線學習？個人簡單的理解就是模型的訓練和更新是在線進行的，能夠實時的根據在線上的反饋更新模型的參數。

好了，我們來看一下linUCB算法的流程吧：

上面的ba可以理解為特征向量x和反饋r的乘積。

是否覺得一頭霧水，不用著急，我們通過代碼來一步步解析上面的流程。

2、linUCB代碼實戰

本文的代碼地址為：

https://github.com/princewen/tensorflow_practice/blob/master/recommendation/Basic-Bandit-Demo/Basic-LinUCB.py

設定超參數和矩陣

首先我們設定一些超參數，比如α，正反饋和負反饋的獎勵程度r1，r0，上下文特征的長度d

self.alpha = 0.25self.r1 = 0.6self.r0 = -16self.d = 6# dimension of user features

接下來，我們設定我們的幾個矩陣，比如A和A的逆矩陣，b(x和r的乘積），以及參數矩陣：

self.Aa = {} # Aa : collection of matrix to compute disjoint part for each article a, d*dself.AaI = {} # AaI : store the inverse of all Aa matrixself.ba = {} # ba : collection of vectors to compute disjoin part, d*1self.theta = {}

初始化矩陣

初始化矩陣對應上面的4-7步，A設置為單位矩陣，b設置為0矩陣，參數也設置為0矩陣，注意的是，每個arm都有這么一套矩陣：

def set_articles(self,art): 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))

計算推薦結果

計算推薦結果對應于上面的8-11步，我們直接根據公式計算當前的最優參數和置信上界，并選擇最大的arm作為推薦結果。代碼中有個小trick，及對所有的arm來說，共同使用一個特征，而不是每一個arm單獨使用不同的特征：

def recommend(self,timestamp,user_features,articles): xaT = np.array([user_features]) # d * 1 xa = np.transpose(xaT) 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)))] self.x = xa self.xT = xaT self.a_max = art_max return self.a_max

更新矩陣信息

這對應于上面的12-13步，根據選擇的最優arm，以及得到的用戶反饋，我們更新A和b矩陣：

def update(self,reward): if reward == -1: pass elif reward == 1or 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] = np.linalg.inv(self.Aa[self.a_max]) self.theta[self.a_max] = np.dot(self.AaI[self.a_max],self.ba[self.a_max]) else: # error

寫到這里，本來應該就要結束了，可是腦子里又想到一個問題，為什么可以直接通過加法來更新A矩陣？其實是個很簡單的問題，試著寫出A矩陣中每個元素的計算公式來，問題就迎刃而解了！

結語

總結一下LinUCB算法，有以下優點（來自參考文獻3，自己又增加了一條）：1）由于加入了特征，所以收斂比UCB更快（論文有證明）；2）特征構建是效果的關鍵，也是工程上最麻煩和值的發揮的地方；3）由于參與計算的是特征，所以可以處理動態的推薦候選池，編輯可以增刪文章；4）特征降維很有必要，關系到計算效率。5）是一種在線學習算法。