揭示符号回归的泛化能力受深度与算子平滑性控制，为科学发现提供理论支撑。
Sample Complexity of Scientific Discovery: PAC Learnability of Compositional Function Trees
- 基于PAC学习框架，分析组合函数树的泛化性能，关键受深度和算子光滑性影响。
- 证明复杂度上界为 $L^d/\ oot\of{n}$，当算子数量、分支数有界时，样本需求可控制。
- 提出可微算子树实现，实验证明泛化误差与理论预测一致，适合物理建模研究者。
通过PAC学习视角重审符号回归在科学发现中的统计可行性，聚焦由有限平滑算子（如 {+ ,×, sin, exp} 和仿射映射）构成的组合函数树。研究表明，相关泛化量——Rademacher复杂度，并非随符号结构数量指数增长，而是受深度 $d$ 与基础算子的Lipschitz常数控制。在算子满足弱Lipschitz条件且仿射叶节点有界前提下，利用大小为 $K=|\mathcal{H}_{\mathrm{base}}|$ 的词汇表与向量收缩不等式，得到 $\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{d}) \leq (Kb\sqrt{2}L)^{d-1}\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{1})$，其中 $b$ 为分支数。对应高概率风险界为 $\mathcal{O}(L^d/\sqrt{n})$，当 $K,b=O(1)$ 且 $\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{1})=O(n^{-1/2})$。进一步构建模块化代码库，在可控深度的“类物理”合成目标上训练可微算子树，实证显示泛化差距与预测复杂度项 $(\widehat{L}^d)/\sqrt{n}$ 呈正相关。
原文摘要 · Abstract (English)
Scientific discovery via symbolic regression is often viewed as statistically and computationally intractable because the hypothesis space of expressions grows combinatorially with depth. This paper revisits the statistical side through the lens of PAC learning, focusing on compositional function trees built from a finite vocabulary of smooth operators (e.g., $\{+,\times,\sin,\exp\}$ and affine maps). We prove that the relevant generalization quantity, Rademacher complexity, hence the excess risk, does not necessarily blow up exponentially with the number of distinct symbolic structures, but is controlled by (i) the depth $d$ and (ii) the Lipschitz constants of the base operators along the composed computation graph. Concretely, under mild Lipschitz conditions on operators and bounded affine leaves, a finite-union bound over a vocabulary of size $K=|\mathcal{H}_{\mathrm{base}}|$ together with Maurer-type vector contraction yields $\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{d}) \leq (Kb\sqrt{2}L)^{d-1}\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{1})$ with arity bound $b$; corresponding high-probability risk bounds scale as $\mathcal{O}(L^{d}/\sqrt{n})$ when $K,b=O(1)$ and $\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{1})=O(n^{-1/2})$. We complement the theory with a modular codebase that trains differentiable operator trees (not MLPs) on synthetic "physics-like" targets of controlled depth and shows that the empirical generalization gap correlates positively with the predicted complexity term $(\widehat{L}^{d})/\sqrt{n}$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。