一、FmFM [2021]

《FM2: Field-matrixed Factorization Machines for Recommender Systems》

1. CTR 预估所涉及的数据通常是 multi-field categorical data，这类数据具有以下特性：

   • 首先，所有的特征都是 categorical 的，并且是非常稀疏的，因为其中许多是 id 。因此，特征的总数很容易达到数百万或数千万。

   • 其次，每个特征都唯一地属于一个 field ，而且可能有几十到几百个 field 。

   针对 ctr 预测问题的一个卓越模型是具有交叉特征的逻辑回归。当考虑到所有的交叉特征时，产生的模型等同于二阶的多项式核。然而，要考虑所有可能的交叉特征需要太多的参数。为解决这个问题，人们提出了 matrix factorization: MF 和 factorization machine: FM ，这些方法通过两个 feature embedding 向量的点乘来学习交叉特征的影响。在 FM 的基础上，人们提出了 Field-aware Factorization Machine: FFM，从而考虑 field 信息来建模来自不同 field pair 的不同的特征交互。最近，人们又提出了 Field-weighted Factorization Machine: FwFM 模型，以一种更加 parameter-efficient 的方式来考虑 field 信息。

   现有的考虑 field 信息的模型要么有太多的参数（如 FFM ），要么不是很有效（如 FwFM）。论文 《FM2: Field-matrixed Factorization Machines for Recommender Systems》 建议使用两个特征向量之间的 field matrix 来建模这两个特征向量之间的交互，其中矩阵是为每个 field-pair 单独学习的。论文表明，field-pair matrix 方法在保持计算空间和时间效率的同时，实现了良好的准确性。

1.1 模型

