PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Learning for Symbolic Mathematics

Guillaume Lample, François Charton

arXiv:1912.01412v1cs.SCcs.LG

TL;DR

Neural networks have shown limited success in symbolic computation, motivating models for difficult mathematical transformations. The paper represents problems for seq2seq models and generates large paired datasets, achieving performance that exceeds established mathematical frameworks on the tested tasks, while requiring external validity checking and sometimes wider beam search.

  • Problem

    Neural networks are effective in statistical pattern recognition but have had limited success combining continuous representations with symbolic reasoning.

  • Method

    The paper introduces a mathematical syntax and dataset-generation methods for training seq2seq models on integration and first- and second-order differential equations.

  • Results

    The models outperform Mathematica across all tested tasks, with integration near 100% accuracy and first-order ODE accuracy rising from 81.2% to 97.0% using beam size 50.

  • Takeaways & Limitations

    Standard seq2seq models can perform difficult symbolic mathematics and write equivalent solutions in different forms.

  • Takeaways & Limitations

    Predictions are sometimes incorrect, multiple beam hypotheses are often needed, and validity is established by an external symbolic framework.

Abstract

from arXiv · show

Neural networks have a reputation for being better at solving statistical or approximate problems than at performing calculations or working with symbolic data. In this paper, we show that they can be surprisingly good at more elaborated tasks in mathematics, such as symbolic integration and solving differential equations. We propose a syntax for representing mathematical problems, and methods for generating large datasets that can be used to train sequence-to-sequence models. We achieve results that outperform commercial Computer Algebra Systems such as Matlab or Mathematica.

1 INTRODUCTION

The paper targets symbolic mathematics, where neural networks have had limited success despite their strength in statistical pattern recognition. It represents integration and differential-equation problems for seq2seq models, generates supervised datasets, and reports performance exceeding Matlab and Mathematica.

  • Motivation: Neural networks excel at statistical pattern recognition but remain limited in symbolic computation.Combining symbolic reasoning with continuous representations is identified as a machine-learning challenge.
  • Motivation: Prior neural-network studies of mathematical objects mostly addressed arithmetic tasks, where performance was generally poor.Only a few exceptions investigated broader mathematical tasks.
  • Motivation: Symbolic integration and ordinary differential equations are difficult targets for both trained humans and computer software.Human rules are not guaranteed to succeed, while computer algebra systems use complex algorithms exploring many cases.
  • Motivation: Detecting patterns in mathematical expressions may support integration, but becomes harder as expressions gain more operators.The paper notes that no prior study had investigated neural networks’ ability to detect such patterns.
  • Contributions: The paper proposes a seq2seq-compatible mathematical representation, dataset-generation methods, and evaluations on integration and first- and second-order differential equations.The reported models outperform Matlab and Mathematica.

2 MATHEMATICS AS A NATURAL LANGUAGE

The paper treats mathematical expressions as structured trees and maps those trees to prefix sequences for seq2seq processing. It formalizes the resulting expression space and develops sampling methods to generate balanced random trees and quantify its growth.

  • 2.1 EXPRESSIONS AS TREES: Expressions are represented as trees whose internal nodes are operators or functions and whose leaves are operands, numbers, constants, or variables.Under stated assumptions, expressions and trees have a one-to-one correspondence.
  • 2.1 EXPRESSIONS AS TREES: Tree representations disambiguate operation order, precedence, and associativity without requiring parentheses.Equivalent expressions are represented by equivalent trees.
  • 2.1 EXPRESSIONS AS TREES: Mathematical problems such as simplification, integration, and differential equations can be framed as transformations between expression trees.The paper treats these transformations as a particular instance of machine translation.
  • 2.2 TREES AS SEQUENCES: Prefix notation maps each tree node before its children, producing unambiguous sequences that are shorter because they need no parentheses.Operators, functions, variables, and integers receive specific token representations.
  • 2.3 GENERATING RANDOM TREES: Uniform random expression generation is nontrivial because naive sampling favors particular tree shapes.The proposed algorithm generates selected tree structures with equal probability.
  • 2.4 COUNTING EXPRESSIONS: The expression space is parameterized by internal-node count, unary and binary operators, and possible leaves.Binary and unary-binary tree counts use Catalan and large Schroeder numbers, respectively.
  • 2.4 COUNTING EXPRESSIONS: Adding leaves and binary operators significantly increases the number of possible expressions.Figure 1 plots tree counts and associated expression counts across operator and leaf settings.

3 GENERATING DATASETS

