1 背景

1.1 LR模型方程

        对于监督学习，机器学习模型的预测是一个估计函数$\hat{y}$（映射$F$）
$$\hat{y}=F:X\text{X}X\to y\text{\hspace{1em}(1)}$$
        其中$X\text{X}X$属于$n$维特征向量，即$X\text{X}X\in {\mathbb{R}}^n$，$y$属于目标值，回归问题中$y\in \mathbb{R}$，二分类问题中 y ∈ { − 1 , + 1 } y\in\{ -1,+1 \} y∈{−1,+1}

        我们首先回顾一般的线性回归方程LR，对于输入任意一个$n$维特征向量$X\text{X}X=(x_1,x_2,\cdots ,x_n)$，建模估计函数$\hat{y}(X\text{X}X)$为
$$\hat{y}(X\text{X}X)=w_0+\sum _{i=1}^n{w}_i{x}_i\text{\hspace{1em}(2)}$$
        LR模型的参数为：$w_0\in \mathbb{R}$，$w\in {\mathbb{R}}^n=(w_1,w_2,\cdots ,w_n)$

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

（1）各个特征分量$x_i和x_j(i\ne j)$彼此之间是独立的

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

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

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

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

（3）高阶特征：即两个以上的特征组合产生的新特征，如$x_1{x}_2{x}_3$

        综上可知，LR模型只考虑了一阶特征的线性组合关系。

1.2 多项式模型方程

        为了克服模型欠缺二阶特征组合因素，我们将LR模型改写为二阶多项式模型
$$\hat{y}(X\text{X}X)=w_0+\sum _{i=1}^n{w}_i{x}_i+\sum _{i=1}^{n-1}\sum _{j=i+1}^n{w}_{ij}{x}_i{x}_j\text{\hspace{1em}(3)}$$
        其中$x_i{x}_j$表示两个互异特征组合的二阶特征，$w_{ij}$表示二阶特征的交叉项系数

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

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

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

        造成学习困难的原因是：

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

（2）样本本身是稀疏的，同时满足$x_i{x}_j\ne 0$的样本非常稀少

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

---

2 FM算法原理

2.1 FM模型方程

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

        为此，针对样本$X\text{X}X$的第i维特征分量$x_i$，引入辅助隐向量${v\text{v}v}_i$
$${v\text{v}v}_i=(v_{i1},v_{i2},\cdots ,v_{ik}{)}^T\in {\mathbb{R}}^k\text{\hspace{1em}(4)}$$

        其中$k$为超参数，表示特征分量$x_i$对应一个$k$维隐向量${v\text{v}v}_i$，则将$w_{ij}$表示为：
$${\hat{w}}_{ij}={v\text{v}v}_i^T{v\text{v}v}_j=<{v\text{v}v}_i,{v\text{v}v}_j>=\sum _{f=1}^k{v}_{if}vjf\text{\hspace{1em}(5)}$$

        上式引入隐向量的含义为：二阶特征系数$w_{ij}$等价于：特征分量$x_i$和$x_j$对应的隐向量${v\text{v}v}_i$和${v\text{v}v}_j$的内积$<{v\text{v}v}_i,{v\text{v}v}_j>$，这就是FM模型的核心思想。

        则我们将二阶多项式模型改写为FM模型：
$$\hat{y}(X\text{X}X)=w_0+\sum _{i=1}^n{w}_i{x}_i+\sum _{i=1}^{n-1}\sum _{j=i+1}^n<{v\text{v}v}_i,{v\text{v}v}_j>x_i{x}_j\text{\hspace{1em}(6)}$$
        从FM模型方程可知，FM模型的参数为：$w_0\in \mathbb{R},w\text{w}w\in {\mathbb{R}}^n,V\text{V}V\in {\mathbb{R}}^{n\times k}$
        各个参数的含义为：

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

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

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

        参数的个数为$1+n+nk$；模型的复杂度为：$O(n^{2}k)$

        对比(3)式和(6)式可知，交叉项$x_i{x}_j$的系数，前者用的是$w_{ij}$，后者用的是${\hat{w}}_{ij}$，为了弄清二者之间的关系，引入几个矩阵。

