序
广告点击预测是广告交易中非常重要的任务，例如阿里妈妈团队的核心业务就是在做这样的事情，预估广告点击率以及预估广告点击转化为购买的比率等。近年来，该Task的解决方案有很多，FM（因子分解机）是其中较为经典且被广泛使用的模型。
问题背景
传统的逻辑回归等相关变种模型中都是认为特征直接是相互独立的，但是很多情况下特征之间的依赖关系是不可忽视的，因此需要进行特征组合，但是大多数业务场景下，类别特征做完onehot后会变得相当稀疏，尤其是特征组合后，特征空间变得很大，而FM就是为了解决特征组合下数据稀疏所带来的一些列问题。
线性和多项式模型
上文说道，特征之间是存在相关性的，也就是说特征工程中需要考虑去挖掘特征之间的关联性，以此来构造新的特征。
一般的线性模型定义如下，很直观地可以看出，特征均单独出现。
引入多项式回归模型来加入特征间的关联性，例如下面的二阶多项式定义：
上述多项式模型的二阶特征的参数共有n(n-1)/2种，且任意参数间相互独立，并且在进行参数估计时发现，对于这些二次项的参数，都需要大量的非零样本来进行求解，但是很多时候特征空间是相当稀疏的，这种情况下参数的估计值变得相当不准确。
FM原理
为了解决上述特征矩阵稀疏带来的参数估计不准确的问题，FM引入了矩阵分解的思路，对交叉项的系数矩阵进行了如下分解：
上述矩阵分解的思想是：由于特征之间不是相互独立的，因此可以使用一个隐因子来串联，类似于推荐算法中，可以将一个打分矩阵分解为user矩阵和item矩阵，每个user和item都可以用一个隐向量来表示，下例中将一个user表示成一个二维向量，同时把每个movie表示为一个二维向量，两个向量的点乘就是每个用户对每个movie的评分（图片来源于网络）：
FM中采用了类似的思想，将所有的二次项系数组成一个对称矩阵W，W可被分解为V^T*V，V的第j列即为第j维特征的隐向量，因此FM模型可表示为：
其中<vi,vj>表示点乘，隐向量长度为k（k<<n），这样变换后，二次项的系数个数减少至kn个。
上式实质上是通过辅助向量Vi来对Wij进行求解，V的形式如下所示：
Wij组成的矩阵可以表示为：
可以通过限制k的大小来反应FM的表达能力。
直观上看FM的复杂度为O（kn^2），通过化简为下式，可以优化至O（kn）
上式的推导过程如下，之所以是1/2是因为W矩阵是一个对称矩阵，只需计算其一般的值即可。vj,f表示的是隐向量vj的第f个元素
