一、BPR [2009]

《BPR: Bayesian Personalized Ranking from Implicit Feedback》

1. 内容推荐是很多信息系统中的一项重要任务，例如像 Amazon 这样的在线购物网站为每个客户提供用户可能感兴趣商品的个性化推荐。其它例子像 YouTube 这样的视频门户网站，为用户推荐电影。个性化对于内容提供商和用户都很有吸引力，前者可以增加销售额或者浏览量，后者可以更容易找到有趣的内容。这里我们专注于 item 推荐。 item 推荐任务是为一组 item 创建 user-specific 排序。用户对 item 的偏好是从用户历史行为中获悉的，如用户的购买历史、观看历史等等。

   推荐系统是一个活跃的研究课题。最近的工作是关于用户提供显式反馈的场景，例如在评分方面。然而，在现实世界的场景中，大多数反馈不是显式而是隐式的。隐式反馈会自动跟踪，例如跟踪点击次数、浏览次数、购买次数等等。隐式反馈的收集要容易的多，因为用户不需要显式表达他的口味。事实上，几乎任何信息系统都已经可以使用隐式反馈，例如 web 服务器在日志文件中记录的任何页面浏览行为。

   在论文 《BPR: Bayesian Personalized Ranking from Implicit Feedback》 中，作者提出了一种用于学习个性化排序模型的通用方法。这项工作的主要贡献是：

   • 论文提出了从最大后验估计导出的、用于最佳个性化排序的通用优化标准 BPR-Opt。论文展示了 BPR-Opt 与 AUC 的类比。

   • 为了最大化 BPR-Opt，论文提出了通用学习算法 LearnBPR，它基于随机梯度下降、以及对训练三元组的 bootstrap 采样。论文表明作者的算法在优化 BPR-Opt 方面优于标准的梯度下降方法。

   • 论文展示了如何将 LearnBPR 应用于两个 SOTA 的推荐模型族。

   • 论文的实验表明，对于个性化排序任务，使用 BPR 学习的模型优于其它学习方法。

2. 相关工作：

   • 推荐系统最流行的模型是 k-nearest neighbor: KNN 协同过滤。传统上，KNN 的相似度矩阵是通过启发式计算的，例如 Pearson 相关性。但是在最近的工作 《Factorization meets the neighborhood: a multifaceted collaborative filtering model》 中，相似度矩阵被视为模型参数，并为任务专门学习。

   • 最近，矩阵分解 matrix factorization: MF 在隐式反馈和显式反馈的推荐系统中变得非常流行。在早期的工作 《Incremental singular value decomposition algorithms for highly scalable recommender systems》 中，作者已经提出奇异值分解（singular value decomposition: SVD）来学习特征矩阵。

     SVD 学习的 MF 模型已经被证明非常容易过拟合，因此人们使用正则化技术。对于 item 预测，《Collaborative filtering for implicit feedback datasets》 和 《One-class collaborative filtering》 提出了一种带有样本权重正则化的最小二乘优化（WR-MF）。样本权重可用于减少负样本的影响。

   • 《Latent semantic models for collaborative filtering》 提出了一种用于 item 推荐的概率潜在语义模型。《Compound classification models for recommender systems》 将问题转变为多分类问题，并使用一组二分类器解决它。

   尽管上面讨论的所有 item 预测工作都是在个性化排序数据集上进行评估的，但是这些方法都没有为排序任务直接优化模型参数。相反，他们优化模型参数从而预估用户是否会选择某个 item。在我们的工作中，我们导出了一个基于 item pair （即特定用户的两个 item 之间的顺序）的个性化排序优化标准。我们将展示如何根据该标准优化 MF 或者自适应 kNN 等 SOTA 模型，从而提供比常规的学习方法更好的排序质量。

   我们还详细讨论了 《Collaborative filtering for implicit feedback datasets》 和 《One-class collaborative filtering》 的WRMF 方法、以及

   《Improving maximum margin matrix factorization》 的 maximum margin matrix factorization: MMMF 方法与我们方法之间的关系。我们还将讨论我们的优化准则和 AUC 优化准则的关系。

   在本文中，我们专注于模型参数的离线学习。在评分预测相关的任务中，《Online updating regularized kernel matrix factorization models for large-scale recommender systems》 已经为 MF 研究了将学习方法扩展到在线学习的场景（如，添加一个新用户，然后新用户的历史行为记录从 0 增加到 1,2,...）。相同的方法可用于 BPR。

   还有关于学习使用非协同过滤模型进行排序的相关工作（《Efficient inference for distributions on permutations》，《《Multiobject tracking with representations of the symmetric group》）。一个方向是对排列的分布进行建模。 《Learning to rank using gradient descent》 针对排序任务，使用梯度下降优化了一个神经网络模型。所有这些方法只学习一个排序，即它们是非个性化的。相反，我们的模型是学习个性化排序的协同过滤模型，即每个用户一个单独的排序。在我们的评估中，我们根据实验表明，在典型的推荐设置中，我们的个性化 BPR 模型甚至优于非个性化排序的理论上限。

