協(xié)同過濾(4):論文速讀 Collaborative List-and-Pairwise Filtering from Implicit Feedback

前言

發(fā)表在期刊TKDE 2020上的一篇關(guān)于通用CF推薦的論文
本篇筆記為本人原創(chuàng)，如需轉(zhuǎn)載引用着绊，請務(wù)必在文中附上原鏈接及相應(yīng)說明，包括作者信息（阿瑟）
碼字不易又沾，好心人隨手點個贊
本篇筆記非標(biāo)準(zhǔn)譯文弊仪，其中包含了筆者自己對問題的部分理解，僅供參考杖刷，歡迎學(xué)習(xí)交流
文中涉及到的推薦評估指標(biāo)励饵，可以參見https://zhuanlan.zhihu.com/p/38875570
https://zhuanlan.zhihu.com/p/73335362

摘要

近年來，基于隱式反饋的協(xié)同過濾是重要的研究內(nèi)容滑燃，現(xiàn)有的主流逐對方法(Pairwise)優(yōu)化AUC役听，經(jīng)驗證明，AUC有助于利用二元關(guān)聯(lián)數(shù)據(jù)，但不能解決排序問題典予，并沒有真正關(guān)注 top-k 推薦甜滨。

雖然存在最大化MRR(平均倒數(shù)排序)的List-wise方法，但它效率低下瘤袖，不能特別適用于一般的隱式反饋情況為此衣摩，本文提出了一個新的框架，即協(xié)同列表和成對過濾(CLAPF) 捂敌，旨在將Pair-wise思維引入到List-wise方法中艾扮。具體來說，我們平滑另一個排序指標(biāo)MAP(Mean Average Precision) 占婉，并使用Pair-wise的方法結(jié)合兩個度量指標(biāo)(MAP泡嘴，MRR)來提升top-k 推薦的性能。此外逆济，為了加快收斂速度酌予，還討論了 CLAPF 的采樣方案。它提供了一種在隱式反饋上成對地利用秩偏測度的思想纹腌。

引言

隱式反饋數(shù)據(jù)通常存在缺乏負(fù)反饋的挑戰(zhàn)霎终，特別是在數(shù)據(jù)稀少的情況下。大量的負(fù)例和缺失的正例混合在一起升薯，無法區(qū)分莱褒，這使得許多現(xiàn)有的分類算法不能直接應(yīng)用于該問題。一般來說涎劈，以前處理隱式反饋的方法可以分為兩組 (1)逐點回歸方法(pointwise regression methods)广凸，(2)逐對排序方法(pairwise ranking)。

pointwise:將隱式反饋作為絕對偏好得分蛛枚，通過最小化平方損失來逼近絕對評分.
pairwise 通過優(yōu)化(Area Under the Curve谅海，AUC)來訓(xùn)練推薦模型，這種方法基于相關(guān)物品樣本和不相關(guān)物品樣本之間的成對比較蹦浦。(AUC可以理解為考察模型的分類問題扭吁，看正樣本的分值有多大概率大于負(fù)樣本的分值，與Pairwise本質(zhì)相同)
例如盲镶，Bayesian Personalized Ranking (BPR)是
采用這種成對偏好假設(shè)的最流行的方法之一侥袜。給定觀察到的用戶-項交互(u; i)和未觀察到的用戶-項交互(u; j) ，BPR 假設(shè)用戶 u 對項目 i 的偏好高于物品j溉贿。

研究表明枫吧，成對方法明顯優(yōu)于Point-wise方法，是解決隱式反饋問題的首選方法宇色。

