[paper阅读] 度量分解: 矩阵分解之下的推荐(二)

背景

推荐中的矩阵分解

矩阵分解是物品推荐中最有效的技术之一. 矩阵分解用于推荐系统的第一个版本是Simon Funk等人Netflix比赛的评分任务. 之后的研究改进了矩阵分解, 并且提供了很多变种. 例如, Koren等人引入了用户和物品偏置来对针对用户和物品特定的特征进行建模(详情见参考资料4). Salakhutdinov等人将矩阵分解解析为一个概率图形模型来缓解真实数据集中的稀疏和不平衡问题(详情见参考资料56). 矩阵分解也可以被泛化到解决个性化物品推荐问题. 基于矩阵分解的两个典型top-N推荐模型为: BPR(Bayesian Personalized Ranking, 贝叶斯个性化排序)以及WRMF(Weighted Regularized matrix factorization, 加权正则化矩阵分解, 详情见资料8). BRP从贝叶斯的角度解决排序问题, 其目标是尽量拉开已经观察到的用户-物品对和未观察到的用户-物品对之间的距离( 详情见资料7). WRMF是另一个物品排序的高效算法. WRMF使用隐式的二进制反馈作为二进制实例, 然后考虑用户-物品交互矩阵中的所有条目(包括未观察到的条目). WRMF有一个置信值来控制正负例条目的权重.

推荐中的神经模型

正如之前提到的, 尽管MF取得了一定的效果, 它的能力被点积限制. 而研究人员们也尝试了一些方法来克服这个问题. 方法之一是在矩阵分解中引入非线性. Dziugaite等人提出了矩阵分解的神经网络泛化, 使用非线性神经网络对用户-物品关系进行建模. 其基本思想是: 在用户和物品潜在因子元素级别的点积上使用非线性的激活函数(详情见资料9). He等人沿着这个思路, 提出了NeuMF(Neural collaborative filtering, 神经协同过滤)模型用于个性化排序任务. NeuMF由一个泛化的MF和一个多层感知机组成. 它将one-class的协同过滤问题转化为一个分类任务, 然后使用交叉熵损失来优化网络(详情见资料3).
Wu 等人提出了在交互模型中使用降噪自动编码机引入非线性的方法(详情见资料10). 当然, 也有一些其他研究通过使用神经网络融合辅助信息. 然而, 这些研究主要关注克服点乘的局限性, 作者将额外信息建模作为未来的一项工作. 可以通过查阅资料11了解更多关于这个主题的信息.

推荐中的度量学习

另一个有希望的尝试是直接采用一个满足三角不等式定理的度量. CML(Collaborative metric learning) 是一个将度量学习推广到协同过滤的方法(详情可查阅资料12). CML遵循了LMNN(largest margin nearest neighbor, 最大边缘最近邻)算法的思想. LMNN希望估计一个线性转化来定义一个距离度量,最小化期望的kNN分类错误. LMNN由两个严格的操作组成: pullpush. pull操作主要用于将相同类中的实例拉得更近, 而push操作则希望将不同类中的实例推得更远(详情可查阅资料13). 严格说来, CML不学习转化函数, 而希望学习到用户和物品的向量. 它只有一个push的术语, 这就意味着CML值能将用户不喜欢的数据推开, 但是没有提供一个策略将用户和喜欢的物品拉得更近. Hsieh等人提到: CML的损失函数在遇到欺诈实例时也会将正向的物品拉近. 然而, 这种非直接的pull力与LMNN中的相比弱了很多, 可能会造成过度拥塞的问题, 可能会造将可能的推荐候选集推得太远, 从而只能得到次佳的效果.

本文提出的方法

在本章节中, 将会介绍FML(Factorized metric learning, 分解度量学习)方法. 图1中展示了FML的简要高层概述, 假设有M个用户和N个物品, 偏好(评分或隐式交互)矩阵表示为: $R \in \mathcal{R}^{M\times N}$. $R_{ui}$表示用户u对物品i的偏好. R的值可以是显式的评分(例如评分)也可以是隐式返回. 显式评分可以用于针对未知条目的评分估计, 而隐式反馈一般用于个性化排序. 这两个问题都是推荐领域非常常见的问题, 在这里不做过多解释.


