一文讀懂Bayesian Personalized Ranking算法
原創(chuàng)【51CTO.com原創(chuàng)稿件】就像哲學(xué)有不同的流派一樣，推薦系統(tǒng)的算法設(shè)計(jì)思路也可以分為不同的流派。排序?qū)W習(xí)恰恰就是其中的一種流派。熟悉 RecSys 等推薦系統(tǒng)國(guó)際會(huì)議的從業(yè)者可能會(huì)發(fā)現(xiàn)，自 2010 年以后的若干年內(nèi)，陸續(xù)出現(xiàn)了許多基于排序?qū)W習(xí)的推薦系統(tǒng)算法。從 Bayesian Personalized Ranking (BPR) 到后續(xù)的 Collaborative Less is More Filtering (CLiMF) 以及 GapFM 和 XCLiMF 等算法，在推薦系統(tǒng)領(lǐng)域出現(xiàn)了百家爭(zhēng)鳴，百花齊放的局面。
排序?qū)W習(xí)的設(shè)計(jì)思想與協(xié)同過(guò)濾和矩陣分解以及隨后出現(xiàn)的深度學(xué)習(xí)的主要不同在于排序?qū)W習(xí)把推薦系統(tǒng)看成是一個(gè)排序的問(wèn)題。也就是如何給用戶(hù)推薦商品的問(wèn)題變成了如何在用戶(hù)有可能喜歡的物品集合中對(duì)物品排序的問(wèn)題。這個(gè)過(guò)程中算法不糾結(jié)于對(duì)于用戶(hù)喜歡的物品的評(píng)分進(jìn)行準(zhǔn)確預(yù)測(cè)，而是把物品之間的順序關(guān)系作為優(yōu)化的目標(biāo)。
排序?qū)W習(xí)的英文名稱(chēng)是 Learning to Rank ，根據(jù)優(yōu)化目標(biāo)的不同，共分為三類(lèi)：基于點(diǎn)的排序?qū)W習(xí) ( Point-wise Learning to Rank ) ，基于關(guān)系對(duì)的排序?qū)W習(xí) ( Pair-wise Learning to Rank )，以及基于列表的排序?qū)W習(xí)( List-wise Learning to Rank )?；邳c(diǎn)的排序?qū)W習(xí)本質(zhì)上就是傳統(tǒng)的分類(lèi)算法，例如 SVM ，邏輯回歸等都屬于基于點(diǎn)的排序?qū)W習(xí)，這類(lèi)排序?qū)W習(xí)通常被認(rèn)為是排序?qū)W習(xí)的退化形式;基于關(guān)系對(duì)的排序?qū)W習(xí)強(qiáng)調(diào)的是物品集合中物品兩兩之間的關(guān)系，本章將要展開(kāi)討論的 Bayesian Personalized Ranking 算法就屬于這一類(lèi)算法;基于列表的排序?qū)W習(xí)強(qiáng)調(diào)的是物品集合中物品列表的整體排序關(guān)系，后續(xù)章節(jié)中將要展開(kāi)討論的 Collaborative Less is More Filtering 算法屬于這個(gè)范疇，這類(lèi)算法將物品集合中物品評(píng)分的整體排序關(guān)系作為最終的優(yōu)化目標(biāo)。
Bayesian Personalized Ranking 的整體思路如下：假設(shè)我們現(xiàn)在有 N 個(gè)視頻，每個(gè)視頻有兩種用戶(hù)行為：被用戶(hù)點(diǎn)擊，沒(méi)有被用戶(hù)點(diǎn)擊?，F(xiàn)在設(shè)定用戶(hù)給物品的評(píng)分如下：被用戶(hù)點(diǎn)擊過(guò)的視頻得分 +1 ，從沒(méi)有被用戶(hù)點(diǎn)擊過(guò)的視頻中進(jìn)行采樣得到一部分視頻，這部分視頻被認(rèn)為是用戶(hù)不喜歡的視頻，得分 -1 。
Bayesian Personalized Ranking 首先假設(shè)用戶(hù)對(duì)物品的評(píng)分背后的模型是某個(gè)常見(jiàn)模型，比如矩陣分解模型，也就是用戶(hù)對(duì)物品的評(píng)分 R = U’ * V ，其中 U 是用戶(hù)向量，而 V 是物品向量。算法假定所有得分 +1 的物品和所有得分 -1 的物品，如果用評(píng)分矩陣 R 重新對(duì)物品進(jìn)行打分，原本得分 +1 的物品的新得分將高于原本得分 -1 的物品的新得分。
算法的本質(zhì)訴求是在***可能的滿(mǎn)足原有的 +1 物品得分高于 -1 物品得分的排序?qū)Τ闪⒌那闆r下，倒推出 R 評(píng)分分解后的 U 和 V 向量。***通過(guò)計(jì)算 U和 V 的乘積，得到用戶(hù)對(duì)物品的完整評(píng)分矩陣，完成整個(gè)算法過(guò)程。下面我們?cè)敿?xì)的展開(kāi)算法進(jìn)行討論：
首先定義有序關(guān)系，如果用戶(hù)喜歡物品 I1 而不喜歡物品 I2 ，則存在有序關(guān)系 I1 >u I2 。定義評(píng)分矩陣為參數(shù) theta, 建立需要被優(yōu)化的貝葉斯模型
。用 u 表示有序?qū)?( I1 , I2 )，建立***似然函數(shù)求解公式如下：
，其中
，而
是 sigmoid 函數(shù)
，
。這里定義的貝葉斯模型是一個(gè)一般性的框架，具體的算法模型實(shí)現(xiàn)由
的計(jì)算方式而定。
Bayesian Personalized Ranking 優(yōu)化的指標(biāo)是 AUC 函數(shù)。AUC 函數(shù)在 Bayesian Personalized Ranking 問(wèn)題中被歸約為以下形式：
其中
采用隨機(jī)梯度下降求解參數(shù) 得到：
，
可以看到
就是用戶(hù) u 對(duì)物品 i 和物品 j 的評(píng)分之差。我們已經(jīng)得到了隨機(jī)梯度下降過(guò)程中的參數(shù)計(jì)算方法，在實(shí)際應(yīng)用中只需要將用具體的模型替代即可，比如協(xié)同過(guò)濾，或者矩陣分解。我們給他們分別用代號(hào) BPR-CF 和 BPR-MF 等表示。
現(xiàn)在假定
是由矩陣分解模型計(jì)算得到的。也就是
= U’V =
，帶入隨機(jī)梯度下降公式計(jì)算可得到：
類(lèi)似的，我們可以得到基于協(xié)同過(guò)濾的 BPR 的梯度下降公式。
BPR 因?yàn)槭怯?jì)算兩兩有序?qū)χg的關(guān)系，所以在實(shí)際的計(jì)算過(guò)程中涉及到的數(shù)據(jù)量可能非常龐大。另外，在***進(jìn)行評(píng)分預(yù)測(cè)時(shí)需要進(jìn)行龐大的矩陣運(yùn)算。通常在實(shí)際的計(jì)算過(guò)程中采取了抽樣等方法來(lái)降低計(jì)算量，而不是采用全量數(shù)據(jù)進(jìn)行計(jì)算。
BPR 是推薦系統(tǒng)中基于對(duì)的排序?qū)W習(xí)中的比較重要的一類(lèi)方法，廣泛應(yīng)用在推薦系統(tǒng)的各種實(shí)踐之中。
汪昊， 區(qū)塊鏈公司科學(xué)家，美國(guó)猶他大學(xué)本科/碩士，對(duì)外經(jīng)貿(mào)大學(xué)在職 MBA，在百度、新浪、網(wǎng)易、豆瓣等公司有超過(guò)8年的技術(shù)研發(fā)經(jīng)驗(yàn)，曾擔(dān)任恒昌利通大數(shù)據(jù)部總監(jiān)。擅長(zhǎng)機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、計(jì)算機(jī)圖形學(xué)和科學(xué)可視化等技術(shù)。在 TVCG 和 ASONAM 等國(guó)際會(huì)議和期刊發(fā)表論文 10 篇。本科畢業(yè)論文獲國(guó)際會(huì)議 IEEE SMI 2008 ***論文獎(jiǎng)。
【51CTO原創(chuàng)稿件，合作站點(diǎn)轉(zhuǎn)載請(qǐng)注明原文作者和出處為51CTO.com】
