AI Feynman: a Physics-Inspired Method for Symbolic Regression

Silviu-Marian Udrescu; Max Tegmark

Source-linked AI summary

AI Feynman: a Physics-Inspired Method for Symbolic Regression

Silviu-Marian Udrescu, Max Tegmark

arXiv:1905.11481v2May 27, 2019physics.comp-phcs.AIcs.LGhep-th

TL;DR

Symbolic regression must recover expressions from data despite an exponentially large search space. AI Feynman combines neural-network fitting with physics-inspired tests for simplicity and recursive decomposition, discovering 100% of the basic Feynman mysteries and 90% of the bonus mysteries, versus 68% and 15% for Eureqa.

Problem
General symbolic regression remains difficult because the number of candidate expressions grows exponentially with string length.
Method
AI Feynman combines neural-network fitting with physics-inspired strategies that detect properties such as symmetry and separability, recursively reducing mysteries to simpler problems.
Results
AI Feynman discovered 100% of the 100 Feynman equations and 90% of the bonus equations, compared with Eureqa’s 68% and 15%, respectively.
Takeaways & Limitations
The algorithm provides a physics-inspired approach that recursively simplifies multidimensional analytic regression problems and supports quantitative benchmarking through public mystery sets.

Abstract

from arXiv · show

A core challenge for both physics and artificial intellicence (AI) is symbolic regression: finding a symbolic expression that matches data from an unknown function. Although this problem is likely to be NP-hard in principle, functions of practical interest often exhibit symmetries, separability, compositionality and other simplifying properties. In this spirit, we develop a recursive multidimensional symbolic regression algorithm that combines neural network fitting with a suite of physics-inspired techniques. We apply it to 100 equations from the Feynman Lectures on Physics, and it discovers all of them, while previous publicly available software cracks only 71; for a more difficult test set, we improve the state of the art success rate from 15% to 90%.

I. INTRODUCTION

Symbolic regression seeks an expression matching data from an unknown function, but exhaustive search is infeasible because expression strings grow exponentially. AI Feynman addresses this by combining neural-network-detected simplicity with physics-inspired transformations and recursive decomposition.

Symbolic regression seeks a symbolic expression y = f(x1, ..., xn) that matches a table of numerical data.
The general problem remains unsolved because the number of candidate symbol strings grows exponentially with expression length.Brute-force enumeration can take longer than the age of the universe to reach the target function.
AI Feynman uses neural networks to detect hidden symmetries and separability, recursively reducing difficult mysteries to simpler problems with fewer variables.
Physics-relevant functions often exhibit units, low-order polynomial structure, compositionality, smoothness, symmetry, or separability that can simplify symbolic discovery.
Dimensional analysis, polynomial fitting, parse-tree search, neural-network approximation, and symmetry tests each exploit a distinct simplifying property.

A. Overall Algorithm

The overall algorithm applies physics-inspired modules iteratively, transforming a mystery into simpler problems and recursively rerunning the full procedure. Its modules include dimensional analysis, polynomial fitting, and brute-force search.

The algorithm tries modules in sequence and recursively sends transformed subproblems to fresh instances when the full mystery is not solved directly.Figure 1 schematically represents this iterative divide-and-solve process.
Brute-force search is applied to symbolic pieces after transformations make them simpler, rather than typically attacking the full mystery directly.
Dimensional analysis converts variables into dimensionless combinations, often reducing the number of independent variables.The method represents physical units as vectors and uses a null-space basis to construct the transformed mystery.
Choosing dimensionless variables that depend on as few original variables as possible tends to produce integer powers and simpler final expressions.
The polynomial module fits degrees 0 through 4 by solving linear systems and accepts a fit when its r.m.s. error is at most εp.

D. Brute Force

AI Feynman’s brute-force module enumerates syntactically valid symbolic strings by increasing complexity, using alternative symbol sets and selection criteria to balance expressiveness, runtime, and simplicity.

The brute-force module tests symbolic expressions in increasing complexity until fitting error falls below ϵp or runtime exceeds tmax.
Reverse Polish notation represents expressions as symbol strings without parentheses, such as “xy+” for x + y.
Three symbol subsets are tried in turn to balance the cost of larger alphabets against the need for longer or more expressive expressions.
Two brute-force variants automatically solve multiplicative or additive constants so search can focus on the symbolic structure.
Among candidates with fitting error below ϵb, the winning expression has the smallest total description length, prioritizing simpler formulas.

E. Neural-network-based tests & transformations

Neural networks provide interpolating functions that let AI Feynman test hidden symmetries and transform mysteries into lower-dimensional or separable problems. These transformations are then solved recursively by the full algorithm.

