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就是矩阵拆解的规模值，利用Vi*Vj.T对交叉项的系数wij进行估计,
及
则
这边需要注意一点，k理论上讲，越大越能强化拟合的能力，但是实际在运算过程中，一来受限于计算能力，二来受限于数据量，过大的k只会带来过拟合的问题。我实测了40w作用的数据，观察到k值在6-8左右，valid集合数据拟合效果最优，仅供参考
很明显，上面这么多未知数：1+n是线性未知数个数，nfeature是组合特征的未知数个数，常规求解的效率可想而知。但是看到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属于{-1，1}
这边的求导，我算了一个小时都没搞出来，等哪天有空了，再仔细的去算一下，最后的迭代形式如下：
η是常规的速率，V是初始均匀分布即可
代码实现
我这边完成了FM的代码实现，详细见我的github：fm代码
为了方便不想看细节，只想撸代码的同学，我打包上传到了pypi，你只需要pip install Fsfm即可体验
至于ffm，我下午实在没写出来，对不起彭老师，给你教的数分丢脸了，后续看什么时候有空再研究一下。
最后，着重提示，本文很多思路很解析都参考的Yu-Chin Juan的源代码，附上github地址，欢迎去关注原作者的内容，感谢大神带路，谢谢大家阅读。
欢迎大家关注我的个人bolg，更多代码内容欢迎follow我的个人Github，如果有任何算法、代码疑问都欢迎通过公众号发消息给我哦。
