转《FM,FFM,DeepFM》
本文仅为记录学习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