3. 个性化排序（personalized ranking）任务是为用户提供一个排序的 item 列表，这也被称作 item 推荐（item recommendation）。例如，一家在线商城会向用户推荐用户可能想要购买的商品的个性化排序列表。在本文中，我们研究了从隐式反馈中推断 ranking 的场景。隐式反馈有意思的地方在于，只有正的观察值是可用的。未观察到的 user-item pair （例如，用户尚未购买的商品）的真实反馈是未知的，可能是用户不喜欢（负反馈）、也可能是用户喜欢但是尚未见过。

1.1 BPR 准则

1. 令 $\mathbb{U}$$\mathbb U$ 为所有用户集合，$\mathbb{I}$$\mathbb I$ 为所有 item 集合。推荐系统的任务是针对用户 $u$$u$ 提供个性化排名函数 ${>}_u\subset \mathbb{I}\times \mathbb{I}$$\gt_u \sub \mathbb I\times \mathbb I$，其中 ${>}_u$$\gt_u$ 满足以下条件：

   • 完备性（totality）：$\mathrm{\forall }i,j\in \mathbb{I}:i\ne j\to (i{>}_{u}j)\vee (j{>}_{u}i)$$\forall i,j\in \mathbb I: i\ne j \rightarrow (i \gt_u j) \; \or\; (j\gt_u i)$ 。

   • 反对称性（antisymmetry）： $\mathrm{\forall }i,j\in \mathbb{I}:(i{>}_{u}j)\wedge (j{>}_{u}i)\to i=j$$\forall i,j\in \mathbb I: (i\gt_u j) \;\and \;(j\gt_u i) \rightarrow i= j$ 。

   • 传递性（transitivity）： $\mathrm{\forall }i,j,k\in \mathbb{I}:(i{>}_{u}j)\wedge (j{>}_{u}k)\to i{>}_{u}k$$\forall i,j,k\in \mathbb I: (i\gt_u j)\; \and (j\gt_u k)\rightarrow i\gt_u k$ 。

2. 常规的 item 推荐思路是预测用户 $u$$u$ 对 item $i$$i$ 的评分 ${\hat{r}}_{u,i}$$\hat r_{u,i}$，从而反映用户对该 item 的偏好。然后根据预估评分对 item 进行排序。

3. 令隐式反馈数据 $\mathbb{S}\subseteq \mathbb{U}\times \mathbb{I}$$\mathbb S\sube \mathbb U\times \mathbb I$ 。定义缺失样本集合为 ${\complement }_{\mathbb{S}}=\mathbb{U}\times \mathbb{I}-\mathbb{S}$$\complement_{\mathbb S} = \mathbb U\times \mathbb I - \mathbb S$ ，它为 $\mathbb{S}$$\mathbb S$ 的补集。定义 ${\mathbb{I}}_u^{+}=\{i\in \mathbb{I}:(u,i)\in \mathbb{S}\},{\mathbb{U}}_i^{+}=\{u\in \mathbb{U}:(u,i)\in \mathbb{S}\}$$\mathbb I_u^+ = \{i\in \mathbb I:(u,i)\in \mathbb S\},\quad \mathbb U_i^+ = \{u\in \mathbb U:(u,i)\in \mathbb S\}$ 。

   在隐式反馈系统中，系统只能观察到用户的 postive 行为，剩余的数据是缺失值。

   • 一种解决缺失值的方法是忽略这些缺失值。但是直接忽略缺失值使得我们没有 negative 样本，从而模型无法学习。

   • 另一种解决缺失值的方法是将缺失值都是为 negative 行为。这意味着模型对 $\mathbb{S}$$\mathbb S$ 中的样本预估为1 、对 ${\complement }_{\mathbb{S}}$$\complement_{\mathbb S}$ 中的样本预估为 0 。考虑到 ${\complement }_{\mathbb{S}}$$\complement_{\mathbb S}$ 中的item 就是我们候选的、需要向用户推荐的 item，因此一个学习能力强的模型会根据这些 negative 数据学到 ${\complement }_{\mathbb{S}}$$\complement_{\mathbb S}$ 中所有得分都为零。 这意味着模型完全无法排序。

     目前该方法之所以有一定效果的原因是模型采取了一些缓解过拟合的策略，如正则化。

   我们采用了不同的思路：使用 item pair 来训练模型从而优化 item pair 的排名，而不是优化单个 item 的得分。这相比使用 negative 来代替缺失值更好地刻画了问题。

