三十三、AFN [2020]

1. 手工制作有用的交叉特征是昂贵的、耗时的，而且结果可能无法泛化到未见过的特征交互。为了解决这个问题，人们提出了 Factorization Machine: FM ，通过将交叉特征的权重参数化为原始特征的 embedding 向量的内积从而显式地建模二阶交叉特征。为了更加通用，在最初的工作中还引入了涉及高阶特征组合的高阶FM （HOFM）。

   尽管有卓越的预测能力，但在 FM/HOFM 中仍有两个关键问题需要回答：

   • 首先，我们应该考虑交叉特征的最大阶次是什么？虽然较大的阶次可以建模更复杂的特征交互，并且似乎是有益的，但交叉特征的数量会随着最高阶次的增加而呈指数级增长，从而导致高的计算复杂度。这限制了高阶交叉特征的实际使用。
   • 其次，在最高阶数下有用的交叉特征集合是什么？必须认识到，并非所有的特征都包含针对估计目标的有用信号，不同的交叉特征通常具有不同的预测能力。不相关的特征之间的交互可以被认为是噪音，对预测没有贡献，甚至会降低模型的性能。AFM 通过用注意力分数来 reweighing 每个交叉特征来区分特征交互的重要性。然而，在复杂的特征组合上应用注意力机制会大大增加计算成本。因此，AFM 旨在仅仅建模二阶的特征交互。

   在论文 《Adaptive Factorization Network: Learning Adaptive-Order Feature Interactions》 中，作者认为现有的因子分解方法未能适当地回答上述两个问题。通常而言，现有的因子分解方法是按照列举、以及过滤的方式来建模特征交互：首先定义最大阶次，然后枚举最大阶次以内的所有交叉特征，最后通过训练来过滤不相关的交叉特征。这个过程包括两个主要的缺点：

   • 首先，预设最大阶数（通常较小）限制了模型在寻找有 discriminative 的交叉特征方面的潜力，因为要在表达能力和计算复杂性之间进行 trade-off 。
   • 其次，考虑所有的交叉特征可能会引入噪音并降低预测性能，因为并非所有无用的交叉特征都能被成功过滤掉。

   因此，论文 《Adaptive Factorization Network: Learning Adaptive-Order Feature Interactions》 提出了 Adaptive Factorization Network: AFN，从数据中自适应地学习任意阶次的交叉特征及其权重。其关键思想是：将 feature embedding 编码到一个对数空间中，并将特征的幂次转换为乘法。AFN 的核心是一个对数神经转换层 logarithmic neural transformation layer ，由多个 vector-wise 对数神经元组成。每个对数神经元的目的是：在可能有用的特征组合中，自动学习特征的幂次（即，阶次）。在对数神经转换层上，AFN 应用前馈神经网络来建模 element-wise 的特征交互。与 FM/HOFM 不同的是，AFN 能够自适应地从数据中学习有用的交叉特征，而且最大阶次可以通过数据自动学到。

   论文主要贡献：

   • 据作者所知，他们是第一个将对数转换结构与神经网络结合起来，从而建模任意阶次的特征交互。
   • 基于所提出的对数转换层，作者提出了 AFN 从而从数据中自适应地学习任意阶次的交叉特征及其权重。
   • 作者表明：FM/HOFM 可以被解释为 AFN 的两种特例，并且 AFN 中学到的阶次允许在不同的交叉特征中 rescaling feature embedding 。
   • 论文在四个公共数据集上进行了广泛的实验。结果表明：所学的交叉特征的阶次跨度很大；与 SOTA 方法相比，AFN 取得了卓越的预测性能。

33.1 背景

1. Feature Embedding：遵从传统，我们将每个输入样本表示为一个稀疏的向量：

   $$\begin{array}{}\text{(1)}& \overrightarrow{\mathbf{x}}=[{\overrightarrow{\mathbf{x}}}_1,{\overrightarrow{\mathbf{x}}}_2,\cdots ,{\overrightarrow{\mathbf{x}}}_m]\end{array}$$

   其中：$m$$m$ 为 feature field 的数量，${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 为第 $i$$i$ 个 feature field 的 representation ，$[\cdot ,\cdot ]$$[\cdot,\cdot]$ 为向量的拼接。

   • 由于大多数 categorical features 是稀疏的、高维的，一个常见的做法是将它们映射到低维潜空间中的稠密向量（即，embedding ）。具体而言，一个 categorical feature ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 被初始化为一个 one-hot encoded vector ，然后计算 embedding 向量 ${\overrightarrow{\mathbf{e}}}_i$$\mathbf{\vec e}_i$ ：

     $$\begin{array}{}\text{(2)}& {\overrightarrow{\mathbf{e}}}_i={\mathbf{V}}_i{\overrightarrow{\mathbf{x}}}_i\end{array}$$

     其中 ${\mathbf{V}}_i$$\mathbf V_i$ 为 feature field $i$$i$ 的 embedding matrix 。

   • 对于数值特征 ${\overrightarrow{\mathbf{x}}}_j$$\mathbf{\vec x}_j$ ，它的 representation 是一个标量 $x_j$$x_j$ 。为了捕获数值特征和 categorical feature 之间的交互，$x_j$$x_j$ 也被转换为同一低维空间中的密集向量：

     $$\begin{array}{}\text{(3)}& {\overrightarrow{\mathbf{e}}}_j={\overrightarrow{\mathbf{v}}}_j{x}_j\end{array}$$

     其中：${\overrightarrow{\mathbf{v}}}_j$$\mathbf{\vec v}_j$ 为field $j$$j$ 的 embedding vector （由该 field 内的所有特征取值所共享）。

   最终我们得到 feature embedding 集合 $\mathbf{e}=\{{\overrightarrow{\mathbf{e}}}_1,{\overrightarrow{\mathbf{e}}}_2,\cdots ,{\overrightarrow{\mathbf{e}}}_m\}$$\mathbf{ e} = \left\{\mathbf{\vec e}_1,\mathbf{\vec e}_2,\cdots,\mathbf{\vec e}_m\right\}$ 从而用于 FM 或其他模型。

2. FM：FM 显式建模高维数据的二阶特征交互。从公式上看，FM 的预测为：

   $$\begin{array}{}\text{(4)}& y=<\overrightarrow{\mathbf{w}},\overrightarrow{\mathbf{x}}>+\sum _{j_2>j_1}^m<{\overrightarrow{\mathbf{e}}}_{j_1},{\overrightarrow{\mathbf{e}}}_{j_2}>\end{array}$$

   其中 $<\cdot ,\cdot >$$<\cdot, \cdot>$ 为内积。

   直观地，第一项 $<\overrightarrow{\mathbf{w}},\overrightarrow{\mathbf{x}}>$$<\mathbf{\vec w}, \mathbf{\vec x}>$ 是原始特征的线性组合，第二项是 feature embedding 的 pair-wise 内积之和。

   此外，Higher-Order Factorization Machine: HOFM 用于捕获高阶的特征交互：

   $$\begin{array}{}\text{(5)}& y=<\overrightarrow{\mathbf{w}},\overrightarrow{\mathbf{x}}>+\sum _{j_2>j_1}^m<{\overrightarrow{\mathbf{e}}}_{j_1},{\overrightarrow{\mathbf{e}}}_{j_2}>+\sum _{j_3>j_2>j_1}^m<{\overrightarrow{\mathbf{e}}}_{j_1},{\overrightarrow{\mathbf{e}}}_{j_2},{\overrightarrow{\mathbf{e}}}_{j_3}>+\cdots +\sum _{j_n>\cdots >j_1}^m<{\overrightarrow{\mathbf{e}}}_{j_1},\cdots ,{\overrightarrow{\mathbf{e}}}_{j_n}>\end{array}$$

   其中：$n$$n$ 为交叉特征的最大阶次；内积运算被扩展为多个 feature embedding 的 element-wise 的乘积之和。

   HOFM 的时间复杂度为 $O(k{m}^n)$$O(km^n)$ ，其中 $k$$k$ 为 feature embedding 的维度。由于计算复杂度高，HOFM 很少被应用于真正的工业系统。

   FM 和 HOFM 的一个共同局限性是：它们以相同的权重来建模所有的特征交互。由于并非所有的交叉特征都是有用的，纳入所有的交叉特征进行预测可能会引入噪音并降低模型性能。

   如前所述，一些方法致力于缓解这一问题：AFM 利用注意力机制为不同的交叉特征分配非均匀的权重，xDeepFM 只为保留的交叉特征学习权重。然而，这些方法引入了额外的成本，并且在模型训练前仍被限制在一个预设的最大特征交互阶次 $n$$n$ 。在实践中，$n$$n$ 通常被设置为一个小值，以使模型大小适中。这样的设计阻碍了寻找具有 discriminative 的高阶交叉特征的机会。

   在本文中，我们建议从数据中自适应地学习任意阶交叉特征。最大阶次和交叉特征集合都将通过模型训练自适应地确定，从而在不牺牲预测能力的前提下实现高计算效率。

3. Logarithmic Neural Network: LNN：对数神经网络 Logarithmic Neural Network 最初是为了近似 unbounded 的非线性函数而提出的。LNN 由多个对数神经元组成，其结构如下图所示。从形式上看，一个对数神经元可以表述为：

   $$\begin{array}{}\text{(6)}& y=\exp (\sum _i{w}_i\ln x_i)=\prod _i{x}_i^{w_i}\end{array}$$

   LNN 的理念是将输入转换到对数空间，将乘法转化为加法，除法转化为减法，幂次转化为乘法。尽管多层感知机（multi-layer perceptron: MLP）是众所周知的通用函数逼近器，但当输入无界时，它们在逼近某些函数如乘法、除法和幂次方面的能力有限。相反，LNN 能够在整个输入范围内很好地逼近这些函数。

   在本文中，我们利用对数神经元来自适应地学习数据中交叉特征的每个feature field的幂次。我们强调 LNN 和我们提出的 AFN 之间的三个关键区别：

   • AFN 学到的幂次被应用到 vector-wise level ，并且在相同 field 的所有 feature embedding 之间共享。

   • 我们模型的输入是待学习的 feature embedding 。因此，我们需要使用一些技术来保持梯度稳定，并学习适当的 feature embedding 和 combination 。

   • 在 AFN 中，我们在学到的交叉特征上进一步应用前馈隐层，以增强我们模型的表达能力。

     AFN 有几个显著的缺点：

     • 要求 embedding 为正数，这对模型施加了很强的约束。
     • 由于大多数 embedding 在零值附近，一个很微小的扰动（如计算精度导致的计算误差）就可能对模型产生影响，因此读者猜测模型难以训练。

   

33.2 模型

1. AFN 的整体结构如下图所示。

   • Input Layer and Embedding Layer：AFN 的 inpyt layer 同时采用 sparse categorical feature 和 numerical feature 。如前所述，所有的原始输入特征首先被转换为共享潜在空间的 embedding。

     这里我们介绍两个实现 embedding layer 的关键技术：

     • 首先，由于我们将对后续的层中的 feature embedding 进行对数转换，我们需要保持 embedding 中的所有数值为正数。

       如何确保 embedding 中的所有数值都是正的？论文没有说明。此外，embedding 非负，这对模型施加了一个很强的约束。然后，即使采用了非负的 embedding，然后对于接近零的 embedding，它的 “对数--指数” 变换非常敏感，一个很微小的扰动（如计算精度导致的计算误差）就可能对模型产生影响，因此读者猜测模型较难训练。

     • 其次，建议在 zero embedding 中加入一个小的正值（如 ${10}^{-7}$$10^{-7}$）从而避免数值溢出。

     最后，embedding layer 的输出是 positive feature embedding 的一个集合：$\mathbf{e}=\{{\overrightarrow{\mathbf{e}}}_1,{\overrightarrow{\mathbf{e}}}_2,\cdots ,{\overrightarrow{\mathbf{e}}}_m\}$$\mathbf{ e} = \left\{\mathbf{\vec e}_1,\mathbf{\vec e}_2,\cdots,\mathbf{\vec e}_m\right\}$ 。

   • Logarithmic Transformation Layer：AFN 的核心是对数转换层 logarithmic transformation layer，它学习交叉特征中每个 feature field的幂（即阶次）。该层由多个 vector-wise 的对数神经元组成，第 $j$$j$ 个 vector-wise 对数神经元的输出为：

     $$\begin{array}{}\text{(7)}& {\overrightarrow{\mathbf{y}}}_j=\exp (\sum _{i=1}^m{w}_{i,j}\ln {\overrightarrow{\mathbf{e}}}_i)={\overrightarrow{\mathbf{e}}}_1^{w_{1,j}}\odot {\overrightarrow{\mathbf{e}}}_2^{w_{2,j}}\odot \cdots \odot {\overrightarrow{\mathbf{e}}}_m^{w_{m,j}}\end{array}$$

     其中：$w_{i,j}$$w_{i,j}$ 为第 $j$$j$ 个神经元在第 $i$$i$ 个 feature field 上的系数；$\ln (\cdot )$$\ln(\cdot)$ 和 $\exp (\cdot )$$\exp(\cdot)$ 以及幂次 $(\cdot {)}^{w_{i,j}}$$(\cdot)^{w_{i,j}}$ 都是 element-wise 的；$\odot$$\odot$ 为逐元素乘法。

     对上式的主要观察是：每个对数神经元 ${\overrightarrow{\mathbf{y}}}_j$$\mathbf{\vec y}_j$ 的输出能够代表任何交叉特征。例如，当 $w_{1,j}=w_{2,j}=1$$w_{1,j} = w_{2,j} = 1$，而 $w_{i,j}=0,3\le i\le m$$w_{i,j} = 0, \quad 3\le i \le m$ 时，我们有 ${\overrightarrow{\mathbf{y}}}_j={\overrightarrow{\mathbf{e}}}_1\odot {\overrightarrow{\mathbf{e}}}_2$$\mathbf{\vec y}_j = \mathbf{\vec e}_1\odot \mathbf{\vec e}_2$，这是前两个原始 feature field 的二阶交叉特征。因此，我们可以使用多个对数神经元来获得任意阶次的不同 feature combination 作为该层的输出。

     注意，系数矩阵 ${\mathbf{W}}_{\text{LTL}}\in {\mathbb{R}}^{m\times N}$$\mathbf W_\text{LTL}\in \mathbb R^{m\times N}$ 为可学习的参数并且没必要收敛到 0 或 1 ，其中 $N$$N$ 为该层的对数神经元的数量。

   • Feed-forward Hidden Layers and Prediction：在对数转换层上，我们堆叠了几个全连接层从而组合所得到的交叉特征。

     • 我们首先将所有的交叉特征拼接起来作为前馈神经网络的输入：

       $$\begin{array}{}\text{(8)}& {\overrightarrow{\mathbf{z}}}_0=[{\overrightarrow{\mathbf{y}}}_1,{\overrightarrow{\mathbf{y}}}_2,\cdots ,{\overrightarrow{\mathbf{y}}}_N]\end{array}$$

       其中： $N$$N$ 为前一层的对数神经元的数量，$[\cdot ,\cdot ]$$[\cdot,\cdot]$ 表示向量拼接操作。

     • 然后我们将 ${\overrightarrow{\mathbf{z}}}_0$$\mathbf{\vec z}_0$ 馈入到 $L$$L$ 个隐层：

       $$\begin{array}{}\text{(9)}& \begin{array}{c}{\overrightarrow{\mathbf{z}}}_1=\text{ReLU}({\mathbf{W}}_1{\overrightarrow{\mathbf{z}}}_0+{\overrightarrow{\mathbf{b}}}_1)\\ \cdots \\ {\overrightarrow{\mathbf{z}}}_L=\text{ReLU}({\mathbf{W}}_L{\overrightarrow{\mathbf{z}}}_{L-1}+{\overrightarrow{\mathbf{b}}}_L)\end{array}\end{array}$$

       其中：${\mathbf{W}}_L$$\mathbf W_L$ 和 ${\overrightarrow{\mathbf{b}}}_L$$\mathbf{\vec b}_L$ 分别表示第 $L$$L$ 层的权重矩阵和偏置向量。

     • 最后，隐层的输出 ${\overrightarrow{\mathbf{z}}}_L$$\mathbf{\vec z}_L$ 被转换为最终预测值 $\hat{y}$$\hat y$ ：

       $$\begin{array}{}\text{(10)}& \hat{y}={\overrightarrow{\mathbf{w}}}_p^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}_L+b_p\end{array}$$

       其中：${\overrightarrow{\mathbf{w}}}_p,b_p$$\mathbf{\vec w}_p, b_p$ 分别表示 prediction layer 的权重向量和偏置。

   

