Press "Enter" to skip to content

FM 理论与实践

背景

 

FM 算法( FactorMachine ),又叫因子分解机算法。在推荐系统和点击率预估( CTR 预估)中, FM 算法有很广泛的应用。这两个场景的实质都是根据所提供的一些特征信息来判断用户是否会有点击行为,或者说点击的概率。在推荐系统和 CTR 预估任务中,通常把 LR 作为 baseline 。

 

如果直接利用所提供的特征信息,线性模型将是最简单直接的方法。如下图所示, xi 就是某个特征值,线性模型需要为每一个特征值学习一个权重 wi ,最终的模型预测值就是所有的特征值乘以这个权重,加起来求和。公式如下:

 

 

如果是逻辑回归( LR ),需要在上面求和的基础上套一个 sigmoid 函数,也就是图中的黄色曲线。直观上很好理解,使用 sigmoid 将线性模型的取值范围压缩到 0-1 ,这样就可以很容易的判断是正面的结果还是负面的结果(对应着点击与不点击)。

 

 

在使用 LR 解决推荐和 CTR 预估问题中,常常对数据进行大量的特征工程,构造出大量的单特征,编码后送入 LR 模型,从而预估点击率。这种线性模型的优势在于,运算速度快,可解释性强,在特征挖掘完备且训练数据充分的前提下,能够达到一定的精度。但线性模型的缺点也很多,如:

 

 

模型并未考虑到特征之间的组合关系。而特征交叉组合在推荐系统和 CTR 任务中往往能够更好地提升模型效果。

 

对于类别型( categorical )特征进行 one-hot 编码,具有高度稀疏性,一方面会带来维度灾难问题,另一方面会由于特征高度稀疏,导致模型无法充分利用这些稀疏特征。

 

 

要使用特征两两交叉组合,最直观的做法就是直接引入两两组合特征融入到模型中,在线性模型的基础上得到,可以使用下面的公式表示:

 

然而这样有两个比较大的问题,第一,这样处理组合特征的参数个数为 n(n-1)/2 ,如果 n=1000 (对原始数据连续特征离散化,并且 one-hot 编码,特征很容易达到此量级),那幺参数个数将达到 50w ,参数量巨大;第二,由于对原始数据的 one-hot 处理,数据将特别稀疏,满足 xi , xj 都不等于 0 的个数很少,这样就很难去学习到参数 wij ,导致组合特征的泛化能力差(详细解释:由于 xi 和 xj 大部分为 0 ,所以 xi*xj 也会大部分为 0 ,假设 X=xi*xj ,则,又因为 X=0 ,所以,梯度为 0 ,参数无法更新)。

 

导致这种情况出现的根源在于:特征过于稀疏。需要找到一种方法,使得 wij 的求解不受特征稀疏性的影响。

 

FM算法

 

FM 以特征组合为切入点,在线性模型的基础上引入特征交叉项,弥补了一般线性模型未考虑特征间关系的缺憾。 FM ( Factorization Machine )模型对每个特征学习一个隐向量,由两个隐向量的内积表示两个特征交叉的权重,公式如下:

 

FM 算法的本质是利用近似矩阵分解,将参数权重矩阵 W 分解成两个向量相乘,从而将参数从平方级别减少到线性级别。

 

 

 

vi 和 vj 分别是对于 xi 这个特征来说它会学到一个 embedding 向量,特征组合权重是通过两个单特征各自的 embedding 的内积呈现的,因为它内积就是个数值,可以代表它的权重,这就是 FM 算法。

 

FM 算法最核心的就是后面这个交叉项,为了计算方便,对该交叉项进行化简得到:

 

 

按照这种化简之后, FM 的最终形式如下:

 

 

这样化简之后,计算就会简单多了,改写前,计算 y 的复杂度为,改写后计算 y 的复杂度变为,大大提高了模型预测的速度。

 

FM 算法自被提出以来,在推荐系统、 CTR 和广告等相关领域取得了巨大突破,由于 FM 优越的性能表现,后续出现了一系列 FM 变种模型(如 FFM 、 FNN 、 AFM 、 DeepFM 、 xDeepFM 等),从浅层模型到深度推荐模型中都有 FM 的影子。

 

FM算法求解

 

这里阐述如何求解 FM 的模型参数。

 

求解 FM 参数的过程可以采用梯度下降法,为了对参数进行梯度下降更新,需要计算模型各参数的梯度表达式。

 

当参数是 w0 时,

 

 

当参数是 wi 时,

 

 

当参数为 vif 时,只需要关注模型的高阶项,此时,其余无关的参数可以看作常数:

 

 

其中:

 

 

 

 

则:

 

 

因此可以得到:

 

 

综上,最终模型各参数的梯度表达式如下:

 

 

性能分析

 

FM 进行推断的时间复杂度为 O(kn) 。依据参数的梯度表达式

 

 

,与 i 无关,在参数更新时可以首先将所有的计算出来,复杂度为 O(kn) ,后续更新所有参数的时间复杂度均为 O(1) ,参数量为 1 + k + kn ,所以最终训练的时间复杂度同样为 O(kn) ,其中 n 为特征数, k 为隐向量维数。

 

FM 训练与预测的时间复杂度均为 O(kn) ,是一种十分高效的模型。

 

FM 缺点

 

每个特征只引入了一个隐向量,不同类型特征之间交叉没有区分性。 FFM 模型正是以这一点作为切入进行改进。

 

实践

 

FM 既可以应用在回归任务,也可以应用在分类任务。在分类任务中只需在上面的公式最外层套上 sigmoid 函数即可,上述解析都是基于回归任务来进行推导的。

 

代码请参考: https://github.com/jpegbert/code_study/tree/master/FM

 

注:

 

 

对于回归任务,损失函数可以用 MSE ,对于分类任务损失函数可以用交叉熵( CrossEntry )

 

虽然 FM 可以应用于任意数值类型的数据上,但是需要注意对输入特征数值进行预处理。优先进行特征归一化,其次再进行样本归一化

 

FM 不仅可以用于 rank 阶段,同时可以用于向量召回

 

 

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注