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模型

我们先来看看二阶多项式模型的表达式：

其中$n$表示特征维度。从上式可知，交叉项中的组合特征参数个数一共有$\frac{n(n-1)}{2}$个，在这里，任意两个交叉项的系数$w_{ij}$都是独立的。然而，在数据非常稀疏的情况下，交叉项参数的学习是非常困难的。为什么呢？

因为我们知道，回归模型的参数$w$的学习过程其实就是从训练样本中计算充分统计量，是一个统计的过程；由大数定理我们知道，统计过程是建立在大量的样本基础之上才有意义，而在这里交叉项的每一个参数$w{ij}$的学习过程需要大量的$x_i$、$x_j$同时为非零的训练样本数据，然而经过one-hot编码之后，我们的样本数据本来就很稀疏，能够同时满足$x_i$和$x_j$都非零的样本数非常少，训练样本也就不充分，导致学习到的$w{ij}$不是充分统计量的结果，因此$w_{ij}$就不准确、不稳定，这会严重影响模型的预测效果和稳定性。

那么，如何在降低数据稀疏问题给模型性能带来的重大影响的同时，有效地解决二阶交叉项参数的学习问题呢？矩阵分解方法已经给出了解决思路。接触过协同过滤（CF）的同学应该知道，在基于model-based的协同过滤中，一个rating矩阵可以分解为一个user矩阵和一个item矩阵，每个uese和item都可以采用一个隐向量表示。如下图所示：

上图中，将每一个user表示成一个二维向量，同时也将每个item表示成一个二维向量，两个向量的内积就是矩阵中user对item的打分。根据矩阵分解的启发，如果把多项式模型中二阶交叉项参数$w_{ij}$组成一个对称矩阵$W$，那么这个矩阵就可以分解为$W={VV^T}$，$V\in R^{n*k}$称为系数矩阵，其中第$i$行对应着第$i$维特征的隐向量（熟悉word2vec的同学一定不陌生，word2vec中也是用类似于隐向量的方式来表示一个word的）。

将每个交叉项参数$w_{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在求解过程中的做法是：对每一个特征分量$xi$引入隐向量$v_i=(v{i,1},v{i,2},…,v{i,k})$，利用$viv_j^T$内积结果对交叉项系数$w{ij}$进行估计，即有$w_{ij} := v_iv_j^T$。

根据上式我们不难发现，二阶交叉项参数从$\frac{n(n-1)}{2}$减少到$n*k$个，由于通常情况下$n$要远远大于$k$，因此，FM参数要远少于二阶多项式模型中的参数数量。

另外一个很重要的地方在于，用FM模型表示之后，使得$x_hx_i$的参数和$x_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(kn^2)$，但是通过下面的等式变换，可以将FM的二次项化简，即：

上式中，用$A$表示系数矩阵$V$的上三角元素，$B$表示系数矩阵的对角线上的交叉项系数，由于系数矩阵$V$是一个对称矩阵，因此有下式成立：

由此，最终FM模型可以复杂度可以优化为$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模型训练的时间复杂度为$O(kn)$。综上所述，FM是一个非常高效的模型。

2.5 FM模型总结

以上主要从FM模型的引入、FM模型的推导和参数学习过程介绍了FM模型，这里把FM最核心的部分总结一下：

（1）FM降低了交叉项参数学习不充分的影响
one-hot编码后的样本数据非常稀疏，组合特征更是如此。为了解决交叉项参数学习不充分导致模型有偏或者不稳定的问题，作者借鉴了矩阵分解的思路：将每一维特征用$k$维的隐向量表示，交叉项的参数$w{ij}$用对应的隐向量的内积表示，这样参数学习由之前学习交叉项参数$w{ij}$的过程，转变为学习$n$个特征对应的$k$维隐向量的过程。很明显，单特征参数的学习要比交叉项参数$w_{ij}$学习得更充分。举例说明如下：
假设有10w个训练样本，其中性别为女性的样本数为3w，出现男性的样本数为7w，出现汽车的样本数为2000，出现化妆品的样本数为1000。出现<女性，汽车>的样本数为500，出现<女性，化妆品>的样本数为1000，出现<男性，汽车>的样本数为1500，出现<男性，化妆品>的样本数为0。可以看到，单特征对应的样本数远大于组合特征对应的样本数。训练时，单特征参数相对于交叉项特征参数会学习的更充分。因此，FM降低了因数据稀疏，导致交叉项参数学习不充分的影响。

（2）FM提升了模型的预估能力
上面的例子中，样本集中没有<男性，化妆品>的交叉特征，如果用多项式模型来建模，对应的交叉项参数$w{男性,化妆品}$是学习不出来的，因为数据中没有对应的共现交叉特征，因此多项式模型就不能对出现的男性看化妆品广告场景给出准确的预估。
FM模型则没有这个问题。由于FM模型是把交叉项参数用对应的隐向量内积来表示，因此，$w{男性,化妆品} = $，由于FM学习的参数就是但特征的隐向量，那么男性看化妆品广告的预估效果可以用$$得到。这样，即使训练样本中没有出现<男性，化妆品>的样本，FM模型依然可以用来做预估，提升了模型的预估能力。

（3）FM模型提升了参数学习效率
由于参数的个数从多项式模型的$n^2 + n + 1$变成了$nk + n + 1$，模型训练的复杂度也有$O(n^2)$变成了$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”$f_j$，都会学习一个隐向量$v{i,f_j}$，因此，隐向量不仅与特征相关，也和特征对应的field相关。

假设每个样本的$n$个特征属于$f$个field，那么FFM的二次项就有$nf$个隐向量。而在FM模型中，每一维特征的隐向量只有一个。因此可以把FM当做是FFM的一个特例，那就是将所有的特征都归属于同一个field中。根据FFM的field敏感特征，FFM的表达式为：

其中$f_j$是第$j$个特征所属的field。如果隐向量的长度为$k$，那么FFM的二阶交叉项参数个数就有$nfk$个，远多于FM模型的$nk$个。此外，由于隐向量与field有关，FFM的交叉项并不能够像FM那样做简化，因此其预测复杂度为$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相关的隐向量的内积得到。如果单特征有$n$个，全部做二阶特征组合的化，会有$\frac{n(n-1)}{2}$个。