符号回归中进化特征构建的自适应保护机制及其在信用分类中的应用

# 符号回归中进化特征构造的自适应保护机制及其在信用分类中的应用

来源：https://arxiv.org/html/2608.14209

Hengzhe Zhang  
所属机构：新西兰惠灵顿维多利亚大学数据科学与人工智能中心及工程与计算机科学学院，惠灵顿600信箱，6140  
邮箱：[\{hengzhe\.zhang,qi\.chen,bing\.xue,mengjie\.zhang\}@ecs\.vuw\.ac\.nz](mailto:{hengzhe.zhang,qi.chen,bing.xue,mengjie.zhang}@ecs.vuw.ac.nz)

Qi Chen  
所属机构：新西兰惠灵顿维多利亚大学数据科学与人工智能中心及工程与计算机科学学院，惠灵顿600信箱，6140  
邮箱：[\{hengzhe\.zhang,qi\.chen,bing\.xue,mengjie\.zhang\}@ecs\.vuw\.ac\.nz](mailto:{hengzhe.zhang,qi.chen,bing.xue,mengjie.zhang}@ecs.vuw.ac.nz)

Bing Xue  
所属机构：新西兰惠灵顿维多利亚大学数据科学与人工智能中心及工程与计算机科学学院，惠灵顿600信箱，6140  
邮箱：[\{hengzhe\.zhang,qi\.chen,bing\.xue,mengjie\.zhang\}@ecs\.vuw\.ac\.nz](mailto:{hengzhe.zhang,qi.chen,bing.xue,mengjie.zhang}@ecs.vuw.ac.nz)

Lean Yu  
Wolfgang Banzhaf  
所属机构：美国密歇根州立大学计算机科学与工程系，东兰辛，密歇根州48824  
邮箱：[banzhafw@msu\.edu](mailto:[email protected])

Mengjie Zhang  
所属机构：新西兰惠灵顿维多利亚大学数据科学与人工智能中心及工程与计算机科学学院，惠灵顿600信箱，6140  
邮箱：[\{hengzhe\.zhang,qi\.chen,bing\.xue,mengjie\.zhang\}@ecs\.vuw\.ac\.nz](mailto:{hengzhe.zhang,qi.chen,bing.xue,mengjie.zhang}@ecs.vuw.ac.nz)

###### 摘要

进化特征构造在符号回归中展现出巨大潜力，它能自动发现输入特征的有益变换，以增强简单基础学习器的性能。然而，现有方法通常缺乏明确的机制来保留进化过程中发现的重要构建特征，且当遗传算子破坏了有效的特征时，有价值的遗传物质可能会丢失。本文提出了一种自适应保护机制，该机制利用特征重要性度量，在进化过程中选择性地保留构建特征。该机制为更重要的构建特征提供更强的保护，同时仍允许修改不那么重要的特征，并使其能够从更重要的特征中吸收有用的构建模块。我们使用多种特征重要性计算方法对该方法进行了评估，并证明了其在不同基础学习器上的稳健性。在98个回归基准数据集上的实验结果表明，所提出的机制在基线方法的基础上持续提升了求解质量；在两个信用分类数据集上的实验则表明，该方法也能有效地扩展到符号回归之外，提升搜索效率。

###### 关键词：

符号回归 信用分类 进化计算 特征构造 特征重要性 遗传编程

## 1 引言

符号回归旨在发现最能描述数据关系的数学表达式，而无需假设预定义的函数形式\[7\]。形式化地，给定数据集 \(\mathcal{D} = \{(\mathbf{x}_{i}, y_{i})\}_{i=1}^{n}\)，其中 \(\mathbf{x}_{i} \in \mathbb{R}^{d}\) 是输入特征，\(y_{i} \in \mathbb{R}\) 是目标值，符号回归旨在寻找一个函数 \(f: \mathbb{R}^{d} \rightarrow \mathbb{R}\)，最小化损失函数：
\[f^{*} = \arg\min_{f \in \mathcal{F}} \sum_{i=1}^{n} L(y_{i}, f(\mathbf{x}_{i}))\]
其中 \(\mathcal{F}\) 是所有可能数学表达式构成的空间，\(L\) 是损失函数，如均方误差。