2. Optimization：目标函数针对不同的任务（分类、回归、ranking ）而做出相应的选择。常见的目标函数是对数损失：

   $$\begin{array}{}\text{(11)}& \text{Logloss}=-\frac{1}{K}[\sum _{i=1}^K{y}_i\log \sigma \left({\hat{y}}_i\right)+(1-y_i)\log (1-\sigma \left({\hat{y}}_i\right))]\end{array}$$

   其中：$K$$K$ 为训练样本数量，$\sigma (\cdot )$$\sigma(\cdot)$ 为 sigmoid 函数。

   我们采用 Adam 优化器进行随机梯度下降。此外，我们对logarithmic transformation 、exponential transformation 和所有隐层的输出进行 batch normalization: BN 。有两个原因：

   • 首先，feature embedding $\overrightarrow{\mathbf{e}}$$\mathbf{\vec e}$ 通常被初始化并被优化为接近于零。在对数变换后， embedding 往往涉及大的负值，并有显著的方差，这对后续几层的参数优化是有害的。由于 BN 可以缩放并 shift 输出为归一化的数值，因此它对 AFN 的训练过程至关重要。
   • 其次，我们在对数转换层之后采用多层神经网络。对隐层的输出进行 BN 有助于缓解协方差漂移问题，从而导致更快的收敛和更好的模型性能。

3. Ensemble AFN with DNN：之前的工作（Wide&Deep、DeepFM、xDeepFM）提出将基于交叉特征的模型（如 FM ）的预测结果与基于原始特征的神经方法的预测结果进行 ensemble ，以提高性能。类似地，我们也可以将 AFN 与深度神经网络进行结合。为了执行AFN 和神经网络之间的 ensemble ，我们首先分别训练这两个模型。之后，我们建立一个 ensemble 模型来结合两个训练好的模型的预测结果：

   $$\begin{array}{}\text{(12)}& {\hat{y}}_{\text{ensem}}=w_1\times {\hat{y}}_{\text{AFN}}+w_2\times {\hat{y}}_{\text{DNN}}+b\end{array}$$

   其中：${\hat{y}}_{\text{AFN}},{\hat{y}}_{\text{DNN}}$$\hat y_\text{AFN}, \hat y_\text{DNN}$ 分别为训练好的 AFN 和 DNN 的预测结果，$w_1,w_2$$w_1, w_2$ 分别为相应的系数，$b$$b$ 为偏置项。

   ensemble model 可以通过 logloss 损失来进行训练。我们把这个 ensemble 模型称为 "AFN+" 。

   我们的 ensemble 方法与DeepFM 使用的方法有些不同：DeepFM 的 feature embedding 在 FM 和 DNN 之间共享，而我们将 AFN 和 DNN 的 embedding layer 分开从而避免干扰。主要的原因是：与 DeepFM 不同，AFN 中的 embedding value 的分布应该始终保持 positive ，这和 DNN 中 embedding value 的分布相差甚远。

   众所周知，在 CTR 预测任务中，DNN 模型的参数主要集中在 embedding table。这里用到了两套 embedding table ，模型参数翻倍。

   根据我们的实验，这种分离方法略微增加了模型的复杂性，但会带来更好的性能。

4. 讨论：

   • 理解 AFN 中的阶次：AFN 通过对数转换层学习交叉特征中每个特征的阶次。由于对数转换层的权重矩阵 ${\mathbf{W}}_{\text{LTL}}$$\mathbf W_\text{LTL}$ 没有限制，学到的特征阶次可以是小数或负值。为了理解 AFN 学到的特征阶次，我们借鉴了 field-aware factorization machine: FFM 的一些思想。

     在 FFM 中，每个特征都关联 $m$$m$ 个 feature embedding ，其中 $m$$m$ 是 feature field 的数量。FFM 与 FM 的区别在于，每个特征在与不同 field 的其它特征进行交互时采用不同的 embedding 。FFM 的启示是：要避免不同 field 的特征空间之间的干扰。 在 AFN 中，每个特征的阶次可以被看作是相应 feature embedding 的一个比例因子。例如，考虑一个取值从 0 到 1 之间的 embedding ，大于 1 的阶次会缩小 embedding 值，而小于 1 的阶次则扩大 embedding 值。通过与 FFM 的类比，当与不同 field 的其它特征进行交互时，可以利用 AFN 学到的阶次来 rescale feature embedding 。

   • 与 FM 和 HOFM 的关系：我们首先表明，FM 可以被看作是AFN 的一个特例。根据公式 ${\overrightarrow{\mathbf{y}}}_j=\exp (\sum _{i=1}^m{w}_{i,j}\ln {\overrightarrow{\mathbf{e}}}_i)={\overrightarrow{\mathbf{e}}}_1^{w_{1,j}}\odot {\overrightarrow{\mathbf{e}}}_2^{w_{2,j}}\odot \cdots \odot {\overrightarrow{\mathbf{e}}}_m^{w_{m,j}}$$\mathbf{\vec y}_j = \exp\left(\sum_{i=1}^m w_{i,j} \ln \mathbf{\vec e}_i\right) = \mathbf{\vec e}_1^{w_{1,j}}\odot \mathbf{\vec e}_2^{w_{2,j}}\odot\cdots\odot \mathbf{\vec e}_m^{w_{m,j}}$ ，通过适当设置每个 feature embedding 的幂次 $w_{i,j}$$w_{i,j}$ ，对数神经元的输出 ${\overrightarrow{\mathbf{y}}}_j$$\mathbf{\vec y}_j$ 能够表示任何二阶交叉特征。假设我们有足够多的对数神经元来产生所有的二阶交叉特征，并且后续的隐层在 element-level 上近似于一个简单的 sum 函数，那么 AFN 可以准确地恢复 FM 。

     类似地，当我们有足够多的对数神经元来提供最大阶次内的所有交叉特征，并允许隐层近似 sum 函数时，AFN 能够恢复HOFM。

   • 时间复杂度：令 $k$$k$ 和 $m$$m$ 分别表示 feature embedding 维度和 feature field 数量。在 AFN 中，对数神经元可以在 $O(km)$$O(km)$ 时间内计算出来。假设有 $N$$N$ 个对数神经元，则对数变换层的计算复杂度为 $O(kmN)$$O(kmN)$ 。考虑到隐层的额外成本，AFN 的总时间复杂度是 $O(kmN+n_W)$$O(kmN + n_W)$ ，其中 $n_W$$n_W$ 是隐层的权重总数。

     至于 HOFM ，假设 $n$$n$ 是预先定义的特征组合的最大阶次，它需要 $O(k{m}^n)$$O(km^n)$ 时间来提供预测，通过动态编程可以减少到 $O(km{n}^2)$$O(kmn^2)$。注意，HOFM 的时间复杂度与交叉特征的最大阶次 $n$$n$ 高度相关，而在 AFN 中，由于其自适应的交叉特征生成方式，$N$$N$ 和 $n_W$$n_W$ 都仅由模型结构决定。根据经验，在最佳设置下，训练 AFN 的时间成本与 CIN 接近。

33.3 实验

1. 数据集：

   • Criteo：包含 13 个数值特征和 26 个 categorical feature 。
   • Avazu：包含 22 个 feature field ，包括用户特征和广告属性。
   • Movielens：我们将每个 tagging record （(user ID, movie ID, tag) 三元组）转换为一个特征向量来作为输入。target 为：用户是否为电影分配了一个特定的 tag 。
   • Frappe：我们将每条日志（user ID, app ID, context features ）转换为一个特征向量来作为输入。target 为：用户是否在上下文中使用过该 app 。

   所有数据集的统计信息如下表所示。

   

2. 评估指标：AUC, Logloss 。

3. baseline 方法：

   • 一阶方法（对原始特征进行线性相加）：Linear Regression: LR 。
   • 考虑二阶交叉特征的 FM-based 方法：FM、AFM。
   • 建模高阶特征交互的高级方法：HOFM、NFM、PNN、CrossNet、CIN。
   • 涉及 DNN 作为组件的 ensemble 方法：Wide&Deep （为公平比较，我们省略了手工制作的交叉特征），DeepFM、Deep&Cross、xDeepFM 。

4. 实现细节：

   • 使用 Tensorflow 实现、采用 Adam 优化器、学习率 0.001、mini-batch size = 4096。
   • 对于 Criteo/Avazu/Movielens/Frappe 数据集，默认的对数神经元数量 $N$$N$ 分别被设置为 1500/1200/800/600 。
   • AFN 中默认使用 3 个隐层、每层 400 个神经元。
   • 为了避免过拟合，根据验证集的 AUC 进行 early-stopping 。
   • 在所有的模型中，我们将 feature embedding 的维度设置为 10。
   • 我们对所有涉及 DNN 的方法使用相同的神经网络结构（即 3 层：400-400-400 ）以进行公平的比较。
   • HOFM 的最高阶次设为 3 。
   • 所有其他的超参数都是在验证集上调优的。
   • 对于每个经验结果，我们运行实验 3 次并报告平均值。

5. 单模型的比较：单模型的比较如下表所示。可以看到：

   • AFN 在所有的数据集上产生了最好的或有竞争力的性能。

     • 对于 Criteo 和 Frappe，AFN 比第二好的模型 CIN 要好得多。
     • 对于Movielens，AFN 取得了第二好的性能。
     • 对于 Avazu ，AFN 取得了最好的 logloss ，而 AUC 适中。

     关于较简单的模型在 Movielens 和 Avazu 上的良好表现，我们猜测这两个数据集的预测更多依赖于低阶交叉特征，AFN 的优势因此受到限制。请注意，Movielens 只包含三个 feature field ，找到有用的高阶交叉特征的好处可能是微不足道的。

   • AFN 在所有数据集上的表现一直优于 FM 和 HOFM ，这验证了学习自适应阶次的交叉特征比建模固定阶次的交叉特征可以带来更好的预测性能。

   • 利用高阶交叉特征的模型通常优于基于低阶交叉特征的模型，特别是当feature field 的数量很大时。这与高阶特征交互具有更强的预测能力的直觉是一致的。

   AFN 并没有在所有数据集上展示出显著的提升。

   ensemble 模型的比较：ensemble 模型的比较如下表所示。可以看到：

   • AFN+ 在四个数据集上取得了最佳性能。平均而言，AFN 相比 xDeepFM，在 AUC 和 logloss 上分别取得了 0.003 和 0.012 的改善。

     这表明，AFN 学到的自适应阶次的交叉特征与 DNN 建模的隐式特征交互有很大不同，因此在结合两种不同类型的特征交互进行预测时，性能增益显著提高。

   

6. 超参数研究：我们只提供 Frappe 的结果，因为其他三个数据集的结果是相似的。

   • 对数神经元的数量：如下图 (a) 所示：

     • 当神经元的数量变大时，AFN 的性能呈现上升趋势，随后是下降趋势。这表明应该采用适当数量的对数神经元，在表达能力和泛化之间做出权衡，以达到最佳性能。
     • 令人惊讶的是，即使对数神经元的数量少于 5 个，AFN的优势也很稳定。这一结果表明，找到少量的 discriminative 交叉特征对预测的准确性至关重要，而 AFN 对于找到这些关键的交叉特征是有效的。

   • 隐层深度：如下图 (b) 所示：

     • 在学到的自适应阶次的交叉特征上堆叠隐层有利于提高模型性能。
     • 值得注意的是，AFN 的性能并不高度依赖于隐层的数量。当深度被设置为0 时，AFN 仍然可以取得相当好的结果。这证明了对数转换层在学习 discriminative 交叉特征方面的有效性。

   • 隐层神经元数量：如下图 (c) 所示：

     • AFN 的性能首先随着神经元数量的增加而增长。这是因为更多的参数给模型带来了更好的表达能力。
     • 当隐层的神经元数量超过 600 时，性能开始下降，这是由于过拟合导致的。

   

7. 学到的阶次：下图显示了在 Criteo 数据集上整个训练过程中特征阶次的变化。

   • 从下图 (a) 可以看到：各个 feature field 的阶次通常以 0 为中心，在 [-1，1] 的范围内。这与典型的 factorization-based 的方法截然不同，在这种方法中，每个特征的阶次要么为 0 、要么为 1 。学到的特征阶次的 relaxation 允许原始 feature embedding 在组成不同的交叉特征时被 rescale 。

   • 下图 (b) 给出了交叉特征的阶次的分布，其中交叉特征的阶次是组成它的各个特征的阶次的绝对值之和来计算的。可以看到：在训练过程中，学到的交叉特征的阶次被逐渐优化。

     最终的交叉特征阶次分布在一个很宽的范围内（从 4 到 10 ），而不是像许多 factorization-based 方法那样被固定在一个预定义的值上（例如 2 ）。

   

8. 案例研究：我们对 Frappe 数据集进行了案例研究。为了说明问题，我们将对数神经元的数量限制为 3 个。Figure 4(c) 提供了每个神经元上单个特征阶次的绝对值和总和。

   从图中，我们可以大致推断出，三个交叉特征 (item id, is free, country), (user id, item id), (item id, is free) 在各自的对数神经元中被学习。

   此外，通过 sum 三个神经元的特征阶次，发现最 discriminative 的 feature field 是 item id, is free, user id 。这是合理的，因为 user id 和 item id 是协同过滤中最常用的特征；而 is free 表示用户是否为 mobile app 付费，是用户对 app 偏好的一个有力指标。

三十四、FGCNN[2019]

