推荐系统 教程

推荐系统 召回

推荐系统 笔记

推荐系统 ALS 算法


ALS(Alternating Least Squares,交替最小二乘法)是矩阵分解方法中对损失函数最小化的一个求解方法,除此之外当然还有其他方法,比如 SVD 等。从协同过滤的分类来说,ALS 算法属于 User-Item CF,也叫做混合 CF,它同时考虑了 User 和 Item 两个方面。

矩阵分解

ALS 的矩阵分解算法常应用于推荐系统中,将用户(user)对物品(item)的评分矩阵,分解为用户对物品隐含特征的偏好矩阵物品在隐含特征上的映射矩阵。与传统的矩阵分解 SGD 方法来分解矩阵不同的是,ALS 希望找到两个低维矩阵。用户和物品的关系,可以抽象为如下的三元组:<User,Item,Rating>。其中,Rating 是用户对物品的评分,表明用户对该物品的喜好程度。

矩阵分解形式

矩阵分解是指将一个矩阵分解成两个或者多个矩阵的乘积。对于上述的用户-物品矩阵(评分矩阵),记为 \(R_{m×n}\)。可以将其分解成两个或者多个矩阵的乘积,假设分解成两个矩阵 \(P_{m×k}\) 和 \(Q_{k×n}\),我们要使得矩阵 \(P_{m×k}\) 和 \(Q_{k×n}\) 的乘积能够还原原始的矩阵 \(R_{m×n}\)

\(R_{m×n} \approx P_{m×k} × Q_{k×n} = \hat{R}_{m×n}\)

其中,矩阵 \(P_{m×k}\) 表示的是 m 个用户与 k 个特征之间的关系,而矩阵 \(Q_{k×n}\) 表示的是 k 个特征与 n 个物品之间的关系。特征的每一个维度代表一个隐性因子,比如对电影来说,这些隐性因子可能是导演、演员等。当然,这些隐性因子是机器学习到的,具体是什么含义我们不确定,且并不需要显式的定义这些关联维度,而只需要假定它们存在即可,这里的关联维度又被称为 latent factor。

一般情况下,k 的值远小于 m 和 n 的值,从而达到了数据降维的目的,k 一般的取值在 20~200。

预测模型

基于上述的描述,预测模型为 \(P_{m×k}\) 和 \(Q_{k×n}\) 两个矩阵的组合,这样便可以为用户 i 对商品 j 进行打分:

\(\sum_{k=1}^{K}p_{i,k}q_{k,j}\)

同时两个矩阵还可以用于比较不同的 User(或 Item)之间的相似度,如下图所示:

损失函数

可以使用原始的评分矩阵 \(R_{m×n}\) 与重新构建的评分矩阵 \(\hat{R}_{m×n}\) 之间的误差的平方作为损失函数,即:

\(e_{i,j}^2=(r_{i,j}^2-\hat{r}_{i,j}^2)=(r_{i,j}-\sum_{k=1}^{K}p_{i,k}q_{k,j})^2\)

最终,需要求解所有已知得分项(用户对物品有评分)的损失之和的最小值:

\(min\ L(p_*,q_*)=\sum_{i,j\ is\ known}e_{i,j}^2\)

目标函数

目标函数即为加入正则项的损失函数,通常在求解的过程中,为了能够有较好的泛化能力,会在损失函数中加入正则项,以对参数进行约束,加入 L2 正则的损失函数为:

\(E_{i,j}^2=(r_{i,j}−∑_{k=1}^{K}p_{i,k}q_{k,j})^2+\frac{β}{2}∑_{k=1}^{K}(p_{i,k}^2+q_{k,j}^2)\)

\(=(r_{i,j}−∑_{k=1}^{K}p_{i,k}q_{k,j})^2+λ∑_{k=1}^{K}|p_{i,k}|^2+λ∑_{k=1}^{K}|q_{k,j}|^2\)

通过 ALS 算法优化过程的推导

上述的目标函数的直接优化是很困难的,因为 p 和 q 的二元导数并不容易计算,这时可以使用类似坐标下降法的算法,固定其他维度,而只优化其中一个维度。

待完善。

ALS 算法的优缺点

ALS 算法的优点

  • 在实际应用中,由于待分解的矩阵常常是非常稀疏的,与 SVD 相比,ALS 能有效的解决过拟合问题。
  • 基于 ALS 的矩阵分解的协同过滤算法的可扩展性也优于 SVD。
  • 与随机梯度下降(SGD)的求解方式相比,一般情况下随机梯度下降比 ALS 速度快;但有两种情况 ALS 更优于随机梯度下降:
    • 当系统能够并行化时,ALS 的扩展性优于随机梯度下降法。
    • ALS-WR 能够有效的处理用户对商品的隐式反馈的数据。

ALS 算法的缺点

  • 它是一个离线算法,不能体现实时性。
  • 无法准确评估新加入的用户或商品,即存在冷启动(cold start)问题。