1 FML的简单表示. 其主要有两个步骤: 1. 将偏好矩阵(评分或交互)通过公式1转化为距离矩阵. 2. 将距离矩阵分解为一个度量向量空间中的用户和物品坐标.

偏好转化为距离

作者们希望将度量向量空间拆开, 通过分解学习物品和用户的位置. 矩阵分解通过将评分矩阵(显式/隐式反馈)分解成点积来学习用户和物品的潜在因子. 偏好矩阵也可以被看作是相似性矩阵, 由于相似性和距离是相反的概念, 首先, 需要把用户偏好转化为距离.

在本文中, 作者提供了一个简单但是高效的等式. 通过下面的公式得到距离矩阵:

$\text{Distance}(u, i) = \text{Max Similarity} – \text{Similarity}(u, i)$ 公式1

Max Similarity可能是评分的最大值(例如, 5)或者隐式反馈的最大值(例如, 1). 通过这样的翻转操作, 可以在保持其分布的同时, 将偏好(相似性)转化为距离. 这个转化可以同时应用于显式和隐式的反馈. 距离是两个对象之间分开多远的数值度量. 距离函数应该满足四个严格的条件: 1. 非负性, 2.不可分的同一性, 3.对称性, 4. 三角不等式. 在不同的应用领域有着很多不同的距离函数, 例如: 离散距离, 欧式距离以及图距离等. 在欧式空间$\mathcal{R} ^k $中, 两点之间的距离通常是通过欧式距离(或$l_2$范式距离)进行度量的. 由于其简单的形式和有用的属性, 欧式距离经常被用于机器学习/传感器网络/几何学/面部识别等. 在实践中, 经常采用平方欧式距离以避免计算平方根的问题.

假设用户和物品在度量向量空间的位置表示为$P_u \in \mathcal{R}^k$和$Q_i \in \mathcal{R}^k$. 我们使用平方欧式距离来度量用户和物品之间的距离:

$\mathcal{D}(u,i)={||P_u-Q_i||}_2^2$ 公式2

1简单展示了FML的流程. 首先, 基于公式1基于偏好矩阵获得距离矩阵, 然后将距离矩阵进行分解. 然后学习到用户和物品的位置. 在此之后, 在必要的情况下, 我们可以非常容易地恢复偏好矩阵并且生成推荐.

物品排序中的距离分解

在只有隐式反馈的情况下, 个性化排序是推荐系统中非常重要的一个任务. 在许多现实的应用中, 隐式数据(例如, 购买记录/收听记录/点击)比显式反馈更容易获取, 这就导致对隐式反馈进行建模成为一个主要的关注点. 与之前的研究一样, 本文将隐式反馈定义为二级制数据. 1表示喜欢, 而0表示其它情况. 首先, 使用下面的转化公式将隐式反馈转换成距离:

$Y_{ui}=a\cdot (1-R_{ui})$ 公式3

由于$R_{ui}$要么等于1, 要么等于0, 那么在$R_{ui}=0$的情况下, 距离$Y_{ui}=a$, 在$R_{ui}=1$的情况下, 距离$Y_{ui}=0$, 使得控制用户和物品之间的距离变得非常灵活.

对于排序任务, 将未观察到的交互(负面示例)考虑进去也是非常有益的. 例如, BPRCML通过对每个观察到的交互采样一个负向物品使用成对的方式进行训练. WRMFNeuMF采用逐点的学习, 但是也考虑了负向物品. 在本文中, 由于作者希望直接将距离分解为用户和物品的嵌入, 在这里, 采用了逐点的损失:

$\mathcal{L}(P,Q) = \sum_{(u,i)\in R}c_{ui}{(Y_{ui}-\mathcal{D}(u,i))}^2$ 公式4

在这里, 考虑了所有的未观察到的交互. $c_{ui}$是一个置信值, 定义为$c_{ui} = 1 + \alpha w_{ui}$, 其中, $w_{ui}$表示隐式反馈的观察. 将显式反馈发生的频率作为观察, 例如, 如果一个用户浏览了某个物品两次, 那么$w_{ui}=2$. 对于较大的数字, 也可以将其转化为log形式. 由于这个信息在公开可用的数据集上经常缺失, 可以将w设置为$R_{ui}$(0或者1). 具体的正则化策略将会在3.4部分进行介绍. 尽管采用的是逐点的训练模式, FML的模型不仅可以将用户和他们偏好的物品更接近, 还可以将不喜欢的物品推远. 不像大部分基于度量学习的模型, 通过一些明确的界限来将用户兴趣领域之外的虚假操作, 本方法中的置信机制提供了负向物品入侵用户领域的可能性, 由于它可以作为一个过滤器从推荐的负面候选集中挑选物品. 模型的另一个重要特征是: 可以间接地将有大量相同物品集合的用户聚在一起. 这个属性使得获取邻居用户之间的关系变得可能, 而这对物品推荐来说也非常重要.