4. 我们从 $\mathbb{S}$$\mathbb S$ 中构造训练样本。对于用户 $u$$u$ ：

   • 如果 item $i$$i$ 已被用户购买，即 $(u,i)\in \mathbb{S}$$(u,i) \in \mathbb S$ ，则我们认为：相比于缺失item，用户 $u$$u$ 更喜欢 item $i$$i$ 。

   • 如果item $i,j$$i,j$ 有 $(u,i)\in \mathbb{S},(u,j)\in \mathbb{S}$$(u,i)\in \mathbb S, (u,j)\in \mathbb S$ ，则我们无法比较它们之间的任何偏好。

   • 如果item $i,j$$i,j$ 有 $(u,i)\notin \mathbb{S},(u,j)\notin \mathbb{S}$$(u,i)\notin \mathbb S, (u,j)\notin \mathbb S$ ，则我们也无法比较它们之间的任何偏好。

   因此我们构建训练集：

   $${\mathbb{D}}_{\mathbb{S}}=\{(u,i,j)\mid i\in {\mathbb{I}}_u^{+}\wedge j\in {\complement }_{{\mathbb{I}}_u^{+}}\}$$

   其中 ${\complement }_{{\mathbb{I}}_u^{+}}$$\complement_{\mathbb I_u^+}$ 为 ${\mathbb{I}}_u^{+}$$\mathbb I_u^+$ 的补集 ： ${\complement }_{{\mathbb{I}}_u^{+}}=\mathbb{I}-{\mathbb{I}}_u^{+}$$\complement_{\mathbb I_u^+} = \mathbb I - \mathbb I_u^+$。

   对于任何三元组 $(u,i,j)\in {\mathbb{D}}_{\mathbb{S}}$$(u,i,j)\in \mathbb D_{\mathbb S}$ 意味着用户 $u$$u$ 在 item $i,j$$i,j$ 之间更喜欢 item $i$$i$ 。由于 ${>}_u$$\gt_u$ 的反对称性，在提供正样本的同时也就提供了负样本。

   这种方式有两个优点：

   • 训练集包含 postive pair 、negative pair 。 测试集包含所有缺失 item pair ，这个刚好就是我们希望进行排序的目标 item pair 。这意味着从 pair-wise 角度来看，训练集 ${\mathbb{D}}_{\mathbb{S}}$$\mathbb D_{\mathbb S}$ 和测试集是不相交的。

     训练集包含的是 “（观测样本，未观测样本）” 的 pair，而测试集是 “（未观测样本，未观测样本）” 的 pair ，因此二者是不相交的。

   • 训练数据是为真实的 ranking 目标而构建的。

