Research map / Learning theory and algorithms / Combinatorial and search optimization
Dimension Reduction for Symbolic Regression
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes an iterative dimension-reduction beam search for symbolic regression that finds valid input and out-input substitutions via expression-DAG enumeration and a functional dependence test (Codec), boosting recovery of several SR algorithms.
Problem
Symbolic regression recovery of formulas becomes much harder as the number of variables and operators grows; finding valid variable substitutions that reduce the number of variables is hard without knowing the formula.
Approach
Generalizes AIFeynman-style hand-designed substitution predicates by enumerating small expression DAGs as candidate input substitutions and out-input substitutions, testing validity with a multivariate functional dependence measure (Codec, a conditional Chatterjee-type coefficient), and iterating via beam search before passing reduced problems to any SR algorithm.
Key results
- On the Feynman dataset, beam search raised recovery of UDFS from 0.58 to 0.69 and of DSR from 0.37 to 0.66, and Poly from 0.06 to 0.34.
- The number of input variables is reduced by about 50% on Feynman and about 35% on Wikipedia formulas (noise-free, beam size 1, Codec).
- Adding out-input substitutions raised the average reduction rate on Wikipedia from 0.19 (input only) to 0.34, versus 0.08 for AIFeynman substitutions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add beam-search dimension reduction | UDFS · Feynman | recovery rate: 0.58 -> 0.69 | Helped |
| Add beam-search dimension reduction | DSR · Feynman | recovery rate: 0.37 -> 0.66 | Helped |
| Add beam-search dimension reduction | Transf · Feynman | recovery rate: 0.01 -> 0.11 | Helped |
| Add beam-search dimension reduction | PySR · Feynman | recovery rate: 0.51 -> 0.62 | Helped |
| Add beam-search dimension reduction | Operon · Feynman | recovery rate: 0.41 -> 0.52 | Helped |
| Add beam-search dimension reduction | Poly · Feynman | recovery rate: 0.06 -> 0.34 | Helped |
| Add beam-search dimension reduction | UDFS, DSR, Transf, PySR, Operon, and Poly · Wikipedia | recovery rate: UDFS 0.56 -> 0.7; DSR 0.4 -> 0.61; Transf 0.09 -> 0.24; PySR 0.45 -> 0.54; Operon 0.35 -> 0.46; Poly 0.15 -> 0.35 | Helped |
| Increase beam size from 1 to 5 (ablation) | Dimension reduction beam search · Feynman | reduction rate: 0.489 -> 0.491 | No clear effect |
| Increase beam size from 1 to 5 (ablation) | Dimension reduction beam search · Wikipedia | reduction rate: 0.346 -> 0.358 | Helped |
| Add out-input substitutions to input substitutions (ablation) | Dimension reduction beam search · Feynman | reduction rate: 0.39 -> 0.49 | Helped |
| Add out-input substitutions to input substitutions (ablation) | Dimension reduction beam search · Wikipedia | reduction rate: 0.19 -> 0.34 | Helped |
Surprising findings
- The volume-based heuristic baseline breaks down under noise, while Codec and KMAC keep substantial reduction rates.
- Increasing beam size beyond 1 improves the reduction rate only marginally, so beam size 1 was used.
Limitations
- Search space is small (DAGs with one intermediary and one output node), so only limited substitutions are covered.
- Validity is tested via functional dependence scores that give no definite answer, requiring beam search and thresholds.
- Complexity of recovered expressions slightly increases for most regressors with the beam search.
Experimental setup
Datasets: Wikipedia eponymous equations (880 formulas, sampled to 1000 points each) Feynman symbolic regression dataset (95/114 formulas, AI Feynman)
Benchmarks: Feynman symbolic regression dataset Wikipedia eponymous equations dataset
Metrics: recovery rate NRMSE model complexity (expression tree nodes) Jaccard index reduction rate running time
Baselines: UDFS DSR Transformer (Transf) PySR Operon Polynomial regression AIFeynman substitutions Volume heuristic KMAC
Builds on: AIFeynman UDFS Chatterjee coefficient Codec
Closest papers by meaning
- Deep Generative Symbolic Regression (ICLR 2023 · similarity 0.87)
- A Unified Framework for Deep Symbolic Regression (NeurIPS 2022 · similarity 0.87)
- SMILE: Bridging Continuous Optimization and Discrete Symbolic Recovery (NeurIPS 2026 · similarity 0.86)
- Ab Initio Nonparametric Variable Selection for Scalable Symbolic Regression with Large $p$ (ICML 2025 · similarity 0.86)
- Symbolic regression via MDLformer-guided search: from minimizing prediction error to minimizing description length (ICLR 2025 · similarity 0.86)
- Pareto-Optimal Fronts for Benchmarking Symbolic Regression Algorithms (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.