1 背景说明
1.1 实际应用场景说明
FM 最早是在 2010 年提出，目的是解决大规模稀疏数据下的特征组合问题。关于数据稀疏的问题，在计算广告或者推荐系统等应用场景下，是常见的。
以移动端广告推荐为例，在日志系统中，每条 pv 日志和点击日志中，均包含有用户侧的信息（比如年龄，性别，国籍，手机上安装的 app 列表）、广告侧的信息（广告 id，广告出价，广告标题，广告图片 url，app 包名，app 允许在哪些国家展示）、上下文侧信息（包括用户手机浏览器 speeddial 个数，bookmark 列表，最长访问的网站等，手机操作系统，渠道 id），对于那些 categorical 类型的特征，比如国籍，安装的 app 列表，广告 id 等等，这种类型特征的取值仅仅是一个标识，本身并没有实际意义，更不能用来取值比较大。
以用户的年龄为例（通常情况下，我们将连续的特征离散化，方便 one-hot 标识），将年龄分为以下几个年龄段：0-15, 15-20, 20-25, 25-30, 30-35, 35-45, 45-200，之所以在 20-40 之间划分区间粒度较小是因为我们的用户主要集中在这个区间范围内。那么，当判断用户年龄分别在这几个区间中时，将年龄特征离散化表示为：
0-15: [1,0,0,0,0,0,0]
15-20: [0,1,0,0,0,0,0]
20-25: [0,0,1,0,0,0,0]
25-30: [0,0,0,1,0,0,0]
30-35: [0,0,0,0,1,0,0]
35-45: [0,0,0,0,0,1,0]
45-200: [0,0,0,0,0,0,1]
可以发现，由 one-hot 编码带来的数据稀疏性会导致特征空间变大。在上面的例子中，一维 categorical 特征在经过 one-hot 编码后变成了 7 维数值型特征。真实应用场景中，还要处理广告 id，app 列表（几十维），国籍（200 维左右），性别（二维）等等，这些特征经过 one-hot 编码之后，达到几万维甚至几十万维乃至几亿维也就不奇怪啦。
此外，也能发现，特征空间增长的维度取决于 categorical 型特征的取值个数。在数据稀疏性的现实情况下，我们如何利用这些特征来提升模型性能呢？
1.2 为什么需要特征交叉
大量的研究和实际数据表明：某些特征之间的关联信息对事件结果的发生会产生很大的影响。从实际业务线的广告点击数据分析来看，也确实印证了这样的结论。比如，在做广告推荐时，一个 RPG 类的游戏，显然年龄在 10-30 岁左右的男性用户点击这条广告的概率大一些；一个手机清理类软件，显然在 Android OS 低于 5.0，手机存储空间又比较小的用户点击可能性更大一些；等等，诸如此种例子还有很多，可以很容易下结论，特征交叉对于最终结果必然有较大影响；
那么特征交叉又该如何做呢？表征特征之间的关联，最直接的方法是构造组合特征。样本中特征之间的关联信息在 one-hot 编码和浅层模型（比如 LR、SVM）中是难以做到的。目前工业界主要有一下集中方法来表示特征交叉：
- 人工特征工程（数据分析 + 人工构造）
- 通过模型表示组合特征（深度学习 DSN，FM/FFM 等方法）
下面就将详细阐述 FM/FFM 是如何来表征特征交叉的，以后还会介绍深度学习在特征交叉中的应用。
2 FM 模型原理
为了更好的了解 FM 模型，我们先从多项式回归、交叉组合特征说起，然后再过度到 FM 模型。
2.1 从二阶多项式模型到 FM 模型
我们先来看看二阶多项式模型的表达式：
其中 nnn 表示特征维度。从上式可知，交叉项中的组合特征参数个数一共有 n(n−1)2n(n−1)2\frac{n(n-1)}{2}个，在这里，任意两个交叉项的系数 wijwijw_{ij}都是独立的。然而，在数据非常稀疏的情况下，交叉项参数的学习是非常困难的。为什么呢？
因为我们知道，回归模型的参数 www 的学习过程其实就是从训练样本中计算充分统计量，是一个统计的过程；由大数定理我们知道，统计过程是建立在大量的样本基础之上才有意义，而在这里交叉项的每一个参数 $w{ij} 的学习过程需要大量的的学习过程需要大量的的学习过程需要大量的x_i、、、x_j 同时为非零的训练样本数据，然而经过 one−hot 编码之后，我们的样本数据本来就很稀疏，能够同时满足同时为非零的训练样本数据，然而经过 one−hot 编码之后，我们的样本数据本来就很稀疏，能够同时满足同时为非零的训练样本数据，然而经过one-hot编码之后，我们的样本数据本来就很稀疏，能够同时满足x_i 和和和x_j 都非零的样本数非常少，训练样本也就不充分，导致学习到的都非零的样本数非常少，训练样本也就不充分，导致学习到的都非零的样本数非常少，训练样本也就不充分，导致学习到的w{ij} 不是充分统计量的结果，因此不是充分统计量的结果，因此不是充分统计量的结果，因此w_{ij}$ 就不准确、不稳定，这会严重影响模型的预测效果和稳定性。
那么，如何在降低数据稀疏问题给模型性能带来的重大影响的同时，有效地解决二阶交叉项参数的学习问题呢？矩阵分解方法已经给出了解决思路。接触过协同过滤（CF）的同学应该知道，在基于 model-based 的协同过滤中，一个 rating 矩阵可以分解为一个 user 矩阵和一个 item 矩阵，每个 uese 和 item 都可以采用一个隐向量表示。如下图所示：
上图中，将每一个 user 表示成一个二维向量，同时也将每个 item 表示成一个二维向量，两个向量的内积就是矩阵中 user 对 item 的打分。根据矩阵分解的启发，如果把多项式模型中二阶交叉项参数 wijwijw_{ij}组成一个对称矩阵 WWW，那么这个矩阵就可以分解为 W=VVTW=VVTW={VV^T}，V∈Rn∗kV∈Rn∗kV\in R^{n*k}称为系数矩阵，其中第 iii 行对应着第 iii 维特征的隐向量（熟悉 word2vec 的同学一定不陌生，word2vec 中也是用类似于隐向量的方式来表示一个 word 的）。
将每个交叉项参数 wijwijw_{ij}用隐向量的内积 $$ 来表示，正是 FM 模型的核心思想。
2.2 FM 模型原理
在这里我们只讨论二阶 FM 模型，其表达式为：
$y(x) := w0 + \sum{i=1}^nwix_i + \sum{i=1}^n\sum_{j=i+1}^nx_ix_j$
其中 $vi 表示第表示第表示第i 维特征的隐向量，维特征的隐向量，维特征的隐向量，表示两个长度为表示两个长度为表示两个长度为k 的向量的内积，计算公式为：的向量的内积，计算公式为：的向量的内积，计算公式为： = \sum{j=1}^kv{i,f}v{j,f} 其中，其中， 其中，k 为隐向量的大小，是个经验值，一般不会取很大，通过多次试验，我们最终确定为隐向量的大小，是个经验值，一般不会取很大，通过多次试验，我们最终确定为隐向量的大小，是个经验值，一般不会取很大，通过多次试验，我们最终确定k$ 的大小为 4。
直观的来看 FM 模型的表达式，前两项正是我们熟悉的 LR，最后一项就是二阶特征交叉项，表示模型将两个独立的特征分量之间的关联信息考虑进来。用交叉项表示组合特征，从而建立特征与最终结果之间的非线性关系。
由于 FM 模型是在 LR 的基础上加入了特征交叉，模型求解时不直接求特征交叉项的稀疏 $w{ij}，而是采用隐向量的内积，而是采用隐向量的内积，而是采用隐向量的内积来表示来表示来表示w{ij}。具体的，FM 在求解过程中的做法是：对每一个特征分量。具体的，FM 在求解过程中的做法是：对每一个特征分量。具体的，FM在求解过程中的做法是：对每一个特征分量xi 引入隐向量引入隐向量引入隐向量v_i=(v{i,1},v{i,2},…,v{i,k})，利用，利用，利用viv_j^T 内积结果对交叉项系数内积结果对交叉项系数内积结果对交叉项系数w{ij} 进行估计，即有进行估计，即有进行估计，即有w_{ij} := v_iv_j^T$。
根据上式我们不难发现，二阶交叉项参数从 n(n−1)2n(n−1)2\frac{n(n-1)}{2}减少到 n∗kn∗kn*k 个，由于通常情况下 nnn 要远远大于 kkk，因此，FM 参数要远少于二阶多项式模型中的参数数量。
另外一个很重要的地方在于，用 FM 模型表示之后，使得 xhxixhxix_hx_i 的参数和 xixjxixjx_ix_j 的参数不再相互独立。这样我们就可以在样本稀疏的情况下相对合理的估计 FM 模型交叉项的参数。
$ := \sum{f=1}^kv{h,f}v{i,f} := \sum{f=1}^kv{i,f}v{j,f} xhx_i 和和和x_ix_j 的系数分别为的系数分别为的系数分别为和和和，它们之间有共同项，它们之间有共同项，它们之间有共同项v_i，也就是说，所有包含，也就是说，所有包含，也就是说，所有包含x_i 的非零组合特征（也就是对某个的非零组合特征（也就是对某个的非零组合特征（也就是对某个j\neq i，有，有，有x_ix_j \neq 0）的样本都可以用来学习隐向量）的样本都可以用来学习隐向量）的样本都可以用来学习隐向量v_i，这就在很大程度上避免了因为数据稀疏造成的参数估计不准的影响。然而在二阶多项式模型中，参数，这就在很大程度上避免了因为数据稀疏造成的参数估计不准的影响。然而在二阶多项式模型中，参数，这就在很大程度上避免了因为数据稀疏造成的参数估计不准的影响。然而在二阶多项式模型中，参数w{ij} 和参数和参数和参数w_{ih}$ 的学习过程是相互独立的，没有任何联系。
2.3 FM 参数学习过程
从 FM 模型表达式中不难发现，FM 模型的复杂度为 O(kn2)O(kn2)O(kn^2)，但是通过下面的等式变换，可以将 FM 的二次项化简，即：
上式中，用 AAA 表示系数矩阵 VVV 的上三角元素，BBB 表示系数矩阵的对角线上的交叉项系数，由于系数矩阵 VVV 是一个对称矩阵，因此有下式成立：
由此，最终 FM 模型可以复杂度可以优化为 O(kn)O(kn)O(kn)。
如果采用 SGD 来学习模型参数，那么，模型各个参数的梯度如下：
2.4 模型计算复杂度
由于 $\sum{j=1}^nv{j,f}xj 只与只与只与f 有关，在参数迭代更新过程中，只需要计算第一次所有有关，在参数迭代更新过程中，只需要计算第一次所有有关，在参数迭代更新过程中，只需要计算第一次所有f 的的的\sum{j=1}^nv{j,f}x_j，就能够方便地得到所有，就能够方便地得到所有，就能够方便地得到所有v{i,f} 的梯度。显然，计算所有的梯度。显然，计算所有的梯度。显然，计算所有f 的的的\sum{j=1}^nv{j,f}xj 的复杂度为的复杂度为的复杂度为O(kn)；在已知；在已知；在已知\sum{j=1}^nv_{j,f}x_j 时，计算每个参数梯度的复杂度为时，计算每个参数梯度的复杂度为时，计算每个参数梯度的复杂度为O(n)；得到梯度之后，更新每个参数的复杂度为；得到梯度之后，更新每个参数的复杂度为；得到梯度之后，更新每个参数的复杂度为O(1)；模型一共有；模型一共有；模型一共有nk+n+1 个，因此，FM 模型训练的时间复杂度为个，因此，FM 模型训练的时间复杂度为个，因此，FM模型训练的时间复杂度为O(kn)$。综上所述，FM 是一个非常高效的模型。
2.5 FM 模型总结
以上主要从 FM 模型的引入、FM 模型的推导和参数学习过程介绍了 FM 模型，这里把 FM 最核心的部分总结一下：
（1）FM 降低了交叉项参数学习不充分的影响
one-hot 编码后的样本数据非常稀疏，组合特征更是如此。为了解决交叉项参数学习不充分导致模型有偏或者不稳定的问题，作者借鉴了矩阵分解的思路：将每一维特征用 kkk 维的隐向量表示，交叉项的参数 $w{ij} 用对应的隐向量的内积表示，这样参数学习由之前学习交叉项参数用对应的隐向量的内积表示，这样参数学习由之前学习交叉项参数用对应的隐向量的内积表示，这样参数学习由之前学习交叉项参数w{ij} 的过程，转变为学习的过程，转变为学习的过程，转变为学习n 个特征对应的个特征对应的个特征对应的k 维隐向量的过程。很明显，单特征参数的学习要比交叉项参数维隐向量的过程。很明显，单特征参数的学习要比交叉项参数维隐向量的过程。很明显，单特征参数的学习要比交叉项参数w_{ij}$ 学习得更充分。举例说明如下：
假设有 10w 个训练样本，其中性别为女性的样本数为 3w，出现男性的样本数为 7w，出现汽车的样本数为 2000，出现化妆品的样本数为 1000。出现 <女性，汽车> 的样本数为 500，出现 <女性，化妆品> 的样本数为 1000，出现 <男性，汽车> 的样本数为 1500，出现 <男性，化妆品> 的样本数为 0。可以看到，单特征对应的样本数远大于组合特征对应的样本数。训练时，单特征参数相对于交叉项特征参数会学习的更充分。因此，FM 降低了因数据稀疏，导致交叉项参数学习不充分的影响。
（2）FM 提升了模型的预估能力
上面的例子中，样本集中没有 <男性，化妆品> 的交叉特征，如果用多项式模型来建模，对应的交叉项参数 $w{男性, 化妆品} 是学习不出来的，因为数据中没有对应的共现交叉特征，因此多项式模型就不能对出现的男性看化妆品广告场景给出准确的预估。FM 模型则没有这个问题。由于 FM 模型是把交叉项参数用对应的隐向量内积来表示，因此，是学习不出来的，因为数据中没有对应的共现交叉特征，因此多项式模型就不能对出现的男性看化妆品广告场景给出准确的预估。FM 模型则没有这个问题。由于 FM 模型是把交叉项参数用对应的隐向量内积来表示，因此，是学习不出来的，因为数据中没有对应的共现交叉特征，因此多项式模型就不能对出现的男性看化妆品广告场景给出准确的预估。 FM模型则没有这个问题。由于FM模型是把交叉项参数用对应的隐向量内积来表示，因此，w{男性, 化妆品} = ，由于 FM 学习的参数就是但特征的隐向量，那么男性看化妆品广告的预估效果可以用，由于 FM 学习的参数就是但特征的隐向量，那么男性看化妆品广告的预估效果可以用，由于FM学习的参数就是但特征的隐向量，那么男性看化妆品广告的预估效果可以用$ 得到。这样，即使训练样本中没有出现 <男性，化妆品> 的样本，FM 模型依然可以用来做预估，提升了模型的预估能力。
（3）FM 模型提升了参数学习效率
由于参数的个数从多项式模型的 n2+n+1n2+n+1n^2 + n + 1 变成了 nk+n+1nk+n+1nk + n + 1，模型训练的复杂度也有 O(n2)O(n2)O(n^2)变成了 O(n∗k)O(n∗k)O(n*k )，因此 FM 模型提升了参数的学习效率。
3 FFM 模型原理
FFM 模型在 FM 的基础上借鉴了 field 的概念，是 FM 模型的升级版。通过引入 field 概念，FFM 把相同的特征归于同一个 field 中（这个 field 通常称为 slot）。在文章开始 one-hot 编码中提到的年龄特征，经过 one-hot 编码执行形成了 7 个特征，这 7 个特征都是用于描述用户年龄的，因此可以将其放在同一个 field 中。也就是说，我们可以把属于同一个 categorical 特征经过 one-hot 编码之后形成的数值型特征都可以放入到同一个 field 中。
在 FFM 模型中，每一维特征 $xi，针对其他特征的每一种 “field”，针对其他特征的每一种 “field”，针对其他特征的每一种“field”f_j，都会学习一个隐向量，都会学习一个隐向量，都会学习一个隐向量v{i,f_j}$，因此，隐向量不仅与特征相关，也和特征对应的 field 相关。
假设每个样本的 nnn 个特征属于 fff 个 field，那么 FFM 的二次项就有 nfnfnf 个隐向量。而在 FM 模型中，每一维特征的隐向量只有一个。因此可以把 FM 当做是 FFM 的一个特例，那就是将所有的特征都归属于同一个 field 中。根据 FFM 的 field 敏感特征，FFM 的表达式为：
其中 fjfjf_j 是第 jjj 个特征所属的 field。如果隐向量的长度为 kkk，那么 FFM 的二阶交叉项参数个数就有 nfknfknfk 个，远多于 FM 模型的 nknknk 个。此外，由于隐向量与 field 有关，FFM 的交叉项并不能够像 FM 那样做简化，因此其预测复杂度为 O(kn2)O(kn2)O(kn^2)。
这里结合一个例子来进一步说明 FFM 的原理。给定一个样本数据如下所示：
样本中，price 是数值型特征，实际应用中通常会把价格划分为若干个区间（即连续特征离散化），然后再 one-hot 编码，这里假设 $9.99 对应的离散区间 tag 为 2。当然并不是所有的连续型特征都要做离散化，比如某广告位、某类广告 / 商品、抑或是某类人群统计的历史 CTR 通常无需做离散化。
这个样本可以编码为 5 个数值特征，即 User-YuChin，Movie-3Idiots，Genre-Comedy，Genre-Drama，Price-2。其中，Genre-Comedy，Genre-Drama 属于同一个 field。为了说明 FFM 的样本格式，我们把所有的特征和对应的 field 映射成整数编号。
那么，FFM 所有的（二阶）组合特征共有 10 项，即为：
上图中，红色表示 field 编号，蓝色表示 feature 编号，绿色表示样本的组合特征取值。二阶交叉项的系数是通过与 field 相关的隐向量的内积得到。如果单特征有 nnn 个，全部做二阶特征组合的化，会有 n(n−1)2n(n−1)2\frac{n(n-1)}{2}个。