5. 在贝叶斯分析框架下，个性化排名的任务是：为每个 item $i$$i$ 最大化后验概率。即：

   $$p(\mathrm{\Theta }\mid {>}_u)=\frac{p(\mathrm{\Theta },{>}_u)}{p({>}_u)}=\frac{p({>}_u\mid \mathrm{\Theta })\times p(\mathrm{\Theta })}{p({>}_u)}$$

   考虑到 $p({>}_u)$$p(\gt_u)$ 与 $\mathrm{\Theta }$$\Theta$ 无关，因此有：

   $$p(\mathrm{\Theta }\mid {>}_u)\propto p({>}_u\mid \mathrm{\Theta })\times p(\mathrm{\Theta })$$

   其中 ${>}_u$$\gt_u$ 为用户的偏好， $\mathrm{\Theta }$$\Theta$ 为模型的参数。

   假设用户之间彼此独立，并且假设用户 $u$$u$ 的 item pair 之间的顺序也是相互独立的。因此 $p({>}_u\mid \mathrm{\Theta })$$p(\gt_u\mid \Theta)$ 可以重写为：

   $$\prod _{u\in \mathbb{U}}p({>}_u\mid \mathrm{\Theta })=\prod _{(u,i,j)\in \mathbb{U}\times \mathbb{I}\times \mathbb{I}}p(i{>}_{u}j\mid \mathrm{\Theta }{)}^{\delta ((u,i,j)\in {\mathbb{D}}_{\mathbb{S}})}\times (1-p(i{>}_{u}j\mid \mathrm{\Theta }){)}^{\delta ((u,i,j)\notin {\mathbb{D}}_{\mathbb{S}})}$$

   其中 $\delta$$\delta$ 为示性函数：

   $$\begin{array}{c}\delta (x)=\{\begin{array}{ll}1,& x=\text{ true}\\ 0,& \text{else}\end{array}\end{array}$$

   进一步地，根据完备性和反对称性，我们有：

   $$\prod _{u\in \mathbb{U}}p({>}_u\mid \mathrm{\Theta })=\prod _{(u,i,j)\in {\mathbb{D}}_{\mathbb{S}}}p(i{>}_{u}j\mid \mathrm{\Theta })$$

   目前为止，我们还无法确保得到个性化排序。为满足完备性、反对称性、传递性，我们定义用户 $u$$u$ 在 item $i,j$$i,j$ 之间的偏好概率为：

   $$p(i{>}_{u}j\mid \mathrm{\Theta })=\sigma ({\hat{x}}_{u,i,j}(\mathrm{\Theta }))$$

   其中： $\sigma (x)$$\sigma(x)$ 为 sigmoid 函数；${\hat{x}}_{u,i,j}$$\hat x_{u,i,j}$ 为一个模型，它捕获了用户 $u$$u$ 、item $i$$i$ 、item $j$$j$ 之间的关系。

   即：我们的 BPR 通用框架把对 $u,i,j$$u,i,j$ 之间的关系建模委托给了诸如矩阵分解、kNN 之类的基础模型，由这些模型来预估 ${\hat{x}}_{u,i,j}(\mathrm{\Theta })$$\hat x_{u,i,j}(\Theta)$ 。通过这些基础模型以及 BPR 框架，我们可以对个性化排序 ${>}_u$$\gt_u$ 进行建模。

6. 我们引入先验概率密度函数 $p(\mathrm{\Theta })$$p(\Theta)$ 为零均值、协方差矩阵为 ${\mathrm{\Sigma }}_{\mathrm{\Theta }}$$\Sigma_{\Theta}$ 的高斯分布概率密度分布函数：

   $$p(\mathrm{\Theta })\sim \mathcal{N}(\mathbf{0},{\mathrm{\Sigma }}_{\mathrm{\Theta }})$$

   为减少超参数数量，我们选择 ${\mathrm{\Sigma }}_{\mathrm{\Theta }}=\lambda \mathbf{I}$$\Sigma_{\Theta} = \lambda \mathbf I$ 。

7. BPR-OPT ：个性化排名通用准则 BPR-OPT 是最大化后验估计 $p(\mathrm{\Theta }\mid {>}_u)$$p(\Theta\mid \gt _u)$ ，因此有：

   $$\begin{array}{c}\text{BPR-OPT}:max\ln p(\mathrm{\Theta }\mid {>}_u)=max\ln (p({>}_u\mid \mathrm{\Theta })\times p(\mathrm{\Theta }))\\ =max\ln (\prod _{(u,i,j)\in {\mathbb{D}}_{\mathbb{S}}}\sigma \left({\hat{x}}_{u,i,j}\right)p(\mathrm{\Theta }))=max\sum _{(u,i,j)\in {\mathbb{D}}_{\mathbb{S}}}\ln \sigma ({\hat{x}}_{u,i,j})+\ln p(\mathrm{\Theta })\\ =max\sum _{(u,i,j)\in {\mathbb{D}}_{\mathbb{S}}}\ln \sigma ({\hat{x}}_{u,i,j})-\lambda ||\mathrm{\Theta }|{|}^2\end{array}$$

   其中 $\lambda$$\lambda$ 为模型的正则化参数。

   $p(i{>}_{u}j\mid \mathrm{\Theta })=\sigma ({\hat{x}}_{u,i,j}(\mathrm{\Theta }))$$p(i\gt_u j \mid\Theta) = \sigma(\hat x_{u,i,j}(\Theta))$ 的物理意义是观察到的 item $i$$i$ 排序在未观察到的 item $j$$j$ 之前的概率。因此 $\ln \sigma ({\hat{x}}_{u,i,j})$$\ln\sigma(\hat x_{u,i,j})$ 为训练集排序成立的对数似然。

1.2 BPR 学习

1. 和 AUC 的联系：我们将 BPR 和 AUC 进行类比。用户维度的 AUC 定义为：

   $$\text{AUC}(u)=\frac{\sum _{i\in {\mathbb{I}}_u^{+}}\sum _{j\in {\complement }_{{\mathbb{I}}_u^{+}}}\delta ({\hat{x}}_{u,i,j}>0)}{|{\mathbb{I}}_u^{+}|\times |{\complement }_{{\mathbb{I}}_u^{+}}|}$$

   即在所有 postive item 和 missing item 组合中，模型预估对 postive item 和 missing item 能够正确区分的概率。

   因此所有用户的平均 AUC 为：

   $$\text{AUC}=\frac{\sum _u\text{AUC}(u)}{|\mathbb{U}|}$$

   根据 ${\mathbb{D}}_{\mathbb{S}}$$\mathbb D_{\mathbb S}$ 的定义有：

   $$\text{AUC}(u)=\sum _{(u,i,j)\in {\mathbb{D}}_{\mathbb{S}}}{z}_u\delta ({\hat{x}}_{u,i,j}>0)$$

   其中 $z_u$$z_u$ 为归一化常数：

   $$z_u=\frac{1}{|{\mathbb{I}}_u^{+}|\times |{\complement }_{{\mathbb{I}}_u^{+}}|}$$

   这和 BPR-OPT 准则非常类似。 BPR-OPT 的目标函数为：

   $$\mathcal{J}=\sum _{(u,i,j)\in {\mathbb{D}}_{\mathbb{S}}}\ln \sigma ({\hat{x}}_{u,i,j})-\lambda ||\mathrm{\Theta }|{|}^2$$

   如果将这个代价函数视为损失函数（第一项）和正则化项(第二项)，则 BPR-OPT 的损失函数为：

   $$\sum _{(u,i,j)\in {\mathbb{D}}_{\mathbb{S}}}\ln \sigma ({\hat{x}}_{u,i,j})$$

   这和 AUC 有两个区别：

   • AUC 使用了归一化常数 $z_u$$z_u$ 。

   • AUC 使用不可导的示性函数 $\delta (\cdot )$$\delta(\cdot)$ ，这等价于 Heaviside 函数：

     $$\begin{array}{c}\delta (x>0)=H(x)=\{\begin{array}{ll}1,& x>0\\ 0,& \text{else}\end{array}\end{array}$$

     通常在优化 AUC 时我们使用可导的 $\sigma (x)$$\sigma(x)$ 来替代不可导的 Heaviside 函数。

     而 BPR-OPT 使用可导的损失函数 $\ln \sigma (x)$$\ln\sigma(x)$ 。

2. 学习算法：虽然我们已经导出了个性化排名的优化准则，并且该准则是可微的，但是我们无法利用标准的梯度下降算法来求解该最优化问题。为解决该最优化问题，我们提出了基于bootstrap 采样的随机梯度下降算法 LearnBPR 。

   BPR-OPT 目标函数的梯度为：

   $$\begin{array}{c}{\mathrm{\nabla }}_{\mathrm{\Theta }}\mathcal{J}=\sum _{(u,i,j)\in {\mathbb{D}}_{\mathbb{S}}}{\mathrm{\nabla }}_{\mathrm{\Theta }}\ln \sigma ({\hat{x}}_{u,i,j})-\lambda {\mathrm{\nabla }}_{\mathrm{\Theta }}||\mathrm{\Theta }|{|}^2\\ =\sum _{(u,i,j)\in {\mathbb{D}}_{\mathbb{S}}}\frac{-\exp (-{\hat{x}}_{u,i,j})}{1+\exp (-{\hat{x}}_{u,i,j})}{\mathrm{\nabla }}_{\mathrm{\Theta }}{\hat{x}}_{u,i,j}-\lambda \mathrm{\Theta }\end{array}$$

   • 在 full 随机梯度下降算法中，在每个 step 需要计算所有训练样本的梯度，然后更新参数：

     $$\mathrm{\Theta }\leftarrow \mathrm{\Theta }-\alpha \times {\mathrm{\nabla }}_{\mathrm{\Theta }}\mathcal{J}$$

     这种方法可以确保每次参数更新的方向是正确的，但是缺点是计算复杂度太高：${\mathbb{D}}_{\mathbb{S}}$$\mathbb D_{\mathbb S}$ 包含 $O(|\mathbb{S}|\times |\mathbb{I}|)$$O(|\mathbb S|\times |\mathbb I|)$ 个三元组，因此在每个 step 中计算完整的梯度不可行。

     另外，使用完整的梯度优化也会存在梯度倾斜问题，这也会拖慢训练的收敛速度：

     • 不同的 item 为 postive 的分布不同，因此我们很难选择一个合适的学习率：对于postive 较多的 item （梯度较大）， 我们必须选择一个较小的学习率；对于 postive 较少的 item （梯度较小） ，我们必须选择一个较大的学习率。

     • 另外梯度分布差距太大，导致正则化系数的选择非常困难。

   • 在随机梯度下降算法中，我们对单个三元组 $(u,i,j)\in {\mathbb{D}}_{\mathbb{S}}$$(u,i,j)\in \mathbb D_{\mathbb S}$ 执行更新：

     $$\mathrm{\Theta }\leftarrow \mathrm{\Theta }+\alpha \times (\frac{\exp (-{\hat{x}}_{u,i,j})}{1+\exp (-{\hat{x}}_{u,i,j})}{\mathrm{\nabla }}_{\mathrm{\Theta }}{\hat{x}}_{u,i,j}+\lambda \mathrm{\Theta })$$

     这可以解决梯度倾斜问题。但是，随机梯度下降依赖于样本的遍历顺序，需要确保每次都是随机选择 $(u,i,j)\in {\mathbb{D}}_{\mathbb{S}}$$(u,i,j)\in \mathbb D_{\mathbb S}$ 。

   LearnBPR 学习算法采用每次均匀随机选择三元组 $(u,i,j)\in {\mathbb{D}}_{\mathbb{S}}$$(u,i,j)\in \mathbb D_{\mathbb S}$ 的随机梯度下降算法。通过这种方式，在连续更新 step 中选择相同 user-item 组合的机会很小。我们建议使用 bootstrap 采样方法，这样可以在任何 step 来停止。在我们的案例中，放弃完整 epoch 循环的想法特别有用，因为样本数量巨大，并且只需要整个 epoch 的一小部分模型就能收敛。

   这就是 batch 随机梯度下降，并且 batch 是随机选择（而不是 user-wise 或者 item-wise 选择）。

   下图给出了典型的 user-wise 随机梯度下降，以及 LearnBPR 随机梯度下降的收敛速度。可以看到 learnBPR 随机梯度下降的收敛速度更快。

   

1.3 模型结合 BPR

1. 这里我们展示如何将 BPR 和经典的矩阵分解、kNN 模型融合。

2. 在 BPR-OPT 通用框架中，我们需要利用其它模型来预估 ${\hat{x}}_{u,i,j}$$\hat x_{u,i,j}$ 。我们将 ${\hat{x}}_{u,i,j}$$\hat x_{u,i,j}$ 定义为：

   $${\hat{x}}_{u,i,j}={\hat{x}}_{u,i}-{\hat{x}}_{u,j}$$

   现在我们可以使用标准的协同过滤算法来预估 ${\hat{x}}_{u,l}$$\hat x_{u,l}$ 。

   • 即使我们使用了和别人一样的模型，我们和它也有本质的不同：我们采用了另一个准则来优化模型，这会导致更好的排序结果。因为我们的准则是直接优化个性化排名。

   • 我们的准则并不是尝试通过单个预估值 ${\hat{x}}_{u,l}$$\hat x_{u,l}$ 来拟合某个目标，而是试图拟合两个预估值 ${\hat{x}}_{u,i}-{\hat{x}}_{u,j}$$\hat x_{u,i} - \hat x_{u,j}$ 之间的差异。

3. 矩阵分解结合 BPR：假设每个用户 $u$$u$ 关联一个representation 向量 ${\overrightarrow{\mathbf{w}}}_u\in {\mathbb{R}}^k$$\mathbf{\vec w}_u\in \mathbb R^k$ ， 每个item $i$$i$ 关联一个 representation ${\overrightarrow{\mathbf{h}}}_i\in {\mathbb{R}}^k$$\mathbf{\vec h}_i\in \mathbb R^k$ ， $k$$k$ 为 representation 向量维度。用户$u$$u$ 对 item $i$$i$ 的预估值为：${\hat{x}}_{u,i}={\overrightarrow{\mathbf{w}}}_u\cdot {\overrightarrow{\mathbf{h}}}_i$$\hat x_{u,i} = \mathbf{\vec w}_u \cdot \mathbf{\vec h}_i$ 。

   则有：

   $$\hat{\mathbf{X}}=\mathbf{W}{\mathbf{H}}^{\mathrm{\top }}$$

   其中 $\mathbf{W}\in {\mathbb{R}}^{|\mathbb{U}|\times k}$$\mathbf W\in \mathbb R^{|\mathbb U|\times k}$ 的各行由所有用户向量 ${\overrightarrow{\mathbf{w}}}_u$$\mathbf{\vec w}_u$ 组成 ,$\mathbf{H}\in {\mathbb{R}}^{|\mathbb{I}|\times k}$$\mathbf H\in \mathbb R^{|\mathbb I|\times k}$ 的各行由所有item 向量 ${\overrightarrow{\mathbf{h}}}_i$$\mathbf{\vec h}_i$ 组成， $k$$k$ 远小于用户或item 的数量， $\hat{\mathbf{X}}$$\hat{\mathbf X}$ 为评分矩阵 $\mathbf{X}$$\mathbf X$ 的估计值。

   该模型称作矩阵分解 Matrix Factor ，模型的参数为 $\mathrm{\Theta }=(\mathbf{W},\mathbf{H})$$\Theta=(\mathbf W,\mathbf H)$ 。

   • 可以通过奇异值分解 SVD 来求解参数 $\mathbf{W}$$\mathbf W$ 和 $\mathbf{H}$$\mathbf H$ ，但是该方法很容易陷入过拟合。为此，一些机器学习方法引入了其它的矩阵分解技术，如：带正则化的矩阵分解、非负矩阵分解（non-negative MF）、最大裕量矩阵分解 （maximum margin factorization）等等。

   • 对于个性化排名任务，更好的方法是采用 BPR-OPT 准则进行优化，称作 BPR-MF 。

     对于使用了 BPR-OPT 准则的矩阵分解模型，LearnBPR 优化时使用的梯度为：

     $$\begin{array}{c}\frac{\partial }{\partial \theta }{\hat{x}}_{u,i,j}=\{\begin{array}{ll}(h_{i,j}-h_{j,f}),& \text{if}\theta =w_{u,f}\\ w_{u,f},& \text{if}\theta =h_{i,f}\\ -w_{u,f},& \text{if}\theta =h_{j,f}\\ 0,& \text{else}\end{array}\end{array}$$

     另外我们还引入三个正则化约束：

     • 使用 ${\lambda }_{\mathbf{W}}$$\lambda_{\mathbf W}$ 来约束用户representation矩阵 $\mathbf{W}$$\mathbf W$ 。

     • 使用 ${\lambda }_{{\mathbf{H}}^{+}}$$\lambda_{\mathbf H^+}$ 来约束 $h_{i,f}$$h_{i,f}$ 上的 positive 更新 。

     • 使用 ${\lambda }_{{\mathbf{H}}^{-}}$$\lambda_{\mathbf H^-}$ 来约束 $h_{j,f}$$h_{j,f}$ 上的 negative 更新。之所以拆分 ${\lambda }_{{\mathbf{H}}^{+}}$$\lambda_{\mathbf H^+}$ 和 ${\lambda }_{{\mathbf{H}}^{-}}$$\lambda_{\mathbf H^-}$ 是因为 postive 样本和 negative 样本的规模差异巨大。

4. 自适应 kNN 结合 BPR：kNN 可以基于item 之间的相似或者 user 之间的相似来建模，这里我们介绍基于 item 相似的kNN 方法，但是基于 user 相似性的kNN 方法原理类似。

   基于 item 相似的 kNN 的基本思想是：用户 $u$$u$ 在 item $i$$i$ 上的预估值依赖于 item $i$$i$ 和 ${\mathbb{I}}_u^{+}$$\mathbb I_u^+$ 上 item 的相似性。通常我们仅使用 ${\mathbb{I}}_u^{+}$$\mathbb I_u^+$ 中和 item $i$$i$ 最相似的 top k 个 item，即 kNN 。

   最终基于 item 的 kNN 模型为：

   $${\hat{x}}_{u,i}=\sum _{l\in {\mathbb{I}}_u^{+}\wedge l\ne i}{c}_{i,l}$$

   其中 $\mathbf{C}\in {\mathbb{R}}^{|\mathbb{I}|\times |\mathbb{I}|}$$\mathbf C\in \mathbb R^{|\mathbb I|\times |\mathbb I|}$ 为 item 之间的相似度矩阵，它也是模型的参数 $\mathrm{\Theta }=\mathbf{C}$$\Theta = \mathbf C$ 。

   注意：这里假设 postive 得分为 1、negative 得分为 0 。因此最终预估评分就是top k 个 item 的相似度之和。另外，有的方法也对相似度矩阵按行进行归一化。

   • 大多数方法使用启发式的相似度函数，如余弦相似度：

     $$c_{i,j}=\frac{|{\mathbb{U}}_i^{+}\cap {\mathbb{U}}_j^{+}|}{\sqrt{|{\mathbb{U}}_i^{+}|\times |{\mathbb{U}}_j^{+}|}}$$

   • 一个更好的方法是通过学习相似度矩阵 $\mathbf{C}$$\mathbf C$ 来自适应：直接将 $\mathbf{C}$$\mathbf C$ 作为模型参数。如果 $\mathbf{C}$$\mathbf C$ 规模太大，我们也可以对其进行矩阵分解：$\mathbf{C}=\mathbf{H}{\mathbf{H}}^{\mathrm{\top }}$$\mathbf C = \mathbf H\mathbf H^\top$ 。其中我们只需要学习参数 $\mathbf{H}\in {\mathbb{R}}^{|\mathbb{I}|\times k}$$\mathbf H\in \mathbb R^{|\mathbb I|\times k}$ 。

   我们考虑通过 BPR-OPT 准则和 LearnBPR 学习方法来利用 kNN 对个性化排序进行建模，称作 kNN-BPR 。LearnBPR 优化时采用的梯度为：

   $$\begin{array}{c}\frac{\partial }{\partial \theta }{\hat{x}}_{u,i,j}=\{\begin{array}{ll}+1,& \text{if}\theta \in \{c_{i,l},c_{l,i}\}\wedge l\in {\mathbb{I}}_u^{+}\wedge l\ne i\\ -1,& \text{if}\theta \in \{c_{j,l},c_{l,j}\}\wedge l\in {\mathbb{I}}_u^{+}\wedge l\ne j\\ 0,& \text{else}\end{array}\end{array}$$

   另外我们还引入两个正则化约束：

   • ${\lambda }_{+}$$\lambda_+$ 用于更新 $c_{i,l}$$c_{i,l}$ 。

   • ${\lambda }_{-}$$\lambda_{-}$ 用于更新 $c_{j,l}$$c_{j,l}$ 。

1.3 BPR VS WR-MF 、MMMF

1. 这里我们讨论 BPR 和 WR-MF 以及 MMMF 模型之间的联系。

2. Weighted Regularized Matrix Factorization:WR-MF 用于从隐式反馈数据中执行矩阵分解（参考Implicit Feedback CF 章节），其模型为：

   $$\mathcal{J}=\sum _{(u,i)\in \mathbb{S}}{c}_{u,i}{(1-{\overrightarrow{\mathbf{w}}}_u\cdot {\overrightarrow{\mathbf{h}}}_i)}^2+\lambda (||\mathbf{W}|{|}_F^2+||\mathbf{H}|{|}_F^2)$$

   其中$||\cdot |{|}_F$$||\cdot||_F$ 为矩阵的 F 范数， $c_{u,i}$$c_{u,i}$ 为user-item 组合的先验权重。例如，对于所有postive 样本选择 $c_{i,j}=1$$c_{i,j} =1$、对于所有 negative 样本选择 $c_{i,j}<1$$c_{i,j} \lt 1$ 。

   这里假设正样本的评分为 1、负样本评分为0，因此 $(1-\overrightarrow{\mathbf{w}}\cdot \overrightarrow{\mathbf{h}})$$(1-\mathbf{\vec w}\cdot \mathbf{\vec h})$ 为残差。

   和BPT-OPT 的 $\mathcal{J}=\sum _{(u,i,j)\in {\mathbb{D}}_{\mathbb{S}}}\ln \sigma ({\hat{x}}_{u,i,j})-\lambda ||\mathrm{\Theta }|{|}^2$$\mathcal J = \sum_{(u,i,j)\in \mathbb D_{\mathbb S}}\ln\sigma(\hat x_{u,i,j}) - \lambda ||\Theta||^2$ （应该取负号，从而最小化目标函数）相比可以发现：

   • BPT-OPT 是对每个用户 $u$$u$ 优化的是一对 item pair ，而 WR-MF 优化的是单个 item 。

   • BPT-OPT 的损失函数为逻辑回归损失，而 WR-MF 的损失函数为最小平方误差。

     但是item 预测实际上不是回归任务（定量分析），而是分类任务（定性分析），因此用逻辑回归损失更合适。

   • BPT-OPT 对每个损失的权重为 1 ，而 WR-MF 对每个损失的权重为 $c_{i,j}$$c_{i,j}$ 。

3. Maximum Margin Matrix Factorization:MMMF 并不适合于隐式反馈数据集。我们可以将缺失值设置为0、将非缺失值设置为1。通过这些修改，MMMF 的目标函数为：

   $$\mathcal{J}=\sum _{(u,i,j)\in {\mathbb{D}}_{\mathbb{S}}}max(0,1-{\overrightarrow{\mathbf{w}}}_u\cdot ({\overrightarrow{\mathbf{h}}}_i-{\overrightarrow{\mathbf{h}}}_j))+{\lambda }_w||\mathbf{W}|{|}_F^2+{\lambda }_h||\mathbf{H}|{|}_F^2$$

   和BPT-OPT 的 $\mathcal{J}=\sum _{(u,i,j)\in {\mathbb{D}}_{\mathbb{S}}}\ln \sigma ({\hat{x}}_{u,i,j})-\lambda ||\mathrm{\Theta }|{|}^2$$\mathcal J = \sum_{(u,i,j)\in \mathbb D_{\mathbb S}}\ln\sigma(\hat x_{u,i,j}) - \lambda ||\Theta||^2$ 相比可以发现：

   • BPT-OPT 的损失函数为逻辑回归损失，而 MMMF 的损失函数为 hinge 损失。

   • BPT-OPT 准则是通用的，可应用于多种模型；而 MMMF 方法仅针对矩阵分解。

   MMMF：正负样本预估得分之间的差距尽可能大；BPT-OPT：正样本预估得分大于负样本预估得分的概率尽可能大。二者都是排序关系，因此思想上是相近的。如果将 Hinge 损失替换为逻辑回归损失，则 MMMF 等价于 BPT-OPT 。

1.4 实验

1. 数据集：

   • Rossmann 数据集：一个在线商店数据集，包含 10000 个用户在 4000 个 item 上的购买历史，总共有 426612 条购买记录。我们的任务是为用户推荐该用户下一次可能购买的商品的列表。

   • Netflix 数据集：一个 DVD 出租数据集，包含用户在电影上的显式评分，评分从 1~5 共五个等级。由于我们需要解决隐式反馈任务，因此我们从数据集中删除了评分分数。现在的任务是预测用户是否可能为电影评分。

     我们从原始数据集中采样了 10000 个用户、5000 个 item，包含 565738 个评分。采样时，我们选择至少对10部电影进行评分的用户 $\{u\mid |{\mathbb{I}}_u^{+}|>10\}$$\{u\mid |\mathbb I_u^+|\gt 10\}$， 以及每个item 至少有10个用户观看 $\{i\mid |{\mathbb{U}}_i^{+}|>10\}$$\{i\mid |\mathbb U_i^+|\gt 10\}$。

2. baseline 模型：我们选择了矩阵分解 MF 和 kNN 这两种流行的模型。

   • 对于矩阵分解模型，我们采用三种不同的方法来实现：标准矩阵分解 SVD-MF、带权重矩阵分解WR-MF、基于 BPR-OPT 优化准则的矩阵分解BPR-MF 。

   • 对于kNN 模型，我们采用两种不同的方法来实现： 基于余弦相似度的 kNN 方法cosin-kNN 、基于 BPR-OPT 优化准则的自适应kNN 方法 BPR-kNN 。

   • 另外我们还比较了基于热门程度的 baseline 方法：根据item 热门程度排名，然后为每个用户 $u$$u$ 选择其中的 top 热门的 item 。这也是一种非个性化的推荐，即所有用户推荐的item 都相同。

3. 实验配置：我们使用留一法（leave one out）来评估。对于每个用户随机删除一条历史记录，并将该历史记录作为测试集。这样我们得到了不相交的训练集 ${\mathbb{S}}_{\text{train}}$$\mathbb S_{\text{train}}$ 以及测试集 ${\mathbb{S}}_{\text{test}}$$\mathbb S_{\text{test}}$ 。我们在训练集上训练各个模型，并在测试集上评估模型，评估指标是测试集的平均 AUC：

   $$\text{AUC}=\frac{1}{|\mathbb{U}|}\sum _u\frac{1}{|\mathbb{T}(u)|}\sum _{(i,j)\in \mathbb{T}(u)}\delta ({\hat{x}}_{u,i}>{\hat{x}}_{u,j})$$

   其中 $\mathbb{T}(u)$$\mathbb T(u)$ 为每个用户的评估数据，它由保留的那一条item，以及所有的缺失 item 组成：

   $$\mathbb{T}(u)=\{(i,j)\mid (u,i)\in {\mathbb{S}}_{\text{test}}\wedge (u,j)\ne ({\mathbb{S}}_{\text{test}}\cup {\mathbb{S}}_{\text{train}})\}$$

   AUC 的值越高表明模型效果越好。随机猜测的 AUC 为 0.5， 最好的 AUC 为 1.0 。

   即对每个用户 $u$$u$，评估其测试集中唯一的正样本和未观测样本之间的排序。

   我们还给出了非个性化推荐方法的理论 AUC 上界 ${\text{np}}_{max}$$\text{np}_{\max}$ ，这是通过在测试集 ${\mathbb{S}}_{\text{test}}$$\mathbb S_{\text{test}}$ 上搜索最佳的排名 $>$$\gt$ 函数（不是 ${>}_u$$\gt_u$ ，因为非个性化推荐与用户无关），从而得到理论上的非个性化排名的上界。

   对于每种实验配置，随机重复执行 10 次，在每一次都随机拆分训练、测试集。所有模型的超参数都在第一次执行时采用 grid search 搜索，并在剩余9 次保持不变。

4. 在两个数据集上所有模型的效果如下。结论：

   • BPR-MR 和 BPR-kNN 均优于其它所有方法。这表明我们的BPR-OPT 准则以及对应的 LearnBPR 学习方法在个性化排序任务中的效果。

   • 尽管所有的矩阵分解方法 SVD-MF,WR-MF,BPR-MF 采用完全相同的模型（即 MF），但是它们的效果差别很大。

     • SVD-MF 可以对训练数据拟合的更好，但是它会陷入严重的过拟合。这可以从 SVD-MF 随着维度的增加，测试 AUC 反而下降来观察到。

     • WR-MF 相比之下更为成功。由于正则化的效果，当维度增加时 WR-MF 的效果并未下降。

     • BPR-WF 在所有数据集上都超越了SVD-MF 和 WR-MF 。

   • 即使是 cosin-kNN 这样最简单的个性化推荐方法也超越了非个性化的 ${\text{np}}_{max}$$\text{np}_{\max}$ ，因此也意味着超越了所有的非个性化方法。