评分预测中的距离分解

正如上面提到的, FML也可以使用于评分估计. 对于评分估计, 只考虑观察到的交互数据已经足够并且更加高效. 假设$\mathcal{K}$ 表示观察到的评分数据. 首先, 使用下面的公式将评分矩阵R转化到距离:
$Y_{ui}=R^{max}-R_{ui}$ 公式5
其中, $R_{max}$为最大的评分. 如果$R^{max}=5$, 当评分为3时, 距离$Y_{ui}=5-3=2$.

与矩阵分解想用, 用户或者物品的单个属性也会有影响. 例如, 一些物品倾向于会受到更高的评分, 而一些用户可能会给更低的评分. 因此, 作者们将全局的用户和物品偏好信息集成到了方法中用于评分估计. 最终的评分函数形式化如下:
$\hat{y} = \mathcal{D}(u, i) + b_u + b_i + \mu$ 公式6

其中, $\hat{y}$表示预测的距离, $b_u$和$b_i$分别为用户和物品的偏好项, $\mu$为全局偏好, 等于训练集数据的平均距离. 一般说来, 可以加一个超参$\tau$ 来将$\mu$缩放到一个合适的值.

另一个重要的方面是: 作者们希望考虑评分数据的可靠性和稳定性. 大部分评分预测算法忽略了评分的噪音, 并且假设所有的评分都是置信的. 然而, 并不是所有的评分都应该获得相同的权重. 例如, 一些用户在不同时间在对相同的物品进行评分时可能会给出两个不同的分数. 之前的研究表明: 极端的评分(例如, 1或者5)比中间的评分(2,3.4)更加可靠. 为了缓解这种情形, 作者们提出对每个评分提供以这个置信值$c_{ui}$, 然后获得损失函数:
$\mathcal{L} = \sum_{(u,i)\in \mathcal{R}} {c_{ui}(Y_{ui}-\hat{Y})}$ 公式7

注意: 置信$c_{ui}$可以表示很多因素. 根据参考资料15的结论, 作者设计了一个新颖的置信机制将更高的置信值分类给更可靠的评分.

$c_{ui} = 1+\alpha \cdot g(R_{ui} – R^{max}/2)$ 公式8

其中, $g(\cdot)$ 可以是绝对值, 平方甚至是对数函数. $\alpha$(置信级别)是一个超参, 来控制置信的幅度. 这个置信机制保证了极端的分数获得更高的置信. 也可以使用别的方式来替换这个置信策略.

正则化

传统的矩阵分解一般对潜在因子和偏置项使用$l_2$正则以避免过于复杂的解决方案. 在这里, 作者们引入了另外两个正则选项: norm clippingdropout.

Norm Clipping: 对于P, Q, $l_2$正则是不适用的, 因为它会将用户和物品都推向远点. 在这里, 作者没有最小化$l_2$正则, 作者们将对欧式球的限制进行了放松, 然后在每次更新之后执行$l_2$ norm clipping.
${||P_u||_2\le l, ||Q_i||_2\le l}$ 公式9

使用l来控制欧式球的大小. 这两个限制作为正则式来讲$U_u$和$V_i$的值限制在了$l_2$正则单位的球中, 使得数据点不会发散太宽, 有助于克服维度问题的诅咒. 这个操作一般在每次迭代更新参数之后执行.

dropout: 在神经网络中, dropout是一个解决过拟合问题简单但是有效的方法. 主要思想是在训练阶段丢掉一些神经元以避免神经元单位之间的共同适应. 在文章中, 作者们提出了一个新颖的/针对欧氏距离的dropout策略. 最终的欧氏距离是每个维度距离之和. 为了避免不同纬度之间的共同适应, 作者们提议随意删除一些维度,然后使用下面的公式计算整体的距离:

