一、AutoFIS [2020]

《AutoFIS: Automatic Feature Interaction Selection in Factorization Models for Click-Through Rate Prediction》

1. 显式的特征交互可以显著提高 CTR 模型的性能。早期的协同过滤推荐算法，如矩阵分解（matrix factorization: MF）和分解机（factorization machine: FM），用一个 bi-linear learning model 抽取二阶信息。

   然而，并非所有的交互都有利于性能。一些基于树的方法已经被提出来，以自动找到有用的特征交叉。gradient boosting decision tree: GBDT 试图找到损失函数梯度较高的交互。AutoCross 在一个树状结构的空间中搜索有效的交互。但是树型模型在 multi-field categorical data 的推荐系统中只能探索所有可能的特征交互中的一小部分，所以它们的探索（exploration）能力受到限制。

   同时，深度神经网络 DNN 模型被提出。它们的表达能力更强，而且根据通用近似特性（universal approximation property），它们可以探索大多数的特征交互。然而，使用基于梯度的优化，并不能保证 DNN 自然地收敛到任何预期的函数。简单的 DNN 模型可能无法找到合适的特征交互。因此，人们提出了各种复杂的架构，如深度兴趣网络（Deep Interest Network: DIN）、深度分解机（Deep Factorization Machine: DeepFM）、Product-based Neural Network: PNN、以及 Wide & Deep 。因子分解模型（Factorization Model）（如 FM, DeepFM, PNN, Attention Factorization Machine: AFM, Neural Factorization Machine: NFM ），已被提出采用 feature extractor 来探索显式的特征交互。

   然而，所有这些模型要么是简单地枚举所有的特征交互，要么是需要人为的努力来识别重要的特征交互。前者总是给模型带来巨大的内存和计算成本，并且难以扩展到高阶交互。此外，无用的特征交互可能带来不必要的噪音，使训练过程复杂化。后者，如在 Wide & Deep 中手动识别重要的特征交互，具有很高的人力成本，并有可能错过一些反直觉的（但重要的）特征交互。

   如果在这些因子分解模型中可以事先识别出有用的特征交互，那么模型就可以专注于对它们的学习而不必处理无用的特征交互。通过去除无用甚至有害的特征交互，我们期望模型能在降低计算成本的情况下表现得更好。

   为了自动学习哪些特征交互是必要的，我们为每个特征交互引入了一个 gate （处于打开或关闭状态），以控制其输出是否应该被传递到下一层。在以前的工作中， gate 的状态要么是由专家知识事先指定、要么是设置为全部打开。从数据驱动的角度来看，一个 gate 是打开还是关闭，应该取决于每个特征交互对最终预测的贡献。显然，那些贡献小的特征交互应该关闭，从而防止给模型学习引入额外的噪音。然而，要找到模型性能的最佳 open gate 集合是一个 NP-Hard 问题，因为我们面临着一个巨大的空间（如果我们只考虑 2 阶特征交互， 则搜索空间为 $2^{C_m^2}$$2^{C_m^2}$，其中 $m$$m$ 为 feature field 的数量）来搜索。

   受最近用于神经架构搜索的 DARTS 的启发，论文 《AutoFIS: Automatic Feature Interaction Selection in Factorization Models for Click-Through Rate Prediction》 提出了一个两阶段的方法 AutoFIS ，用于自动选择因子分解模型中的低阶特征交互和高阶特征交互：

   • 在搜索阶段，AutoFIS 不是在一组离散的候选特征交互上进行搜索，而是通过引入一组架构参数（ architecture parameters）（每个特征交互一个）从而将 choice 松弛为连续的，这样就可以通过梯度下降学习每个特征交互的相对重要性。架构参数与神经网络权重由 GRDA 优化器（一种容易产生稀疏解的优化器）联合优化，这样训练过程可以自动丢弃不重要的特征交互（架构参数为零）而保留那些重要的特征交互。

   • 之后，在 re-train 阶段，AutoFIS 选择架构参数值非零的特征交互，用选定的特征交互重新训练模型，同时将架构参数作为注意力单元（attention unit），而不是交互重要性的指标。

   论文在三个大规模的数据集上进行了广泛的实验（两个公开的 benchmark、一个是 private 数据集）。实验结果表明：AutoFIS 可以显著提高所有数据集上因子分解模型的 CTR 预估性能。由于 AutoFIS 可以去除大约 50%-80% 的二阶特征交互，原始模型总是可以实现效率的提升。通过学习每个三阶特征交互的重要性，论文还将 AutoFIS 应用于三阶交互的选择。实验结果表明：在选择了大约1%-10% 的三阶交互之后，因子分解模型的 AUC 可以提高 0.1%-0.2% ，而不会引入很多计算成本。

   实验结果表明，使用 AutoFIS 进行高阶特征交互的自动选择是一个很有前景的方向。实验还表明，重要的二阶特征交互和三阶特征交互，通过在FM 中由 AutoFIS 所识别，也可以大大提升目前 SOTA 模型的性能，这意味着我们可以使用一个简单的模型进行交互选择（interaction selection），并将选择结果应用于其他模型。此外，论文在真实数据和人工合成数据上分析了AutoFIS 所选择的特征交互的有效性。此外，在华为应用商店的推荐服务中进行了为期十天的 online A/B test ，其中 AutoFIS 产生的推荐模型比DeepFM 实现了 20.3% 的CTR 改善、以及 20.1% 的 CVR 改善，这为业务收入的增长做出了巨大贡献。

   综上所述，本文的主要贡献如下：

   • 论文通过经验验证：在训练因子分解模型时，去除冗余的特征交互是有益的。

   • 论文提出了一个两阶段的算法 AutoFIS 来自动选择因子分解模型中重要的低阶特征交互和高阶特征交互。

     • 在搜索阶段，AutoFIS 可以在一个完整的训练过程中通过架构参数学习每个特征交互的相对重要性。

     • 在重训练阶段，移除不重要的交互，作者重新训练得到的神经网络，同时保留架构参数作为注意力单元从而帮助模型的学习。

   • 在三个大规模数据集上的离线实验证明了AutoFIS 在因子分解模型中的优越性能。此外，AutoFIS 还可以找到一组重要的高阶特征交互，以提升现有模型的性能，而没有引入太多的计算成本。一个为期十天的 online A/B test 表明，AutoFIS 在 CTR 和 CVR 方面将 DeepFM 模型平均提高了约 20% 。