在符号回归方法中，基于特征构造的符号回归是一种流行的方法，它生成信息丰富的特征变换 \(\phi_{j}: \mathbb{R}^{d} \rightarrow \mathbb{R}\)，然后用于构建预测模型 \(f(\phi_{1}(\mathbf{x}), ..., \phi_{k}(\mathbf{x}))\) \[26\]。基于进化特征构造的符号回归是一个特别有前景的变体，其中遗传编程 (GP) 自动演化这些变换 \[16, 36\]，创建了一个丰富的潜在变换空间，可以通过线性模型或决策树进行组合，如图1所示。

图1：一个通用的保护框架，包装在任意遗传算子之外，类似于不受限于任何特定遗传算子的深度限制保护。
与许多其他进化方法一样，进化特征构造的一个基本挑战在于平衡有用构建模块的保留与新特征组合的生成。突变和交叉等遗传算子可以产生有希望的新构建特征，但也可能无意中破坏了有价值的现有特征\[4\]。这是一个问题，因为修改或移除一个重要特征可能会用一个效果较差的替代品取代高度有用的构建模块，即使子代引入了其他有用特征，也可能导致求解质量下降。

为解决这一挑战，特征重要性度量提供了一种自然的机制来识别哪些构建特征对模型性能贡献最大\[18, 12\]。传统方法使用模型系数\[38\]和边际贡献\[5\]，而最近的进展引入了更复杂的方法，如Shapley值\[18\]。这些度量从不同角度评估特征贡献，并可以在进化过程中指导有价值遗传物质的保留。尽管已经开发了特征感知遗传算子\[34, 37\]，但目前还没有一种简单的机制能普遍适用于任意遗传算子。

本文引入了一种自适应保护机制，利用特征重要性来指导保留良好的构建模块\(^\text{1}\)。如图1所示，该机制可以嵌入一个通用的保护框架中，与任何遗传算子兼容。其关键思想是，构建特征应获得与其重要性成比例的保护，从而使非常有用的特征得到更可靠的保留，而重要性较低的特征则仍然可以被遗传算子自由修改或替换。通过这种方式，特征保护保留了强大的构建模块，而交叉和突变则继续生成新的特征组合并替换价值较低的特征。

本文工作的具体目标有三个：
- 我们引入了一种自适应保护机制，使用重要性加权分数来保护构建特征并指导修复，为更重要的构建特征提供更强的保护，同时仍允许修改或替换较不重要的特征。
- 我们在不同模型类型上比较了多种特征重要性计算方法，以证明我们方法的通用性。
- 我们在符号回归基准测试上进行了实证评估，并将其应用于信用分类，证明了该方法在不同重要性度量和基础学习器上的有效性。

\(^\text{1}\) https://github.com/hengzhe-zhang/EvolutionaryForest/blob/master/evolutionary_forest/component/crossover/adaptive_feature_importance.py

## 2 相关工作

### 2.1 进化特征构造

进化计算中的特征构造分为三种范式：封装法、过滤法和嵌入法。封装法\[15\]在构建的特征上训练模型，并使用其性能作为适应度。它们包括多维多类遗传编程 (M3GP) \[22\]、交互变换进化算法 (ITEA) \[8\]、多元回归遗传编程 (MRGP) \[2\]和遗传编程基因池最优混合进化算法 (GP-GOMEA) \[28\]。过滤法\[23, 27\]使用独立于学习器的统计或信息论标准。嵌入法\[30\]将构造过程集成到学习过程中。本工作专注于基于封装的方法，这些方法在符号回归和分类中已显示出强大的性能。

### 2.2 构建模块分析

构建模块——可复用的高质量子结构——的概念在GP中已被研究已久。经典工作关注结构构建模块及其在膨胀控制中的作用\[13\]，而语义构建模块则通过其输入-输出行为来表征有用的程序片段\[20\]。相关工作还探索了基于学习到的构建模块的基因池最优混合\[29\]，以及构建模块在模拟电路综合\[19\]、大规模布尔问题\[11\]和图像分类\[6\]中的复用。更直接相关的是，重要性分析已经在树级\[35\]、子树级\[34, 24\]和变量级\[31\]指导了遗传算子。这些方法依赖于频率分析\[29\]、相关性分析\[34\]和Shapley值\[31\]等度量，但交叉和突变通常必须重新设计以利用所识别的组件。因此，理想的情况是使用一种与算子无关的机制来保护有用的部分，该机制应与传统算子、语义算子\[9\]和基于大语言模型 (LLM) 的交叉\[1\]兼容。

