三十三、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. 问题定义：为了便于讨论，首先我们假设所有原始特征都是