BPR介绍

Reading time ~1 minute

介绍

本文讨论了个性化排序学习模型的一个通用方法。主要贡献有:

  • 1.描述了通用的优化方法:BPR-OPT,它来自于对最优个性化排序的最大后验估计。我们展示了BPR-OPT在AUC上的分析。
  • 2.对于最大化BPR-OPT,我们提出了通用学习算法LearnBPR,它基于SGD,在训练过程使用bootstrap sampling。我们展示了该算法会优于最优化BPR-OPT时的SGD。
  • 3.我们展示了如何应用learnBPR到两个state-of-art推荐模型中
  • 4.我们的实验经验上展示了个性化排序任务,使用BPR的模型效果要好于其它学习算法

2.相关工作

推荐系统中最流行的模型是kNN CF。传统上,kNN的相似矩阵通过启发法(heuristics)进行计算(例如:Pearson相关度),但在最近的工作中,相似矩阵可以看成是模型参数,可以学到。最近,矩阵分解(MF)在推荐系统中非常流行,可以使用隐式和显式反馈。在最近工作中,SVD也被证明是可以学习特征矩阵。通过SVD学习得到的MF模型,被证明是很容易overfitting。因而提出了正则化学习方法。对于item的预测,Hu等人提出了一个带case weights的正则的最小二乘优化(WR-MF)。case weights可以被用于减小负样本的影响。Hofmann提出了一个概率隐语义模型来进行item推荐。Schmidt-Thieme将该问题转成一个multi-class问题,并使用一个二分类集合来求解它。即使在item预测上的上述所有工作。。。

本文中,我们主要关注模型参数的离线学习。将学习方法扩展到在线学习情况——例如:添加一个新用户,它的历史增加从0到1,2,… feedback事件——对于MF的排序预测已经被学到。相同的fold-in策略可以被用于BPR。

。。。

3.个性化排序(Personalized Ranking)

个性化排序的任务,会为一个用户提供一个items排序列表。这也被称为item推荐。一个示例是,在线电商希望推荐一个个性化的items排序列表,用户会从中购买。在本paper中,我们会研究以下情形:ranking必须从用户的隐式行为(例如:过去的购买)进行infer得到。隐式反馈系统只提供正例数据(正样本)。未被观察到(non-observed)的user-item pairs(例如:一个用户没有购买一个item)会是一个真实负反馈(用户对购买该item不敢兴趣)以及缺失值(用户可能会在将来购买该item)的混合。

3.1 公式化

图1: 在左侧,为已观察到的数据S。直接从S中学习是不可行的,因为只有正反馈被观察到。通常负例数据通过使用0值填充矩阵来生成

假设U是所有users的集合,I是所有items的集合。在我们的场景下,隐式反馈(见图1左侧)。类似这种反馈方式有:电商中的购买行为,视频观看 或者 网页上的点击。推荐系统的任务是提供给用户一个个性化总排序(personlaized total ranking): ,其中必须满足一个总顺序属性:

  • totallity: 总体性
  • antisymmetry: 反对称性
  • transitivity: 传递性

出于便利,我们也定义了:

3.2 问题分析

前面提到,在隐式反馈系统中只有正例(positive classes)被观察到。剩余数据其实是实际负例(negative)与缺失值(missing value)的一个混合。对于应付缺失值问题,最常见的方法是:忽略所有缺失值。通常典型的机器学习模型不能学习任何东西,因为他们两者间不能进行区分这两者(负例和缺失值)。

对于item推荐,常用的方法是,对一个item预测一个个性化分,它可以影响用户对该item的偏好。接着,该items会根据该分值进行排序。对于item推荐的机器学习方法,通常会从S中创建训练数据:给定:

  • 正例: pairs
  • 负例:所有在中的其它组合

如图1所示。接着,模型会拟合该数据。这意味着模型的最优化是为在S中的元素预测value是1, 其余为0。该方法的问题是,在模型中将来进行排序的所有元素()在训练期间都会作为负反馈被表示给机器学习算法。这意味着:如果一个模型具有足够表现力(它可以精准拟合训练数据),它根本不能进行排序,因为它的预测值基本为全0(很稀疏,大部分为0, 全预测对)。为什么这样的机器学习方法可以预测rankings?唯一原因是,有策略阻止overfitting,比如:正则化

