参考资料：
- https://blog.csdn.net/u012328159/article/details/122938925
- https://blog.csdn.net/u012328159/article/details/120684544?spm=1001.2014.3001.5501
DeepFM
FM部分
目前在模型层面做交叉特征的难点主要有以下两个方面：
- 交叉特征的参数独立，强依赖于在样本中的共现信息，如果交叉特征值没有出现，那么参数无法学习。
- 时间复杂度问题，直接做二阶交叉，时间复杂度为O(N^2)，复杂度过高。
FM 则解决了上面两个问题，直接上 FM 的模型公式：
\[\hat{y}(x) = w_0 + \sum_{i=1}^nw_ix_i + \sum_{i=1}^n\sum_{j=i+1}^n<v_i, v_j>x_ix_j \tag{7} \]其中 \(<\cdot,\cdot>\) 为两个 k 维的向量的点积，即数量积。 \(v_i\) 表示第 \(i\) 个特征的向量。
\[<v_i, v_j>=\sum_{f=1}^k v_{i,f} \cdot v_{j,f} \tag{8} \]因此，公式（7）完整的为：
\[\hat{y}(x) = w_0 + \sum_{i=1}^nw_ix_i + \sum_{i=1}^n\sum_{j=i+1}^n\sum_{f=1}^kv_{i,f} \cdot v_{j,f} x_ix_j \tag{9} \]因此，公式 (7) 这里实际可分为三部分，第一部分一个偏置单元 \(w_0\) ，一阶部分 \(\sum_{i=1}^nw_ix_i\) ，二阶部分
\[\sum_{i=1}^{n}\sum_{j=i+1}^n<v_i, v_j>x_ix_j \tag{10} \]FM 这里巧妙的把公式 (2) 中的独立参数 \(w_{ij}\) 分解成了 \(<v_i,v_j>\) ，实际上是通过学习每一个特征对应的隐向量（现在大家熟知的 embedding 向量），这样就不再依赖于交叉特征 \(x_ix_j\) 的共现信息，因为即使 \(x_ix_j\) 没有共现，假如 \(x_ix_k\) 有共现，那么 \(x_i\) 对应的隐向量 \(v_i\) 依然能够得到训练。
那么问题来了，这种方法是 FM 独创的吗，答案是：NO。这种思想来源于一个古老且有效的方法矩阵分解 MF（matrix factorization），在推荐系统里，每个用户对每个物品的评分，可以构建出一个 user-item 矩阵，而矩阵分解的核心思想是用一个用户 embedding 矩阵和一个物品 embedding 矩阵的乘积来近似这个大矩阵，这两个 embedding 矩阵是可训练学习的。上一张图来形象的表示矩阵分解
到这里，可以看到 FM 解决了我们前面抛出的两个问题中的第一个问题（交叉特征参数独立，依赖于交叉特征的共现），下面来看看 FM 如何解决第二个问题（时间复杂度问题），再来看看公式（7）中的二阶部分，时间复杂度为 O ( N 2 ) O(N^2) O(N2)，FM 把这部分做了个公式推导，把时间复杂度降到了 O ( K N ) O(KN) O(KN)，下面来看看 FM 的推到过程：
\[\begin{aligned} \sum_{i=1}^{n}\sum_{j=i+1}^n<v_i, v_j>x_ix_j &= \frac{1}{2} [\sum_{i=1}^{n}\sum_{j=1}^n<v_i, v_j>x_ix_j - \sum_{i=1}^{n}<v_i, v_i>x_ix_i] \\ &= \frac{1}{2}(\sum_{i=1}^n\sum_{j=1}^n\sum_{f=1}^kv_{i,f} \cdot v_{j,f} x_ix_j - \sum_{i=1}^n\sum_{f=1}^kv_{i,f} \cdot v_{i,f} x_ix_i) \\ &=\frac{1}{2}\sum_{f=1}^k((\sum_{i=1}^nv_{i,f}x_i)(\sum_{j=1}^nv_{j,f}x_j) - \sum_{i=1}^nv_{i,f}^2x_i^2) \\ &=\frac{1}{2}\sum_{f=1}^k((\sum_{i=1}^n v_{i,f}x_i)^2 -\sum_{i=1}^nv_{i,f}^2x_i^2) \end{aligned} \tag{11} \]关于上面这个公式，第一步到第二步，大家想象一个矩阵，行和列都是 \(x_1,....,x_n\) ，第一步为矩阵的上三角，所以等于全矩阵减去对角线，再折半，这样就比较好理解了。
tensorflow版本
网上实现的版本比较杂，挑了一个实现比较好的tensorflow版本DeepFM，参见：https://github.com/ChenglongChen/tensorflow-DeepFM，可以看看FM部分的实现。
# model
self.embeddings = tf.nn.embedding_lookup(self.weights["feature_embeddings"],
self.feat_index) # None * F * K
feat_value = tf.reshape(self.feat_value, shape=[-1, self.field_size, 1])
self.embeddings = tf.multiply(self.embeddings, feat_value)
# ---------- first order term ----------
self.y_first_order = tf.nn.embedding_lookup(self.weights["feature_bias"], self.feat_index) # None * F * 1
self.y_first_order = tf.reduce_sum(tf.multiply(self.y_first_order, feat_value), 2) # None * F
self.y_first_order = tf.nn.dropout(self.y_first_order, self.dropout_keep_fm[0]) # None * F
# ---------- second order term ---------------
# sum_square part
self.summed_features_emb = tf.reduce_sum(self.embeddings, 1) # None * K
self.summed_features_emb_square = tf.square(self.summed_features_emb) # None * K
# square_sum part
self.squared_features_emb = tf.square(self.embeddings)
self.squared_sum_features_emb = tf.reduce_sum(self.squared_features_emb, 1) # None * K
# second order
self.y_second_order = 0.5 * tf.subtract(self.summed_features_emb_square, self.squared_sum_features_emb) # None * K
self.y_second_order = tf.nn.dropout(self.y_second_order, self.dropout_keep_fm[1]) # None * K