BPR：面向隐式反馈数据的贝叶斯个性化排序

[TOC]
# BPR：面向隐式反馈数据的贝叶斯个性化排序
## 摘要
## 引言
## 相关研究
## 个性化排序
　　个性化排序任务是给一个用户提供一个产品排序列表。该任务也被称作项目推荐。例如，一家在线商城想要推荐一个用户想要购买的个性化产品排序列表。本文我们研究了从用户的隐反馈行为（如历史购买记录）中推断排序的场景。隐反馈系统中的问题在于只存在正向偏好。未观察到的用户项目对-例如用户尚未购买某个产品-是真正的负向反馈（用户对购买该产品不感兴趣）和缺失值（用户可能以后会购买该件产品）的混合。
### 形式化定义
　　令$$U$$为所有用户集合，$$I$$为所有产品集合。在本文的推荐场景中使用的是隐式反馈数据$$S\subseteq U \times I$$（如图1左所示）。这种反馈数据的例子有在线商城的购买数据，视频门户网站的浏览数据和网站的点击数据。推荐系统的任务是给用户一个所有产品的个性化排序$$>\_u\subset I^{2}$$，其中$$>\_u$$需要满足如下性质：
```math
\forall i,j\in I:i\neq j\Rightarrow i>_uj\vee j>_ui (totality)
```
```math
\forall i,j\in I:i>_uj\wedge j>_ui\Rightarrow i=j (antisymmetry)
```
```math
\forall i,j,k\in I:i>_uj\wedge j>_uk\Rightarrow i>_uk (transitivity)
```
为方便起见，我们还定义：
```math
I_u^+:=\left \{|i\in I:(u,i)\in S \right \}
```
```math
U_i^+:=\left \{|u\in U:(u,i)\in S \right \}
```
### 问题分析
　　正如我们之前所述，在隐式反馈系统中仅有正样本。剩下的数据是真正的负样本和缺失值的混合。处理缺失值问题的常见方法是忽略所有缺失值，但是常用的机器学习模型就不能学习到任何东西了，因为机器学习模型不能区分这两类样本。
  　常用的产品推荐方法是为一件产品预测一个个性化得分$$\hat{x}\_{ui}$$，反应用户对产品的偏好。然后根据该得分对产品进行排序。产品推荐的机器学习方法[5,10]通常从$$S$$中创造训练数据：给相对$$(u,i)\in S$$正向类标签，所有其它组合$$(U\times I)\backslash S$$为负样本（如图1所示）。然后用模型拟合训练数据。这意味着模型的优化方向是S中的元素为1，不在S中的元素为0。这种方法的问题在于所有应该排在将来购买类的($$(U\times I)\backslash S$$)元素在训练阶段都被作为负反馈。这也意味着一个有着足够表达力的模型（可以准确拟合训练数据）根本不能用来排序。之所以这些机器学习方法可以用来排序的原因在于防止过拟合的策略如正则化方法。
