对比ALS和FM

作者: Colleen_oh | 来源:发表于2020-05-09 11:55 被阅读0次

最近在研究推荐系统矩阵分解算法。下面就来对比这两者。主要通过两者者公式区别、如何求解以及优缺点进行总结。都是个人总结。有问题的麻烦直接提出来哈！

本文围绕一下问题进行：

1、ALS和FM的公式原理

2、ALS与FM的求解过程（如何迭代）

3、ALS和FM的优缺点

一、ALS（Alternating Least Squares，交替最小二乘法）

ALS模型

ALS在推荐系统中就是将用户（user）对商品（item）的评分矩阵分解成2个矩阵：user对item 潜在因素的偏好矩阵(latent factor vector)，item潜在因素的偏好矩阵。这两个矩阵相乘最后会约等于原矩阵。： $R_{m\times n} = X_{m\times k}\times Y_{n\times k}^T$

如何求解？

那么问题来了 X和Y都是未知的。只要我们知道其中一个，就可以求解另一个了。

ALS的核心有个假设：打分矩阵是近似低秩的。换句话说，就是一个 $m\times n$ 的打分矩阵可以由分解的两个小矩阵 $X（m\times k）$ 和 $Y（k\times n）$ 的乘积来近似。这就是ALS的矩阵分解方法。

为了让X和Y相乘能逼近R，因此我们需要最小化损失函数(loss function)，因此需要最小化损失函数，在此定义为平方误差和(Mean square error, MSE)。

$Loss(X,Y)=\sum_{i,u}(r_{ui}-x_uy_i^T)^2$ ,其中 $r_{ui}$ 代表某个user对某个item的评分。

一般损失函数都会需要加入正则化项(Regularization item)来避免过拟合的问题，通常是用L2，所以目标函数会被修改为：

$Loss(X,Y)=\sum_{i,u}(r_{ui}-x_uy_i^T)^2 +\lambda （\sum_{u}||x_u||^2 + \sum_{i}||y_i||^2 ）$

上面介绍了“最小二乘（最小平方误差）”，但是还没有讲清楚“交替”是怎么回事。因为X和Y都是未知的参数矩阵，因此我们需要用“交替固定参数”来对另一个参数求解。

先固定Y, 将loss function对X求偏导，使其导数等于0：

再固定X, 将loss function对Y求偏导，使其导数等于0：

既然是交替，就会有迭代的模式存在：

迭代方法：先写出损失函数（最小二乘——最小平方误差），然后分别对 $x_u$ 和 $y_i$ 求偏导并令偏导结果等于0可以求出 $x_u$ 和 $y_i$ ,然后初始化Y，可以求出 $x_u$ ，把 $x_u$ 带入到 $y_i$ 中，可以求出 $y_i$ ，把两者代入到RMSE中，计算出结果。然后从求偏导开始迭代，知道迭代次数结束或者是达到预期RMSE结果。

优缺点？

优点：相比SVD可以解决稀疏矩阵分解的问题

缺点：对于隐变量个数选择比较敏感，k越大越精确，但是计算时间越长

参考：

推荐算法之矩阵分解——https://flashgene.com/archives/52522.html

协同过滤算法之ALS——https://www.biaodianfu.com/collaborative-filtering-als.html

ALS交替最小二乘法总结——https://www.cnblogs.com/arachis/p/ALS.html

FM（Factorization Machines，因子分解机）

因子分解机是从二阶多项式模型“进化”过来的。二阶多项式模型公式如下： $\hat{y} (X)=w_0+\sum_{i=1}^nw_ix_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^n w_{ij}x_i x_j$

其中 $x_ix_j$ 表示两个互异特征组合的二阶特征, $w_{ij}$ 表示二阶特征的交叉项系数。

上述二阶多项式模型却有一个致命的缺陷的训练是很困难的：数据稀疏性普遍存在的实际应用场景中，二阶特征系数 $w_{ij}$ 是很困难的。

原因是：

（1） $w_{ij}$ 的学习需要大量特征分量X都非零的样本。

（2）样本本身是稀疏的，同时满足 $x_ix_j\neq 0$ 的样本非常少。