1. CTR 预测任务的关键挑战是如何有效地建模特征交互。FM 及其变体将 pairwise 特征交互建模为潜在向量的内积，并显示出有前景的结果。最近，一些深度学习模型被用于 CTR 预测，如 PIN、xDeepFM 等。这类模型将原始特征馈入深度神经网络，以显式或隐式的方式学习特征交互。理论上， DNN 能够从原始特征中学习任意的特征交互。然而，由于与原始特征的组合空间相比，有用的特征交互通常是稀疏的，要从大量的参数中有效地学习它们是非常困难的。

   为解决这个困难，Wide & Deep 利用 wide 组件中的特征工程来帮助 deep 组件的学习。在人工特征的帮助下， deep 组件的性能得到了显著的提高。然而，特征工程可能是昂贵的，并且需要领域知识。如果我们能通过机器学习模型自动生成复杂的特征交互，它将更加实用和鲁棒。

   因此，如下图所示，论文 《Feature Generation by Convolutional Neural Network for Click-Through Rate Prediction》 提出了一个自动生成特征的通用框架。原始特征被馈入到机器学习模型（右图中的红框），从而识别和生成新的特征。之后，原始特征和新特征被结合起来，并馈入一个深度神经网络。被生成的特征能够通过提前捕获稀疏的但重要的特征交互来降低深度模型的学习难度。

   

   自动生成特征的最直接的方法是进行多层感知机Multi-Layer Perceptron: MLP ，并使用隐层的神经元作为生成的特征。然而，如前所述，由于有用的特征交互通常是稀疏的，MLP 很难从巨大的参数空间中学习这种交互。

   作为一种 SOTA 的神经网络结构，卷积神经网络 Convolutional Neural Network: CNN 在计算机视觉和自然语言处理领域取得了巨大成功。在 CNN 中，共享权重、池化机制的设计大大减少了寻找重要局部模式所需的参数数量，它将缓解随后的 MLP 结构的优化困难。因此，CNN 为实现作者的想法（识别稀疏的但重要的特征交互）提供了一个潜在的良好解决方案。然而，直接应用 CNN 可能会导致不满意的性能。在 CTR 预测中，原始特征的不同排列顺序并没有不同的含义。例如，特征的排列顺序是 (Name, Age, Height, Gender) 还是 (Age, Name, Height, Gender) 对描述样本的语义没有任何区别，这与图像和句子的情况完全不同。如果只使用 CNN 抽取的邻居模式 neighbor pattern ，许多有用的 global feature interaction 就会丢失。这也是为什么 CNN 模型在 CTR 预测任务中表现不佳的原因。为了克服这一局限性，作者采用了 CNN 和 MLP ，两者相互补充，学习 global-local 特征交互来生成特征。

   在论文中，作者为 CTR 预测任务提出了一个新的模型，即 Feature Generation by Convolutional Neural Network: FGCNN，它由两个部分组成：特征生成 Feature Generation 、深度分类器 Deep Classifier 。

   • 在特征生成中，作者设计了一个 CNN+MLP 的结构用来从原始特征中识别和生成新的重要特征。更具体地说，CNN 被用来学习 neighbor feature interaction，而 MLP 被用来重新组合它们从而提取 global feature interaction 。在特征生成之后，特征空间可以通过结合原始特征和新特征来进行扩充。
   • 在深度分类器中，几乎所有 SOTA 网络结构（如 PIN、xDeepFM、DeepFM）都可以被采用。因此，论文的方法与推荐系统中SOTA的模型具有良好的兼容性。为了便于说明，作者将采用 IPNN 模型作为 FGCNN 的深度分类器，因为它在模型的复杂性和准确性之间有很好的权衡。

   在三个大规模数据集上的实验结果表明，FGCNN 明显优于九个 SOTA 的模型，证明了 FGCNN的有效性。在深度分类器中采用其他模型时，总是能取得更好的性能，这表明了所生成的特征的有用性。逐步分析表明，FGCNN 中的每个组件都对最终的性能做出了贡献。与传统的 CNN 结构相比，论文提出的 CNN+MLP 结构在原始特征的顺序发生变化时表现得更好、更稳定，这证明了 FGCNN 的鲁棒性。

   综上所述，论文贡献如下：

   • 确定了 CTR 预测的一个重要方向：通过提前自动生成重要的特征来降低深度学习模型的优化难度，这既是必要的，也是有益的。
   • 提出了一个新的模型 FGCNN 用于自动生成特征和分类，它由两个部分组成：Feature Generation 、Deep Classifier。特征生成利用 CNN 和 MLP ，它们相互补充，以识别重要的但稀疏的特征。 此外，几乎所有其他的 CTR 模型都可以应用在深度分类器中，从而根据生成的特征、以及原始的特征进行学习和预测。
   • 在三个大规模数据集上的实验证明了 FGCNN 模型的整体有效性。当生成的特征被用于其他模型时，总是能取得更好的性能，这表明 FGCNN 模型具有很强的兼容性和鲁棒性。

2. 相关工作：

   • CTR 预测的浅层模型：

     • 由于鲁棒性和效率高，Logistic Regression: LR 模型（如 FTRL ）被广泛用于 CTR 预测中。为了学习特征交互，通常的做法是在其特征空间中手动设计 pairwise 特征交互。
     • Poly-2 建模所有 pairwise 特征交互以避免特征工程。
     • Factorization Machine: FM 为每个特征引入了低维向量，并通过特征向量的内积来建模特征交互。在数据稀疏的情况下，FM 提高了建模特征交互的能力。
     • FFM 对每个特征使用多个潜在向量，从而建模与不同 field 特征的交互。

     LR 、Poly-2 、以及 FM 变体被广泛用于工业界的 CTR 预测中。

   • CTR 预测的深层模型：

     • FNN 使用 FM 来预训练原始特征的 embedding，然后将 embedding 馈入全连接层。

     • 一些模型采用 DNN 来改善 FM ，如 Attentional FM 、Neural FM 。

     • Wide & Deep 联合训练一个 wide 模型和一个 deep 模型，其中 wide 模型利用人工特征工程，而 deep 模型学习隐式特征交互。尽管 wide 组件很有用，但特征工程很昂贵，而且需要专业知识。

     • 为了避免特征工程，DeepFM 引入了 FM Layer （建模二阶交互）作为 wide 组件，并使用 deep 组件来学习隐式特征交互。

     • 与 DeepFM 不同，IPNN （也被称为 PNN ）将 FM Layer 的结果和原始特征的 embedding 都馈入 MLP ，从而得到相当好的结果。

     • PIN 没有像 DeepFM 和 IPNN 那样使用内积来建模 pairwise 特征交互，而是使用一个 Micro-Network 来学习每个 feature pair 的复杂特征交互。

     • xDeepFM 提出了一种新颖的 Compressed Interaction Network: CIN ，以显式地建模 vector-wise level 的特征交互。

     • 有一些使用 CNN 进行 CTR 预测的模型：

       • CCPM 应用多个卷积层来探索邻居特征的相关性。CCPM 以一定的排列方式对 neighbor field 进行卷积。由于特征的顺序在 CTR 预测中没有实际意义，CCPM 只能学习邻居特征之间有限的特征交互。
       • 《Convolutional Neural Networks based Click-Through Rate Prediction with Multiple Feature Sequences》中显示，特征的排列顺序对 CNN-based 模型的最终性能有很大影响。因此，作者提出生成一组合适的特征序列，为卷积层提供不同的局部信息。然而，CNN 的关键弱点并没有得到解决。

       在本文中，我们提出了 FGCNN 模型，它将 CTR 预测任务分成两个阶段：特征生成和深度分类器。特征生成阶段通过生成新的特征来增强原始特征空间，而深度分类器可以采用大多数 SOTA 模型从而在增强的特征空间中学习和预测。与传统的CNN 模型预测 CTR 不同，FGCNN 可以利用 CNN 的优势来提取局部信息，并通过引入重组层来重新组合 CNN 学到的不同局部模式的信息来生成新的特征，从而大大缓解了 CNN 的弱点。

       在CTR 预测任务中，是否混洗特征的排列顺序，对于 CNN-based 模型会更好？

34.1 模型

1. 如下图所示，FGCNN 模型由两部分组成：特征生成、深度分类器：

   • 特征生成侧重于识别有用的局部模式和全局模式，以生成新的特征作为原始特征的补充。
   • 深度分类器则通过深度模型在增强的特征空间的基础上进行学习和预测。

   除了这两个组件，我们还有 feature embedding 。

   根据实验部分的结果，通过 CNN 生成的新特征虽然有效果，但是提升不显著（平均而言不到 0.1% 的 AUC 提升）。

   如果将 CNN 替换为 MLP，那么特征生成组件就是一个 MLP 结构，同时将每一层的输出再投影为新的特征向量。

   

34.1.1 Feature Embedding

1. embedding layer 应用于所有原始特征的输入，将原始特征压缩为低维向量。在我们的模型中：

   • 如果一个 field 是 univalent 的（例如，Gender=Male ），它的 embedding 就是该 field 的 feature embedding 。
   • 如果一个 field 是 multivalent 的（例如， Interest=Football, Basketball ），该 field 的 embedding 是 feature embeddings 之和。

   正式而言，在一个样本中，每个 field $i$$i$ （$1\le i\le n_f$$1\le i \le n_f$，$n_f$$n_f$ 为 field 数量）被表示为一个低维向量 ${\overrightarrow{\mathbf{e}}}_i\in {\mathbb{R}}^k$$\mathbf{\vec e}_i\in \mathbb R^k$，其中 $k$$k$ 为 embedding size 。因此，每个样本可以表示为一个 embedding 矩阵 $\mathbf{E}={({\overrightarrow{\mathbf{e}}}_1,{\overrightarrow{\mathbf{e}}}_2,\cdots ,{\overrightarrow{\mathbf{e}}}_{n_f})}^{\mathrm{\top }}\in {\mathbb{R}}^{n_f\times k}$$\mathbf E = \left(\mathbf{\vec e}_1,\mathbf{\vec e}_2,\cdots,\mathbf{\vec e}_{n_f}\right)^\top\in \mathbb R^{n_f\times k}$ 。在 FGCNN 模型中，embedding 矩阵 $\mathbf{E}$$\mathbf E$ 可以在特征生成和深度分类器中得到利用。

   为了避免更新参数时梯度方向的不一致，我们将为深度分类器引入另一个 embedding 矩阵 ${\mathbf{E}}^{\prime }\in {\mathbb{R}}^{n_f\times k}$$\mathbf E^\prime\in \mathbb R^{ n_f\times k}$ ，而 $\mathbf{E}$$\mathbf E$ 用于特征生成。

   这意味着需要引入两套 embedding table，模型的参数要翻倍（模型参数被 embedding table 所主导）。

   如果 $\mathbf{E}$$\mathbf E$ 和 ${\mathbf{E}}^{\prime }$$\mathbf E^\prime$ 共享，性能会下降多少？

34.1.2 Feature Generation

1. 如前所述，从原始特征中生成新的特征有助于提高深度学习模型的性能。为了实现这一目标，特征生成组件设计了一个适当的神经网络结构来识别有用的特征交互，然后自动生成新的特征。

   正如前面所论证的，由于以下原因，单独使用 MLP 或 CNN 无法从原始特征中生成有效的特征交互：

   • 首先，在原始特征的组合空间中，有用的特征交互总是稀疏的。因此，MLP 很难从大量的参数中学习它们。
   • 其次，虽然 CNN 可以通过减少参数的数量来缓解 MLP 的优化困难，但它只产生 neighbor feature interaction ，可能会失去许多有用的 global feature interaction 。

   为了克服单独应用 MLP 或 CNN 的弱点，我们将 CNN 和 MLP 相互补充从而进行特征生成。下图显示了一个 CNN + Recombination 结构的例子，以捕捉 global feature interaction 。可以看到：CNN 用有限的参数学习有用的 neighbor feature pattern ，而重组层（这是一个全连接层）根据 CNN 提供的 neighbor pattern 生成 global feature interaction 。因此，通过这种神经网络结构可以有效地生成重要的特征。相比直接应用 MLP 生成特征，这种方法的参数更少。

   纵向为不同的 field，横向为不同的 embedding 维度，卷积核为 $K\times 1$$K\times 1$ ，这会在每个 embedding 维度上聚合相连的 $K$$K$ 个 field 。

   最后一步的结果是说明：Recombination 会把卷积结果进行投影并减少通道数。

   

2. 卷积层：每个样本通过 feature embedding 被表示为 embedding 矩阵 $\mathbf{E}\in {\mathbb{R}}^{n_f\times k}$$\mathbf E\in \mathbb R^{n_f\times k}$ 。为方便起见，将 embedding 矩阵 reshape 为${\mathbf{E}}^1\in {\mathbb{R}}^{n_f\times k\times 1}$$\mathbf E^1\in \mathbb R^{n_f\times k\times 1}$ 作为第一个卷积层的输入矩阵，即通道数为 1 。为了捕获 neighbor feature interaction ，用非线性激活函数的卷积层对 ${\mathbf{E}}^1$$\mathbf E^1$ 进行卷积，卷积层的输出记做 ${\mathbf{C}}^1\in {\mathbb{R}}^{n_f\times k\times m_c^1}$$\mathbf C^1\in \mathbb R^{n_f\times k\times m^1_c}$ 。其中，卷积核的尺寸为 $h^1\times 1$$h^1\times 1$、输出通道数为 $m_c^1$$m^1_c$ 、输入通道数为 1 ，激活函数为 tanh() ，$h^1$$h^1$ 为卷积核的高度（代表对相连的多少个 field 进行卷积）。

3. 池化层：在第一个卷积层之后，应用一个 maxpooling 层来捕获最重要的特征交互，从而减少参数的数量。令 $h_p^1$$h_p^1$ 为池化层的高度（池化层的宽度为 1 ），那么第一个池化层的输出为 ${\mathbf{S}}^1\in {\mathbb{R}}^{(n_f/h_p^1)\times k\times m_c^1}$$\mathbf S^1\in \mathbb R^{(n_f/h_p^1)\times k\times m_c^1}$ 。第 $i$$i$ 个池化层的池化结果将是第 $(i+1)$$(i+1)$ 个卷积层的输入：${\mathbf{E}}^{i+1}={\mathbf{S}}^i$$\mathbf E^{i+1} = \mathbf S^i$ 。

4. Recombination Layer：${\mathbf{S}}^1$$\mathbf S^1$ 包含了 neighbor feature 的模式。由于 CNN 的性质，如果 ${\mathbf{S}}^1$$\mathbf S^1$ 被视为生成的新特征，全局性非邻接的特征交互将被忽略。因此，我们引入了一个全连接层来重新组合局部的 neighbor feature pattern 并生成重要的新特征。

   我们将 ${\mathbf{S}}^1$$\mathbf S^1$ 展平为一维向量 ${\overrightarrow{\mathbf{s}}}^1\in {\mathbb{R}}^{n_{f}k/h_p^1{m}_c^1}$$\mathbf {\vec s}^1\in \mathbb R^{n_fk/h_p^1m_c^1}$ ，那么全连接层的权重矩阵为：${\mathbf{W}}^1\in {\mathbb{R}}^{(n_{f}k/h_p^1\times m_r^1)\times (n_{f}k/h_p^1\times m_c^1)}$$\mathbf W^1\in \mathbb R^{(n_fk/h_p^1\times m_r^1)\times (n_fk/h_p^1\times m_c^1 )}$ ，bias 向量为 ${\overrightarrow{\mathbf{b}}}^1\in {\mathbb{R}}^{(n_{f}k/h_p^1\times m_r^1)}$$\mathbf{\vec b}^1\in \mathbb R^{(n_fk/h_p^1\times m_r^1)}$ 。生成的新特征为：

   $$\begin{array}{}\text{(13)}& {\mathbf{R}}^1=\tanh ({\mathbf{W}}^1{\overrightarrow{\mathbf{s}}}^1+{\overrightarrow{\mathbf{b}}}^1)\in {\mathbb{R}}^{(n_f/h_p^1)\times k\times m_r^1}\end{array}$$

   其中 $m_r^1$$m_r^1$ 为重组层的输出通道数。

   注意，这里是把全连接层的结果又 reshape 回来。