${||P_u – Q_i||}^2_2={|P_{u1}-Q_{i1}|}^2 + \underbrace{{|P_{u2}-Q_{i2}|}^2}{drop} + \underbrace{{|P{u3}-Q_{i3}|}^2}{drop} + \cdots + {|P{uj}-Q_{ij}|}^2 + \cdots + \underbrace{{|P_{uk}-Q_{ik}|}^2}_{drop}$

在上面的示例中, 作者删除了第二个,第三个一级第k个维度, 因此, 这些维度不会在特定的轮中用于距离的计算. dropout的维度在每一轮中均会变化. 注意: dropout只会在训练阶段执行.

在评分预测模型中, 作者们依然使用正则率为$\lambda$ 的 $l_2$正则对用户和物品偏置进行正则化.

优化和推荐

对于评分估计和排序学习模型, 作者们均使用Adagrad进行优化. Adagrad基于更新的频率来调整参数的步数大小. 这样的做法可以减少调整学习率的需求. 在推荐部分, 首先计算用户和物品之间的距离$\hat{Y}{ui}$, 对于评分预测, 作者们使用下面的规则重构评分: $\hat{R}{ui}=R^{max}-\hat{Y}{ui}$, 例如, 如果$\hat{Y}{ui}=4, R^{max}=5$, 那么预测的评分将是1. 对于物品排序, 直接使用降序对距离进行排序即可, 离目标用户较近的物品将会被推荐.

模型复杂度

FML在评分预测任务中的复杂性与评分数成线性正比. 可以在$O(|\mathcal{K}|k)$的时间复杂度内训练完成, 其中k是潜在因子的维度, $\mathcal{K}$为观察到的评分数. 对于物品排序, 由于会包含所有交互矩阵的条目, 因此其模型复杂度为: $O(|R|k)$. 具体地, 它会花大概50s来获得一个在Movielen 100K数据集中比较好的评分预测推荐效果(在一个VIDIA TITAN XPascal GPU上). 对于FilmTrust中的物品排序, 每次迭代的计算时间大约是15s. 一般迭代30次左右就能实现一个令人比较满意的结果.

延伸探究

5. 距离满足的四个条件分别是什么意思?

  • 非负性: $d(x,y)\le 0$
  • 不可分的同一性: $d(x,y) = 0$, 当且仅当$x=y$
  • 对称性: $d(x,y) = d(y, x)$
  • 三角不等式: $d(x,z) \le d(x,y) + d(y,z)$

6. 离散距离/欧式距离/图距离分别如何度量?

  • 离散距离: 如果x=y, 那么d(x,y)=0, 否则d(x,y)=1
  • 曼哈顿距离: $d(x,y)=|x_1-x_2|+|y_1-y_2|$, 也成为$l_1$范数, $l_1$正则化可以产生稀疏权值矩阵,即产生一个稀疏模型,可以用于特征选择
  • 欧式距离: 平移和旋转不变的距离, $d(x,y)=\sqrt{(x_1-y_1)^2 + (x_2-y_2)^2 + \cdots + (x_n-y_n)^2}$, 也成为$l_2$范数, $l_2$正则化可以防止模型过拟合; 一定程度上,$l_1$也可以防止过拟合, 其原理可以查阅资料14
  • 图距离: 依特定图内的距离定义出度量

参考资料

  1. 机器学习中的数学基础:向量篇
  2. Hulu机器学习问题与解答系列 | 第五弹:余弦距离
  3. Neural Collaborative Filtering
  4. Matrix Factorization Techniques for Recommender Systems
  5. Probabilistic Matrix Factorization
  6. Bayesian probabilistic matrix factorization using Markov chain Monte Carlo
  7. Bayesian Personalized Ranking from Implicit Feedback
  8. Collaborative Filtering for Implicit Feedback Datasets
  9. Neural Network Matrix Factorization
  10. Collabora- tive Denoising Auto-Encoders for Top-N Recommender Systems
  11. DeepLearningbasedRecommender System: A Survey and New Perspectives
  12. Collaborative Metric Learning
  13. Distance Metric Learning for Large Margin Nearest Neighbor Classification
  14. 机器学习中正则化项L1和L2的直观理解
  15. Comparisons Instead of Rat- ings: Towards More Stable Preferences
打赏

mickey

记录生活,写给几十年后的自己。

发表评论

电子邮件地址不会被公开。 必填项已用*标注