FM因式分解机

FM介绍

FM解决点击率预测问题 ，相对于线性回归FM模型引入二阶特征组合。
FM对于每个特征，学习一个大小为k的一维向量，两个特征 xi和 xj 的特征组合的权重值，通过特征对应的向量 vi和 vj的内积来表示。
这本质上是在对特征进行embedding化表征，和目前非常常见的各种实体embedding本质思想是一脉相承的。

FM与MF

MF模型可以看作是FM模型的特例，MF可以被认为是只有User ID 和Item ID这两个特征Fields的FM模型，MF将这两类特征通过矩阵分解，来达到将这两类特征embedding化表达的目的。而FM则可以看作是MF模型的进一步拓展，除了User ID和Item ID这两类特征外，很多其它类型的特征，都可以进一步融入FM模型里，它将所有这些特征转化为embedding低维向量表达，并计算任意两个特征embedding的内积，就是特征组合的权重。

FM原理

假设一个电影评分系统，根据用户和电影的特征，预测用户对电影的评分。

系统记录了用户（U）在特定时间（t）对电影（i）的评分（r），评分为1，2，3，4，5。

给定一个例子：

评分是label，用户id、电影id、评分时间是特征。由于用户id和电影id是categorical类型的，需要经过独热编码（One-Hot Encoding）转换成数值型特征。因为是categorical特征，所以经过one-hot编码以后，导致样本数据变得很稀疏。

下图显示了从S构建的例子：

每行表示目标yi 与其对应的特征向量 xi，蓝色区域表示了用户变量，红色区域表示了电影变量，黄色区域表示了其他隐含的变量，进行了归一化，绿色区域表示一个月内的投票时间，棕色区域表示了用户上一个评分的电影，最右边的区域是评分。
对特征进行组合
普通的线性模型，我们都是将各个特征独立考虑的，并没有考虑到特征与特征之间的相互关系。但实际上，特征之间可能具有一定的关联。以新闻推荐为例，一般男性用户看军事新闻多，而女性用户喜欢情感类新闻，那么可以看出性别与新闻的频道有一定的关联性，如果能找出这类的特征，是非常有意义的。

为了简单起见，我们只考虑二阶交叉的情况，具体的模型如下：
其中， n代表样本的特征数量， xi 是第i个特征的值，w0、 wi 、wij 是模型参数，只有当 xi 与 yi 都不为0时，交叉才有意义。
在数据稀疏的情况下，满足交叉项不为0的样本将非常少，当训练样本不足时，很容易导致参数 [公式] 训练不充分而不准确，最终影响模型的效果。
交叉项参数的训练问题可以用矩阵分解来近似解决，有下面的公式。

其中:

对任意正定矩阵W ，只要 k足够大，就存在矩阵W，使得 W=VVT。然而在数据稀疏的情况下，应该选择较小的k，因为没有足够的数据来估计wij 。限制k的大小提高了模型更好的泛化能力。
为什么说可以提高模型的泛化能力呢？

以上述电影评分系统为例，假设我们要计算用户 A与电影ST的交叉项，很显然，训练数据里没有这种情况，这样会导致 Wa,st = 0 ，但是我们可以近似计算出Va,Vst的内积。首先，用户B和C 有相似的向量 Vb 和 Vc，因为他们对SW 的预测评分比较相似， 所以Vb,Vsw的内积和 Vc,Vsw的内积是相似的。用户A和C 有不同的向量，因为对TI和SW的预测评分完全不同。接下来，ST和 SW 的向量可能相似，因为用户B对这两部电影的评分也相似。最后可以看出， Va,Vst的内积与 Va,Vsw的内积是相似的。

FM求解

通过公式变换，可以减少到线性复杂度

学习参数

参考链接：
1、https://zhuanlan.zhihu.com/p/50426292
2、https://www.jianshu.com/p/152ae633fb00