我们使用一种不同的方法:通过使用item pairs作为训练数据,然后为正确(correctly)的ranking item进行最优化(而非对单个items进行打分),因为这对于使用负例来替代缺失值要更好。从S中,我们可以尝试为每个user parts()进行重构。如果一个item i被user u观看过,(例如:)——那么,我们假设该user喜欢该item要胜过其它未观察到的items。

图2: 在左侧,已观察到的数据S。我们的方法会在一个items pair间创建特定用户的pairwise偏好。在右侧,加号(+)表示一个用户偏爱item i胜过item j;减号(-)表示他偏爱j胜过i。

例如,在图2中,user 已经观看过item ,但没看过item ,因此我们假设,该用户喜欢要胜过对于被一个用户同时观看过的两个items,我们不能推断更偏好哪个。对于用户未观看过的两个items来说(比如:对于user , item ),相类似,也不能推断哪个更好。为了将这种现象公式化,我们创建训练数据

的语义是,user 被假设成:喜欢i,胜过j。由于是非对称的,负例会被隐式对待。

我们的方法有两个优点:

  • 1.我们的训练数据同时包含了正负例pairs以及缺失值。介于两个未观察到的items间的缺失值是将来必须排序的item pairs。这意味着,从pairwise的角度看,训练数据和测试数据是不相交的。
  • 2.为排序的实际目标函数创建训练数据,例如:观察到的子集被用成训练数据。

4.BPR

在这部分,我们为解决个性化排序任务生成了一种通用方法。对于个性化排序,它包含了通用优化准则:BPR-OPT,它源自对该问题的Bayesian分析,会使用似然函数来为以及模型参数的先验概率。我们展示了排序统计AUC的分析。对于遵循BPR-OPT的学习模型,我们提出了算法learnBPR。最后,我们会展示BPR-OPT和LearnBPR是如何应用到两个state-of-art的推荐算法(MF和adaptive kNN)上。比起常用的训练方法,使用BPR来优化这些模型可以生成更好的rankings。

4.1 BPR优化原则

为所有items 寻找正确的个性化排序的Bayesian公式,是为了最大化以下后验概率,其中表示一个指定模型类别(比如:MF)的参数向量。贝叶斯公式为:

这里,是对于user u希望但隐含的偏好结构。所有用户都假设行为间相互独立。我们也假设:对于一个指定用户,每个items pair的顺序,与每一个其它pair相互独立。因而,对于所有用户,以上的特定用户的似然函数可以首先被重写成:单个密度(densities)和第二个的乘积的组合。

其中是指示函数:

归因于合理的pairwise ordering scheme的总体(totality)和非对称性(antisymmetry),上述公式可以简化为:

到目前为止,通常不会保证获得一个个性化的总顺序。为了得到它,必须满足之前提到过的合理性质(totality、antisymmetry、transitivity)。为了这样做,我们定义了一个用户喜欢item i胜过item j的独立概率:

其中,是logistic sigmoid:

其中是一个特定的关于模型参数向量的real-valued函数,它会捕获user u、item i、item j间的特殊关系。换句话说,我们的通用框架会将建模在u、i、j间的关系的任务表示到一个底层模型类(比如:MF或adaptive kNN)上,它们负责估计。因而,统计方式建模一个个性化总顺序变得可行。出于便利,后续章节我们会跳过来自的参数

至今,我们已经讨论了似然函数。为了补全个性化排序任务的Bayesian建模方法,我们引入了一个通用的先验密度,它是一个零均值、协方差矩阵的正态分布。

下面,为了减小未知超参数的数目,我们设置。现在,我们可以将最大后验估计进行公式化,来生成我们为个性化排序BPR-OPT的通用最优化准则:

其中是模型特定的正则化参数。

4.1.1 AUC最优化分析

有了Bayesian Personalized Ranking(BPR) scheme的公式,很容易理解BPR和AUC间的分析。每个用户的AUC通常被定义为:

这里,平均AUC是:

…(1)

其中, 是归一化常数:

在(1)和BPR-OPT间的分析是很明显的。除了归一化常数外,他们只在loss function上有区别。AUC会使用不可微(non-differentiable)的loss ,它等同于Heaviside function:

作为替代,我们会使用可微loss 。惯例上,当为AUC进行最优化时【3】,替代不可微的Heaviside函数。通常,替代选择是启发式的(heuristic),并且有一个与相类似的相似形状函数(similarly shaped function)(见图3)。在本paper中,受MLE的启发,我们已经已经生成了替代法

