FM理论解析及应用


FM的产生背景

我其实没有做过很多CTR预估的事情,但是我在工作中常常遇到CRM流失预估、订单预估这些依赖于特征工程的事情,其中就涉及到特征的组合问题。

one-hot过程

在feature选取过程中,不可避免的会出现,学历这种高中、大学、研究生等多分类的feature,在实际应用中,我们对单个feature需要进行一种one hot过程,就是将原来的学历拆解为 是否为高中,是否为大学,注意,可以不用加是否为研究生一列,因为是否为高中,是否为大学的两列已经可以推导这个用户是否为研究生,加上这一列有时候反而会共线性。但是这样做,看起来没什么问题,想想看要是100个这样的特征,每个特征有100个这样单独的feature value的话,整体数据将是一个非常庞大的稀疏矩阵,无论是计算还是分析都是会存在巨大的问题的,所以看看我们能不能组合一些特征降低维度。

什么叫做组合问题

现在有一组数据,其中特征包含性别(男女),学历(高中,大学,研究生),想要判断这两个feature对是否对化妆品感谢兴趣。单独的观察性别这一栏,发现有一定相关性,但是比较弱,并不是所有的女性都对化妆品感兴趣;单独的观察学历这一栏也发现,学历与对化妆品感兴趣的程度并没有显著的相关性。其实,我们可以从自己的感知理解,首先,数据中女生可能比男生对化妆品更感兴趣,但是女生数据中存在大量的高中生,相对于高中生而言,大学生和研究生可能对化妆品更加感兴趣一点,所以原来的两个feature:性别,学历就组合成了是否为性别女+学历大于高中一个feature,这就是特征组合的过程。如果feature总个数少还可以,要是要有上千上万个,光两两组和就有n*(n-1)/2种可能,所以我们需要想一个其他办法。

组合特征后的表达形式

首先,我们都知道一般的线性模型为:

为了考虑组合特征的作用,我们采用多项式来代表,形如特征xi与xj的组合用xixj表示,具体的表达式如下:

其中,wij为组合特征xixj的权重,n表示样本的feature个数,xi为第i个feature。

方程定义完成了,下面就要开始数学定义

对每一个特征xi引入辅助向量Vi=(vi1,vi2,…vik),这边的k就是矩阵拆解的规模值,利用ViVj.T对交叉项的系数wij进行估计,



这边需要注意一点,k理论上讲,越大越能强化拟合的能力,但是实际在运算过程中,一来受限于计算能力,二来受限于数据量,过大的k只会带来过拟合的问题。我实测了40w左右的数据,观察到k值在6-8左右,valid集合数据拟合效果最优,仅供参考

很明显,上面这么多未知数:1+n是线性未知数个数,nxfeature是组合特征的未知数个数,常规求解的效率可想而知。但是看到xixj这样的形式,我们很容易联想到:2ab = (a+b)^2 -a^2 -b^2,所以在解决这个wij、xi、xj点积的问题上,我们采用了:1/2 * ( (a+b+c)^2 - a^2 - b^2 - c^2)的方式

下面让我们来解这个式子

这边需要一点导数功底,我们先来看对w0也就是bias求导,这个毫无意外,梯度为1;再对wi求导,这个也很简单,xi即可,这个也很简单,少许繁琐的就是wij求导,让我来仔细看看:

ok,我知道我的字很丑,别说话,看问题,所以我们可以总结为下面这个网上到处都有的式子:

这个式子就是上面这么来的。
把上面的那个点积形式代入求解及为:

引申一个FFM概念

在FM模型中,每一个特征会对应一个隐变量,但在FFM模型中,认为应该将特征分为多个field,每个特征对应每个field分别有一个隐变量。

举个例子,我们的样本有3种类型的字段:qualifications, age, gender,分别可以代表学历,年龄段,性别。其中qualifications有3种数据,age有5种数据,gender有男女2种,经过one-hot编码以后,每个样本有7个特征,其中只有3个特征非空。
如果使用FM模型,则7个特征,每个特征对应一个隐变量。
如果使用FFM模型,则7个特征,每个特征对应3个隐变量,即每个类型对应一个隐变量,及对应qualifications, age, gender各占一个。

我看了Yu-Chin Juan实现了一个C++版的FFM模型的源码,倒过来想他的表达式应该是这样的:

其他模块都与fm差不多,主要看Vj1f2Vj2f1这个东西。我们假设j1特征属于f1这个field,j2特征属于f2这个feild,则Vj1f2表示j1这个特征对应j2所属的field的隐变量。很恶心的解释,通俗的来讲就是,性别为女与学历这个field的组合有个隐变量,性别女与年龄这个field的组合又有一个不一样的隐变量,而却不考虑到底是什么学历是啥,年龄具体到什么细节。
Yu-Chin Juan大神在实际写code的过程中,干掉来常数和一次项,可能是为了方便计算,保留的如下:

整理的最优化损失函数如下:

前面为l2正则,后面为交互熵形式,我们看到了y*Φ(V,x)这个及其类似hinge loss里面的1−t⋅y部分,所以注意这边的y属于{-1,1}
这边的求导,我算了一个小时都没搞出来,等哪天有空了,再仔细的去算一下,去翻了原论文,最后的迭代形式如下:

η是常规的速率,V是初始均匀分布即可

代码实现

我这边完成了FM的代码实现,详细见我的github:fm代码
为了方便不想看细节,只想撸代码的同学,我打包上传到了pypi,你只需要pip install Fsfm即可体验
至于ffm,我下午实在没写出来,对不起彭老师,丢脸了,后续看什么时候有空再研究一下。

最后,着重提示,本文很多思路很解析都参考的Yu-Chin Juan的源代码,附上github地址,欢迎去关注原作者的内容,感谢大神带路,谢谢大家阅读。

打赏的大佬可以联系我,赠送超赞的算法资料