1. 假设有 $m$$m$ 个 unique 特征 $\{f_1,\cdots ,f_m\}$$\{f_1,\cdots,f_m\}$，以及 $n$$n$ 个不同的 fields $\{F_1,\cdots ,F_n\}$$\{F_1,\cdots,F_n\}$ 。每个特征 $f_i$$f_i$ 仅属于一个 field，记做 $F(i)$$F(i)$ 。

   给定数据集 $\mathcal{S}={\{y^{(s)},{\overrightarrow{\mathbf{x}}}^{(s)}\}}_{s=1}^N$$\mathcal S = \left\{y^{(s)},\mathbf{\vec x}^{(s)}\right\}_{s=1}^N$ ，其中： $y^{(s)}\in \{1,-1\}$$y^{(s)}\in \{1,-1\}$ 为 label 表示是否点击； ${\overrightarrow{\mathbf{x}}}^{(s)}\in \{0,1{\}}^m$$\mathbf{\vec x}^{(s)}\in \{0,1\}^m$ 为二元特征向量，$x_i^{(s)}=1$$x_i^{(s)}=1$ 表示特征 $f_i$$f_i$ 是 active 的。

   • LR 模型为：

     $$\underset{\overrightarrow{\mathbf{w}}}{min}\lambda \parallel \overrightarrow{\mathbf{w}}{\parallel }_2^2+\sum _{s=1}^N\log (1+\exp (-y^{(s)}{\mathrm{\Phi }}_{\text{LR}}(\overrightarrow{\mathbf{w}},{\overrightarrow{\mathbf{x}}}^{(s)})))$$

     其中：$\lambda$$\lambda$ 为正则化系数，$\overrightarrow{\mathbf{w}}$$\mathbf{\vec w}$ 为模型权重，${\mathrm{\Phi }}_{\text{LR}}(\overrightarrow{\mathbf{w}},\overrightarrow{\mathbf{x}})=w_0+\sum _{i=1}^m{x}_i{w}_i$$\Phi_\text{LR}(\mathbf{\vec w}, \mathbf{\vec x}) = w_0 + \sum_{i=1}^m x_iw_i$ 。

     然而，线性模型缺乏表示特征交互的能力。由于交叉特征可能比那些单一特征更重要，在过去的几十年里，人们提出了许多改进。

   • Poly2：然而，线性模型对于诸如 CTR 预估这样的任务来说是不够的，在这些任务中，特征交互是至关重要的。解决这个问题的一般方法是增加 feature conjunction 。已有研究表明，Degree-2 Polynomial: Poly2 模型可以有效地捕获特征交互。Poly2 模型考虑将 ${\mathrm{\Phi }}_{\text{LR}}$$\Phi_\text{LR}$ 替换为：

     $${\mathrm{\Phi }}_{\text{Poly2}}(\overrightarrow{\mathbf{w}},\overrightarrow{\mathbf{x}})=w_0+\sum _{i=1}^m{x}_i{w}_i+\sum _{i=1}^m\sum _{j=i+1}^m{x}_i{x}_j{w}_{h(i,j)}$$

     其中：$h(i,j)$$h(i,j)$ 是一个哈希函数，它将 $i$$i$ 和 $j$$j$ 哈希到位于哈希空间 $\mathcal{H}$$\mathcal H$ 中的一个自然数，从而减少参数规模。否则，模型中的参数数量将达到 $O(m^2)$$O(m^2)$ 的数量级。

   • FM：Factorization Machine:FM 为每个特征学习一个 embedding 向量 ${\overrightarrow{\mathbf{v}}}_i\in {\mathbb{R}}^K$$\mathbf{\vec v}_i\in \mathbb R^K$ ，其中 $K$$K$ 为一个小的整数（如 $K=10$$K=10$ ）。FM 将两个特征 $i$$i$ 和 $j$$j$ 之间的交互建模为它们相应的 embedding 向量 ${\overrightarrow{\mathbf{v}}}_i$$\mathbf{\vec v}_i$ 和 ${\overrightarrow{\mathbf{v}}}_j$$\mathbf{\vec v}_j$ 之间的内积：

     $${\mathrm{\Phi }}_{\text{FM}}((\overrightarrow{\mathbf{w}},\mathbf{v}),\overrightarrow{\mathbf{x}})=w_0+\sum _{i=1}^m{x}_i{w}_i+\sum _{i=1}^m\sum _{j=i+1}^m{x}_i{x}_j<{\overrightarrow{\mathbf{v}}}_i,{\overrightarrow{\mathbf{v}}}_j>$$

     其中：$<\cdot ,\cdot >$$<\cdot,\cdot>$ 为向量的内积。

     在涉及稀疏数据的应用中（如 CTR 预估），FM 的表现通常优于 Poly2 模型。原因是，只要特征本身在数据中出现的次数足够多，FM 总能为每个特征学习到一些有意义的 embedding 向量，这使得内积能很好地估计两个特征的交互效应（ interaction effect），即使两个特征在数据中从未或很少一起出现。

   • FFM：然而，FM 忽略了这样一个事实：当一个特征与其他不同 field 的特征交互时，其行为可能是不同的。Field-aware Factorization Machines: FFM 通过为每个特征（如 $i$$i$ ）学习 $n-1$$n-1$ 个 embedding 向量来显式地建模这种差异，并且只使用相应的 embedding 向量 ${\overrightarrow{\mathbf{v}}}_{i,F(j)}$$\mathbf{\vec v}_{i,F(j)}$ 与来自 field $F(j)$$F(j)$ 的另一个特征 $j$$j$ 交互：

     $${\mathrm{\Phi }}_{\text{FM}}((\overrightarrow{\mathbf{w}},\mathbf{v}),\overrightarrow{\mathbf{x}})=w_0+\sum _{i=1}^m{x}_i{w}_i+\sum _{i=1}^m\sum _{j=i+1}^m{x}_i{x}_j<{\overrightarrow{\mathbf{v}}}_{i,F(j)},{\overrightarrow{\mathbf{v}}}_{j,F(i)}>$$

     虽然 FFM 比 FM 有明显的性能改进，但其参数数量是 $O(mnK)$$O(mnK)$ 的数量级。在现实世界的生产系统中，FFM 的巨大参数数量是不可取的。因此，设计具有竞争力的和更高内存效率的替代方法是非常有吸引力的。

   • FwFM：在 FwFM 中，feature pair $(i,j)$$(i,j)$ 的交互被建模为：

     $$x_i{x}_j<{\overrightarrow{\mathbf{v}}}_i,{\overrightarrow{\mathbf{v}}}_j>r_{F(i),F(j)}$$

     其中：$<\cdot ,\cdot >$$<\cdot,\cdot>$ 为向量的内积，$r_{F(i),F(j)}\in \mathbb{R}$$r_{F(i),F(j)}\in \mathbb R$ 是建模 field pair $(F(i),F(j))$$(F(i),F(j))$ 之间交互强度的权重。

     FwFM 的公式为：

     $${\mathrm{\Phi }}_{\text{FwFM}}((\overrightarrow{\mathbf{w}},\mathbf{v}),\overrightarrow{\mathbf{x}})=w_0+\sum _{i=1}^m{x}_i{w}_i+\sum _{i=1}^m\sum _{j=i+1}^m{x}_i{x}_j<{\overrightarrow{\mathbf{v}}}_i,{\overrightarrow{\mathbf{v}}}_j>r_{F(i),F(j)}$$

     FwFM 是 FM 的扩展，即它使用额外的权重 $r_{F(i),F(j)}$$r_{F(i),F(j)}$ 来显式地建模不同 feature pair 的不同交互强度。FFM 可以隐式地建模不同 feature pair 的不同交互强度，因为 FFM 为每个特征 $i$$i$ 学习了几个 embedding 向量，每个向量 ${\overrightarrow{\mathbf{v}}}_{i,F_k}$$\mathbf{\vec v}_{i,F_k}$ 对应于其他的 field $F_k$$F_k$，其中$F_k\ne F(i)$$F_k\ne F(i)$ ，从而建模 $F(i)$$F(i)$ 与不同 field 特征的不同交互。

   最近，也有很多关于基于深度学习的 CTR 预测模型的工作。这些模型同时捕获了低阶交互和高阶交互，并取得了明显的性能改进。然而，这些模型的在线推理复杂性比浅层模型要高得多。通常需要使用模型压缩技术，如剪枝、蒸馏或量化来加速这些模型的在线推理。在本文中，我们专注于改进低阶交互，所提出的模型可以很容易地作为这些深度学习模型中的浅层组件。