The paper constructs large supervised datasets by generating solvable integration and differential-equation problems with associated solutions. Its approaches balance coverage, solvability, solution structure, and expression length through backward generation, integration by parts, analytic inversion, and simplification.

  • 3 GENERATING DATASETS: The datasets cover symbolic integration and first- and second-order ordinary differential equations.They are designed to provide problems paired with solutions for network training.
  • 3.1 FUNCTION INTEGRATION: Forward generation samples random functions and retains those whose integrals a computer algebra system can compute.This produces a representative subset of externally solvable integration problems.
  • 3.1 FUNCTION INTEGRATION: Backward generation differentiates randomly generated functions and pairs each derivative with its original function as an integration example.This avoids the cost and coverage limitations of computing many integrals directly.
  • 3.1 FUNCTION INTEGRATION: Integration-by-parts generation produces integrals of functions that backward sampling is unlikely to create, without relying on an external symbolic integration system.Known derivative–function pairs are combined to infer new integral pairs.
  • 3.1 FUNCTION INTEGRATION: FWD generates short problems with long solutions, BWD long problems with short solutions, and IBP data comparable to FWD without an external system.The authors suggest mixing BWD and IBP data to improve dataset coverage.
  • 3.2 FIRST ORDER DIFFERENTIAL EQUATION (ODE 1): First-order ODE datasets are generated from bivariate functions F(x,y) analytically solvable for y, then differentiated to obtain equations with known solutions.The method can also generate a solution first and derive an equation it satisfies.
  • 3.2 FIRST ORDER DIFFERENTIAL EQUATION (ODE 1): The first-order construction requires generated functions to be solvable in the constant c, ensured by placing c in exactly one tree leaf.Functions such as c × log(x + c) are excluded because they cannot be analytically solved in c.
  • 3.3 SECOND ORDER DIFFERENTIAL EQUATION (ODE 2): Second-order ODE generation extends the method to functions of x, c1, and c2, requiring solvability first in c2 and then in c1.The differentiation equation can be solved in c1 about 50% of the time, and unsolvable cases are skipped.

4 EXPERIMENTS

The experiments train seq2seq models to generate symbolic solutions and evaluate them with symbolic correctness checks across integration and differential-equation tasks. The models perform strongly on matched datasets and outperform Mathematica on the tested comparisons, while broader generalization depends on training-data diversity.

  • Experimental setup: The models predict primitives or differential-equation solutions with a transformer seq2seq architecture, using beam search widths of 1, 10, and 50.Generated hypotheses are checked symbolically, and an input is counted as solved when any hypothesis in the beam is correct.
  • Results: Close to 100% accuracy is achieved for integration on held-out datasets, including with greedy decoding across FWD, BWD, and IBP.The reported performance is consistent across the three integration datasets.
  • Results: Almost 40% accuracy improvement is observed for second-order differential equations when beam size increases to 50.Across experiments, beam size 50 typically improves accuracy by 8% compared with beam size 10.
  • Comparison with mathematical frameworks: 81.2% to 97.0% accuracy is reported for first-order differential equations when decoding changes from greedy search to beam size 50, surpassing Mathematica.On integration, the model approaches 100% while Mathematica reaches about 85%; Matlab and Maple perform slightly below Mathematica on the tested problems.
  • Generalization across generators: 99.7% accuracy is reached on the BWD test set by models trained with BWD, BWD + IBP, or BWD + IBP + FWD data, but cross-generator accuracy can remain low.A FWD-trained model obtains 17.2% on BWD, while adding IBP and FWD data raises BWD-trained performance on FWD from 27.5% to 94.3%.
  • Generalization beyond the generator: The FWD-trained model sometimes integrates functions that SymPy cannot, despite training only on functions SymPy successfully integrates.The paper reports SymPy accuracy of 30% on the BWD test set and model accuracy of 17.2% for the same cross-generator evaluation.

5 RELATED WORK

Earlier deep-learning work on mathematics largely targeted symbolic simplification, expression equivalence, equation verification, and integer arithmetic, while more difficult integration remained outside the main focus.

  • Computer algebra systems for symbolic integration rely on complex algorithms, including implementations of the Risch algorithm.The complete description of the Risch algorithm exceeds 100 pages and is not fully implemented.
  • Neural networks have been used to simplify treelike expressions and learn semantic representations of algebraic expressions.Related models include recursive neural networks and neural equivalence networks.
  • Neural approaches have also verified symbolic entities, predicted missing equation entries, and assessed whether expressions solve differential equations.
  • Most mathematical applications of deep networks focused on integer arithmetic, while other work considered polynomial functions and differentiation rather than integration.The cited arithmetic work includes addition and multiplication, whereas differentiation is described as significantly easier than integration.

6 CONCLUSION

The conclusion presents standard sequence-to-sequence models trained on generated equation datasets as effective for integration and differential equations, while noting errors and reliance on symbolic validation.

  • 6 CONCLUSION: Standard seq2seq models and a simple transformer perform well on function integration and first- and second-order differential equations.
  • 6 CONCLUSION: The approach outperforms Matlab and Mathematica, which rely on many algorithms, heuristics, and complex implementations.
  • 6 CONCLUSION: The model can generate identical mathematical expressions in substantially different forms.The paper reports that all top-10 generations for one equation were valid solutions despite differing expressions.
  • 6 CONCLUSION: Large datasets are generated by enumerating mathematical expressions and constructing problems with associated solutions.The paper describes dataset generation for integration and first- and second-order differential equations.
  • 6 CONCLUSION: Some hypotheses are incorrect, so obtaining a valid solution often requires considering multiple beam hypotheses.An external symbolic framework validates the generated solution rather than the neural model itself.
  • 6 CONCLUSION: The representation maps expression trees to sequences while imposing one-to-one correspondence through conventions for associative operators and unary minus.Operators are assumed to have at most two operands and associativity defaults to the right; negative expressions use −1 × x.

