1、背景

在计算广告和推荐系统中，CTR预估(click-through rate)是非常重要的一个环节，判断一个商品的是否进行推荐需要根据CTR预估的点击率来进行。在进行CTR预估时，除了单特征外，往往要对特征进行组合。对于特征组合来说，业界常用的方法有人工特征工程 + LR（Logistic Regression）、GBDT（Gradient Boosting Decision Tree） + LR、FM（Factorization Machine）和FFM（Field-aware Factorization Machine）模型。最近几年也出现了很多基于FM改进的方法，如deepFM，FNN，PNN，DCN，xDeepFM等。

2、动机（one-hot编码带来的问题）

FM(Factorization Machine)主要是为了解决数据稀疏的情况下，特征怎样组合的问题。已一个广告分类的问题为例，根据用户与广告位的一些特征，来预测用户是否会点击广告。数据如下：(本例来自美团技术团队分享的paper)
《推荐系统》-FM模型
图1、训练数据

clicked是分类值，表明用户有没有点击该广告。1表示点击，0表示未点击。而country,day,ad_type则是对应的特征。对于这种categorical特征，一般都是进行one-hot编码处理。

将上面的数据进行one-hot编码以后，就变成了下面这样：
《推荐系统》-FM模型
图2、经过one-hot

因为是categorical特征，所以经过one-hot编码以后，不可避免的样本的数据就变得很稀疏。举个非常简单的例子，假设淘宝或者京东上的item为100万，如果对item这个维度进行one-hot编码，光这一个维度数据的稀疏度就是百万分之一。由此可见，数据的稀疏性，是我们在实际应用场景中面临的一个非常常见的挑战与问题。

one-hot编码带来的另一个问题是特征空间变大。同样以上面淘宝上的item为例，将item进行one-hot编码以后，样本空间有一个categorical变为了百万维的数值特征，特征空间一下子暴增一百万。所以大厂动不动上亿维度，就是这么来的。

3、对特征进行组合

普通的线性模型，我们都是将各个特征独立考虑的，并没有考虑到特征与特征之间的相互关系。但实际上，大量的特征之间是有关联的。最简单的以电商为例，一般女性用户看化妆品服装之类的广告比较多，而男性更青睐各种球类装备。那很明显，女性这个特征与化妆品类服装类商品有很大的关联性，男性这个特征与球类装备的关联性更为密切。如果我们能将这些有关联的特征找出来，显然是很有意义的。

一般的线性模型为：
y ( x ) = w 0 + ∑ i = 1 n w i x i y(x)=w_{0} +\sum_{i=1}^n{w_{i} }x_{i} y(x)=w0+i=1∑nwixi

从上面的式子很容易看出，一般的线性模型压根没有考虑特征间的关联。为了表述特征间的相关性，我们采用多项式模型。在多项式模型中，特征 x i x_{i} xi 与 x j x_{j} xj 的组合用 x i x j x_{i} x_{j} xixj 表示。为了简单起见，我们讨论二阶多项式模型。具体的模型表达式如下：

为了简单起见，我们只考虑二阶交叉的情况，具体的模型如下：
y ( x ) = w 0 + ∑ i = 1 n w i x i + ∑ i = 1 n ∑ j = i + 1 n w i j x i x j y(x)=w_{0} +\sum_{i=1}^n{w_{i} x_{i} }+\sum_{i=1}^{n} \sum_{j=i+1}^n w_{ij} x_{i} x_{j} y(x)=w0+i=1∑nwixi+i=1∑nj=i+1∑nwijxixj

式中，n表示样本的特征数量, x i x_{i} xi 表示第i个特征，与线性模型相比，FM的模型就多了后面特征组合的部分。

4、FM求解

从FM公式可以看出，组合特征的参数一共有 n(n−1)/2个，任意两个参数都是独立的。然而，在数据稀疏性普遍存在的实际应用场景中，二次项参数的训练是很困难的。其原因是，每个参数 w i j w_{ij} wij 的训练需要大量 x i x_{i} xi 和 x j x_{j} xj 都非零的样本；由于样本数据本来就比较稀疏，满足 x i x_{i} xi 和 x j x_{j} xj 都非零”的样本将会非常少。训练样本的不足，很容易导致参数 w i j w_{ij} wij 不准确，最终将严重影响模型的性能。

那么，如何解决二次项参数的训练问题呢？矩阵分解提供了一种解决思路。在model-based的协同过滤中，一个rating矩阵可以分解为user矩阵和item矩阵，每个user和item都可以采用一个隐向量表示。比如在下图中的例子中，我们把每个user表示成一个二维向量，同时把每个item表示成一个二维向量，两个向量的点积就是矩阵中user对item的打分。
《推荐系统》-FM模型

3、矩阵分解