Neural-network interpolation enables evaluating a mystery function at points absent from the original data, which is required for symmetry tests.
The network is a feed-forward fully connected model with six hidden layers using softplus activations, trained on generated mystery data.
Translational symmetry is tested by comparing f(x1, x2, x3, ...) with f(x1 + a, x2 + a, x3, ...).
When translational symmetry is found, x1 and x2 are replaced by their difference, reducing the number of input variables by one.
The algorithm also tests whether variable pairs can be replaced by sums, products, or ratios, then recursively applies the full procedure to the transformed mystery.

3. Separability

The algorithm uses neural networks to detect separability and other simplifying transformations, recursively reducing multivariable mysteries to simpler problems that can be solved by fitting or symbolic search.

Separability: A function is separable when it splits into additive or multiplicative parts with no variables in common.Multiplicative separability can also be tested after taking the logarithm, which converts products into sums.
Separability: The separability test evaluates a non-separability measure over the mystery data and accepts separability when its rms average is below a threshold tied to neural-network validation error.The threshold is chosen as 10 times the neural-network validation error.
Recursive reduction: When separability is detected, the algorithm creates two reduced mysteries, solves them recursively, and recombines their solutions into the original function.For multiplicative separation, the reduced functions are y′ = f(x1, c2) and y′′ = f(c1, x2)/f(c1, c2), with numerical constants corrected during recombination.
Recursive reduction: The algorithm also sets pairs of input variables equal, solves the resulting lower-dimensional mystery, and divides out the found solution when possible.This strategy solves the Gaussian probability distribution example by removing the denominator and then applying a logarithm before brute-force search.
Transformations: Transformations such as square root, squaring, logarithm, exponentiation, inversion, and trigonometric functions are applied before brute-force or polynomial fitting to simplify selected equations.Squaring the 3D distance formula converts it into a polynomial suitable for polynomial fitting.
Hyperparameters: The method includes hyperparameters that can be tuned to optimize performance on the problems being solved.These settings are summarized in Table II.

III. RESULTS

The paper introduces a freely available database for evaluating symbolic regression on physics equations, with data, units, analytic answers, and solution-method records spanning standard and bonus sets.

Database: The Feynman Symbolic Regression Database provides a standardized resource for quantitative testing of symbolic regression algorithms.Each regression mystery includes data and additional information for evaluation.
Database: Each mystery includes a data table, an optional unit table, and the analytic expression used for answer-checking.The data table represents rows of input variables and function values; the unit table records physical units as six-dimensional vectors.
Evaluation: Candidate expressions are counted as correct when they are algebraically equivalent to the mystery function, even if their symbolic forms differ.For example, reordered additions are accepted as equivalent expressions.
Test sets: The main database contains 100 equations from the Feynman Lectures on Physics, covering one to nine independent variables and multiple elementary functions.The equations span classical mechanics, electromagnetism, quantum mechanics, and other core physics topics, with complex equations prioritized and derivatives or integrals excluded.
Test sets: A separate bonus set contains 20 famous and complicated equations drawn from other seminal physics books.The sources include works on classical mechanics, electrodynamics, gravitation and cosmology, and quantum field theory.
Evaluation: The database records equation identifiers, methods used, data requirements, solution times, and noise tolerances for tested equations.The method notation includes dimensional analysis, brute force, polynomial fitting, variable equalization, symmetry, and separability.

B. Method comparison

AI Feynman combines neural-network fitting with physics-inspired strategies to simplify symbolic-regression problems recursively. Compared with Eureqa, it achieves stronger performance, especially when neural networks identify symmetries and separability.

Experimental comparison: AI Feynman was compared with Eureqa on the Feynman Database using a maximum of 2 hours of CPU time per mystery.Eureqa used four CPUs per mystery, while AI Feynman used the settings specified in Table II.
Experimental comparison: 71% of the 100 basic mysteries were solved by Eureqa, compared with 100% solved by AI Feynman.
Neural-network role: Neural networks are especially important for the most complicated mysteries because they enable variable elimination through discovered symmetries and separability.
Neural-network role: Without dimensional analysis, AI Feynman still solved 93% of the mysteries by repeatedly discovering and factoring out variables using neural-network strategies.The strategy was used six times in one example: three translational-symmetry discoveries, two variable groupings, and one separability step.
Progress mechanism: AI Feynman’s progress comes from repeatedly reducing the number of independent variables, whereas Eureqa improves through successively better approximations.The paper notes that variable reduction is virtually guaranteed to move AI Feynman in the right direction, unlike approximation-based progress.

C. Dependence on data size

AI Feynman often solves polynomial-fit and brute-force cases with very small data sets, but neural-network-dependent cases require substantially more observations. More complex equations also increase overfitting risk.

