A Comparative Study of Model Selection Criteria for Symbolic Regression

技术摘要：符号回归模型选择准则的比较研究

问题陈述
符号回归（SR）通常通过遗传编程（GP）求解，旨在发现平衡准确性与复杂性的数学表达式。尽管现代 GP 实现能够生成候选解的帕累托前沿，但自动选择一个能良好泛化至未见数据的单一模型仍是一个未解决的挑战。现有文献提供了多种信息论和贝叶斯方法，但缺乏在不同数据机制下对其性能进行全面实证比较的研究。目前缺乏关于在特定条件下应优先选择何种选择准则以避免过拟合同时保持可解释性的实用指导。

方法论
作者对六种广泛使用的模型选择准则进行了系统的实证比较：

1. 赤池信息量准则（AIC）
2. 校正 AIC（AICc）
3. 贝叶斯信息量准则（BIC）
4. 最小描述长度（MDL）
5. 基于 Efron 自助法的样本内误差估计（$Err_{in}$）
6. 训练均方误差（$MSE_{train}$），用作基线。

实验设置：

• 数据集： 使用了七个合成基准函数（在 GP 文献中常见）。训练数据由 100 个添加高斯噪声（$\epsilon \sim N(0, (0.1\sigma(y))^2)$）的点组成，而测试数据由 10,000 个无噪声点组成。
• 候选生成： 为了将评估与特定的 SR 算法解耦，通过扰动真实函数生成了一个受控的候选表达式池。变异过程将真实树中的随机节点替换为随机子树。这些候选表达式使用 BFGS 优化拟合训练数据（重复 100 次以避免局部最优）。该过程为每个基准生成了 100 个过拟合模型（即训练均方误差低于真实值的模型），以测试各准则从一组过拟合替代方案中检索真实模型的能力。
• 评估指标：
  • 平均 $MSE_{test}$： 排名前 $k$ 的模型的性能。
  • 前 $k$ 精度： 基于测试误差，属于真实前 $k$ 名的被选模型所占的比例。
  • 平均表达式规模： 所选模型的平均结构复杂度（节点计数）。
  • 真实命中： 精确恢复真实表达式时的最小排名 $k$。

主要贡献与结果
本研究基于上述四项指标对选择准则进行了详细排名：

• MDL（最小描述长度）： 始终表现为最稳健的准则。在七个基准中的六个中，它针对较小的 $k$ 识别出了测试误差最低的模型，并产生了最简约（最小）的表达式。MDL 和 BIC 在恢复真实表达式方面表现出最高的效率，其平均首次命中排名分别为 5.14 和 6.00。
• BIC： 在真实表达式恢复方面表现与 MDL 相似，并在各基准中提供了稳定、居中的结果，通常能生成简洁的公式。
• AIC 和 AICc： 在泛化能力方面，排名通常低于 MDL 和 BIC。虽然 AICc 在特定函数（$f_1, f_2$）上显示出比标准 AIC 略微的改进，但两者往往比 MDL 选择更复杂的模型。
• $Err_{in}$（自助法样本内误差）： 结果好坏参半。虽然它在某些数据集（$f_1, f_2, f_3, f_6, f_7$）上实现了良好的精度和泛化能力，但在其他数据集（$f_4, f_5$）上表现不佳，通常选择更大的表达式且未能高效恢复真实表达式（平均排名为 31.71）。作者将这种不一致性归因于其对随机森林噪声方差估计的依赖。
• $MSE_{train}$： 表现始终最差，证实了未正则化的训练误差会导致严重的过拟合和较差的泛化能力。

计算复杂度
本文分析了这些准则的计算开销：

• AIC、AICc、BIC： 效率最高（$O(n)$），仅需在参数估计后对数据进行单次遍历。
• MDL： 由于需要计算费雪信息矩阵，成本略高（$O(n \cdot p)$），但对于典型的 SR 表达式规模而言仍然高效。
• $Err_{in}$： 计算量显著最大，需要 $B$ 次自助法迭代（通常为 200 次）和重复的参数重新拟合，使其在迭代式进化搜索过程中可能不切实际。

意义与主张
作者声称，他们的发现为 SR 流程提供了实用指导。他们得出结论，MDL 是稳健的早期选择和紧凑模型的强默认选择，BIC 可作为次要选项。他们建议，仅当可以接受稍大的模型且认为 MDL 的惩罚过于保守时，AIC/AICc 才可能是更好的选择。相反，由于其高昂的计算成本以及在实验中的不一致表现，他们不推荐$Err_{in}$。

该研究明确指出了局限性，包括使用单一噪声水平生成数据，以及这些准则是在候选者的事后池中进行评估，而非直接集成到 GP 搜索循环中。作者指出，未来的工作应研究变化的噪声强度，并将这些准则集成到进化搜索过程中。