5. 拼接：新的特征可以通过多次执行 CNN+Recombination 来产生。假设有 $n_c$$n_c$ 组卷积层、池化层、以及重组层。通过 Feature Generation 生成的所有的新特征为：

   $$\begin{array}{}\text{(14)}& {\mathbf{R}}_{\text{all}}=({\mathbf{R}}^1,{\mathbf{R}}^2,\cdots ,{\mathbf{R}}^{n_c})\in {\mathbb{R}}^{(\sum _{i=1}^{n_c}{n}_f/h_p^i\times m_r^i)\times k}\end{array}$$

   注意，这里也有 reshape 操作。

   原始特征和新特征的拼接为：

   $$\begin{array}{}\text{(15)}& {\mathbf{E}}_{\text{concat}}=({\mathbf{E}}^{\prime },{\mathbf{R}}_{\text{all}})\end{array}$$

   其中 ${\mathbf{E}}^{\prime }$$\mathbf E^\prime$ 是用于深度分类器的原始特征的 embedding 矩阵。

   令 $N_i=n_f\times (m_r^i/h_p^i)$$N_i = n_f\times (m_r^i/h_p^i)$ 为第 $i$$i$ 个重组层得到的新 embedding 的数量，它等于 $n_f$$n_f$ 乘以一个系数，该系数为重组层的输出通道数除以池化层的高度。令 $N=\sum _{i=1}^{n_c}{N}_i$$N=\sum_{i=1}^{n_c} N_i$ ，则 $N$$N$ 表示所有新生成的特征数量。

34.1.3 Deep Classifier

1. ${\mathbf{E}}_{\text{concat}}$$\mathbf E_\text{concat}$ 被馈入深度分类器中，其目的是进一步学习原始特征和新生成特征之间的交互。这里我们采用 IPNN 模型作为深度分类器的网络结构，因为它在模型复杂性和准确性之间有很好的权衡。事实上，任何先进的网络结构都可以被采用，这表明 FGCNN 与现有工作的兼容性。

2. 网络结构：IPNN 模型结合了 FM和 MLP 的学习能力。它利用一个 FM layer，通过内积运算从 embedding 向量中抽取 pairwise 特征交互。之后， input feature 的 embedding 和 FM layer 的结果被拼接起来，并馈入 MLP 进行学习。根据 IPNN 原始论文的评估，IPNN 的性能比 PIN 略差，但 IPNN 的效率更高。我们将对 IPNN 模型的网络结构进行说明。

   如下图所示，增强的 embedding 矩阵 ${\mathbf{E}}_{\text{concat}}$$\mathbf E_\text{concat}$ 的 pairwise 特征交互由 FM layer 来建模。 ${\mathbf{R}}_{\text{all}}$$\mathbf R_\text{all}$ 的 embedding 向量个数为 $N$$N$ ， ${\mathbf{E}}^{\prime }$$\mathbf E^\prime$ 有 $n_f$$n_f$ 个特征向量，因此 ${\mathbf{E}}_{\text{concat}}$$\mathbf E_\text{concat}$ 有 $N+n_f$$N+n_f$ 个特征向量。FM layer 的输出维度为 $(N+n_f)(N+n_f-1)/2$$(N+n_f)(N+n_f-1)/2$ ，因为 embedding 向量之间两两内积。

   假设 FM layer 的输出为 ${\overrightarrow{\mathbf{e}}}_{\text{fm}}\in {\mathbb{R}}^{(N+n_f)(N+n_f-1)/2}$$\mathbf {\vec e}_\text{fm}\in \mathbb R^{(N+n_f)(N+n_f-1)/2}$ ，则我们将它和展平后的 ${\mathbf{E}}_{\text{concat}}$$\mathbf E_\text{concat}$ 进行拼接，然后馈入 MLP ：

   $$\begin{array}{}\text{(16)}& {\overrightarrow{\mathbf{h}}}_{\text{0}}=[{\overrightarrow{\mathbf{e}}}_{\text{concat,1}}||\cdots ||{\overrightarrow{\mathbf{e}}}_{\text{concat},N+n_f}||{\overrightarrow{\mathbf{e}}}_{\text{fm}}]\in {\mathbb{R}}^{(N+n_f)k+(N+n_f)(N+n_f-1)/2}\end{array}$$

   其中 $[\cdot ||\cdot ]$$[\cdot||\cdot]$ 表示向量拼接。

   

3. BN 层：在 FGCNN 中，Batch Normalization 应用在每个激活函数之前从而加速模型训练。

4. 目标函数：最小化交叉熵：

   $$\begin{array}{}\text{(17)}& \mathcal{L}=-[y\log \hat{y}+(1-y)\log (1-\hat{y})]\end{array}$$

   其中： $y$$y$ 为 ground-truth，$\hat{y}$$\hat y$ 为预测的点击率。

34.1.4 复杂度分析

1. 空间复杂度：空间复杂度由三部分组成，即 Feature Embedding、Feature Generation、Deep Classifier。

   • Feature Embedding：包含两个 embedding 矩阵（一个用于 feature generation、一个用于 deep classifier ），总的参数规模为 $s_0=2t_f\times k$$s_0 = 2t_f\times k$ ，其中 $t_f$$t_f$ 为总的 vocab size 。

   • Feature Generation：第 $i$$i$ 个卷积层有 $h^i{m}_c^{i-1}{m}_c^i$$h^i m_c^{i-1}m_c^i$ 个参数，其中 $h^i$$h^i$ 为卷积核的高度；第 $i$$i$ 个重组层有 $(n_{f}k/h_p^i{)}^2{m}_c^i{m}_r^i$$(n_fk/h_p^i)^2m_c^im_r^i$ 个参数。因此，这里的参数数量为：

     $$\begin{array}{}\text{(18)}& \sum _{i=1}^{n_c}{h}^i{m}_c^{i-1}{m}_c^i+(n_{f}k/h_p^i{)}^2{m}_c^i{m}_r^i\end{array}$$

   • Deep Classifier：令 $T=N+n_f$$T=N+n_f$ 表示 Feature Generation 之后所有的 embedding 数量（包括原始的、以及新生成的）。那么 Deep Classifier 的空间复杂度为：

     $$\begin{array}{}\text{(19)}& s_2=O(\frac{T(T-1)+2Tk}{2}\times H_1+\sum _{i=2}^{n_h}{H}_i{H}_{i-1})\end{array}$$

     其中 $H_i$$H_i$ 为第 $i$$i$ 层 MLP 的隐层维度，$n_h$$n_h$ 为层数。

   最终的空间复杂度大约为 $O(t_{f}k+N_1^2{k}^2+T^2{H}_1+\sum _{i=1}^{n_h}{H}_i{H}_{i-1})$$O(t_fk+N_1^2k^2 + T^2H_1 + \sum_{i=1}^{n_h} H_iH_{i-1})$，其中 $N_i=n_f/h_p^i{m}_r^i$$N_i = n_f/h_p^im_r^i$ 为第 $i$$i$ 个重组层得到的新 embedding 的数量。（具体推导见原始论文）。

2. 时间复杂度：

   • Feature Generation：时间复杂度约为 $O(N_{1}k\sum _{i=1}^{n_c}{m}_c^{i-1}{h}^i+N_1^2{k}^2)$$O(N_1k\sum_{i=1}^{n_c} m_c^{i-1}h^i + N_1^2k^2)$ 。具体推导见原始论文。
   • Deep Classifier ：时间复杂度约为 $O(T^2{H}_1)+\sum _{i=2}^{n_h}O(H_i{H}_{i-1})$$O(T^2H_1) + \sum_{i=2}^{n_h} O(H_iH_{i-1})$ 。具体推导见原始论文。

   最终的时间复杂度约为 $O(N_{1}k\sum _{i=1}^{n_c}{m}_c^{i-1}{h}^i+N_1^2{k}^2+T^2{H}_1+\sum _{i=2}^{n_h}{H}_i{H}_{i-1})$$O(N_1k\sum_{i=1}^{n_c} m_c^{i-1}h^i + N_1^2 k^2 + T^2H_1 + \sum_{i=2}^{n_h} H_iH_{i-1})$ 。

   超参数太多了，不太好调优。

34.2 实验

1. 数据集：Criteo, Avazu, Huawei App Store 。

   • 对于 Criteo 数据集，我们选择 "day 6-12" 作为训练集，同时选择 "day 13" 进行评估。由于巨大的数据量和严重的类不平衡（即只有 3% 的样本是正样本），我们采用了负采样来保持正负比例接近 1:1 。我们通过分桶从而将 13 个 numerical field 离散化。 field 中出现少于 20 次的特征被设置为 dummy 特征 "other" 。
   • 对于Avazu数据集，我们以 4:1 的比例随机拆分为训练集和测试集。同时，我们删除了出现少于 20 次的特征以降低维度。
   • 对于 Huawei App Store 数据集，我们用 20180617 ~ 20180623 的日志用于训练，20180624 的日志用于测试。为了减少数据量并调整正负样本的比例，采用了负采样。

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

   

2. baseline：LR, GBDT, FM, FFM, CCPM, DeepFM, xDeepFM, IPNN, PIN 。

   Wide & Deep 未参与比较，因为一些 SOTA 的模型（如 xDeepFM 、DeepFM 、PIN ）在各自的原始论文中显示了更好的性能。我们分别使用 XGBoost 和 libFFM 作为 GBDT 和 libFFM 的实现。在我们的实验中，其他 baseline 模型是用 Tensorflow 实现的。

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

4. 配置：下表给出了每个模型的超参数。

   注意，在 Criteo 和 Avazu 上进行实验时，我们观察到 FGCNN 在深度分类器中使用的参数比其他模型多。为了进行公平的比较，我们也进行了实验，增加其他深度模型的 MLP 中的参数。然而，所有这些模型都不能达到比原始设置更好的性能。原因可能是过拟合的问题，这类模型只是简单地使用原始特征的 embedding 进行训练，但使用的是复杂的结构。另一方面，由于我们的模型增强augment 了特征空间并丰富了输入，因此在深度分类器中更多的参数可以提高我们模型的性能。

   在 FGCNN 模型中，new 表示 $m_r$$m_r$。生成的特征数量可以计算为 $\sum _{i=1}^{n_c}{n}_f/h_p^i{m}_r^i$$\sum_{i=1}^{n_c} n_f/h_p^im_r^i$。

   对于 FGCNN 和 best baseline model，我们改变随机数种子并重复实验 10 次。我们进行 wo-tailed pairwise t-test 来检测 FGCNN 和 best baseline model 之间的显著差异。

   

5. 整体性能：不同模型在测试集上的表现如下，其中下划线数字是 baseline 模型的最佳结果，粗体数字是所有模型的最佳结果。可以看到：

   • 首先，在大多数情况下，非神经网络模型的表现比神经网络模型差。原因是深度神经网络可以学习复杂的特征交互，比没有特征交互建模的模型（即 LR ），或通过简单的内积来建模特征交互的模型（即 FM 和 FFM ）要好得多。

   • 其次，FGCNN 在三个被评估的数据集上取得了所有模型中最好的性能。它明显优于最佳 baseline 模型，在 Criteo, Avazu, Huawei App Store 数据集上的 AUC 分别提高了 0.05%, 0.14%, 0.13% （ logloss 分别改善了 0.09%, 0.24%, 0.79% ），这表明了 FGCNN 的有效性。

   • 第三，在 Criteo, Avazu, Huawei App Store 数据集上，在生成的新特征的帮助下 FGCNN 在 AUC 方面比 IPNN 分别高出0.11%, 0.19%, 0.13% （在 logloss 方面分别改善了 0.2%, 0.29%, 0.79% ）。这表明生成的特征是非常有用的，它们可以有效地减少传统 DNN 的优化难度，从而导致更好的性能。

   • 第四，直接应用 CNN 的 CCPM 在神经网络模型中取得了最差的性能。此外，CCPM 在 Criteo 数据集和 Avazu 数据集上的表现比 FFM 差。这表明，直接使用传统的 CNN 进行 CTR 预测任务是不可取的，因为 CNN 被设计为生成 neighbor pattern ，而特征的排列顺序在推荐场景中通常没有意义。

     然而，在 FGCNN 中，我们利用 CNN 的优势来提取 local pattern ，同时辅以重组层来提取 global feature interaction 并生成新的特征。因此，可以实现更好的性能。

   

6. FGCNN 与不同模型的兼容性：如前所述，FGCNN 的深度分类器可以采用任何高级深度神经网络。这里我们选择不同的模型作为 Deep Classifeir 来验证特征生成的效果，结果如下表所示。可以看到：

   • 首先，在生成的新特征的帮助下，所有模型的性能都得到了提高，这表明了生成的特征的有效性，并显示了 FGCNN 的兼容性。
   • 其次，我们观察到，当只使用原始特征时，DeepFM 总是优于 DNN 。但是当使用被增强的特征时，FGCNN+DNN 优于FGCNN+DeepFM。可能的原因是 DeepFM 将输入特征的内积加到了最后一个 MLP 层，这可能会在 embeddinng 上引起矛盾的梯度更新（与 MLP 相比）。这可能是 IPNN （将乘积结果馈入 MLP ）在所有数据集中都优于 DeepFM 的原因之一。

   总之，结果表明：FGCNN 模型可以被视为一个通用框架，通过自动生成新的特征来增强现有的神经网络。

   平均而言，FGCNN 对 DeepFM 和 IPNN 等先进模型的提升不显著。

   

7. FGCNN 变体的有效性：我们进行实验来研究 FGCNN 中的每个组件对最终性能的贡献。每个变体都是通过移除或替换 FGCNN 中的一些组件而产生的：

   • Removing Raw Features：在这个变体中，原始特征没有被馈入到深度分类器中，只有生成的新特征被馈入深度分类器。
   • Removing New Features：这个变体移除了特征生成。实际上，它等同于 IPNN 。
   • Applying MLP for Feature Generation：在这个变体中，特征生成被 MLP 取代，MLP 将每个隐层的输出作为新特征。这个变体使用相同的隐层，并在每一层生成与 FGCNN 相同数量的特征。
   • Removing Recombination Layer：这个变体是为了评估重组层如何补充 CNN 从而捕获 global feature interaction 。重组层被从特征生成中移除，因此池化层的输出直接作为新特征。每层生成的新特征的数量与 FGCNN 保持一致。

   结果如下表所示。可以看到：

   • 首先，仅有原始特征的FGCNN 、或仅有新生成的特征的FGCNN 的性能比两者兼有的 FGCNN 要差。这一结果表明，生成的特征是对原始特征的良好补充，这两者都很关键。

     移除原始特征时，效果下降不显著。此时馈入后续 Deep Classifier 的输入向量长度减少一半，可以大幅降低计算量。因此，仅用新生成的特征，是一个比较好的 tradeoff 。

   • 其次，与 FGCNN 相比，应用 MLP 进行特征生成的性能下降，表明 MLP 在从大量的参数中识别稀疏的但重要的特征组合方面效果不佳。CNN 通过使用共享卷积核简化了学习的困难，它的参数少得多，可以得到所需的组合。此外，MLP 重新组合由 CNN 提取到的 neighbor feature interaction ，以产生 global feature interaction 。

   • 第三，移除重组层将限制生成的特征为 neighbor feature interaction 。由于原始特征的排列顺序在 CTR 预测任务中没有实际意义，这种限制会导致失去重要的 nonneighbor feature interaction ，从而导致性能下降。

   

