推薦系統的苟且和遠方

苟且和遠方

提到推薦系統，你們會首先想到什麼？

產品和運營們首先想到的就是打標籤，而做過的人還會想到協同過濾（collaborative filter，下面簡稱CF）。

是的，CF幾乎是推薦系統發展史上濃墨重彩的一筆，其背後的思想簡單深刻，在萬物互聯的今天，協同過濾的威力更加強大。CF看上去是一種技術，不如說是一種方法論，不是機器在給你推薦，而是「集體智慧」在給你推薦。

CF的基本假設就是「物以類聚，人以群分」，你的圈子決定了你能見到的物品。這很靠譜，但是卻隱藏了一些重要的問題：作為用戶的我們還可能看到新的東西嗎？還可能有驚喜嗎？還可能有圈子的流動嗎？

是咯，我就知道你會提出這麼精妙的問題，要不然也不會有這篇文章了。畢竟你我都曾經站在高高的谷堆上唱過：「推薦系統不是只有眼前的苟且，還有詩和遠方的田野」。這也是在推薦和廣告界被大量研究的EE問題（Exploit & Explore），Exploit就是眼前的苟且，Explore就是詩和遠方的田野。

做Explore的方法有很多，bandit演算法是其中的一種流派。前面也介紹過幾種bandit演算法，基本上就是估計置信區間的做法，然後按照置信區間的上界來進行推薦，以UCB,LinUCB為代表。

作為要尋找詩和遠方的bandit浪漫派演算法，能不能和CF這種名門望族結合起來呢？事實上已經有人這麼嘗試過了，前陣子在arxiv看到一篇論文，題目是Collaborative Filtering Bandits[1]，arxiv上還有另一篇是同一作者先前的嘗試（Online Clustering of Bandits）[2]，兩者的區別是後者只對用戶聚類（即只考慮了User-based的協同過濾），而前者採用了協同聚類（co-clustering，可以理解為item-based和user-based兩種協同方式在同時進行），後者算是前者的一個特殊情況。今天我們就一起來開拓一下思路，看看Collaborative Filtering Bandits這篇文章是如何把CF和Bandit結合起來的。

bandit怎麼結合CF

很多推薦場景中都有這兩個規律：

1. 相似的用戶對同一個物品的反饋可能是一樣的。也就是對一個聚類用戶群體推薦同一個item，他們可能都喜歡，也可能都不喜歡，同樣地，同一個用戶會對相似的物品反饋相同。這是屬於CF可以解決的問題；

2. 在使用推薦系統過程中，用戶的決策是動態進行的，尤其是新用戶。這就導致無法提前為用戶準備好推薦候選，只能「走一步看一步」，是一個動態的推薦過程。

這篇文章就提出，每一個推薦候選item，都可以根據用戶對其偏好不同（payoff不同）將用戶聚類成不同的群體，一個群體來集體預測這個item的可能的收益，這就有了協同的效果，然後再實時觀察真實反饋回來更新用戶的個人參數，這就有了bandit的思想在裡面。

舉個例子，如果你父母給你安排了很多相親對象，要不要見面去相一下？那需要提前看看每一個相親對象的資料，每次大家都分成好幾派，有說好的，有說再看看的，也有說不行的；你自己也會是其中一派的一員，每次都是你所屬的那一派給你集體打分，因為他們是和你「三觀一致的人」，「誠不欺我」；這樣從一堆資料中挑出分數最高的那個人，你出去見TA，回來後把實際感覺說給大家聽，同時自己心裡的標準也有些調整，重新給剩下的其它對象打分，打完分再去見，周而復始......

以上就是CF和bandit結合的思想。

另外，如果要推薦的候選item較多，還需要對item進行聚類，這樣就不用按照每一個item對user聚類，而是按照每一個item的類簇對user聚類，如此以來，item的類簇數相對於item數要大大減少。

COFIBA演算法

基於這些思想，文中設計的演算法COFIBA（讀作coffee bar），簡要描述如下：

在時刻t，有一個用戶來訪問推薦系統，推薦系統需要從已有的候選池子中挑一個最佳的物品推薦給他，然後觀察他的反饋，用觀察到的反饋來更新挑選策略。

