推薦系統遇上深度學習(十三)--linUCB方法淺析及實現

推薦系統遇上深度學習(十三)--linUCB方法淺析及實現

來自專欄大數據分析挖掘13 人贊了文章

作者:石曉文 Python愛好者社區專欄作者

個人公眾號:小小挖掘機

博客專欄:wenwen

上一篇中介紹了Bandit演算法,並介紹了幾種簡單的實現,如 Epsilon-Greedy演算法,Thompson sampling演算法和UCB演算法。

但是傳統的實現方法存在很大的缺陷,主要是缺乏用附加信息刻畫決策過程的機制。今天的文章就來介紹一種結合上下文信息的Bandit方法,LinUCB,它是Contextual bandits演算法框架的一種。

本文的原文是雅虎的新聞推薦演算法:arxiv.org/pdf/1003.0146。裡面公式是真的挺多的,而且涉及到了兩種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代碼實戰

本文的代碼地址為:github.com/princewen/te

設定超參數和矩陣

首先我們設定一些超參數,比如α,正反饋和負反饋的獎勵程度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 == 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] = 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)是一種在線學習演算法。

參考文獻

1、arxiv.org/pdf/1003.0146

2、zhuanlan.zhihu.com/p/35

3、blog.csdn.net/legendavi

4、zhuanlan.zhihu.com/p/32

推薦閱讀:

台大林軒田機器學習課第廿三講筆記:混合法與裝袋法 (blending & bagging)
機器學習中的數學基礎(線性代數)
機器翻譯不可不知的Seq2Seq模型
打開機器學習的黑盒——卷積神經網路原理介紹
牆後的所有姿勢,全被「瞎眼」AI透視

TAG:機器學習 | 深度學習DeepLearning | 推薦系統 |