类似地，所有二次项参数 w i j w_{ij} wij 可以组成一个对称阵W（为了方便说明FM的由来，对角元素可以设置为正实数），那么这个矩阵就可以分解为 W = V T V W=V^T V W=VTV，V的第j列便是第j维特征的隐向量。换句话说，每个参数 x i j = < v i , v j > x_{ij} = <v_{i}, v_{j}> xij=<vi,vj>，这就是FM模型的核心思想。因此，FM的模型方程为（本文不讨论FM的高阶形式）
y ( x ) = w 0 + ∑ i = 1 n w i x i + ∑ i = 1 n ∑ j = i + 1 n < v i , v j > x i x j y(x)=w_{0}+ \sum_{i=1}^n w_{i} x_{i}+ \sum_{i=1}^{n} \sum_{j=i+1}^n <v_{i}, v_{j}> x_{i} x_{j} y(x)=w0+i=1∑nwixi+i=1∑nj=i+1∑n<vi,vj>xixj

其中， v i v_{i} vi 是第i维特征的隐向量，<.,.>代表向量点积。隐向量的长度为k(k<<n)，二次项的参数数量减少为kn个，远少于多项式模型的参数数量。另外，参数因子化使得 x h x j x_{h}x_{j} xhxj的参数和 x i x j x_{i}x_{j} xixj的参数不再是相互独立的，因此我们可以在样本稀疏的情况下相对合理地估计FM的二次项参数。具体来说， x h x i x_{h} x_{i} xhxi 和 x i x j x_{i} x_{j} xixj 的系数分别为 < v h , v i > <v_{h} ,v_{i} > <vh,vi>和 < v i , v j > <v_{i} ,v_{j} > <vi,vj> ，它们之间有共同项 v i v_{i} vi 。也就是说，所有包含" x i x_{i} xi 的非零组合特征"（存在某个 j ≠ i j \neq i j=i，使得 x i x j ≠ 0 x_{i} x_{j} \neq 0 xixj=0）的样本都可以用来学习隐向量 v i v i vivi vivi，这很大程度上避免了数据稀疏性造成的影响。而在多项式模型中， w h i w_{hi} whi和 w i j w_{ij} wij 是相互独立的。

显而易见，FM的模型公式是一个通用的拟合方程，可以采用不同的损失函数用于解决回归、二元分类等问题，比如可以采用MSE（Mean Square Error）损失函数来求解回归问题，也可以采用Hinge/Cross-Entropy损失来求解分类问题。当然，在进行二元分类时，FM的输出需要经过sigmoid变换，这与Logistic回归是一样的。直观上看，FM的复杂度是O(kn^2)。但是，通过下面的等式，FM的二次项可以化简，其复杂度可以优化到O(kn) 。由此可见，FM可以在线性时间对新样本作出预测。
∑ i = 1 n ∑ j = i + 1 2 < v i , v j > = 1 2 ∑ f = 1 k ( ( ∑ i = 1 n x i , f x i 2 ) 2 − ∑ i = 1 n x i , f 2 x i 2 ) \sum_{i=1}^n \sum_{j=i+1}^2 <v_{i},v_{j}>=\frac{1}{2}\sum_{f=1}^k ((\sum_{i=1}^n x_{i,f}x_{i} ^2)^2-\sum_{i=1}^nx_{i,f}^2 x_{i} ^2) i=1∑nj=i+1∑2<vi,vj>=21f=1∑k((i=1∑nxi,fxi2)2−i=1∑nxi,f2xi2)
《推荐系统》-FM模型
图4、推导过程

《推荐系统》-FM模型图5、二次项化简

我们再来看一下FM的训练复杂度，利用SGD（Stochastic Gradient Descent）训练模型。模型各个参数的梯度如下：
《推荐系统》-FM模型
图6、求解参数梯度

其中， x j , f x_{j,f} xj,f是隐向量 v j v_{j} vj 的第f个元素。由于 ∑ j = 1 n x j , f x j \sum\nolimits_{j=1}^n x_{j,f}x_{j} ∑j=1nxj,fxj 只与f有关，而与i无关，在每次迭代过程中，只需计算一次所有f的 ∑ j = 1 n x j , f x j \sum\nolimits_{j=1}^n x_{j,f}x_{j} ∑j=1nxj,fxj ，就能够方便地得到所有 v j , f v_{j,f} vj,f的梯度。显然，计算所有f的 ∑ j = 1 n x j , f x j \sum\nolimits_{j=1}^n x_{j,f}x_{j} ∑j=1nxj,fxj 的复杂度是O(kn)；已知 ∑ j = 1 n x j , f x j \sum\nolimits_{j=1}^n x_{j,f}x_{j} ∑j=1nxj,fxj 时，计算每个参数梯度的复杂度是O(1)；得到梯度后，更新每个参数的复杂度是O(1)；模型参数一共有nk+n+1个。因此，FM参数训练的复杂度也是O(kn)。综上可知，FM可以在线性时间训练和预测，是一种非常高效的模型。