然而九杂，由這些成對方法優(yōu)化的 AUC 指標(biāo)并不能很好地反映推薦列表的質(zhì)量颁湖，因為它不是一個有排名偏差的度量。這意味著大多數(shù)Pairwise方法可能在 top-k 推薦方面表現(xiàn)不佳例隆。雖然已經(jīng)有一些工作通過直接優(yōu)化排序的方法將成對排名一般化為列表排序甥捺，但是很難對列表間的損失建模，而且效率很低：例如裳擎，CLiMF[Recsys 2012]最大化MRR 涎永。此外，研究表明鹿响，這種列表方法通诚畚ⅲ可以顯著提高基于多分類數(shù)據(jù)集的性能，就像顯式數(shù)據(jù)一樣惶我，但是對于二分類數(shù)據(jù)集（隱式數(shù)據(jù)）的建模能力不夠妈倔。

模型方法 Collaborative List-And-Pairwise Filtering

具體來說，我們首先平滑的MAP作為一個低限版本掂恕，使它可以在可比的時間內(nèi)優(yōu)化成對的方法拖陆。MAP 是一個列表式的評估指標(biāo)，通常為用戶提供更有價值的Top推薦懊亡。然后依啰，我們分別將平滑 MAP 和上述 MRR 與成對目標(biāo)函數(shù)相結(jié)合，使這些列表方法更有效地應(yīng)用于隱式反饋的 top-k 推薦斋配。

MAP

AP定義如下：

可以簡化成下面的公式表示形式：

即計算所有正例所在位置的精度情況孔飒。跟上面情況相似，用預(yù)測值做一個平滑改造：

這個地方為什么可以用sigmoid函數(shù)代替呢艰争？：

那么相關(guān)性越高/預(yù)測分值越高坏瞄，排名就會越靠前，影響排序倒數(shù)就會越大甩卓，因此替換是比較合理的鸠匀。
下面就是對AP進行進一步的化簡，文中提到基于琴生不等式和sigmoid函數(shù)凹性來取優(yōu)化逾柿，好像并沒有直接用到

相關(guān)性質(zhì)

這個地方用的主要是In()函數(shù)缀棍，該函數(shù)為凹函數(shù)宅此，因此存在

In(\sum x /N) \geq \sum In(x)/N

的性質(zhì)，上面的推導(dǎo)中也主要用該式找到函數(shù)下界爬范。

最后省略常量得到MAP損失的表示形式

再來對比一下MRR的形式

區(qū)別主要在于第二項父腕，最大化第二項來學(xué)習(xí)其他被觀察項的潛在向量，以提高它們的相關(guān)性分?jǐn)?shù)青瀑，這與 Eq 給出的 CLiMF 方法有很大的不同璧亮。總之斥难，CLiMF 導(dǎo)致促進一個觀察項目和分散其他物品枝嘶，而 Eq。(12)在同時促進和分散兩個觀測項目方面取得了較好的平衡哑诊。

這段也太扯了吧群扶，無法理解，這兩個公式根本就是一個式子呀镀裤，就算符號不一樣竞阐，符號對換一下就行呀，哪有差別呀淹禾，woc

是因為這篇是future issue馁菜，還沒改完么，太不正常了铃岔，都不想看了

CLAPF公式

第一項可以表示成為下面的形式汪疮，這個地方是不是用約等號比較合適？

LMAP 僅依賴于觀察到的物品毁习，忽略探索未觀察到的物品間的相互作用智嚷。在隱性反饋情況下，用戶通常只看到較少的項目纺且，而大多數(shù)項目是未觀察到的項目盏道，因此這種目標(biāo)函數(shù)在一定程度上造成了不足。载碌，我們可以將未觀測到的項目注入到目標(biāo)函數(shù) LMAP 中猜嘱，假設(shè)已觀察項目 i 的位置應(yīng)高于未觀察物品的位置。利用這種技巧嫁艇，我們可以在模型中引入成對排序朗伶，并進一步利用未觀測項目中隱藏的更豐富的交互，期望進一步提高推薦性能步咪。

期刊文章的精髓：重復(fù)描述拉扯篇幅论皆，給我看??了

