Translating a Math Word Problem to a Expression Tree

Lei Wang, Yan Wang, Deng Cai, Dongxiang Zhang, Xiaojiang LiuEMNLP 2018

TL;DR

This paper tackles the ambiguity in translating math word problems into equations by proposing an "equation normalization" method that converts potentially multiple valid equations into a single, canonical expression tree. They then demonstrate that combining multiple sequence-to-sequence models (an ensemble approach) with this normalization significantly boosts performance on the Math23K dataset.

What Problem Does This Paper Address?

Automatically solving math word problems (MWPs) is a long-standing challenge in NLP. While sequence-to-sequence (Seq2Seq) models have shown promise, a key issue is that a single MWP can often be represented by multiple, mathematically equivalent equations. This "equation duplication" problem creates a non-deterministic output space, hindering the performance of models trained with maximum likelihood estimation, which aim to find the single "best" translation. For example, the problem "Dan has 5 pens and 3 pencils, Jessica has 4 more pens and 2 less pencils than him. How many pens and pencils does Jessica have in total?" could be translated to x = 5+4+3-2, x = 4 + (5 - 2) + 3, or x = 5 - 2 + 3 + 4, all yielding the correct answer.

Methods

The paper introduces two main innovations:

  1. Equation Normalization: To address equation duplication, they propose a two-step normalization process:
  2. Order Normalization: Rules are defined to standardize the order of number tokens within an equation template. This includes prioritizing shorter templates and ordering number tokens based on their appearance in the original problem.
  3. Bracket Normalization (Expression Tree): To handle variations in operator precedence and grouping (e.g., a+b-c vs. a+(b-c)), they convert equation templates into a unique expression tree. Each inner node represents an operator, and leaf nodes represent number tokens. The postorder traversal of this tree then serves as the canonical representation.
  4. Ensemble Model: Recognizing that different Seq2Seq architectures (BiLSTM, Convolutional, Transformer) have their own strengths in solving MWPs, the authors propose an ensemble method. This approach selects the output from the model that generates it with the highest probability, effectively combining their individual capabilities.

Datasets

  • Math23K: This dataset, collected by Wang et al. (2017), contains 23,162 labeled math word problems. The paper uses the testing set for evaluation and splits 1,000 problems from the training set for validation. The problems are primarily linear algebra questions with a single unknown variable.

Key Insights and Ideas

  • Uniqueness is Key: The core insight is that by normalizing equations to a unique representation (the expression tree), the ambiguity that plagues Seq2Seq models can be significantly reduced.
  • Different Models, Different Strengths: The paper empirically shows that various Seq2Seq architectures excel at different types of MWPs. For instance, Transformers might handle complex inference better, while ConvS2S is adept at processing contextual information.
  • Ensembling for Robustness: Combining the strengths of multiple models through ensembling is a powerful strategy for improving overall performance and robustness, especially when individual models have complementary capabilities.
  • Normalization Boosts Performance: Equation normalization, even without ensembling, provides a substantial accuracy improvement across all tested models.

Key Results

  • The proposed equation normalization method, combined with an ensemble of BiLSTM, ConvS2S, and Transformer models, achieved a significant accuracy boost on the Math23K dataset, increasing from a baseline of 60.7% to 68.4%.
  • Equation normalization alone improved the accuracy of individual models by 2.7% to 7.1%.
  • The ensemble model, when compared to individual models, showed further gains. For example, the Transformer model achieved 62.3% accuracy without normalization and 68.4% with normalization and ensembling.

Limitations and Future Work

  • Dataset Size: The authors suggest that the Transformer model's occasional generation of mathematically incorrect templates might be due to insufficient training data for its complex self-attention structures. This implies that larger datasets or more advanced training techniques could further improve Transformer performance.
  • Problem Complexity: The current work focuses on MWPs with a single unknown variable. Future work could explore extending these methods to more complex problems involving multiple unknowns or different mathematical domains.
  • Generalization: While the Math23K dataset is used, the generalizability of the proposed methods to other MWP datasets or even different types of structured text generation tasks could be an area for future exploration.

Summary updated

BibTeX
@inproceedings{wang2018translating,
  author = {Lei Wang and Yan Wang and Deng Cai and Dongxiang Zhang and Xiaojiang Liu},
  title = {{Translating a Math Word Problem to a Expression Tree}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2018},
}
Figure