2. 我们提出了一个新的模型，将 field pair 的交互表达为一个矩阵。与 FM 和 FwFM 类似，我们为每个特征学习一个 embedding 向量。 我们定义一个矩阵 ${\mathbf{M}}_{F(i),F(j)}$$\mathbf M_{F(i),F(j)}$ 来表示 field $F(i)$$F(i)$ 和 field $F(j)$$F(j)$ 之间的交互：

   $$x_i{x}_j<{\mathbf{M}}_{F(i),F(j)}{\overrightarrow{\mathbf{v}}}_i,{\overrightarrow{\mathbf{v}}}_j>$$

   其中：

   • ${\overrightarrow{\mathbf{v}}}_i,{\overrightarrow{\mathbf{v}}}_j$$\mathbf{\vec v}_i,\mathbf{\vec v}_j$ 分别为 feature $i$$i$ 和 $j$$j$ 的 embedding 向量。

   • $F(i),F(j)$$F(i), F(j)$ 分别为 feature $i$$i$ 和 $j$$j$ 的 field。

   • ${\mathbf{M}}_{F(i),F(j)}\in {\mathbb{R}}^{K\times K}$$\mathbf M_{F(i), F(j)}\in \mathbb R^{K\times K}$ 为建模 field $F(i)$$F(i)$ 和 field $F(j)$$F(j)$ 之间交互的矩阵。

     注意：${\mathbf{M}}_{F(i),F(j)}\ne {\mathbf{M}}_{F(j),F(i)}$$\mathbf M_{F(i), F(j)} \neq \mathbf M_{F(j), F(i)}$ ，因为它们作用的 embedding 向量不同。此外，考虑到 “ field $F(i)$$F(i)$ 和 field $F(j)$$F(j)$ 之间的交互” 应该等于 “ field $F(j)$$F(j)$ 和 field $F(i)$$F(i)$ 之间的交互”，因此有：

     $$<{\mathbf{M}}_{F(i),F(j)}{\overrightarrow{\mathbf{v}}}_i,{\overrightarrow{\mathbf{v}}}_j>=<{\mathbf{M}}_{F(j),F(i)}{\overrightarrow{\mathbf{v}}}_j,{\overrightarrow{\mathbf{v}}}_i>$$

   我们称这个模型为 Field-matrixed Factorization Machine: FmFM（也叫做 FM2）：

   $${\mathrm{\Phi }}_{\text{FmFM}}((\overrightarrow{\mathbf{w}},\mathbf{v}),\overrightarrow{\mathbf{x}})=w_0+\sum _{i=1}^m{x}_i{w}_i+\sum _{i=1}^m\sum _{j=i+1}^m{x}_i{x}_j<{\mathbf{M}}_{F(i),F(j)}{\overrightarrow{\mathbf{v}}}_i,{\overrightarrow{\mathbf{v}}}_j>$$

   FmFM 是 FwFM 的扩展，它使用一个二维矩阵 ${\mathbf{M}}_{F(i),F(j)}$$\mathbf M_{F(i),F(j)}$ （而不是FwFM 中的标量 $r$$r$ ）来建模不同field pair 的交互。通过这些矩阵，每个特征的 embedding 空间可以被转换到另外的 $n-1$$n-1$ 个 embedding 空间。我们将这些矩阵命名为 Field-Matrix 。

   核心思想：将 FwFM 中的标量 $r_{F(i),F(j)}$$r_{F(i), F(j)}$ 升级成矩阵 ${\mathbf{M}}_{F(i),F(j)}$$\mathbf M_{F(i), F(j)}$ 。

   下图展示了 feature pair $(i,j)$$(i,j )$ 和 $(i,k)$$(i,k)$ 的交互，其中 $i,j,k$$i, j,k$ 来自于三个不同的 field 。计算可以分解为三步：

   • Embedding Lookup：从 embedding table 中查找 feature embedding 向量 ${\overrightarrow{\mathbf{v}}}_i,{\overrightarrow{\mathbf{v}}}_j,{\overrightarrow{\mathbf{v}}}_k$$\mathbf{\vec v}_i,\mathbf{\vec v}_j,\mathbf{\vec v}_k$ 。

   • 转换：将 ${\mathbf{M}}_{F(i),F(j)}$$\mathbf M_{F(i),F(j)}$ 和 ${\mathbf{M}}_{F(i),F(k)}$$\mathbf M_{F(i),F(k)}$ 分别与 ${\overrightarrow{\mathbf{v}}}_i$$\mathbf{\vec v}_i$ 相乘，得到中间向量 ${\overrightarrow{\mathbf{v}}}_{i,F(j)}={\mathbf{M}}_{F(i),F(j)}{\overrightarrow{\mathbf{v}}}_i$$\mathbf{\vec v}_{i,F(j)} = \mathbf M_{F(i),F(j)} \mathbf{\vec v}_i$ 用于 field $F(j)$$F(j)$ 、 ${\overrightarrow{\mathbf{v}}}_{i,F(k)}={\mathbf{M}}_{F(i),F(k)}{\overrightarrow{\mathbf{v}}}_i$$\mathbf{\vec v}_{i,F(k)} = \mathbf M_{F(i),F(k)} \mathbf{\vec v}_i$ 用于 field $F(k)$$F(k)$ 。

   • 点乘：最终的交互项将是 ${\overrightarrow{\mathbf{v}}}_{i,F(j)}\cdot {\overrightarrow{\mathbf{v}}}_j$$\mathbf{\vec v}_{i,F(j)}\cdot \mathbf{\vec v}_j$ 以及 ${\overrightarrow{\mathbf{v}}}_{i,F(k)}\cdot {\overrightarrow{\mathbf{v}}}_k$$\mathbf{\vec v}_{i,F(k)}\cdot \mathbf{\vec v}_k$ 。

   

1.2 FM2 作为统一框架

