1. 背景
FM模型是最近几年提出的模型，凭借其在数据量比较大并且特征稀疏的情况下，忍让能够得到优秀的性能和效果，屡次在各大公司举办的CTR预估比赛中获得不错的战绩。
在计算广告领域，点击率CTR（click-through rate）和转化率CVR（conversion rate）是衡量广告流量的两个关键指标。准确的估计CTR、CVR对于提高流量的价值，增加广告收入有重要的指导作用。预估CTR、CVR，业界常用的方法由人工特征工程+LR（Logistic Regression）、GBDT（Gradient Boosting Decision Tree）+LR、FM（Factorization Machine）和FFM（Field-aware Factorization Machine）模型。在这些模型中，FM和FFM近年来表现突出，分别在Criteo和Avazu举办的CTR预测竞赛中夺得冠军。
2. FM模型原理推导
因子分解机（Factorization Machine，简称FM），又称分解机。是由德国康斯坦茨大学的Steffen Rendle（现任职于Google）于2010年最早提出的，旨在解决大规模稀疏数据下的特征组合问题。在系统介绍FM之前，先了解一下在实际场景中，稀疏数据是怎样产生的。
假设一个广告分类的问题，根据用户和广告位相关的特征，预测用户是否点击了广告。元数据如下：
| Clicked? | Country | Day | Ad_type |
|---|---|---|---|
| 1 | USA | 26/11/15 | Movie |
| 0 | China | 1/7/14 | Game |
| 1 | China | 19/2/15 | Game |
“Clicked？”是label，Country、Day、Ad_type是特征。由于三种特征都是categorical类型的，需要经过独热编码（One-Hot Encoding）转换成数值型特征。
| Clicked? | Country=USA | Country=China | Day=26/11/15 | Day=1/7/14 | Day=19/2/15 | Ad_type=Movie | Ad_type=Game |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
由上表可以看出，经过One-Hot编码之后，大部分样本数据特征是比较稀疏的。上面的样例中，每个样本有7维特征，但平均仅有3维特征具有非零值。实际上，这种情况并不是此例独有的，在真实应用场景中这种情况普遍存在。例如，CTR/CVR预测时，用户的性别、职业、教育水平、品类偏好、商品的品类等，经过One-Hot编码转换后都会导致样本数据的稀疏性。特别是商品品类这种类型的特征，如商品的末级品类约有550个，采用One-Hot编码生成550个数值特征，但每个样本的这550个特征，有且仅有一个是有效的（非零）。由此可见，数据稀疏性是实际问题中不可避免的挑战。
One-Hot编码的另一个特点就是导致特征空间大。例如，商品品类有550维特征，一个categorical特征转换为550维数值特征，特征空间剧增。
同时通过观察大量的样本数据可以发现，某些特征经过关联之后，与label之间的相关性就会提高。如：“USA”与“Thanksgiving”、“China”与“Chinese New Year”这样的关联特征，对用户的点击有着正向的影响。换句话说，来自“China”的用户很可能会在“Chinese New Year”有大量的浏览、购买行为，而在“Thanksgiving”却不会有特别的消费行为。这种关联特征与label的正向相关性在实际问题中是普遍存在的，如“化妆品”类商品与“女”性，“球类运动配件”的商品与“男”性，“电影票”的商品与“电影”品类偏好等。因此，引入两个特征的组合是非常有意义的。
表示特征之间的关联，最直接的方法的是构造组合特征。样本中特征之间的关联信息在one-hot编码和浅层学习模型（如LR、SVM）是做不到的。目前工业界主要有两种手段得到组合特征：
- 1）人工特征工程（数据分析＋人工构造）；
- 2）通过模型做组合特征的学习（深度学习方法、FM/FFM方法）
本章主要讨论FM用来学习特征之间的关联。多项式模型是包含特征组合的最直观的模型。在多项式模型中，特征 $xi$和 $xj$ 的组合采用$ xi$ 表示，即 $xi$和 $xj$都非零时，组合特征$ xixj$才有意义。从对比的角度，本文只讨论二阶多项式模型。模型的表达式如下：
$y(x)=w_0+∑_{i=1}^nw_ix_i+∑_{i=1}^n∑_{j=i+1}^nw_{ij}x_ix_j$
其中，$n$代表样本的特征数量，$xi$是第ii个特征的值，$w_0、w_i、w_{ij}$是模型的参数。
从这个公式可以看出，组合特征的参数一共有$n(n−1)/2$个，任意两个参数都是独立的。然而，在数据稀疏性普遍存在的实际应用场景中，二次项参数的训练是很困难的。其原因是，回归模型的参数$w$的学习结果就是从训练样本中计算充分统计量（凡是符合指数族分布的模型都具有此性质），而在这里交叉项的每一个参数wijwij的学习过程需要大量的$xi$、$xj$同时非零的训练样本数据。由于样本数据本来就很稀疏，能够满足“$xi$和$xj$都非零”的样本数就会更少。训练样本不充分，学到的参数wijwij就不是充分统计量结果，导致参数$w_{ij}$不准确，而这会严重影响模型预测的效果（performance）和稳定性。
那么，如何解决二次项参数的训练问题呢？矩阵分解提供了一种解决思路。在Model-based的协同过滤中，一个rating矩阵可以分解为user矩阵和item矩阵，每个user和item都可以采用一个隐向量表示。比如在下图中的例子，我们把每个user表示成一个二维向量，同时把每个item表示成一个二维向量，两个向量点积就是矩阵中user对item的打分。
类似地，所有二次项参数 $w_{ij}$可以组成一个对称阵 $W$（为了方便说明FM的由来，对角元素可以设置为正实数），那么这个矩阵就可以分解为 $W=V^TV$，$V$ 的第$j$列便是第 $j$ 维特征的隐向量。换句话说，每个参数 $w_{ij}=⟨v_i,v_j⟩$，这就是FM模型的核心思想。因此，FM的模型方程为（本文不讨论FM的高阶形式）
$y(x)=w_0+\sum {i=1}^nw_ix_i+\sum{i=1}^n\sum_{j=i+1}^n⟨vi,vj⟩x_ix_j \ \ \ \ \ \ ···（2）$
其中，$v_i$是第i维特征的隐向量，$⟨⋅,⋅⟩$代表向量点积，计算公式为
$⟨v_i,v_j⟩=\sum_{f=1}^kv_{i,f}·v_{j,f}$
隐向量的长度为$k(k<<n)$，包含k个描述特征的因子。
具体解读一下这个公式
- 线性模型+交叉项：直观地看FM模型表达式，前两项是线性回归模型的表达式，最后一项是二阶特征交叉项（又称组合特征项），表示模型将两个互异的特征分量之间的关联信息考虑进来。用交叉项表示组合特征，从而建立特征与结果之间的非线性关系。
- 交叉项系数 → 隐向量内积：由于FM模型是在线性回归基础上加入了特征交叉项，模型求解时不直接求特征交叉项的系数$w_{ij}$（因为对应的组合特征数据稀疏，参数学习不充分），故而采用隐向量的内积$⟨vi,vj⟩$表示$w_{ij}$。具体的，FM求解过程中的做法是：对每一个特征分量$xi$引入隐向量$vi＝(vi,1,vi,2,⋯,vi,k)$，利用$v_iv^T_j$内积结果对交叉项的系数$w_{ij}$进行估计，公式表示：$ŵ ij=v_iv^T_j$
根据上式，二次项的参数数量减少为$kn$个，远少于多项式模型的参数数量。
此外，参数因子化表示后，使得$x_hx_i$的参数与$x_ix_j$的参数不再相互独立。这样我们就可以在样本系数的情况下相对合理地估计FM模型交叉项的参数。具体地：
$⟨v_h,v_i⟩=\sum_{f=1}^k v_{h,f}·v_{i,f}$
$⟨v_i,v_j⟩=\sum_{f=1}^k v_{i,f}·v_{j,f}$
$x_hx_i$与$x_ix_j$的系数分别为$⟨v_h,v_i⟩$和$⟨v_i,v_j⟩$，它们之间有共同项$v_i$，也就是说，所有包含$x_i$的非零组合特征（存在某个$j≠i$,使得$x_ix_j≠0$）的样本都可以用来学习隐向量$v_i$，这在很大程度上避免了数据系数行造成参数估计不准确的影响。而在多项式模型中，$w_{hi}$和$w_{ij}$是相互独立的。
显而易见，公式(2)是一个通用的拟合方程，可以采用不同的损失函数用于解决回归、二元分类等问题，比如可以采用MSE（Mean Square Error）损失函数来求解回归问题，也可以采用Hinge、Cross-Entropy损失来求解分类问题。当然，在进行二元分类时，FM的输出需要经过Sigmoid变换，这与Logistic回归是一样的。
| FM应用场景 | 损失函数 | 说明 |
|---|---|---|
| 回归 | 均方误差（MSE）损失 | Mean Square Error，与平方误差类似 |
| 二类分类 | Hinge/Cross-Entopy损失 | 分类时，结果需要做sigmoid变换 |
| 排序 |
直观上看，FM的复杂度是$O(kn^2)$，但是，通过下面的等价转换，可以将FM的二次项化简，其复杂度可以优化到$O(kn)$，即：
$\sum_{i=1}^n\sum_{j=i+1}^n⟨v_i,v_j⟩x_i,x_j=\frac{1}{2}\sum_{f=1}^k[(\sum_{i=1}^nv_{i,f}x_i)^2-\sum_{i=1}^nv_{i,f}^2x_i^2]$
下面给出详细推导：
$\sum_{i=1}^n\sum_{j=i+1}^n⟨v_i,v_j⟩x_ix_j \\ =\frac{1}{2}\sum_{i=1}^n\sum_{f=1}^n⟨v_i,v_j⟩x_ix_j-\frac{1}{2}\sum_{i=1}^n⟨v_i,v_i⟩x_ix_i \\ =\frac{1}{2}(\sum_{i=1}^n\sum_{j=1}^n\sum_{f=1}^kv_{i,f}v_{j,f}x_ix_j-\sum_{i=1}^n\sum_{f=1}^kv_{i,f}v_{i,f}x_ix_i) \\ =\frac{1}{2}\sum_{f=1}^k[(\sum_{i=1}^nv_{i,f}x_i)·(\sum_{j=1}^nv_{j,f}x_j)-\sum_{i=1}^nv_{i,f}^2x_i^2] \\ =\frac{1}{2}\sum_{f=1}^k[(\sum_{i=1}^nv_{i,f}x_i)^2- \sum_{i=1}^nv_{i,f}^2x_i^2]$
解读第一步到第二部，这里用A表示系数矩阵V的上三角元素，B表示对角线上的交叉项系数。由于系数矩阵V是一个对称阵，所以下三角和上三角相等，有下式成立：
$A=\frac{1}{2}(2A+B)-\frac{1}{2}B$
其中，
$A=\sum_{i=1}^n\sum_{j=i+1}^n⟨v_i,v_j⟩x_ix_j,B=\sum_{i=1}^n⟨v_i,v_j⟩x_ix_i$
把上式合并，得到等价的FM模型公式：
$\hat y(\mathbf{x}) = w_0+ \sum_{i=1}^d w_i x_i + \frac{1}{2} \sum_{f=1}^k \left( \left(\sum_{i=1}^dv_{i,f}x_i \right) ^2 – \sum_{i=1}^d v_{i,f}^2x_i^2\right) $
如果用随机梯度下降（SGD）法学系模型参数。那么模型各个参数的梯度如下：
$\frac{\partial}{\partial\theta}y\left(x\right)=\left\{\begin{array}{l} 1,\ \ if\ \theta\ is\ w_0\left (\textrm{常数项}\right)\\ x_i,\ if\ \theta\ is\ w_i\left (\textrm{线性项}\right)\\ x_i\underset{j=1}{\overset{n}{\varSigma}}v_{j,f}x_j-v_{i,f}x_{i}^{2},\ if\ \theta\ is\ v_{i,f}\left(\textrm{交叉项}\right)\\ \end{array}\right.$其中，$v_{j,f}$是隐向量$vj$的第f个元素。
由于$Σ^n_{j=1}v_{j,f}x_j$只与f有关，在参数迭代过程中，只需要计算第一次所有f的$Σ^n_{j=1}v_{j,f}x_j$，就能够方便地得到所有$v_{i,f}$的梯度。显然，计算所有f的$Σ^n_{j=1}v_{j,f}x_j$的复杂度是O$(kn)$；已知$Σ^n_{j=1}v_{j,f}x_j$时，计算每个参数梯度的复杂度是$O(n)$；得到梯度后，更新每个参数的复杂度是$O(1)$；模型参数一共有$nk+n+1$个。因此，FM参数训练的时间复杂度为$O(kn)$
3. FM的优3势
综上可知，FM算法可以在线性时间内完成模型训练，以及对新样本作出预测，所以说FM是一个非常高效的模型。FM模型的核心作用可以概括为以下三个：
- 1）FM降低了交叉项参数学习不充分的影响：one-hot编码后的样本数据非常稀疏，组合特征更是如此。为了解决交叉项参数学习不充分、导致模型有偏或不稳定的问题。作者借鉴矩阵分解的思路：每一维特征用k维的隐向量表示，交叉项的参数$w_{ij}$用对应特征隐向量的内积表示，即$<v_i,v_j⟩$。这样参数学习由之前学习交叉项参数$w_{i,j}$的过程，转变为学习$n$个单特征对应k维隐向量的过程。很明显，单特征参数（k维隐向量$v_i$）的学习要比交叉项参数$w_{ij}$学习的更加充分。示例说明：
假如有10w条训练样本，其中出现女性特征的样本数为3w，出现男性特征的样本数为7w，出现汽车特征的样本数为2000，出现化妆品的样本数为1000。特征共现的样本数如下：
| 共现交叉特征 | 样本数 | 注 |
|---|---|---|
| <女性，汽车> | 500 | 同时出现<女性，汽车>的样本数 |
| <女性，化妆品> | 1000 | 同时出现<女性，化妆品>的样本数 |
| <男性，汽车> | 1500 | 同时出现<男性，汽车>的样本数 |
| <男性，化妆品> | 0 | 样本中无此特征组合项 |
<女性，汽车>的含义是女性看汽车广告。可以看到，但特征对应的样本数远大于组合特征对应的样本数。训练时，但特征参数相比交叉项特征参数会学习地更充分。因此，可以说FM降低了因数据稀疏，导致交叉项参数学习不充分的影响。
2）FM提升了模型预估能力。依然看上面的示例，样本中没有没有<男性，化妆品>交叉特征，即没有男性看化妆品广告的数据。如果用多项式模型来建模，对应的交叉项参数$w_{男性，化妆品}$是学不出来的，因为数据中没有对应的共现交叉特征。那么多项式模型就不能对出现的男性看化妆品广告场景给出准确地预估。
FM模型是否能得到交叉项参数$w_{男性，化妆品}$呢？答案是肯定的。由于FM模型是把交叉项参数用对应的特征隐向量内积表示，这里表示为$w_{男性，化妆品}$=，即用男性特征隐向量$v_{男性}$和化妆品特征隐向量$v_{化妆品}$的内积表示交叉项参数$w_{男性，化妆品}$。由于FM学习的参数就是单特征的隐向量，那么男性看化妆品广告的预估结果可以用$w_{男性，化妆品}$得到。这样，即便训练集中没有出现男性看化妆品广告的样本，FM模型仍然可以用来预估，提升了预估的能力。
3）FM提升了参数学习效率：这个显而易见，参数个数由$(n^2+n+1)$变为$(nk+n+1)$个，模型训练复杂度也由$O(mn2)$变为$O(mnk)$。$m$为训练样本数。对于训练样本和特征数而言，都是线性复杂度。此外，就FM模型本身而言，它是在多项式模型基础上对参数的计算做了调整，因此也有人把FM模型称为多项式的广义线性模型，也是恰如其分的。从交互项的角度看，FM仅仅是一个可以表示特征之间交互关系的函数表法式，可以推广到更高阶形式，即将多个互异特征分量之间的关联信息考虑进来。例如在广告业务场景中，如果考虑User-Ad-Context三个维度特征之间的关系，在FM模型中对应的degree为3。
最后一句话总结，FM最大特点和优势：FM模型对稀疏数据有更好的学习能力，通过交互项可以学习特征之间的关联关系，并且保证了学习效率和预估能力。
与其他模型相比，它的优势如下：
- FM是一种比较灵活的模型，通过合适的特征变换方式，FM可以模拟二阶多项式核的SVM模型、MF模型、SVD++模型等；
- 相比SVM的二阶多项式核而言，FM在样本稀疏的情况下是有优势的；而且，FM的训练/预测复杂度是线性的，而二项多项式核SVM需要计算核矩阵，核矩阵复杂度就是N平方。
- 相比MF而言，我们把MF中每一项的rating分改写为$r_{ui}∼β_u+γ_i+x^T_uy_i$，从公式(2)中可以看出，这相当于只有两类特征 $u$ 和$i$ 的FM模型。对于FM而言，我们可以加任意多的特征，比如user的历史购买平均值，item的历史购买平均值等，但是MF只能局限在两类特征。SVD++与MF类似，在特征的扩展性上都不如FM，在此不再赘述。