推荐系统-矩阵分解
  • Jul 13, 2019
  • 8 minutes read

矩阵分解

近邻模型存在的问题：

  1. 物品之间存在相关性，信息量并不随着向量维度增加而线性增加。
  2. 矩阵元素稀疏，计算结果不稳定，增减一个向量维度，导致近邻结果差异很大的情况存在。

矩阵分解，直观上就是把原来的大矩阵，近似分解成两个小矩阵的乘机，在实际推荐计算时不再使用大矩阵A，而是使用分解得到的两个小矩阵U和V，公式如下：

$$ U_{m \times k} V_{n \times k}^T \approx A_{m \times n} $$

SVD

SVD全称奇异值分解，在推荐系统中实际使用的是伪奇异值分解。是将用户物品评分矩阵分解成两个小矩阵，一个矩阵是代表用户偏好的用户隐因子向量组成，该矩阵中每个用户对应一个k维向量；另一个矩阵是代表物品语义主题的隐因子向量组成，该矩阵中每个物品对应一个k维向量。两个矩阵相乘之后就得到了任何一个用户对任何一个物品的预测评分。

矩阵分解换个说法就是在做矩阵填充，将原本的矩阵中没有的值填充起来。

假设用户u的向量是pu，物品i的向量是qi，那么，要计算物品i推荐给用户u的推荐分数，直接计算点积即可：

$$ r_{ui} = p_u q_i^T $$

重点在于得到每一个用户和每一个物品的K维向量，是一个机器学习问题，一般考虑两个核心要素：

  1. 损失函数
  2. 优化算法

SVD的损失函数是：

$$ \min_{q*,p*} \sum_{(u,i) \in \kappa } (r_{ui} - p_u q_i^T) + \lambda (| | q_i | |^2 + | | p_u | |^2) $$

分成两部分：

  1. 前一部分： 用分解后的矩阵预测分数，要和实际的用户评分之间误差越小越好
  2. 后一部分： 得到的隐因子向量要越简单越好，正则化项，控制模型的方差

SVD计算过程

  1. 准备好用户物品的评分矩阵，每一条评分数据看做一条训练样本
  2. 给分解后的U矩阵和V矩阵随机初始化元素值
  3. 用U和V计算预测后的分数
  4. 计算预测的分数和实际的分数误差
  5. 按照梯度下降的方向更新U和V中的元素值
  6. 重复步骤3和5，直到达到停止条件

得到分解后的矩阵之后，实质上就是得到了每个用户和每个物品的隐因子向量，用户和物品隐因子向量计算点积就是推荐分数。

增加偏执信息

每个用户的评价标准不同，需要将该因素考虑到损失函数中，原本的一个用户给一个物品的评分变为由四部分相加：

$$ r_{ui} = \mu + b_i + b_u + p_u q_i^T $$

从左到右分别代表：全局平均分，物品的评分偏置，用户评分的偏置，用户和物品之间的兴趣偏好。

目标损失函数变为：

$$ \min_{q*,p*} \sum_{(u,i) \in \kappa } (r_{ui} - \mu - b_i - b_u - p_u q_i^T) + \lambda (| | q_i | |^2 + | | p_u | |^2 + b_i^2 + b_u^2) $$

比基础的SVD多学两个参数，用户偏置和物品偏置

增加历史信息

在SVD中结合用户的隐式反馈行为和属性的模型叫SVD++。

如果一个用户还没有对物品进行评分，则可以根据他的隐式反馈行为和属性如性别等，做出预测，可以弥补冷启动问题。

在推荐分数预测部分，原来的用户向量那部分增加了隐式反馈向量（用户已经操作过的物品隐因子向量）x 和用户属性向量 y。实际上，每隔隐式反馈对象ID都是特征，这些特征背后都有一个K维的隐因子向量，所有这些隐因子向量都是未知参数，同等地位被优化，都是随机初始化　：

$$ r_{ui} = \mu + b_i + b_u + (p_u + | N(u)| ^{-0.5} \sum_{i \in N(u)} x_i + \sum_{a \in Au}y_a)q_i^T $$