優(yōu)化損失函數(shù)第二項意味著最大化用戶喜歡正例 k 而不是其他正例 i 的獨立概率; 優(yōu)化第一項可以擴展到最大化用戶喜歡正例i 而不是未觀察的j 的獨立概率,即下面的形式

面對多個排序?qū)Φ呐判騿栴}，受 MPR 框架的啟發(fā)，我們可以通過最大化兩個排序?qū)Φ穆?lián)合分布概率來最大化這兩個目標(biāo)点晴。然后感凤，我們有一個新的標(biāo)準(zhǔn)稱為 CLAPF-MAP：

其中可以把概率形式表示成下面的差值形式

其中的待訓(xùn)練的參數(shù)就是矩陣分解的兩個目標(biāo)矩陣

其中的R()就是L2正則項：

下面給出MRR的優(yōu)化形式：按照上面的替換形式，只是在第二項的位置有點稍微不同粒督，變成這樣的形式 $Pr(R_{ui}<R_{uk},R_{ui}<R_{uj})$ 與MAP對比陪竿，只是提供一種新的排序。

可以理解為MAP的形式一方面考慮了正例與負(fù)例的差異屠橄，同時考慮了正例間的差異萨惑，標(biāo)準(zhǔn)位于正例和負(fù)例中間，做了一個綜合仇矾；而MRR的形式標(biāo)準(zhǔn)在排序的最左側(cè)；一句話理解就是：兩類樣本解总，三個樣本可以有兩種排序方式

前面MRR和MAP公式對比分析的那段話應(yīng)該拿到這兒來說明贮匕，單靠公式根本沒有區(qū)別呀！；ǚ恪？萄巍！＠秃病敦锌！

CLAPF優(yōu)化

最后的推薦評分基于下式得到:

通過SGD對兩個損失函數(shù)進行優(yōu)化

CLAPF 的總時間復(fù)雜度為 O (Tnd) ，其中 T是迭代次數(shù)佳簸，n是用戶數(shù)乙墙。同時，預(yù)測物品上用戶偏好的時間復(fù)雜度為 O(d) 生均，與 BPR 相同听想。因此， CLAPF 和開創(chuàng)性的方法 BPR 的計算復(fù)雜度在效率方面是可比的马胧，這比現(xiàn)有的列表方法快得多汉买。

CLAPF 采樣

與Pair-wise方法相比，CLAPF 對兩個觀察物品(正例)進行了比較佩脊，這對 top-k 推薦中的排序問題有很大的貢獻;
與List-wise方法相比蛙粘，CLAPF 能夠深入挖掘被觀察項和未觀察項之間的聯(lián)系，從而挖掘出用戶和未觀察項之間隱藏的豐富交互威彰。在這一部分中出牧，介紹CLAPF 目標(biāo)函數(shù)下的抽樣問題

抽樣策略在從數(shù)據(jù)中學(xué)習(xí)中起著重要作用。在采樣器中抱冷，動態(tài)負(fù)采樣(DNS)[25]和 (AoBPR)已經(jīng)成為最流行的兩種方法崔列，它們動態(tài)地從當(dāng)前預(yù)測模型產(chǎn)生的排序列表中挑選負(fù)例，并反復(fù)更新包含所有未觀測物品的列表。

然而赵讯，這些負(fù)采樣策略是針對Pairwise中兩兩比較的梯度消失問題而設(shè)計的盈咳。需要設(shè)計適合CLAPF的新采樣策略，需要包含所有觀察項和未觀察項的采樣策略边翼。

模型梯度計算如下：

其中因子R就是前面推導(dǎo)中的公式：

或者是MRR的形式鱼响。當(dāng)更新模型參數(shù)時，我們?yōu)榱思涌焓諗啃枰P(guān)注因子項：

當(dāng)該項接近0時组底，會出現(xiàn)梯度消失的情況(Gradient Vanish)丈积，參數(shù)不會更新。

因此采樣的時候债鸡，我們需要選擇合適的(k,j)對江滨，使得因子項中的Ru盡量小，例如對于