(1)每个特征$x_i$对应的隐向量${v\text{v}v}_i$组成的矩阵$V\text{V}V$：
$$V\text{V}V=\left[\begin{array}{c}{v\text{v}v}_1^T\\ {v\text{v}v}_2^T\\ ⋮\\ {v\text{v}v}_n^T\end{array}\right]={\left[\begin{array}{cccc}{v}_{11}& v_{12}& \cdots & v_{1k}\\ v_{21}& v_{22}& \cdots & v_{2k}\\ ⋮& ⋮& ⋮& ⋮\\ v_{n1}& v_{n2}& \cdots & v_{nk}\end{array}\right]}_{n\times k}\text{\hspace{1em}(7)}$$
(2)多项式模型的二阶特征系数$w_{ij}$组成的交互方阵$W\text{W}W$
$$W\text{W}W={\left[\begin{array}{cccc}{w}_{11}& w_{12}& \cdots & w_{1n}\\ w_{21}& w_{22}& \cdots & w_{2n}\\ ⋮& ⋮& ⋮& ⋮\\ w_{n1}& w_{n2}& \cdots & w_{nn}\end{array}\right]}_{n\times n}\text{\hspace{1em}(8)}$$
(3) FM模型的二阶特征系数$<{v\text{v}v}_i,{v\text{v}v}_j>$组成的方阵$\widehat{W\text{W}W}$
$$\begin{array}{rl}\widehat{W\text{W}W}& =V\text{V}V\times {V\text{V}V}^T=\left[\begin{array}{c}{v\text{v}v}_1^T\\ {v\text{v}v}_2^T\\ ⋮\\ {v\text{v}v}_n^T\end{array}\right]\times \left[\begin{array}{cccc}{v\text{v}v}_1& {v\text{v}v}_2& \cdots & {v\text{v}v}_n\end{array}\right]\\ & ={\left[\begin{array}{cccc}{v\text{v}v}_1^T{v\text{v}v}_1& {v\text{v}v}_1^T{v\text{v}v}_2& \cdots & {v\text{v}v}_1^T{v\text{v}v}_n\\ {v\text{v}v}_2^T{v\text{v}v}_1& {v\text{v}v}_2^T{v\text{v}v}_2& \cdots & {v\text{v}v}_2^T{v\text{v}v}_n\\ ⋮& ⋮& ⋮& ⋮\\ {v\text{v}v}_n^T{v\text{v}v}_1& {v\text{v}v}_n^T{v\text{v}v}_2& \cdots & {v\text{v}v}_n^T{v\text{v}v}_n\end{array}\right]}_{n\times n}\\ & ={\left[\begin{array}{cccc}{v\text{v}v}_1^T{v\text{v}v}_1& {\widehat{w\text{w}w}}_{12}& \cdots & {\widehat{w\text{w}w}}_{1n}\\ {\widehat{w\text{w}w}}_{21}& {v\text{v}v}_2^T{v\text{v}v}_2& \cdots & {\widehat{w\text{w}w}}_{2n}\\ ⋮& ⋮& ⋮& ⋮\\ {\widehat{w\text{w}w}}_{n1}& {\widehat{w\text{w}w}}_{n2}& \cdots & {v\text{v}v}_n^T{v\text{v}v}_n\end{array}\right]}_{n\times n}\end{array}\text{\hspace{1em}(9)}$$
        从上面三个矩阵，我们可以看到：
（1）方阵$W\text{W}W$的非对角线上三角的元素，即为多项式模型的二阶特征系数：$w_{ij}$
（2）方阵$\widehat{W\text{W}W}$的非对角线上三角的元素，即为FM模型的二阶特征系数：$<v_i,v_j>$
由于$\widehat{W\text{W}W}=V\text{V}V{V\text{V}V}^T$，即隐向量矩阵的相乘结果，这是一种矩阵分解的方法

        引用线性代数中的结论：当$k$足够大时，对于任意对称正定的实矩阵$\widehat{W\text{W}W}\in {\mathbb{R}}^{n\times n}$，均存在实矩阵$V\text{V}V\in {\mathbb{R}}^{n\times k}$，使得$\widehat{W\text{W}W}=V\text{V}V\times {V\text{V}V}^T$

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