1. FM 家族的统一框架：

   • FM：下图展示了 FM 中特征交互的计算。如果将 FmFM 中所有的 field matrix 都固定为单位矩阵，那么 FmFM 将退化为 FM 。由于单位矩阵是固定的、不可训练的，因此我们定义其自由度为 0 。

     

   • FwFM：下图展示了 FwFM 中特征交互的计算。如果将 FmFM 中的 ${\mathbf{M}}_{F(i),F(j)}$$\mathbf M_{F(i),F(j)}$ 定义为 $r{\mathbf{I}}_K\in {\mathbb{R}}^{K\times K}$$r\mathbf I_K\in \mathbb R^{K\times K}$ （如下图左边的矩阵所示），其中 $r$$r$ 为标量并且针对不同的 field pair 取不同的值，那么 FmFM 将退化为 FwFM 。我们定义 FwFM 的自由度为 1 。

     

   • FvFM：根据 Figure 3 的线索，我们将 FmFM 中的 ${\mathbf{M}}_{F(i),F(j)}$$\mathbf M_{F(i),F(j)}$ 定义为对角矩阵 ${\mathbf{D}}^{F(i),F(j)}=\text{diag}(d_1^{F(i),F(j)},d_2^{F(i),F(j)},\cdots ,d_K^{F(i),F(j)})\in {\mathbb{R}}^K$$\mathbf D^{F(i),F(j)} = \text{diag}(d^{F(i),F(j)}_1,d^{F(i),F(j)}_2,\cdots,d^{F(i),F(j)}_K)\in \mathbb R^{K}$ ，其中不同 field pair 选择不同的对角矩阵，如 Figure3 的右边的矩阵所示，那么：

     $${\overrightarrow{\mathbf{v}}}_{i,F(j)}={\mathbf{D}}^{F(i),F(j)}{\overrightarrow{\mathbf{v}}}_i={\overrightarrow{\mathbf{v}}}_i\odot {\overrightarrow{\mathbf{d}}}^{F(i),F(j)}$$

     其中：${\overrightarrow{\mathbf{d}}}^{F(i),F(j)}=(d_1^{F(i),F(j)},d_2^{F(i),F(j)},\cdots ,d_K^{F(i),F(j)})$$\mathbf{\vec d}^{F(i),F(j)} = \left(d^{F(i),F(j)}_1,d^{F(i),F(j)}_2,\cdots,d^{F(i),F(j)}_K\right)$ 。

     我们将这种方法命名为 Field-vectorized Factorization Machine: FvFM ，它的自由度为 2 。

   • FmFM：它具有一个矩阵的所有自由度，即自由度为 3 。我们预期 FmFM 比其他 FM 模型有更强大的预测能力。

   总之，我们发现 FM、FwFM 、FvFM 都是 FmFM 的特例，唯一的区别是它们的 field matrix的限制。根据它们的灵活性，我们把它们总结在下表中。

   

2. FmFM 与 OPNN 的关系：FmFM 也可以看做是通过加权外积来建模两个 feature embedding vector 的交互：

   $$\begin{array}{c}{\mathrm{\Phi }}_{\text{FmFM}}((\overrightarrow{\mathbf{w}},\mathbf{v}),\overrightarrow{\mathbf{x}})=w_0+\sum _{i=1}^m{x}_i{w}_i+\sum _{i=1}^m\sum _{j=i+1}^m{x}_i{x}_{j}p({\overrightarrow{\mathbf{v}}}_i,{\overrightarrow{\mathbf{v}}}_j,{\mathbf{W}}_{F(i),F(j)})\\ {\mathbf{W}}_{F(i),F(j)}\in {\mathbb{R}}^{K\times K},p({\overrightarrow{\mathbf{v}}}_i,{\overrightarrow{\mathbf{v}}}_j,{\mathbf{W}}_{F(i),F(j)})=\sum _{k=1}^K\sum _{k^{\prime }=1}^K{v}_{i,k}{v}_{j,k^{\prime }}{w}_{F(i),F(j),k,k^{\prime }}\end{array}$$

   OPNN 也提出通过外积来建模特征交互。然而，FmFM 在以下两个方面与 OPNN 不同：

   • 首先，FmFM 是一个简单的浅层模型，没有像 OPNN 中那样的全连接层。我们可以将 FmFM 作为任何深度 CTR 模型的一个浅层组件或构建块。

   • 其次，FmFM 支持针对不同 feature field 的可变 embedding size 。