厌均，我們盡量選取較大的預(yù)測值的物品k和j唬滑，這樣的樣本被認(rèn)為是好樣本.
為了進行抽樣，需要首先根據(jù)預(yù)測的相關(guān)性得分生成排序列表棺弊，以幫助從全局?jǐn)?shù)據(jù)中獲得概率值較高/低的樣本晶密。由于現(xiàn)實世界中的大多數(shù)數(shù)據(jù)都遵循長尾分布，因此采用幾何采樣器對排序列表進行采樣模她。

針對CLAPF稻艰，作者提出了Double Sampling Strategy DSS策略

其包括兩部分：負(fù)采樣器(item j)和正采樣器(item k);而對于物品i，是從用戶u觀察過的物品中等概率隨機抽取的侈净。對于k和j則是按照上圖的4步進行的：

第一步：矩陣分解得到用戶和物品的嵌入表示
第二步：隨機選擇一個嵌入維度尊勿，取物品在該維度上的嵌入值，按照該值對物品做降序排序
第三步：對于用戶u取其用戶嵌入畜侦，計算該嵌入和剛得到物品嵌入的關(guān)系
第四步：根據(jù)sgn()的值运怖，進行采樣(按照幾何采樣，從列表頂部向下/底部向上)夏伊。如上圖所示摇展，不同的指標(biāo)采樣的方向不同。

實驗情況

數(shù)據(jù)情況如下：

對于所有的6個數(shù)據(jù)集溺忧，根據(jù)之前常用的訓(xùn)練/測試劃分策略咏连，隨機將觀察到的用戶-項對的一半作為訓(xùn)練數(shù)據(jù)，其余作為測試數(shù)據(jù)鲁森，然后從訓(xùn)練數(shù)據(jù)中為每個用戶隨機選取一個用戶-項對來構(gòu)造一個驗證集祟滴。

重復(fù)上述程序五次，構(gòu)成有五份訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)歌溉。實驗結(jié)果是取這五份測試數(shù)據(jù)上的平均性能垄懂。

實驗結(jié)果方面文中有張整頁的表骑晶，感興趣自己看原文，實驗工作量還挺足的草慧，能夠說明方法效果可行桶蛔。

文中也分析了采樣策略對模型收斂的影響，證明了DSS的有用漫谷。

總結(jié)

這篇工作前半部分的論文寫的相當(dāng)精彩仔雷，分析的也十分到位。但是在模型介紹部分舔示，個人感覺有較多問題碟婆，讓人困惑。而且模型整體看起來也就是Pairwise的擴展惕稻，沒有擺脫BPR結(jié)構(gòu)的限制竖共。總體上模型分析上有很多值得的借鑒的部分俺祠，但MRR和MAP部分作者真的需要再好好修改一下肘迎。

END

本人簡書所有文章均為原創(chuàng)，歡迎轉(zhuǎn)載锻煌，請注明文章出處。百度和CSDN等站皆不可信姻蚓，搜索請謹(jǐn)慎鑒別宋梧。本人習(xí)慣不定期對自己的博文進行修正和更新，因此請訪問本人簡書主頁查看最新文章http://www.reibang.com/u/40d14973d97c

協(xié)同過濾(4):論文速讀 Collaborative List-and-Pairwise Filtering from Implicit Feedback

協(xié)同過濾(4):論文速讀 Collaborative List-and-Pairwise Filtering from Implicit Feedback

前言

摘要

引言

相關(guān)工作

Pairwise Methods

面向排序的CF (Ranking-oriented CF)

相關(guān)定義說明

符號說明

Pairwise方法的優(yōu)化指標(biāo)

CLIMF優(yōu)化指標(biāo)

模型方法 Collaborative List-And-Pairwise Filtering

MAP

CLAPF公式

CLAPF優(yōu)化

CLAPF 采樣

實驗情況

總結(jié)

END