8. 超参数研究：FGCNN 模型有几个关键的超参数，即卷积核的高度 $h^i$$h^i$ 、卷积核的数量 $m_c^i$$m_c^i$、卷积层的数量 $n_c$$n_c$ 、以及用于生成新特征的核的数量 $m_r^i$$m_r^i$。在本小节中，为了研究这些超参数的影响，我们在 Criteo 和 Huawei App Store 数据集上，通过改变一个超参数而固定其他参数来研究FGCNN 模型的工作情况。

   • 卷积核的高度：卷积核的高度 $h^i$$h^i$ 控制卷积层的感知范围。高度越大，neighbor pattern 中涉及的特征就越多，但需要优化更多的参数。为了研究其影响，我们将高度从 2 增加到数据集的 field 数量 $n_f$$n_f$ 。结果如下图所示。

     可以看到：随着卷积核高度的增加，性能一般先升后降。结果表明，随着卷积核中涉及的特征越来越多，可以学习到更高阶的特征交互，从而使性能提高。然而，由于有用的特征交互通常是稀疏的，更大的高度会给有效学习它们带来更多的困难，从而导致性能下降。这一观察结果前面的发现一致，即应用 MLP 进行特征生成时，性能会下降。

   • 卷积层的数量：如下图所示，随着卷积层数量 $n_c$$n_c$ 的增加，FGCNN 的性能得到了提高。请注意，更多的层通常会导致更高阶的特征交互。因此，该结果也显示了高阶特征交互的有效性。

   • 用于生成新特征的核的数量：我们在不同重组层中使用相同的 $m_r$$m_r$ ，然后我们试验了 $m_r$$m_r$ 在各种取值下的性能，如下图所示。可以看到：随着生成的特征越多，性能就会逐渐提高。

   这些结果验证了我们的研究思路，即：

   • 首先识别稀疏的但重要的特征交互是有用的，这可以有效降低 DNN 的学习难度。
   • 然而，有用的特征交互可能是稀疏的和有限的。如果产生了太多的特征，额外的新特征是有噪声的，这将增加 MLP 的学习难度，导致性能下降。

   

9. 对原始特征的顺序进行混洗的效果：如前所述，CNN 的设计是为了捕获 local neighbor feature pattern ，所以它对原始特征的排列顺序很敏感。在我们的 FGCNN 模型中，重组层的设计是基于 CNN 提取的 local pattern 来学习 global feature interaction 。直观地说，如果原始特征的顺序被混洗，我们的模型应该比传统 CNN 的结构有更稳定的性能。因此，为了验证这一点，我们比较了两种情况的性能：with/without Recombination Layer 。原始特征的排列顺序被随机地混洗多次，两个被比较的模型都是在相同的混洗后的排列顺序下进行的。

   如下图所示，有重组层的模型比没有重组层的模型取得了更好的、更稳定的性能。这表明，在重组层的帮助下，FGCNN 可以大大减少改变原始特征排列顺序的副作用，这也证明了我们模型的鲁棒性。

   根据结果来看，似乎重组层的提升也不太明显？

   

三十五、AutoCross[2019]

1. 众所周知，机器学习方法的性能在很大程度上取决于特征的质量。由于原始特征很少产生令人满意的结果，因此通常进行手动 feature generation 从而更好地表达数据并提高学习性能。然而，这通常是一项乏味且 task-specific 的工作。这促使了自动化的 feature generation ，这也是 AutoML 的一个主要话题。第四范式 4Paradigm 是一家致力于让更多人使用机器学习技术的公司，并且也致力于这个主题。

   特征交叉，即稀疏特征的叉积 cross-product ，是捕获 categorical feature 之间的交互的一种很有前途的方法，广泛用于增强从表格数据中的学习。表格数据中，每一行对应一个样本、每一列对应一个 distinct 特征。

   • 特征交叉表示特征的共现，它可能与 target label 高度相关。例如，交叉特征 "job x company" 表示一个人在特定公司从事特定工作，这是预测个人收入的一个强大特征。
   • 特征交叉还增加了数据的非线性，这可能会提高学习方法的性能。例如，线性模型的表达能力受到其线性的限制，但可以通过交叉特征来扩展。
   • 最后但并非最不重要的是，显式生成的交叉特征具有高度的可解释性，这是许多真实世界业务中的一个吸引人的特性，例如医疗和欺诈检测。

   然而，枚举所有交叉特征可能会导致学习性能下降，因为它们可能是不相关的或冗余的，会引入噪声，并增加学习难度。因此，只应生成有用且重要的交叉特征，但它们通常是 task-specific 。在传统的机器学习应用中，人类专家大量参与特征工程，努力为每项任务生成有用的交叉特征，并以试错的方式使用其领域知识。此外，即使是经验丰富的专家，当原始特征的数量很大时也可能会遇到麻烦。人工特征交叉的人力需求和难度大大增加了应用机器学习技术的总成本，甚至阻碍了许多公司和组织充分利用其数据。

   这提出了对自动特征交叉的巨大需求，这是论文 《AutoCross: Automatic Feature Crossing for Tabular Data in Real-World Applications》提出的工作目标。除了主要目标，即以高效率的、高效果的方式自动化特征交叉之外，论文还需要考虑其他几个要求：

   • 简单性要求：用户友好且易于使用。

     大多数现有的自动特征生成方法的性能在很大程度上取决于一些超参数。如 ExploreKit 中的阈值、《Simple and scalable response prediction for display advertising》 中的降采样率、以及基于深度学习的方法中的网络架构。这些超参数应该由用户为每个 specific task 正确确定或仔细调优，这需要用户有专业的机器学习知识。

   • 分布式计算：现实世界企业中的大量的数据和特征使得分布式计算成为必须。特征交叉方法应考虑计算成本、传输成本、以及存储成本。

   • 实时推理需求：实时推理涉及许多真实世界的业务。在这种情况下，一旦输入了实例，就应该立即生成特征并进行预测。

   总结上述需求，自动特征交叉工具需要具有高效果、高效率、简单性，能够针对分布式计算进行优化，并实现快速推理。为了解决这些挑战，论文提出了 AutoCross 。AutoCross 是一种自动特征交叉工具，专门为具有大量 categorical feature 的表格数据设计。

   论文主要贡献如下：

   • 提出了一种高效的 AutoML 算法，从而在广泛的搜索空间中显式地搜索有用的交叉特征。它能够构造高阶交叉特征，这可以进一步提高学习性能。
   • AutoCross 具有高度简单性和最小化的超参数暴露。论文提出 successive mini-batch gradient descent 和多粒度离散化。它们提高了特征交叉的效率和效果，同时避免了仔细的超参数设置。
   • AutoCross 针对分布式计算进行了充分优化。通过设计，这些算法可以降低计算成本、传输成本、和存储成本。
   • 在 benchmark 和真实世界数据集上进行大量实验，结果验证了 AutoCross 的效率和效果。它可以显著提高广义线性模型的性能，同时保持较低的推理延迟。研究还表明，AutoCross 可以结合深度模型，这意味着可以结合显式特征生成和隐式特征生成的优势，进一步提高学习性能。

2. 相关工作：这里简要回顾与 AutoCross 大致相关的一些工作，并说明它们不符合我们的目的的原因。

   • FM 寻求原始特征的低维 embedding ，并捕获它们的交互。然而，这种交互并不是显式地被构建的（通过 embedding 被间接地构建）。此外，FM 可能过度泛化和/或引入噪声，因为FM 枚举了所有可能的交互，而不管该交互是否有用。
   • 还有一些 embedded feature selection/generation 方法，如 group lasso 和 gradient boost machine: GBM ，它们本质上伴随着模型训练来识别、或隐式地构建有用的特征。然而，这些方法通常难以处理 large scale 问题（其中，从categorical feature 生成了高维稀疏数据），和/或计算问题（当特征数量很大时，如考虑高阶特征交叉）。
   • 最后，itemstes 在数据挖掘社区中得到了很好的研究。与交叉特征一样，它们也表示属性的共现。然而，不同之处在于 itemsets 中的元素通常是相同的类型，例如，所有元素都是商品。此外， itemsets 主要用于 rule-based 的机器学习技术，如 frequent pattern 和 association rule 。这些技术可能难以推广，并且在规则数量较大时推理速度较慢（因为检索成本高）。

35.1 模型

35.1.1 动机

1. 通过对原始特征的叉积的结果进行向量化来构建交叉特征：

   $$\begin{array}{}\text{(20)}& {\overrightarrow{\mathbf{c}}}_{i,j,\cdots ,k}=\text{vec}({\overrightarrow{\mathbf{f}}}_i\otimes {\overrightarrow{\mathbf{f}}}_j\otimes \cdots \otimes {\overrightarrow{\mathbf{f}}}_k)\end{array}$$

   其中：${\overrightarrow{\mathbf{f}}}_i$$\mathbf{\vec f}_i$ 为二元的特征向量（通过 one-hot encoding 或哈希技巧）；vec() 函数把张量展平为向量；$\otimes$$\otimes$ 为向量的叉积。

   交叉特征也是二元的特征向量。如果交叉特征使用三个或更多个原始特征，我们称它为高阶交叉特征。这里将陈述我们工作的动机。

2. 虽然大多数早期的自动特征生成工作集中于原始特征的二阶交互，但是趋势表明：考虑更高阶（即，阶次高于两阶）的交互将使得数据更 informative 和 discriminative 。与其他高阶交互一样，高阶交叉特征可以进一步提高数据质量，提高学习算法的预测能力。例如三阶交叉特征 item x item x region 可以是在某些节日期间推荐区域性偏好的食物的一个强大特征。然而，在现有的工作中还没有发现高阶交叉特征的显式生成。接下来，我们将说明：现有的特征生成方法要么不能生成高阶交叉特征、要么不能满足我们的业务需求。

   • 一方面，基于搜索的 feature generation 方法采用显式搜索策略来构造有用的特征或特征集。许多这样的方法专注于数值特征，并且不生成交叉特征。至于现有的特征交叉方法，它们没有设计成执行高阶特征交叉。

   • 另一方面，存在基于深度学习的 feature generation 成方法，其中特征之间的交互由特定网络隐式地或显式地表达。人们提出了各种深度学习模型来处理 categorical 特征，如 FM 、PNN 等。还有一些工作将深度学习模型和额外的结构相结合，这些结构包括：

     • 手动设计的特征，如 Wide & Deep 。
     • FM，如 DeepFM, xDeepFM 。
     • 其它特征构建组件，如 Deep & Cross Network 。

     其中，xDeepFM 提出了一种 compressed interaction network: CIN 来显式捕获 embedded feature 之间的高阶交互，并证明优于上述其它基于深度学习的方法。这是通过对 embedded feature 之间执行 element-wise 乘积来实现的：

     $$\begin{array}{}\text{(21)}& {\overrightarrow{\mathbf{e}}}_{i,j,\cdots ,k}=\left({\mathbf{W}}_i{\overrightarrow{\mathbf{f}}}_i\right)\circ \left({\mathbf{W}}_j{\overrightarrow{\mathbf{f}}}_j\right)\circ \cdots \circ \left({\mathbf{W}}_k{\overrightarrow{\mathbf{f}}}_k\right)\end{array}$$

     其中：$\circ$$\circ$ 表示逐元素乘积，${\mathbf{W}}_i$$\mathbf W_i$ 为 embedding 矩阵，${\mathbf{W}}_i{\overrightarrow{\mathbf{f}}}_i\in {\mathbb{R}}^D$$\mathbf W_i\mathbf{\vec f}_i\in \mathbb R^D$ ，$D$$D$ 为 emebdding size 。

     然而，如以下Proposition 所述，上述方法得到的特征仅仅是 embedded high-order cross feature 的特殊情况。此外，深度模型在推理方面相对较慢，这使得我们必须在实时推理系统中部署模型压缩或其他加速技术。

3. Proposition：存在无限多具有 $D$$D$ 行的 embedding 矩阵 $\mathbf{C}$$\mathbf C$ ，使得：对于任意的二元向量 $\overrightarrow{\mathbf{x}},\overrightarrow{\mathbf{y}}$$\mathbf{\vec x},\mathbf{\vec y}$ 以及它们之间的叉积 $\overrightarrow{\mathbf{z}}$$\mathbf{\vec z}$ ，不存在任何 embedding 矩阵 $\mathbf{A}$$\mathbf A$ 和 $\mathbf{B}$$\mathbf B$ 从而满足以下等式：

   $$\begin{array}{}\text{(22)}& \left(\mathbf{A}\overrightarrow{\mathbf{x}}\right)\circ \left(\mathbf{B}\overrightarrow{\mathbf{y}}\right)=\left(\mathbf{C}\overrightarrow{\mathbf{z}}\right)\end{array}$$

   证明见原始论文的附录。

4. 受高阶交叉特征的有用性、以及现有工作的局限性的启发，在本文中，我们旨在提出一种新的自动特征交叉方法，该方法足够有效地、高效地自动生成高阶交叉特性，同时满足我们的业务需求（即简单、针对分布式计算进行优化，并实现快速推理）。下表比较了AutoCross 和其他现有方法。

   

35.1.2 AutoCross

1. 下图给出了 AutoCross 的概览，其中包括三个部分：通用工作流、组件算法、底层基础设施。

   • 从用户的角度来看，AutoCross 是一个黑匣子，它将训练数据和特征类型（即 categorical 、numerical 、时间序列等等）作为输入，并输出一个 feature producer 。feature producer 可以快速执行 AutoCross 学到的 crossing 从而转换输入数据，然后用于模型训练或推理。feature producer 使用哈希技巧来加速特征生成。与基于深度学习的方法相比，feature producer 占用的计算资源明显更少，因此特别适合于实时推理。

     在黑匣子（下图中的 "Flow" 部分）内，数据将首先进行预处理，其中包括确定超参数、填充缺失值、数值特征离散化。然后，在由两个步骤组成的循环中迭代构建有用的特征集：

     • 特征集生成：生成具有新的交叉特征的候选特征集。
     • 特征集评估：评估候选特征集并选择最佳的作为新的解决方案。

     一旦满足某些条件，该迭代过程就终止。

   • 从实现的角度来看（下图中的 "Infrastructures" 部分），AutoCross 的基础是基于参数服务器（parameter server: PS ）架构的分布式计算环境。数据按 block 缓存在内存中，每个 block 包含一小部分训练数据（这里指的是所有样本的一小部分特征，而不是一小部分样本的所有特征）。 worker 访问缓存的 data block ，生成相应的特征，并对其进行评估。特征管理器控制特征集的生成和评估。过程管理器控制特征交叉的整个过程，包括超参数适配、数据预处理、工作流控制、以及程序终止。

   • 连接工作流程和基础设施的算法是本文的主要重点（下图的 "Algorithms" 部分）。每种算法都对应于工作流程中的一部分：

     • 我们使用 beam search 来生成特征集，以探索广泛的搜索空间。
     • 我们使用 field-wise 逻辑回归和 successive mini-batch gradient descent 来评估特征集。
     • 我们使用多粒度离散化来进行数据预处理。

     这些算法的选择、设计和优化考虑了分布式计算的简单性和成本。

     AutoCross 算法的原理比较简单明了，但是需要基础架构的支持，不太容易在实践中使用。

     此外，AutoCross 仅能评估表格型数据，无法处理序列特征、也无法处理 multi-set 特征（即，一个 field 上取多个值），更无法处理图片和文本特征。

    

   

