FM模型的算法思想

作者: PrivateEye_zzy | 来源:发表于2019-08-16 16:42 被阅读0次

本章涉及到的知识点清单：

1、LR模型方程

2、多项式模型方程

3、FM模型方程

4、矩阵分解

5、FM模型化简

6、损失函数

7、目标函数

8、最优化目标函数

9、FM模型的算法步骤

10、案例演示

11、FM模型的优势

一、LR模型方程

对于监督学习，机器学习模型的预测是一个估计函数 $\hat{y}$ （映射F）

监督学习

其中 $X$ 属于n维特征向量，即 $X \ \epsilon \ \mathbb{R}^{n}$ ， $y$ 属于目标值，回归问题中 $y \ \epsilon \ \mathbb{R}$ ，二分类问题中 $y \ \epsilon \ \{ -1,+1 \}$

我们首先回顾一般的线性回归方程LR，对于输入任意一个n维特征向量 $X = (x_{1},x_{2},...,x_{n})$ ，建模估计函数 $\hat{y}(X)$ 为

LR模型方程

LR模型的参数为： $w_{0} \ \epsilon \ \mathbb{R}$ ， $w \ \epsilon \ \mathbb{R^{n}} = (w_{1},w_{2},...,w_{n})$

从LR模型方程中我们可以看到：

（1）各个特征分量 $x_{i}$ 和 $x_{j}$ $(i \neq j)$ 彼此之间是独立的

（2） $\hat{y}(X)$ 将单个特征分量线性的组合起来，却忽略了特征分量彼此之间的相互组合关系

对于特征的组合关系，我们定义：

（1）一阶特征：即单个特征，不产生新特征，如 $x_{1}$

（2）二阶特征：即两个特征组合产生的新特征，如 $x_{1}x_{2}$

（3）高阶特征：即两个以上的特征组合产生的新特征，如 $x_{1}x_{2}x_{3}$

所以LR模型只考虑了一阶特征的线性组合关系

二、多项式模型方程

为了克服模型欠缺二阶特征组合因素，我们将LR模型改写为二阶多项式模型

二阶多项式模型

其中 $x_{i}x_{j}$ 表示两个互异特征组合的二阶特征， $w_{ij}$ 表示二阶特征的交叉项系数

至此，该模型似乎已经加入了特征组合的因素，接下来只要学习参数即可

但是，上述二阶多项式模型却有一个致命的缺陷：

数据稀疏性普遍存在的实际应用场景中，二阶特征系数 $w_{ij}$ 的训练是很困难的

造成学习困难的原因是：

（1） $w_{ij}$ 的学习需要大量特征分量 $x_{i}$ 和 $x_{j}$ 都非零的样本

（2）样本本身是稀疏的，同时满足 $x_{i}x_{j} \neq 0$ 的样本非常稀少

所以多项式模型虽然加入了二阶特征组合，却受到数据稀疏的影响

三、FM模型方程

为了克服模型无法在稀疏数据场景下学习二阶特征系数 $w_{ij}$ ，我们需要将 $w_{ij}$ 表示为另外一种形式

为此，针对样本 $X$ 的第i维特征分量 $x_{i}$ ，引入辅助隐向量 $v_{i}$

辅助隐向量

其中k为超参数，表示特征分量 $x_{i}$ 对应一个k维隐向量 $v_{i}$ ，则将 $w_{ij}$ 表示为：

二阶特征系数

上式引入隐向量的含义为：

二阶特征系数 $w_{ij}$ 等价于：特征分量 $x_{i}$ 和 $x_{j}$ 对应的隐向量 $v_{i}$ 和 $v_{j}$ 的内积 $<v_{i}, v_{j}>$ ，这就是FM模型的核心思想

则我们将二阶多项式模型改写为FM模型

FM模型方程

从FM模型方程可知，FM模型的参数为：

FM模型的参数

各个参数的意义为：

（1） $w_{0} \in \mathbb{R}$ 表示FM模型的偏置

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

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

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

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

下面我们从数学的角度来分析FM模型方程的可行性

四、矩阵分解

我们引入下面几个矩阵

（1）每个特征 $x_{i}$ 对应的隐向量 $v_{i}$ 组成的矩阵 $V$ ：

V矩阵

即矩阵 $V$ 的第i行表示：第i维特征 $x_{i}$ 的隐向量 $v_{i}$

则矩阵 $V^{T}$ 为：

V矩阵转置