图3: 用于最优化AUC的loss function。不可微的Heaviside H(x)通常使用sigmoid 来近似。我们的MLE导数建议使用来替代

4.2 BPR learning算法

在最后一节,我们已经为个性化排序生成了一个最优化原则(optimization criterion)。由于criterion函数是可微的,基于梯度下降(gradient descent)的算法是一个用于最大化的很明智的选择。但正如我们所见,对于我们的问题,标准梯度下降并不适合。为了解决该问题,我们提出了LearnBPR,一个基于SGD的、在训练的三元组上进行bootstrap sampling的算法(见图4)。

图4:基于SGD的boostrapping BRP最优化模型。学习率,正则参数

首先,BPR-OPT的梯度会各自按模型参数求导:

对于梯度下降,两种常用算法是full GD或SGD。在第一种方法中,每一step,会在所有训练数据上进行计算,接着模型参数会使用learning rate 进行更新:

总之,该方法会在“正确”方向上产生一个下降,但收敛很慢。因此,我们在上有条训练三元组(triples),在每个update step上计算full gradient是不可行的。再者,对于使用full DG进行BPR-OPT的最优化、以及在训练pairs上的数据倾斜,会导致很差的收敛。想象下,一个item i,通常是positive的。接着我们在loss中的上有许多项(terms),因为对于许多用户u、item i,会与所有负例items j进行对比(占主导的分类)。因而,模型参数的梯度依赖于i是否在梯度上占据主导地位。这意味着必须选择非常小的learning rates。第二,由于梯度的不同,正则化很难。

另一个流行的方法是SGD。在这种情况下,对于每个triple ,只会执行一个更新。

总之,对于我们的倾斜问题,这是一个好方法。但training pairs遍历的顺序是很严格的。一个常用的方法是,以item-wise或user-wise的方式遍历数据,会产生很差的收敛,因为在相同的user-item pair上有许多连续的更新——例如:对于一个user-item pair (u,i),有许多j 满足

为了解决这个问题,我们建议使用一个SGD算法来随机选择triples(非均匀分布)。该方法在连续更新steps很小时,会选择相同的user-item组合。我们建议使用一个有放回的bootstrap sampling方法,因为在任意step上都可能执行stopping。放弃通过该数据进行full cycles的思想,在我们的case中特别有用,因为样本数目会非常大,为了收敛通常一个full cycle的一部分就足够了。在我们的评估中,我们选择了单个steps的数目,它线性依赖于观察到的正反馈S的数目。

图5展示了一个常用的user-wise SGD、与我们的带bootstrapping的LearnBPR的比较。该模型是16维的BPR-MF。正如你看到的,LearnBPR比user-wise GD收敛更快。

图5: 常见的user-wise SGD与我们的基于bootstrapp sampling的learnBPR算法收敛率的经验比较

4.3 使用BPR来学习模型

对于item推荐,下面我们描述了两个state-of-the-art的模型,以及如何使用我们提出的BPR方法来学习它们。我们已经选择两个不同的模型:MF[5,12]和learned kNN[8]。这两个模型都尝试建模一个用户在一个item上的隐式偏好。它们的预测是对于每个user-item-pair (u,l)的一个实数

由于在我们的optimization中,我们有triples ,我们首先对estimator 进行解耦,并将它定义为:

现在,我们可以应用任意标准的CF模型来预测

需要重点注意的是,尽管在其它工作中我们使用相同的模型,我们会使用不同的准则(criterion)对它们进行最优化。这会产生一个更好的排序,因为我们的准则对于排序任务是最优的。我们的准则不会尝试将单个predictor 看成是单个数字,但作为替换,尝试对两个预测的差进行分类。

4.3.1 MF

预测的问题可以看成是估计一个矩阵:。对目标矩阵X使用MF,可以通过两个低秩矩阵:

其中k是维度/秩 (dimensionality/rank)的近似。在W中的每行 可以被看成是描述一个user u的一个feature vector,相似的,H中的每行描述了一个item i。因而,预测公式可以被写为:

除了点乘外,总之类似于[11]的任意kernel都可以被使用。对于MF的模型参数是。该模型参数可以被看成是隐变量(latent variables),会建模一个用户的未观察到的品味(taste)、以及一个item未观察到的属性(properties)。