2. 问题定义：为了便于讨论，首先我们假设所有原始特征都是 categorical的。数据以 multi-field categorical 的形式表示，其中每个 field 是通过 encoding （ one-hot encoding 或哈希技巧）从 categorical feature 中生成的 binary 向量。给定训练数据 ${\mathcal{D}}_{\text{TR}}$$\mathcal D_\text{TR}$，我们将它拆分为训练集 ${\mathcal{D}}_{\text{tr}}$$\mathcal D_\text{tr}$ 、验证集 ${\mathcal{D}}_{\text{vld}}$$\mathcal D_\text{vld}$ 。然后我们用特征集 $\mathcal{S}$$\mathcal S$ 来表达 ${\mathcal{D}}_{\text{tr}}$$\mathcal D_\text{tr}$ ，并用学习算法 $\mathcal{L}$$\mathcal L$ 来学习模型 $\mathcal{L}({\mathcal{D}}_{\text{tr}},\mathcal{S})$$\mathcal L(\mathcal D_\text{tr}, \mathcal S)$ 。为了评估该模型，我们用相同的特征集 $\mathcal{S}$$\mathcal S$ 来表达验证集 ${\mathcal{D}}_{\text{vld}}$$\mathcal D_\text{vld}$ ，并最大化指标 $\mathcal{E}(\mathcal{L}({\mathcal{D}}_{\text{tr}},\mathcal{S}),{\mathcal{D}}_{\text{vld}},\mathcal{S})$$\mathcal E(\mathcal L(\mathcal D_\text{tr},\mathcal S), \mathcal D_\text{vld}, \mathcal S)$ 。

   现在，我们定义 feature crossing problem 为：

   $$\begin{array}{}\text{(23)}& \underset{\mathcal{S}\subseteq \mathcal{A}(\mathcal{F})}{max}\mathcal{E}(\mathcal{L}({\mathcal{D}}_{\text{tr}},\mathcal{S}),{\mathcal{D}}_{\text{vld}},\mathcal{S})\end{array}$$

   其中：$\mathcal{F}$$\mathcal F$ 为 ${\mathcal{D}}_{\text{TR}}$$\mathcal D_\text{TR}$ 的原始特征集，$\mathcal{A}(\mathcal{F})$$\mathcal A(\mathcal F)$ 为包括原始特征和所有可能交叉特征的特征集。

3. 特征集生成：假设原始特征集的大小为 $d$$d$ ，这也是交叉特征的最高阶次。$\mathcal{A}(\mathcal{F})$$\mathcal A(\mathcal F)$ 的大小为：

   $$\begin{array}{}\text{(24)}& \text{card}(\mathcal{A}(\mathcal{F}))=\sum _{k=1}^d{C}_d^k=2^d-1\end{array}$$

   所有可能的特征集合为 $2^{(2^d-1)}$$2^{(2^d-1)}$ 。显然，在如此广泛的空间中搜索全局最优特征集是不切实际的。为了在有限的时间和计算资源下找到一个适度的解决方案，我们采用贪婪的方法迭代地构造一个局部最优特征集。

   在 AutoCross 中，我们考虑下图所示的树结构空间 $\mathcal{T}$$\mathcal T$ ，其中每个节点对应于一个特征集，根是原始特征集 $\mathcal{F}$$\mathcal F$ 。为了简单起见，在本示例中，我们将两个特征 A 和 B 的交叉表示为 AB ，更高阶的交叉特征也是类似的表示方式。对于一个节点（一个特征集），它的每个子节点都是通过在当前节点的基础上添加自身元素的一个 pair-wise crossing 来构造的。交叉特征之间（或交叉特征和原始特征之间、原始特征和原始特征之间）的 pair-wise 交互将导致高阶特征交叉。

   树结构空间 $\mathcal{T}$$\mathcal T$ 考虑 $\mathcal{A}(\mathcal{F})$$\mathcal A(\mathcal F)$ 中的所有可能特征，但排除了一部分子集。使用 $\mathcal{T}$$\mathcal T$ ，搜索特征集等同于识别从 $\mathcal{T}$$\mathcal T$ 的根节点到特定节点的路径。这可以通过迭代地将交叉特征添加到维护的特征集中来实现。然而，$\mathcal{T}$$\mathcal T$ 的大小是 $O((d^2/2{)}^k)$$O\left((d^2/2)^k\right)$ ，其中 $k$$k$ 是生成的交叉特征的最大数量。$\mathcal{T}$$\mathcal T$ 的大小随着 $k$$k$ 呈指数增长。因此，遍历 $\mathcal{T}$$\mathcal T$ 将非常昂贵。为了解决这个问题，我们使用 beam search 来进一步提高效率。

   beam search 的基本思想是在搜索过程中只扩展最有前途的节点：

   • 首先，我们生成根节点的所有子节点，评估它们对应的特征集，然后选择性能最佳的子节点进行下一次访问。
   • 在接下来的过程中，我们扩展当前节点并访问其最有希望的子节点。

   当过程终止时，处于结束位置的节点就是我们得到的结果特征集。

   通过这种方式，我们在大小为 $O((d^2/2{)}^k)$$O\left((d^2/2)^k\right)$ 的搜索空间中仅考虑 $O(k{d}^2)$$O(kd^2)$ 个节点，并且成本随着交叉特征的最大数量 $k$$k$ 线性增长。它使我们能够高效地构造高阶交叉特征。下图展示了一个搜索路径，该路径从原始特征集 {A, B, C, D}开始，到解决方案 {A, B, C, D, AB, CD, ABC, ABCD} 结束。

   

4. AutoCross 中特征集选择算法：

   • 输入：原始特征集 $\mathcal{F}$$\mathcal F$ 、训练集 ${\mathcal{D}}_{\text{tr}}$$\mathcal D_\text{tr}$ 、验证集 ${\mathcal{D}}_{\text{vld}}$$\mathcal D_\text{vld}$

   • 输出：结果特征集 ${\mathcal{S}}^{\ast }$$\mathcal S^*$

   • 算法步骤：

     • 初始化当前节点：${\mathcal{S}}^{\ast }\leftarrow \mathcal{F}$$\mathcal S^*\leftarrow \mathcal F$ 。

     • 迭代直到满足停止条件：

       • 特征集生成：通过将 ${\mathcal{S}}^{\ast }$$\mathcal S^*$ 的不同 pair-wise crossing 添加到 ${\mathcal{S}}^{\ast }$$\mathcal S^*$ 中，从而得到不同的子节点（每个子节点一个 crossing）。
       • 特征集评估：对所有这些子节点进行评估，得到最佳子节点 ${\mathcal{S}}^{\prime }$$\mathcal S^\prime$ 。
       • 替换：${\mathcal{S}}^{\ast }\leftarrow {\mathcal{S}}^{\prime }$$\mathcal S^*\leftarrow \mathcal S^\prime$ 。

   这里的 beam size = 1，也可以考虑 beam size = s ，$s$$s$ 为超参数。

5. 特征集评估：特征集选择算法的关键步骤是评估候选特征集的性能。这里候选集 $\mathcal{S}$$\mathcal S$ 的性能表示为 $\mathcal{E}(\mathcal{L}({\mathcal{D}}_{\text{tr}},\mathcal{S}),{\mathcal{D}}_{\text{vld}},\mathcal{S})$$\mathcal E(\mathcal L(\mathcal D_\text{tr},\mathcal S), \mathcal D_\text{vld}, \mathcal S)$ ，简称 $\mathcal{E}(\mathcal{S})$$\mathcal E(\mathcal S)$ 。为了直接估计 $\mathcal{E}(\mathcal{S})$$\mathcal E(\mathcal S)$ ，我们需要在由 $\mathcal{S}$$\mathcal S$ 表示的训练集上学习具有算法 $\mathcal{L}$$\mathcal L$ 的模型，并评估模型在验证集上的性能。尽管这种方法很准确，但对特征集的直接评估通常相当昂贵。为了提高评估效率，我们在 AutoCross 中提出了 field-wise 逻辑回归和 successive mini-batch 。

   • field-wise 逻辑回归：我们加速特征集评估的第一个努力是 field-wise逻辑回归（ field-wise LR ）。这里进行了两种近似：

     • 首先，我们使用用 mini-batch 梯度下降训练的逻辑回归来评估候选特征集，并使用相应的性能来近似实际使用的学习算法 $\mathcal{L}$$\mathcal L$ 的性能。我们选择逻辑回归，因为它简单、可扩展、速度快、可解释。

     • 其次，在模型训练期间，我们只学习新添加的交叉特征的权重，而其他权重是固定的。因此，训练是 'field-wise' 的。例如，假设当前的特征集是 ${\mathcal{S}}^{\ast }＝\text{A, B, C, D}$$\mathcal S^*＝ \text{{A, B, C, D}}$ ，并且我们希望评估候选特征集 $\mathcal{S}＝\text{A, B, C, D, AB}$$\mathcal S ＝ \text{{A, B, C, D, AB}}$ ，那么只有新的 AB 特征的权重需要被学习。

       具体而言，给定一个样本，假设 ${\overrightarrow{\mathbf{x}}}_s$$\mathbf{\vec x}_s$ 为当前特征集对应的特征向量，${\overrightarrow{\mathbf{x}}}_c$$\mathbf{\vec x}_c$ 为新增交叉特征对应的特征向量。那么 LR 模型为：

       $$\begin{array}{}\text{(25)}& P(y=1\mid \overrightarrow{\mathbf{x}})=\text{sigmoid}({\overrightarrow{\mathbf{x}}}_s\cdot {\overrightarrow{\mathbf{w}}}_s+{\overrightarrow{\mathbf{x}}}_c\cdot {\overrightarrow{\mathbf{w}}}_c)=\text{sigmoid}({\overrightarrow{\mathbf{x}}}_c\cdot {\overrightarrow{\mathbf{w}}}_c+b_{\text{sum}})\end{array}$$

       其中：${\overrightarrow{\mathbf{w}}}_s$$\mathbf{\vec w}_s$ 是固定的，$b_{\text{sum}}$$b_\text{sum}$ 是一个标量对应于 ${\overrightarrow{\mathbf{x}}}_s\cdot {\overrightarrow{\mathbf{w}}}_s$$\mathbf{\vec x}_s\cdot \mathbf{\vec w}_s$ 。

     下图展示了 field-wise LR 如何在参数服务器架构上工作。 field-wise LR 从几个方面提高了特征集评估的效率：

     • 存储： worker 只存储 ${\overrightarrow{\mathbf{x}}}_c$$\mathbf{\vec x}_c$ （以 sparse 格式）和 $b_{\text{sum}}$$b_\text{sum}$，而不是实例的完整 representation 。在内存缓存中存储 $b_{\text{sum}}$$b_\text{sum}$ 的开销可以忽略不计。
     • 传输：内存缓存和 worker 之间的传输内容是 $b_{\text{sum}}$$b_\text{sum}$ 、以及用于构造 ${\overrightarrow{\mathbf{x}}}_c$$\mathbf{\vec x}_c$ 的特征的哈希值。因此，不需要传输完整的实例 representation 。
     • 计算：只更新 ${\overrightarrow{\mathbf{w}}}_c$$\mathbf{\vec w}_c$ ，减少了 worker 和 parameter server 的计算负担。所有 worker 都直接获取存储的 $b_{\text{sum}}$$b_\text{sum}$，因此不需要为每个 worker 的每个 mini-batch 重复计算 $b_{\text{sum}}$$b_\text{sum}$。

     一旦 field-wise LR 完成，我们就在验证集 ${\mathcal{D}}_{\text{vsl}}$$\mathcal D_\text{vsl}$ 上评估结果模型的性能。我们使用 AUC, accuracy, negative logloss 等指标来评估 $\mathcal{S}$$\mathcal S$ 的质量。显然，评估结果是 $\mathcal{E}(\mathcal{S})$$\mathcal E(\mathcal S)$ 的近似值，以更高的效率换取准确性。然而，由于特征集评估的目的是识别最有前景的候选，而不是准确地估计候选集的性能，因此，如果算法能够以高概率识别最佳候选，则准确性的降低是可接受的。实验部分报告的实验结果证明了 field-wise LR 的有效性。

     

   • Successive Mini-batch Gradient Descent：在 AutoCross 中，我们使用 successive mini-batch gradient descent 方法来进一步加速 field-wise LR 的训练。这是由最初针对 multi-arm bandit 问题提出的 successive halving 算法所推动的。 successive halving的特点是计算资源的高效分配和高度简单。

     在我们的例子中，我们将每个候选特征集视为一个 arm ，拉动手臂就是用数据块训练相应的 field-wise LR 模型。拉动手臂的即时回报是 partially trained model 的验证 AUC 。训练数据平均分为 $N\ge \sum _{k=0}^{\lceil {\log }_{2}n\rceil -1}{2}^k$$N\ge \sum_{k=0}^{\lceil\log_2n\rceil - 1} 2^k$ 个数据块，其中 $n$$n$ 是候选特征集的数量。然后我们调用下述算法来识别最佳候选特征集。

     successive mini-batch gradient descent 将更多的资源分配给更有前景的候选集。唯一的超参数 $N$$N$ （即，数据的数量），需要根据数据集的大小和工作环境来选择。用户不需要调优 mini-batch size 和采样率。

     可以看到：

     • 在训练的早期，数据块的数量较少，此时更多的候选特征集会被评估。
     • 在训练的后期，数据块的数量较多，此时只有最优秀的候选特征集会被评估。

     每次迭代之后，数据块翻倍、候选特征集的数量减半。

     Successive Mini-batch Gradient Descent: SMBGD 算法：

     • 输入：所有的候选集 $\mathbb{S}=\{{\mathcal{S}}_i{\}}_{i=1}^n$$\mathbb S = \{\mathcal S_i\}_{i=1}^n$ ，训练数据平均分为 $N$$N$ 个数据块。

     • 输出：最佳候选集 ${\mathcal{S}}^{\prime }$$\mathcal S^\prime$

     • 算法步骤：

       迭代：$k=0,1,\cdots ,\lceil \log 2n\rceil -1$$k=0,1,\cdots,\lceil \log2 n\rceil-1$ ，迭代步骤为：

       • 使用 $2^k$$2^k$ 个数据块来更新所有候选集 $\mathcal{S}\in \mathbb{S}$$\mathcal S\in \mathbb S$ 的 field-wise LR 模型。
       • 在验证数据集上评估所有候选集 $\mathcal{S}\in \mathbb{S}$$\mathcal S\in \mathbb S$ 的模型。
       • 保留头部 50% 的候选集：$\mathbb{S}\leftarrow \text{top-half}(\mathbb{S})$$\mathbb S \leftarrow \text{top-half}(\mathbb S)$ ，向下取整。
       • 如果 $\mathbb{S}$$\mathbb S$ 只有一个元素，则返回（作为最佳候选集 ${\mathcal{S}}^{\prime }$$\mathcal S^\prime$ ）。

6. 预处理：在 AutoCross 中，我们在数据预处理步骤中对数值特征进行离散化。为了实现离散化的自动化并避免对人类专家的依赖，我们提出了一种多粒度离散化方法。基本思想很简单：我们将每个数值特征离散化为几个 categorical feature 而不是一个 categorical feature ，每个 categorical feature 具有不同的粒度，而不是微调粒度。下图给出了用四个级别的粒度来离散化数值特征的示例。由于考虑了更多级别的粒度，因此更可能获得有前景的结果。

   为了避免离散化导致的特征数量急剧增加，一旦生成了这些特征，我们就使用 field-wise LR （不考虑 $b_{\text{sum}}$$b_\text{sum}$）来评估它们，只保留最好的一半。

   剩下的问题是如何确定粒度级别。经验丰富的用户可以人工设置一组值。如果未指定任何值，AutoCross 将使用 $\{{10}^p{\}}_{p=1}^P$$\{10^p\}_{p=1}^P$ 作为默认值，其中 $P$$P$ 是基于规则（考虑可用内存、数据规模、特征数量等等）确定的整数。

   此外，AutoCross 将在预处理步骤中调用超参数调优程序，以找到 LR 模型的最佳超参数。它们将在随后涉及的所有 LR 模型中使用。

   

