Sequence to General Tree: Knowledge-Guided Geometry Word Problem Solving

Shih-hung Tsai, Chao-Chun Liang, Hsin-Min Wang, Keh-Yih SuACL 2021

TL;DR

This paper introduces Sequence-to-General Tree (S2G), a novel architecture for solving math word problems that can generate interpretable "operation trees" with nodes representing formulas, not just basic operators. This allows S2G to better incorporate domain knowledge, like geometry formulas, leading to improved performance and explainability on complex math problems.

What Problem Does This Paper Address?

Solving math word problems (MWPs) is a challenging task in AI that requires both language understanding and mathematical reasoning. Existing state-of-the-art solvers often generate binary expression trees that, while functional, are lengthy and uninterpretable because they break down complex formulas into many basic operations. This approach fails to leverage mathematical domain knowledge, such as geometry formulas, making it difficult to solve problems that inherently rely on such concepts. The paper aims to bridge this gap by creating solvers that can generate more structured and interpretable representations of solutions, incorporating domain-specific knowledge.

Methods

The core of the proposed solution is the Sequence-to-General Tree (S2G) architecture. Unlike previous "sequence-to-tree" models that generate binary expression trees, S2G's decoder can produce nodes representing formulas with an arbitrary number of arguments. This "general tree" structure allows for more concise and meaningful representations.

Key components of the S2G model include:

  • Encoder: A bidirectional GRU processes the input problem text to generate hidden states and a summary state.
  • Geometry Knowledge Graph (KG): A manually collected KG of geometry shapes and quantities is embedded using a Graph Convolutional Network (GCN). This KG provides semantic information about formula arguments, aiding the decoding process.
  • General Tree Decoder: This decoder recursively generates the operation tree. It predicts the current output (operator, number, or formula) and then, based on the output type, determines the number of children to generate. For formulas, it generates a pre-specified number of child states. The decoder uses attention mechanisms to incorporate encoder states and KG embeddings.
  • Knowledge-Guided Mechanism: The KG embeddings are used to guide the tree decoding, helping the model understand the physical meaning of formula arguments and predict appropriate children.

Datasets

The paper introduces a new dataset called GeometryQA.

  • GeometryQA: This dataset consists of 1,398 geometry word problems. It is curated from Math23K using keywords related to common geometric objects. Crucially, problems are annotated with associated formulas for six major shapes (square, cubic, rectangle, cuboid, triangle, and circle). This dataset is designed to evaluate models on problems requiring domain-specific formulas. The paper also notes that some problems in GeometryQA are intentionally misleading or do not require formulas, testing the model's robustness.

Key Insights and Ideas

  • Interpretable Solutions via Formulas as Nodes: The most significant insight is that allowing nodes in the solution tree to be formulas (e.g., circle_area) rather than just basic operators (+, -, *) dramatically improves interpretability and allows for the direct incorporation of domain knowledge.
  • General Tree Structure for Flexibility: Moving beyond binary trees to general trees allows for a more natural representation of complex formulas and operations, leading to more concise and human-readable solution trees.
  • Knowledge Graph for Semantic Guidance: Integrating a geometry knowledge graph provides crucial semantic context for formula arguments, helping the model make more informed decisions during the decoding process. This is particularly effective for problems that rely on understanding relationships between geometric concepts.
  • Robustness to Misleading Information: The inclusion of problems with misleading keywords or no required formulas in the GeometryQA dataset is a good test for the model's ability to discern relevant information and apply appropriate reasoning, rather than just pattern matching.

Key Results

  • Performance Improvement: The S2G model achieved an accuracy of 54.79% on the GeometryQA dataset, outperforming strong seq2tree baselines like KA-S2T (49.61%) and GTS (51.01%).
  • Knowledge Graph Benefit: Adding the geometry knowledge graph provided a small but positive performance gain, increasing accuracy to 54.99% (S2G + Geometry KG). The authors suggest this gain might be more significant with more complex KGs or a larger variety of geometric shapes.
  • Interpretable Results: The generated operation trees are described as more interpretable due to the explicit inclusion of formulas as nodes, making the solution process easier to follow.

Limitations and Future Work

  • Limited KG Impact: The improvement from the geometry KG was not significant. The authors hypothesize this is because the current dataset only covers six geometric objects, which may not be complex enough to fully demonstrate the KG's effectiveness. Future work could involve expanding the KG to cover more shapes and concepts.
  • Dataset Size: While GeometryQA is described as "middle-sized," further expansion with more diverse problems and formulas could lead to more robust models.
  • Generalizability: The current work focuses on geometry problems. Extending the S2G framework and KG integration to other domains of math word problems (e.g., algebra, physics) would be a natural next step.
  • Formula Discovery: The current model uses pre-annotated formulas. Future research could explore models that can discover or learn new formulas from data.

Summary updated

BibTeX
@inproceedings{tsai2021sequence,
  author = {Shih-hung Tsai and Chao-Chun Liang and Hsin-Min Wang and Keh-Yih Su},
  title = {{Sequence to General Tree: Knowledge-Guided Geometry Word Problem Solving}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
}
Figure