| 标题 | Exhaustive Symbolic Regression |
|---|---|
| 机构 | University of Oxford |
| 代码 | https://github.com/DeaglanBartlett/ESR |
| 论文 | https://arxiv.org/pdf/2211.11461 |
摘要
符号回归（SR）算法试图学习能够准确拟合数据并以高度可解释的方式表达的解析表达式。传统的SR存在两个基本问题。首先，这些方法（通常使用遗传编程）是随机搜索空间的，因此不一定能找到最佳函数。其次，用于选择最佳方程的准则，即在准确性和简单性之间取得最佳平衡的标准，一直是变化的和主观的。为了解决这些问题，我们引入了穷尽式符号回归（ESR），它系统且高效地考虑所有可能的方程——由给定的一组操作符构成，并且复杂度不超过指定的最大值——因此保证能找到真正的最优解（如果参数被完美优化），以及在这些约束下的完整函数排名。我们实现了最小描述长度原则，作为一种将这些偏好合并为单一目标的严格方法。为了展示ESR的强大能力，我们将其应用于宇宙计时器目录和Pantheon+超新星样本，以学习哈勃率作为红移函数的表达式，发现约有40个函数（在520万个试验函数中）比弗里德曼方程更经济地拟合数据。因此，这些低红移数据并不唯一地偏好标准宇宙学模型的膨胀历史。我们公开提供我们的代码和完整的方程集。
方法
A. 树表示
本文考虑了三种不同类型的运算符。1）二元运算符（例如，+，×， pow）；2）一元运算符（例如，exp，log，square）；3）零元运算符（参数或者变量）。当一个人看到树中的二元运算符时，例如，人们知道该节点要么是树的“根”，要么是有一个“父”节点，并且它有两个“子”节点（函数的参数）。因此，如果一棵树具有遍历树的规则，则可以从运算符列表中唯一地重建树，其中列表的长度等于函数的复杂性。
对于一个列表，列表中的第一个运算符是“根”节点，放在树的顶部。如果这个运算符是二元的，我们绘制连接到根的两个节点，列表中的第二个运算符被放置在左侧节点上。如果运算符是一元的，我们只绘制一个连接到根的节点，因为第二个运算符标记该节点。我们尽可能地以深度优先的方式继续遍历树，直到我们到达空运算符。然后我们回树以找到下一个节点，该节点在其右侧有一个未标记的子节点，并将下一个运算符放在列表中在那里。图1给出了一个例子。
注意到我们在 ESR 算法中使用的这种表示的两个重要属性。首先，列表和树之间的映射是双射的，因此我们在整个过程中选择列表表示。因此，我们的任务是找到产生有效函数的给定长度的所有可能的列表。其次，给定的函数可能有多个树表示，因此该符号存在冗余。为了提高效率，将函数的参数拟合到数据中，ESR 算法应该能够识别这些重复项。
B. 有效树生成
方程的数量随着复杂度（树中结点的数量）呈指数增长，对于 个基函数和 个结点，有个列表。然而，并不是所有的列表都能生成有效树。例如，列表和都不能生成有效树。因此，没必要检查所有的个列表，很多列表是无效的。
我们的第一个任务是识别所有可能的树结构（不考虑节点标签），以及如何将这些表示为列表。我们生成所有可能的长度为 k 列表，由“0”、“1”和“2”的组合组成，其中 0、1 和 2 分别是零、一元和二元运算符的占位符。然后，我们尝试使用上节中概述的遍历方法将这些列表转换为树，只保留那些产生有效树的列表。例如，对于k = 4，在0、1和2的组合中，只有4个有效的图结构:[1,1,0],[1,2,0,0],[2,0,1,0]和[2,1,0,0]。一旦我们有所有有效的树结构，所有有效函数的生成是微不足道的:人们简单地考虑所有可能的方法，从基函数列表中用正确的操作符类型装饰节点。
C. 重复检查和简化
既然我们已经得到了给定一组基函数在给定复杂度下的所有可能方程，我们可以就此止步，并将每个方程的参数拟合到数据上。然而，这样做效率不高，因为存在重复的方程，所以识别出唯一的方程并对它们的参数进行优化是有意义的。因此，我们检查以下模式，这些模式会产生重复的方程。
树重新排序，列表和产生相同的方程，突显了树的冗余。 简化，我们还搜索在数学上等价但以不同的方式表达的函数。例如，可以生成多项式的分解版本和扩展版本。 参数排列，方程和对给定的参数和是不同的，我们希望将这些参数拟合到数据中，因此一旦优化，这些将返回相同的表达式。 重新参数化不变性，假设有两个方程 和 。优化时，给 不同值，但是在这两种情况下，函数中的 x 系数将是相同的。 参数组合，如果参数仅出现在方程中作为其他参数的组合（例如，），那么这些函数可以表示为复杂度较低的树（）。
为了执行此重复检查，当前的实现中，使用 了 SYMPY 包将函数的树表示转换为字符串。最初搜索所有唯一的字符串，然后显式地搜索出现在这些方程中的模式，这些模式可以用替代方案代替。
D. 数值参数优化
接下来的步骤是优化这些参数，以最大化给定函数下数据的可能性，为此我们使用BFGS算法。
BFGS优化器的任何单次运行都可能收敛到一个局部似然最大值，或者根本不能收敛。因此，我们用不同的随机起始位置重复优化次，选择最佳结果。为了减少对简单函数优化的运行时间，如果优化器的次迭代给出了一个对数L，且这个值在迄今为止找到的最佳解决方案的0.5范围内，我们就会提前结束。如果任何迭代实现了至少比迄今为止找到的最佳解决方案好2个对数，我们认为这是不同的局部最大值，并将计数重置为0。在θ本身被优化的情况下，我们从[0, 3]的均匀分布中选择随机起始位置。
E. 生成方程
每个复杂度上给定数量的自由参数的方程数如图2所示。
当复杂度等于 1 或 2 时生成的函数非常简单；在复杂度 1 中，只能生成一个常数或函数 ，并且在复杂度 2 时，可以有一个作用于的一元算子或一个常数，后者产生另一个常数。然而，通过复杂性 3，人们已经提供了有用的物理方程。例如，函数表示以球形对称体轨道的概率质量的牛顿引力势，可以表示为 ]。在复杂度 5 时，可以拟合直线 和幂律 。直到和包括复杂度 10，不需要优化超过四个参数。可以直接证明，如果想要一个依赖于输入变量 x 的方程，那么在复杂度 k 时，任何包含空元、一元和二元算子的函数都不能包含超过 参数。
ESR 算法分为两个不同的阶段。首先，计算所有可能的函数并尝试删除重复项，在第二阶段，这些函数适合数据。如果不希望更改基函数，那么当考虑更改数据集或问题时，第一步不需要重新运行。
方程选择
最小描述长度(MDL)提供了一种方法来衡量给定方程的好坏。MDL可以表示如下：
实验
表1和表2分别表明了ESR算法对Cosmic Chronometers和Pantheon+ samples这两个问题的最好拟合结果。
图3绘制了cosmic chronometer和Pantheon+ data的帕累托前沿，比较了似然和描述长度。
讨论
A. ESR的局限性
穷尽式符号回归（ESR）方法虽然能够全面考虑所有可能的函数组合，但它主要适用于较低复杂度的函数，并且在处理高复杂度问题时受限。由于算法需要考虑大量的函数组合，运行时间和内存需求随着基集的增大而增加。此外，ESR在识别重复函数方面存在不足，导致需要优化更多参数。尽管ESR能够找到描述长度最低或接近帕累托前沿的最佳函数，但这需要在每个复杂度级别进行详尽的搜索，效率不如那些使用启发式方法的确定性方法，后者可以在不进行全面搜索的情况下增加找到好函数的概率。因此，尽管ESR在某些方面具有优势，但其在处理大规模问题和优化最佳函数方面的局限性不容忽视。
B. 针对其他算法对ESR进行基准测试
ESR 算法系统地搜索可以从给定基函数集生成的所有可能的方程，并用具有固定节点数的树表示。这与不考虑所有可能方程的传统 SR 方法相比，而是试图通过函数空间随机搜索。由于 SR 的一个关键目标是可解释性，通常不想产生高度复杂的函数，因此对函数空间的详尽搜索是可行的。我们发现宇宙年表和 Pantheon+ 数据集的 L(D) 最小值的复杂度为 5，表明即使是多达 1590 个点的真实数据集也可以根据 MDL 在 ESR 范围内具有最佳的功能表示。不同方法的帕累托前沿如图7所示。
C. 展望
未来人们可能想要考虑更高的复杂度函数。主要的瓶颈是找到重复项的任务，我们使用了 SYMPY 包，一旦超过，它需要大量的内存，此外，SYMPY 在许多情况下无法找到重复项。从这个意义上说，开发一个更简单、自定义的符号操作包，特别关注改进重复查找过程。
以前的确定性 SR 方法在没有完全扫描函数空间的情况下实现了更高的复杂性。ESR 可以提供一种方法，通过在可能更大范围的模型行为的情况下以更高的复杂性初始化它们来提高这些搜索的效率。这将降低未能找到质量与最佳拟合非常简单的函数不同的高质量函数的风险。另一种可能性是使用ESR实现的功能参数空间的完整知识，将概率分配给优先级队列中可能的转换，以将它们扩展到更高的复杂性。这将允许函数扩展和转换应用于从数据中学习，这应该加快发现好的新函数。
另一个潜在的改进是去除重复方程的方法。虽然能够通过考虑树表示的拓扑结构来剔除 97% 的可能函数，但我们发现只有高达 26% 的剩余函数是唯一的。因此，人们可能想知道是否存在更经济的符号，人们可以利用更少的冗余。
总结
SR是一类固有的可解释的机器学习方法，它学习准确描述数据的解析表达式。这个问题的传统方法涉及通过参数空间进行随机搜索，例如遗传编程、强化学习，或通过搜索数据中的对称性，以产生可行的解决方案的帕累托前沿，以平衡简单性和准确性。这种技术通常不知道无法获得最佳解决方案的概率，并且在比较简单性和准确性的目标以获得最佳方程方面几乎没有努力。
在这项工作中，我们介绍了一种 ESR 的新方法——旨在解决这两个问题。首先，受 SR 算法倾向于选择的函数的相对简单性的启发，我们通过在给定复杂度（定义为函数树表示中的节点数量）下明确考虑所有可能的函数来消除未能获得最优解的风险给定算子集。尽管这个问题的复杂性呈指数增长，但通过考虑有效树的拓扑结构并应用简化程序来识别重复函数，但我们发现我们可以将需要将数据拟合到可行数的函数数减少到比 naïve 期望小约1400倍。其次，我们推导出一个统计量 ，它将似然矩阵和 Fisher 矩阵与函数的参数和结构复杂性结合到一个数字中，描述在函数的帮助下必须传达的信息量来指定数据。MDL 断言最小化这个数字的函数提供了对数据的最佳描述。这样，我们将帕累托前沿折叠成一维排序，从而消除双目标SR算法中模型选择相关的歧义(当然，如果需要，ESR 中可以考虑完整的帕累托前沿)。作为我们方法的演示，我们将（正方形）Hubble 参数重建为从宇宙计时计和 Ia 超新星类型的 Pantheon+sample 红移的函数。
