Sample Complexity of Scientific Discovery: PAC Learnability of Compositional Function Trees

技术摘要：科学发现的样本复杂度

问题陈述
通过符号回归（Symbolic Regression, SR）进行的科学发现通常被认为在统计和计算上是难以处理的。主流观点认为，符号表达式的假设空间随深度呈组合爆炸式增长，使得寻找最优表达式成为 NP-hard 问题，且此类模型的统计泛化能力并不可靠。本文挑战了将计算难度与统计可学习性混为一谈的观点。本文指出，尽管寻找最优符号结构在计算上非常困难，但如果底层算子具有稳定性属性，那么组合函数树的统计泛化可能是良好的。核心问题在于：学习组合算子树的样本复杂度是随深度呈指数级爆炸，还是受控于算子的稳定性（Lipschitz 连续性）和树的深度。

方法论
作者通过概率近似正确（PAC）学习理论的角度来研究该问题，具体利用 Rademacher 复杂度来限制泛化误差。

1. 假设空间定义： 研究定义了一个组合假设空间 $H^d_{comp}$，它由深度为 $d$ 的根节点算子树组成。内部节点取自有限的平滑、可微算子词汇表（$H_{base}$），例如 $\{+, \times, \sin, \cos, \exp\}$ 和仿射映射。叶节点是输入坐标或有界的仿射函数。
2. 理论框架：
   • Lipschitz 假设： 分析假设基础算子在相关数据范围内是局部 Lipschitz 连续的，其 Lipschitz 常数为 $L_h$。使用全局 Lipschitz 常数 $L = \max L_h$ 进行界定。
   • Rademacher 复杂度： 作者推导了经验 Rademacher 复杂度 $R_n(H^d_{comp})$ 的界。他们将经典的收缩论证（Ledoux & Talagrand, 1991）和向量收缩不等式（Maurer, 2016）扩展到了树状结构的组合中。
   • 递归界限： 通过对有限算子词汇量（$K = |H_{base}|$）进行并集界（Union Bound），并利用 $b$ 个子节点的组合中的向量收缩（其中 $b$ 为元数/arity），作者建立了深度为 $d$ 与深度为 $d-1$ 之间的复杂度递归关系。
3. 实验验证：
   • 合成数据： 作者构建了一个模块化的 PyTorch 代码库，用于生成具有受控深度（$d \in \{1, 2, 3, 4\}$）和已知真值结构的合成“类物理”目标。
   • 可微树： 他们没有使用遗传编程或离散搜索，而是使用梯度下降（Adam）训练可微算子树（而非 MLP）来拟合算子的系数。
   • 指标： 他们测量了泛化差距（测试 MSE 减去训练 MSE），并将其与理论复杂度项 $(bL^d)/\sqrt{n}$ 进行比较，其中 $\hat{L}$ 是从梯度范数中导出的 Lipschitz 常数的经验估计值。

核心贡献

1. SR 的统计可学习性： 本文证明了组合树的泛化能力并不一定会随着不同符号结构的数量而呈指数级爆炸。相反，它受控于树的深度 $d$ 和算子的 Lipschitz 常数。
2. 显式复杂度界限： 作者推导出了一个具体的 Rademacher 复杂度上界：
   $$R_n(H^d_{comp}) \leq (K \cdot b \sqrt{2} L)^{d-1} R_n(H^1_{comp})$$
   因此，当词汇量大小 $K$ 和元数 $b$ 被视为常数时，超额风险（excess risk）按 $O(L^d / \sqrt{n})$ 缩放。这与依赖于离散语法空间基数的界限形成了对比。
3. 分离搜索与估计： 该工作正式分离了离散优化问题（搜索树结构）与连续回归问题（拟合系数）。所推导的界限适用于后者，明确了在提出一个结构后可以预期的统计缩放情况。
4. 经验相关性： 实验表明，观察到的泛化差距与预测的复杂度项 $(bL^d)/\sqrt{n}$ 之间存在正相关关系。数据表明，虽然差距随深度增加（由于 Lipschitz 常数的累积）而增加，并随样本量（$1/\sqrt{n}$）而减小，但其缩放与理论预测是一致的。

结果

• 理论层面： 定理 4.9 确立了对于有界输出和 Lipschitz 算子，超额风险随 $1/\sqrt{n}$ 衰减，其常数因子通过 Lipschitz 常数的乘积随深度呈指数级依赖。推论 4.11 将其转化为 PAC 样本复杂度界限，表明样本复杂度随 $L^{2d}$ 而非树的组合计数进行缩放。
• 实验层面： 在 400 次改变深度（$d$）和样本量（$n$）的实验运行中，泛化差距被发现追踪了理论项。
  • 对于浅层深度（$d=1, 2$），Lipschitz 代理 $\hat{L}$ 保持稳定，差距主要随 $1/\sqrt{n}$ 缩放。
  • 对于涉及 $\exp$ 等非线性项的深层组合（$d=3, 4$），$\hat{L}$ 增加，导致更大的差距，这与稳定性常数的乘积累积效应一致。
  • 在对数-对数尺度上的幂律拟合得出了 0.48 的相关性，表明组合复杂度项捕捉到了泛化差距中意义显著的一部分方差，尽管其他因素（优化误差、噪声）也发挥了作用。

意义与主张
本文声称为使用符号回归进行科学发现提供了“可学习性证书”。其主要意义在于将视角从符号结构的组合爆炸转向了算子的组合稳定性。

• 小数据发现的可行性： 作者认为，对于稳定的算子词汇表和适中的深度，从小型数据集中进行科学发现从统计学上是可行的。统计泛化并不是瓶颈；真正的挑战仍然在于结构的计算搜索和归纳偏置的设计。
• 澄清缩放规律： 该工作澄清了非线性系数估计的统计缩放是由沿计算图累积的 Lipschitz 常数决定的，而不是由所有可能的树形状的枚举决定的。
• 局限性： 作者谦虚地指出，他们的保证是统一界限（uniform bounds），并未像 PAC-Bayes 方法那样有效地利用结构先验（如奥卡姆剃刀）。此外，实验验证依赖于受控的、分布内（in-distribution）的单维输入合成数据；这些界限并不保证在分布偏移或模型误设下的行为。估计器 $\hat{L}$ 测量的是拟合映射上的稳定性，而非证明最坏情况下的全局常数。

总之，本文断言，当被视为具有稳定原语的组合函数树时，符号回归模型具有良好的统计特性，只要管理好深度和算子稳定性，即使在数据有限的情况下也能实现泛化。