2.2 模型化简

        从上述FM模型方程看，模型的复杂度的确是：$O(n^{2}k)$，但我们通过一些技巧可以化简模型的二阶系数项，如下：
$$\begin{array}{rl}& \sum _{i=1}^n\sum _{j=i+1}^n<v_i,v_j>x_i{x}_j\\ & =\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n<v_i,v_j>x_i{x}_j-\frac{1}{2}\sum _{i=1}^n<v_i,v_i>x_i{x}_i\\ & =\frac{1}{2}(\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)\\ & =\frac{1}{2}\sum _{f=1}^k((\sum _{i=1}^n{v}_{i,f}{x}_i)(\sum _{j=1}^n{v}_{j,f}{x}_j)-\sum _{i=1}^n{v}_{i,f}^2{x}_i^2)\\ & =\frac{1}{2}\sum _{f=1}^k((\sum _{i=1}^n{v}_{i,f}{x}_i{)}^2-\sum _{i=1}^n{v}_{i,f}^2{x}_i^2)\end{array}\text{\hspace{1em}(10)}$$
        对上述化简过程做一些解释：

• 第1个等号：对称方阵$\widehat{W\text{W}W}$的所有元素之和减去主对角线元素之和
• 第2个等号：$<v_i,v_j>$向量内积展开成累加形式
• 第3个等号：提出公共部分${\sum }_{f=1}^k$
• 第4个等号：表示为“和平方”减去“平方和”

        将式子(10)的化简结果代入式子(6)，可以得到：
$$\begin{array}{r}\hat{y}(X\text{X}X)=w_0+\sum _{i=1}^n{w}_i{x}_i+\frac{1}{2}\ast \sum _{f=1}^k\left\{{\left(\sum _{i=1}^n{v}_{if}{x}_i\right)}^2-\sum _{i=1}^n{v}_{if}^2{x}_i^2\right\}\end{array}\text{\hspace{1em}(11)}$$

        可以看到通过数学上的化简，参数个数为：$1+n+kn$，模型的复杂度为：$O(kn)$，FM模型的复杂度降低到了线性级别

---

3 模型建立

3.1 损失函数

        利用FM模型方程，可以进行各种机器学习预测的任务，包括：

• Regression：$\hat{y}(x)$可以直接用作预测，并且最小平方误差来优化。
• Binary classification：$\hat{y}(x)$作为目标函数并且使用hinge loss或者logit loss来优化。
• Ranking：向量$x\text{x}x$通过$\hat{y}(x)$的分数排序，并且通过pairwise的分类损失来优化成对的样本$(x^{(a)},x^{(b)})$
  对以上的任务中，正则化项参数一般加入目标函数中以防止过拟合。

        对于回归问题，损失函数可以取最小平方误差函数
$$loss(\hat{y},y)=\frac{1}{2}(\hat{y}-y{)}^2\text{\hspace{1em}(12)}$$
        对于分类问题，损失函数可以取logit逻辑函数
$$loss(\hat{y},y)=log(1+e^{-\hat{y}y})\text{\hspace{1em}(13)}$$

3.2 目标函数

        通过损失函数构造出目标函数为
$$obj=\sum _{i=1}^{N}loss({\hat{y}}_i,y_i)\text{\hspace{1em}(14)}$$
        其中包含具体的损失函数loss和估计函数$\hat{y}(X)$。这里$\hat{y}$即FM模型方程，损失函数loss可以带入具体的可导函数（如logit函数）即可。

        最优化目标函数，即最优化模型方程的参数，即转化为下面最优化问题
$${\theta }^{\ast }=argmin\sum _{i=1}^{N}loss({\hat{y}}_i,y_i)\text{\hspace{1em}(15)}$$
        目标函数对模型参数的偏导数通式为：
$$\frac{\partial }{\partial \theta }loss({\hat{y}}_i,y_i)=\frac{\partial loss({\hat{y}}_i,y_i)}{\partial {\hat{y}}_i}\frac{\partial {\hat{y}}_i}{\partial \theta }\text{\hspace{1em}(16)}$$
        对于$R^2$和或logit作为损失函数而言，loss对模型估计函数$\hat{y}(X)$的偏导数为：
