Source-linked AI summary
AI Feynman 2.0: Pareto-optimal symbolic regression exploiting graph modularity
Silviu-Marian Udrescu, Andrew Tan, Jiahai Feng, Orisvaldo Neto, Tailin Wu, Max Tegmark
TL;DR
Symbolic regression must find simple, accurate formulas from data despite a combinatorially large expression space, noise, and outliers. AI Feynman 2.0 recursively exploits graph modularity, Pareto-frontier pruning, hypothesis testing, and normalizing flows, improving robustness and solving harder problems including symbolic density estimation. The paper also reports generalized symmetry discovery from neural-network gradients and a scope that includes author-acknowledged failure modes and broader risks.
Problem
Symbolic regression seeks simple, accurate symbolic expressions from tabulated data, but the expression space is exponentially large and data may contain noise or outliers.
Method
The method recursively discovers computational-graph modularity from neural-network gradients, prunes candidates on a complexity-versus-inaccuracy Pareto frontier, uses hypothesis testing, and applies normalizing flows to sampled distributions.
Results
The method improves state-of-the-art performance by increasing robustness to noise and solving harder problems, including symbolic density estimation, while improving noise robustness by 1-3 orders of magnitude.
Takeaways & Limitations
The publicly released method extends symbolic regression toward more complex formulas, sampled probability distributions, and applications requiring robustness to noise and bad data.
Takeaways & Limitations
The authors report that some mysteries remain failures unless the code runs longer or uses additional basis functions, and identify accelerated progress toward artificial general intelligence as a potential risk.
Abstract
from arXiv · showhide
We present an improved method for symbolic regression that seeks to fit data to formulas that are Pareto-optimal, in the sense of having the best accuracy for a given complexity. It improves on the previous state-of-the-art by typically being orders of magnitude more robust toward noise and bad data, and also by discovering many formulas that stumped previous methods. We develop a method for discovering generalized symmetries (arbitrary modularity in the computational graph of a formula) from gradient properties of a neural network fit. We use normalizing flows to generalize our symbolic regression method to probability distributions from which we only have samples, and employ statistical hypothesis testing to accelerate robust brute-force search.
1 Introduction
The paper presents symbolic regression as the search for simple, accurate expressions, and introduces AI Feynman 2.0 to improve robustness and extend discoverable structure. Its approach combines graph-modularity discovery, Pareto-frontier pruning, hypothesis testing, and normalizing flows.
- Symbolic regression seeks a simple, accurate expression for an unknown function from tabulated inputs and outputs, optionally with noise and outliers.
- AI Feynman 2.0 recursively discovers generalized graph modularity from gradients of a neural-network fit, extending beyond earlier symmetry and separability cases.The method targets arbitrary modularity involving functions of two or more variables.
- Pareto-frontier pruning removes candidates that are not optimal in description-length complexity versus inaccuracy, eliminating arbitrary accuracy thresholds.The authors report improved robustness to noise and bad data from this design.
- Statistical hypothesis testing replaces L∞-norm rejection of formula candidates, improving robustness during brute-force search.
- Normalizing flows extend symbolic regression to probability distributions represented only by samples.
- The method enables discovery of more complex formulas while improving noise robustness by 1-3 orders of magnitude.
2 Method
AI Feynman 2.0 recursively decomposes mystery functions into simpler modules, using neural-network gradients to detect graph modularity and Pareto optimality to balance accuracy with complexity. It also improves robustness through MEDL-based fitting, statistical pruning, and extensions to sampled probability distributions.
- Recursive strategy: The algorithm uses divide-and-conquer recursion, directly solving low-order polynomial or sufficiently simple mysteries and otherwise replacing them with simpler mysteries.The recursive strategy aims to reduce the number of input variables before solving subproblems.
- Modularity discovery: Graph modularity is discovered by training a neural network on the data table and numerically testing its fitted function and gradients.The method tests six modularity types, including compositionality, symmetry, generalized symmetry, generalized additivity, and separability.
- Modularity discovery: Compositionality reduces f(x) = g(h(x)) to a one-dimensional regression for g after finding an h whose gradient is proportional to that of f.The original data table is transformed by replacing x with the scalar h(x), then regression proceeds recursively.
- Modularity discovery: Generalized symmetry is detected when normalized gradients over one variable group are independent of the remaining variables, without initially knowing the inner function h.This postpones the expensive search for h until the gradient signature indicates that a solution exists.
- Robustness and search: Pareto-optimal candidates are selected by jointly tracking description-length complexity and mean error-description-length rather than optimizing accuracy alone.MEDL is intended to improve robustness to outliers, while description length measures both formula complexity and prediction-error information.
- Robustness and search: Statistical hypothesis testing accelerates brute-force search by rejecting candidates after a small number of evaluations when their estimated error exceeds the current Pareto-frontier record.The procedure commonly uses ν = 10 standard deviations as the rejection criterion, with larger ν trading runtime for robustness.
3 Results
The method is more robust to noise, solves equations that previously resisted symbolic regression, and extends symbolic regression to probability distributions from samples.
- 73 of 100 Feynman database problems were solved at noise level r = −1, with typically 1-3 orders of magnitude greater robustness than [25].
- Within two hours, the method solved all tested new modularity equations and four outstanding mysteries that [25] had failed to solve.The comparison set included 17 previously failed mysteries and a dozen newly selected mysteries.
- 80% of ten tested probability distributions were discovered from samples, requiring between 10^2 and 10^5 samples.The normalizing-flow training took about 20 minutes on one CPU and scaled roughly linearly with sample size and network weights.
- The method’s robustness strategy avoids overfitting through validation-loss early stopping, domain restriction, modularity effects, and minimum-description-length principles.
4 Conclusions
The paper concludes that Pareto-optimal symbolic regression improves robustness and extends discovery to harder equations and symbolic density estimation, while several equations remain unsolved.
- The released method combines neural networks, graph modularity, hypothesis testing, and normalizing flows to improve noise robustness and solve harder problems, including symbolic density estimation.
- Some equations remain unsolved because their form prevents decomposition into sufficiently small pieces for the available search procedures.
- For certain failures, the brute-force search is too limited by runtime or by the available basis functions to discover required expressions such as tanh γ.Longer runtime or adding basis functions such as tanh could solve some reported failures.
- Future extensions include discovering additional graph modularity, adding simplification strategies, and applying flow-based regression to sparse high-dimensional density estimation.
- Pareto-optimal regression can produce useful approximate formulas that are both accurate and simple, in addition to exact formulas.
Broader Impact
The method may broaden access to interpretable symbolic models, while introducing risks from extrapolation, complexity choices, and accelerated progress toward AGI.
- Broader impact: Symbolic regression may benefit researchers across the natural and social sciences by enabling broader mathematical pattern discovery.The paper connects this potential to the ubiquity of linear regression and the future availability of sufficiently capable algorithms.
- Broader impact: Closed-form Pareto-optimal models offer simpler, interpretable approximations that may reduce overfitting-related bias and failure risk.Their formulas make it easier for humans to inspect computations and judge whether they embody unacceptable bias.
- Risks: Automation bias may arise when users overtrust formulas extrapolated into untested domains.The paper also warns that symbolic regression could encourage phenomenological modeling instead of first-principles scientific work.
- Scope: The discoverable function class is biased by the chosen basis functions, although the method remains agnostic to mostly differentiable bases.This defines an assumption on the method’s applicability rather than eliminating basis-function dependence.
- Risks: Accelerating symbolic regression, modularity discovery, and program synthesis could hasten AGI development before humanity has adequate tools to manage it safely.The paper also notes that understanding future AI may improve safety relative to relying on inscrutable black boxes.
A Testing for generalized symmetry
The generalized-symmetry test uses normalized neural-network gradients to measure whether selected input subsets produce stable directions, then recursively searches the strongest candidate.
- Gradient test: Generalized symmetry is indicated when the normalized gradient vector is independent of the complementary input variables.The test compares gradients at one point in the candidate subset against gradients from other data points.
- Variation measure: The variation measure V is one minus the smallest eigenvalue of the gradient covariance matrix.V equals 0 when all normalized gradients are identical and approaches 1 − 1/m when eigenvalues are equal.
- Candidate selection: For each input subset of up to n_g variables, the algorithm computes V(x_i) and selects the subset with the smallest median variation.The experiments set n_g = 3 to avoid considering all 2^n subsets for large n.
- Candidate selection: Figure 6 shows stronger evidence for f(x, y, z) = g[h(x, y), z] than for the alternative pairings.The displayed distributions compare the three possible bivariate pairings, with curves slightly smoothed for clarity.
B Testing for generalized additivity
Generalized additivity is tested through additive separability of the logarithm of a neural-network fit, followed by recursive decomposition when the test succeeds.
- Separability criterion: Multiplicative separability of s(x1, x2) is equivalent to additive separability of f(x1, x2) = ln s(x1, x2).The method therefore tests ln s_NN(x1, x2) using a normalized separability score.
- Separability criterion: The score S[f] is zero for additively separable functions and positive otherwise.A median score below S* = 0.1 is treated as evidence for generalized additivity, and smooth activations are required for the derivative test.
- Recursive reduction: When direct discovery succeeds, the algorithm recursively discovers one-dimensional functions and reduces the original problem to a one-dimensional search over h(x1, x2) = g(x1) + h(x2).This reduction follows symbolic integration of the component solutions and substitution into the original data table.
- Recursive reduction: If direct discovery fails, the method fits f_NN(x1, x2) = F[g(x1) + h(x2)] and recursively searches for F, g, and h.This provides a second route for exploiting generalized additivity.
C Further details on success and failure modes
The paper defines success through held-out accuracy and exact recovery, extends evaluation to normalized density estimation, and documents both recursive successes and complexity-related failures.
- Success definition: Success requires the top-ranked candidate on held-out data to match the true function exactly or recover irrational parameters within 0.01% relative accuracy.Candidates are generated from 90% of the data and ranked by MEDL accuracy on the remaining 10%.
- Success definition: Mathematically equivalent formulas count as solved even when they differ from the tabulated presentation.The paper gives an equivalent triple-angle-style velocity expression as an example within the supplied domain.
- Density estimation: For density estimation, candidates must be non-negative and normalizable, then are normalized and ranked by surprisal loss on held-back test data.Normalization constants are obtained through symbolic or numerical integration.
- Success examples: Tables 7 and 8 compare the highest noise level permitting each of 100 Feynman Database equations to be solved by the original and present methods.The paper uses these tables to document benchmark success examples.
- Success examples: Recursive modularity discovery was sometimes required multiple times, including twice for the quadruple velocity-addition equation.The algorithm successively replaced discovered variable combinations with new variables before continuing the search.
- Failure modes: The complexity measure depends on the operation set and can prefer less intuitive formulas, such as cos(cos θ) over cos^2 θ.The paper attributes this preference to the chosen {×, cos} operations and the small numerical difference over the tested parameter range.
- Failure modes: Taylor expansions are not always favored by the complexity definition, even when they provide more interpretable approximations.The paper’s example treats a fourth-order expansion as less preferred than the unfamiliar exact-form solution.