bpr演算法

❶ 推薦系統中的BPR演算法

一、什麼是BPR演算法？

BPR演算法，全稱為貝葉斯個性化排序（Bayesian Personalized Ranking），是一種常用的推薦系統演算法。它主要利用用戶的隱式反饋，如點擊、收藏等，通過對問題進行貝葉斯分析，得到最大後驗概率來對物品進行排序，從而產生推薦。

二、BPR演算法的基本原理

1.符號定義：

U：用戶集

I：物品集

S：隱式反饋集

u：用戶u的偏好

此關系滿足完整性、反對稱性和傳遞性約束

2.訓練數據的預處理：

首先對隱式反饋矩陣進行預處理，得到訓練數據集

3.兩個基本假設：

BPR演算法的基本思想是利用最大化後驗概率來確定所有item的正確個性化排序

4.BPR的推導：

根據貝葉斯公式得[公式]

因為BPR假設用戶的排序和其他用戶無關，那麼對於任意一個用戶u來說，P(>u)對所有的物品都為一個常數，所以最大化，等價於最大化

這個最大化目標可以分為兩部分，左邊的部分與數據集有關，右邊部分P（θ）與數據集無關

我們先最大化左邊的部分[公式]

根據完整性和反對稱性約束，上式可以簡化成

而對於

這個概率，可以使用下面這個式子來代替:

其中，

事實上[公式] 也可以取其他滿足完整性、反對稱性和傳遞性三個約束條件的其他函數，BPR的最先提出者使用sigmod函數是為了方便接下來的計算

這兒的

同樣可以是任何關於模型參數向量θ的實值函數，前提是該函數能映射出用戶u與物品i和j之間的關系

於是第一部分的優化目標最終變成了

接下來我們再對第二部分P（θ）進行最大化

由於θ的分布是未知的，為了方便我們的計算，不妨假設其服從均值為0，協方差矩陣為的正態分布

於是最大化變成了求解下式的最大值

三、一個BPR演算法的求解實例

在上一節的BPR演算法的推導中，我們假設θ為某個模型的參數向量，本節我們討論當這個模型為矩陣分解模型時，BPR演算法的求解方法

此時我們的預測目標是得到一個預測排序矩陣

這個矩陣可以被分解為

，其中W為|U|×k維矩陣，H為|I|×k維矩陣，k遠小於|U|和|I|

由於BPR是基於用戶維度的，所以對於任意一個用戶u，對應的任意一個物品i我們期望有：

[公式] 表示物品i對於用戶u的排序優先度

此時我們再令

可得到最終需要求解的最大對數後驗估計函數

這個式子對θ求偏導後，可以用梯度上升法或者牛頓法等方法來優化求解模型參數

❷ 矩陣分解的一點總結

------------------------------------------------------------------------------------------------------------------------------------------------

對於推薦系統來說存在兩大場景即評分預測（rating prediction）與Top-N推薦（item recommendation，item ranking）。矩陣分解主要應用於評分預測場景。

推薦系統的評分預測場景可看做是一個矩陣補全的游戲，矩陣補全是推薦系統的任務，矩陣分解是其達到目的的手段。因此，矩陣分解是為了更好的完成矩陣補全任務（欲其補全，先其分解之）。之所以可以利用矩陣分解來完成矩陣補全的操作，那是因為基於這樣的假設：假設UI矩陣是低秩的，即在大千世界中，總會存在相似的人或物，即物以類聚，人以群分，然後我們可以利用兩個小矩陣相乘來還原它。

矩陣分解就是把原來的大矩陣，近似的分解成小矩陣的乘積，在實際推薦計算時不再使用大矩陣，而是使用分解得到的兩個小矩陣。

具體來說就是，假設用戶物品的評分矩陣A是m乘n維，即一共有m個用戶，n個物品.通過一套演算法轉化為兩個矩陣U和V,矩陣U的維度是m乘k，矩陣V的維度是n乘k。

這兩個矩陣的要求就是通過下面這個公式可以復原矩陣A:

說起矩陣分解，我們第一個想起的就是SVD。

