改进蒙特卡洛树搜索,让符号回归更高效准确。
Improving Monte Carlo Tree Search for Symbolic Regression
- 用极端奖励分配策略优化搜索方向,保证有限步内收敛。
- 引入突变和交叉操作,实现跨区域跳转,提升搜索效率。
- 在真实与黑箱数据上表现优异,适合追求高可解释性的研究者。
符号回归旨在发现简洁且可解释的数学表达式以满足特定目标(如拟合数据),是一个高度组合化的优化问题。尽管遗传编程是主流方法,近期研究尝试用强化学习提升搜索效率。蒙特卡洛树搜索(MCTS)凭借其探索与利用的平衡能力,成为符号表达式发现的有前景技术。然而,传统基于赌博机的策略与逐符号构造方式常限制性能。本文提出一种改进的MCTS框架:(1)设计针对全局最优表达式识别的极端赌博机分配策略,在多项式奖励衰减假设下具备有限时间性能保证;(2)引入进化启发的状态跳转动作(如突变、交叉),实现搜索空间中非局部转移,重塑奖励景观,增强鲁棒性与效率。我们在多种数据集(包括真实与黑箱数据)上进行系统实验,结果表明该方法在恢复率上达到先进水平,并在准确率与模型复杂度的帕累托前沿占据有利位置。代码已开源:https://github.com/PKU-CMEGroup/MCTS-4-SR。
原文摘要 · Abstract (English)
Symbolic regression aims to discover concise, interpretable mathematical expressions that satisfy desired objectives, such as fitting data, posing a highly combinatorial optimization problem. While genetic programming has been the dominant approach, recent efforts have explored reinforcement learning methods for improving search efficiency. Monte Carlo Tree Search (MCTS), with its ability to balance exploration and exploitation through guided search, has emerged as a promising technique for symbolic expression discovery. However, its traditional bandit strategies and sequential symbol construction often limit performance. In this work, we propose an improved MCTS framework for symbolic regression that addresses these limitations through two key innovations: (1) an extreme bandit allocation strategy tailored for identifying globally optimal expressions, with finite-time performance guarantees under polynomial reward decay assumptions; and (2) evolution-inspired state-jumping actions such as mutation and crossover, which enable non-local transitions to promising regions of the search space. These state-jumping actions also reshape the reward landscape during the search process, improving both robustness and efficiency. We conduct a thorough numerical study to the impact of these improvements and benchmark our approach against existing symbolic regression methods on a variety of datasets, including both ground-truth and black-box datasets. Our approach achieves competitive performance with state-of-the-art libraries in terms of recovery rate, attains favorable positions on the Pareto frontier of accuracy versus model complexity. Code is available at https://github.com/PKU-CMEGroup/MCTS-4-SR.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。