FM：Factorization Machines

... We introduce Factorization Machines (FM) which are a new model class that combines the advantages of Support Vector Machines (SVM) with factorization models ... In contrast to SVMs, FMs model all interactions between variables using factorized parameters. Thus they are able to estimate interactions even in problems with huge sparsity (like recommender systems) where SVMs fail...

TL;DR，按我个人的理解就是：

1. 这是一种新的模型类型，可以用作任意Real-Value Vector的分类，跟LR/SVM一样
2. 它可以拿来对不同变量之间的Interaction建模（比如不同Feature之间的相关性），这点跟带kernel的SVM类似；它胜过LR的也是这点，因为LR只是一个线性模型
3. 它胜过SVM的地方在于，它使用了"factorization"（简单来说，理解为矩阵分解？）来进行建模，这就使得它可以用于非常稀疏的Features，而SVM更适合用于Dense Feature，在Sparse Feature上表现并不好

下面进入技术细节

模型结构

我们先从Logistic Regression出发，回顾一下LR的Score Function

基本就是一个线性模型，对输入Feautre X的每一个纬度有一个参数w_i。好处是非常简单，非常容易Scale Up，得到的泛化能力一般都还挺不错，因此在工业界得到广泛应用；坏处就是建模能力有限，毕竟只是一个线性模型。

那么，下面是FM的Score Function

这里只是二阶的情况（二阶的意思是对变量两两之间关系建模，三阶或更高就是对三个或更多个变量之间的关系进行建模），也是一般实际场景所用的模型。可以看到，跟LR相比，多出来一项是

，其中

是参数矩阵

中的一行，而V是一个 N x k 的矩阵。也就是说，对X中的每一个变量，我们会用一个k维的向量（记住是一个向量，这很重要，后面会提到为什么）来建模，然后每两个变量之间的Interaction，就用这两个k维向量的内积来模拟。

Scalability

前面讲到LR的优势之一是非常Scalable，所以在工业界得到广泛应用——工业界一般有大量数据，但是计算资源有限啊，而且对实时性要求非常高，所以很多很酷炫，理论效果很好的模型反而得不到重用，就是因为Scalability的问题。前面看到，LR是线性的，基本是O(N)的复杂度；FM加了一个新的项之后，新加的那项看起来似乎需要

的复杂度，这似乎是不可忍受的复杂度，那为什么FM还能得到广泛应用呢？

主要原因就是，原作者通过一个数学Trick，把新加项的计算复杂度降到了O(kN) (k是可以自己选择的参数，一般会远远远远小于N，所以基本就相当于O(N)了）。直接上原论文的图，不感兴趣的可以跳过：

得到这个牛逼的公式之后就可以直接上梯度下降了：）

深究与SVM的优劣——为什么这个方法在Sparse Data下可以Work？

我们把上面FM的Score Function和一个带有多项式Kernel（Degree=2）的SVM比较。我们知道，简化来看，带Kernel的SVM可以看作先把输入X投影到另外一个特征空间，再做线性分类的算法。一个二项式kernel的SVM，相当于对输入Feature做了如下的变换：

那么Score Function就是：

可以看到基本上最大的区别就在于模拟变量两两Interaction的一项：在SVM里面，对x_i 和x_j的Interaction，以及x_i和x_k之间的interaction的建模，也就是

和

，是相互独立的参数；但是在FM里面，这两者互不独立，因为

和

都依赖于

。这点看似减少了模型的自由度，但是Sparse Feature的情况下发挥出了巨大的作用（以下为个人理解）：

对于SVM来说，

必须在有足够多的满足

样本存在的情况下，才能得到很好的训练。但是在输入稀疏的情况下，在输入特征X里面大部分的

值都是0，更不必提

同时不为0了。所以SVM在这种情况下不能得到很好的训练。

反观FM，尽管要训练

也依赖于

，但是好处是，所有其他非0的

都会成为梯度的一部分，这样对于

的训练就有明显更多的训练数据，可以更好地训练出合适的参数。

同样的道理，我们平常在工业界里面常常采用的N-Gram Logistic Regression （人为对输入特征对二项式的变换，再把得到之后的特征拿LR进行训练），也由于同样的问题，无法和FM在效果上媲美。

值得注意的是，这个特性是FM是优势也是它的弊病。在输入特征比较稠密的情况下，其实FM的效果应该是并不如SVM的，因为SVM的模型自由度更高。

总结

FM作为一个通用的模型，在Scalability上可以和LR媲美，又可以拿来对变量之间的Interaction建模，在工业界中被广泛应用于推荐系统，但理论上也可以应用于一般的分类问题。

Steffen Rendle. Factorization Machines, ICDM (CCF-B), 出自大阪大学。2010年。