3. FFM vs FmFM ，即 Memorization vs Inference ：与上述其他 FM 不同，FFM 不能被改造成 FmFM 框架。下图展示了 FFM 中特征交互的计算。 FFM 不共享 feature embedding，因此对于每个特征都有 $n-1$$n-1$ 个 embedding 从而分别与其它 $n-1$$n-1$ 个 field 进行交叉。在训练过程中，这些 field-specific embedding 将被独立学习，而且这些 embedding 之间没有任何限制，即使它们属于同一特征。

   这种 FFM 机制给了模型最大的灵活性来拟合数据，而且大量的 embedding 参数也具有惊人的记忆能力。同时，即使有数十亿的样本需要训练，也总是存在着过拟合的风险。特征分布的属性是一个长尾分布，而不是均匀分布，这使得 feature pair 的分布更加不平衡。

   以下图为例。假设 feature pair $(i,j)$$(i, j)$ 是高频组合、$(i,k)$$(i,k)$ 是低频（甚至是从未出现）组合。由于 ${\overrightarrow{\mathbf{v}}}_{i,F(j)}$$\mathbf{\vec v}_{i,F(j)}$ 和 ${\overrightarrow{\mathbf{v}}}_{i,F(k)}$$\mathbf{\vec v}_{i,F(k)}$ 是两个独立的 embedding，因此 embedding ${\overrightarrow{\mathbf{v}}}_{i,F(j)}$$\mathbf{\vec v}_{i,F(j)}$ 可能被训练得很好而 ${\overrightarrow{\mathbf{v}}}_{i,F(k)}$$\mathbf{\vec v}_{i,F(k)}$ 未被训练得很好。由于特征的长尾分布，那些高频的 feature pair 可能占据了训练数据的绝大部分，而低频的 feature pair （占据了 feature pair 中的绝大多数）则不能被很好地训练。

   FmFM 使用共享 embedding 向量，因为每个特征只有一个 embedding 向量。它利用一个变换过程，将这一个 embedding向量投影到其他 $n-1$$n-1$ 个 field 。这基本上是一个推理过程，那些 $n-1$$n-1$ 个 embedding 向量 ${\overrightarrow{\mathbf{v}}}_{i,F(\ast )}$$\mathbf{\vec v}_{i,F(*)}$ 其实是与原始的 embedding 向量 ${\overrightarrow{\mathbf{v}}}_i$$\mathbf{\vec v}_i$ 绑定的。有了这些 field matrix ，向量是可以前向变换和反向变换。这就是 FFM 和 FmFM 的根本区别：在同一特征中那些可变换的中间向量（即，${\overrightarrow{\mathbf{v}}}_{i,F(\cdot )}$$\mathbf{\vec v}_{i,F(\cdot)}$）有助于模型很好地学习那些低频 feature pair 。

   

   回到 Figure 1 的例子。即使 feature pair $(i,k)$$(i, k)$ 是低频的，feature embedding ${\overrightarrow{\mathbf{v}}}_i$$\mathbf{\vec v}_i$ 仍然可以通过其他高频 feature pair （如 $(i,j)$$(i,j)$ ）来训练。而 field matrix ${\mathbf{M}}_{F(i),F(k)}$$\mathbf M_{F(i), F(k)}$ 可以通过 field $F(i)$$F(i)$ 和 field $F(k)$$F(k)$ 之间的其他特征交互得到良好的训练。因此，如果低频 feature pair $(i,k)$$(i,k)$ 在评估或测试过程中出现，中间向量 ${\overrightarrow{\mathbf{v}}}_{i,F(k)}$$\mathbf{\vec v}_{i,F(k)}$ 可以通过 ${\mathbf{M}}_{F(i),F(k)}{\overrightarrow{\mathbf{v}}}_i$$\mathbf M_{F(i),F(k)} \mathbf{\vec v}_i$ 推断出来。

   尽管 FFM 和 FmFM 之间有这种差异，但它们有更多的共同点。Figure 4 和 Figure 1 之间一个有趣的观察是：当所有变换完成后，FmFM 模型变成了 FFM 模型。我们可以缓存那些中间向量，避免在运行时进行矩阵操作。细节将在下一节讨论。

   相反，FFM 模型无法被改造成 FmFM 模型。那些 $n-1$$n-1$ 个 field feature embedding table 是独立的，因此很难将它们压缩成单个 feature embedding table ，并在需要时恢复它们。

4. 模型复杂度：

   • FM 的参数数量为 $m+mK$$m + mK$ ，其中 $m$$m$ 为线性部分每个特征的权重、$mK$$mK$ 为所有特征的 embedding 向量。

   • FwFM 对每个 field 对使用 $n(n-1)/2$$n(n-1)/2$ 的额外参数，因此 FwFM 的参数总数为 $m+mK+n(n-1)/2$$m+mK+n(n-1)/2$ 。

   • FmFM 对每个 field 对使用 $n(n-1)/2$$n(n-1)/2$ 个额外的矩阵，对应于 $\frac{n(n-1)}{2}{K}^2$$\frac{n(n-1)}{2}K^2$ 个参数，因此 FwFM 的参数总数为 $m+mK+n(n-1)K^2/2$$m+mK+n(n-1)K^2/2$ 。

   • FFM 的参数数量为 $m+m(n-1)K$$m+m(n-1)K$ ，因为每个特征有 $n-1$$n-1$ 个 embedding 向量。

   在下表中，我们比较了到目前为止提到的所有模型的复杂度。我们还列出了每个模型的估计参数规模（模型配置，如 embedding size ，参考实验部分），这些模型使用了公共数据集 Criteo 。这些数字可以让我们对每个模型的规模有一个直观的印象。FM 、FwFM 和 FmFM 的规模相近，而 FFM 的规模比其他模型大十几倍。

   

1.3 模型优化

1. 这里我们可以设计出 3 种策略来进一步降低 FmFM 的复杂度：

   • field-specific embedding dimension：它是 FmFM 的一个独特属性，允许我们在 embedding table 中使用 field-specific 的维度，而不是全局的固定长度 $K$$K$ 。

     这里 field-specific 的维度是通过对训练好的 embedding table 进行降维来实现的。因此需要训练两遍。

   • 缓存中间向量：避免矩阵运算从而在运行时减少 FmFM 的计算复杂度（仅用于推断期间）。

   • 减少线性项：用 field-specific 权重来代替。

   这里面提到的优化方法大多数都不实用，无法优化训练速度，而仅聚焦于优化推断速度。实际上，如果想优化推断速度，那么可以用模型剪枝、模型量化、模型蒸馏技术。

