Factorization Machines
简介
简单的说FM（Factorization Machine）是一类自动特征组合算法。相比于传统的SVM、LR等模型，FM可以自动的进行特征的组合运算用以替代一部分人工特征工程的工作，并且计算量可控对于海量输入特征仍然可以尝试使用这个方法。另一方面，对于稀疏特征SVM等模型相对难以取得特别好的效果，而FM应用分解的方法可以很好的处理稀疏的输入。
相比较于其他的分解方法（MF，PMF，SVD等等）FM是一个更加通用化的特征组合与分解手段，其可以应用在多个场景下。
总的来说FM有如下几个优势：
- 适用于极端稀疏的输入
- 线性的计算复杂度支持海量数据训练
- 适用范围广
特征组合
在介绍的具体方法之前有必要简单的介绍一下特征组合，因为FM就是在特征组合的方法上做了一些工作。
假设输入的数据有$N$个维度：\(X_1...X_n\)，当输入一个传统的线性模型的时候会得到一个形式类似\(F = W_1X_1 + W_2X_2 + ... + W_nX_n + b\)这样一个式子，也就是说最终的结果由所有输入维度乘上一个权重来得到。那么考虑一种情况，如果输出的信息需要同时考虑两个维度同时存在的情况，那么这样的线性加权和的方式就不容易很好的表达了（举例：男 + 啤酒；女 + 奶粉）。因此容易的想到可以输入特征\(X_iX_j\)的乘积作为加权和的输入项，就可以表达两个维度同时存在的情况了。
以上就是一个特征组合的简单例子，组合的方式有很多种，组合的项也可以有很多项，但是万变不离其宗，其宗旨就是解决联合特征表达的问题。
那么考虑如果$N$特别大的时候，组合特征将会非常的大：$N^d$，而且如果输入的数据非常的稀疏那么组合之后的特征将会呈指数级的增加稀疏程度，非常不利于传统模型的训练。举例：考虑如上的线性求和公式，只有当对应的输入项\(X_i\)出现足够多次数的时候\(W_i\)才能计算得到一个相对合理的数值。考虑一种极端情况假设\(X_i\)从来没出现过，那么$W_i$有可能被初始化为0（完全无效果）或者一个随机数（随机效果），这两者都不是我们想看到的。
接下来我们看FM是如何解决这个问题的。
方法
双特征组合
我们先只考虑组合两个特征的情况，这种情况非常的直截了当并且可以推广。从上文的分析中可知假设我们组合了全部特征，那么输入就变成了$N^2$这个量级的那么对于组合之后的特征的$W_{ij}$训练就是一个需要解决的问题。FM通过矩阵分解的方式将\(W_{ij}\)分解为\(V_i \cdot V_j\)的方式进行了降维，这也是这个方法叫Factorization的原因。
因此FM在双特征组合情况下的公式为：\(F(x) = W_0 + \sum_{i=1}^{N}W_iX_i + \sum_{i=1}^{N}\sum_{j=i+1}^{N} (V_i \cdot V_j )X_iX_j\)其中$V$是一个长度为$K$的向量。
这个式子就非常的直观了，其使用了单特征和双特征组合来建立模型。从这个式子的形式来看其计算复杂度是$O(N^2)$，但是实际上其可以化简为$O(N)$的复杂度从而可以适应于非常大规模的输入特征：
\[\sum_{i=1}^{N}\sum_{j=i+1}^{N} (V_i \cdot V_j )X_iX_j = \frac {1} {2} (\sum_{i=1}^{N} \sum_{j=1}^{N} (V_i \cdot V_j)X_iX_j - \sum_{i=1}^{N} (V_i \cdot V_i) X_i^2 )\] \[=\frac {1} {2} (\sum_{i=1}^{N} \sum_{j=1}^{N} \sum_{k=1}^{K} v_{ik}v_{jk}X_iX_j - \sum_{i=1}^{N} \sum_{k=1}^{K} v_{ik}^2X_i^2 )\] \[=\frac {1} {2} \sum_{k=1}^{K} ((\sum_{i=1}^{N} v_{ik}X_i)^2 - \sum_{i=1}^{N} v_{ik}^2X_i^2)\]应用以上最后一个式子的简化方法后可以只遍历一次特征就计算出最终的结果。
训练方法
训练方法可以使用梯度下降以及其各种优化方法，损失函数可以根据不同的应用进行不同的选择。那么这里列出各种损失函数求偏导之后都会用的$F(x)$的偏导数。
- \(\frac {\partial F(x)} {\partial W_0} = 1\)
- \(\frac {\partial F(x)} {\partial W_i} = X_i\)
- \(\frac {\partial F(x)} {\partial v_{ik}} = \frac {X_i} {2} \sum_{j=1}^{N} v_{jk}x_j - x_i^2v_{ik}\) 其中\(\sum_{j=1}^{N} v_{jk}x_j\)与某个具体的$x_i$无关，因此可以预先计算好。 PS：此处和论文原文计算的不一致，原文中第一项没有\(\frac {1} {2}\)
多特征组合
将双特征组合的公式推广到$N$个特征的组合就得到了多特征组合公式：
\[F(x) = W_0 + \sum_{i=1}^{N}W_i + \sum_{l=2}^{d}\sum_{i_1=1}^{N}\sum_{I_2=I_1+1}^{N}...\sum_{i_l = i_{l-1}+1}^{N} (\prod_{j=1}^{l}X_{i_j})(\sum_{k=1}^{K_l}V^{(l)}_{i_j}k)\]这个式子看起来很复杂其实原理和双特征组合是一样的，只不过用了更一般化的形式化表达方式而已。基于同样的简化方法上式可以简化为一个$O(N)$复杂度的式子，只是简化的过程就很长了，这里就不赘述了。
FMs vs *
论文最后把FMs与各种其他算法进行了一下对比，这里简单说一下：
- FMs vs SVM（Linear Kernel）：显然的线性核函数的SVM无法捕捉组合特征信息
- FMs vs SVM（Polynomial Kernel）：多项式核函数的SVM是包含了双特征组合的，但是SVM中每个特征组合的权重是独立训练的，因此会受到稀疏数据的巨大影响。
- FMs vs MF：如果把MF中的U/I都作为一个独立的输入维度$X$，那么两者是等价的。（因为每一条输入数据只有一个U和I是1，其他都为0）
- FMs vs SVD++：此处没看懂，回头补上
- FMs vs PITF：两者最大的不同时FMs的$V_t$向量在式子中是共享的。
- FMs vs FPMC：感觉和SVD++的形式非常类似，同样没看懂，回头补上