Data requirements: Most equations solved by polynomial fitting and brute-force methods require only 10 data points.
Data requirements: 100 data points are needed in some cases because complex true equations can otherwise be overfit by an incorrect equation that is too simple.
Data requirements: Neural-network-dependent equations require between 10^2 and 10^6 data points to learn the mystery function with r.m.s. accuracy better than 10^-3.These expressions are typically more complex than equations solved by alternative approaches.

D. Dependence on noise level

AI Feynman is robust to moderate noise in the dependent variable, recovering most equations exactly at relative noise ϵ ≤ 10^-4. The noise evaluation favored exact recovery over approximate fits and did not test noise in independent variables.

Noise robustness: Most equations can still be recovered exactly when the relative dependent-variable noise level is ϵ = 10^-4 or less.
Evaluation caveat: The noise experiments adjusted brute-force and polynomial-fit thresholds to prefer no solution over an approximate solution.The thresholds were not optimized separately for each mystery, so some equations might permit exact recovery at higher noise levels.
Evaluation caveat: The study did not quantify performance when noise was added to independent variables or when the algorithm was applied directly to real-world data.

E. Bonus mysteries

On deliberately more complex bonus mysteries, AI Feynman substantially outperforms Eureqa, but its failures expose limits of brute-force search and neural-network separability detection. The paper also frames the basic set as training data and the bonus set as a test set.

Benchmark design: The 100 basic mysteries were optimized during implementation and hyperparameter development, whereas the 20 bonus mysteries were selected and analyzed afterward as a test set.
Benchmark results: 90% of bonus mysteries were solved by AI Feynman, compared with 15% solved by Eureqa.The larger performance gap reflects the greater equation complexity and the increased need for neural-network strategies.
Failure analysis: AI Feynman failed on two bonus mysteries because the resulting brute-force searches were estimated to require about 2 years and about 100 times the age of the universe.
Failure analysis: One failure resulted from a neural network missing separability because a fifth-power denominator created a large dynamic range.Suggested remedies include limiting the parameter range or analyzing the logarithm of the absolute value.
Future improvements: Adding numerically optimized parameter symbols could address both failures, but this capability was implemented in Eureqa rather than AI Feynman.
Benchmark results: On the separate mystery-function test set, AI Feynman discovered 66.7% of equations, compared with 48.9% for Eureqa.The equations were mostly arbitrary compositions lacking the symmetries and separability exploited by the neural-network component.
Contribution: The paper presents a recursive algorithm that combines traditional fitting with neural networks to discover symmetries and separability and reduce problems to simpler pieces.
Contribution: The authors created a downloadable benchmark containing 100 Feynman equations and 20 additional difficult mysteries.

A. Key findings

AI Feynman discovered all 100 Feynman equations and 90% of the bonus equations, substantially exceeding Eureqa’s results. Its largest gains occur on difficult problems where neural-network-guided reductions simplify the search.

AI Feynman discovered 100% of the Feynman equations and 90% of the bonus equations, compared with Eureqa’s 68% and 15%, respectively.Most Feynman equations remained solvable with 10^2 data points or percent-level noise, while the most complex neural-network-dependent equations required more data and less noise.
The largest improvements over Eureqa occur on the most difficult mysteries, where AI Feynman repeatedly deploys its neural-network strategy.
Genetic algorithms improve through successively better approximations, whereas AI Feynman progresses by reducing the number of independent variables.AI Feynman’s variable reductions are described as virtually guaranteed steps in the right direction; genetic algorithms explore a vast search space and risk local optima.

B. Opportunities for further work

The paper identifies several ways to extend AI Feynman, including improved neural-network fitting, richer symbolic searches, derivative-aware inputs, and hybridization with genetic algorithms. These directions target fitting noise, broader formula discovery, and more robust candidate generation.

B. Opportunities for further work: Elementary-function choices and hyperparameters could be selected through automated pre-analysis of each mystery.Observed oscillations could motivate including sin and cos, while their absence could justify excluding them to save time.
B. Opportunities for further work: Derivative estimates can be added as independent variables so the algorithm can discover suspected differential equations.
B. Opportunities for further work: Better neural-network architectures could reduce fitting noise toward 10^-6 and simplify subsequent solution steps.The method needs high accuracy within the observed data domain, even if the network generalizes poorly outside that domain.
B. Opportunities for further work: The brute-force symmetry search could be generalized from simple binary operations to longer strings involving multiple variables.The current implementation tests whether two variables can be replaced by a bivariate function using +, −, ∗, or /.
B. Opportunities for further work: Neural-network discoveries of special cases could guide local brute-force searches toward the full formula.For example, expressions valid at a = 0 can guide searches using terms that vanish or equal unity there.
B. Opportunities for further work: Combining AI Feynman with genetic algorithms could outperform either method alone by using Pareto-frontier candidates for factors and full-expression testing.Genetic algorithms can perform well under significant noise by returning increasingly complex formulas with progressively better accuracy.