写在前面

背景

FM算法，全称Factorization Machines,一般翻译为“因子分解机”。2010年，它由当时还在日本大阪大学的Steffen Rendle提出。FM模型以其优雅的数学表达和极强的工业拓展能力，使其在当今的推荐系统、计算广告领域占据十分核心的位置。

此模型的主要作用是解决了线性模型中高阶交叉特征的选择和特征参数的训练问题，工程师可以解放精力寻求新的基本特征或进行模型调优，极大的减少人工参与特征组合和特征选择的工作。相比于传统线性模型，FM模型具有以下优点：

• FM模型极大地压缩参数规模
• 模型训练线性时间复杂度，可以应用于大规模机器学习
• 克服One-Hot编码带来的数据稀疏性问题
• 通过特征对应的隐向量内积表示组合特征系数，对训练集中未出现过的特征组合依旧具有参数学习能力

相关结论：

• FM的特征学习能力至少不弱于人工组合特征+线性模型的结果
• FM在CTR预估、CVR预估等领域的效果经过了工业界的验证
• 在稀疏数据集上FM的效果要好于SVM

符号定义

模型形式

对于特征集合$x=\left(1, x_{1}, x_{2}, \cdots, x_{n}\right)$和标签$y$。我们希望得到$x$与$y$的关系，最简单是建立线性回归模型

$\hat{y}(x)=w_{0}+\sum_{i=1}^{n} w_{i} x_{i}$

但是，对于实际问题，仅仅依靠一阶特征的线性模型拟合效果较差，需要构造高阶的组合特征，在机器学习领域使基本特征构造复杂特征的方法被称为“特征工程”，本文不展开说明。

特征工程的目的之一是根据基本特征生成高阶的组合特征，这里以二阶为例(理论上，FM可以组合任意高阶，但是由于计算复杂度，实际中常用二阶，后面也主要介绍二阶组合的内容)

模型形式为：

$\hat{y}(x)=w_{0}+\sum_{i=1}^{n} w_{i} x_{i}+\sum_{i=1}^{n} \sum_{j=i+1}^{n} w_{i j} x_{i} x_{j}$

相比于模型(1)而言，模型(2)根据基本特征生成了$n(n−1)/2$个二阶的组合特征，同时也增加了$n(n−1)/2$个参数

在这里，任意两个组合特征参数$w_{i j}$都是独立的。然而，在数据非常稀疏的实际应用场景中，准确的从样本中学习$w_{i j}$是十分困难的。

原因是因为，数据稀疏场景中回归模型的参数的学习结果就是从训练样本中计算充分统计量（凡是符合指数族分布的模型都具有此性质），而在这里组合特征的每一个参数$w_{i j}$的学习过程需要大量的$x_{i}, x_{j}$同时非零的训练样本。当某些组合特征在训练样本中不存在时，$w_{i j}$的参数训练结果为0。这样会导致模型存在参数不稳定和泛化能力不足的问题，且$$O(n^2)$$的参数规模也增加了存储和训练的难度。

那么解决问题这个问题我们可以从两个角度考虑，做模型压缩(降低参数规模)和寻找一种方法可以很好的学习到特征参数

很自然的想到(我是想不到)采用矩阵分解技术(MF),于是引出了一个问题:MF和FM的关系是什么？

FM的核心就是通过近似矩阵分解有效的解决了这一问题，FM组合特征参数可以用参数矩阵$W$表示

$W = \begin{bmatrix} w_{11} & w_{12} & \cdots & w_{1n} \\ w_{21}& w_{22}\\ \vdots & \vdots & \ddots \\ w_{n1} & w_{n2} & \cdots & w_{nn} \end{bmatrix}$

可以看出$W$是实对称矩阵，为了方便表述，可以更进一步假定参数矩阵$W$的对角元素均为正实数，那么$W$为正定矩阵。根据正定矩阵的性质，$W$可以进行对角化分解，而且形式非常优雅

$W=Q \Lambda Q^{T}$

其中$Q$是正交单位矩阵，即$Q Q^{T}=I$ ,$\Lambda$是对角矩阵，且对角线元素全部大于0。可以将其对角线元素从大到小排列，即$\lambda_{1} \geq \lambda_{2} \geq \cdots \lambda_{n}>0$，只要$Q$的进行初等行变换即可。基于这些特性，可以分解$\Lambda=\sqrt{\Lambda} \sqrt{\Lambda^{T}}$,同时令$V=Q \sqrt{\Lambda}​$所以有

$W=V V^{T}$

