BPR: Bayesian Personalized Ranking from Implicit Feedback

原文请狂击这里

概述

本文提出了一种对推荐结果进行排序的方法和框架，旨在基于已有的多种推荐算法上应用该算法以提高推荐结果的排序效果。

已有的各种推荐算法其输可以理解为是对物品是否可被推荐的概率分布，而在实际场景下往往是会召回很多个待推荐的物品的，大部分算法直接使用了这个概率分布取得TopN结果来作为推荐候选并且推荐项之间的顺序是按照概率大小来决定的。

这种方法是可行的，但是从原理上讲物品之间的顺序并不是这些模型的建模目标，模型会倾向于把应该推荐的项目的概率拟合为1而不应该推荐的项目的概率拟合为0，但是物品之间的先后顺序是没有被明确的学习的。

本文提出的方法就是旨在解决物品之间顺序的问题，其提出了一个算法框架可以应用于各个已有的推荐算法并在其上以物品之间的顺序为优化目标，解决推荐的物品之间的排序问题。

如果你对LTR算法有了解的话，那么本文的思想会非常的容易理解。

本文的另一个建模目标是解决应用所谓的Implicit Feedback也就是指非用户明确的反馈信息的问题。这个很好理解：譬如如果对一部电影打了分，那么这就是一个明确的反馈（Explicit Feedback），相反如果用户没有打分而是选择观看了电影、购买了电影等等，那么这就是一个非明确的反馈（Implicit Feedback）。明确的反馈与非明确反馈的区别就是明确反馈天然的包含了正样本与负样本（譬如：高评分与低评分），而非明确反馈很大概率是难以区分出负样本的（用户未观看就代表用户不喜欢吗？也可能是担心流量问题。）

方法

为了可以直接建模推荐物品之间的顺序作为优化目标，在模型的设计上一定是要引入对比的（Pair），因此非常直观的本文提出的模型的首要参数是三个：

• \(u \in U\)
• \(i \in I\)
• \(j \in I\)

其中\(U\)表示所有的用户，\(I\)表示所有的物品，那么相应的我们可以使用\(S\)表示所有用户和物品之间的非明确反馈关系。从这里往后我们首先假设\(S\)中表示的所有反馈都是正反馈。

接下来定义比较的函数，假设对于一对物品\(ij\)，用户更加喜欢\(i\)那么表示为\(i >_u j\)，那么这个模型的求解目标实际上就变成了\(P(i >_u j\vert\theta)\)。（考虑到对称性，\(i <_u j\)就不需要被建模了）。这个目标的求解方法在后文描述。

接下来我们定义一下正样本集合：\(D_s = \{u, i, j\}\)其中\((u, i) \in S\) \((u, j) \notin S\)，非常的直观。

优化方法

本文采用的是最大后验估计方法来学习参数，关于常见的几种优化方法（最大似然估计、最大后验估计、EM等等）我会单独写一篇文章，这里就不赘述了。

因为\(>_u\)是已知的，\(\theta\)是求解目标因此应用贝叶斯公式：

\[P(\theta\vert>_u) \propto P(>_u\vert\theta)P(\theta)\]

假设所有用户之间的行为都是独立的那么：

\[P(>_u\vert\theta) = {\displaystyle \prod_{u \in U} } {p(>_u\vert\theta)} = {\displaystyle \prod_{(u,i,j) \in U \times I \times I}} ({p(i >_u j\vert\theta)}^{\delta((u,i,j) \in D_s)} \cdot (1 - p(i >_u j\vert\theta))^{\delta((u,i,j) \notin D_s)})\]

其中\(\delta(x)\)函数返回1如果条件\(x\)成立否则返回0。

考虑到对称性上式可以简化为：\(P{\displaystyle \prod_{(u,i,j) \in D_s} {p(i >_u j\vert\theta)}}\)

那么使用sigmoid函数表示该概率则：\(p(i >_u j\vert\theta) = \sigma (\hat{x}_{uij}(\theta))\)其中\(\sigma(x) = \frac {1} {1 + e^{-x}}\)

应用最大后验估计方法，那么求解目标就是：

\[O_{bpr} = \ln p(\theta\vert>_u) = \ln p(>_u\vert\theta)p(\theta) = \ln {\displaystyle \prod_{(u,i,j) \in D_s}} \sigma(\hat{x}_{uij})p(\theta) = {\displaystyle \sum_{(u,i,j) \in D_s}} \ln \sigma(\hat{x}_{uij}) + \ln p(\theta)\]

那么我们假设\(p(\theta)\)满足正态分布，即：\(p(\theta) \sim N(0, \sum_\theta)\)，其中\(\sum_\theta = \lambda_\theta I\)则上式可以变换为：

