推薦系統：貝氏個人化推薦 (BPR)
Recommender System : Bayesian Personalized Ranking (BPR)
【前言 : 傳統推薦系統的缺點】
2012年， Steffen Rendle 等人在德國的希德斯海姆機器學習研究實驗室中，發表了一個基於貝氏機率的推薦系統方式論文，該論文在 arxiv 上就能夠搜尋到。這個推薦方式解決了以往常使用的協同過濾(Collaborative Filtering) 只能依靠顯性反饋，比如用戶是否有針對電影評分來做推薦，而不能對隱性反饋(Implicit Feedback)，比如說顧客對這個電影觀看了兩次，但實際上我們並不能確定顧客對該影集的偏好程度，這樣的資料做推薦。此外，就算解決了上述問題，改進過後的模型比如 Matrix Factorization 等系統一下子會反饋許多待推薦的影集，但這些影集的順序是沒有被優化的，但實際上我們會想要對這些待推薦物品做一個排序，而且這個排序是根據個人化的，並非根據整體觀眾的偏好做調整。此時，今天要介紹的 BPR (Bayesian Personalized Ranking) 就能派上用場，該系統是基於後驗機率(Posterior Probability)的方式來估計，並透過 Boostrap 抽樣與隨機梯度下降的方式去優化該機率。整體而言，該模型的宗旨是建立一個基於每個用戶的推薦 Item Set，而 Item Set 中的細部偏好，則根據用戶過去的行為(購買紀錄、觀看紀錄等)來學習。
在了解模型思想與原理以前，我們應該先對傳統的方法有一些認識，當然模型有很多種，但我這邊簡單介紹一下協同過濾，一個被應用最廣泛也相對好理解的推薦系統模式。首先，假設我們有一個數據集長這樣：
上述的數據代表了每一位用戶對不同電影的評分，當然不是每一個電影，畢竟不可能每人都看過所有電影，也因此上述有些數據是缺失的。而這些缺失的值，顯然就是用戶沒看過的電影，我們想要知道的是，如果該用戶看了這部電影，他的評分會是多少，只要可能的評分達到一定程度，舉例來說 5，我們就將其推薦給該用戶，協同過濾就是一個估計這些缺失值的方法。
估計這些缺失值，需要一點調整，這些調整是給予這些電影一點資料，舉個例子，如果我們想基於內容去做推薦，我們可以：
我們透過 Romance 和 Action 兩個方式來描述一部電影，舉例來說，Love at last 幾乎都是 Romance 的成分等。此時，我們可以很簡單地透過一個迴歸模型，去預估每一個人他對 Romance 和 Action 兩個方面的效益程度。比如我們看 Alice，我們可以用 Y(評分) = 5.56 * romance -55 * action 來描述 Alice 對這兩種元素的效益評估，因此，當 Cute puppies of love 被決定是否推薦給 Alice 的時候，我們的答案是 Yes!
因此，協同過濾其實就是在求解以下問題：
從傳統的最小平方問題往外延伸(上述例子加入懲罰項)，我們希望同時過濾兩個以上的參數，以上面電影的例子來說，我們希望針對每一個用戶找到一個最適當的 theta 係數，即他們各自的效益函數。這就是協同過濾的概念。
當然，上面是 Andrew Ng 給出的例子，我們其實可以做各種不同的延伸情境，比如購物商城上面的搜尋次數、Steam 上面的遊戲評分等等。這種作法叫做 Item-based，基於過去使用者評分過的內容來最佳化這個系統，你也可以使用 User-based，計算兩到三個或更多用戶之間的相似度，並把相似度最小的組合彼此看的商品，推薦給組內的其他人，因此你有時候會看到廣告寫說：" 其他用戶也搜尋了某某商品 "，這樣的推薦標語。
然而，缺點正如上面曾經提過的，一是太依靠顯性反饋(Explicit Feedback)，二是並不能對推薦物品做排序。如果一次將一兩百件商品同時推播給用戶，用戶可是要大肆抨擊你的 UX 做得差的！接下來，我們就來講講 BPR 系統對這兩個問題的改進。
【如何做個人化推薦：前置條件】
首先，我們先來研究個人化推薦到底是怎麼一回事，當你說要按照順序推播用戶喜歡的商品時，衡量那個順序的標準是甚麼，這件事必須好好研究。當然，為了兼具泛用性，這裡的資料僅為由 User-Item 組成，並具備缺失職的矩陣，而矩陣內容則是隱性反饋，比如點擊頻率、觀看次數等。
先從簡單的想法開始，假設有一對物品 (i, j)，如果顧客喜歡 i > j ，我們就寫作 i (>u) j ，其中 U 定義為所有用戶的集合，I 定義為所有 Item 集合，我們可以把所有可能的情況寫下來變成：
簡單來說，對於物品 (i, j)， 如果 i ≠ j 則用戶一定會在兩者之間有一個偏好，否則的話必定 i = j，如果用戶喜歡 i > j 且 j > k，用戶必定喜歡 i > k，以上這些是基本假設。接著，因為在 Implicit Feedback 中，只有正樣本會被觀察到，比如說我們的隱反饋是 Youtube 上點讚與否，而剩餘的資料實際上是負樣本(倒讚)或是缺失值(沒點)。我們當然不能直接忽視掉，因為在一般的機器學習模型中，大都是把缺失值作為另外一種類別來處理，但實際上缺失值是代表某些價值的，有一種想法是會統一用 Label 來處理：
但這樣做有個小問題，資料中的元素即使是有意義的，也會被模型輸出成 0 ，這違背了我們希望對推薦物品做排序的目標，比較像是我們過往在做機器學習時設定正則化的方式，顯然不是我們要的。因此，我們採取另一種方式，也就是用 item pairs 來做為訓練資料，並做出一個重要假設：User 對於有下標籤的資料，絕對比沒下標籤的要來得更為偏好。(當然你可以否決這個假設，這邊只是確保你在進行建模時，符合這個假設而已)
以上面來說，對 User 1，我們認為他偏好 item 2 大於 item 1，以此類推可以得到一個 4 * 4 (item_num) 的矩陣，總共我們的資料筆數會變成 item_num * item_num * user_num 這麼多，每一個矩陣也就是 subset，就是我們的訓練資料，我們希望據此假設，來最大化用戶偏好的後驗機率，這就是整個 BPR系統的核心理論與前提。
【BPR演算法流程】
要優化這個演算法，我們必須先建構目標函數：
稍微講解一下，我們知道給定的參數 Θ 下，對於每一位 User，我們要找到 他對所有物品 (i, j) 的優先次序排列，根據 Likelihood Function 我們可以展開得到上面的式子，其中 Ds 代表非缺失值。
我們進一步對用戶是否偏好 i > j 這件是用一個更泛用的方式表達，加入 sigmoid function，讓輸出值介於 0 到 1 之間：
不熟悉 sigmoid function (activation function) 的朋友可以參考：
我們還有一件事沒有解決，也就是一開始參數 Θ 的分布是甚麼？切合題目，既然我們要用 Bayesian Probability，我們就假設該分布是常態分布，並且平均值為 0，但我們還得解決變異數-共變異數矩陣，這邊就變得稍微複雜一些，我們引入超參數(hyperparameter)來模擬該矩陣：
對於 variance-covariance 矩陣轉換成特徵值的部分應該很好理解，接著我們需要用最大後驗機率(Maximum posterior probability)來解決這條方程式，第二條到第三條是透過 Likelihood Function 去改寫並取對數後，會近似對數相加，代入參數後就會得到上面的展開，而上面的 λ 就轉變成類似一個給予模型的懲罰參數(這邊轉換有意思，雖然是用特徵值來模擬的共變矩陣，但經過最大後驗估計以後，等於求解一個帶 l2-regularization 平方的問題)，接著，我們就可以開始求參數 Θ 啦！引入MLE的概念，我們對參數 Θ 求導數：
展開就請自己嘗試，否則一步一步寫會太長，此時你就會發現，整個函數變成了一個凸函數(L2-范數為凸函數)，於是你就可以來引入梯度下降啦：
當然，你希望用其他方式來求解也是可以的，比如我們提過的投影梯度法，但我們這邊就遵照論文所說的方式來做，因此整個演算法的流程變為：
直到收斂為止，我們只需要不斷 Θ 就可以了，而對於收斂，實際上也跟之前的梯度下降方法一樣，你可以設定每次 Θ 更新值的容忍度(tolerance)，以及最大迭代次數來完成這件事。
當然，你也可以用別種估計方式，事實上作者在論文中另外提及了透過Matrix Factorization 與 Adaptive KNN 的估計方法，並且給出了測試同樣一組data set，幾種不同方法所估計的 AUC 差異。
可以看到 BPR-based 的系統會有比較好的表現。
【如何評估推薦系統的表現與使用時機】
上面一小節提到，作者是透過 AUC 這個評估方式來衡量模型的好壞的，那麼為甚麼要用 AUC 來衡量呢? 首先我們必須先了解，AUC 是指 ROC 曲線下的面積，因此，我們必須先了解 ROC 是甚麼。
在信號處理領域，ROC曲線是一種可以不受到成本/效益影響，而給出決策依據的模型評斷方式，換言之就是不會受到基數的影響，舉例來說，MSE會隨著資料量或是每筆資料的量級而有所變化，不會有固定的範圍，相比之下，ROC 的衡量較為直觀，他是來源於 Confusion Matrix 的測度方式：
簡單來說，對於分類的問題上，我們有兩種錯誤：誤把對的分成錯的，或誤把錯的分成對的，此時我們就可以進一步定義：
我們用這兩個東西分別作橫軸與縱軸，就可以畫出一條曲線：
其中，AUC 是曲線下面積，如果整個方格叫做 1.0，那麼上圖 AUC 就是 0.5，大家可以思考一個問題，這個曲線長得甚麼樣，代表甚麼意思？
以上圖為例，AUC = 0.8 的曲線代表，一開始隨著 FPR 的增高，TPR 會更快速上升，這代表我們提升了一點誤判正確的機率，卻可以換來更高的正確判斷率，因此，接近 1 的 AUC 是最好的，而小於 0.5 的 AUC 則代表模型基本是不能用的 (感謝 Jack Shiba 的補充，實際上 AUC 幾乎不可能小於0.5，因為這代表模型還不如亂猜，因此更應該考慮的是，是不是程式碼寫錯了，或是將 AUC 反向解讀的可能性)，這也提供了我們一種不考慮直接成本效益的決策方式，而是用另一種權衡的機制來考量。
不過，因為我們的資料是三維的 (user * item * item)，AUC 會變得有點難理解，實際上應該是寫成：
簡單來說，我們希望最終 AUC 是所有 user 各自 AUC 的平均。
最後來整理一下該模型的一些優缺點，以便於使用者判斷使用時機：
- 優點：給予推薦物品順序，確保用戶能優先看到最喜歡的產品，且能夠對隱性回饋做推薦，效果通常比其他的 MF, KNN 好。
- 缺點：僅著重 User 過去的行為，而非與其他 User 的相似關係，且資料量直接多一個維度、冷啟動問題被放大(剛開始用戶只使用一兩個產品時，就會不斷推薦那兩種產品)
【實戰：Coding 與 分析】
Python 已經有個 implicit feedback 強而有力的 package了：
為了兼顧泛用性與速度，該 package 使用了 Cython 與 OpenMP 做平行運算，因此這邊就不自己手刻了，否則訓練速度要死人。不過個人覺得這邊的 tutorial 與 sample code 沒有做得很好，估計也是團隊不足的問題，因此我們這次就僅用該 package 內建的 data set 來實作他的 BPR 看看。
這邊先上 Code，接著一步一步來講解：
我們使用的內建資料來自 movielens，是用戶對各個電影的評分資料，要注意的是這裡的 input_data 型態是 coo_matrix，如果不是使用內建的資料集，我們要創建這種型別可以從 scipy.sparse.coo_matrix 去轉換得到。coo_matrix 會建立一個稀疏矩陣，只有在 m 列 n 行儲存有資料的元素，其他地方則皆為 0 (不顯示)。如果我們 print 出來，會長成下面這樣：
其中，m 列代表我們的元素， n 行則代表電影(總共有大約13萬部電影)，而右邊的輸出值則代表該用戶對此電影的評價，採取五分制的評分方式，每一個輸出值都會是 integer，因此你會看到電影的 index 有些被跳過了，這是因為使用者沒有對該電影評價的緣故。
當然，因為數據量龐大，實際上不可能這樣寫 Code，應該先訓練好模型之後將之儲存下來，後續再針對每個用戶作個別推薦，不過這邊為了方便觀察，就將所有的資料輸入成 DataFrame。
接著，我們執行腳本，你會看到作者很貼心地加上了進度條：
將 recommend 輸出可以看到，對每個用戶都有對應的一組 Item Set，我們這邊只列出前三名(根據需求調整)，每個 Item 都有一個對應分數，分數的高低代表應該推薦的順序，而根據我們先前的定義，這個分數是該用戶喜歡某產品勝過其他產品的後驗機率(使用sigmoid轉換得到)，範圍介於 0 與 1 之間。
*稍微觀察一下，那個年代比較有名的大概就是野蠻遊戲、寶嘉康蒂等等。
再將 relate 結果輸出，實際上 similar items 也就是反向的 user recommendations，這邊可以直接看結果：
顯而易見，這樣做的好處是，當你的應用場景高度依賴個人化時，會是一個很好的方法，然而當你需要考量他人的喜好來做推薦時，BPR的效果就沒那麼強，因此在使用時，務必先理解你的商業模式。當然，這邊你也可以考量用戶過去看過甚麼，或是用戶是否很密集的觀看某一類型的影集，來對你的模型做出微調，這邊就不再一一實作。最後一個要注意的點是，推薦系統是一個未經過標籤訓練的模型，因此你必須實際使用該模型以後，比較模型使用前後產生的收益差，來做為衡量模型有用的標準與否，而非單純用模型本身的 loss function，這也算是另一個小缺點。
【結尾：推薦系統的難題】
最後，介紹一些推薦系統會遇到的問題。
實際操作推薦系統時，我們會遇到有別於一般機器學習模型的難題，這是導因於系統對資料的高度依賴性以及即時變動性，首先，一個常見的問題就是冷啟動(Cold Start)問題，也就是在剛開始時，幾乎不可能有足夠的資料讓你去建立推薦系統，如果你想保證產品的營運順暢或是消費者體驗，起初的推薦系統就只能用一些 Rule-based 的方法來處理，比如，把熱門排行榜前五名一股腦全部推到用戶的個人頁面上(然而這大部分時候滿有用的，甚至比你花費心力建模來得有用)。
第二個問題是，你必須建立一個 Online Learning 的資料流，也就是隨著時間蒐集即時資訊，並定時更新模型參數，否則，用戶每次看到的推薦商品都是相似類別，這顯然不會是我們想看到的。
此外，如同上一段所說，單純建立 BPR 並不是這麼盡善盡美，先不提大樣本時的訓練問題，單純只針對用戶本身行為，而不考慮其他人的變化這一點，就會出現很多限制。當然，在某些地方 BPR 表現得不錯，這就要跟你的應用場景有關，不過也有些時候，我們舉個例子，Youtube，如果你只考慮用戶過去觀看的影片，而不考慮市場熱門，顯然是不夠的。因此 Youtube 把推薦系統建立得非常複雜，有不同的特徵去訓練模型，這個之後可以再單獨拉出來研究，今天只是一個推薦系統的熱身。