SVD分解的形式為3個矩陣相乘，左右兩個矩陣分別表示用戶/項目隱含橘巧因子矩陣，中間矩陣為奇異值矩陣並且是對角矩陣，每個元素滿足非負性，並且逐漸減小。因此我們可以只需要前個K因子來表示它。

但SVD分解要求矩陣是稠密的，也就是說矩陣的所有位置不能有空白。有空白時我們的M是沒法直接去SVD分解的。大家會說，如果這個矩陣是稠密的，那不就是說我們都已經找到所有用戶物品的評分了嘛，那還要SVD幹嘛! 的確，這是一個問題，傳統SVD採用的方法是對評分矩陣中的缺失值進行簡單的補全，比如用全局平均值或者用用戶物品平均值補全，得到補全後的矩陣。接著可以用SVD分解並降燃伍逗維。

雖然有了上面的補全策略，我們的傳統SVD在推薦演算法上還是較難使用。因為我們的用戶數和物品一般都是超級大，隨便就成千上萬了。這么大一個矩陣做SVD分解是非常耗時的。那麼有沒有簡化版的矩陣分解可以用呢？我們下面來看看實際可以用於推薦系統的矩陣分解。

FunkSVD是在傳統SVD面臨計算效率問題時提出來的，既然將一個矩陣皮賣做SVD分解成3個矩陣很耗時，同時還面臨稀疏的問題，那麼我們能不能避開稀疏問題，同時只分解成兩個矩陣呢？也就是說，現在期望我們的矩陣M這樣進行分解：

SVD分解已經很成熟了，但是FunkSVD如何將矩陣M分解為P和Q呢？這里採用了線性回歸的思想。目標是讓用戶的評分和用矩陣乘積得到的評分殘差盡可能的小，也就是說，可以用均方差作為損失函數，來尋找最終的P和Q。

在實際應用中，為了防止過擬合，會加入一個L2的正則化項。加入了正則化系數，需要調參。對於這個優化問題，一般通過梯度下降法來進行優化得到結果。

在FunkSVD演算法火爆之後，出現了很多FunkSVD的改進版演算法。其中BiasSVD算是改進的比較成功的一種演算法。BiasSVD假設評分系統包括三部分的偏置因素：一些和用戶物品無關的評分因素，用戶有一些和物品無關的評分因素，稱為用戶偏置項。而物品也有一些和用戶無關的評分因素，稱為物品偏置項。這其實很好理解。比如一個垃圾山寨貨評分不可能高，自帶這種爛屬性的物品由於這個因素會直接導致用戶評分低，與用戶無關。

一個用戶給一個物品的評分會由四部分相加：

從左到右分別代表：全局平均分、物品的評分偏置、用戶的評分偏置、用戶和物品之間的興趣偏好

BiasSVD增加了一些額外因素的考慮，因此在某些場景會比FunkSVD表現好。

SVD++演算法在BiasSVD演算法上進一步做了增強，這里它增加考慮用戶的隱式反饋。它是基於這樣的假設：用戶除了對於項目的顯式歷史評分記錄外，瀏覽記錄或者收藏列表等隱反饋信息同樣可以從側面一定程度上反映用戶的偏好，比如用戶對某個項目進行了收藏，可以從側面反映他對於這個項目感興趣，具體反映到預測公式為：

學習演算法依然不變，只是要學習的參數多了兩個向量：x和y。一個是隱式反饋的物品向量，另一個是用戶屬性的向量，這樣在用戶沒有評分時，也可以用他的隱式反饋和屬性做出一定的預測。

它是基於這樣的假設：用戶的興趣或者偏好不是一成不變的，而是隨著時間而動態演化。於是提出了timeSVD，其中用戶的和物品的偏置隨著時間而變化，同時用戶的隱含因子也隨著時間而動態改變，在此物品的隱含表示並未隨時間而變化（假設物品的屬性不會隨著時間而改變）。

其中，t為時間因子，表示不同的時間狀態。