這裡的每個物品都有一個特徵向量，所以這裡的bandit演算法是context相關的。

這裡依然是用嶺回歸去擬合用戶的權重向量，用於預測用戶對每個物品的可能反饋（payoff），這一點和我們上一次介紹的linUCB演算法是一樣的。

對比上一次介紹的LinUCB演算法，COFIBA的不同有兩個：

1. 基於用戶聚類挑選最佳的item（相似用戶集體決策的bandit）

2. 基於用戶的反饋情況調整user和item的聚類（CF部分）

整體演算法過程如下：

對關鍵部分用人話來說就是：

在針對某個用戶i，在每一輪試驗時做以下事情：

1. 首先計算該用戶的bandit參數W（和LinUCB相同），但是這個參數並不直接參与到bandit的選擇決策中（和LinUCB不同），而是用來更新用戶聚類的；

2. 遍歷候選item，每一個item表示成一個context向量了。

3. 每一個item都對應一套用戶聚類結果，所以遍歷到每一個item時判斷當前用戶在當前item下屬於哪個類簇，然後把對應類簇中每個用戶的M矩陣(對應LinUCB裡面的A矩陣)，b向量（payoff向量，對應linUCB裡面的b向量）聚合起來，從而針對這個類簇求解一個嶺回歸參數（類似LinUCB裡面單獨針對每個用戶所做），同時計算其payoff預測值和置信上邊界

4. 每個item都得到一個payoff預測值及置信區間上界，挑出那個上邊界最大的item推出去（和LinUCB相同）

5. 觀察用戶的真實反饋，然後更新用戶自己的M矩陣和b向量（更新個人的，對應類簇里其他的不更新）

以上是COFIBA演算法的一次決策過程。在收到用戶真實反饋之後，還有兩個計算過程：

1. 更新user聚類

2. 更新item聚類

如何更新user和item的聚類呢？文章中給出了一個示意圖：

解釋一下這個圖。

(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矩陣

cofiba演算法也很容易實現，github上就有[3]。論文也從理論和實驗兩方面證明了它的有效性，但是能否在實際項目中用上，仍然存疑，畢竟複雜度不低。

關於EE問題的思考

之所以想寫bandit演算法系列，是因為Exploit-Explore這一對矛盾一直客觀存在，而bandit演算法是公認的一種比較好的解決EE問題的方案。除了bandit演算法之外，還有一些其他的explore的辦法，比如跟xlvector大牛討論時，他就提到一種：在推薦時，隨機地去掉一些用戶歷史行為（特徵）。

解決Explore，勢必就是要冒險，勢必要走向未知，而這顯然就是會傷害用戶體驗的：明知道用戶肯定喜歡A，你還偏偏以某個小概率給推薦非A。

實際上，很少有公司會採用這些理性的辦法做Explore，反而更願意用一些盲目主觀的方式。究其原因，可能是因為：

1. 互聯網產品生命周期短，而Explore又是為了提升長期利益的，所以沒有動力做；

2. 用戶使用互聯網產品時間越來越碎片化，Explore的時間長，難以體現出Explore 的價值；

3. 同質化互聯網產品多，用戶選擇多，稍有不慎，用戶用腳投票，分分鐘棄你於不顧。

4. 已經成規模的平台，紅利杠杠的，其實是沒有動力做Explore的；

基於這些，我們如果想在自己的推薦系統中引入Explore機制，需要注意以下幾點：

1. 用於Explore的item要保證其本身質量，縱使用戶不感興趣，也不至於引起其反感；

2. Explore本身的產品需要精心設計，讓用戶有耐心陪你玩兒；

3. 深度思考，這樣才不會做出腦殘的產品，產品不會早早夭折，才有可能讓Explore機制有用武之地。

好了，讓我們再唱一遍，結束本系列：

推薦不止眼前的苟且，還有詩和遠方的田野

[1] http://arxiv.org/abs/1401.8257

[2] http://arxiv.org/abs/1502.03473

[3] https://github.com/qw2ky/CoLinUCB_Revised/blob/master/COFIBA.py

推薦關注微信公眾號【ResysChina】，中國最專業的個性化推薦技術與產品社區。更多內容會首發在微信公眾號。

猜你喜歡：LinUCB演算法

推薦閱讀：