2. 相关工作：

   • factorization machine: FM 将每个特征投影到一个低维向量中，并通过内积来建模特征交互，这对于稀疏的数据来说效果很好。Field-aware factorization machine: FFM 进一步使每个特征有多个 vector representation 从而与其他 field 的特征进行交互。

   • 最近，深度学习模型在一些公共 benchmark 上取得了 SOTA 的性能。有几个模型使用 MLP 来改进 FM，如 Attention FM、Neural FM 。

     • Wide & Deep 联合训练了一个 wide 模型（采用人工特征）、和一个 deep 模型（采用原始特征）。

     • DeepFM 使用一个 FM layer 来代替 Wide & Deep 中的 wide 组件。

     • PNN 使用 MLP 来建模 FM layer 和 feature embeddings 的交互，而 PIN 引入了 network-in-network 架构来建模 pairwise 特征交互，而不是 PNN 和 DeepFM 的内积操作。

       PNN 用内积/外积来建模 feature embeddings 的交互。

     需要注意的是：现有的因子分解模型都是简单地枚举所有二阶的特征交互，其中包含了许多无用的和噪音的交互。

   • gradient boosting decision tree: GBDT 是一种通过决策树算法进行特征工程和搜索交互的方法。然后，转换后的特征交互可以被送入逻辑回归或 FFM 模型。在实践中，树状模型更适合于连续数据，但不适合推荐系统中的高维 categorical data ，因为 categorical feature 的使用率很低。

   • 同时，也有一些工作使用 AutoML 技术来处理推荐系统中的问题。人们提出了 AutoCross 在许多候选特征的子集上进行搜索，从而识别有效的交互。这需要训练整个模型来评估每一个所选择的特征交互，但候选集多得令人难以置信：例如，对于一个有 $m$$m$ 个 field 的数据集，仅仅考虑二阶特征交互就有 $2^{C_m^2}$$2^{C_m^2}$ 个候选集合。因此，AutoCross 通过两个方面的近似来加速：

     • 它通过树状结构中的 beam search 贪心地构建局部最优的特征集合。

     • 它通过 field-aware LR 模型来评估新生成的特征集合。

     由于这两种近似，从 AutoCross 中提取的高阶特征交互可能对深度模型没有用。

     与 AutoCross 相比，我们提出的 AutoFIS 只需要执行一次搜索阶段来评估所有特征交互的重要性，这要高效得多。此外， AutoFIS 学到的有用的交互将改善深度模型，因为这些特征交互是在该深度模型中直接学习和评估的。

   • 最近， one-shot 架构搜索方法（如 DARTS）已经成为最流行的神经架构搜索（neural architecture search: NAS）算法，以有效地搜索网络架构。在推荐系统中，这种方法被用来为协同过滤模型搜索适当的交互函数。《Efficient Neural Interaction Function Search for Collaborative Filtering》 中的模型主要是为特征交互识别适当的交互函数，而我们的模型主要是搜索和保留重要的特征交互。

     受最近用于神经架构搜索的 DARTS 工作的启发，我们将搜索有效特征交互的问题表述为一个包含架构参数（architecture parameters）的连续搜索问题。与 DARTS 使用 two-level optimization 来交替优化架构参数和模型权重，并通过训练集和验证集进行迭代不同，我们使用 one-level optimization 来联合训练这两类参数，并以所有数据作为训练集。

1.1 模型

1.1.1 Factorization Model: Base Model

1. 因子分解模型是指：通过内积或神经网络等操作将来自不同特征的几个 embedding 的交互建模为一个实数。我们将 FM 、DeepFM和 IPNN 作为实例来描述我们的算法，并探索在各种数据集上的性能。下图展示了 FM 、DeepFM和 IPNN 模型的结构。

   • FM 由一个 feature embedding layer 和一个 feature interaction layer 组成。

   • DeepFM 和 IPNN 模型除了 feature embedding layer 、 feature interaction layer 之外，还有一个额外的 MLP layer。DeepFM 和 IPNN 的区别在于：在 DeepFM 中，feature interaction layer 和 MLP layer 是并行工作的，而在 IPNN 中是堆叠排列的。

   