2. Field-specific Embedding Dimension：为了进行点积， FM 要求所有 feature embedding 的向量维度 $K$$K$ 相同，即使特征来自不同的 field 。改进后的模型如 FwFM 、FvFM 也采用了这个特性。然而，向量维度 $K$$K$ 只能全局优化。

   当我们利用 FmFM 中的矩阵乘法时，它实际上并不要求 field matrix 是方阵：我们可以通过改变 field matrix 的 shape 来调整输出向量的维度。这一特性给了我们另一种灵活性，可以在 embedding table 中按需设置 field-specific 维度，如下图所示。

   embedding 向量的维度决定了它所能携带的信息量。例如，field user_gender 可能只包含 3 个值（ male, female, other ），field top_level_domain 可能包含超过 1M 个特征。因此，user_gender 的 embedding table 可能只需要 5 维，而 field top_level_domain 的 embedding table 可能需要 7 维，因此它们之间的 field matrix 的 shape 为 $(7,5)$$(7, 5)$ 。

   

   为了在不损失模型性能的前提下设计 field-specific embedding vector dimension ，我们提出了一种 2-pass 方法：

   • 在第一个 pass，我们对所有 field 使用较大的固定的 embedding 向量维度，如 $K=16$$K=16$ ，并将 FmFM 训练为完整模型。从完整的模型中，我们了解到每个 field 有多少信息（方差），然后我们在每个 field 的 embedding table 上应用标准的 PCA 降维方法。从实验部分中我们发现，包含 95%原始方差的新维度是一个很好的 tradeoff。

   • 有了这个新的 field-specific 的维度设置，我们在第二个 pass 中从头开始训练模型。与第一个完整的模型相比，所得到的第二个模型没有任何明显的性能损失。

   这种方法训练时间翻倍。一般而言，CTR 预测任务的数据集很大、模型也比较复杂，因此整体训练时间会很长。翻倍的训练时间不太有利。

   并且，这种方法还需要仔细设计 field matrix 的 shape，增加了开发成本。

   下表显示了 Criteo 数据集中每个 field 通过 PCA 进行优化后的维度。可以看到，这些维度的范围很大，从 2 到 14 ，而且大部分维度都小于 10 。平均 $\overline{K}$$\bar K$只有 7.72 ，低于 FwFM 的最佳 $K$$K$ 值。由于保留了数据集的大部分方差，较低的平均维度意味着模型的参数较少，需要较少的内存。

   

3. Intermediate Vectors Cache：在参数数量上，FmFM 是一个比 FFM 更低复杂度的模型。但是 FmFM 在变换步骤中需要昂贵的矩阵运算。在下表中，我们列出了每个模型的浮点运算( Floating Point Operations: FLOPs )的数量，并以典型的设置对其进行估计。

   注：典型设置为：$n=39,K=16,H=200$$n=39, K=16, H=200$ 为 DNN 隐层的单元数， $L=3$$L=3$ 为 DNN 的隐层数量，$K^{\prime }=32$$K^\prime=32$ 为AutoInt 中新空间的维度，$s_{\text{FwFM}}=90\mathrm{\%}$$s_\text{FwFM} = 90\%$ 和 $s_{\text{DNN}}=80\mathrm{\%}$$s_\text{DNN} = 80\%$ 分别为在 DeepLight 中 FwFM 和 DNN 组件的稀疏率。

   在这些 FM 模型中，FmFM 需要最多的操作来完成其计算，大约是FwFM 和 FFM 的 $K$$K$ 倍，但仍然比大多数 DNN 模型快。如前所述，我们已经表明，通过缓存所有的中间向量，可以将 FmFM 模型转化为 FFM 模型。在这个意义上，我们可以把它的操作数量减少到与FM 和 FFM 相同的量级，这几乎是 20 倍的速度。

   首先，如何缓存？论文并未提到细节。

   其次，缓存中间向量仅在推理期间有效，因为此时所有参数都已经学好并固定不动。然而在训练期间，每经过一个 training iteration 参数都发生更新，因此缓存的中间向量到下一个 iteration 就没有意义。因此，读者估计，FmFM 的训练时间会非常的长。

   最后，这里给的计算复杂度及其估计值是针对推理期间的，而不是训练期间的。而 95% variance 是在训练完成之后进行的，在训练期间不可用。

   

