UCB演算法升職記——LinUCB演算法

UCB再回顧

上回書說到，UCB這個小夥子在做EE(Exploit-Explore)的時候表現不錯，只可惜啊，是一個不關心組織的上下文無關(context free)bandit演算法，它只管埋頭幹活，根本不觀察一下面對的都是些什麼樣的arm。

進一步送UCB去深造之前，我們再把UCB演算法要解決的問題描述一下：

面對固定的K個item（廣告或推薦物品），我們沒有任何先驗知識，每一個item的回報情況完全不知道，每一次試驗要選擇其中一個，如何在這個選擇過程中最大化我們的回報？

UCB解決這個Multi-armed bandit問題的思路是：用置信區間。置信區間可以簡單地理解為不確定性的程度，區間越寬，越不確定，反之亦反之。

每個item的回報均值都有個置信區間，隨著試驗次數增加，置信區間會變窄（逐漸確定了到底回報豐厚還是可憐）。

每次選擇前，都根據已經試驗的結果重新估計每個item的均值及置信區間。

選擇置信區間上限最大的那個item。

「選擇置信區間上界最大的那個item」這句話反映了幾個意思：

1. 如果item置信區間很寬（被選次數很少，還不確定），那麼它會傾向於被多次選擇，這個是演算法冒風險的部分；

2. 如果item置信區間很窄（備選次數很多，比較確定其好壞了），那麼均值大的傾向於被多次選擇，這個是演算法保守穩妥的部分；

3. UCB是一種樂觀的演算法，選擇置信區間上界排序，如果時悲觀保守的做法，是選擇置信區間下界排序。

給UCB插上特徵的翅膀

UCB還是很有前途的，所以演算法大神們還是有心提攜它一把。

這不，Yahoo!的科學家們在2010年發表了一篇論文[1]，給UCB指了一條明路，同時還把改造後的UCB演算法用在了Yahoo!的新聞推薦中，深造後的UCB演算法現在title叫LinUCB。

這篇論文很有名，很多地方都有引用，在劉鵬博士的著作《計算廣告》中也專門講到了[2]。我知道，大家都很忙，尤其是面對英文論文，尤其是論文中有大量的數學公式，所以「沒時間」去閱讀它，所以這裡我就轉述一下這個演算法的改造過程，以期望大家在百忙之中能夠領會其精神。

單純的老虎機，它回報情況就是老虎機自己內部決定的，而在廣告推薦領域，一個選擇的回報，是由User和Item一起決定的，如果我們能用feature來刻畫User和Item這一對CP，在選擇之前通過feature預估每一個arm的期望回報及置信區間，那就合理多了。

為UCB插上特徵的翅膀，這就是LinUCB最大的特色。

LinUCB演算法做了一個假設：一個Item被選擇後推送給一個User，其回報和相關Feature成線性關係，這裡的「相關feature」就是context，也是實際項目中發揮空間最大的部分。

於是試驗過程就變成：用User和Item的特徵預估回報及其置信區間，選擇置信區間上界最大的item推薦，觀察回報後更新線性關係的參數，以此達到試驗學習的目的。

LinUCB基本演算法描述如下：

對照每一行解釋一下：

0. 設定一個參數alpha，這個參數決定了我們Explore的程度

1. 開始試驗迭代

2. 獲取每一個arm的特徵向量xa,t

3. 開始計算每一個arm的預估回報及其置信區間

4. 如果arm還從沒有被試驗過，那麼：

5. 用單位矩陣初始化Aa

6. 用0向量初始化ba，

7. 處理完沒被試驗過的arm

8. 計算線性參數theta

9. 用theta和特徵向量xa,t計算預估回報, 同時加上置信區間寬度

10. 處理完每一個arm

11. 選擇第9步中最大值對應的arm，觀察真實的回報rt

12. 更新Aat

13. 更新bat

14. 演算法結束

本來，按照上面的步驟已經可以寫代碼完成KPI了，但是我們都是愛學習的小夥伴，其中一些關鍵的地方還得弄得更明白些。

注意到上面的第4步，給特徵矩陣加了一個單位矩陣，這就是嶺回歸（ridge regression），嶺回歸主要用於當樣本數小於特徵數時，對回歸參數進行修正［3］。

對於加了特徵的bandit問題，正符合這個特點：試驗次數（樣本）少於特徵數。

每一次觀察真實回報之後，要更新的不止是嶺回歸參數，還有每個arm的回報向量ba。

實現LinUCB

根據論文給出的演算法描述，其實很好寫出LinUCB的代碼[5]，麻煩的只是構建特徵。

代碼如下，一些必要的注釋說明已經寫在代碼中。