这时的$V$是$n \times n$矩阵，可以用主成分近似的思想，取$\sqrt{\Lambda}$前$\mathrm{f}(\ll n)$个主对角元素

$W \approx V_{f} V_{f}^{T}$

近似的矩阵$V_f$为$n \times f$矩阵。

$V_{f}=\left[ \begin{array}{cccc}{v_{1,1}} & {v_{1,2}} & {\cdots} & {v_{1, f}} \\ {v_{2,1}} & {v_{2,2}} & {\cdots} & {v_{2, f}} \\ {\vdots} & {\vdots} & {\vdots} & {\vdots} \\ {v_{n, 1}} & {v_{n, 2}} & {\cdots} & {v_{n, f}}\end{array}\right]=\left[ \begin{array}{llll}{v_{1}} & {v_{2}} & {\cdots} & {v_{n} ]}\end{array}\right.^{T}$

为了便于理解我们展开转换细节：

$V_{f}V_{f}^{T}=\left[ \begin{array}{c}{V_{1}} \\ {V_{2}} \\ {\cdots} \\ {V_{n}}\end{array}\right] \times\left[V_{1}, V_{2}, \ldots, V_{n}\right] \\= \left[ \begin{array}{cccc}{v_{11}} & {v_{12}} & {\dots} & {v_{1 k}} \\ {v_{21}} & {v_{22}} & {\dots} & {v_{2 k}} \\ {\cdots} & {\cdots} & {\cdots} & {\cdots} \\ {v_{n 1}} & {v_{n 2}} & {\dots} & {v_{n k}}\end{array}\right] \times \left[ \begin{array}{cccc}{v_{11}} & {v_{21}} & {\dots} & {v_{n 1}} \\ {v_{12}} & {v_{22}} & {\dots} & {v_{n 2}} \\ {\cdots} & {\cdots} & {\cdots} & {\cdots} \\ {v_{1 k}} & {v_{2 k}} & {\dots} & {v_{n k}}\end{array}\right]$

将(6)带入(2)我们得到FM的公式：

$\hat{y}(\mathbf{x}) =w_{0}+\sum_{i=1}^{n} w_{i} x_{i}+\sum_{i=1}^{n} \sum_{j=i+1}^{n}\left\langle\mathbf{v}_{i}, \mathbf{v}_{j}\right\rangle x_{i} x_{j}$

其中$\mathbf{V}_{i}$表示特征$x_i$的$k$维隐向量，$\langle\cdot, \cdot\rangle$代表向量内积。

$\left\langle\mathbf{v}_{i}, \mathbf{v}_{j}\right\rangle :=\sum_{f=1}^{k} v_{i, f} \cdot v_{j, f}$

到此为止我们从线性模型推导出了FM模型的表达式(9)(10)

从表达式我们看到FM确实解决了之前提到的一些问题：

• 组合特征的参数规模从$\frac{n(n-1)}{2}$降低到$n f​$，在高阶组合特征情况下更明显
• 参数因子化使得$x_{h} x_{i}$和$x_{i} x_{j}$不在独立。所有包含“$ x_{i}$ 的非零组合特征”（存在某个$j \neq i$，使得 $x_{i} x_{j} \neq 0$）的样本都可以用来学习隐向量$v_i$,在出现新的特征组合时依旧可以通过向量内积表示的参数进行预测，从而缓解了数据稀疏性带来的参数稳定性问题和泛化能力不足问题

FM的参数学习

接下来需要学习模型的参数，首先需要根据实际问题设定对应的损失函数和求解方法。

求解算法最常用的是使用SGD求解参数，也可以使用L-BFGS，MCMC或ALS。使用随机梯度下降或L-BFGS均需要计算出损失函数的梯度。

最优化一般需要加上正规化项，避免参数过拟合，FM添加L2正规化，回归问题和二元分类问题的损失函数如下

回归目标函数：

$\begin{aligned} E_{r}(w, v)=\frac{1}{2 m} \sum_{h=1}^{m}\left(w_{0}+\sum_{i=1}^{n} w_{i} x_{i}^{(h)}+\sum_{i=1}^{n} \sum_{j=i+1}^{n} v_{i} v_{j}^{T} x_{i}^{(h)} x_{j}^{(h)}-y^{(h)}\right)^{2} \\+\frac{\lambda_{0}}{m} w_{0}^{2}+\frac{\lambda_{1}}{m} \sum_{i=1}^{n} w_{i}^{2}+\frac{\lambda_{2}}{m} \sum_{i=1}^{n} v_{i}^{T} v_{i} \end{aligned}$