4. Embedding Dimension and Cache Optimization Combined ：当我们把 field-specific embedding dimensional optimization 和缓存优化结合起来时，推理速度可以快得多，而且所需的内存也可以大大减少。这得益于 FmFM 的另一个特性：交互矩阵是对称的。这意味着：

   $$<{\mathbf{M}}_{F(i),F(j)}{\overrightarrow{\mathbf{v}}}_i,{\overrightarrow{\mathbf{v}}}_j>=<{\mathbf{M}}_{F(i),F(j)}^{\mathrm{\top }}{\overrightarrow{\mathbf{v}}}_j,{\overrightarrow{\mathbf{v}}}_i>$$

   证明见原始论文。

   因此，我们可以选择缓存那些 field embedding 维度较低的中间向量，并在推理过程中与其他特征向量进行点乘。例如，在 Table 3 中，两个特征 $i$$i$ 和 $j$$j$ 分别来自 field #16 和 field #28 。有了这个对称性，当我们计算 $i$$i$ 和 $j$$j$ 之间的交互时，我们可以缓存 ${\mathbf{M}}_{16,28}{\overrightarrow{\mathbf{v}}}_i$$\mathbf M_{16,28} \mathbf{\vec v}_i$ 、或者缓存 ${\mathbf{M}}_{16,28}^{\mathrm{\top }}{\overrightarrow{\mathbf{v}}}_j$$\mathbf M_{16,28}^\top \mathbf{\vec v}_j$。

   • 由于 field matrix ${\mathbf{M}}_{16,28}$$\mathbf M_{16, 28}$ 的形状为 $(14,2)$$(14, 2)$， ${\mathbf{M}}_{16,28}{\overrightarrow{\mathbf{v}}}_i$$\mathbf M_{16,28} \mathbf{\vec v}_i$ 将维度从 2 （ field #16 ）增加到 14 （中间向量），然后与维度也为 14 的 ${\overrightarrow{\mathbf{v}}}_j$$\mathbf{\vec v}_j$ 进行点乘。它花费了 14 个单位的内存用于中间向量的缓存，在推理过程中需要 2*14 个 FLOPs 。

   • 相比之下，后者 ${\mathbf{M}}_{16,28}^{\mathrm{\top }}{\overrightarrow{\mathbf{v}}}_j$$\mathbf M_{16,28}^\top \mathbf{\vec v}_j$ 将维度从 14 （field #28 ）缩减到 2 （中间向量），然后与维度也是 2 的 ${\overrightarrow{\mathbf{v}}}_i$$\mathbf{\vec v}_i$ 进行点乘，它在中间向量缓存中花费 2 个单位的内存，并在推理中花费 2*2 FLOPs 。因此缓存维度为 2 的中间向量，可以节省 7 倍的内存和时间，而没有任何精度损失。

   通过这两种优化技术的结合，FmFM 模型的时间复杂度大大降低。在 Table 4 中，我们估计优化后的模型只需要 8,960 个 FLOPs ，这只是FFM 的 1/3 左右。在实验部分中，我们将说明这个优化的模型可以达到与完整模型相同的性能。

5. Soft Pruning：field-specific embedding dimension 实际上也起到了类似于剪枝的作用。传统的剪枝，如 DeepLight ，给出了保留或放弃一个 field 或一个 field pair 的二元决定。而 field-specific embedding dimension 给了我们一个新的方法：按需确定每个 field 和 field pair 的重要性，并给每个 field 分配一个系数（即，emebdding 维度）来代表其重要性。例如，在 Table 3 的 FmFM 模型中，cross field #17 和 #20 是一个高强度的 field pair ，它在推理过程中需要 11 个单位的缓存和 2*11 个 FLOPs ；相反，一个低强度的 field pair ，即 cross field #18 和 #22 ，只需要 2 个单位的缓存和 2*2 个 FLOPs 。

   缓存空间大小就是 field pair 中最短的那个 emebdding 维度。

   在传统的剪枝方法中，当我们放弃一个 field pair 时，它的信号就完全消失了。而在我们的方法中，一个 field pair 仍然以最小的代价保留主要信息（即，很小的 embedding 维度）。这是一个 soft pruning 的版本，类似于 Softmax 。它的效率更高，在 soft pruning 过程中性能下降更少。

   然后这种剪枝方法依赖于 emebdding 维度，而 embedding 维度是针对 embedding table 进行降维而得到的。这意味着在正式训练之前，先要完成一个训练从而得到 embedding table。此外，PCA 降维方法无法应用到大规模 embedding table 。

   Figure 6 显示了 Criteo 数据集中 field pair 和 label 之间的互信息分数的热力图，它代表了 field pair 在预测中的强度。Figure 7 显示了 cross field dimension ，这是两个 field 之间的较低维度，它表示每个 field pair 的参数和计算成本。显然，这两个热力图是高度相关的，这意味着优化后的 FmFM 模型在那些强度较高的 field pair 上分配了更多的参数和更多的计算，而在强度较低的 field pair 上分配了较少的参数和较少的计算。

   

   

6. 线性项：线性部分为：

   $$\sum _{i=1}^m{x}_i{w}_i$$

   这需要为每个特征 $i$$i$ 学习一个额外的标量 $w_i$$w_i$ 。然而，学到的 embedding 向量 ${\overrightarrow{\mathbf{v}}}_i$$\mathbf{\vec v}_i$ 应该包含更多的信息，而权重 $w_i$$w_i$ 可以通过简单的点乘从 ${\overrightarrow{\mathbf{v}}}_i$$\mathbf{\vec v}_i$ 中学习。这种方式（即，从 ${\overrightarrow{\mathbf{v}}}_i$$\mathbf{\vec v}_i$ 中学习 $w_i$$w_i$ ）的另一个好处是，它可以帮助从线性部分学习 embedding 向量。

   我们遵从 FwFM 的方法，通过学习一个 field-specific 向量 ${\overrightarrow{\mathbf{w}}}_{F(i)}$$\mathbf {\vec w}_{F(i)}$，这样所有来自同一 field $F(i)$$F(i)$ 的特征将共享相同的线性权重向量。然后，线性项可以被改写为：

   $$\sum _{i=1}^m{x}_i<{\overrightarrow{\mathbf{v}}}_i,{\overrightarrow{\mathbf{w}}}_{F(i)}>$$

   在本文的其余部分，我们默认对 FwFM、FvFM 和 FmFM 应用这种线性项优化。

1.4 实验

