Question

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 的快速推理。