FM/FFM算法的产生

我们使用传统的线性模型（如逻辑回归）进行广告CTR（广告点击率）、CVR（转化率）预测时，往往遇到下面的问题:

数据集特征极度稀疏。许多特征如用户的地区、职业等都是类别型特征，其特征取值非常多，但每个取值的出现次数很少，这样我们对这些类别型特征进行one_hot编码后就会产生大量的零值特征，这样的特征对于传统的线性模型的预测会产生负面效果，导致模型的预测效果较差；
同样地，由于类别型特征的取值非常之多，转换成one_hot编码后会导致特征空间大大扩张，这增加了训练时的计算量，也使得模型的训练变得困难；
传统的线性模型没有考虑特征之间的相互关系，比如“化妆品”类商品与“女”性，“球类运动配件”的商品与“男”性，“电影票”的商品与“电影”品类偏好，这些特征之间往往是有联系的。但传统线性模型如逻辑回归模型只能通过手动构造组合特征来考虑特征与特征之间的相互关系，而非线性SVM虽然可以对特征进行核变换学习它的交叉特征，但是在特征高度稀疏的情况下，并不能很好的进行学习。

为什么线性SVM在和多项式SVM在稀疏条件下效果会比较差呢？
线性svm只有一维特征，不能挖掘深层次的组合特征；多项式svM交叉的多个特征需要在训练集上共现才能被学习到（即xi和xj需要同时不为0才对wij有训练效果），否则wij就为0，这样对于测试集上的样本而言这样的特征就失去了意义，因此在稀疏条件下，SVM表现并不能让人满意。

为了解决以上三个问题，产生了FM与FFM系列算法。

FM算法原理推导

论文:Factorization Machines
论文地址:https://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf 。
FM（Factorization Machines，因子分解机）主要是为了解决数据稀疏的情况下，特征怎样组合的问题。
举例:

       x1年龄    x2北京    x3上海    x4深圳    x5男    x6女
用户1    23      1          0          0          1          0
用户2    31      0          0          1          0          1

特征X有6个维度，年龄是连续值，城市和性别用one-hot表示，假设我们用最简单的线性拟合来预测y值:
$$
y=w_{0}+\sum_{i=1}^{n} w_{i} x_{i}
$$
实际中“北京的男性用户”、“上海的女性用户”这种组合特征可能是有用的，即xixj（xi,xj都是one-hot特征）同时为1时可能是一个很有用的特征，这种组合特征是xi和xj的线性组合所无法表示的。这样一来乘积xixj就成一个新的特征。
为了不错过任何一个这种可能有用的组合特征，我们穷举所有的i,j组合，把二项特征组合xixj都加到特征中，即使其中某些xi不是one-hot特征或者某些xixj不是有用的特征也没有关系，经过训练后模型会把那些无用的特征的系数训练为0。
模型公式变为下面这样:
$$
y=w_{0}+\sum_{i=1}^{n} w_{i} x_{i}+\sum_{i}^{n} \sum_{j=i+1}^{n} w_{i j} x_{i} x_{j}
$$
我们发现，加入二项组合后，模型的参数增加了n（n-1）/2个，这不但大大增加了计算量，同时由于大部分one_hot编码中的xi和xj同时不为0的样本较少，这些二项组合的参数很难训练。

FM模型推导

