| 作者：YEN
| 单位：东北大学
| 研究方向：推荐系统、计算广告
本文分享一篇发表在SIGIR’21的点击率预估方面的文章，AutoPI：一种自动发掘点击率预估中强大特征交互的通用方法[1]
论文核心内容：使用Neural Architecture Search（NAS）对CTR问题中特征交互进行搜索
点击率（CTR）预估是个性化广告和推荐系统中最典型的机器学习任务，建模强大的特征交互是CTR中一个关键的挑战。尽管对于仅有少量数据的场景手工定制特征交互是有效的，但这样的方式在大数据量的场景中通常需要费力而乏味的特征工程。近年来，学者们提出了几种基于神经架构搜索（NAS）方法来自动设计特征交互。然而，现有的方法只探索有限的交互类型和连接方式，导致模型泛化能力较弱。为了解决这些问题，这篇论文提出了一种更通用的自动化方法来构建强大的特征交互，命名为AutoPI。AutoPI采用了更通用的搜索空间，从具有代表性的专家设计结构中提取模块来构成AutoPI计算图边上的交互和连接算子。它允许对各种强大的特征交互进行搜索，以在各种应用程序中产生更高的AUC和更低的Logloss。此外，AutoPI采用了一种基于梯度的搜索策略，以便显著的降低结构搜索的计算成本。通过实验，作者在不同的基准数据集上对AutoPI进行了评估，展示了AutoPI相对于专家架构和前沿的基于NAS算法的性能和效率。
这篇论文的核心贡献总结如下：
- 设计一个通用的、高效的搜索空间来生成强大的特征交互。具体来说，构造搜索空间时，通过对已有文献中有代表性的交互算子进行提取和模块化，然后设计了一个定制的基于单元（Cell）的计算图来寻找算子间的最佳连接。
- 为了提高搜索效率，AutoPI采用了一种基于梯度的搜索策略。引入架构超参数来松弛离散搜索空间，并求解Bi-level优化问题迭代优化架构参数和边上的连接权值。
- 使用了两种训练技术用于缓解连续架构和的离散架构之间的性能差距。
- 通过大量实验证明了AutoPI在不同量级的数据集上的泛化和效率。与SOTA方法相比，AutoPI方法在公共和私有数据集上的AUC平均分别提高了
和
。此外，与NAS基线相比，基于梯度的搜索策略可以减少
的搜索开销。
相关背景
CTR问题
预估用户是否会对一个推荐的物品进行点击（CLICK=0 | 1）是CTR中的关键任务。CTR预估问题的训练数据一般组织为下面的多域（Field）多特征（Feature）的形式。其中，‘CITY, BRAND’表示域（Field），‘LA，London，B1’表示特征(Feature)，其中每个特征属于且只属于一个特定的域。一般而言域的量级是几十到几千，特征的量级是几百万到几十亿。
CTR训练数据格式[2]
CTR预估问题的重要挑战是如何对特征交互进行建模。如下图所示，现有模型可粗糙的分为两类：单塔和双塔结构。单塔结构（如FNN, PNN, NFM, ...）隐式的建模特征的高阶交互；多塔结构（如Wide&Deep, DeepFM, XDeepFM, ...）显式的建模特征的低阶和高阶交互，同时隐式的建模特征的高阶交互。
深度CTR架构中单塔(左)和双塔(右)模式的示意图[3]
CTR模型训练时一般被建模为二分类问题的形式，进而通过梯度下降算法优化LogLoss以训练模型参数:
NAS神经架构搜索
深度学习领域，虽然大多数流行和成功的模型架构（AlexNet, ResNet, VGG, GoogleNet...）都是由人工专家设计的，但这并不意味着这些成功的架构就已经探索了整个网络架构空间并确定了他们就是最佳选择。如果我们采用一种系统的、自动的学习高性能模型架构的方法，我们将有更好的机会找到最佳的解决方案，这就是Neural Architecture Search(NAS)的目标。
NAS[4]的方法可以分解为三个组件：
- 搜索空间：NAS搜索空间定义了一组操作（例如卷积、全连接、池化）以及如何将操作连接起来形成有效的网络架构。搜索空间的设计通常涉及人类的专业知识，以及不可避免的人类偏见。现有的主要的方法包括：顺序逐层操作(Sequential Layer-wise Operations)；基于单元的代表(Cell-based Representation)；分层结构(Hierarchical Structure)等。
- 搜索算法：NAS搜索算法对网络体系结构候选对象进行抽样。它接受子模型性能指标作为奖励（例如，高精度，低延迟等目标），并优化生成高性能架构候选。现有的主要的方法包括：随机搜索（Random Search, 一般是拿来作为Baseline）；强化学习（Reinforcement Learning）；进化算法（Evolutionary Algorithms）；梯度下降（Gradient Descent）。
- 性能评估策略：我们需要测量、估计或预测大量被抽样出来的子模型的性能，以获得用于对搜索算法学习效果的反馈。候选评估的过程可能非常昂贵，许多新的方法被提出来节省时间或计算资源。现有的主要的方法包括：从零开始训练（Training from Scratch）；代理任务性能（Proxy Task Performance）；参数共享（Parameter Sharing）；
NAS领域有很多优秀的工作，在本文中，我们先不看具体的细节，简单的介绍一篇NAS的代表作：Differentiable Architecture Search (DARTS)[5]，也是这篇论文用到的方法。
DARTS在搜索超图的每条路径上引入了连续的松弛，使得通过梯度下降联合训练架构参数和权值成为可能。下图说明了DARTS模型如何在directed acyclic graph(DAG)超图的边缘上应用连续松弛并确定最终模型。
DARTS架构
假设这里的结构是使用有向无环图(DAG)表示。一个单元是一个由
个节点组成的拓扑有序序列。每个节点都可以看作是有一个潜在的表示
需要学习。每条边
都绑定到某个操作
，比如(convolution, max pooling, zero)等。当前节点的表示由它之前的节点得到：
为了使搜索空间连续，DARTS将特定操作的绝对选择放松为所有操作的softmax，而架构搜索的任务简化为学习一组混合概率(
) ：
因此整个问题转化为了一个bilevel optimization问题：
即在训练集上找到最优的模型参数
, 在验证集上找到最优的权重参数
。我们训练几个步骤后固定住
，更新权重参数
：
DARTS算法流程
AutoPI模型问题定义
文章对CTR预测的总体框架总结如下图所示。从自底向上的角度来看，深度CTR预测模型有三个基本阶段:（i）输入转换（离散输入特征映射为连续Embedding），（ii）建模不同的特征交互，（iii）多交互方式集成（如DeepFM集成了基于FM和DNN的交互方式）。
原文用词：(i) input transformation, (ii) modeling diverse feature interactions, (iii) multi-interaction ensemble.
CTR模型由固定部分（嵌入层和分类器）和可搜索部分（特征交互和多种交互方式集成）组成
定义1（input transformation）：假设有
个Field, 原始输入特征一般被表示为：
。其中
是第
个Field的one-hot特征表示。由于特征表示是非常稀疏和高维的，我们采用嵌入层（Embedding）将稀疏特征转换为低维和密集的实值向量
。所有输入特征经过嵌入层后堆叠得到嵌入矩阵
。为了避免深模型和浅模型之间的干扰，这篇文章采用对偶嵌入(即两个独立的嵌入层
和
)分别构建低阶和高阶特征交互（上图省略了对偶嵌入）。
定义2（modeling diverse feature interactions）：关键问题是确定应该构建哪种交互类型和交互的阶数来形成有意义的交叉特征。这篇文章参考xDeepFM论文的方式定义p阶交叉特征为：
这一部分通常是基于专家设计的方式，在本文希望用NAS的方式来处理这个问题。
定义3（multi-interaction ensemble）：在手工设计的CTR预测模型中，最关键的设计之一是多种交互集成，它结合了各种交互阶数和交互类型，形成一个多塔结构。对于最终的预测，将所有塔的交叉特征串联，然后输入到单层感知机（SINGLE-LAYER PERCEPTRON），如下所示:
最后通过优化LogLoss来学习。
AutoPI方法概述
AutoPI的工作流程下图所示。AutoPI架构大致包括三部分:(i)搜索空间，(ii)搜索策略和(iii)性能评估。具体来说，作者采用了基于单元（Cell）的搜索空间，它由计算图和运算空间组成。然后采用高效的基于梯度的搜索策略来搜索算子的最佳连接。
搜索空间的设计：
作者将手工模型的交互总结为三个关键因素:(1)交互的阶：需要结合多少操作来形成一个交互。(2)用于构造交互的操作：应该选择哪些操作，以及如何连接操作来构建交互。(3)多交互集成：哪些交互需要用到最终的预测。因此，AutoPI的搜索空间由运算空间和定制的计算图组成。图中的每个节点代表一个隐式表示(即任意阶交叉特征)，每条边是来自操作空间的一个算子。为了更好地推广到各种应用中，搜索空间应该在计算图中包含足够的节点，同时尽可能在操作空间中包含不同的交互操作。另外，图中包含用于多交互集成的多塔结构，用来提高性能。需要注意的是，多塔结构中算子的连接也会自动优化。因此，作者从具有代表性的手工模型中提取出多样化的交互操作，形成操作空间。此外，还设计了两种类型的计算单元作为图的构建块，包括交互单元（interaction cell）和集成单元（ensemble cell）。
计算图：本节首先介绍两种类型的计算单元。如下图所示，每个cell都是一个有向无环图，由一个有序的节点序列组成，包括输入节点、中间节点和输出节点，其中
是一个超参数，表示interaction cell中的最大阶和ensemble cell中的tower数。
AutoPI将可搜索部分分解为interaction cell和ensemble cell
每一个结点
是一个隐式表示（一个特征矩阵），每个有向边
是一个交互算子
的连接。每个中间节点根据它所有前序节点进行计算：
因此，学习cell的任务减少到为其连接的边选择最佳的算子。
AutoPI有两种类型的单元提供两种主要功能：（1）交互单元建模高阶特征交互。具体来说，交互单元有一个输入节点(节点
)，也就是对偶嵌入层之一产生的输入嵌入，三个中间节点(节点
)表示中间交叉特征，输出节点(节点
)，通过组合运算（即卷积）融合所有中间节点的特征矩阵。（2）集合单元建模了低阶和高阶交互的集合。与交互单元不同，集成单元有两个输入节点，其中节点
是交互单元生成的高阶交叉特征矩阵，节点
是另一个双嵌入层生成的输入嵌入矩阵。节点
在集合单元函数中作为两个塔的输出。输出节点
是所有中间节点的连接。由于中间节点的数量是可配置的，因此集成单元中的tower的数量可以适应各个场景。值得注意的是，虽然两个cell是独立的有向无环图，但也可以采用联合优化，而不是顺序优化cell。
算子空间：为了搜索各种交互，我们的搜索空间应该包含各种交互操作。我们提取并模块化交互式操作时需要考虑以下因素:
- 功能(Functionality):我们的搜索空间中的运算符应该相互补充并适应广泛场景中的应用程序。例如，复杂算子(如单层感知机、卷积层等)具有较强的学习能力，能够建模更复杂的交叉特征。相比之下，简单的操作符(如LR、SENET层等)可以学习一般表示，而过拟合的风险很小。
- 运算符粒度(Operator granularity)：细粒度操作符(如FM、SLP等)比粗粒度操作符(如AFM、MLP等)具有更大的组合灵活性。由于NAS方法对计算开销敏感，高效的操作空间要求操作符具有较低的时间空间复杂度。因此，更可取的是细粒度操作符。
- 尺度调整（Dimension alignment）：在我们的计算图中，我们需要保持输出特征的维数
和输入维度
一致。
根据上述原则,我们从代表中提取操作算子，如
LR, inner product, hadamard product, outer product, cross layer, none, skip-connection, self-attention, FM, logarithmic transformation layer, SENET layer, 2d convolution, 1d convolution等。
经过广泛的实验和仔细的比较，我们最终确定了以下操作来形成操作空间:
Skip-connection, SENET Layer, Self-attention, FM, Single-layer Perceptron, 1d Convolution
注意，除了Skip-connection，每个操作符后面都有一个非线性激活函数（例如RELU(
)）。
搜索策略
和Darts模型一样，AutoPI也是使用离散空间连续化的方式，通过求解Bi-level优化问题来学习模型参数和边上的连接参数。
具体来说，让
表示候选的交互算子集合，每个交互算子定义为运用在
上的函数
。对于每一个cell，目标是
中从选择最合适的操作来连接两个节点。连续放松的关键是组合优化问题转换为找到一组合适的权重
来组合
之间所有的操作算子。
除了操作级别的参数
，AutoPI也定义了边级别的参数
来选择interaction cell中重要的节点对。
因此，神经架构搜索的任务简化为学习两组连续变量。
另外，AutoPI对每个算子都做了Batch Normalization操作。
性能评估
我们的方法的目标是找到强大的交互，以便在目标数据上获得较高的预测性能。我们在搜索过程中获得了验证集上性能最好的体系结构参数，然后将连续体系结构编码转换为离散体系结构编码。具体的，在体系结构参数搜索完成后，我们可以保留前
个最强的算子（这篇论文中
）。其中算子的强度定义为：
另外，论文还引入了两种额外的训练技术（Reducing Discrete Loss和Noisy Skip-connection）来减少连续结构变为离散结构的性能差距。
实验效果
数据集
论文使用了四个公开数据集和五个私有数据集进行验证，各数据集基本信息统计如下：
AutoPI实验数据集
实验效果
- AutoRec-R, AutoRec-G, AutoRec-B分别表示AutoRec的random, greedy, Bayesian版本。
- AutoPI-D (AutoPI with Bilevel optimization in DARTS)
- AutoPI-R (AutoPI with random search strategy)
不同算法在公共基准上的有效性比较
不同算法在真实场景下的有效性比较
SOTA方法的架构搜索效率比较
搜索空间中删除不同的算子性能变化
AutoPI在Avazu和Criteo数据集上搜索出的结构
参考资料
[1]
Ze Meng, Jinnian Zhang, Yumeng Li, Jiancheng Li, Tanchao Zhu, Lifeng Sun.A General Method For Automatic Discovery of Powerful Interactions In Click-Through Rate Prediction.SIGIR, 2021.: https://arxiv.org/abs/2105.10484
[2]
Weinan Zhang, Jiarui Qin, Wei Guo, Ruiming Tang, Xiuqiang He. Deep Learning for Click-Through Rate Estimation. IJCAI, 2021.: https://arxiv.org/abs/2104.10584v1
[3]
Weinan Zhang, Jiarui Qin, Wei Guo, Ruiming Tang, Xiuqiang He. Deep Learning for Click-Through Rate Estimation. IJCAI, 2021.: https://arxiv.org/abs/2104.10584v1
[4]
Neural Architecture Search: https://lilianweng.github.io/lil-log/2020/08/06/neural-architecture-search.html
[5]
Hanxiao Liu, Karen Simonyan, Yiming Yang. DARTS: Differentiable Architecture Search. ICLR，2019.: https://openreview.net/forum?id=S1eYHoC5FX