## 3 算法

### 3.1 总体工作流程

(a) 工作流程。 (b) 评估过程。
图2：(a) 从种群初始化到精英保留的总体工作流程。(b) 进化特征构造过程的评估。
进化特征构造过程遵循代际进化算法框架\[4\]。设 \(\Phi = \{\Phi_{1}, \Phi_{2}, \ldots, \Phi_{N}\}\) 表示包含 \(N\) 个个体的种群，其中每个个体 \(\Phi_{i}\) 是一组特征变换树 \(\{\phi_{1}^{(i)}, \phi_{2}^{(i)}, \ldots, \phi_{k}^{(i)}\}\)。每棵树 \(\phi_{j}^{(i)}\) 使用GP的基本元素构建，包括数学算子以及代表输入变量或常数的终端节点。图2(a) 展示了进化特征构造过程的总体工作流程。该工作流程包括七个主要阶段：

- • **种群初始化**：创建一个包含 \(N\) 个个体的初始种群 \(\Phi^{(0)}\)，其中每个个体 \(\Phi_{i}^{(0)}\) 包含多棵树 \(\{\phi_{1}^{(i)}, \ldots, \phi_{k}^{(i)}\}\)，每棵树 \(\phi_{j}^{(i)}\) 使用GP基本元素通过随机的坡半坡初始化方法\[4\]生成。
- • **解评估**：对于当前种群中的每个个体 \(\Phi_{i}\)，使用其树 \(\{\phi_{1}^{(i)}, \phi_{2}^{(i)}, \ldots, \phi_{k}^{(i)}\}\) 构造的特征训练一个机器学习模型。适应度 \(f(\Phi_{i})\) 是一个衡量预测性能的标量：回归任务使用决定系数 (\(R^{2}\))，分类任务使用ROC曲线下面积 (\(AUC\))。损失向量对每个训练样本有一个分量，用于父代选择的epsilon字典选择法：回归任务使用每个样本的平方误差，分类任务使用每个样本的交叉熵。对于回归任务，我们考虑岭回归和随机决策树。对于分类任务，我们使用逻辑回归：
  - – **岭回归\[16\]**：该方法使用岭回归，并采用高效的留一法评估进行模型训练和适应度计算。
  - – **随机决策树\[39\]**：该方法使用具有随机分割器的决策树，随机选择候选分割点而非最优分割点。选择随机决策树是因为它们在进化特征构造中已被证明优于标准决策树\[39\]。使用五折交叉验证误差作为适应度。
  - – **逻辑回归**：基础学习器是正则化逻辑回归，将构建的特征向量映射到类概率：\(\mathbb{P}(y=1 \mid \mathbf{x}; \boldsymbol{\beta}) = \sigma\bigl(\beta_{0} + \boldsymbol{\beta}^{\top}\boldsymbol{\phi}(\mathbf{x})\bigr) = \sigma\biggl(\beta_{0} + \sum_{j=1}^{k}\beta_{j}\,\phi_{j}^{(i)}(\mathbf{x})\biggr)\)，(1) 其中 \(\sigma(z) = 1/(1+e^{-z})\) 是逻辑函数，\(\boldsymbol{\beta} = (\beta_{1}, \ldots, \beta_{k})^{\top}\) 是构建特征的系数。同样，使用五折交叉验证分数作为适应度。
- • **重要性计算**：评估后，使用所选基础学习器的重要性方法（详见3.2节）计算每棵树 \(\phi_{j}^{(i)}\) 的特征重要性 \(I_{j}^{(i)}\)。对于岭回归，我们使用三种选项之一：内置系数、SHAP值或边际贡献。对于随机决策树，我们使用五次交叉验证折叠平均后的不纯度减少重要性。对于信用分类中的逻辑回归，我们使用系数的绝对值 \(|\beta_{j}|\)。这些重要性值随每个个体存储，并构成保护机制的基础。
- • **父代选择**：使用epsilon字典选择法从当前种群 \(\Phi\) 中选择父代个体 \(\Phi_{p}\) 和 \(\Phi_{q}\)。