传统的线性回归模型公式如下:
$$
\begin{aligned} f(x) &=w_{0}+w_{1} x_{1}+w_{2} x_{2}+\ldots+w_{n} x_{n} \\ &=w_{0}+\sum_{i=1}^{n} w_{i} x_{i} \end{aligned}
$$
其中(w0,w1…wn)为模型参数，(x1,x2…xn)为特征。
我们在传统的线性回归模型的基础上，考虑任意2个特征分量之间的关系，得到下面的二项式模型:
$$
y=w_{0}+\sum_{i=1}^{n} w_{i} x_{i}+\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} w_{i j} x_{i} x_{j}
$$
其中n表示样本的特征数量，这里的特征是离散化后的特征。与线性模型相比，FM的模型多了后面的特征组合的部分。二项组合特征的参数一共有n(n−1)/2个，任意两个参数都是独立的。对于参数wi，只要这个样本中对应的xi不为0，则可以完成一次训练；对于参数wij的训练，需要这个样本中的xi和xj同时不为0，才可以完成一次训练。
在数据稀疏的实际应用场景中，二次项wij的训练是非常困难的。因为每个wij都需要大量xi和xj都不为0的样本。但在数据稀疏性比较明显的样本中，xi和xj都不为0的样本会非常稀少，这会导致wij不能得到足够的训练，容易导致参数wij不准确，最终将严重影响模型的性能。
假设有n个特征维度，为了求解Wij，我们为每个特征维度xi引入一个辅助向量：
$$
V_{i}=\left(v_{i1}, v_{i2}, \ldots, v_{ik}\right)^{T}
$$
Vi是第i维特征的隐向量，隐向量的长度为k（k<<n）。
隐变量V是所有Vi组成的矩阵:
$$
V=\left[ \begin{array}{ccccc}{v_{11}} & {v_{21}} & {v_{31}} & {\cdots} & {v_{n 1}} \\ {v_{12}} & {v_{22}} & {v_{32}} & {\cdots} & {v_{n 2}} \\ {\vdots} & {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ {v_{1 k}} & {v_{2 k}} & {v_{3 k}} & {\cdots} & {v_{n k}}\end{array}\right]=\left[ \begin{array}{c}{V_{1}} & {V_{2}} & {\cdots} & {V_{n}}\end{array}\right]
$$

我们需要求出所有wij组成的矩阵W，这是一个nxn矩阵:
$$
W=\left[\begin{array}{cccc}{w_{11}} & {w_{12}} & {\dots} & {w_{1 n}} \\ {w_{21}} & {w_{22}} & {\dots} & {w_{2 n}} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ {w_{n 1}} & {w_{n 2}} & {\dots} & {w_{n n}}\end{array}\right]
$$
W矩阵是一个对称阵，只要它的值能保证矩阵正定，矩阵就可以进行如下分解:
$$
w=V^{T} V=\left[ \begin{array}{ccccc}{v_{11}} & {v_{12}} & {v_{13}} & {\cdots} & {v_{1 k}} \\ {v_{21}} & {v_{22}} & {v_{23}} & {\cdots} & {v_{2 k}} \\ {\vdots} & {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ {v_{n 1}} & {v_{n 2}} & {v_{n 3}} & {\cdots} & {v_{n k}}\end{array}\right] \left[\begin{array}{ccccc}{v_{11}} & {v_{21}} & {v_{31}} & {\cdots} & {v_{n 1}} \\ {v_{12}} & {v_{22}} & {v_{32}} & {\cdots} & {v_{n 2}} \\ {\vdots} & {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ {v_{1 k}} & {v_{2 k}} & {v_{3 k}} & {\cdots} & {v_{n k}}\end{array}\right]
$$
V 的第j列便是第j维特征的隐向量。这样我们就把大小为nxn的w矩阵分解成了nxk的V矩阵与kxn的V的转置矩阵的乘积。
于是上面的二项式模型可写成:
$$
y(x)=w_{0}+\sum_{i=1}^{n} w_{i} x_{i}+\sum_{i=1}^{n} \sum_{j=1}^{n}<v_{i}, v_{j}>x_{i} x_{j}
$$
这就是FM模型。
二次项的参数数量减少为kn个，远少于最初的二项式模型的参数数量。另外，参数因子化使得xhxi 的参数和xixj的参数不再是相互独立的，因此我们可以在样本稀疏的情况下相对合理地估计FM的二次项参数。具体来说，xhxi和xixj的系数分别为<vh,vi>和<vi,vj>，它们之间有共同项vi。也就是说，所有包含”xi的非零组合特征”（存在某个 j≠i，使得 xixj≠0）的样本都可以用来学习隐向量vi，这很大程度上避免了数据稀疏性造成的影响。而在多项式模型中，whi和wij是相互独立的。
FM模型既可以解决回归问题，也可以解决二分类问题。如可以采用平方差损失函数来求解回归问题，也可以采用交叉熵损失来求解分类问题。在进行二元分类时，输出需要经过sigmoid变换，这与Logistic回归是一样的。直观上看，FM的复杂度是 O（kn2）。

FM模型的化简

我们可以对上面的FM模型进行进一步化简，降低时间复杂度。
$$
\sum_{i=1}^{n} \sum_{j=1}^{n}<v_{i}, v_{j}>x_{i} x_{j}
$$
是一个完整的对称矩阵，而下面的矩阵是这个对称矩阵的上三角部分（不包含对角线）:
$$
\sum_{i=1}^{n} \sum_{j=i+1}^{n}<v_{i}, v_{j}>x_{i} x_{j}
$$
所以有下列对应关系:
$$
\sum_{i=1}^{n} \sum_{j=i+1}^{n}<v_{i}, v_{j}>x_{i} x_{j}=(\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n}<v_{i}, v_{j}>x_{i} x_{j})-(\frac{1}{2} \sum_{i=1}^{n}<v_{i}, v_{i}>x_{i} x_{i})
$$
即对称矩阵减去对角线再除以2就是我们要求的对称矩阵上三角部分。
把求和符号放到式子里面，得:
$$
\sum_{i=1}^{n} \sum_{j=i+1}^{n}<v_{i}, v_{j}>x_{i} x_{j} =\frac{1}{2}\left(\left(\sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{f=1}^{k} v_{i,f} v_{j,f} x_{i} x_{j}\right)-\left(\sum_{i=1}^{n} \sum_{f=1}^{k} v_{i,f} v_{i,f} x_{i} x_{i}\right)\right) \\ =\frac{1}{2}\left(\left(\sum_{f=1}^{k} \sum_{i=1}^{n} v_{i,f} x_{i} \sum_{j=1}^{n} v_{j,f} x_{j}\right)-\left(\sum_{i=1}^{n} \sum_{f=1}^{k} v_{i,f} v_{i,f} x_{i} x_{i}\right)\right)
$$
vi,f是隐向量vi的第f个元素，vj,f是隐向量vj的第f个元素。由于vi,fxi跟j没有关系，vj,fxj跟i没有关系，因此
$$
\sum_{i=1}^{n} v_{i,f} x_{i} \sum_{j=1}^{n} v_{j,f} x_{j}=\left(\sum_{i=1}^{n} v_{i,f} x_{i}\right)\left(\sum_{j=1}^{n} v_{j,f} x_{j}\right)
$$
上式就可继续化简为
$$
\sum_{i=1}^{n} \sum_{j=i+1}^{n}<v_{i}, v_{j}>x_{i} x_{j} =\frac{1}{2}\left(\sum_{f=1}^{k}\left(\sum_{i=1}^{n} v_{i,f} x_{i}\right)\left(\sum_{j=1}^{n} v_{j,f} x_{j}\right)-\sum_{i=1}^{n} \sum_{f=1}^{k} v_{i,f} v_{i,f} x_{i} x_{i}\right) \\ =\frac{1}{2} \sum_{f=1}^{k}\left(\left(\sum_{i=1}^{n} v_{i,f} x_{i}\right)\left(\sum_{j=1}^{n} v_{j,f} x_{j}\right)-\sum_{i=1}^{n} v_{i,f}^{2} x_{i}^{2}\right) \\ =\frac{1}{2} \sum_{f=1}^{k}\left(\left(\sum_{i=1}^{n} v_{i,f} x_{i}\right)^{2}-\sum_{i=1}^{n} v_{i,f}^{2} x_{i}^{2}\right)
$$
这样时间复杂度就降为O（kn）。把上式带入到FM模型公式中，我们就得到了时间复杂度优化到O（kn）的FM模型公式。

梯度下降法求解W和V

梯度下降法求解梯度公式:
$$
\frac{\partial y(x)}{\partial \theta} =\begin{cases}{1,} & {\text { if } \theta \text { is } w_{0}} \\ {x_{i},} & {\text { if } \theta \text { is } w_{i}} \\ {x_{i} \sum_{j=1}^{n} v_{j,f} x_{j}-v_{i f} x_{i}^{2},} & {\text { if } \theta \text { is } v_{i f}}\end{cases}
$$
vj,f是隐向量vj的第f个元素。在根据x计算y时
$$
\sum_{j=1}^{n} v_{j,f} x_{j}
$$
只与f有关，而与i无关，在每次迭代过程中，只需计算一次所有f的上式，就能够方便地得到所有vi,f 的梯度。求vi,f 的梯度
$$
\frac{\partial \hat{y}}{\partial v_{i f}}
$$
的时间复杂度为O（1），对所有参数求偏导的总的时间复杂度为O（kn）。化简后的FM模型可以在线性时间训练和预测，是一种非常高效的模型。

FM与SVM的区别

SVM的二元特征交叉参数是独立的，而FM的二元特征交叉参数是两个k维的向量vi、vj，交叉参数就不是独立的，而是相互影响的；
FM可以在原始形式下进行优化学习，而基于kernel的非线性SVM通常需要在对偶形式下进行；
FM的模型预测是与训练样本独立，而SVM则与部分训练样本（支持向量）有关。

FFM算法原理推导

论文:Field-aware Factorization Machines
论文地址:https://www.csie.ntu.edu.tw/~r01922136/slides/ffm.pdf 。
FFM（Field-aware Factorization Machines，场感知分解机）是对FM模型的改进。在FM中，原始特征通过one-hot编码新生成的特征集合我们没有用一个field来标识它们是由同一个原始类别型特征生成的。而在FFM算法中，这种关系得到了保留，即那就是同一个原始特征使用one_hot编码生成的新特征属于同一个Field。
举例:

field    field1年龄        field2城市                field3性别
feature    x1年龄        x2北京    x3上海    x4深圳        x5男    x6女
用户1    23            1        0        0            1        0
用户2    31            0        0        1            0        1

对于连续特征，一个特征就对应一个Field。或者对连续特征离散化，一个分箱成为一个特征；对于离散特征，采用one-hot编码，同一种属性的归到一个Field。

FM对每一个新特征学习一个长度为k的隐式向量vi，共有nk个参数；FFM是对每一个新特征学习f个长度为k的隐式向量vifj，共有nkf个参数。即FFM有f个FM中的参数矩阵，针对每个field都有一个。从这个角度看，FM是FFM的f=1的特例。
假设样本的n个新特征属于f个field，那么FFM的二次项有nf个隐向量。而在FM模型中，每一维特征的隐向量只有一个，FM的二次项共有n个隐向量。
FFM的模型公式如下:
$$
y(x)=w_{0}+\sum_{i=1}^{n} w_{i} x_{i}+\sum_{i=1}^{n} \sum_{j=i+1}^{n}<v_{i,f_{j}}, v_{j,f_{i}}> x_{i} x_{j}
$$
其中，fj是第j个特征所属的field。如果隐向量的长度为k，那么FFM的二次参数有nfk个，远多于FM模型的nk个。此外，由于隐向量与field相关，FFM二次项并不能够化简，其预测复杂度是O（kn2）。
网上实现的FFM模型都没有考虑非交叉特征，即省略了常数项和一次项，实现的FFM模型公式如下:
$$
\phi(\mathbf{w}, \mathbf{x})=\sum_{j_{1}, j_{2} \in C_{2}}<w_{j_{1}, f_{2}}, w_{j_{2}, f_{1}}> x_{j_{1}} x_{j_{2}}
$$
其中，C2是非零特征的二元组合，j1是特征，属于field f1，wj1,f2是特征j1对fieldf2的隐向量。
如Yu-Chin Juan实现了一个C++版的FFM模型，源码下载地址:https://github.com/ycjuan/libffm 。此FFM模型采用logistic loss作为损失函数，和L2惩罚项，因此只能用于二元分类问题。
损失函数如下:
$$
\min_{w} \sum_{i=1}^{L} \log \left(1+\exp \left(-y_{i} \phi\left(\mathbf{w}, \mathbf{x}_{i}\right)\right)\right)+\frac{\lambda}{2}|\mathbf{w}|^{2}
$$
其中，yi取值−1或1，是第i个样本的label，L是训练样本数量，λ是惩罚项系数。模型采用SGD优化算法。
在使用FFM模型时，我们最好进行数值型特征的归一化，因为特征中同时包含数值型特征和类别型特征，而类别型特征进行one_hot编码后的特征取值只有0或1，较大的数值型特征会造成模型学习时类别型特征的参数变得很小，使得模型预测性能下降。

deepFM算法原理

论文:DeepFM: A Factorization-Machine based Neural Network for CTR Prediction
论文地址:https://arxiv.org/pdf/1703.04247.pdf 。
FM算法通过对于每一个特征的隐变量内积来提取特征组合，最后的结果也不错，虽然理论上FM可以对高阶特征组合进行建模，但实际上因为计算复杂度原因，一般都只用到二阶特征组合。对于大于二阶的高阶特征组合来说，我们很自然想到多层神经网络DNN。DeepFM算法同时使用了FM和DNN，其中FM算法负责对一阶特征以及由一阶特征两两组合而成的二阶特征进行特征的提取，DNN算法负责对由输入的一阶特征进行全连接等操作形成的高阶特征进行特征的提取。

deepFM算法结构

DeepFM包含两部分：FM部分与DNN部分，分别负责一二阶特征的提取和大于二阶的高阶特征的提取。这两部分共享同样的输入。对于特征i，标量wi用于表示其一阶权重。隐向量Vi用于表示特征i与其他特征之间的相互作用。Vi在FM部分是用于对2阶特征进行建模，即特征之间的相互作用；Vi输入到Deep部分则是用于进行大于二阶的高阶特征建模。
DeepFM的预测结果可以写为：
$$
\hat y=\operatorname{sigmoid}\left(y_{F M}+y_{D N N}\right)
$$

FM部分

$$
y_{F M}=w_{0}+\sum_{i=1}^{n} w_{i} x_{i}+\sum_{i=1}^{n} \sum_{j=1}^{n}<v_{i}, v_{j}>x_{i} x_{j}
$$
FM算法中除了一阶特征的表示，还有2阶的组合特征表示。通过特征的隐向量之间的内积表示2阶的组合特征。即计算Vi和Vj的内积，从而得到特征i和特征j的2阶相互作用。这种方案就可以解决训练数据集中很少出现或者不出现的特征其权重很难训练的问题。
注意：
虽然公式上yFM是所有部分都求和，是一个标量。但是实际上输入到输出单元的部分并不是一个标量，应该是一个向量。
实际实现中采用的是FM化简之后的内积公式，最终的维度是：field_size+embedding_size（对应FM Layer中的神经元个数: Field数量+嵌入维度=F+k，其中F为one-hot之前特征维度，k为embedding的特征维度）。
field_size对应的是一阶特征的权重，embedding_size对应的是二阶组合特征的权重。由FM算法的化简公式，最后可化简为:
$$
\frac{1}{2} \sum_{f=1}^{k}\left(\left(\sum_{i=1}^{n} v_{i,f} x_{i}\right)^{2}-\sum_{i=1}^{n} v_{i,f}^{2} x_{i}^{2}\right)
$$
上式是在[1,K]上的一个求和。 K就是Embedding后的维度，也就是embedding_size。也就是说，在DeepFM的FM模块中，最后没有对结果从[1,K]进行求和。而是把这K个数拼接起来形成了一个K维度的向量。

deep部分

deep部分是一个全连接神经网络。由于CTR的输入一般是极其稀疏的。因此需要重新设计网络结构。具体实现中为，在第一层隐含层之前，引入一个嵌入层（embedding）来完成将输入向量压缩到低维稠密向量。
在deepFM中，FM部分的隐向量与嵌入层的权重矩阵是共享的（隐向量作为嵌入层的权重矩阵）。这种共享的策略又进一步通过反向传播的方式影响了低阶与高阶的特征组合。从而构建出更具有表征能力的特征。
嵌入层的表示如下：
$$
a_{0}=\left[e_{1}, e_{2}, \cdots, e_{m}\right]
$$
其中ei表示嵌入层的第i个field。a0为输入深度神经网络的向量，前馈过程可以表示为：
$$
a_{l+1}=\sigma\left(W^{(l)} a^{(l)}+b^{(l)}\right)
$$
嵌入层有两个有趣的特性：

尽管不同field的输入长度不同，但是embedding之后向量的长度均为K；
在FM里得到的隐变量Vik现在作为嵌入层网络的权重，Vik是嵌入层中第i个特征连接到嵌入层第k个节点的权重。

对于第二点举例说明:
假设我们的k=5，某个类别型特征经过one_hot编码后为第5-15特征，其隐向量按列排成矩阵如下：
$$
\left[\begin{array}{c}{V_{5,1}, V_{6,1}, V_{7,1},\cdots, V_{13,1},V_{14,1}, V_{15,1} }\\ {V_{5,2}, V_{6,2}, V_{7,2},\cdots, V_{13,2},V_{14,2}, V_{15,2} }\\{V_{5,3}, V_{6,3}, V_{7,3},\cdots, V_{13,3},V_{14,3}, V_{15,3} } \\ {V_{5,4}, V_{6,4}, V_{7,4},\cdots, V_{13,4},V_{14,4}, V_{15,4} } \\
{V_{5,5}, V_{6,5}, V_{7,5},\cdots, V_{13,5},V_{14,5}, V_{15,5} }
\end{array}\right]
$$
同时，它也可看作嵌入层（embedding）的参数矩阵，按照神经网络前向传播的方式，embedding后的向量值应该表示为：
$$
\left[\begin{array}{c}{V_{5,1}, V_{6,1}, V_{7,1},\cdots, V_{13,1},V_{14,1}, V_{15,1} }\\ {V_{5,2}, V_{6,2}, V_{7,2},\cdots, V_{13,2},V_{14,2}, V_{15,2} }\\{V_{5,3}, V_{6,3}, V_{7,3},\cdots, V_{13,3},V_{14,3}, V_{15,3} } \\ {V_{5,4}, V_{6,4}, V_{7,4},\cdots, V_{13,4},V_{14,4}, V_{15,4} } \\
{V_{5,5}, V_{6,5}, V_{7,5},\cdots, V_{13,5},V_{14,5}, V_{15,5} }
\end{array}\right]\left[\begin{array}{c}{x_{5}} \\ {x_{6}} \\ {x_{7}} \\ \cdots \\ {x_{13}} \\ {x_{14}} \\ {x_{15}} \end{array}\right]
$$
上面矩阵相乘的结果就是一个5维向量，由于这10列特征是一个类型型特征one_hot编码后而成，故右边矩阵中只有一个值为1，其他为0。假设右边矩阵中x7的值为1，那么矩阵相乘之后的结果为：
$$
\left[\begin{array}{c} {V_{7,1}} \\ {V_{7,2}} \\ {V_{7,3}} \\ {V_{7,4}} \\ {V_{7,5}} \end{array}\right] \ast x_{7}
$$
实际上嵌入层（embedding）的参数矩阵与输入向量相乘后得到是one-hot后有值的那一维特征所对应的隐向量。
假如我们现在有两个类别型特征，我们看看FM中的二阶组合特征的隐向量权重矩阵如何得到。假如有两个类别型特征，其one_hot编码后分别是第7个特征和第20个特征值为1，则经过嵌入层（embedding）计算后得到的两个矩阵，让他们相乘后为：
$$
\left[\begin{array}{c} {V_{7,1}} \\ {V_{7,2}} \\ {V_{7,3}} \\ {V_{7,4}} \\ {V_{7,5}} \end{array}\right] x_{7} \left[\begin{array}{c} {V_{20,1}} \\ {V_{20,2}} \\ {V_{20,3}} \\ {V_{20,4}} \\ {V_{20,5}} \end{array}\right] x_{20}=<v_{7}, v_{20}>x_{7} x_{20}
$$
这个乘积的结果就是FM中二阶组合特征的其中一项，而对于所有非0组合（embedding向量组合）求和之后，就是FM中所有的二阶组合特征的部分，FM中的一阶特征则直接在embedding之前对于特征进行组合即可。