　　这里我们使用了一种不同的方法，将项目对作为训练数据，优化目标是对项目对进行正确排序而不是对单个项目进行评分，因为这更好地表示了问题而不仅仅是以负样本来替代缺失样本。从$$S$$中我们试图每个用户部分$$>\_u$$。如果用户$$u$$曾经浏览过某个项目$$i$$，即$$(u,i)\in S$$，那么我们假设相比于所有其它未观察到的产品用户更偏爱这个产品。例如在图2中用户$$u\_1$$看过产品$$i\_2$$但是没看过产品$$i\_1$$，所以我们假设用户喜欢产品$$i\_2$$胜过$$i\_1$$：$$i\_2>\_ui\_1$$。对于用户均浏览过的产品，我们不能推断出任何偏好。同样，对于那些用户都没有看过的两个产品，我们也不能推断出任何偏好。为了形式化描述这种情形，我们定义训练数据$$D\_S: U\times I\times I$$:
```math
D_S:=\left \{ (u,i,j)|i\in I_U^+ \wedge j\in I\backslash I_u^+\right \}
```
那么$$(u,i,j)\in D\_S$$的语义是用户$$u$$更喜欢$$i$$胜过$$j$$。由于$$>\_u$$是反对称的，因此我们也隐式地考虑了负样本。
　　我们的方法有两大优势：
１.训练数据由正样本，负样本和缺失值构成。两个未观测到的项目的缺失值正好就是以后需要进行排序的项目对。这意味着从成对训练的角度，训练数据$$D\_S$$和测试数据是不相交的。
2．训练数据是为后面的排序目标函数生成的，也就是观测值$$>\_u$$的子集$$D\_S$$被用作训练数据。
## BPR:贝叶斯个性化排序
　　本节我们推导出一个通用方法来解决个性化排序问题。该方法主要包括个性化排序的一般化最优化准则BPR-OPT，该准则由利用Bayesian公式使用似然函数$$p(i>\_uj|\Theta)$$和先验概率$$p(\Theta)$$（模型参数）推导得出。我们给出了其余排序指标AUC（ROC曲线下方的面积）的类比。对于使用BPR-OPT的学习模型，我们提出了算法LEARNBPR。最后，我们展示了BPR-OPT和LEARNBPR可以用于两种最先进的推荐算法矩阵分解和自适应最近邻方法中。利用BPR优化的推荐算法可以生成比传统算法更好的排序结果。
### BPR最优化准则
　　为所有产品$$i\in I$$找到正确的个性化排序的贝叶斯形式化描述是最大化如下的后验概率，其中$$\Theta$$表示任意模型（如矩阵分解）的参数向量：
```math
p(\Theta|>_u)\propto p(>_u|\Theta)p(\Theta)
```
这里$$>\_u$$是用户u的隐偏好结构（排序模型）。模型假设所有用户是相互独立的。我们还假设对于一个特定用户每对产品$$(i,j)$$的排序与其它产品对的顺序独立。因此上述用户特定的似然函数$$p(>\_u|\Theta)$可以首先改写为单密度的积，进一步改写为所有用户$$u\in U$$的积。
```math
\prod_{u\in U}p(>_u|\Theta)=\prod_{(u,i,j)\in U\times I\times I}p(i>_uj|\Theta)^{\delta ((u,i,j)\in D_S)}\cdot (1-p(i>_uj|\Theta))^{\delta ((u,i,j)\notin  D_S)}(1)
```
其中$$\delta$$是指示函数,$$\delta(b)=1$$如果$$b$$为真，否则$$\delta(b)=0$$.
　　由于成对排序方案的总体性和反对称性，上式可以进一步简化为：
```math
\prod _{u\in U}p(>_u|\Theta)=\prod _{(u,i,j)\in D_S}p(i>_uj|\Theta)(2)
```
（译注：(1)式到(2)式的变形主要注意下标，一个是针对全集一个仅仅针对训练集。）
　　到目前为止我们的方法还不能保证得到一个个性化的排序。为此，我们还需要满足已经提到的所有性质（总体性，反对称性和传递性）。我们定义了用户相比产品$$j$$更偏向$$i$$的个体概率为：
```math
p(i>_uj|\Theta):=\sigma(\hat{x}_{uij}(\Theta))
```
其中$$\sigma$$是逻辑乙型函数(logistic sigmoid)：
```math
\sigma(x):=\frac{1}{1+e^{-x}}
```
这里$$\hat{x}\_{uij}(\Theta)$$是任意一个关于模型参数向量$$\Theta$$的实值函数，刻画的是用户$$u$$，产品$$i$$和产品$$j$$的关系。换句话说，本文提出的框架的主要是给用户$$u$$，产品$$i$$和产品$$j$$的关系建模，而底层模型如矩阵分解或自适应$$kNN$$则负责估计$$\hat{x}\_{uij}(\Theta)$$。因此，对个性化排序$$>\_u$$在统计上是可行的。为简单起见，接下来我们先跳过$$\hat{x}\_{uij}$$的参数$$\Theta$$。
　　到目前为止，我们仅仅讨论了似然函数，为了完成对个性化排序任务的贝叶斯建模方法，我们引入了一个一般性的先验密度函数$$p(\Theta)$$，它是一个均值为0，方差协方差矩阵为$$\Sigma \_\Theta$$的正态分布。
```math
p(\Theta)\sim N(0,\Sigma _\Theta)
```
　　接下来，为了减少未知超参数的数量我们令$$\Sigma \_\Theta = \lambda \_\Theta I$$。现在我们可以形式化描述最大后验估计从而推导用于个性化排序的一般性最优化准则BPR-OPT。
```math
BPR-OPT:=ln p(\Theta|>_u)=ln p(>_u|\Theta)p(\Theta)=ln \prod _{(u,i,j)\in D_S} \sigma(\hat(x)_{uij})p(\Theta)=\sum _{(u,i,j)\in D_S}{ln\sigma(\hat{x}_{uij})+lnp(\Theta)}=\sum _{(u,i,j)\in D_S}{ln\sigma(\hat{x}_{uij})-\lambda_{\Theta}\left \| \Theta \right \|^2}
```
其中$$\lambda\_\Theta$$是与模型相关的正则化参数。
#### AUC最优化类比
### BPR学习算法
　　在上一节我们为个性化排序推导出了一个最优化准则。由于该优化准则可微分，我们很容易想到利用梯度下降算法进行最大化。不过后面我们会看到，标准梯度下降不适合解决本问题。为此我们提出了一种基于对训练数据进行bootstrap抽样的随机梯度下降算法LEARNBPR（如图4）。
　　首先BPR-OPT关于模型参数的梯度为：
```math
\frac{\partial BPR-OPT}{\partial \Theta}=\sum_{(u,i,j)\in D_S}\frac{\partial}{\partial \Theta}ln\sigma(\hat{x}_{uij})-\lambda_{\Theta}\frac{\partial}{\partial \Theta}\left \| \Theta\right \|^{2} \propto \sum_{(u,i,j)\in D_S}\frac{-e^{-\hat{x}_{uij}}}{1+e^{-\hat{x}_{uij}}}\frac{\partial}{\partial \Theta}\hat{x}_{uij}-\lambda _{\Theta}\Theta
```
　　梯度下降的两个最常见算法是完全或部分梯度下降。对于前者，完全梯度下降的每一步都会对所有训练数据进行计算，然后依据学习速率$$\alpha$$更新模型参数：
```math
\Theta \Leftarrow \Theta - \alpha \frac{\partial BPR-OPT}{\partial \Theta}
```
　　一般地这种完全梯度下降方法会得到正确方向的梯度，但是收敛速度很慢。由于在$$D\_S$$中有$$O(|S||I|)$$个训练样本，在每一次更新时计算完全梯度是不现实的。此外，训练集的偏态(skewness)也会导致较差的收敛。想象一下某个产品$$i$$一直是正例，那么在丢失函数中就存在很多$$\hat{x}\_{uij}$$的形式，因为对很多用户$$u$$而言，我们将项目$$i$$与所有的负样本$$j$$进行了比较。因此依赖于$$i$$的模型参数会很大程度上影响梯度。这意味着需要选择非常小的学习速率。其次，由于梯度差别较大正则化较为困难。
　　另外一种流行的方法是随机梯度下降（SGD,Stochastic Gradient Descent)。在这种情况下，对于每个元组$$(u,i,j)\in D\_S$$可以进行一次更新。
```math
\Theta \Leftarrow \Theta + \alpha \left ( \frac{e^{-\hat{x}_{uij}}}{1+e^{-\hat{x}_{uij}}}\frac{\partial}{\partial \Theta}\hat{x}_{uij}+\lambda _{\Theta}\Theta \right)
```
　　总体而言这种方法对于我们的有偏数据是一个好方法，但是如何选择数据就至为重要。通常选择训练数据的方法是基于项目或者基于用户，但是这一般会导致收敛性交叉。因为在同一个用户项目对上存在很多连续的更新：即对于一个用户项目对$$(u,i)$$存在很多$$j$$有$$(u,i,j)\in D\_S$$。
　　为了解决该问题我们建议在使用随机梯度下降算法时随机选择三元组（即训练样本服从均匀分布）。这种方法下在连续更新步选择相同的用户项目组合的机率较小。我们建议在每一步使用一种bootstrap的有放回抽样方法。由于我们的方法涉及到的样本规模较大，因此完全遍历所有数据的思想是较为困难的。在实验验证中我们选择的训练步数与正向反馈$$S$$线性相关。
　　图5给出了常用的基于用户的随机梯度下降算法与我们的基于bootstrapping的LEARNBPR比较。我们的模型是特征维度为16的BPR-MF。由图可知LEARNBPR收敛速度远快于基于用户的梯度下降。
### 基于BPR的学习模型
　　接下来我们描述两种产品推荐的最先进算法以及如何用所提的BPR方法学习它们。我们选择的是矩阵分解方法[5,12]和自适应k近邻方法[8]。这两种方法都是对用户对产品的隐偏好进行建模。它们的预测结是对每一个用户项目对$$(u,l)$$都生成一个实数$$\hat{x}\_{ul}$$。
　　由于在BPR中的优化准则是三元组$$(u,i,j)\in D\_S$$，因此我们首先将BPR中的预测器$$\hat{x}\_{uij}$$进行分解，定义为：
```math
\hat{x}_{uij}:=\hat{x}_{ui}-\hat{x}_{uj}
```
　　现在我们可以运用任意标准协同过滤模型来预测$$\hat{x}\_{ul}$$。
　　需要注意的是即使我们使用了与其它方法相同的模型，但是我们的优化准则是不同的。这种专门面向排序任务的优化准则可以得到一个更好的排序。我们的优化准则不会对单个预测器$$\hat{x}\_{ul}$$进行回归而是对两个预测器之差$$\hat{x}\_{ui}-\hat{x}\_{uj}$$进行分类。
#### 矩阵分解
　　预测$$\hat{x}\_{ui}$$的问题可以视作对矩阵进行估计$$X:U\times I$$。通过矩阵分解我们可以将目标矩阵$$X$$近似分解为两个低秩矩阵的乘积：$$W:|U|\times k$$，$$H:|I|\times k$$：
```math
  \hat{X}:=WH^{t}
```
其中k是特征矩阵的维度。$$W$$中的每一行$$w\_u$$可以视作描述一个用户的特征向量，类似地$$H$$中的每一行$$h\_i$$可以视作描述项目$$i$$的特征向量。因此，预测公式也可以写成：
```math
\hat{x}_{ui}=<w_u,h_i>=\sum _{f=1}^{k}w_{uf} \cdot h_{if}
```
　　矩阵分解的模型参数为$$\Theta = (W,H)$$。模型参数也可以视作隐变量，对用户的未观测偏好和产品的未观测特征进行建模。
　　一般地，对X矩阵进行近似通过SVD方法进行实现。对于机器学习任务而言，SVD很容易导致过拟合，因此研究者提出了很多其他的矩阵分解方法包括约束最小二乘优化，非负矩阵分解和最大边缘分解等等。
　　对于排序任务即估计用户是否喜欢一个项目胜过另一个项目而
#### 自适应k近邻
## BPR与其它方法的关系
### 加权正则化矩阵分解（WR-MF）
### 最大边缘矩阵分解（MMMF）
## 实验评价
### 数据集
### 评价方法
### 实验结果和讨论
### 非个性化排序
## 结论</w_u,h_i>

BPR：面向隐式反馈数据的贝叶斯个性化排序

相关博客

最热博客