B MATHEMATICAL DERIVATIONS OF THE PROBLEM SPACE SIZE

The paper analyzes the size of the mathematical-expression space by counting expressions with a specified number of internal nodes, first for binary operators and then for mixed arities.

  • B MATHEMATICAL DERIVATIONS OF THE PROBLEM SPACE SIZE: The derivation counts expressions with n internal nodes using generating functions, closed formulas or recurrences, and asymptotic expansions.

B.1 BINARY TREES AND EXPRESSIONS

For binary expression trees, the paper derives recurrence, generating-function, closed-form, and asymptotic descriptions of the number of possible expressions.

  • B.1 BINARY TREES AND EXPRESSIONS: Binary trees with n internal nodes are counted through a recurrence that partitions the tree into left and right subtrees.
  • B.1 BINARY TREES AND EXPRESSIONS: The generating function B(z) encodes the sequence of binary-tree counts b_n.
  • B.1 BINARY TREES AND EXPRESSIONS: Binary trees with n internal nodes have n + 1 leaves, allowing operator and leaf choices to determine the number of expression combinations.
  • B.1 BINARY TREES AND EXPRESSIONS: The binary-tree count is identified with Catalan numbers and converted into a closed formula for b_n.
  • B.1 BINARY TREES AND EXPRESSIONS: Applying Stirling’s formula yields an asymptotic approximation for the number of binary expressions.

B.2 UNARY-BINARY TREES

The section derives generating-function recurrences for unary-binary tree counts, identifies the resulting sequence as the Schroeder numbers, and obtains an asymptotic estimate.

  • Unary-binary trees are counted by s_n, with initial values s_0 = 1 and s_1 = 2.
  • The tree decomposition yields the recurrence s_n = s_{n−1} + s_0s_{n−1} + s_1s_{n−2} + · · · + s_{n−1}s_0.
  • The generating function S(z) is obtained from the recurrence and its initial condition S(0) = 1.
  • The coefficients generated by S(z) are the Schroeder numbers, which also count diagonal-constrained grid paths.
  • Calculation: The recurrence enables fast O(n) calculation of Schroeder numbers.
  • Asymptotic estimate: Developing the generating function around its smallest singularity provides an asymptotic formula for s_n.

B.3 UNARY-BINARY EXPRESSIONS

The section counts unary-binary expressions by combining tree structures with operator and leaf choices, then gives recurrences and algorithms for generating them randomly.

  • Unary-binary expression counts depend on the number of binary operators because trees with n internal nodes can have different numbers of leaves.
  • Generating function: A unary-binary tree is formed from a binary tree by adding unary parents to its nodes, with the number of additions determined by n and n_2.
  • Generating function: Summing over possible binary-operator counts yields a generating function for expressions with p_1 unary operators, p_2 binary operators, and L leaves.
  • Calculation: Differentiating the generating function produces a recurrence that calculates E_n.
  • Calculation: The recurrence (n + 1)E_n − (p_1 + 2p_2L)(2n − 1)E_{n−1} + p_1(n − 2)E_{n−2} = 0 provides a formula for calculating E_n.
  • Random generation: Random expression generation samples tree structures and decorates internal nodes and leaves with operators and mathematical entities, optionally using nonuniform priors.
  • Random generation: The binary and unary-binary generation algorithms sample node positions and, for unary-binary trees, the next node’s arity using distributions derived from subtree counts D(e, n) and L(e, n).
  • Random generation: The unary-binary recurrence accounts for the next empty position becoming a leaf, unary operator, or binary operator.

D IMPACT OF TIMEOUT ON MATHEMATICA

Mathematica’s integration accuracy improves as its timeout increases, but timeout failures remain substantial even with a three-minute limit.

  • With a 30-second timeout, Mathematica times out on 20% of unsolved equations.
  • Increasing the timeout delay naturally improves Mathematica’s accuracy on the evaluated functions.
  • With a three-minute timeout, timeouts account for 10% of failures, and accuracy without timeout would not exceed 86.2%.

E GENERALIZATION ACROSS GENERATORS

Models generalize well when training and test data use the same integration generator, but cross-generator performance varies because the generators impose different input-output length distributions.

  • Near-perfect integration accuracy is achieved when training and test data are generated by the same method: FWD, BWD, or IBP.
  • Cross-generator accuracy is low from FWD to BWD (17.2%) and BWD to FWD (27.5%), but FWD to IBP reaches 88.9% and BWD to IBP 59.2%.
  • FWD generates short problems with long solutions, whereas BWD generates long problems with short solutions; IBP lies between these distributions.
  • Models learn generator-specific shortening or expansion patterns, which explains the poor reciprocal generalization between BWD and FWD datasets.
  • Adding IBP or FWD data to BWD training improves cross-generator coverage, and self-supervised example generation is suggested as a possible approach.
Loading 1912.01412v1…