由于以上原因，大佬们就将 $w_{ij}$ 表示为另一种形式。即引入辅助隐向量 $v_i$ 。公式如下： $w_{ij}=<v_i,v_j>=\sum_{f=1}^kv_{if}v_{jf }$ ，于是就可以改写为FM模型： $\hat{y} (X)=w_0+\sum_{i=1}^nw_ix_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^n <v_i,v_j>x_i x_j$ ，

（表示FM模型的偏置）

$w\in R^n$ （表示FM模型对一阶特征的建模）

$V\in R^{n\times k}$ （表示FM模型对二阶特征的建模）

参数的个数为： $1+n+nk$

模型复杂度 $O(n^2k)$

化简方程

首先化简二阶项系数项。

对上述化简过程做一些解释：

第1个等号：对称方阵 $\hat{W}$ 的所有元素之和减去主对角线元素之和

第2个等号： $<v_i,v_j>$ 向量内积展开成累加形式

第3个等号：提出公共部分 $\sum_{f=1}^k$

第4个等号：表示为“和平方”减去“平方和”

带入化简后的表达式，FM模型方程为： $\hat{y} (X)=w_0+\sum_{i=1}^nw_ix_i+\frac{1}{2} \sum_{f=1}^{k}[(\sum_{i=1}^n (v_{if}x_i))^2-\sum_{i=1}^n v_{if}^2x_i^2]$

损失函数

对于回归问题，损失函数可以取最小平方误差函数： $loss(\hat{y},y )=\frac{1}{2} (\hat{y} -y)^2$

对于分类问题，损失函数可以取logit逻辑函数: $loss(\hat{y},y )=log(1+e^{-\hat{y} y})$

最优化目标函数：

$\theta ^*=argmin\sum_{i=1}^N loss(\hat{y_i} ,y_i)$

如何求解？

首先对目标函数求偏导，目标函数对模型参数的偏导数通式为：

$loss$ 对模型估计函数 $\hat{y} (X)$ 的偏导数为：

对于FM模型而言，优化的参数为： $\theta ^*=\left\{ w_0,w,V \right\}$ ，则FM模型方程对各个参数 $\theta ^*$ 的偏导数为：

于是对于FM模型的优化问题，我们可以采用SGD优化目标函数.

FM模型的算法步骤：

优缺点？

优点：

（1）FM模型对特征的一阶组合和二阶组合都进行了建模

（2）FM模型通过MF思想，基于K维的Latent Factor Vector，处理因为数据稀疏带来的学习不足问题

（3）FM模型的训练和预测的时间复杂度是线性的

（4）FM模型可以用于DNN的embedding

（5） FM是一个通用模型，它可以用于任何特征为实值的情况

缺点：

每个特征只引入了一个隐向量，不同类型特征之间交叉没有区分性

参考：

FM模型的算法思想——https://www.jianshu.com/p/8d792422e582

FM、FFM——https://www.jianshu.com/p/1db7404689c5

总结

其实ALS和FM都是比较好理解的，ALS则是直接对于评分矩阵做矩阵分解，则FM则是在二阶多项式模型公式基础上把二阶系数改成了隐向量的形式。

算法上共同点：

1、两者都进行了隐语义分解

3、都可以解决评分矩阵稀疏的问题

FM运行的速度是比ALS快的。接下来还会继续挖掘FM！！！

参考：

关于矩阵分解：特征值分解 svd分解 mf分解 lmf分解 pca 以及个性化推荐 fm ffm als——https://blog.csdn.net/weixin_37589896/article/details/78423493

对比ALS和FM

一、ALS（Alternating Least Squares，交替最小二乘法）

ALS模型

如何求解？

优缺点？

FM（Factorization Machines，因子分解机）

化简方程

如何求解？

FM模型的算法步骤：

优缺点？

总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

对比ALS和FM

一、ALS（Alternating Least Squares，交替最小二乘法 ）

ALS模型

如何求解？

优缺点？

FM（Factorization Machines，因子分解机）

化简方程

如何求解？

FM模型的算法步骤：

优缺点？

总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

一、ALS（Alternating Least Squares，交替最小二乘法）