BPR 與推薦系統排名

Bayesian Personalized Ranking from Implicit Feedback

Photo by rawpixel on Unsplash

使用者在逛購物網站看見推薦商品的時候，往往就只看了前面幾個，而且現在越來越多人都用手機、平板來瀏覽購物網站的情況下，一頁可能也放不了幾個推薦商品，所以這個時候排序就很重要啦。這次要講的是個人化的推薦排名系統，也就是說他和商品收歡迎程度比較沒有關係，而是用個人的對商品的評價來排名使用者會喜歡的商品。

在使用者使用了網站一段時間後，我們可以得到一個矩陣 S (U x I) ，來表示使用者瀏覽過哪些商品，如果使用者 u 看過商品 i，則S[u][i] 為正數，反之則為缺失值。因為通常商品一定有什麼特點吸引使用者，使用者才會點開他，所以可以假設使用者對看過的商品的喜好度大於沒有看過商品。我們就可以為每一個使用者 u 建出矩陣 u(I x I)，看過 i 沒有看過 j 則 u[i][j] 為正數(喜歡 i > j)，反之為負數(喜歡 j > i)，如果都看過貨都沒看過則是缺失值(要預測的資料)。

+: 看過 i 沒看過 j, -: 看過 j沒看過 i, ?: 都看過或都沒看過無法分辨比較喜歡哪一個

此外，我們也可以得到一個集合 Ds 代表所有使用者、比較喜歡的商品、比較不喜歡的商品組合，也就是所有的使用者、看過的商品、沒有看過的商品組合，做為我們的訓練資料。

這時候就可以用 Bayesian Personalized Ranking(BPR) 來為他們做排序了！

— 基本概念 —

BPR 不能算是一個模型，而是一個演算法 LearnBPR, 來解專門對 Ranking 設計的損失函數BPR-OPT，所以首先要了解什麼是 BPR-OPT。

排名的時候，比起預測分數準確度，更重要的是能判斷使用者更喜歡的哪個 商品，所以希望給任意使用者和商品 i, 商品 j，判斷使用者是否喜歡物品 i 大於物品 j 的正確率越高越好。也就是排名系統希望可以最佳化 ROC曲線 所覆概的面積 — AUC，AUC 的值介於 0~1 之間，越大代表越有鑑別度，當AUC>0.5(有鑑別度)，代表 ROC 曲線在斜率為1的線的上面，也就是當正確判斷使用者沒有喜歡 i 大於喜歡 j 的機率相同時，正確判斷使用者喜歡 i 大於喜歡 j 的機率大於隨機判斷時的機率。

AUC 的公式定義為：

I 為 所有的物品，Iu^+為user u有看過的物品，也就是將所有看過的物品 i 與沒有評分過的物品 j來比較，判斷為 i > j 的平均數量。x_uij 是任意函式可以提供使用者 u，對於物品i、j的喜好順序。

但是 AUC 用了不可微分的單位階梯函數 (Heaviside function) ，所以 ROC 曲線其實不是可以微分的平滑曲線，而是像階梯依樣，沒有辦法直接使用梯度下降法最佳化 AUC。

而 BPR-OPT 用 logistic sigmoid 代表分正確的機率來類比 Heaviside function:

圖片來自原始論文[1]，用綠色的線來類比藍色的線。

LearnBPR 的目標就是找出Theta(任意模型的參數) 來最大化：

在假設下述條件的狀況下：

1. 使用者的喜好是互相獨立的
2. 對一個使用者每一對物品 i 、j 的喜好程度是互相獨立的

在給定模型 Theta 的情況下>u的機率可以表示為：

又因為 Log 為遞增函數，所以 BPR-OPT 定義為：

這樣求 BPR-OPT 的微分，然後用梯度下降法來最佳化AUC了：

另外要注意，求解的時候如果照著使用者的順序放入資料會很難收斂，因為大家都喜歡的商品 i 的話，商品 i 會比別的商品產生出更多筆資料，使得模型和商品 i 相關的權重會被更新的頻率會遠大於其他商品，而不容易收斂。作者建議使用 boostrap sampling (可以重複的抽樣方法) 來取代每一個 epoch 都看完一輪全部的資料。

演算法如下：

— LearnBPR + Matrix Factorization 演算法與實作 —

LearnBPR 可以和不同模型結合，而 MF 又是一個用來實作推薦系統的很基本方法，所以就來看他們要怎麼結合吧。

Matrix Factorization (SVD) 就是要找出使用者矩陣 P(U x k) 和物品矩陣 Q(I x k) 來近似我們的目標使用者評分矩陣 X (U x I)。矩陣 W 就可以想成 SVD 的矩陣 P，而 H 可以想成 SVD 的矩陣 Q。

首先我們需要 Ds 集合，也就是上述所說的所有 <使用者 (u)、比較喜歡的商品 (i)、比較不喜歡的商品 (j) > 組合。在這裡不同的是，我們有評分矩陣，所以我們可以改用評分來決定使用者比較喜歡哪的商品：

我們參考之前 SVD 的微分求出 x_uij 的微分後：

我們就可以結合 BPR-OPT 的驗算法 來更新模型的參數了，對每次抽取到的 <u, i, j> 的更新方法就可以寫成下面這樣：

— 結果—

上半部為 rating 中 user 19 給予超過 3 分電影，下半部則是預測 user 19 會喜歡的前五名電影(依序)。

— 總結 —

paper 裡的 evaluation 的結果

LearnBPR 有以下的優點：

1. 可以用在不同模型上使用來梯度下降法最佳化不可微分的 ROC 曲線下的面積的方法
2. 可以讓結合不同模型使其在排名上表現得更好

就像圖中所示，在不同的情境下，嘗試不同模型或置換不同損失函數可能可以得到更好結果。Paper 裡還有結合 k-Nearest-Neighbor 的實作，有興趣可以去看看。

不過，LearnBPR + SVD 也有一些缺點，就是在某一個使用者 u 資料很少的情況下，很難更新到 W[u] ，導致結果很不準確。

— 完整程式—

https://github.com/leafinity/gradient_dscent_svd/blob/master/bpr.ipynb

— 參考資料 —

[1] BPR: Bayesian Personalized Ranking from Implicit Feedback

[2] ROC曲線 (Receiver Operating Characteristic Curve)