Abby Yeh
Abby Yeh
May 30 · 7 min read

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)

Taiwan AI Academy

news, tech reviews and supplemental materials

Abby Yeh

Written by

Abby Yeh

Teaching assistants in Taiwan AI Academy, sharing what I learn when I assist students.

Taiwan AI Academy

news, tech reviews and supplemental materials

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade