[深度学习] FM & FFM 算法基本原理

大家好,又见面了,我是你们的朋友全栈君。

在推荐系统和计算广告业务中,点击率CTR(click-through rate)和转化率CVR(conversion rate)是衡量流量转化的两个关键指标。准确的估计CTR、CVR对于提高流量的价值,增加广告及电商收入有重要的指导作用。

[深度学习] FM & FFM 算法基本原理

无论使用什么类型的模型,点击率这个命题可以被归纳到二元分类的问题,我们通过单个个体的特征,计算出对于某个内容,是否点击了,点击了就是1,没点击就是0。对于任何二元分类的问题,最后我们都可以归结到逻辑回归上面。

  • 早期的人工特征工程 + LR(Logistic Regression):这个方式需要大量的人工处理,不仅需要对业务和行业有所了解,对于算法的经验要求也十分的高。
  • GBDT(Gradient Boosting Decision Tree) + LR:提升树短时这方面的第二个里程碑,虽然也需要大量的人工处理,但是由于其的可解释性和提升树对于假例的权重提升,使得计算准确度有了很大的提高。
  • FM-FFM:FM和FFM模型是最近几年提出的模型,并且在近年来表现突出,分别在由Criteo和Avazu举办的CTR预测竞赛中夺得冠军,使得到目前为止,还都是以此为主的主要模型占据主导位置。
  • Embedding模型可以理解为FFM的一个变体。

一、LR模型

LR是一种宽而不深的结构,所有的特征直接作用在最后的输出结果上。模型优点是简单、可控性好,但是效果的好坏直接取决于特征工程的程度,需要非常精细的连续型、离散型、时间型等特征处理及特征组合。通常通过正则化等方式控制过拟合。

[深度学习] FM & FFM 算法基本原理
[深度学习] FM & FFM 算法基本原理

二、FM模型

因子分解机(Factorization Machine, FM)是由Steffen Rendle提出的一种基于矩阵分解的机器学习算法,其主要用于解决数据稀疏的业务场景(如推荐业务),特征怎样组合的问题。

paper指出FM与SVM相比,有如下优势:

  1. FM可以实现非常稀疏数据参数估计,而SVM会效果很差,因为训出的SVM模型会面临较高的bias;
  2. FMs拥有线性的复杂度, 可以通过 primal 来优化而不依赖于像SVM的支持向量机;

FM(Factorization Machines,因子分解机),在数据非常稀疏的情况下,依然能估计出可靠的参数进行预测。与传统的简单线性模型不同的是,因子分解机考虑了特征间的交叉,对所有嵌套变量交互进行建模(类似于SVM中的核函数),因此在推荐系统和计算广告领域关注的点击率CTR(click-through rate)和转化率CVR(conversion rate)两项指标上有着良好的表现。此外,FM的模型还具有可以用线性时间来计算,以及能够与许多先进的协同过滤方法相融合等优点。

线性模型建模为如下公式:

[深度学习] FM & FFM 算法基本原理

对于二分类问题则需要在上式的基础上添加一个对数几率回归:

[深度学习] FM & FFM 算法基本原理

线性模型的优点是简单、方便、易于求解,但缺点在于线性模型中假设不同特征之间是独立的,即特征 不会相互影响。为了解决简单线性模型无法学得特征间交叉影响的问题,SVM通过引入核函数来实现特征的交叉,实际上和多项式模型是一样的,这里以只考虑两个特征交叉的二阶多项式模型为例:

[深度学习] FM & FFM 算法基本原理

上式也可以称为Poly2(degree-2 poly-nomial mappings)模型

[深度学习] FM & FFM 算法基本原理

模型覆盖了LR的宽模型结构,同时也引入了交叉特征,增加模型的非线性,提升模型容量,能捕捉更多的信息. 从公式来看,模型前半部分就是普通的LR线性组合,后半部分的交叉项即特征的组合。单从模型表达能力上来看,FM的表达能力是强于LR的,至少不会比LR弱,当交叉项参数全为0时退化为普通的LR模型。

多项式模型的问题在于二阶项的参数过多,设特征维数为 n,那么二阶项的参数数目为 n(n-1)/2。

任意两个参数都是独立的。然而,在数据稀疏性普遍存在的实际应用场景中,二次项参数的训练是很困难的.

对于广告点击率预估问题,由于存在大量id特征,导致 n 可能为 维,这样一来,模型参数的量级为 ,这比样本量多得多!这导致只有极少数的二阶组合模式才能在样本中找到,而绝大多数模式在样本中找不到,因而模型无法学出对应的权重。

为此,Rendle于2010年提出FM模型,它能很好的求解上式,其特点如下:

  • FM模型可以在非常稀疏的情况下进行参数估计
  • FM模型是线性时间复杂度的,可以直接使用原问题进行求解,而且不用像SVM一样依赖支持向量。
  • FM模型是一个通用的模型,其训练数据的特征取值可以是任意实数。而其它最先进的分解模型对输入数据有严格的限制。FMs可以模拟MF、SVD++、PITF或FPMC模型。

FM模型原理

在矩阵分解,一个rating可以分解为user矩阵和item矩阵,如下图所示:

[深度学习] FM & FFM 算法基本原理

分解后得到user和item矩阵的维度分别为nk和km,(k一般由用户指定),相比原来的rating矩阵,空间占用得到降低,并且分解后的user矩阵暗含着user偏好,Item矩阵暗含着item的属性,而user矩阵乘上item矩阵就是rating矩阵中用户对item的评分。因此,参考矩阵分解的过程,FM模型也将上式的二次项参数

进行分解:

[深度学习] FM & FFM 算法基本原理
[深度学习] FM & FFM 算法基本原理
[深度学习] FM & FFM 算法基本原理

通过上式得变换,因子分解机的二次项的复杂度简化到O(kn)。

[深度学习] FM & FFM 算法基本原理

FM例子

[深度学习] FM & FFM 算法基本原理

上图是一个人造的广告CTR的数据例子,代表的意思是在某个网站(Publisher)上刊登一则广告(Advertiser),某个用户(用户性别特征Gender)是否会点击某条广告的数据。

这个例子中假设包含三个特征域(Field):

网站Publisher(可能的特征值是ESPN、Vogue、NBC)、

广告Advertiser(可能的特征值是Nike、Adidas、Gucci)

性别Gender(可能的特征值是Male、Female)。

由这个例子可以看出组合特征的重要性:

如果在体育网站ESPN上发布Nike的广告,那么100次展现,80次会被点击,而20次不会被点击。

意味着组合特征(Publisher=”ESPN” and Advertiser=”Nike”)是个很强的预测用户是否点击的二阶组合特征。

[深度学习] FM & FFM 算法基本原理

FM模型在做二阶特征组合的时候,对于每个二阶组合特征的权重,是根据对应两个特征的Embedding向量内积,来作为这个组合特征重要性的指示。当训练好FM模型后,每个特征都可以学会一个特征embedding向量,如上图所示。当做预测的时候,比如我们接收到上面例子的数据,需要预测用户是否会点击这条广告,则对三个特征做两两组合,每个组合特征的权重,可以根据两个对应的特征embedding内积求得,对所有组合特征求和后,套接Sigmoid函数即可做出二分类预测。

三、FFM模型

FFM(Field Factorization Machine)是在FM的基础上引入了“场(Field)”的概念而形成的新模型。在FM中的特征 与其他特征的交叉时,特征 使用的都是同一个隐向量 。而FFM将特征按照事先的规则分为多个场(Field),特征属于某个特定的场F。每个特征将被映射为多个隐向量 ,每个隐向量对应一个场。当两个特征 ,组合时,用对方对应的场对应的隐向量做内积。

[深度学习] FM & FFM 算法基本原理

FFM例子

对于FM模型来说,每个特征学会唯一的一个特征embedding向量。注意,和FFM的最大不同逐渐出现,为了更容易向FFM模型理解过渡,我们可以这么理解FM模型中的某个特征的embedding,我们拿ESPN这个特征作为例子,当这个特征和其它特征域的某个特征进行二阶特征组合的时候,不论哪个特征域的特征和ESPN这个特征进行组合,ESPN这个特征都反复使用同一个特征embedding去做内积。也可以理解为ESPN这个特征在和不同特征域特征进行组合的时候,共享了同一个特征向量。

沿着这个思路思考,我会问出一个问题:我们可以改进下FM模型吗?ESPN这个特征和不同特征域特征进行组合的时候,可以使用不同的特征向量吗?

[深度学习] FM & FFM 算法基本原理

既然FM模型的某个特征,在和任意其它特征域的特征进行组合求权重的时候,共享了同一个特征向量。那么,如果我们把这个事情做地更细致些,比如ESPN这个特征,当它和Nike(所属特征域Advertiser)组合的时候用一个特征embedding向量,而当它和Male(所属特征域Gendor)组合的时候,使用另外一个特征embedding向量,这样是否在描述特征组合的时候更细腻一些?

也就是说,当ESPN这个特征(属于Publisher网站这个域)和属于广告Advertiser这个域的特征进行组合的时候,用一个特征embedding;和属于性别Gender这个特征域的特征进行组合的时候,用另外一个特征embedding。

这意味着,如果有F个特征域,那么每个特征由FM模型的一个k维特征embedding,拓展成了(F-1)个k维特征embedding。之所以是F-1,而不是F,是因为特征不和自己组合,所以不用考虑自己。

[深度学习] FM & FFM 算法基本原理

上图展示了这个过程,因为这个例子有三个特征域,所以ESPN(属于Publisher网站这个域站)有两个特征embedding,

当和Nike特征组合的时候,用的是针对网站Advertisor这个特征域的embedding去做内积;

而当和Male这个特征组合的时候,则用的是针对性别Gender这个特征域的embedding去做内积。

同理,Nike和Male这两个特征也是根据和它组合特征所属特征域的不同,采用不同的特征向量去做内积。

而两两特征组合这个事情的做法,FFM和FM则是完全相同的,区别就是每个特征对应的特征embedding个数不同。

FM每个特征只有一个共享的embedding向量,

而对于FFM的一个特征,则有(F-1)个特征embedding向量,用于和不同的特征域特征组合时使用。

从上面的模型演化过程,我们可以推出,假设模型具有n个特征,那么FM模型的参数量是n*k(暂时忽略掉一阶特征的参数),其中k是embedding特征向量大小。

而FFM模型的参数量呢?因为每个特征具有(F-1)个k维特征向量,所以它的模型参数量是(F-1)nk,也就是说参数量比FM模型扩充了(F-1)倍。

这意味着,如果我们的任务有100个特征域,FFM模型的参数量就是FM模型的大约100倍。

这其实是很恐怖的,因为现实任务中,特征数量n是个很大的数值,特征域几十上百也很常见。

正因为FFM模型参数量太大,所以在训练FFM模型的时候,很容易过拟合,需要采取早停等防止过拟合的手段。而根据经验,FFM模型的k值可以取得小一些,一般在几千万训练数据规模下,取8到10能取得较好的效果,当然,k具体取哪个数值,这其实跟具体训练数据规模大小有关系,理论上,训练数据集合越大,越不容易过拟合,这个k值可以设置得越大些。

下面的图来很好的表示了三个模型的区别:

[深度学习] FM & FFM 算法基本原理
[深度学习] FM & FFM 算法基本原理
[深度学习] FM & FFM 算法基本原理

参考:

  1. https://zhuanlan.zhihu.com/p/97886466
  2. https://www.biaodianfu.com/ctr-fm-ffm-deepfm.html

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/133460.html原文链接:https://javaforall.cn