\[{\displaystyle \sum_{(u,i,j) \in D_s}} \ln \sigma(\hat{x}_{uij}) - \lambda_\theta\vert\theta\vert^2\]

此处的推导没有完全理解（展开正态分布之后并不是\(- \lambda_\theta\vert\theta\vert^2\)这项），有理解的同学欢迎指教。

其中\(\lambda_\theta\)是模型的正则化参数。

得到了待学习参数的目标函数之后，接下来就是求解参数的过程。显然上式是一个连续函数，因此可以使用梯度下降法，因此我们对参数\(\theta\)求偏导数：

\[\frac {\partial O_{bpr}} {\partial \theta} = {\displaystyle \sum_{(u,i,j) \in D_s} \frac {\partial \ln \sigma(\hat{x}_{uij})} {\partial \theta}} - 2\lambda_\theta\theta = {\displaystyle \sum_{(u,i,j) \in D_s} \frac {-e^{-\hat{x}_{uij}}} {1 + e^{-\hat{x}_{uij}}}} \cdot \frac {\partial\hat{x}_{uij}} {\partial\theta} - \lambda_\theta\theta\]

其中最后一项\(2\lambda_\theta\)因\(\lambda_\theta\)本身是一个超参数因此可以省略掉常数项\(2\)，这里用等号不是非常严谨。

此处求导我计算的结果和原文中不一致，我计算的结果中第一项没有负号。此处先假设原文正确，各位如有过程不吝赐教。

接下来做梯度下降更新就比较直接了，每次更新参数加上一个负梯度上的结果乘上一个学习率参数。文中提出了一种放回抽样的方式来从样本中随机抽取数据来实现随机梯度下降，而不是基于用户或者基于物品的随机。

以上是模型框架和优化方法的定义，那么结合不同的算法就可以定义不同的\(\hat{x}\)进而实现对某个具体算法的优化。

应用

以下介绍各个算上应用这个算法框架之后的结果。考虑到绝大部分推荐算法都是对\(\hat{x}_{ui}\)进行的建模，因此首先需要对分解带估计的函数：

\[\hat{x}_{uij} = \hat{x}_{ui} - \hat{x}_{uj}\]

那么我们就可以把任何可以计算出\(\hat{x}_{ui}\)的模型应用在这个框架上了。

矩阵分解

矩阵分解是最常见的协同过滤方法了，其目标是\(\hat{X} = WH^T\)其中\(W\)是一个\(U * K\)大小的矩阵\(H\)是一个\(I * K\)大小的矩阵，分解出来：

\(\hat{x}_{ui} = {\displaystyle \sum_{f=1}^k} w_{uf}h_{if}\)那么\(\hat{x}_{uij} = {\displaystyle \sum_{f=1}^k}w_{uf}(h_{if} - h_{jf})\)

将上式带入上一节中求得到的偏导数公式会得到：

• \(\frac {\partial \hat{x}_{uij}} {\partial w_{uf}} = (h_{if} - h_{jf})\)
• \(\frac {\partial \hat{x}_{uij}} {\partial h_{if}} = w_{uf}\)
• \(\frac {\partial \hat{x}_{uij}} {\partial h_{if}} = -w_{uf}\)

相应的可以将\(\lambda_\theta\)分为三个参数分别应用在三个偏导公式中。

Adaptive KNN

KNN的思想非常简单，譬如计算用户\(u\)与物品\(i\)之间的推荐强度那么就计算一下\(i\)和该用户历史上所有的物品反馈进行计算，通常情况下可以计算和\(i\)最相思的\(k\)个物品就可以近似的表达在整个历史上的计算结果。

因此可以近似的认为：\(\hat{x}_{ui} = \sum c_{ij}\)其中\(j\)是该用户的物品历史记录全集。

关于\(c_{ij}\)的计算方法有很多，譬如常见的cosine相似度。那么在本文里，作者直接建模并优化这个参数，也就是说参数\(C\)是一个\(I * I\)大小的矩阵。如果矩阵过于的大可以用矩阵分解的方式分解为\(HH^T\)，其中\(H\)大小为\(I * K\)。

那么\(\hat{x}_{uij} = \sum c_{il} - \sum c_{jl}\)其中\(l\)是该用户的历史物品记录全集，则应用以上偏导数后：

• \(\frac {\partial \hat{x}_{uij}} {\partial c_{il}} = 1\)
• \(\frac {\partial \hat{x}_{uij}} {\partial c_{jl}} = -1\)

相应的可以将\(\lambda_\theta\)分为两个参数分别应用在两个偏导公式中。