通常,通过SVD根据最小二乘获得的X的的最佳近似。对于机器学习任务,SVD会overfits,因此提出了许多其它的MF方法,包含正则化最小二乘最优化,非负因子分解,最大间隔因子分解,等。

对于排序任务,例如:估计一个用户是否偏爱一个item胜过其它item,一个更好的方法是根据BPR-OPT准则来最优化。这可以通过使用提出的LearnBPR来达到。正如之前所述,对于使用LearnBPR的最优化,每个模型参数的梯度是已知的。对于MF模型,导数为:

另外,我们使用三个正则化常数:对应用户特征W; item features H有两个正则常数:被用于只在上用于positive更新;用于在上的negative更新。

4.3.2 Adaptive KNN

最近邻方法在CF中很流行。它依赖items间(item-based)或users间(user-based)的相似度衡量。以下我们描述了item-based方法,通常他们会提供更好的结果,但user-based方法也类似。该思想是:为一个user u预测一个item i,它依赖于item i与该用户过往看过的其它所有items(例如:)间的相似度。通常,中只有k个最相似的items会被看成是K个最近邻。如果items间的相似度被选中,你可以比较在上的所有items。对于item-based KNN的item预测:

其中:是对称的(item-correlation / item-similarity)矩阵。这里,kNN的模型参数为

最常用的选择C的方法是,通过应用一个启发式相似度来衡量,比如:cosine向量相似度:

一个更好的策略是,通过学习来将相似度 C适配该问题。这可以通过直接使用C作为参数,或者如果items数很大,你可以学习一个C的因子分解,其中:。下面,在我们的评估中,我们会使用第一种方法来直接学习C,无需因子分解。

为了对kNN模型最优化来进行ranking,我们使用BPR-OPT准则,并使用LearnBPR算法。为了应用该算法,对应模型参数C的梯度为:

我们有两个正则常数,用于在上更新,用于在上更新。

5.与其它方法的关系

  • WR-MF: Weighted Regularized Matrix Factorization
  • MMMF: Maximum Margin Matrix Factorization

6.评估

在我们的评估中,我们比较了BPR学习与其它学习方法。我们选择两个流行的模型:MF和kNN。MF模型的效果要好于其它模型(比如:Bayesian模型URP、PLSA等 )。在我们的评估中,MF模型使用三种不同方法学到:SVD-MF, WR-MF, BPR-MF。对于kNN,我们比较了Cosine-kNN,以及一个使用BPR方法优化的模型(BPR-kNN)。另外,我们也上报了baseline(most-polular)的结果,它会按用户独立的方式来加权每个item:比如:。另外,我们给出了对于任意非个性化排序方法在AUC ()的理论上界。

6.1 datasets

我们使用两个来自不同应用的数据集。

  • Rossmann dataset:来自在线电商。它包含了1w用户在4k items上的购买历史。总共有426612个购买记录。该任务是预测用户希望在下次购买的一个个性化items列表.
  • Netflix DVD rental dataset: 该数据集包含了用户行为的打分,其中一个用户对电影提供了1-5星的显式评分。如果我们希望以隐式反馈的方式求解,我们可以移除rating。该任务是预测用户是否可能对一个电影进行评分。我们会为用户提供一个最可能打分的个性化排序列表。对于Netflix我们创建了一个subsample: 1w用户,5000 items,包含了565738个rating动作。我们会做子抽样:每个用户至少包含10个items,每个item至少有10个用户。

6.2 评估方法

我们使用留一法(leave-one-out)来进行评估,训练集,测试集。该模型会在上学习,并在上通过平均AUC统计进行评估:

…(2)

其中,每个用户u评估的pairs为:

…(2)

AUC越高表示效果越好。随机猜测法的AUC是0.5,最好为1。

我们会重复10次实验,每次抽取新的train/test splits。超参数通过grid search进行最优化。

6.3 结果

图6

参考

https://arxiv.org/pdf/1205.2618.pdf

MIND召回介绍

#tmall在《Multi-Interest Network with Dynamic Routing forRecommendation at Tmall》开放了它们的召回算法。在matching stage上,提出了Multi-Interest Network with...… Continue reading

capsule介绍二

Published on March 26, 2019

TDM介绍2

Published on March 24, 2019