7. Termination：AutoCross 使用三种终止条件：

   • 运行时条件：用户可以设置 AutoCross 的最大 runtime 。时间过去后，AutoCross 终止并输出当前解决方案 ${\mathcal{S}}^{\ast }$$\mathcal S^*$。此外，用户可以随时中断程序并获得当前时刻的结果。
   • 性能条件：在生成新的特征集之后，用其所有特征训练 LR 模型。如果与前一组相比，验证集性能下降，则程序终止。
   • 最大特征数：用户可以给出最大交叉特征数，这样当达到该数字时，AutoCross 停止。

35.2 实验

1. 数据集：来自 benchmark 、以及真实世界商业数据集（来自第四范式的客户，经过脱敏），所有数据集都是二分类问题。数据集信息如下表所示。

   

2. baseline 方法：

   • AC + LR：具有 AutoCross 生成的交叉特征的逻辑回归。
   • AC+W&D：Wide & Deep 模型，其中 wide 侧使用 AutoCross 生成的交叉特征。
   • LR (base)：采用原始特征的逻辑回归，作为 baseline 。
   • CMI+LR：具有交叉特征的逻辑回归，其中交叉特征通过 《Simple and scalable response prediction for display advertising》 中提出的方法来生成，采用条件互信息（conditional mutual information : CMI ）用作评估特征的指标。
   • Deep：具有 embedding layer 的深度模型，它隐式地生成特征交互。
   • xDeepFM：通过 compressed interaction network: CIN 显式生成特征的、 SOTA 的 deeplearning-based 方法。

   在这些方法中，AC+LR 和 AC+W&D 使用 AutoCross 生成的交叉特征，并证明了其增强线性模型和深度模型的有效性。CMI+LR 使用了一种典型的基于搜索的特征交叉方法。xDepFM 是遵从 Wide&Deep 框架的 SOTA 方法。所有这些方法都旨在处理具有 categorical feature 的表格数据。

3. 配置：特征以及模型在训练数据集、验证数据集（如果需要的话，为训练数据的 20%）上学习，然后通过测试 AUC 来评估不同方法的性能。

   • AutoCross 配置：超参数包括数据块数量 $N$$N$ 、多粒度离散化的粒度数量、停止条件。

     • 对于相对较小的数据集，即 Bank, Adult, Credit, Employee ， $N=2\sum _{k=0}^{\lceil {\log }_{2}n\rceil -1}{2}^k$$N=2\sum_{k=0}^{\lceil \log_2n\rceil -1}2^k$ 。这表明，最多 50% 的训练数据将用于连续小批量梯度下降。对于其他数据集，$N=5\sum _{k=0}^{\lceil {\log }_{2}n\rceil -1}{2}^k$$N=5\sum_{k=0}^{\lceil \log_2n\rceil -1}2^k$，这对应于最大 20% 的采样率。
     • 关于粒度级别，AutoCross 对所有数据集使用 $\{{10}^i{\}}_{i=1}^3$$\{10^i\}_{i=1}^3$。
     • 至于终止条件，我们只调用性能条件，即只有在新添加的交叉特征导致性能下降时，AutoCross 才会终止。

   • 逻辑回归配置：超参数包括学习率 $\alpha \in [0.005,1]$$\alpha\in [0.005, 1]$、L1 正则化系数 ${\lambda }_1\in [{10}^{-4},10]$$\lambda_1\in [10^{-4},10]$ 、L2 正则化系数 ${\lambda }_2\in [{10}^{-4},10]$$\lambda_2\in [10^{-4}, 10]$ 。

     在我们的实验中，我们在特征生成之前调用了一个超参数调优过程，采用 log-grid search。找到的最佳超参数应用于所有 LR 相关的模型。

   • CMI+LR 配置：我们只在 benchmark 数据集上测试 CMI+LR ，因为 CMI 无法处理多值 categorical feature 。我们使用多粒度离散化来转换数值特征。为了确保特征评估的准确性，我们使用所有训练数据来估计CMI ，Criteo 数据集是一个例外，我们将其降采样比率设置为 10% 。我们将最大交叉特征数设置为 15 。

   • 深度模型配置：我们使用 xDeepFM 的开源实现并在 AC+W&D 和 Deep 方法中使用深度组件。我们使用0.001 学习率，Adam 优化器，batch size = 4096 ，0.0001 的 L2 正则化惩罚。深度组件的 layer 的隐单元数量为 400 。对于 Criteo 数据集和其它数据集，CIN 组件分别采用 200 和 100 的隐单元数量。field embedding size = 10 。

     由于在 xDepFM 和 Deep 中不需要验证数据，因此我们不拆分训练集，并将其全部用于模型训练。

4. 效果：实验结果如下表所示，其中我们突出显示了每个数据集的前两个方法。可以看到：

   • AC+LR 在大多数情况下排名前二，并且通常优于基于深度学习的方法（ Deep 和 xDepFM ）。
   • AC+W&D 还显示出具有竞争力的性能，展示了 AutoCross 增强深度模型的能力。
   • 大多数情况下，AC+LR 和 AC+W&D 显示出比 xDepFM 更好的结果。

   

   下表显示了 AutoCross 带来的测试 AUC 改善。可以看到：AC+LR 和 AC+W&D 都实现了比 LR(base) 显著的改进，并且 AC+W＆D 也显著提高了 Deep 模型的性能。这些结果表明，通过生成交叉特征，AutoCross 可以使数据更 informative 和 discriminative ，并提高学习性能。AutoCross 取得的有前景的结果也证明了 field-wise LR 识别有用交叉特征的能力。

   

5. 高阶特征的效果：下图显示了为每个数据集生成的二阶/高阶交叉特征的数量，其中后者占相当大的比例。

   此外，在下表中，我们比较了仅生成二阶交叉特征的 CMI+LR 、以及考虑高阶交叉特征的 AC+LR 。我们可以看到，AC+LR 稳定且持续地优于 CMI+LR 。这一结果证明了高阶交叉特征的有用性。

   

6. 特征交叉的时间代价：下表报告了 AutoCross 在每个数据集上的特征交叉时间。下图显示了真实世界业务数据集上验证 AUC （ AC+LR ）与运行时的关系。用户可以看到这些曲线，并随时终止 AutoCross 以获得当前结果。

   是在什么硬件配置下测试的？论文提到，AutoCross 采用 PS 架构，因此这里用到了几个 parameter server 、几个 worker ？

   值得注意的是，由于 AutoCross 的高度简单性，不需要微调任何超参数，用户也不需要花费任何额外的时间来实现它。相比之下，如果使用基于深度学习的方法，则将在网络架构设计和超参数调优上花费大量时间。

   

7. 推断延迟：在线推理包括两个主要步骤：生成特征从而转换输入数据、推理以进行预测。深度学习方法结合了这些步骤。在下表中，我们报告了 AC+LR 、AC+W&D 、Deep 和 xDepFM 的推断时间。可以看到：AC+LR 在推断方面比其他方法快几个数量级。这表明，AutoCross 不仅可以提高模型性能，还可以确保其 feature producer 的快速推理。

   

三十六、InterHAt[2020]

1. 现有 CTR 预测模型的架构复杂度和计算复杂度一直在增加，以便学到多个特征的联合效应，即高阶特征（也叫做交叉特征），并获得更好的预测准确性。具体而言，$k$$k$ 阶特征指的是一个变量，该变量是原始特征集的一个 $k$$k$ 阶多项式。深度神经网络由于层数和单元数很多，具有很强的捕获丰富高阶信息的能力。

   然而，不断增长的模型复杂度有两个缺点：可解释性差、效率低。

   • 就可解释性而言，预测过程很难得到合理的解释，因为神经网络层的权重和激活 activation 通常被认为是不可解释的。例如，Wide&Deep 的 Wide 组件将叉积变换 cross-product transformation 应用于 feature embedding ，但未能量化和证明其对实际点击率预测性能的有效性。模型预测缺乏令人信服的理由，这给模型的可靠性和安全性蒙上了阴影。

   • 就效率而言，现有方法的效率低，因为深度神经网络的高阶交互特征的生成涉及 DNN 中极其繁重的矩阵计算。例如，xDeepFM 中的 compressed interaction network: CIN 通过一个外积层和一个全连接层来计算第 $(k+1)$$(k+1)$ 阶特征矩阵，这需要 embedding 维度的立方复杂度。Wide&deep 中的 Deep 组件具有多个全连接层，其中每个全连接层都涉及矩阵乘法。

     在实际应用中，效率问题是普遍而关键的。利用现有方法，学习大量现有特征、或新兴特征的 representation 在计算上可能是难以处理的。

   除了可解释性和效率问题，论文 《Interpretable Click-Through Rate Prediction through Hierarchical Attention》 还指出了另一个障碍：模型会影响重要的交叉特征的评估。不同的交叉特征可能对 CTR 具有冲突的影响，必须全面分析。例如，电影推荐记录 movie.genre = horror, user.age = young, time = 8am 具有冲突的因素：前两者的组合鼓励点击，而后两者的组合抑制点击（因为电影观看通常发生在晚上）。这种冲突问题是由特征交互在不同语义子空间中的多义性引起的。在这个例子中，当user.age=young 与两个不同的属性 movie.genre 和 time 组合时，user.age 的多义性交互对 CTR 产生相反的影响。然而，这个问题在很大程度上被现有的方法所忽略。

   为了解决上述问题，在论文 《Interpretable Click-Through Rate Prediction through Hierarchical Attention》 中，该论文提出了一个 Interpretable CTR prediction model with Hierarchical Attention: InterHAt 模型。InterHAt 模型以端到端的方式有效地学习不同阶次的显著特征作为解释性的洞察，并同时准确地预测 CTR 。

   具体而言，InterHAt 通过一种新颖的 hierarchical attention 机制显式地量化任意阶次的特征交互的影响，聚合重要的特征交互以提高效率，并根据学到的特征显著性来解释推荐决策。与 《Hierarchical attention networks for document classification》 的研究语言的 hierarchy （单词和句子）的 hierarchical attention network 不同，InterHAt 对特征阶次采用 hierarchical attention ，高阶特征是在低阶特征的基础上生成的。

   为了适应特征交互在不同语义子空间中的多义性，InterHAt 利用具有multi-head self-attention 的 Transformer 来全面研究不同的潜在特征交互。作者利用 Transformer 来检测特征交互的复杂多义性，并学习一个多义性增强的 feature list ，该列表用作 hierarchical attention layer 的输入。

   论文贡献如下：

   • 论文提出使用 InterHAt 进行 CTR 预测。具体而言，InterHAt 采用 hierarchical attention 来精确定位对点击有很大贡献的重要的单个特征、或不同阶次的交互特征。然后，InterHAt 可以基于各阶特征交互为 CTR 预测组成 attention-based 解释。
   • InterHAt 利用具有 multi-head self-attention 的 Transformer ，从而在不同潜在语义子空间中彻底分析特征之间可能的交互关系。据作者所知，InterHAt 是第一个方法使用具有 multi-head self-attention 的 Transformer 来学习潜在特征的多义性，从而以进行 CTR 预测。
   • InterHAt 预测 CTR 时无需使用需要大量计算成本的深层 MLP 。相反，它聚合了特征，因此节省了枚举指数级数量的特征交互的指开销。因此，它在处理高阶特征方面比现有算法更有效。
   • 在三个主要的 CTR 基准数据集( Criteo, Avazu, Frappe )、一个流行的推荐系统数据集( MovieLens-1M )和一个合成数据集上，论文进行了大量的实验来评估 InterHAt 的可解释性、效率和有效性。结果表明，InterHAt 解释了决策过程，在训练时间上实现了巨大的改善，并且仍然具有与 SOTA 的模型相当的性能。

2. 相关工作：

   • CTR 预测模型：

     • FM 为每个不同特征分配一个$d$$d$ 维可训练的 embedding 向量 ，并通过一阶特征和二阶特征的线性组合来进行预测。虽然 FM 可以推广到高阶情况，但高阶 FM 的计算复杂度为指数级，并且浅层架构的模型容量较低。
     • Field-aware Factorization Machine: FFM 假设特征在不同的 field 下可能具有不同的语义，并通过 field-specific feature representation 来扩展 FM 的思想。虽然它获得了比 FM 更好的效果，但是也增加了参数规模和计算量，并且更容易发生过拟合。
     • Attentional Factorization Machine: AFM 通过 attention net 扩展了 FM ，不仅提高了性能，还提高了可解释性。然而，由于 FM 固有的结构限制，AFM 只能学习二阶特征交互。
     • Wide&Deep 由 wide 组件和 deep 组件构成，它们本质上分别是广义线性模型和 MLP 。注意，deep 组件，即 MLP ，破坏了可解释性，因为 layer-wise transformation 是在 unit level 而不是 feature level 进行的，并且单个 unit level 取值不能携带特征的具体的、完整的语义信息。
     • Deep&Cross Network: DCN 与 Wide&Deep 略有不同，因为 DCN 用叉积变换取代了线性模型，从而将高阶信息与非线性深度特征相结合。
     • DeepFM 通过用 FM 作为 wide 组件来改进这两个模型，其中 deep MLP 组件捕获高阶特征交互，wide FM 捕获二阶特征交互。
     • xDeepFM 声称 MLP 实际上是建模隐式特征交互，因此作者引入 compressed interaction network: CIN 来建模显式特征交互。
     • 工业实践的最新成果包括 DIN 和 DIEN，它们分别建模用户的静态购物兴趣和动态购物兴趣。这两种方法都严重依赖于深度前馈网络，而这种网络通常是不可解释的。

     所有上述 CTR 预测模型都严重依赖于深度神经网络，并实现不断提高的性能。然而，正如一把双刃剑，深度学习算法在可靠性和安全性方面存在潜在风险。隐层的权重和激活 activation 很难解释，输入和输出之间的因果关系是掩藏的、不确定的。它们都没有提供任何 feature-level 的线索来解释为什么这种深度 feature learning 策略会增强或减弱 CTR 性能。

     相反，InterHAt 在 feature-level 上使用 attention-based 的解释来解决 CTR 预测。也就是说，InterHAt 没有不合理的深度 MLP 模块，并且InterHAt 仅工作在 feature level 上，这也提高了 InterHAt 的效率。

   • attention 机制：attention 机制最初是为 neural machine translation: NMT 提出的，它为源语言和目标语言之间密切相关的单词分配更大的权重，以便在翻译中关注重要的单词。NLP 中另一种形式的 attention 是自注意力，如 Transformer 架构。我们采用注意力机制来解释 InterHAt 模型的 CTR 预测。

36.1 模型

1. InterHAt 模型的整体架构如下图所示。

   Transformer with Multi-head Self-attention 可以视为是单个交互层的 AutoInt 模型。实验部分表明，该组件很重要，移除该组件会导致模型性能较大的下降。但是，实验部分并没有比较 InterHAT 和 AutoInt 的比较，因为二者都宣称是可解释的，并且 InterHAT 将 AutoInt 作为组件。

   Attentional Aggregation Layer 通过自注意力机制来获得不同阶次的、聚合所有 field 信息的 representation 向量，并将其用于预测和可解释。

   

