论文标题：Cognitive Evolutionary Search to Select Feature Interactions for Click-Through Rate Prediction

作者：Runlong Yu, Xiang Xu, Yuyang Ye, Qi Liu, Enhong Chen

单位：中国科学技术大学、认知智能全国重点实验室、罗格斯大学

论文链接：

代码链接： or

视频链接：

本文介绍了陈恩红、刘淇教授团队在 KDD23 会议上发表的研究成果——“认知进化搜索：基于交叉特征选择的点击率预估算法”。针对交叉特征选择问题，该团队另辟蹊径，从认知智能和进化计算角度，提出了一种认知进化搜索（Cognitive EvoLutionary Search, CELS）算法。传统处理交叉特征的方法多是采用专家设计的预定义操作来统一构造所有特征对，这种方式可能会引入不合适的交叉特征，从而产生不必要的噪声，并增加训练的复杂度。与之相比，认知进化搜索引入一种新颖的思路：通过任务驱动模型演化以构建交叉特征。认知进化搜索将交叉特征视为基因组，将模型视为生物体，将任务视为环境，借鉴基因延展性发展环境适应性的原理，通过诊断模型的适应度来模拟生物体在自然选择中的存活率。由此，认知进化搜索超越了仅依据表面层次来评估个体，转而选择在基因层面对模型进行深入诊断，并促进针对性的变异机制。实验结果表明认知进化搜索可以针对不同的任务发展为不同的模型，且在预测指标上展现最优的性能。

1
研究背景在当今的智能营销系统中，点击率（Click-Through Rate, CTR）预估具有举足轻重的地位。其目标在于预测用户对推荐项目的点击数占总展示次数的比率。广告主努力通过提高此比率来增加投资回报，同时，流量主也试图通过此方式更高效地将网络流量转化为收入。

如图1所示，在这个场景中，广告交易平台起到了枢纽的作用，它连通了广告主和流量主之间的交易需求。为了优化广告预算，精准的点击率预估显得至关重要。任何对点击率的误估可能会导致预算的浪费，或者是错失潜在的机会。

考虑到当前商业营销业务的规模，点击率预估无疑吸引了学术界和工业界的广泛关注。通过用户建模和深度学习等技术来筛选出对点击率预估有价值的特征，已经成为研究的热点。

图1 点击率预估大量的研究结果显示，特征对之间的交叉作用能带来超越单一特征的预测效果 [1]。这引出一个基础研究问题：如何有效地选择交叉特征。见图2所示。在特征选择领域，有3种主要的方法，即过滤器方法（filter）、包装器方法（wrapper）以及嵌入式方法（embeded）。过滤器方法通过使用各种度量指标来评估特征与目标的相关程度，然后依赖排序算法来挑选出与目标高度相关的特征。包装器方法以模型性能为目标函数，评估不同特征子集的表现。为了实现这个目标，需要在所有可能的特征子集上反复地训练模型。另一方面，嵌入式方法将特征选择与训练过程相融合，使得两者成为一个整体过程。在实践中，由于稳定性较差和效率较低，过滤器和包装器方法通常不适用于大规模或高维度的数据集 [2]。相对而言，嵌入式方法由于其较低的计算需求和较少的过拟合问题，越来越受到人们的青睐。

图2 交叉特征选择如图3所示，当前的嵌入式方法主要依赖专家设计的操作进行特征对的交叉。例如，因式分解机（Factorization Machines, FM）通过将特征投影到低维向量并利用内积来建模特征交叉 [3]。另一方面，Field-aware FM 允许特征具有多个隐向量与不同特征域的特征进行交叉 [4]。然而，由于浅层模型的表示能力有限，引起学者关注使用深度学习模型建模高阶交叉特征。例如，Attentional FM 和 Neural FM 将深度神经网络堆叠在FM的输出上以建模高阶交叉特征 [5, 6]。即便如此，这种深度学习模型捕获的低阶交叉特征仍然较少。解决这个问题的方法之一是采用像 Wide&Deep 这样的混合结构，它结合了浅层和深层组件，以实现学习模型的记忆和泛化功能 [7]。例如，DeepFM 就是使用FM层来代替了浅层部分 [8]，类似地 Deep&Cross 和 xDeepFM 的浅层部分则分别采用位级和向量级特征的外积形式 [9, 10]。

图3 嵌入式方法尽管现有的嵌入式方法已经取得了一定的成功，但它们大都遵循一个模式，即在专家指导下，通过相同的预定义操作来建模交叉特征，并等同地枚举所有的特征和交叉特征。这其中存在着两个局限：首先，这些方法无法确保模型的学习能力，因为它们的架构对于具体的任务和数据缺乏适应性。其次，无关的特征和交叉特征可能会引入不必要的噪声，从而使训练过程变得更加复杂。举图4的例子来说，专家们可能会定义一种按位求和的操作，但是对于用户收入和手机操作系统之间的按位求和可能会产生无关的交叉特征，从而增加模型训练的复杂性。

图4 嵌入式方法的局限因此，我们期望理想的交叉特征选择方法应当能自适应地演化模型，以在任务指导下选择适当的操作进行特征对之间的交叉。一种可能实现模型演化的方法是进化学习，这是一种受自然启发的元启发式算法，能够解决机器学习中的复杂搜索问题。它也包括进化式自动机器学习（AutoML）方法 [11]。一般用于特征选择的进化学习算法由五个步骤组成 [11]，见图5所示，包括：1）编码；2）初始化；3）搜索策略；4）特征集建模；以及5）模型适应度评估（Model Fitness Evaluation）。

