Neural networks, particularly Transformers, are designed to process linear sequences of tokens. However, mathematical and logical expressions are inherently hierarchical, traditionally represented as trees where internal nodes are operators and leaves are operands. To bridge this gap, researchers have converged on expression tree linearization: a method of serializing these trees into unambiguous sequences that allow sequence-to-sequence models to perform "rigid" symbolic reasoning.
The Problem with Infix Notation
Standard mathematical notation (e.g., $2 + (3 \times 4)$) is known as infix notation. While intuitive for humans, it is computationally difficult for neural networks to generate for two reasons:
- Ambiguity: Without parentheses or complex precedence rules (PEMDAS), the order of operations is unclear.
- Syntactic Overhead: Generating balanced parentheses is a structural requirement that consumes model capacity. If a model fails to close a bracket, the entire expression becomes syntactically invalid.
As Lample and Charton demonstrate in Deep Learning For Symbolic Mathematics, treating math as a translation task requires a representation that is as streamlined as natural language but as precise as a computer program.
Serialization via Tree Traversal
The solution is to represent expressions as trees and then flatten them using specific traversal algorithms. Two primary formats emerge across the literature:
- Prefix Notation (Polish Notation): Derived from a pre-order traversal (root-left-right). Operators precede their operands (e.g., $+ \ 2 \ \times \ 3 \ 4$). Ustyuzhanin et al. note in Symbolic expression generation via variational auto-encoder that this format simplifies the generation of valid formulas by removing the need for explicit brackets.
- Postfix Notation (Reverse Polish Notation): Derived from a post-order traversal (left-right-root). Operands precede their operators (e.g., $2 \ 3 \ 4 \ \times \ +$). Wang et al. argue in Reinforcement-Enhanced Autoregressive Feature Transformation that postfix notation ensures every generated sequence is structurally valid and reduces the token set, making it easier for decoders to process complex formulas.
Why Linearization Works
The power of these representations lies in their unambiguity. In a linearized tree, the structure of the calculation is baked into the sequence itself.
1. Eliminating Parentheses
By using prefix or postfix notation, the model no longer needs to learn the "tax" of balancing nested parentheses. d'Ascoli et al. highlight in ODEFormer that this structural choice ensures every generated sequence can be uniquely parsed back into a computational tree. This is particularly useful for Symbolic Regression, where the model must discover the underlying physics of a system from noisy data.
2. Leveraging Fixed Arity
In many formal systems, operators have a fixed number of arguments (arity). For example, addition ($+$) is binary, while square root ($\sqrt{x}$) is unary. Yeh and Ong explain in Most of a Formal Proof is Forced that when arity is fixed, a pre-order traversal creates a token stream that requires no delimiters at all. The model simply "knows" how many tokens to expect after each operator.
3. Simplifying the Grammar
For tasks like Math Word Problems (MWP), Wang et al. show in Translating Math Word Problem to Expression Tree that predicting a postorder traversal allows the decoder to focus on the logical sequence of operations rather than the surface-level syntax of the expression. This is echoed in Evolutionary Large Language Model for Automated Feature Transformation, where postfix notation reduces syntactic errors during the automated discovery of new data features.
Applications Across Domains
This technique has enabled Transformers to master domains previously reserved for symbolic solvers:
- Formal Logic: Hahn et al. demonstrate in Teaching Temporal Logics to Neural Networks that prefix notation allows models to learn the underlying semantics of Linear Temporal Logic (LTL). Similarly, Liu et al. use prefix notation in Lang2LTL to help robots translate natural language instructions into executable logic.
- Advanced Calculus: Charton et al. show in Learning advanced mathematical computations from examples that models can solve differential equations and design control systems by treating linearized tree sequences as a language.
- Finance and Regression: Xu et al. use Polish notation in HRFT to generate interpretable risk factor formulas for high-frequency trading, while Wu uses pre-order traversal in Transformer-based model for symbolic regression to recover the "skeletons" of mathematical equations from raw data.
By transforming hierarchical logic into a flat, unambiguous sequence, linearization allows neural networks to treat symbolic reasoning as a standard language modeling task, effectively bridging the gap between connectionist pattern recognition and symbolic logic.
Key Foundational Work
Modeling Intra-Relation in Math Word Problems with Different Functional Multi-Head Attentions (2019) — contributed 1 concept elements to this direction.
Translating Math Word Problem to Expression Tree (2018) — contributed 1 concept elements to this direction.