考虑时间因素

人是会随着时间变化的，因此考虑时间因素的影响也是必要的，常见做法：

  1. 对评分按照时间加权，让久远的评分更趋近平均值
  2. 对评分时间划分区间，不同的时间区间内分别学习出隐因子向量，使用时按照区间使用对应的隐因子向量来计算
  3. 对特殊的日期，如节日、周末等训练对应的隐因子向量

Ｆacebook怎么为10亿人互相推荐好友

矩阵分解有了目标函数之后，就是需要优化算法来计算最优参数值。常见的优化方法有两个：

  1. 随机梯度下降(SGD)
  2. 交替最小二乘(ALS)

Facebook的推荐系统中主要使用的方法是ALS。

ALS原理

目标是找到两个矩阵Ｐ和Ｑ，让他们相乘之后等于原矩阵Ｒ：

$$ R_{m \times n} = P_{m \times k} \times Q_{n \times k}^T $$

重点在于Ｐ与Ｑ都是未知的，如果知道其中任意一个，就可以利用线性代数标准解法求解另一个。交替最小二乘通过迭代的方式解决了这个鸡生蛋蛋生鸡的问题：

  1. 初始化随机矩阵Ｑ里边的元素值
  2. 把Ｑ矩阵当做已知的，直接用线性代数的方法求解矩阵Ｐ
  3. 得到了矩阵Ｐ之后，把Ｐ当做已知的，故技重施，回去求解矩阵Ｑ
  4. 上面两个过程交替进行，一直到误差可以接受为止

ALS优点：

  1. 在假设已知其中一个矩阵求解另一个时，要优化的参数是很容易并行化的
  2. 在不那么稀疏的数据集上，交替最小二乘通常比随机梯度下降要更快地得到结果

隐式反馈

预测行为问题，叫One-Class问题，因为如果将行为预测看成一个二分类问题，预测用户会不会做某件事，但是收集到的数据只有用户干了什么，而用户明确“不干”某件事的数据却没有明确表达。

One-Class数据也是隐式反馈的通常特点。

对隐式反馈的矩阵分解，改进的交替最小二乘法叫加权交替最小二乘：Weighted-ALS.

行为的次数是对行为的置信度反应，这就是加权。

加权交替最小二乘对待隐式反馈：

  1. 如果用户对物品无隐式反馈则认为评分是０
  2. 如果用户对物品有至少一次隐式反馈则认为评分是１，次数作为该评分的置信度

此时的目标函数变为：

$$ \min_{q*,p*} \sum_{(u,i) \in \kappa } c_{ui}(r_{ui} - p_u q_i^T) + \lambda (| | q_i | |^2 + | | p_u | |^2) $$

C_ui就是置信度，在计算误差时考虑反馈次数，次数越多，就越可信。通常置信度不等于反馈次数，公式如下：

$$ C_{ui} = 1 + \alpha C $$

α为超参数，需要调整，默认值为４０可以得到差不多的效果，Ｃ就是反馈次数。

单纯这样对待隐式反馈，会产生大量的缺失值为０的情况，样本严重不平衡，但是矩阵分解的目的就是去预测填充这些缺失值，解决方法是负样本采样：挑一部分缺失值作为负类样本即可。

挑选负样本的方法：

  1. 随机均匀采样和真类别一样多，实践中不靠谱
  2. 按照物品的热门程度采样，实践中靠谱

推荐计算

分解后的矩阵Ｐ和Ｑ，Ｐ的行向量对应每个用户的隐因子向量，代表它的兴趣，Ｑ的行向量对应每个物品的隐因子向量，代表它的主题或语义，两个都是稠密向量，可以认为两者是一一对应的，用户的兴趣就是表现在物品的语义维度上的。