图5 进化学习现有的研究表明，由于模型适应度评估的限制，基于进化算法的特征选择主要应用于过滤器和包装器方法 [2, 11]。具体来说，包装器方法将学习算法的性能作为其评估标准，而过滤器方法则依赖于数据的内在特征。另一方面，嵌入式方法在选择特征的同时也学习分类器。因为传统的进化算法通常将个体视为原子解决方案，依赖数值响应进行适应度评估，只提供了模型整体状况的概述，所以，对于评估嵌入式方法的适应度，传统的进化算法显得力不从心，这一观点在许多研究中已经得到了证实 [2, 11]。最近，一些嵌入式方法采用基于梯度下降的 AutoML 算法来搜索神经架构以预估点击率 [12, 13]。然而，这些方法通常依赖于一个难以满足的假设（期望搜索空间是连续、可微的凸函数）来将模块的离散选择放宽为所有模块上的连续softmax 选择 [14]。通常，它们的模块是复杂的架构级别的算法，例如多层感知机（MLP）或FM，因此，通常需要大规模的种群和大量的迭代来解决巨大的搜索空间难题 [13]。综上所述，如何设计一种元启发式进化算法，能够超越在模型的表面层次评估模型，进而深入诊断模型内部组件的学习能力，是设计自适应交叉特征选择算法的关键。

图6 研究现状总结

2
研究动机在认知科学理论的指导下，我们认识到，包括意识、知觉、记忆、学习和分析能力等在内的认知功能，是适应环境的强有力的决定因素 [15]。这些认知能力使生物体能够感知、记忆并妥当地对环境变化作出反应。从认知神经科学的视角看，这种发展认知功能的能力被定义为延展性，它赋予生物体对环境的适应性 [16, 17]。如图7所示，人类在婴儿阶段，大脑的延展性最强，因此能有效地适应环境中的各种任务，如学习一种全新的语言。这种内在的延展性对发展各种心理活动极为关键，同时也被视为一种衡量智力的标准 [17, 18]。

图7 认知能力最新的认知人工智能（Cognitive AI）研究强调对生物体认知能力的定量分析和模拟 [19]。我们的研究团队一直致力于探索和理解人的认知能力，并且已经开展了一系列关于认知诊断的研究 [20, 21, 22]。本研究深受这些认知诊断原理的启发。在本文介绍的工作中，希望整合这些认知能力的理念，尤其是神经延展性或基因延展性（见图8），以发展出具有环境适应性的模型。因此，本文迈出了依据表面层次的“表象”评估模型，选择在更深层次的基因水平精细地诊断模型。

图8 认知人工智能受自然生物体进化和性状显现机制的启发，本文提出了一种认知进化搜索（Cognitive Evolutionary Search）算法框架，缩写为CELS。在交叉特征选择的任务中，CELS 强调搜索细粒度的底层操作，而不是粗粒度的上层架构。如图9所示，CELS 将交叉特征视为基因组，将模型视为生物体，将任务视为自然环境。CELS 将交叉特征选择过程视为一个进化搜索过程，它模拟了生物体为了提高适应度而努力进化出更好的特征。可以理解为，不同的特征为模型提供了不同的生存率和适应度，模型进化过程反映了特征及交叉特征的选择过程。

图9 认知进化搜索（CELS）为了体现基因延展性如何促进发展环境适应性，本文对模型适应度的进行了深度诊断，以模拟生物体的自然选择和生存率。如图10所示。

图10 适应度诊断这种适应度诊断（Fitness Diagnosis）技术与传统的适应度评估（Fitness Evaluation）技术形成了鲜明的对比，后者主要通过数值评估来衡量模型的适应度。新的适应度诊断方法使我们能够更深入地探究模型，明确其内部组件的功能。如图11所示。

图11 适应度评估 v.s. 适应度诊断

3
算法框架在CELS框架中，特征被视为核苷酸，操作被视为配对相连的碱基。为了发现每个特征对产生任务友好交叉特征的最适操作，搜索空间被扩大并引入了各种类型的操作，这反映了核苷酸配对原则的实施方式。简洁地，选出了四种代表性的操作作为候选操作，如图12所示，以此展示CELS的工作原理。如图所示，可以选择以下操作：按位求和（⊕）：此操作接受两个输入向量，并输出包含它们逐位求和的向量。按位乘积（⊗）：此操作接受两个输入向量，并输出包含它们逐位乘积的向量。连接与前馈层（⊠）：此操作接受两个输入向量，将它们连接起来，并通过带ReLU激活函数的前馈层传递，以降低输出向量的维度。按位乘积与前馈层（⊞）：此操作接受两个输入向量，并将它们的逐位乘积通过带ReLU激活函数的前馈层传递，以生成输出向量。

图12 操作集（编码）作为对比，本文提出了认知进化搜索的一般过程，如图13所示，该过程包括四个主要步骤：1）编码，2）初始化，3）模型适应度诊断，以及4）模型生成。在编码步骤完成后，通过随机为特征对分配操作来生成初始模型。CELS 迭代地诊断当前模型（也就是父代模型）中的特征及其交叉特征的相关性，并将不相关的交叉特征的操作变异为其他操作，以此创建新的模型（也就是子代模型）。如此，父代模型被下一代经过变异产生的子模型所替代。接下来的部分将重点阐述模型适应度诊断和个体变异的具体实现策略。

图13 认知进化搜索的一般过程对于生物体来说，如果其基因组区域能解码出有助于生存的表型，那么它就会具有较高的适应性；反之，如果基因组区域解码出的表型对生存无益，那么它的适应性就会相对较差。进化策略应当有助于保留有益的遗传信息，这促使通过相关性参数来衡量特征及其交叉特征的相关性。让