本文仅为记录学习FM、FFM、DeepFM过程中的一些理解，并不会涉及太多公式细节推导，细节方面可以参考 深入FFM原理与实践 和 『我爱机器学习』FM、FFM与DeepFM
以及相关论文，本文主要内容也是摘自与上述博客。
FM模型的引入-广告特征的稀疏性
FM（Factorization machines）模型由Steffen Rendle于2010年提出，目的是解决稀疏数据下的特征组合问题。
在介绍FM模型之前，来看看稀疏数据的训练问题。以广告CTR（click-through rate）点击率预测任务为例，假设有如下数据：
第一列Clicked是类别标记，标记用户是否点击了该广告，而其余列则是特征（这里的三个特征都是类别类型），一般的，我们会对数据进行One-hot编码将类别特征转化为数值特征，转化后数据如下:
经过One-hot编码后，特征空间是十分稀疏的。特别的，某类别特征有m种不同的取值，则one-hot编码后就会被变为m维！当类别特征越多、类别特征的取值越多，其特征空间就更加稀疏。
此外，往往我们会将特征进行两两的组合，这是因为：通过观察大量的样本数据可以发现，某些特征经过关联之后，与label之间的相关性就会提高。例如，“USA”与“Thanksgiving”、“China”与“Chinese New Year”这样的关联特征，对用户的点击有着正向的影响。换句话说，来自“China”的用户很可能会在“Chinese New Year”有大量的浏览、购买行为，而在“Thanksgiving”却不会有特别的消费行为。这种关联特征与label的正向相关性在实际问题中是普遍存在的，如“化妆品”类商品与“女”性，“球类运动配件”的商品与“男”性，“电影票”的商品与“电影”品类偏好等。
再比如，用户更常在饭点的时间下载外卖app，因此，引入两个特征的组合是非常有意义的。
如何表示两个特征的组合呢？一种直接的方法就是采用多项式模型来表示两个特征的组合，𝑥𝑖为第𝑖个特征的取值（注意和以往表示第𝑖个样本的特征向量的区别），𝑥𝑖𝑥𝑗表示特征𝑥𝑖和𝑥𝑗的特征组合，其系数𝑤𝑖𝑗即为我们学习的参数，也是𝑥𝑖𝑥𝑗组合的重要程度：
式1-1也可以称为Poly2(degree-2 poly-nomial mappings)模型。注意到式子1-1中参数的个数是非常多的！一次项有d+1个，二次项（即组合特征的参数）共有𝑑(𝑑−1)/2个，而参数与参数之间彼此独立，在稀疏场景下，二次项的训练是很困难的。因为要训练𝑤𝑖𝑗，需要有大量的𝑥𝑖和𝑥𝑗都非零的样本（只有非零组合才有意义）。而样本本身是稀疏的，满足𝑥𝑖𝑥𝑗≠0的样本会非常少，样本少则难以估计参数𝑤𝑖𝑗，训练出来容易导致模型的过拟合。
为此，Rendle于2010年提出FM模型，它能很好的求解式1-1，其特点如下：
- FM模型可以在非常稀疏的情况下进行参数估计
- FM模型是线性时间复杂度的，可以直接使用原问题进行求解，而且不用像SVM一样依赖支持向量。
- FM模型是一个通用的模型，其训练数据的特征取值可以是任意实数。而其它最先进的分解模型对输入数据有严格的限制。FMs可以模拟MF、SVD++、PITF或FPMC模型。
FM模型
前面提到过，式1-1的参数难以训练时因为训练数据的稀疏性。对于不同的特征对𝑥𝑖,𝑥𝑗和𝑥𝑖,𝑥𝑘，式1-1认为是完全独立的，对参数𝑤𝑖𝑗和𝑤𝑖𝑘分别进行训练。而实际上并非如此，不同的特征之间进行组合并非完全独立，如下图所示:
回想矩阵分解，一个rating可以分解为user矩阵和item矩阵，如下图所示：
分解后得到user和item矩阵的维度分别为𝑛𝑘和𝑘𝑚，（k一般由用户指定），相比原来的rating矩阵，空间占用得到降低，并且分解后的user矩阵暗含着user偏好，Item矩阵暗含着item的属性，而user矩阵乘上item矩阵就是rating矩阵中用户对item的评分。
因此，参考矩阵分解的过程，FM模型也将式1-1的二次项参数𝑤𝑖𝑗进行分解：
其中𝑣𝑖是第𝑖维特征的隐向量，其长度为𝑘(𝑘≪𝑑)。 (𝐯𝑖⋅𝐯𝑗)为内积，其乘积为原来的𝑤𝑖𝑗，即:
为了方便说明，考虑下面的数据集（实际中应该进行one-hot编码，但并不影响此处的说明）：
对于上面的训练集，没有（NBC，Adidas）组合，因此，Poly2模型就无法学习到参数𝑤𝑁𝐵𝐶,𝐴𝑑𝑖𝑑𝑎𝑠。而FM模型可以通过特征组合(NBC，Nike)、(EPSN，Adidas) 分别学习到隐向量𝑉𝑁𝐵𝐶和𝑉𝐴𝑑𝑖𝑑𝑎𝑠，这样使得在测试集中得以进行预测。
更一般的，经过分解，式2-1的参数个数减少为𝑘𝑑个，对比式1-1，参数个数大大减少。使用小的k，使得模型能够提高在稀疏情况下的泛化性能。此外，将𝑤𝑖𝑗进行分解，使得不同的特征对不再是完全独立的，而它们的关联性可以用隐式因子表示，这将使得有更多的数据可以用于模型参数的学习。比如𝑥𝑖,𝑥𝑗与𝑥𝑖,𝑥𝑘的参数分别为：⟨𝐯𝑖,𝐯𝑗⟩和⟨𝐯𝑖,𝐯𝑘⟩，它们都可以用来学习𝐯𝑖，更一般的，包含𝑥𝑖𝑥𝑗≠0&𝑖≠𝑗的所有样本都能用来学习𝐯𝑖，很大程度上避免了数据稀疏性的影响。
FFM模型
考虑下面的数据集：
对于第一条数据来说，FM模型的二次项为：𝐰𝐸𝑃𝑆𝑁⋅𝐰𝑁𝑖𝑘𝑒+𝐰𝐸𝑃𝑆𝑁⋅𝐰𝑀𝑎𝑙𝑒+𝐰𝑁𝑖𝑘𝑒⋅𝐰𝑀𝑎𝑙𝑒。（这里只是把上面的v符合改成了w）每个特征只用一个隐向量来学习和其它特征的潜在影响。对于上面的例子中，Nike是广告主，Male是用户的性别，描述（EPSN，Nike）和（EPSN，Male）特征组合，FM模型都用同一个𝐰𝐸𝑆𝑃𝑁，而实际上，ESPN作为广告商，其对广告主和用户性别的潜在影响可能是不同的。
因此，Yu-Chin Juan借鉴Michael Jahrer的论文（Ensemble of collaborative filtering and feature engineered models for click through rate prediction），将field概念引入FM模型。
field是什么呢？即相同性质的特征放在一个field。比如EPSN、NBC都是属于广告商field的，Nike、Adidas都是属于广告主field，Male、Female都是属于性别field的。简单的说，同一个类别特征进行one-hot编码后生成的数值特征都可以放在同一个field中，比如最开始的例子中Day=26/11/15 Day=19/2/15可以放于同一个field中。如果是数值特征而非类别，可以直接作为一个field。
引入了field后，对于刚才的例子来说，二次项变为：
- 对于特征组合（EPSN，Nike）来说，其隐向量采用的是𝐰𝐸𝑃𝑆𝑁,𝐴和𝐰𝑁𝑖𝑘𝑒,𝑃，对于𝐰𝐸𝑃𝑆𝑁,𝐴这是因为Nike属于广告主（Advertiser）的field，而第二项𝐰𝑁𝑖𝑘𝑒,𝑃则是EPSN是广告商（Publisher）的field；
- 再举个例子，对于特征组合（EPSN，Male）来说，𝐰𝐸𝑃𝑆𝑁,𝐺 是因为Male是用户性别(Gender)的field，而第二项𝐰𝑀𝑎𝑙𝑒,𝑃是因为EPSN是广告商（Publisher）的field。
下面的图来自criteo，很好的表示了三个模型的区别：
FFM 数学公式
因此，FFM的数学公式表示为：
其中𝑓𝑖和𝑓𝑗分别代表第i个特征和第j个特征所属的field。若field有𝑓个，隐向量的长度为k，则二次项系数共有𝑑𝑓𝑘个，远多于FM模型的𝑑𝑘个。此外，隐向量和field相关，并不能像FM模型一样将二次项化简，计算的复杂度是𝑑2𝑘。
通常情况下，每个隐向量只需要学习特定field的表示，所以有𝑘𝐹𝐹𝑀≪𝑘𝐹𝑀。
好了，上面都是转自博客 『我爱机器学习』FM、FFM与DeepFM
。对于FM和FFM的关系，深入FFM原理与实践中有这么一段话：假设样本的 n 个特征属于 f 个field，那么FFM的二次项有 nf个隐向量。而在FM模型中，每一维特征的隐向量只有一个。FM可以看作FFM的特例，是把所有特征都归属到一个field时的FFM模型。根据FFM的field敏感特性，可以导出其模型方程。
说一下自己对上面这段话的理解：
在FM中我们将组合特征系数进行了矩阵分解以进行了一个降维，得到每个特征系数的一个k维隐向量，我们可以理解为将每个特征系数进行了embedding到k维空间中。而在FFM中，我们对这加入了filed信息。从FFM角度理解，在FM中我们可以所有系数的k维embedding向量看作是一个filed中的k维向量，所以一个特征x的的FM隐向量只有[v1, v2, ..., vk]，当加入filed信息后的嵌入空间信息如下：
也即之前是embedding 到同一个filed（f=1）的k维空间中，现在考虑了不同的field信息后，相当于将系数embedding到fk维空间中。
DeepFM
FM模型可以用神经网络进行表示：
模型输入𝑥=[𝑥𝑓𝑖𝑒𝑙𝑑1,𝑥𝑓𝑖𝑒𝑙𝑑2,⋯,𝑥𝑓𝑖𝑒𝑙𝑑𝑚]，这是一个d维的向量，其中𝑥𝑓𝑖𝑒𝑙𝑑𝑖即为第i个field的特征表示，如果是类别，则为one-hot编码后的向量，连续值则为它本身。
然后对每个field分别进行embedding，如下图：
值得注意的是，即使各个field的维度是不一样的，但是它们embedding后长度均为k。
接着FM层即为embedding后结果的内积和一次项的和，最后一层sigmoid后再输出结果。
看到这里，可能你感到困惑的就是embedding层，这么表示是为啥？答案是这样表示和fm模型等价！
假设第i个field 向量维度为k，embedding层的参数可以表示为一个k * m的矩阵：
其中𝑣𝑎𝑏可以理解为第a个取值embedding后的结果在隐向量的第b维。
由于进行了one-hot编码，所以对应的𝐱𝐟𝐢𝐥𝐞𝐝𝐢只有一个值为1，其余的都为0,假设第c列为1，则：
若两个field做内积，假设非0的那一列为c和d则：
其实和FM模型是一样的！
DeepFM的模型如下图：
左边就是刚才将的FM模型的神经网络表示，而右边的则为deep部分，为全连接的网络，用于挖掘高阶的交叉特征。整个模型共享embedding层，最后的结果就是把FM部分和DNN的部分做sigmoid：
参考：
- Rendle, Steffen. “Factorization machines.” Data Mining (ICDM), 2010 IEEE 10th International Conference on. IEEE, 2010.
- Juan, Yuchin, et al. “Field-aware factorization machines for CTR prediction.” Proceedings of the 10th ACM Conference on Recommender Systems. ACM, 2016.
- Guo, Huifeng, et al. “Deepfm: A factorization-machine based neural network for CTR prediction.” arXiv preprint arXiv:1703.04247 (2017).
- 深入FFM原理与实践
- Factorization Machines
- CTR Prediction: From Linear Models to Field-aware Factorization Machines
