FM、Wide&Deep、DeepFM模型

看论文的过程中看到过多次Factorization Machine(FM)和相关的方法，却一直没有去具体了解一下。这次读了相关的paper和资料，记一下理解。该系列的方法还挺多的，这里主要只看了FM、Wide&Deep和DeepFM模型，FFM等模型没有关注。

引入

假设问题如下：我们有\(N\)个特征，分别为\(x_1,\dots,x_N\)，要预测结果\(\hat{y}(\mathbf{x})\)。最简单的方法是直接做线性回归： \[ \hat{y}(\mathbf{x}) = w_0 + \sum_{i=1}^Nw_ix_i\tag{1.1} \] 这样的做法对各个特征分别独立看待了，而实际上不同特征之间如果经过关联会有助于预测。于是可以对特征进行两两组合： \[ \hat{y}(\mathbf{x}) = w_0 + \sum_{i=1}^Nw_ix_i + \sum_{i=1}^N\sum_{j=i+1}^N w_{ij}x_ix_j \tag{1.2} \] 可以看到，首先，这个式子中参数空间非常大，二次项中的参数\(W\)的维度有\(N \times N\)。而参数各项之间是相互独立的，要训练参数\(w_{ij}\)就必须用\(x_i\)和\(x_j\)都有效（非零）的样本。而由于样本有很多是类别型特征，经过one-hot编码转化过，因此非常稀疏，\(x_i\)和\(x_j\)同时非零的样本很少，难以准确估计参数\(w_{ij}\)，这就会容易导致模型过拟合。

FM

Factorization Machine (FM)模型由Steffen Rendle于2010年提出[1]，能够在数据稀疏的情况下估计参数，计算特征组合。

利用矩阵分解，FM可以将式\((1.2)\)的二次项系数进行分解： \[ \hat{y}(\mathbf{x}) = w_0 + \sum_{i=1}^Nw_ix_i + \sum_{i=1}^N\sum_{j=i+1}^N (\mathbf{v}_i \cdot \mathbf{v}_j ) x_ix_j \tag{2.1} \] 其中\(\mathbf{v}_i\)表示第\(i\)个特征的隐向量，其维度为\(k\) (\(k \ll N\))，两个隐向量的内积仍是\(w_{ij}\)。这样一来，有两个好处：

二次项系数个数为\(kN\)个，相比原先大大减少。
隐向量\(\mathbf{v}_i\)只和第\(i\)个特征相关，因此，只要是和特征\(x_i\)相关的组合都可以用来训练\(\mathbf{v}_i\)。而原来的式子中，参数\(W\)是和特征\(i\)、\(j\)同时相关的，也就限制了训练可以用到的样本数量。

而在实际运算中，可以对二次项进行等价变换，将运算的时间复杂度从\(O(kN^2)\)降为\(O(kN)\)： \[ \begin{align*} &\sum_{i=1}^N \sum_{j=i+1}^N \langle \mathbf{v}_i, \mathbf{v}_j \rangle x_i x_j \\ =& \frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \langle \mathbf{v}_i, \mathbf{v}_j \rangle x_i x_j – \frac{1}{2}\sum_{i=1}^N \langle \mathbf{v}_i, \mathbf{v}_i \rangle x_i x_i\\ =& \frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N\sum_{f=1}^k v_{i,f}v_{j,f} x_i x_j – \frac{1}{2}\sum_{i=1}^N \sum_{f=1}^k v_{i,f}v_{i,f}x_i x_i\\ =& \frac{1}{2} \sum_{f=1}^k \left( \left(\sum_{i=1}^Nv_{i,f}x_i \right) \left(\sum_{j=1}^Nv_{j,f}x_j \right) – \sum_{i=1}^N v_{i,f}^2x_i^2\right) \\ =&\frac{1}{2} \sum_{f=1}^k \left( \left(\sum_{i=1}^Nv_{i,f}x_i \right) ^2 – \sum_{i=1}^N v_{i,f}^2x_i^2\right) \end{align*} \] 最后，FM最终的式子为： \[ \hat y(\mathbf{x}) = w_0+ \sum_{i=1}^N w_i x_i + \frac{1}{2} \sum_{f=1}^k \left( \left(\sum_{i=1}^Nv_{i,f}x_i \right) ^2 – \sum_{i=1}^N v_{i,f}^2x_i^2\right) \tag{2-2} \] 对应的，它在tensorflow中的模板代码：

# Calculate output with FM equation
linear_terms = tf.add(
  W_0,
  tf.reduce_sum(
    tf.multiply(W, X), 1,
    keepdims=True))
pair_interactions = (tf.multiply(
  0.5,
  tf.reduce_sum(
    tf.subtract(
      tf.pow(tf.matmul(X, V_f), 2),
      tf.matmul(
        tf.pow(X, 2), tf.pow(
          V_f, 2))),
    1,
    keepdims=True)))
self.predictions = tf.add(
  linear_terms, pair_interactions, name="predictions")

Wide & Deep

Google提出的Wide & Deep模型其实和FM没有直接的关系，只是两者都对离散特征进行了特征组合，且后面的DeepFM是对这两个方法的结合，所以一起学习了一下。

模型有两种能力：

记忆（memorization）即从历史数据中发现item或者特征之间的相关性。
泛化（generalization）即相关性的传递，发现在历史数据中很少或者没有出现的新的特征组合。

本文利用Wide & Deep模型，使得训练出来的模型能够同时拥有上述的两种特性。模型结构如下：

Wide部分是通过人工构造特征的叉乘、再使用线性模型做预测，最常用的是LR模型。这种做法中特征的组合情况是较浅的，即只有2层、3层的组合，因为需要人工构造。而Deep部分则是首先将稀疏特征转换为低维的embedding向量，然后通过多层的前馈神经网络来挖掘特征中较深的组合关系。

DeepFM

该模型由华为和哈工大在IJCAI 2017中提出，其主要贡献很简单，就是使用Wide & Deep的框架结构，并在此结构上使用FM来自动构造二阶特征叉乘，替代掉Wide部分的LR+人工构造特征。模型图如下：

可以看出，Deep部分依然不变，而Wide部分变为了FM Layer。另外，FM层和神经网络层共享特征的embedding作为输入。这样做的好处一方面在于降低模型复杂度；另一方面能使embedding学习到low & high order interaction的信息。

Reference

S. Rendle, “Factorization Machines“. 2010 IEEE International Conference on Data Mining, Sydney, NSW, 2010, pp. 995-1000. doi: 10.1109/ICDM.2010.127
Heng-Tze Cheng, et al. 2016. “Wide & Deep Learning for Recommender Systems“. In Proceedings of the 1st Workshop on Deep Learning for Recommender Systems (DLRS 2016). ACM, New York, NY, USA, 7-10. DOI: https://doi.org/10.1145/2988450.2988454
Guo, H., Tang, R., Ye, Y., Li, Z., & He, X. (2017). DeepFM: A Factorization-Machine based Neural Network for CTR Prediction. ArXiv, abs/1703.04247.
『我爱机器学习』FM、FFM与DeepFM