1. 数据集：Criteo、Avazu 。

   • 我们遵循那些已有的工作，将每个数据集随机分成三部分，80% 用于训练、10% 用于验证、10% 用于测试。

   • 对于 Criteo 数据集中的数值特征，我们采用 Criteo 竞赛冠军提出的对数变换来归一化数值特征：

     $$\begin{array}{c}z(x)=\{\begin{array}{ll}\log (x{)}^2,& \text{ if }x>2\\ x,& \text{else}\end{array}\end{array}$$

   • 对于 Avazu 数据集中的 date/hour 特征，我们将其转换为两个特征：day_of_week(0-6) 、hours(0-23) 。

   • 我们还删除了两组数据中那些低于阈值的低频特征，并用该 field 的默认 "unknown" 特征来替换。Criteo 数据集的阈值为 8，Avazu 数据集的阈值为 5 。

   归一化后的数据集的统计数字如下表所示：

   

2. baseline 方法：LR、FM、FwFM、FFM、FvFM、FmFM。

   我们遵循 PNN 原始论文中 LR 和 FM 的实现，并遵循 FwFM 原始论文中 FFM 和 FwFM 的实现。

3. 评估指标：验证集的 AUC, logloss 。

4. 模型配置：对于那些 SOTA 模型，它们都是 DNN 模型，可能需要更多的超参数调优，我们从它们的原始论文中提取它们的性能（AUC 和 Log Loss ），以保持它们的结果最佳。我们列出他们的结果只是为了参考。

   Deep & Cross 网络是一个例外，因为他们的论文只列出了 logloss 而没有列出 AUC 。因此，我们实现了他们的模型，得到了类似的性能。

   对于所有模型中的正则化系数 $\lambda$$\lambda$ 和学习率 $\eta$$\eta$ 等超参数，我们选择最佳验证集性能的超参数，然后在测试集上使用它们进行评估。

5. 模型评估结果如下所示，其中对于 FmFM 我们不采用任何优化手段。可以看到：

   • 在这两个数据集上，FvFM 和 FmFM 都能取得比 LR 、FM 和 FwFM更好的性能，这也是我们所预期的。

   • 令人惊讶的是，FmFM 在两个测试集上都能取得比 FFM 更好的性能。正如我们之前提到的，即使 FFM 是一个比 FmFM 大几十倍的模型，我们的 FmFM 模型仍然在所有浅层模型中得到最好的 AUC 。

     FmFM 和 FFM 的性能相差无几，非常接近。

   • 此外，如果我们比较训练集和测试集之间的 AUC 差异，我们发现 $\mathrm{\Delta }{\text{AUC}}_{\text{FmFM}}=0.0074$$\Delta \text{AUC}_\text{FmFM} = 0.0074$ 是那些 factorization machine 模型中最低的一个，这肯定了我们前面的假设：那些低频特征在交互矩阵的帮助下也被训练得不错，这种机制帮助 FmFM 避免过拟合。

     这里的数据和结论都不正确，$\mathrm{\Delta }{\text{AUC}}_{\text{FmFM}}$$\Delta \text{AUC}_\text{FmFM}$ 并不是最低的，而且数值也不是 0.0074 ，最低的是 LR 模型。

   

   

6. Embedding Dimension Optimization：在这一部分，我们前面描述的方法，即我们有一个 full size 的模型，我们可以为每个 field 提取其 embedding table ，然后我们利用标准的 PCA 降维。在这里，我们做了几个实验，比较降维对模型性能的影响，并试图在模型大小、速度和性能之间找到一个平衡点。

   我们使用 Criteo 数据集，PCA 降维中分别保持 99%, 97%, 95%, 90%, 85%, 80% 的方差，并估计平均 embedding 维度和 FLOPS （具有缓存的中间向量）。在新的维度设置下，我们分别训练这些 FmFM 模型的第二遍，并观察测试集的 AUC 和 Log Loss 变化。结果如下表所示。可以看到：

   • 当我们保持较少的 PCA 方差时，平均 embedding 维度明显减少。

   • 当我们保持 95% 的方差时，与 full size 模型相比，只有不到 1/2 的 emebdding 维度和 1/3 的计算成本，而模型的性能没有明显变化。因此，当我们优化 FmFM 的 embedding 维度时，95% 的方差是一个很好的 tradeoff 。

   

7. 下图 显示了这些模型的性能（AUC ）和它们的计算复杂性（ FLOPs ）。与所有的 baseline 模型相比，作为一个浅层模型，优化后的 FmFM 模型得到了更高的 AUC 以及更低的 FLOPs ，除了 Deep&Cross 和 DeepLight 。然而 FmFM 的计算成本比这两个 ensemble 了 DNN 模块和浅层模块的复杂模型（即，Deep&Cross 和 DeepLight ）要低得多，其 FLOPs 分别只有它们的 1.76% 和8.78% 。较低的 FLOPs 使得 FmFM 在计算延迟受到严格限制时更受欢迎，这也是实时在线广告 CTR 预测和推荐系统中的常见情况。

   

1.5 讨论

1. 未来方向：

   • FmFM 仍然是一个线性模型，我们可以将非线性层引入到 field 交互中，让模型成为非线性模型，这样就更加灵活。

   • 所有的 FM 模型实际上都是二阶模型，它最多允许 2 个 field 交互。这种限制主要是因为点积的原因。在未来，我们可以引入三维张量，允许 3 个 field 的交互，或者甚至更高阶次。这项工作可能需要更多的模型优化，因为有太多的三阶交互。

   • 我们可以结合 DNN 模型，如 Wide & Deep、DeepFM、DeepLight，并尝试将 FmFM 作为 DNN 模型的一个构建模块，以进一步提高其性能。