$$\frac{\partial loss({\hat{y}}_i,y_i)}{\partial {\hat{y}}_i}=\{\begin{array}{ll}{\hat{y}}_i-y_i& loss=\frac{1}{2}({\hat{y}}_i-y_i{)}^2\\ \frac{-y_i}{1+e^{{\hat{y}}_i{y}_i}}& loss=log(1+e^{-{\hat{y}}_i{y}_i})\end{array}\text{\hspace{1em}(17)}$$

        对于FM模型而言，优化的参数为： θ ∗ = { w 0 , w , V } \theta^{*} = \{w_{0}, \pmb{w}, \pmb{V}\} θ∗={w0​,www,VVV}，则FM模型方程对各个参数${\theta }^{\ast }$的偏导数为：
$$\frac{\partial {\hat{y}}_i}{\partial \theta }=\{\begin{array}{ll}1,& \text{if }\theta \text{ is }{w}_0;\\ x_i,& \text{if }\theta \text{ is }{w}_i;\\ x_i{\sum }_{j=1}^n(v_{jf}{x}_j)-x_i^2{v}_{if},& \text{if }\theta \text{ is }{v}_{if}.\end{array}\text{\hspace{1em}(18)}$$
        FM进行推断的时间复杂度为$O(kn)$。分析训练的复杂度，依据参数的梯度表达式， ${\sum }_{j=1}^n(v_{jf}{x}_j)$与 ​$i$无关，在参数更新时可以首先将所有的${\sum }_{j=1}^n(v_{jf}{x}_j)$计算出来，复杂度为$O(kn)$，后续更新所有参数的时间复杂度均为$O(1)$，参数量为$1+n+kn$，所以最终训练的时间复杂度同样为$O(kn)$，其中$n$为特征数，$k$为隐向量维数。

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

---

4 模型求解

4.1 优化算法

        这部分内容借鉴自作者: peghoty的学习算法：https://blog.csdn.net/itplus/article/details/40536025

---

5 总结

        FM模型的主要优势为：

• FM模型对特征的一阶组合和二阶组合都进行了建模，在高度稀疏的情况下特征之间的交叉仍然能够估计，而且可以泛化到未被观察的交叉；
• FM模型通过MF思想，基于K维的Latent Factor Vector，处理因为数据稀疏带来的学习不足问题；
• FM模型的训练和预测的时间复杂度是线性的；
• FM模型可以用于DNN的embedding。

        详细的Python代码实现，可以参考：FM(Factorization Machine)算法（推导与实现）：https://blog.csdn.net/qq_24819773/article/details/86308868

---

补充：

        对称矩阵上三角求和，设矩阵为$M\text{M}M$：
$$M={\left(\begin{array}{cccc}{m}_{11}& m_{12}& \cdots & m_{1n}\\ m_{21}& m_{22}& \cdots & m_{1n}\\ ⋮& ⋮& \ddots & ⋮\\ m_{n1}& m_{n2}& \cdots & m_{nn}\end{array}\right)}_{n\ast n}\text{\hspace{1em}(19)}$$
        其中，$m_{ij}=m_{ji}$
        令上三角元素和为$A\text{A}A$，即${\sum }_{i=1}^{n-1}{\sum }_{j=i+1}^n{m}_{ij}=A$，那么，$M\text{M}M$的所有元素之和等于$2\ast A\text{A}A+tr(M\text{M}M)$，$tr(M\text{M}M)$为矩阵的迹。
$$\sum _{i=1}^n\sum _{j=1}^n{m}_{ij}=2\ast \sum _{i=1}^{n-1}\sum _{j=i+1}^n{m}_{ij}+\sum _{i=1}^n{m}_{ii}\text{\hspace{1em}(20)}$$
        于是，可以得到：
$$A=\sum _{i=1}^{n-1}\sum _{j=i+1}^n{m}_{ij}=\frac{1}{2}\ast \left\{\sum _{i=1}^n\sum _{j=1}^n{m}_{ij}-\sum _{i=1}^n{m}_{ii}\right\}\text{\hspace{1em}(21)}$$

        当参数为$v_{if}$时，只需要关注模型高阶项，当计算参数$v_{if}$的梯度时，其余无关参数可看做常数。
∂ y ^ i ∂ v i f = ∂ 1 2 { ( ∑ i = 1 n v i f x i ) 2 − ∑ i = 1 n v i f 2 x i 2 } / ∂ v i f = 1 2 ∗ { ∂ { ∑ i = 1 n v i f x i } 2 ∂ v i f − ∂ { ∑ i = 1 n v i f 2 x i 2 } ∂ v i f } (22) \begin{aligned} \frac{\partial{\hat{y}_i}}{\partial{v_{if}}} ={} & \partial{\frac{1}{2}\left\{\left(\sum_{i=1}^{n}v_{if}x_i\right)^{2}-\sum_{i=1}^{n}v_{if}^{2}x_{i}^2\right\}}/\partial{v_{if}} \\ ={} & \frac{1}{2}* \left\{ \frac{ \partial{ \left\{ \sum_{i=1}^{n}v_{if}x_i \right\}^2 } }{\partial{v_{if}}} - \frac{ \partial{ \left\{ \sum_{i=1}^{n}v_{if}^{2}x_{i}^2 \right\} } }{\partial{v_{if}}} \right\} \\ \end{aligned} \tag{22} ∂vif​∂y^​i​​==​∂21​⎩⎨⎧​(i=1∑n​vif​xi​)2−i=1∑n​vif2​xi2​⎭⎬⎫​/∂vif​21​∗⎩⎨⎧​∂vif​∂{∑i=1n​vif​xi​}2​−∂vif​∂{∑i=1n​vif2​xi2​}​⎭⎬⎫​​(22)
        其中，
$$\frac{\partial \left\{{\sum }_{i=1}^n{v}_{if}^2{x}_i^2\right\}}{\partial v_{if}}=2x_i^2{v}_{if}\text{\hspace{1em}(23)}$$
        令$\lambda ={\sum }_{i=1}^n{v}_{if}{x}_i$，则：
∂ { ∑ i = 1 n v i f x i } 2 ∂ v i f = ∂ λ 2 ∂ v i f = ∂ λ 2 ∂ λ ∂ λ ∂ v i f = 2 λ ∗ ∂ ∑ i = 1 n v i f x i ∂ v i f = 2 λ ∗ x i = 2 ∗ x i ∗ ∑ j = 1 n ( v j f x j ) (24) \begin{aligned} \frac{ \partial{ \left\{ \sum_{i=1}^{n}v_{if}x_i \right\}^2 } }{\partial{v_{if}}} ={} & \frac{\partial{\lambda^2}}{\partial{v_{if}}} \\ ={} & \frac{\partial{\lambda^2}}{\partial{\lambda}} \frac{\partial{\lambda}}{\partial{v_{if}}} \\ ={} & 2\lambda*\frac{\partial{\sum_{i=1}^{n}v_{if}x_i}}{\partial{v_{if}}} \\ ={} & 2\lambda*x_i \\ ={} & 2*x_i*\sum_{j=1}^{n}(v_{jf}x_j) \\ \end{aligned} \tag{24} ∂vif​∂{∑i=1n​vif​xi​}2​=====​∂vif​∂λ2​∂λ∂λ2​∂vif​∂λ​2λ∗∂vif​∂∑i=1n​vif​xi​​2λ∗xi​2∗xi​∗j=1∑n​(vjf​xj​)​(24)
        结合公式（22~24），可得：
$$\frac{\partial {\hat{y}}_i}{\partial v_{if}}=x_i\sum _{j=1}^n(v_{jf}{x}_j)-x_i^2{v}_{if}\text{\hspace{1em}(25)}$$

---

参考

• Factorization Machines：https://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf
• FM模型的算法思想：https://www.jianshu.com/p/8d792422e582
• Factorization Machines 学习笔记：https://blog.csdn.net/itplus/article/details/40534885?spm=1001.2014.3001.5501
• 因子分解机（Factorization Machine）详解：https://blog.csdn.net/lijingru1/article/details/88623136
• FM理论与实践：https://zhuanlan.zhihu.com/p/89639306