2. Embedding Layer：输入特征包含一组 field $\mathcal{F}$$\mathcal F$ ，每个 field $f\in \mathcal{F}$$f\in \mathcal F$ 要么是 categorical 的、要么是 numerical 的。

   • 对于 categorical field ，每个 categorical value $v$$v$ 被分配一个可训练的 $d$$d$ 维 embedding ${\overrightarrow{\mathbf{e}}}_v^{(f)}\in {\mathbb{R}}^d$$\mathbf{\vec e}_v^{(f)}\in \mathbb R^d$。令 categorical field $f\in \mathcal{F}$$f\in \mathcal F$ 的取值为 $v$$v$ ，则该 field 的的 representation ${\overrightarrow{\mathbf{x}}}^{(f)}$$\mathbf{\vec x}^{(f)}$ 就是 $v$$v$ 的 emebdding ，即 ${\overrightarrow{\mathbf{x}}}^{(f)}={\overrightarrow{\mathbf{e}}}_v^{(f)}$$\mathbf{\vec x}^{(f)} = \mathbf{\vec e}_v^{(f)}$ 。
   • 对于 numerical field ，我们为每个 field 分配一个可训练的 $d$$d$ 维 embedding 。令 $v_f$$v_f$ 为数值 field $f\in \mathcal{F}$$f\in \mathcal F$ 的归一化值，${\overrightarrow{\mathbf{e}}}^{(f)}\in {\mathbb{R}}^d$$\mathbf{\vec e}^{(f)}\in \mathbb R^d$ 为该 field 分配的 embedding，那么该 field 的 representation 为 ${\overrightarrow{\mathbf{x}}}^{(f)}=v_f\times {\overrightarrow{\mathbf{e}}}^{(f)}$$\mathbf{\vec x}^{(f)}=v_f\times \mathbf{\vec e}^{(f)}$ 。

   考虑所有的 field ，定义初始的 input representation matrix 为：

   $$\begin{array}{}\text{(26)}& {\mathbf{X}}_0={({\overrightarrow{\mathbf{x}}}_0^{(1)},{\overrightarrow{\mathbf{x}}}_0^{(2)},\cdots ,{\overrightarrow{\mathbf{x}}}_0^{(m)})}^{\mathrm{\top }}\in {\mathbb{R}}^{m\times d}\end{array}$$

   其中： $m=|\mathcal{F}|$$m=|\mathcal F|$ 为 field 数量。

3. Multi-head Transformer：在 CTR 预测任务重，我们将特征朝着不同极性（消极或积极）的协同效应（即，特征交互）定义为多义性 polysemy 。因此，我们为 InterHAt 采用了一个 Multi-head Transformer 从而捕获丰富的 pair-wise 特征交互，并且学习不同语义子空间中特征交互的多义性。

   给定输入矩阵 ${\mathbf{X}}_0$$\mathbf X_0$ ，Transformer head $i$$i$ 的 representation ${\mathbf{H}}_i$$\mathbf H_i$ 被定义为：

   $$\begin{array}{}\text{(27)}& \begin{array}{c}{\mathbf{H}}_i={\text{softmax}}_i\left(\frac{\mathbf{Q}{\mathbf{K}}^{\mathrm{\top }}}{{\sqrt{d}}_k}\right)\mathbf{V}\in {\mathbb{R}}^{m\times d_k}\\ \mathbf{Q}={\mathbf{X}}_0{\mathbf{W}}_i^{(Q)},\mathbf{K}={\mathbf{X}}_0{\mathbf{W}}_i^{(K)},\mathbf{V}={\mathbf{X}}_0{\mathbf{W}}_i^{(V)}\end{array}\end{array}$$

   其中：${\mathbf{W}}_i^{(Q)},{\mathbf{W}}_i^{(K)},{\mathbf{W}}_i^{(V)}\in {\mathbb{R}}^{d\times d_K}$$\mathbf W_i^{(Q)}, \mathbf W_i^{(K)}, \mathbf W_i^{(V)}\in \mathbb R^{d\times d_K}$ 为投影矩阵，$d_k$$d_k$ 为第 $i$$i$ 个 head 的维度。

   hidden feature ${\mathbf{H}}_i$$\mathbf H_i$ 的组合构成了 augmented representation matrix ${\mathbf{X}}_1$$\mathbf X_1$ ，该矩阵保留了每个特征的固有信息和多义信息。我们拼接 $\{{\mathbf{H}}_i\}$$\{\mathbf H_i\}$ ，然后馈入到一个带 ReLU 的前馈层从而学习非线性：

   $$\begin{array}{}\text{(28)}& {\mathbf{X}}_1=\text{ReLU}(\text{FeedForward}([{\mathbf{H}}_1;{\mathbf{H}}_2;\cdots ;{\mathbf{H}}_h]{\mathbf{W}}_m))\in {\mathbb{R}}^{m\times d}\end{array}$$

   其中：${\mathbf{W}}_m\in {\mathbb{R}}^{(h{d}_k)\times d}$$\mathbf W_m\in \mathbb R^{(hd_k)\times d}$ ，$h$$h$ 为 head 数量，“ $;$$;$ ” 表示矩阵拼接（沿着 embedding 维度）。

4. Hierarchical Attention： augmented representation matrix ${\mathbf{X}}_1$$\mathbf X_1$ 作为 hierarchical attention layer 的输入。hierarchical attention layer 学习特征交互并同时产生解释。然而，由于组合爆炸，通过枚举所有可能的组合来计算高阶 multi-feature interaction 是昂贵的。因此，我们在计算更高阶次的特征交互之前，首先聚合当前阶次的特征交互。即，为了生成第 $(i+1)$$(i+1)$ 阶的交叉特征 ${\mathbf{X}}_{i+1}$$\mathbf X_{i+1}$ ，我们首先将第 $i$$i$ 阶的交叉特征 ${\mathbf{X}}_i=({\overrightarrow{\mathbf{x}}}_i^{(1)},{\overrightarrow{\mathbf{x}}}_i^{(2)},\cdots ,{\overrightarrow{\mathbf{x}}}_i^{(m)})$$\mathbf X_i=\left(\mathbf{\vec x}_i^{(1)},\mathbf{\vec x}_i^{(2)},\cdots,\mathbf{\vec x}_i^{(m)}\right)$ 聚合到向量 ${\overrightarrow{\mathbf{u}}}_i$$\mathbf{\vec u}_i$ ：

   $$\begin{array}{}\text{(29)}& \begin{array}{c}{\overrightarrow{\mathbf{u}}}_i=\text{AttentionalAgg}({\mathbf{X}}_i)=\sum _{j=1}^m{\alpha }_i^{(j)}{\overrightarrow{\mathbf{x}}}_i^{(j)}\\ {\alpha }_i^{(j)}=\frac{\exp ({\overrightarrow{\mathbf{c}}}_i\cdot \text{ReLU}\left({\mathbf{W}}_i{\overrightarrow{\mathbf{x}}}_i^{(j)}\right))}{\sum _{j^{\prime }\in \mathcal{F}}\exp ({\overrightarrow{\mathbf{c}}}_i\cdot \text{ReLU}\left({\mathbf{W}}_i{\overrightarrow{\mathbf{x}}}_i^{(j^{\prime })}\right))}\end{array}\end{array}$$

   其中：${\alpha }_i^{(j)}\in \mathbb{R}$$\alpha_i^{(j)} \in \mathbb R$ 为第 $j$$j$ 个 field 在第 $i$$i$ 个 attentional aggregation layer 的注意力权重；${\mathbf{W}}_i\in {\mathbb{R}}^{s\times d}$$\mathbf W_i\in \mathbb R^{s\times d}$ 为 layer weight ；${\overrightarrow{\mathbf{c}}}_i\in {\mathbb{R}}^s$$\mathbf{\vec c}_i\in \mathbb R^s$ 为上下文向量；$s$$s$ 为注意力空间大小。这里也可以采用其它注意力机制，如 gated attention mechanism 。

   这里采用的是自注意力机制。

   然后我们根据 ${\overrightarrow{\mathbf{u}}}_i$$\mathbf{\vec u}_i$ （代表了 ${\mathbf{X}}_i$$\mathbf X_i$ ）和 ${\mathbf{X}}_1$$\mathbf X_1$ 来计算 ${\mathbf{X}}_{i+1}$$\mathbf X_{i+1}$ ：

   $$\begin{array}{}\text{(30)}& {\overrightarrow{\mathbf{x}}}_{i+1}^{(j)}={\overrightarrow{\mathbf{u}}}_i\circ {\overrightarrow{\mathbf{x}}}_1^{(j)}+{\overrightarrow{\mathbf{x}}}_i^{(j)}\end{array}$$

   其中：$\circ$$\circ$ 表示 Hadamard product 。

   根据 ${\overrightarrow{\mathbf{x}}}_{i+1}^{(j)}={\overrightarrow{\mathbf{u}}}_i\circ {\overrightarrow{\mathbf{x}}}_1^{(j)}+{\overrightarrow{\mathbf{x}}}_i^{(j)}=\sum _{j^{\prime }=1}^m{\alpha }_i^{(j^{\prime })}\times ({\overrightarrow{\mathbf{x}}}_i^{(j^{\prime })}\circ {\overrightarrow{\mathbf{x}}}_1^{(j)})+{\overrightarrow{\mathbf{x}}}_i^{(j)}$$\mathbf{\vec x}_{i+1}^{(j)} = \mathbf{\vec u}_i\circ \mathbf{\vec x}_{1}^{(j)} + \mathbf{\vec x}_{i}^{(j)} = \sum_{j^\prime=1}^m \alpha_i^{(j^\prime)}\times \left(\mathbf{\vec x}_{i}^{(j^\prime)}\circ\mathbf{\vec x}_{1}^{(j)}\right) + \mathbf{\vec x}_{i}^{(j)}$ ，则第 $i+1$$i+1$ 层的第 $j$$j$ 个特征 ${\overrightarrow{\mathbf{x}}}_{i+1}^{(j)}$$\mathbf{\vec x}_{i+1}^{(j)}$ 是由两部分组成：

   • 第 $i$$i$ 层的第 $j$$j$ 个特征 ${\overrightarrow{\mathbf{x}}}_i^{(j)}$$\mathbf{\vec x}_{i}^{(j)}$，这是残差连接。
   • 第 1 层的第 $j$$j$ 个特征 ${\overrightarrow{\mathbf{x}}}_1^{(j)}$$\mathbf{\vec x}_{1}^{(j)}$ 与所有第 $i$$i$ 层特征的交叉的加权和，权重为第 $i$$i$ 层的 self-attention 的权重。

   那么，是否可以用 ${\overrightarrow{\mathbf{x}}}_1^{(j)}$$\mathbf{\vec x}_1^{(j)}$ 作为 query 向量从而用传统的注意力机制来计算 ${\alpha }_i^{(j^{\prime })}$$\alpha_i^{(j^\prime)}$ ？

   最后，模型预测时利用的是 ${\overrightarrow{\mathbf{u}}}_i$$\mathbf{\vec u}_i$ 而不是 ${\overrightarrow{\mathbf{x}}}_i^{(j)}$$\mathbf{\vec x}_{i}^{(j)}$ 。

   通过一系列的 attentional aggregation layer ，我们得到了从第 1 ~ k 阶的交叉特征。这些层组成了一个 hierarchy，表示从低阶到高阶所抽取的特征。

   最后，我们联合所有的 attentional aggregation $\mathbf{U}=({\overrightarrow{\mathbf{u}}}_1,{\overrightarrow{\mathbf{u}}}_2,\cdots ,{\overrightarrow{\mathbf{u}}}_k)$$\mathbf U = \left(\mathbf{\vec u}_1,\mathbf{\vec u}_2,\cdots,\mathbf{\vec u}_k\right)$ 来预测点击率。$\mathbf{U}$$\mathbf U$ 收集了 $k$$k$ 阶的所有的组合特征的语义。

5. 目标函数和优化：最终的预测函数为 $\hat{y}=g(\mathbf{U})$$\hat y = g(\mathbf U)$ ：

   $$\begin{array}{}\text{(31)}& \begin{array}{c}\hat{y}=g(\mathbf{U})=\text{sigmoid}(\text{MLP}({\overrightarrow{\mathbf{u}}}_f))\\ {\overrightarrow{\mathbf{u}}}_f=\text{AttentionalAgg}(\mathbf{U})=\sum _{j=1}^k{\alpha }_f^{(j)}{\overrightarrow{\mathbf{u}}}_j\\ {\alpha }_f^{(j)}=\frac{\exp ({\overrightarrow{\mathbf{c}}}_f\cdot \text{ReLU}\left({\mathbf{W}}_f{\overrightarrow{\mathbf{u}}}_j\right))}{\sum _{j=1}^k\exp ({\overrightarrow{\mathbf{c}}}_f\cdot \text{ReLU}\left({\mathbf{W}}_f{\overrightarrow{\mathbf{u}}}_{j^{\prime }}\right))}\end{array}\end{array}$$

   其中：${\alpha }_f^{(j)}\in \mathbb{R}$$\alpha_f^{(j)}\in \mathbb R$ 为 ${\overrightarrow{\mathbf{u}}}_j$$\mathbf{\vec u}_j$ 的聚合权重；${\overrightarrow{\mathbf{c}}}_f,{\mathbf{W}}_f$$\mathbf{\vec c}_f, \mathbf W_f$ 为待学习的参数。

   目标函数为交叉熵：

   $$\begin{array}{}\text{(32)}& \mathcal{L}(\mathrm{\Theta })=\left(\sum _{t\in \mathcal{D}}[-y_t\log {\hat{y}}_t-(1-y_t)\log (1-{\hat{y}}_t)]\right)+\lambda ||\mathrm{\Theta }|{|}_2\end{array}$$

   其中：$\mathcal{D}$$\mathcal D$ 为训练集，$\mathrm{\Theta }$$\Theta$ 为所有的训练参数，$\lambda$$\lambda$ 为 L2 正则化系数。

   我们采用 Adam 优化器来优化目标函数。

6. 可解释性：我们使用注意力分布 $({\overrightarrow{\alpha }}_1,{\overrightarrow{\alpha }}_2,\cdots ,{\overrightarrow{\alpha }}_k,{\overrightarrow{\alpha }}_f)$$\left(\vec \alpha_1,\vec \alpha_2,\cdots,\vec \alpha_k,\vec \alpha_f\right)$ 作为理解 CTR 预测结果的重要因素，其中：

   • ${\overrightarrow{\alpha }}_f=({\alpha }_f^{(1)},{\alpha }_f^{(2)},\cdots ,{\alpha }_f^{(k)})$$\vec\alpha_f = \left(\alpha_f^{(1)},\alpha_f^{(2)} ,\cdots,\alpha_f^{(k)} \right)$ 为 final attentional aggregation layer 的注意力分布，其中的 top 权重确定了那些阶次的交叉特征 ${\mathbf{X}}_i$$\mathbf X_i$ 对于预测结果最重要。
   • ${\overrightarrow{\alpha }}_i=({\alpha }_i^{(1)},{\alpha }_i^{(2)},\cdots ,{\alpha }_i^{(m)}),1\le i\le k$$\vec\alpha_i = \left(\alpha_i^{(1)},\alpha_i^{(2)} ,\cdots,\alpha_i^{(m)} \right), 1\le i\le k$ 为第 $i$$i$ 个 attentional aggregation layer 的注意力分布，其中的 top 权重决定了哪些单个 feature field ${\overrightarrow{\mathbf{x}}}_i^{(j)}$$\mathbf{\vec x}_i^{(j)}$ 对于交叉特征 ${\mathbf{X}}_i$$\mathbf X_i$ 最重要。

   注意，注意力机制仅突出了特征的显著性，因此不期望它生成完全人类可读的解释。

   最后，根据上述步骤，我们可以识别不同阶次的所有特征。对点击行为的解释是通过逐层地、逐阶次地识别显著特征来解释的。