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

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

LinUCB淺析

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

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

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

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

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

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

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

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

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

什么是在線學(xué)習(xí)？個人簡單的理解就是模型的訓(xùn)練和更新是在線進(jìn)行的，能夠?qū)崟r的根據(jù)在線上的反饋更新模型的參數(shù)。

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

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

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

2、linUCB代碼實戰(zhàn)

本文的代碼地址為：

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

設(shè)定超參數(shù)和矩陣

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

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

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

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 = {}

初始化矩陣

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

def set_articles(self,art): for key in art: self.Aa[key] = np.identity(self.d) # 創(chuàng)建單位矩陣 self.ba[key] = np.zeros((self.d,1)) self.AaI[key] = np.identity(self.d) self.theta[key] = np.zeros((self.d,1))

計算推薦結(jié)果

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

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

更新矩陣信息

這對應(yīng)于上面的12-13步，根據(jù)選擇的最優(yōu)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

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

結(jié)語

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