二分类目标函数：

$\begin{aligned} E_{c}(w, v)=\frac{1}{m} & \sum_{h=1}^{m} \ln \left(1+e^{-y^{(h)}\left(w_{0}+\sum_{i=1}^{n} w_{i} x_{i}+\sum_{i=1}^{n} \sum_{j=i+1}^{n} v_{i}^{T} v_{j} x_{i} x_{j}\right)}\right) \\ &+\frac{\lambda_{0}}{m} w_{0}^{2}+\frac{\lambda_{1}}{m} \sum_{i=1}^{n} w_{i}^{2}+\frac{\lambda_{2}}{m} \sum_{i=1}^{n} v_{i}^{T} v_{i} \end{aligned}$

分类问题标签：$y^{h} \in-1,1$

模型优化(加速求解)

FM模型的复杂度为$O\left(k n^{2}\right)$，但是通过下面的等价转换，可以将FM的二次项化简，其复杂度可优化到$O\left(k n\right)$

$\sum_{i=1}^{n} \sum_{j=i+1}^{n}\left\langle\mathbf{v}_{i}, \mathbf{v}_{j}\right\rangle x_{i} x_{j}=\frac{1}{2} \sum_{f=1}^{k}\left(\left(\sum_{i=1}^{n} v_{i f} x_{i}\right)^{2}-\sum_{i=1}^{n} v_{i, f}^{2} x_{i}^{2}\right)$

详细的推导过程如下：

$\begin{aligned} & \sum_{i=1}^{n} \sum_{j=i+1}^{n}\left\langle\mathbf{v}_{i}, \mathbf{v}_{j}\right\rangle x_{i} x_{j} \\=& \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n}\left\langle\mathbf{v}_{i}, \mathbf{v}_{j}\right\rangle x_{i} x_{j}-\frac{1}{2} \sum_{i=1}^{n}\left\langle\mathbf{v}_{i}, \mathbf{v}_{i}\right\rangle x_{i} x_{i} \\=& \frac{1}{2}\left(\sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{f=1}^{k} v_{i, f} v_{j, f} x_{i} x_{j}-\sum_{i=1}^{n} \sum_{f=1}^{k} v_{i, f} v_{i f} x_{i} x_{i}\right) \\=& \frac{1}{2} \sum_{f=1}^{k}\left[\left(\sum_{i=1}^{n} v_{i, f} x_{i}\right) \cdot\left(\sum_{j=1}^{n} v_{j, f} x_{j}\right)-\sum_{i=1}^{n} v_{i, f}^{2} x_{i}^{2}\right]\\=& \frac{1}{2} \sum_{f=1}^{k}\left[\left(\sum_{i=1}^{n} v_{i, f} x_{i}\right)^{2}-\sum_{i=1}^{n} v_{i f}^{2} x_{i}^{2}\right] \end{aligned}\\$

解释：

$v_{i, f}$ 是一个具体的值；

第1个等号：对称矩阵 $W$对角线上半部分；

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

第3个等号：提出公共部分；

第4个等号：$i 和 $j 相当于是一样的，表示成平方过程。

采用随机梯度下降法SGD求解参数

$\frac{\partial \hat{y}(x)}{\partial \theta}=\left\{\begin{array}{ll}{1,} & {\text { if } \theta \text { is } \omega_{0}} \\ {x_{i},} & {\text { if } \theta \text { is } \omega_{i}} \\ {x_{i} \sum_{j=1}^{n} v_{j, f} x_{j}-v_{i, f} x_{i}^{2}} & {i f \theta i s v_{i, f}}\end{array}\right.$

训练的伪代码：

待补充

偏导数(12)中，除了$\sum_{j=1}^{n} v_{j, k} x_{j}$，其他是常量复杂度$O(1)$，但是$\sum_{j=1}^{n} v_{j, k} x_{j}$可以复用，复杂度为$O(n)$，需要计算$f$个，总共复杂度为$O(nf)$。因为需要计算$nf$个偏导，所以最后整体的二项组合部分的复杂度仍为$O(nf)$。

参考资料

• Factorization Machines,Steffen Rendle,2010
• libFM,由FM作者Steffen Rendle开发，C++实现单机版
• spark-libFM，基于spark mllib框架实现的FM算法
• 美团FFM应用
• 新浪FM/FFM应用
• 因子分解机FM-高效的组合高阶特征模型
• 深入浅出ML之Factorization家族
• FM算法解析
• 推荐系统召回四模型之：全能的FM模型