用等式图加速符号回归，减少60%冗余计算
Equality Graph Assisted Symbolic Regression
- 用等式图合并等价表达式，避免重复计算
- 实验显示效率提升，准确率在多数据集稳定
- 仅需少量超参数，适合追求效率的研究者
在符号回归（SR）中，遗传编程（GP）是主流搜索算法，其性能依赖于中性现象带来的大片平坦区域，使搜索能安全穿越至更优区域。然而，穿越这些区域需计算大量冗余表达式，据近期研究，冗余计算占比高达总评估数的60%。等式图（e-graph）结构可紧凑存储并分组等价表达式，从而判断新表达式是否已被访问，避免重复计算。本文提出新算法SymRegg，基于e-graph结构：从图中采样表达式进行扰动，若生成未访问的新表达式，则将其加入e-graph并生成其等价形式。结果表明，SymRegg显著提升搜索效率，在多个数据集上保持一致高准确率，且仅需极简超参数配置。
原文摘要 · Abstract (English)
In Symbolic Regression (SR), Genetic Programming (GP) is a popular search algorithm that delivers state-of-the-art results in term of accuracy. Its success relies on the concept of neutrality, which induces large plateaus that the search can safely navigate to more promising regions. Navigating these plateaus, while necessary, requires the computation of redundant expressions, up to 60% of the total number of evaluation, as noted in a recent study. The equality graph (e-graph) structure can compactly store and group equivalent expressions enabling us to verify if a given expression and their variations were already visited by the search, thus enabling us to avoid unnecessary computation. We propose a new search algorithm for symbolic regression called SymRegg that revolves around the e-graph structure following simple steps: perturb solutions sampled from a selection of expressions stored in the e-graph, if it generates an unvisited expression, insert it into the e-graph and generates its equivalent forms. We show that SymRegg is capable of improving the efficiency of the search, maintaining consistently accurate results across different datasets while requiring a choice of a minimalist set of hyperparameters.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。