概述
在使用线性模型如 LR 模型时，特征工程通常占据了大部分的工作量，有时为了产生较好的效果甚至需要人工进行一些特征的二维或者三维交叉。FM（Factorization machines）提供了一种方法，可以在自动进行特征交叉的同时，也能够处理非常稀疏数据，并且具有线性的时间复杂度。
由于 FM 实现简单且效果好，因此应用范围非常广，常见于各种比赛和公司的生产场景。
FM优势
FM能够解决的问题及优点包括[1]：
- FM能够解决分类和回归问题
- FM能够代替SVD、SVD++等进行矩阵分解
- FM可以处理非常稀疏数据，此时SVM等模型会失效
- FM线性时间复杂度，计算简单
- FM可表示性较强，将模型参数表示为K维向量。向量之间可以交叉运算，即使两个交叉特征没有对应训练数据，也能表示出权重。
二维-FM
先回顾一下线性回归模型，其建模为：
$$ \hat {y}({\rm{x}}) = {\omega_0} + {\omega_1}{x_1} + {\omega_2}{x_2} + \cdots + {\omega_n}{x_n} = {\omega_0} + \sum\limits_{i = 1}^n {{{\omega_i}} {x_i}} \tag{1} $$
从上式可以看出各特征分量$x_i$和$x_j\ (i \ne j )$之间是相互孤立的，因此仅考虑了单个的特征分量而没有考虑特征分量之间的相互关系。
在$(1)$的基础上改写为：
$$ \hat{y({\rm{x}})} = {\omega_0} + \sum\limits_{i = 1}^n {{\omega_i}} {x_i} + \sum\limits_{i = 1}^{n - 1} {\sum\limits_{j = i + 1}^n {{\omega_{ij}}} } {x_i}{x_j} \tag{2} $$
这样也就将任意两个不同的特征向量之间的关系同时考虑进来了。
但是，有一个问题是在稀疏数据中这种直接在${x_i} {x_j}$前面配上一个系数$\omega_{ij}$的方式会有很大的缺陷：对于观察样本中未出现过交互的特征分量，不能对相应的参数进行估计[2]。一定要注意的是，在高度稀疏数据场景中，由于数据量的不足，样本中出现未交互的特征分量是很普遍的。
为了克服这个缺陷，考虑在(2)中的系数$\omega_{ij}$上进行适当的处理以将其换成另外一种形式。针对每个维度的特征分量$x_i$，引入辅助向量：
$$ \rm{v}{i}=( v{i 1}, v_{i 2}, \cdots, v_{i k} )^{T} \in R^{k}, \quad i=1,2, \cdots, n \tag{3} $$
其中$k$为超参数，将(2)中的$\omega_{ij}$改写为：
$$ {\hat \omega_{ij}} = {{\rm{v}}_i}^T{{\rm{v}}_j}: = \sum\limits_{l = 1}^k {{v_{il}}{x_{jl}}} \tag{4} $$
如此，可获得FM的二维模型。
模型
对于2次特征交叉的FM模型可以表示为[2]：
$$ y(x) = {w_0} + \sum\limits_{i = 1}^n {({w_i}{x_i})} + \sum\limits_{i = 1}^{n - 1} {\sum\limits_{j = i + 1}^n {( < {v_i},{v_j} > {x_i}{x_j})} } \tag{5} $$
其中模型参数有$w_0$为截距，$w_i$为一维特征权重，$v_i$为每一维度特征的分布式表示，也即$w_0$为整体偏置量，$W$对特征向量的每个分量的强度进行建模，$V$对特征向量中任意两个分量之间的关系进行建模。
其中特征交叉权重计算为:
$$ < {v_i},{v_j} > = \sum\limits_{f = 1}^k {{v_{i,f}}} {v_{j,f}} \tag{5.1} $$
二维-FM计算复杂度
如果对式子(1)直接进行计算，那么其复杂度是$O(kn^2)$，但是可以通过简单的数学变换将其转化为$O(kn)$。由于前面两项的计算复杂度都是$O(kn)$，所以只需要对第三项进行处理[3]：
$$
\begin{aligned}
&\sum\limits_{i = 1}^n {\sum\limits_{j = i + 1}^n {\left( { < {v_i},{v_j} > {x_i}{x_j}} \right)} } \
&= \frac{1}{2}\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {\left( { < {v_i},{v_j} > {x_i}{x_j}} \right)} } - \frac{1}{2}\sum\limits_{i = 1}^n < {v_i},{v_i} > {x_i}{x_i} \
&= \frac{1}{2}\left( {\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {\sum\limits_{f = 1}^k {\left( {{v_{i,f}}{v_{{j,f}}}{x_i}{x_j}} \right)} } } - \sum\limits_{i = 1}^n {\sum\limits_{f = 1}^k {\left( {{v_{i,f}}{v_{i,f}}{x_i}{x_i}} \right)} } } \right) \
&= \frac{1}{2}\sum\limits_{f = 1}^k {\left( {\left( {\sum\limits_{i = 1}^n {{v_{i,f}}} {x_i}} \right)\left( {\sum\limits_{j = 1}^n {{v_{j,f}}} {x_j}} \right) - \sum\limits_{i = 1}^n {v_{i,f}^2} x_i^2} \right)} \
&= \frac{1}{2}\sum\limits_{f = 1}^k {\left( {{{\left( {\sum\limits_{i = 1}^n {{v_{i,f}}} {x_i}} \right)}^2} - \sum\limits_{i = 1}^n {v_{i,f}^2} x_i^2} \right)}
\end{aligned}
\tag{6}
$$
相当于特征分布式表示中每一维度和特征进行求和平方和平方求和相减。
二维-FM的梯度计算
采用SGD进行模型计算 :
$$
\frac{\partial }{{\partial \theta }}y(x) =
\begin{cases}
{1}
&{{\text{if }}\theta {\text{ is }}{\omega_0}} \
{{x_i}}
&{{\text{if }} \theta {\text{ is }} {\omega_i}} \
{{x_i}\sum\limits_{j = 1}^n {{v_{j,f}}} {x_j} - {v_{i,f}}x_i^2}
&{{\text{if }} \theta {\text{ is }}{\nu_{i,f}}}
\end{cases}
\tag{7}
$$
基于随机梯度的方式求解[4]：
FM应用
在很多应用中，FM可以取代常用模型并且能够取得不错效果，例如
- FM - SVM，能够处理稀疏特征
- FM - MF
- FM - SVD++
- FM - PITF
- FM - FPMC
具体可以参考相关引用的论文。