但是对于超高维度数据情况如Facebook来说，直接对用户和物品的隐因子向量点积运算复杂度太高，不太现实，因此Facebook使用了：

  1. 利用一些专门的数据结构存储所有物品的隐因子向量，从而实现通过一个用户向量可以返回最相似的Ｋ个物品，FB开源实现了Faiss(使用Ball Tree来存储物品向量)，,其他的实现有Annoy, KGraph, NMSLIB。如果需要动态增加新的物品向量到内存数据中，推荐Faiss，不是推荐NMSLIB或者KGraph。用户向量可以存储在内存数据中，可以在用户访问时，实时产生推荐结果。
  2. 先使用物品的隐因子向量进行聚类，海量的物品会减少为少量的类别。然后再逐一计算用户和每个聚类中心的推荐分数，给用户推荐物品就成了给用户推荐物品聚类。

总结

在真正的推荐系统的实际引用中，评分预测实际上场景很少，而且数据也很少。因此相比预测评分，预测“用户会对物品干什么事”，会更加有效。针对预测行为One-Class问题，负样本太多，需要改进的加权最小二乘作为矩阵分解方法，被Facebook采样在了他们的推荐系统中。

贝叶斯个性化排序

矩阵分解的不足

针对单个用户对单个物品的偏好程度进行预测，得到结果后再排序的问题，在排序学习中行话叫做point-wise，其中point意思就是：只单独考虑每个物品，每个物品像是空间中孤立的点一样。与之相对，直接预测物品两两之间的相对顺序的问题，就叫做pair-wise。

前面讲解的矩阵分解都是属于point-wise模型。这类模型只能收集到正样本，没有负样本，于是认为缺失值就都是负样本（实际上有很多并不是缺失值），再以预测误差为评判标准去逼近这些样本。

贝叶斯个性化排序

推荐系统中跟直接的推荐模型应该是，能够较好地为用户排列出更好的物品相对顺序，而非更精确的评分。

针对相对排序，评价指标是AUC，全称是Area Under Curve，即ROC曲线下的面积。

AUC在数学上等价于：模型把关心的那一类样本排在其他样本前面的概率，最大是1，完美结果，0.5是随机排序，0就是完美错过。

贝叶斯个性化排序(BPR: Bayesian Personalized Ranking)主要做了：

  1. 一个样本构造方法
  2. 一个模型目标函数
  3. 一个模型学习框架

构造样本

前面介绍的矩阵分解，训练时候的样本是：用户、物品、反馈，反馈包含真实反馈和确实值，缺失值充当的是负样本职责。 BPR关心的是物品之间对于用户的相对顺序，构造的样本是：用户、物品１、物品２、两个物品相对顺序。其中，两个物品相对顺序的取值为：

  1. 物品１消费过，物品２没有，取值为１，是正样本
  2. 物品２消费过，物品１没有，取值为０，是负样本
  3. 样本中不包含其他情况：物品１和物品２都是消费过的，或者都是没消费过的

训练数据反应的是用户偏好的相对顺序，使用时，是用户还没有消费过的物品，但是仍然可以得到物品的相对顺序。

目标函数

BPR的目标函数是最大化交叉熵，也是预测了物品１在物品２前面的似然概率。目标函数要防止过拟合，加上正则项，正则项认为模型参数有个先验概率，这是贝叶斯学派的观点，也是BPR中“贝叶斯”的来历。

BRP认为模型的先验概率符合正太分布，所以采用L2正则化方法。目标函数如下：

$$ \prod_{u,i,j} p(i > j| \theta) p(\theta) $$ 所有样本都计算，模型参数先验概率p(theta)，和似然概率的乘积，最大化这个目标函数就能得到分解后的矩阵参数，其中theta就是分解后的矩阵参数。

训练方法

梯度下降或者随机梯度下降，前者收敛慢，后者训练快但是不稳定。BPR作者结合重复抽样的梯度下降，如下：

  1. 从全部样本中有放回地随机抽取一部分样本
  2. 用这部分样本，采用随机梯度下降优化目标函数，更新模型参数
  3. 重复步骤1，知道满足条件

这样，就得到了一个更符合推荐排序要求的矩阵分解模型了。

本文是《推荐系统三十六式》的读书笔记，仅限个人学习，请勿用作商业用途，谢谢。

Note: Cover Picture

  • RS
    • Previous
    推荐系统-近邻推荐
    Next
    推荐系统-模型融合