（2）多项式模型的二阶特征系数 $w_{ij}$ 组成的方阵 $W$

多项式模型的W方阵

（3）FM模型的二阶特征系数 $<v_{i}, v_{j}>$ 组成的方阵 $\hat{W}$

FM模型的W方阵

从上面三个矩阵，我们可以看到：

（1）方阵 $W$ 的非对角线上三角的元素，即为多项式模型的二阶特征系数： $w_{ij}$

（2）方阵 $\hat{W}$ 的非对角线上三角的元素，即为FM模型的二阶特征系数： $<v_{i}, v_{j}>$

由于 $\hat{W} = V \times V^{T}$ ，即隐向量矩阵的相乘结果，这是一种矩阵分解的方法

引用线性代数中的结论：

当k足够大时，对于任意对称正定的实矩阵 $\hat{W} \in \mathbb{R^{n\times n}}$ ，均存在实矩阵 $V \in \mathbb{R^{n\times k}}$ ，使得 $\hat{W} = V \times V^{T}$

所以FM模型需要保证 $\hat{W}$ 的正定性。由于FM只关心互异特征之间的关系（ $i>j$ ），因此 $\hat{W}$ 的对角线元素可以任意取值，只需将它们取足够大（保证行元素严格对角占优），就可以保证 $\hat{W}$ 的正定性

五、FM模型化简

从上述FM模型方程看，模型的复杂度的确是： $O(n^2k)$

不过，数学是奇妙的，我们可以改写模型的二阶项系数项

改写模型的二阶项系数项

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

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

第2个等号： $<v_{i}, v_{j}>$ 向量内积展开成累加形式

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

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

带入化简后的表达式，FM模型方程为：

FM模型方程

其中参数个数为： $1+n+kn$

模型的复杂度为： $O(kn)$

可以看到通过数学上的化简，FM模型的复杂度降低到了线性级别

六、损失函数

利用FM模型方程，可以进行各种机器学习预测的任务，如回归、分类和排名等

对于回归问题，损失函数可以取最小平方误差函数

最小平方误差函数

对于分类问题，损失函数可以取logit逻辑函数

logit逻辑函数

七、目标函数

通过损失函数构造出目标函数为

目标函数

其中包含具体的损失函数 $loss$ 和估计函数 $\hat{y}(X)$ 。这里 $\hat{y}$ 即FM模型方程，损失函数 $loss$ 可以带入具体的可导函数（如logit函数）即可

八、最优化目标函数

最优化目标函数，即最优化模型方程的参数，即转化为下面最优化问题

优化目标函数

目标函数对模型参数的偏导数通式为：

目标函数对模型参数的偏导数

对于 $R^2$ 和或 $logit$ 作为损失函数而言， $loss$ 对模型估计函数 $\hat{y}(X)$ 的偏导数为：

loss对模型估计函数的偏导数

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

FM模型方程对参数的偏导数

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

九、FM模型的算法步骤

（1）初始化模型参数： $w_{0} \in \mathbb{R}，w \in \mathbb{R}^{n}, V \in \mathbb{R}^{n \times k} \rightarrow N(0，1)$

（2）遍历每个n维样本 $X$

（3）FM方程计算 $\hat{y}(X)$

（4）更新 $w_{0} \leftarrow w_{0} - \alpha \frac{\partial}{\partial w_{0}}l(\hat{y}_{i}(X|\theta^{*}), y_{i})$

（5）遍历 $X$ 样本中的每个特征 $x_{j}$ ， $j \in (1,2,...,n)$

（6）更新 $w_{j} \leftarrow w_{j} - \alpha \frac{\partial}{\partial w_{j}}l(\hat{y}_{i}(X|\theta^{*}), y_{i})$

（7）遍历 $x_{j}$ 的k维隐向量 $v_{f}$ ， $f \in (1,2,...,k)$

（8）更新 $v_{jf} \leftarrow v_{jf} - \alpha \frac{\partial}{\partial v_{jf}}l(\hat{y}_{i}(X|\theta^{*}), y_{i})$

十、案例演示

最后我们用python实现FM算法，数据场景为二分类问题

数据场景

损失函数我们使用 $logit$ 函数

损失函数

FM模型方程

SGD更新FM模型的参数列表

模型分类结果

十一、FM模型的优势

最后我们总结出FM模型的优势：

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

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

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

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

案例代码见：FM模型的算法思想

FM模型的算法思想

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读