class LinUCB:nn def __init__(self):nn self.alpha = 0.25 nn self.r1 = 1 # if worse -> 0.7, 0.8nn self.r0 = 0 # if worse, -19, -21nn # dimension of user features = dnn self.d = 6nn # Aa : collection of matrix to compute disjoint part for each article a, d*dnn self.Aa = {}nn # AaI : store the inverse of all Aa matrixnn self.AaI = {}nn # ba : collection of vectors to compute disjoin part, d*1nn self.ba = {}nn nn self.a_max = 0nn nn self.theta = {}nn nn self.x = Nonenn self.xT = Nonenn # linUCBnnnn def set_articles(self, art):nn # init collection of matrix/vector Aa, Ba, bann for key in art:nn self.Aa[key] = np.identity(self.d)nn self.ba[key] = np.zeros((self.d, 1))nn self.AaI[key] = np.identity(self.d)nn self.theta[key] = np.zeros((self.d, 1))nn nn """nn 這裡更新參數時沒有傳入更新哪個arm，因為在上一次recommend的時候緩存了被選的那個arm，所以此處不用傳入nn nn 另外，update操作不用阻塞recommend，可以非同步執行nn """ nn def update(self, reward):nn if reward == -1:nn passnn elif reward == 1 or reward == 0:nn if reward == 1:nn r = self.r1nn else:nn r = self.r0nn self.Aa[self.a_max] += np.dot(self.x, self.xT)nn self.ba[self.a_max] += r * self.xnn self.AaI[self.a_max] = linalg.solve(self.Aa[self.a_max], np.identity(self.d))nn self.theta[self.a_max] = np.dot(self.AaI[self.a_max], self.ba[self.a_max])nn else:nn # errornn passnn nn """nn 預估每個arm的回報期望及置信區間nn """nn def recommend(self, timestamp, user_features, articles):nn xaT = np.array([user_features])nn xa = np.transpose(xaT)nn art_max = -1nn old_pa = 0nn nn # 獲取在update階段已經更新過的AaI(求逆結果)nn AaI_tmp = np.array([self.AaI[article] for article in articles])nn theta_tmp = np.array([self.theta[article] for article in articles])nn art_max = articles[np.argmax(np.dot(xaT, theta_tmp) + self.alpha * np.sqrt(np.dot(np.dot(xaT, AaI_tmp), xa)))]nnnn# 緩存選擇結果，用於updatenn self.x = xann self.xT = xaTnn # article index with largest UCBnn self.a_max = art_maxnn nn return self.a_max n

怎麼構建特徵

LinUCB演算法有一個很重要的步驟，就是給User和Item構建特徵，也就是刻畫context。在原始論文里，Item是文章，其中專門介紹了它們怎麼構建特徵的，也甚是精妙。容我慢慢表來。

• 原始用戶特徵有：

人口統計學：性別特徵（2類），年齡特徵（離散成10個區間）

地域信息：遍布全球的大都市，美國各個州

行為類別：代表用戶歷史行為的1000個類別取值

• 原始文章特徵：

URL類別：根據文章來源分成了幾十個類別

編輯打標籤：編輯人工給內容從幾十個話題標籤中挑選出來的

原始特徵向量都要歸一化成單位向量。

還要對原始特徵降維，以及模型要能刻畫一些非線性的關係。

用Logistic Regression去擬合用戶對文章的點擊歷史，其中的線性回歸部分為：

擬合得到參數矩陣W，可以將原始用戶特徵（1000多維）投射到文章的原始特徵空間（80多維），投射計算方式：

這是第一次降維，把原始1000多維降到80多維。

然後，用投射後的80多維特徵對用戶聚類，得到5個類簇，文章頁同樣聚類成5個簇，再加上常數1，用戶和文章各自被表示成6維向量。

Yahoo!的科學家們之所以選定為6維，因為數據表明它的效果最好[4]，並且這大大降低了計算複雜度和存儲空間。

我們實際上可以考慮三類特徵：U（用戶），A（廣告或文章），C（所在頁面的一些信息）。

前面說了，特徵構建很有發揮空間，演算法工程師們盡情去揮灑汗水吧。

總結

總結一下LinUCB演算法，有以下優點：

1. 由於加入了特徵，所以收斂比UCB更快（論文有證明）；

2. 特徵構建是效果的關鍵，也是工程上最麻煩和值的發揮的地方；

3. 由於參與計算的是特徵，所以可以處理動態的推薦候選池，編輯可以增刪文章；

4. 特徵降維很有必要，關係到計算效率。

另外，可能有人已經發現了，bandit演算法有個問題，就是要求同時參與候選的arm數量不能太多，幾百上千個差不多了，更多就不好處理了，如果arm更多的時候，recommend也是非同步計算，這塊可以深思一下，儘是工程上的事。

當年在學習Yahoo!這篇介紹LinUCB論文時，還一一看了其參考文獻，比如這兩篇，一個是關於特徵處理的[6]，一個是關於降維和數據分析的[7]，有興趣也可以看看，這裡就不畫重點了，高考不考。

[1] http://www.research.rutgers.edu/~lihong/pub/Li10Contextual.pdf

[2] 《計算廣告：互聯網商業變現的市場與技術》p253, 劉鵬，王超著

[3] https://en.wikipedia.org/wiki/Tikhonov_regularization

[4] http://www.gatsby.ucl.ac.uk/~chuwei/paper/isp781-chu.pdf

[5] https://github.com/Fengrui/HybridLinUCB-python/blob/master/policy_hybrid.py

[6] http://www.wwwconference.org/www2009/proceedings/pdf/p691.pdf

[7] http://www.gatsby.ucl.ac.uk/~chuwei/paper/isp781-chu.pdf

本文首發微信公眾號【ResysChina】，中國最專業的個性化推薦技術社區。

猜你喜歡：「專治選擇困難症——bandit演算法」

推薦閱讀：