通過之前構建目標函數之後，就要用到優化演算法找到能使它最小的參數。優化方法常用的選擇有兩個，一個是隨機梯度下降(SGD)，另一個是交替最小二乘(ALS),在實際應用中，交替最小二乘更常用一些，這也是推薦系統中選擇的主要矩陣分解方法。
找到兩個矩陣P和Q，讓它們相乘後約等於原矩陣R:

P和Q兩個都是未知的，如果知道其中一個的話，就可以按照代數標准解法求得，比如知道Q，那麼P就可以這樣算：

也就是R矩陣乘Q矩陣的逆矩陣就得到了結果，反之，知道了P 再求Q 也一樣，交替最小二乘通過迭代的方式解決這個雞生蛋蛋生雞的難題：
1)、初始化隨機矩陣Q裡面的元素值

2)、把Q矩陣當做已知的，直接用線性代數的方法求得矩陣P

3)、得到了矩陣P後，把P當做已知的，故技重施，回去求解矩陣Q

4)、 上面兩個過程交替進行，一直到誤差可以接受為止

使用交替最小二乘好處：
1.在交替的其中一步，也就是假設已知其中一個矩陣求解另一個時，要優化的參數是很容易並行的；
2.在不是很稀疏的數據集合上，交替最小二乘通常比隨機梯度下降要更快的得到結果。

在很多推薦場景中，我們都是基於現有的用戶和商品之間的一些數據，得到用戶對所有商品的評分，選擇高分的商品推薦給用戶，這是funkSVD之類演算法的做法，使用起來也很有效。但是在有些推薦場景中，我們是為了在千萬級別的商品中推薦個位數的商品給用戶，此時，我們更關心的是用戶來說，哪些極少數商品在用戶心中有更高的優先順序，也就是排序更靠前。也就是說，我們需要一個排序演算法，這個演算法可以把每個用戶對應的所有商品按喜好排序。BPR就是這樣的一個我們需要的排序演算法。

BPR根據像交替最小二乘那樣完成矩陣分解，先假裝矩陣分解結果已經有了，於是就計算出用戶對於每個物品的推薦分數，只不過這個推薦分數可能並不滿足均方根誤差最小，而是滿足物品相對排序最佳

得到了用戶和物品的推薦分數後，就可以計算四元組的樣本中，物品1和物品2的分數差，這個分數可能是正數，也可能是負數，也可能是0。如果物品1和物品2相對順序為1，那麼希望兩者分數之差是個正數，而且越大越好；如果物品1和物品2的相對順序是0，則希望分數之差是負數，且越小越好。
目標函數：

把這個目標函數化簡和變形後，和把AUC當成目標函數是非常相似的，也正是因為如此，BPR模型宣稱該模型是為AUC而生的。

SVDFeature 是由上海交大Apex Data & Knowledge Management Lab(APEX)開發的一個推薦系統工具包。他們提出了一種基於feature 的矩陣分解的框架。

它的目的是有效地解決基於特徵的矩陣分解。新的模型可以只通過定義新的特徵來實現。

這種基於特徵的設置允許我們把很多信息包含在模型中，使得模型更加與時俱進。使用此工具包，可以很容易的把其他信息整合進模型，比如時間動態，領域關系和分層信息。除了評分預測，還可以實現pairwise ranking任務。

SVDFeature的模型定義如下：

輸入包含三種特徵<α，β，γ>，分別是用戶特徵，物品特徵和全局特徵。

SVD ：要求矩陣是稠密的，時間復雜度高。不推薦使用。
FunkSVD ：不在將矩陣分解為3個矩陣，而是分解為2個低秩的用戶項目矩陣，同時降低了時間復雜度。
BiasSVD ：考慮偏置項時使用，也就是用戶的愛好。
SVD++ ：考慮用戶的隱式反饋時使用。主動點評電影或者美食的用戶是少數，也就是說顯示反饋比隱式反饋少，這個時候就可以根據用戶的隱式反饋推薦。
timeSVD ：考慮時間因素時使用。人是善變的，隨著時間的流逝，興趣也會發生變化。
ALS ：考慮建模時間時使用。強烈推薦使用，這也是社交巨頭 Facebook 在他們的推薦系統中選擇的主要矩陣分解演算法。
BPR ：考慮排序結果時使用。
SVDFeature ：當我們有多個特徵時，可以使用。SVDFeature的目的就是解決基於特徵的矩陣分解。

