贝叶斯个性化排序

发表于 分类于 Disqus：

Bayesian Personalized Ranking 是基于隐式反馈数据的非常通用的个性化模型，一般实现使用的是 matrix factorization 机制，利用随机梯度下降来求解。

假设用来表达训练集的三元组为 \((u,i,j)\)，只需要找到“最优化”的用户的 f 维向量表征 \(w_{uf}\)，positive item i 的 f 维向量表征 \(h_{if}\)，negative item j 的 f 维向量表征 \(h_{jf}\)，则建模完毕。

它有以下几点优势：

  • 不关注于拟合的具体数值损失最小，而是关注于 item 的排序关系
  • 由于特殊的负采样策略，导致它的结果相对偏 High-Precision & Low-Recall
  • 因为是潜变量模型，预测只是向量的相乘，工程化性能优异

1. 模型推导

考虑我们优化的目标(\(\theta\) 是我们求解的任意参数，比如矩阵分解的潜向量，\(>_u\) 代表了 user 对其他所有 item 的排序关系），它可以用贝叶斯公式表示为

\[ P(\theta|>_u) = \frac{P(>_u|\theta)P(\theta)}{P(>_u)} \]

假设所有的用户行为都是独立的，因此有

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

因此优化目标拆解成了两部分，先看第一部分，可以表示为

\[ \prod_{u \in U}P(>_u|\theta) = \prod_{(u,i,j) \in D}P(i >_u j|\theta) \]

定义user \(u\) 和 item \(i\) 的内积为 user 对 item 的偏好 \(x_{ui}\)。 对于 \(P(i >_u j|\theta)\) 这个概率，直观解释就是 \(x_{ui}\) 是否大于 \(x_{uj}\)，大于零则表示：对于用户 \(u\) 来说，\(i\) 和 \(j\) 更偏好 \(i\) ：

\[ x_{uij} = x_{ui} - x_{uj} \]

但这里有个问题，这个如果直接减的话，是 non-continuous, non-differential， 所以我们需要变换一下，把 \(x_{ui} - x_{uj}\) 的结果用 sigmod 函数变换一下（概率化），可以写成这样

\[ P(i >_u j|\theta) = \sigma(x_{uij}(\theta)) \]

因此第一部分的优化目标就可以变成这个样子了：

\[ \prod_{u \in U}P(>_u|\theta) = \prod_{(u,i,j) \in D} \sigma(x_{ui} - x_{uj}) \]

对于第二部分的 \(P(\theta)\)，我们将它简化为均值为0，协方差矩阵为 \(\lambda_{\theta}I\)，即

\[ P(\theta) \sim N(0, \lambda_{\theta}I) \]

因此对数后验估计函数可以表示为：

\[ \ln P(\theta|>_u) \propto \ln P(>_u|\theta)P(\theta) = \ln \prod\limits_{(u,i,j) \in D} \sigma(x_{uij}) + ln P(\theta) = \sum\limits_{(u,i,j) \in D}\ln\sigma(x_{uij}) + \lambda||\theta||^2\; \]

上式的对于 \(\theta\) 的一阶导为：

\[ \begin{align*} &= \prod\limits_{(u,i,j)} \frac{\partial \ln \sigma(x_{uij})}{\partial \theta} - \lambda_{\theta} \frac{\partial ||\theta||^2}{\partial \theta} \\ &\propto \prod\limits_{(u,i,j)} \frac{e^{-x_{uij}}}{1 + e^{x_{uij}}} \frac{\partial x_{uij}}{\partial \theta} - \lambda_{\theta}\theta \end{align*} \]

在这里有

\[ x_{uij} = x_{ui} - x_{uj} = \sum\limits_{f=1}^kw_{uf}h_{if} - \sum\limits_{f=1}^kw_{uf}h_{jf} \]

因此很容易得到：

\[ \frac{\partial (x_{ui} - x_{uj})}{\partial \theta} = \begin{cases} (h_{if}-h_{jf})& {if\; \theta = w_{uf}}\\ w_{uf}& {if\;\theta = h_{if}} \\ -w_{uf}& {if\;\theta = h_{jf}}\end{cases} \]

也就是说，对于矩阵分解算法的参数 \(\theta\) 来说，user 的 f 维隐向量 \(w_{uf}\)，以及 item 的 f 维隐向量 \(h_{if}, h_{jf}\) 非常容易通过梯度上升法来求解。

2. 实现细节

摘抄一部分 C++ 代码

1
2
3
4
5
6
prob = sum(U(user_id, _) * (I(liked_id, _) - I(disliked_id, _)));
prob = 1 / (1 + exp(prob));
temp = U(user_id, i);
U(user_id, i) +=  alpha * (prob * (I(liked_id, i) - I(disliked_id, i)) - lamb*temp);
I(liked_id, i) += alpha * (prob * temp - rlamb * I(liked_id, i));
I(disliked_id, i) += alpha * (-prob * temp - lamb * I(disliked_id, i));

可以很清晰的看到所有的运算基于 \(\sigma(x_{uij})\) 以及 \(w_{uf}, h_{if}, h_{jf}\) 以及常数项 alpha, lambda。

negative item j 是通过抽样方式来确定的，实际在计算的过程中只考虑 positive item i，因为 negative item 很多，所以会在所有的 item 里随机抽一个，即便是抽到了 positive item 从概率上来讲也不会对计算速度和精度有太大影响，但速度会加快很多。（想象一下电商推荐场景，不点击的长尾商品很多）

在 51Talk 老师推荐的实际应用场景又有不同，我们只针对有评分（positive）的老师进行训练，来更新用户和老师的向量，实际效果更佳优异。