2. Feature Embedding Layer：在大多数 CTR 预测任务中，数据是以 multi-field categorical form 收集的。一个典型的数据预处理是：通过 one-hot encoding 或 multi-hot encoding 将每个数据实例转化为高维稀疏向量。只有当一个 field 是 multivariate 的时候，它才被表示为 multi-hot encoding vector 。一个数据样本可以被表示为：

   $$\overrightarrow{\mathbf{x}}=[{\overrightarrow{\mathbf{x}}}_1,{\overrightarrow{\mathbf{x}}}_2,\cdots ,{\overrightarrow{\mathbf{x}}}_m]$$

   其中： $m$$m$ 为 field 数量，${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 为第 $i$$i$ 个 field 的 one-hot/multi-hot encoding vector 。

   feature embedding layer 用于将 encoding vector 转化为低维向量，即：

   $${\overrightarrow{\mathbf{e}}}_i={\mathbf{V}}_i{\overrightarrow{\mathbf{x}}}_i\in {\mathbb{R}}^d$$

   其中：${\mathbf{V}}_i\in {\mathbb{R}}^{d\times n_i}$$\mathbf V_i\in \mathbb R^{d\times n_i}$ 为第 $i$$i$ 个 field 的 embedding 矩阵；$n_i$$n_i$ 为第 $i$$i$ 个 field 的 feature value 数量；$d$$d$ 为低维向量的维度。

   • 如果 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 为 one-hot encoding vector，其中第 $j$$j$ 个元素为 1，那么 ${\overrightarrow{\mathbf{e}}}_i={\overrightarrow{\mathbf{v}}}_i^{(j)}$$\mathbf{\vec e}_i = \mathbf{\vec v}_i^{(j)}$ ，其中 ${\overrightarrow{\mathbf{v}}}_i^{(j)}\in {\mathbb{R}}^d$$\mathbf{\vec v}_i^{(j)}\in \mathbb R^d$ 为 ${\mathbf{V}}_i$$\mathbf V_i$ 的第 $j$$j$ 列。

   • 如果 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$为 multi-hot encoding vector ，其中第 $\{j_1,\cdots ,j_{i_k}\}$$\{j_1,\cdots,j_{i_k}\}$ 个元素为 1，那么：${\overrightarrow{\mathbf{e}}}_i=\sum _{j\in \{j_1,\cdots ,j_{i_k}\}}{\overrightarrow{\mathbf{v}}}_i^{(j)}$$\mathbf{\vec e}_i = \sum_{j\in \{j_1,\cdots,j_{i_k}\}}\mathbf{\vec v}_i^{(j)}$ （sum 池化）或者 ${\overrightarrow{\mathbf{e}}}_i=\frac{1}{i_k}\sum _{j\in \{j_1,\cdots ,j_{i_k}\}}{\overrightarrow{\mathbf{v}}}_i^{(j)}$$\mathbf{\vec e}_i =\frac{1}{i_k} \sum_{j\in \{j_1,\cdots,j_{i_k}\}}\mathbf{\vec v}_i^{(j)}$ （均值池化）。

   feature embedding layer 的输出为多个 embedding 向量的拼接：$\overrightarrow{\mathbf{e}}=[{\overrightarrow{\mathbf{e}}}_1,{\overrightarrow{\mathbf{e}}}_2,\cdots ,{\overrightarrow{\mathbf{e}}}_m]\in {\mathbb{R}}^{md}$$\mathbf{\vec e} = \left[\mathbf{\vec e}_1,\mathbf{\vec e}_2,\cdots,\mathbf{\vec e}_m\right]\in \mathbb R^{md}$ 。

3. Feature Interaction Layer：将特征转换到低维空间后，可以用 feature interaction layer 在这样的空间中建模特征交互。

   • 首先，计算pairwise特征交互的内积：

     $$[<{\overrightarrow{\mathbf{e}}}_1,{\overrightarrow{\mathbf{e}}}_2>,<{\overrightarrow{\mathbf{e}}}_1,{\overrightarrow{\mathbf{e}}}_3>,\cdots ,<{\overrightarrow{\mathbf{e}}}_{m-1},{\overrightarrow{\mathbf{e}}}_m>]$$

     其中：${\overrightarrow{\mathbf{e}}}_i$$\mathbf{\vec e}_i$ 为第 $i$$i$ 个 field 的 feature embedding；$<\cdot ,\cdot >$$<\cdot,\cdot>$ 为两个向量的内积。

     这里 pairwise特征交互的数量为 $C_m^2$$C_m^2$ 。

     可以根据 $\sum x_i{x}_j=(\sum x_i{)}^2-(\sum x_i^2)$$\sum x_ix_j=(\sum x_i)^2 - (\sum x_i^2)$ 进行简化，此时的计算复杂度降低到 $O(m)$$O(m)$ 。

   • 然后，在 FM 和 DeepFM 模型中，feature interaction layer 的输出为：

     $$l_{\text{fm}}=<\overrightarrow{\mathbf{w}},\overrightarrow{\mathbf{x}}>+\sum _{i=1}^m\sum _{j>i}^m<{\overrightarrow{\mathbf{e}}}_i,{\overrightarrow{\mathbf{e}}}_j>\in \mathbb{R}$$

     在这里，所有的特征交互以相同的贡献被传递到下一层。正如前面内容所指出的（并将在实验部分得到验证），并非所有的特征交互都具有同等的预测性，无用的特征交互甚至会降低性能。因此，我们提出了 AutoFIS 算法来有效选择重要的特征交互。

   • 为了研究我们的方法是否可以用来识别重要的高阶特征交互，我们将具有三阶交互（即三个 field 的组合）的 feature interaction layer 定义为：

     $$l_{\text{fm}}^{\text{3rd}}=<\overrightarrow{\mathbf{w}},\overrightarrow{\mathbf{x}}>+\sum _{i=1}^m\sum _{j>i}^m<{\overrightarrow{\mathbf{e}}}_i,{\overrightarrow{\mathbf{e}}}_j>+\sum _{i=1}^m\sum _{j>i}^m\sum _{t>j}^m<{\overrightarrow{\mathbf{e}}}_i,{\overrightarrow{\mathbf{e}}}_j,{\overrightarrow{\mathbf{e}}}_t>\in \mathbb{R}$$

     其中 $<\overrightarrow{\mathbf{a}},\overrightarrow{\mathbf{b}},\overrightarrow{\mathbf{c}}>=\sum _{s=1}^d{a}_i\times b_i\times c_i$$<\mathbf{\vec a}, \mathbf{\vec b}, \mathbf{\vec c}> = \sum_{s=1}^d a_i\times b_i\times c_i$ 。

4. MLP Layer：MLP Layer 由若干个带激活函数的全连接层组成，它学习特征的 relationship 和 combination 。单层 MLP Layer 的输出为：

   $${\overrightarrow{\mathbf{h}}}^{(l+1)}=\text{relu}({\mathbf{W}}^{(l)}{\overrightarrow{\mathbf{h}}}^{(l)}+{\overrightarrow{\mathbf{b}}}^{(l)})$$

   其中：${\overrightarrow{\mathbf{h}}}^{(l)}$$\mathbf{\vec h}^{(l)}$ 为第 $l$$l$ 层的输入； ${\mathbf{W}}^{(l)},{\overrightarrow{\mathbf{b}}}^{(l)}$$\mathbf W^{(l)}, \mathbf{\vec b}^{(l)}$ 为第 $l$$l$ 层的权重和 bias ；relu 为 relu 激活函数。

5. Output Layer：

   • FM 模型没有 MLP Layer，它直接将 feature interaction layer 和 prediction layer 相连：

     $${\hat{y}}_{\text{FM}}=\text{sigmoid}\left(l_{\text{fm}}\right)=\frac{1}{1+\exp (-l_{\text{fm}})}$$

     其中：${\hat{y}}_{\text{FM}}$$\hat y_\text{FM}$ 为 predicted CTR 。

   • DeepFM 以并行的方式将 feature interaction layer 和 MLP layer 进行组合：

     $${\hat{y}}_{\text{DeepFM}}=\text{sigmoid}(l_{\text{fm}}+\text{MLP}(\overrightarrow{\mathbf{e}}))$$

   • IPNN 以堆叠的方式将 feature interaction layer 和 MLP layer 进行组合：

     $${\hat{y}}_{\text{IPNN}}=\text{sigmoid}(\text{MLP}([\overrightarrow{\mathbf{e}},l_{\text{fm}}]))$$

     请注意，IPNN 的 MLP layer 也可以作为不同特征交互的 re-weighting ，从而捕获其相对重要性。这也是 IPNN 比 FM 和DeepFM 有更高容量的原因。然而，在 IPNN 的公式中，人们无法检索到对应于每个特征交互的相对贡献的精确值。因此，IPNN 中无用的特征交互既不能被识别、也不能被丢弃，这给模型带来了额外的噪声和计算成本。

6. Objective Function：FM、DeepFM 和 IPNN 有着相同的目标函数，即最小化预测值和标签的交叉熵：

   $$\mathcal{L}(y,{\hat{y}}_M)=-y\log {\hat{y}}_M-(1-y)\log (1-{\hat{y}}_M)$$

   其中：$y\in \{0,1\}$$y\in \{0,1\}$ 为 label；$0\le {\hat{y}}_M\le 1$$0\le \hat y_M \le 1$ 为预测 $y=1$$y=1$ 的概率。

1.1.2 AutoFIS

1. AutoFIS 自动选择有用的特征交互，可以应用于任何因子分解模型的 feature interaction layer 。AutoFIS 可以分为两个阶段：

   • 搜索阶段（ search stage）：检测有用的特征交互

   • 重训练阶段（ re-train stage）：对具有选定特征交互的模型进行重训练。

   核心思想：根据 data-driven 的权重 $\alpha$$\alpha$ 来学习 field 交互特征的重要性，并裁剪不重要的 field 交互特征。

   AutoFIS 和 AFM 很类似，它们都是学习每个交互特征的重要性，然而：

   • AutoFIS 通过自由参数来描述交互特征的重要性，可以视为 global-level 的建模。

   • AFM 通过 attention 机制来描述交互特征的重要性，可以视为 sample-level 的建模。理论上而言，对于给定的 field-pair，我们可以统计所有样本在它上面的注意力权重，从而得到 global-level 的重要性。

   • 此外，AFM 用逐元素乘积来描述交互特征，而 AutoFIS 用内积。

a. 搜索阶段

1. 为了便于介绍算法，我们引入了 gate 操作来控制是否选择一个特征交互：一个打开的 gate 对应于选择一个特征交互，而一个关闭的 gate 则导致丢弃一个特征交互。所有二阶特征交互对应的 gate 的总数为 $C_m^2$$C_m^2$ 。要想以暴力的方式找到最佳的 open gate 的集合是非常具有挑战性的，因为我们面临着一个难以置信的巨大空间 $O\left(2^{C_m^2}\right)$$O\left(2^{C_m^2}\right)$ 来搜索。

   在这项工作中，我们从不同的角度来处理这个问题：我们不是在一个离散的 open gate 的集合上进行搜索，而是通过引入架构参数 $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ 将 choice 放宽为连续的，这样就可以通过梯度下降学习每个特征交互的相对重要性。下图显示了所提出的 AutoFIS 的概览。

   

2. 这种通过梯度学习的架构选择方案受到 DARTS的启发，其中，DARTS 的目标是从卷积神经网络架构的一组候选操作中选择一个操作。具体而言，我们将因子分解模型中的 interaction layer 重新表述为：

   $$l_{\text{AutoFIS}}=<\overrightarrow{\mathbf{w}},\overrightarrow{\mathbf{x}}>+\sum _{i=1}^m\sum _{j>i}^m{\alpha }_{(i,j)}\times <{\overrightarrow{\mathbf{e}}}_i,{\overrightarrow{\mathbf{e}}}_j>$$

   其中：$\overrightarrow{\mathit{\alpha }}=\{{\alpha }_{(1,2)},\cdots ,{\alpha }_{(m-1,m)}\}$$\vec {\boldsymbol\alpha} = \{\alpha_{(1,2)},\cdots,\alpha_{(m-1,m)}\}$ 为架构参数。

   在 AutoFIS 的搜索阶段，我们可以学习 ${\alpha }_{(i,j)}$$\alpha_{(i,j)}$ 使得它代表每个特征交互对最终预测的相对贡献。然后，我们可以通过将那些不重要的特征交互（即 ${\alpha }_{(i,j)}=0$$\alpha_{(i,j)} = 0$ ）关闭从而决定每个特征交互的 gate 状态。

   如何确保 $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ 的稀疏性？论文采用特殊的优化器 GRDA Optimizer 来实现。

   此外，是否可以保留最重要的 field ，而不仅仅是最重要的 field pair ？实际上，如果 field $i$$i$ 的线性项权重 $w_i=0$$w_i = 0$ 、交互项权重 $\{{\alpha }_{i,1},\cdots ,{\alpha }_{i,m}\}$$\{\alpha_{i,1},\cdots,\alpha_{i,m}\}$ 全部都接近零（或者等于零），那么 field $i$$i$ 就可以被裁剪掉。

3. Batch Normalization：从整个神经网络的角度来看，特征交互的贡献由 ${\alpha }_{(i,j)}\times <{\overrightarrow{\mathbf{e}}}_i,{\overrightarrow{\mathbf{e}}}_j>$$\alpha_{(i,j)}\times <\mathbf{\vec e}_i, \mathbf{\vec e}_j>$ 来衡量。但是，完全相同的贡献可以通过重新缩放来实现：$\left(\frac{{\alpha }_{(i,j)}}{\eta }\right)\times (\eta <{\overrightarrow{\mathbf{e}}}_i,{\overrightarrow{\mathbf{e}}}_j>)$$\left(\frac{\alpha_{(i,j)}}{\eta}\right)\times \left(\eta <\mathbf{\vec e}_i, \mathbf{\vec e}_j>\right)$ ，其中 $\eta$$\eta$ 为任意非零的实数。

   由于 $<{\overrightarrow{\mathbf{e}}}_i,{\overrightarrow{\mathbf{e}}}_j>$$<\mathbf{\vec e}_i, \mathbf{\vec e}_j>$ 的值是与 ${\alpha }_{(i,j)}$$\alpha_{(i,j)}$ 共同学习的，它们的 scale 耦合会导致对 ${\alpha }_{(i,j)}$$\alpha_{(i,j)}$ 的不稳定估计，这样 ${\alpha }_{(i,j)}$$\alpha_{(i,j)}$ 就不能再代表 $<{\overrightarrow{\mathbf{e}}}_i,{\overrightarrow{\mathbf{e}}}_j>$$<\mathbf{\vec e}_i, \mathbf{\vec e}_j>$ 的相对重要性。为了解决这个问题，我们对 $<{\overrightarrow{\mathbf{e}}}_i,{\overrightarrow{\mathbf{e}}}_j>$$<\mathbf{\vec e}_i, \mathbf{\vec e}_j>$ 应用 Batch Normalization: BN 来消除其 scale 问题。

   原始的 BN 采用 mini-batch 统计量从而对 activated output 进行标准化。具体而言：

   $$\widehat{\overrightarrow{\mathbf{z}}}=\frac{{\overrightarrow{\mathbf{z}}}_{\text{in}}-{\overrightarrow{\mu }}_{\mathcal{B}}}{\sqrt{{\overrightarrow{\sigma }}_{\mathcal{B}}^2+ϵ}},{\overrightarrow{\mathbf{z}}}_{\text{out}}=\overrightarrow{\theta }\odot \widehat{\overrightarrow{\mathbf{z}}}+\overrightarrow{\beta }$$

   其中：${\overrightarrow{\mathbf{z}}}_{\text{in}}$$\mathbf{\vec z}_\text{in}$ 为 BN 层的输入；${\overrightarrow{\mathbf{z}}}_{\text{out}}$$\mathbf{\vec z}_\text{out}$ 为 BN 层的输出；${\overrightarrow{\mu }}_{\mathcal{B}}$$\vec\mu_\mathcal B$ 和 ${\overrightarrow{\sigma }}_{\mathcal{B}}^2$$\vec \sigma_\mathcal B^2$ 为 ${\overrightarrow{\mathbf{z}}}_{\text{in}}$$\mathbf{\vec z}_\text{in}$ 在 mini-batch $\mathcal{B}$$\mathcal B$ 上的均值和标准差；$\overrightarrow{\theta },\overrightarrow{\beta }$$\vec\theta,\vec\beta$ 为 BN 层的可训练的 scale/shift parameters；$ϵ$$\epsilon$ 为一个小的常数从而用于数值稳定性；$\odot$$\odot$ 以及除法都是逐元素进行的。

   为了获得对 ${\alpha }_{(i,j)}$$\alpha_{(i,j)}$ 的稳定估计，我们将 scale/shift parameters 分别设为 1 和 0 。对每个特征交互$<{\overrightarrow{\mathbf{e}}}_i,{\overrightarrow{\mathbf{e}}}_j>$$<\mathbf{\vec e}_i, \mathbf{\vec e}_j>$ 的 BN 操作计算如下：

   $$<{\overrightarrow{\mathbf{e}}}_i,{\overrightarrow{\mathbf{e}}}_j{>}_{\text{BN}}=\frac{<{\overrightarrow{\mathbf{e}}}_i,{\overrightarrow{\mathbf{e}}}_j>-{\mu }_{\mathcal{B}}(<{\overrightarrow{\mathbf{e}}}_i,{\overrightarrow{\mathbf{e}}}_j>)}{\sqrt{{\sigma }_{\mathcal{B}}^2(<{\overrightarrow{\mathbf{e}}}_i,{\overrightarrow{\mathbf{e}}}_j>)+ϵ}}$$

   其中：${\mu }_{\mathcal{B}},{\sigma }_{\mathcal{B}}^2$$\mu_\mathcal B, \sigma_\mathcal B^2$ 为 $<{\overrightarrow{\mathbf{e}}}_i,{\overrightarrow{\mathbf{e}}}_j>$$<\mathbf{\vec e}_i, \mathbf{\vec e}_j>$ 在 mini-batch $\mathcal{B}$$\mathcal B$ 上的均值和标准差。

4. GRDA Optimizer：generalized regularized dual averaging: GRDA 优化器旨在获得一个稀疏的深度神经网络。为了在每个梯度step $t$$t$ 用数据 ${\mathbb{Z}}_t$$\mathbb Z_t$ 更新 $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ ，我们使用以下公式：

   $${\overrightarrow{\mathit{\alpha }}}_{t+1}=\arg \underset{\overrightarrow{\mathit{\alpha }}}{min}\left\{{\overrightarrow{\mathit{\alpha }}}^{\mathrm{\top }}(-{\overrightarrow{\mathit{\alpha }}}_0+\gamma \sum _{i=0}^t\mathrm{\nabla }\mathcal{L}({\overrightarrow{\mathit{\alpha }}}_t;{\mathbb{Z}}_{i+1})+g(t,\gamma ){\Vert \overrightarrow{\mathit{\alpha }}\Vert }_1+\frac{1}{2}{\Vert \overrightarrow{\mathit{\alpha }}\Vert }_2^2)\right\}$$

   其中：$g(t,\gamma )=c{\gamma }^{1/2}(t\gamma {)}^u$$g(t,\gamma) = c\gamma^{1/2}(t\gamma)^u$ ，$\gamma$$\gamma$ 为学习率，$c$$c$ 和 $u$$u$ 为可调的超参数从而权衡准确性和稀疏度。

   在搜索阶段，我们使用 GRDA 优化器来学习架构参数 $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ ，并得到一个稀疏的解决方案。那些不重要的特征交互（即具有零值的 ${\alpha }_{(i,j)}$$\alpha_{(i,j)}$）将被自动丢弃。

   除了 $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ 之外的其他参数由 Adam 优化器学习。

5. One-level Optimization：为了在 AutoFIS 的搜索阶段学习结构参数 ${\alpha }_{(i,j)}$$\alpha_{(i,j)}$ ，我们建议将 $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ 与所有其他网络权重共同优化。这与DARTS 不同。DARTS 将$\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ 作为 higher-level 决策变量、将网络权重 $\mathrm{\Theta }$$\Theta$ 作为lower-level 变量，然后用 bi-level 优化算法对其进行优化。在 DARTS 中，假设只有当网络权重被正确学习后，模型才能选择操作，从而使 $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ 能够 "做出正确的决定"。

   在 AutoFIS 的公式中，这意味着我们可以在网络权重被正确训练后决定 gate 应该打开还是关闭，这使我们回到了问题：完全训练 $2^{C_m^2}$$2^{C_m^2}$ 个模型来做决策。为了避免这个问题，DARTS 建议只用一个梯度下降步来近似计算网络权重的最优值，并迭代地训练 $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ 和 $\mathrm{\Theta }$$\Theta$ 。

   我们认为，这种近似的不精确性可能会降低性能。因此，我们建议不使用 bi-level 优化，而是用 one-level 优化来联合优化 $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ 和 $\mathrm{\Theta }$$\Theta$ 。具体而言，参数 $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ 和 $\mathrm{\Theta }$$\Theta$ 使用训练集通过梯度下降一起更新，基于：

   $${\mathrm{\nabla }}_{\mathrm{\Theta }}{\mathcal{L}}_{\text{train}}({\mathrm{\Theta }}_{t-1},{\overrightarrow{\mathit{\alpha }}}_{t-1}),{\mathrm{\nabla }}_{\overrightarrow{\mathit{\alpha }}}{\mathcal{L}}_{\text{train}}({\mathrm{\Theta }}_{t-1},{\overrightarrow{\mathit{\alpha }}}_{t-1})$$

   在这种情况下， $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ 和 $\mathrm{\Theta }$$\Theta$ 可以自由地探索它们的设计空间，直到收敛，并且 $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ 被学习作为单个特征交互的贡献。

   在实验部分中，我们将展示 one-level optimization 比 two-level optimization 的优越性。

b. 重训练阶段

1. 在搜索阶段的训练结束后，根据搜索阶段的架构参数 ${\overrightarrow{\mathit{\alpha }}}^{\ast }$$\vec {\boldsymbol\alpha}^*$ ，一些不重要的交互被自动丢弃。我们用 $G_{(i,j)}$$G_{(i,j)}$ 表示特征交互$<{\overrightarrow{\mathbf{e}}}_i,{\overrightarrow{\mathbf{e}}}_j>$$<\mathbf{\vec e}_i, \mathbf{\vec e}_j>$ 的 gate 状态，当 ${\alpha }_{(i,j)}^{\ast }=0$$\alpha^*_{(i,j)}=0$ 时，将 $G_{(i,j)}=0$$G_{(i,j)} = 0$；否则 $G_{(i,j)}=1$$G_{(i,j)} = 1$。在重训练阶段，这些不重要的特征交互的 gate 状态被固定为永久关闭。

   在移除这些不重要的交互后，我们重新训练新的模型。具体来说， feature interaction layer 被替换为：

   $$l_{\text{fm}}^{\text{re}}=<\overrightarrow{\mathbf{w}},\overrightarrow{\mathbf{x}}>+\sum _{i=1}^m\sum _{j>i}^m{\alpha }_{(i,j)}\times G_{(i,j)}\times <{\overrightarrow{\mathbf{e}}}_i,{\overrightarrow{\mathbf{e}}}_j>$$

   注意这里 $\alpha (i,j)$$\alpha(i,j)$ 不再作为决定一个特征交互是否应该包括在模型中的指标（如搜索阶段）。取而代之的是，它作为一个注意力单元，让架构学习被保留下来的特征交互的相对重要性。在这个阶段，我们不需要选择特征交互。因此，所有的参数都由 Adam 优化器学习。

   这里 $G_{i,j}$$G_{i,j}$ 被初始化为 0 或 1 （根据特征交互的选择的结果），并且在训练过程中保持不变。

   重训练阶段，所有参数（包括 $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ ）都用 Adam 优化器来优化。

1.2 实验

1. 数据集：两个 public 数据集（Avazu, Criteo ）、一个 private 数据集。

   • Avazu：在 Kaggle 的 CTR 预估竞赛中被发布。随机拆分80% 的数据作为训练和验证，剩余 20% 用于测试。出现次数少于 20 次的 categories 将被删除从而进行降维。

   • Criteo：包含一个月的点击日志，有数十亿的数据样本。我们选择 "data 6-12" 作为训练集和验证集，同时选择 "day-13" 进行评估。为了应对标签的不平衡，我们采用了负降采样的方法，使正样本比例大致保持在 50% 左右。13 个数值字段通过分桶被转换为 one-hot 特征，其中某个字段中出现少于 20 次的特征被设置为 dummy feature "other" 。

     如何分桶？论文并未说明。

   • Private：从华为应用商店的游戏推荐场景中收集的。该数据集包含 app 特征（如 ID, category ），用户特征（如用户的行为历史）和上下文特征。

   数据集统计结果如下表所示。

   

2. baseline：我们将 AutoFIS 应用于 FM 和 DeepFM 模型以显示其有效性（分别表示为 AutoFM 和 AutoDeepFM ）。

   baseline 方法为：GBDT-based 的方法（ GBDT+LR, GBDT+FFM），FM 模型（AFM, FwFM, FFM, IPNN）。

   由于其巨大的计算成本和源代码的不可用，我们没有将我们的模型与 AutoCross 进行比较。

3. 评估指标：AUC, Log loss 。

4. 超参数配置：

   

5. 实现细节：

   • 为 AutoFM 和 AutoDeepFM 选择二阶特征交互：在搜索阶段，我们首先在所有训练数据上联合训练 $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ 和 $\mathrm{\Theta }$$\Theta$ 。然后，我们删除无用的交互，重新训练我们的模型。

   • 为 AutoFM 和 AutoDeepFM 选择三阶特征交互：我们复用所选中的二阶交互，并在搜索阶段枚举三阶特征交互从而学习其重要性。最后，我们用选中的二阶交互和三阶交互来重新训练我们的模型。

   注意，在搜索阶段，架构参数 $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ 由 GRDA 优化器优化，而其他参数 $\mathrm{\Theta }$$\Theta$ 由 Adam 优化器优化。在重新训练阶段，所有参数都由 Adam 优化器优化。

6. AutoFIS 选择的特征交互：Table 1 和 Table3 总结了 AutoFM 和 AutoDeepFM 在 Avazu, Criteo, Private 数据集上自动选择二阶重要交互和三阶重要交互的性能。可以看到：

   • 对于 Avazu 数据集，FM/DeepFM 分别可以移除 71%/76% 的二阶交互。移除这些无用的交互：

     • 不仅可以使模型在推理时更快：AutoFM(2nd) 和 AutoDeepFM(2nd) 的推理时间明显少于 FM 和 DeepFM 。

     • 而且可以明显提高预测准确性：从 AUC 来看，AutoFM(2nd) 比 FM 的相对性能提高了 0.49% 、AutoDeepFM(2nd) 比 DeepFM 的相对性能提高了 0.20%。

     类似的改进也可以从其他数据集中得出。

   • 对于高阶特征交互的选择，只有 2%-10% 的三阶特征交互需要包含在模型中。

     • AutoFM(3rd) 和 AutoDeepFM(3rd) 的推理时间远远少于 FM(3rd) 和 DeepFM(3rd) （与 FM 和 DeepFM 相当）。

     • 同时，通过移除不重要的三阶特征交互，准确率得到了显著的提高。即在 Avazu 上的 AUC 指标上，AutoFM(3rd) 比 FM(3rd) 的相对性能提高了 0.22% 、AutoDeepFM(3rd) 比 DeepFM(3rd) 提高了 0.20% 。

       对 Criteo 的观察也是如此。

   • 所有这些性能提升都是以边际时间成本（ marginal time cost）实现的。例如，AutoDeepFM(3rd) 在 Avazu 和 Criteo 用一块 GPU 卡搜索重要的二阶特征交互和三阶特征交互需要 24 分钟和 128 分钟。同样的结果可能需要人类工程师花很多小时或几天的时间来手动识别这些重要的特征交互。

   注意，在 FM 和 DeepFM 中直接枚举三阶特征交互会使推理时间增加 7 到 12 倍，这在工业应用中是不可接受的。

   

   

7. 所选特征的可迁移性：我们研究了由 AutoFM （这是一个简单的模型）所学到的特征交互是否可以迁移到 SOTA 的模型（如 IPNN ）从而提高其性能。

   如下表所示：

   • 使用 AutoFM 选择的二阶特征交互（即 AutoIPNN(2nd) ）实现了与 IPNN 相当的性能，在 Avazu 和 Criteo 的所有交互中约占 30% 和 50% 。

   • 使用 AutoFM 选择的二阶特征交互和三阶特征交互（即 AutoIPNN(3rd) ），性能得到明显改善。

   这两个证据都验证了 AutoFM 所选择的特征交互的可迁移性。

   

8. 所选特征的效果：

   • 在真实数据上：我们定义 statistics_AUC 来表示一个特征交互对最终预测的重要性。对于一个给定的特征交互。我们构建一个只考虑该交互的 predictor ，其中 prediction 为训练集中特定特征交互的 statistical CTR （#downloads/#impressions ）。然后，这个 predictor 的 AUC 是相对于这个给定的特征交互的 statistics_AUC 。 statistics_AUC 越高，表明该特征交互在预测中的作用越重要。然后，我们将 statistics_AUC 和 ${\alpha }_{(i,j)}$$\alpha_{(i,j)}$ 值之间的关系可视化。

     即，仅仅以这一对特征作为输入，label 不变。这个 predictor 如何构建？论文并未说明。可以选择 LR 或 FM 模型。

     如下图所示，我们可以发现，被我们模型选中的大多数特征交互（绝对值较高的 ${\alpha }_{(i,j)}$$\alpha_{(i,j)}$）都有较高的 statistics_AUC ，但并非所有具有高 statistics_AUC 的特征交互都被选中。这是因为这些交互中的信息也可能存在于其它交互中，而这些其它交互也被我们模型所选中。

     为了评估我们的模型所选择的特征交互的有效性，我们还根据 statistics_AUC 选择了 top-N 特征交互（ $𝑁$$𝑁$ 是我们的模型所选择的二阶特征交互的数量），并利用这些特征交互重新训练模型。如下表所示，在计算成本相同的情况下，我们的模型的性能远远好于通过 statistics_AUC 选择的特征交互的模型。

     

     

   • 在人工合成数据上：合成数据集是由一个不完整的 poly-2 函数产生的，其中的双线性项类似于 categories 之间的交互。基于这个数据集，我们研究了：我们的模型是否能够找到重要的交互、我们的模型与其他FM 模型相比的性能。

     数据集的输入 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 从 $m$$m$ 个 field 的 $N$$N$ 个类目中随机采样的。输出 $y$$y$ 是 binary 标签：

     $$\begin{array}{c}y=\sigma (\sum _{i=1}^m{w}_i{x}_i+\sum _{(i,j)\in \mathcal{C}}{v}_{i,j}{x}_i{x}_j+b+ϵ)\\ \sigma (z)=\{\begin{array}{ll}1,& \text{ if }z\ge \text{threshold}\\ 0,& \text{ otherwise }\end{array}\end{array}$$

     其中，数据分布 $p(\overrightarrow{\mathbf{x}})$$p(\mathbf{\vec x})$ 、双线性项集合 $\mathcal{C}$$\mathcal C$ 、参数 $\overrightarrow{\mathbf{w}},\overrightarrow{\mathbf{v}},b$$\mathbf{\vec w}, \mathbf{\vec v}, b$ 都是随机采样和固定的。data pair 是独立同分布采样来构建训练集和测试集。我们还在采样的数据中加入一个小的随机噪声 $ϵ$$\epsilon$ 。

     我们使用 FM 和我们的模型来拟合人工合成数据。我们在测试数据集上使用 AUC 来评估这些模型。

     我们选择 $m=6,N=60$$m=6, N=60$ 来测试我们模型的有效性。$\mathcal{C}$$\mathcal C$ 被随机初始化为 $\mathcal{C}=\{(x_0,x_1),(x_2,x_5),(x_3,x_4)\}$$\mathcal C = \{(x_0, x_1), (x_2, x_5), (x_3, x_4)\}$ 。Figure 4 展示了我们的模型与FM 的性能比较，这表明了我们的模型的优越性。

     

     如 Figure 5 所示，我们的模型可以精确地提取重要的特征交互：$\mathcal{C}$$\mathcal C$ 中的交互具有最高的 ${\alpha }_{(i,j)}$$\alpha_{(i,j)}$ 值，一些不重要的特征交互被移除。

     

9. 在线实验：我们在华为应用商店的推荐系统中进行了在线实验，以验证 AutoDeepFM 的卓越性能。

   具体而言，在 App Store 的游戏推荐场景中进行了为期 10 天的 A/B test 。我们在线实验的 baseline 是 DeepFM ，这是一个强大的baseline ，因为它具有优秀的准确性和高效率，已经在商业系统中部署了很长一段时间。

   • 对照组：随机选择 5% 的用户，并向他们展示由 DeepFM 生成的推荐。

   • 实验组：随机选择 5% 的用户，并向他们展示由 AutoDeepFM 生成的推荐。

   Figure 6 和 Figure 7 显示了实验组比对照组在 CTR （#downloads/#impressions ）和 CVR（#downloads/#user ）上的改进。可以看到：

   • 该系统是相当稳定的，在 A/A test 期间，CTR 和 CVR 都在8% 以内波动。

   • 我们的 AutoDeepFM 模型在第 8 天被启动到实时系统中。从第 8 天开始，我们观察到在 CTR 和 CVR 方面比 baseline 模型有明显的改善。在 10 天的 A/B test 中，CTR 的平均改进为 20.3% ，CVR 的平均改进为 20.1% 。这些结果证明了我们所提出的模型的巨大有效性。

   • 从第 18 天开始，我们再次进行 A/A test，在实验组中用 baseline 模型替换我们的 AutoDeepFM 模型。我们观察到实验组的性能急剧下降，这再次验证了实验组在线性能的改善确实是由我们提出的模型引入的。

   

10. 消融研究：

    • 不同随机数种子下 $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ 估计的稳定性：对 $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ 的稳定估计意味着模型的决定（哪种交互是重要）不受随机数种子的影响。我们在Avazu上用不同的随机数种子运行 AutoFM 的搜索阶段。

      由不同随机数种子估计的 $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ 的 Pearson 相关性约为 0.86 ，这验证了 $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ 的估计是稳定的。如果对特征交互不使用 BN ，这个Pearson 相关性会下降到 0.65 左右。

    • AutoFIS 组件的效果：为了验证 AutoFIS 中各个组件的有效性，我们提出了几个变体，如 Table 6 所示。

      • 为了验证AutoFIS搜索阶段的有效性，我们将其与 "Random" 策略（即，随机选择特征交互）进行比较。

      • 在重训练阶段，我们验证了 BN 和 $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ 的优势。

      注意，对于 AutoFM-BN，仅仅是在重训练阶段没有 BN，而在搜索阶段还是用了 BN 的。

      

      Table 7 列出了这些变体的性能。对于 "Random" 策略，我们选择与 AutoFM 相同的交互数量，我们尝试了 10 种不同的 "Random" 策略，并对结果进行了平均。

      结论：

      • 比较 AutoFM-BN-𝛼 和 Random+FM ，我们可以看到：在相同数量的交互下，AutoFIS 的选择总是能取得比随机选择更好的性能。这说明在搜索阶段 AutoFIS 就能识别出重要的交互。

      • 在 Criteo 数据集中，Random+FM 和 FM 之间的性能差距表明：在某些情况下，随机选择的特征交互可能优于保留所有特征交互的模型。这支持了我们的说法：移除一些无用的特征交互可以提高性能。

        类似于 xgboost 中的 feature sample 。

        在 Avazu 数据集中， Random+FM 略逊于 FM 。

      • AutoFM 和 AutoFM-BN 之间的比较验证了 BN 在重训练阶段的有效性，其中的原因在 AutoFIS 章节已经说明。

      • AutoFM-BN 和 AutoFM-BN-𝛼 之间的性能差距表明： $\overrightarrow{\mathit{\alpha }}$$\vec {\boldsymbol\alpha}$ 提高了性能，因为它区分了不同特征交互在重训练阶段的贡献。

      

    • one-level optimization vs bi-level optimization：结果如 Table 8 所示。可以看到：AutoFM 和 Bi-AutoFM （以及AutoDeepFM 和 Bi-AutoDeepFM ）之间的性能差距表明了 one-level optimization 比 bi-level optimization 的优越性，其原因在 one-level optimization 章节已经说明。