矩陣分解演算法的缺點 ：都沒有解決冷啟動問題

准確率表示預測正確的樣本數占總樣本數的比例。

TP（true positive）：表示樣本的真實類別為正，最後預測得到的結果也為正；
FP（false positive）：表示樣本的真實類別為負，最後預測得到的結果卻為正；
FN（false negative）：表示樣本的真實類別為正，最後預測得到的結果卻為負；
TN（true negative）：表示樣本的真實類別為負，最後預測得到的結果也為負.

精確率表示預測為正樣本的樣本中，正確預測為正樣本的概率。

召回率表示正確預測出正樣本占實際正樣本的概率。

折中了召回率與精確率。

對於評分預測任務，一般都是根據原有的評分數據，利用矩陣分解等方法去擬合原評分，使得優化後的模型可以去預測新的評分，這里就要衡量你預測的評分和實際評分的差異了，指標也很簡單，分為RMSE和MSE。
MSE 是指參數估計值與參數真值之差平方的期望值;
MSE可以評價數據的變化程度，MSE的值越小，說明預測模型描述實驗數據具有更好的精確度。
RMSE ：RMSE是MSE的算術平方根。

AUC 這個值在數學上等價於：模型把關心的那一類樣本排在其他樣本前面的概率。最大是 1，完美結果，而 0.5 就是隨機排列，0 就是完美地全部排錯。
這個非常適合用來評價模型的排序效果，很適合作為BPR的評價指標。得到一個推薦模型後，按照它計算的分數，可以把用戶想要的物品排在最前面。

具體的計算過程可看我的另一篇 文章

其中Rel表示與用戶 u 相關的商品集（測試集）， Rec表示推薦給用戶的前K個列表，二者的交集除以Rec的集合元素個數（其實就是K），得到Precision@K。一般是算出每個用戶的Precision@K，然後取平均值。

其中Rel表示與用戶u相關的商品集（測試集），Rec表示推薦給用戶的前K個列表，二者的交集除以Rec的集合元素個數（也就是測試集中用戶u評過分的商品數），得到Recall@K。一般是算出每個用戶的Recall@K，然後取平均值。

MAP(Mean Average Precision)：單個主題的平均准確率是每篇相關文檔檢索出後的准確率的平均值。

主集合的平均准確率(MAP)是每個主題的平均准確率的平均值。

MAP 是反映系統在全部相關文檔上性能的單值指標。

系統檢索出來的相關文檔越靠前(rank 越高)，MAP就可能越高。如果系統沒有返回相關文檔，則准確率默認為0。
例如：

假設有兩個主題，主題1有4個相關網頁，主題2有5個相關網頁。

某系統對於主題1檢索出4個相關網頁，其rank分別為1, 2, 4, 7；

對於主題2檢索出3個相關網頁，其rank分別為1,3,5。

對於主題1，平均准確率為(1/1+2/2+3/4+4/7)/4=0.83。對於主題2，平均准確率為(1/1+2/3+3/5+0+0)/5=0.45。

則MAP= (0.83+0.45)/2=0.64。

正確檢索結果值在檢索結果中的排名來評估檢索系統的性能。

其中Q是用戶的個數，rank是對於第i個用戶，推薦列表中第一個在ground-truth結果中的item所在的排列位置。

舉個例子：假如檢索三次的結果如下，需要的結果（cat，torus，virus）分別排在3,2,1的話，此系統地MRR為（1/3 + 1/2 + 1)/3 = 11/18

比較復雜，可參考這篇 文章

參考文章：
https://blog.csdn.net/qq_40006058/article/details/89432773
https://blog.csdn.net/weixin_41362649/article/details/82848132
https://blog.csdn.net/qq_19446965/article/details/82079367
https://www.cnblogs.com/pinard/p/9128682.html
https://time.geekbang.org/column/article/5055