Source-linked AI summary
Solving General Arithmetic Word Problems
Subhro Roy, Dan Roth
TL;DR
Arithmetic word-problem solvers have been limited by restricted operations, additional annotations, or predefined templates. This paper uses Expression Trees, decomposed classifiers, quantity schemas, and constrained inference to construct solutions, achieving state-of-the-art performance on two existing datasets and competitive performance on a new multistep dataset.
Problem
Existing arithmetic word-problem systems restricted operations, required additional annotations, or relied on predefined equation templates, limiting the targeted general problem class.
Method
The approach represents valid solutions as read-once arithmetic expressions, uniquely decomposes them with Expression Trees, and combines classifier decisions using quantity schemas and constrained inference.
Results
The system achieves state-of-the-art performance on two existing datasets and competitive performance on a newly created multistep dataset.
Takeaways & Limitations
Decomposed expression prediction supports generalization across problem types, including combinations of operations absent from training examples.
Takeaways & Limitations
The method is limited to problems whose solutions can be expressed as read-once arithmetic expressions, with quantity-extraction and rare-verb errors remaining major error sources.
Abstract
from arXiv · showhide
This paper presents a novel approach to automatically solving arithmetic word problems. This is the first algorithmic approach that can handle arithmetic problems with multiple steps and operations, without depending on additional annotations or predefined templates. We develop a theory for expression trees that can be used to represent and evaluate the target arithmetic expressions; we use it to uniquely decompose the target arithmetic problem to multiple classification problems; we then compose an expression tree, combining these with world knowledge through a constrained inference framework. Our classifiers gain from the use of {\em quantity schemas} that supports better extraction of features. Experimental results show that our method outperforms existing systems, achieving state of the art performance on benchmark datasets of arithmetic word problems.
1 Introduction
The paper introduces a template-free approach to solving multistep arithmetic word problems by decomposing expression construction into simpler predictions and combining them with constrained inference. Quantity schemas focus learning on relevant information, while experiments report state-of-the-art results on existing datasets and competitive performance on a new multistep dataset.
- Motivation: Earlier systems either restricted the operations they handled or assumed solutions came from predefined equation templates.These limitations affected multistep problems involving all four basic operations.
- Contribution: The proposed approach solves a general class of arithmetic problems without predefined equation templates and handles multiple-step arithmetic problems.The approach is illustrated with problems requiring multiple operations.
- Technical approach: Expression Trees uniquely decompose mapping text to arithmetic expressions into prediction problems for the lowest common ancestor operation between quantity pairs.The final tree is composed through joint inference using legitimacy and background-knowledge constraints.
- Generalization: Learning decomposed expressions supports generalization across problem types, including solving a problem requiring both addition and multiplication without prior exposure to that combination.The paper also incorporates constraints such as positivity for amounts and likely integrality for “how many” questions.
- Technical approach: Quantity schemas extract information relevant to each quantity, improve reasoning features, and identify irrelevant snippets such as the activity used to earn money.In the example, the earning activity is unnecessary for determining the amount earned.
- Evaluation: The system achieves state-of-the-art performance on two existing datasets and competitive performance on a newly created multistep dataset.The evaluation covers existing benchmarks and a challenging multistep setting.
2 Related Work
Related work includes restricted arithmetic solvers, template-based systems, broader scientific question-answering efforts, and constrained structured-prediction methods. The paper positions its approach as avoiding additional annotations and predefined templates while generalizing to unseen expression forms.
- Arithmetic problem solving: Earlier arithmetic solvers handled restricted subsets, such as addition and subtraction, and some required additional annotated data for verb categories.These systems did not cover the same general problem class described by this paper.
- Arithmetic problem solving: Kushman et al. mapped problem numbers to predefined equation templates, assuming similar equation forms appeared during training.The paper contrasts this assumption with its own ability to perform competitively on unseen expressions.
- Scientific and quantitative question answering: Related research also addresses standardized tests, biology questions, geometry with diagrams, and science questions verified through images.These efforts extend text understanding toward scientific and quantitative question answering.
- Constrained structured prediction: The constrained inference module uses the L + I scheme of Constrained Conditional Models to combine independently learned components at inference time.This framework has been used to incorporate world knowledge and reduce dependence on large jointly annotated datasets.
3 Expression Tree and Problem Decomposition
The paper represents valid arithmetic solutions as expression trees and uses monotonicity to uniquely decompose text-to-expression mapping into simpler prediction and inference steps.
- Expression trees: A valid expression is a read-once arithmetic expression whose quantities appear at most once and can be represented by a binary expression tree.Leaves represent quantities, while internal nodes represent addition, subtraction, multiplication, or division; evaluating the root gives the expression’s numeric value.
- Monotonicity: A monotonic expression tree places subtraction above adjacent addition and division above adjacent multiplication.These structural constraints normalize alternative tree representations while preserving the represented expression.
- Problem decomposition: The method predicts quantity relevance and pairwise LCA operations, then combines these predictions through joint inference to construct the final expression tree.The theory therefore decomposes mapping text to a complex arithmetic expression into simpler classification problems.
- Problem decomposition: Monotonicity makes the lowest-common-ancestor operation for each pair of quantities invariant across valid tree representations.Without this restriction, the same quantity pair can receive different LCA operations in different trees.
- Theoretical guarantee: Every valid expression has a monotonic expression-tree representation, supporting the paper’s decomposition strategy.The proof gives a procedure for transforming non-monotonic trees while preserving the expression.
4 Mapping Problems to Expression Trees
The system maps problem text to expression trees by predicting quantity relevance and pairwise operations, then selecting a globally coherent tree through constrained inference. Quantity schemas and local quantity-pair features provide information for these predictions and support generalization across problem types.
- Expression-tree mapping: Expression-tree uniqueness reduces mapping text to arithmetic expressions to predicting relevance and lowest-common-ancestor operations between quantities.Joint inference combines these predictions to determine the final expression tree.
- Global inference: The system scores candidate trees using pairwise operation likelihoods and the likelihood that quantities are irrelevant.These scores are combined in a global objective for expression selection.
- Global inference: Constrained inference rejects negative answers for amount or object-count questions and requires integral answers when questions ask “how many.”The valid-expression set is restricted by these legitimacy and background-knowledge constraints.
- Search: Beam search builds expression trees bottom up by enumerating irrelevant-quantity sets and pairwise operations, retaining the top k candidates at each step.The experiments use k = 200; if no constraint-satisfying tree remains, the highest-scoring beam candidate is selected.
- Quantity schemas: Quantity schemas extract information around each quantity, including associated verbs, subjects, units, related noun phrases, and rate components.Rate indicators and nearby adverbs or comparative adjectives help model multiplication, division, and other lowest-common-ancestor operations.
- Features: Quantity-pair features capture shared verbs, unit compatibility, rate-unit matches, and value ordering, while local context includes rate and neighborhood features.These features help distinguish operations such as addition signaled by “more.”
5 Experimental Results
The experiments evaluate the system on three datasets, including a newly created multistep collection, and analyze classifier features, constraints, and end-to-end accuracy. The system achieves state-of-the-art results on AI2 and IL, while constraints improve performance especially on multistep CC problems.
- Datasets: The evaluation covers three datasets: AI2, IL, and a new Commoncore collection of multistep arithmetic problems.Commoncore contains 600 problems, with 100 for each listed operation combination.
- Datasets: The Commoncore evaluation uses 6-fold cross validation across operation categories, testing generalization to multistep problems without matching operation sets in training.Each fold contains all problems from one category, making this setting more challenging than the individual dataset evaluations.
- Classifier Analysis: Quantity-unit features are most important for relevance classification, while individual-quantity features are most significant for LCA operation classification.Removing individual-quantity features reduces CC LCA accuracy to 0.0, and question features are unhelpful on CC.
- End-to-End Results: The full system is evaluated with different constraint configurations and compared with previously best-known and template-based systems.The experiments report results with both constraints, each constraint separately, and no constraints.
- End-to-End Results: The system achieves state-of-the-art results on AI2 and IL without additional annotated data, outperforming the IL comparison system by over 20% absolute.The authors attribute the IL improvement mainly to quantity-schema features that support generalization across problem types.
- End-to-End Results: Constraints contribute an absolute improvement of over 15% on the CC dataset, while the template-based system performs poorly on unseen CC problem types.The integrality constraint is particularly helpful when division can produce fractional answers.
6 Conclusion
The paper introduces a theory and algorithm for solving general read-once arithmetic word problems, achieving strong benchmark performance and supporting natural generalizations. Its expression-tree framework could extend to algebraic expressions, while the datasets are publicly available.
- Contributions: The approach targets problems whose solutions are read-once arithmetic expressions and achieves state-of-the-art performance on two public datasets.Each quantity from the text appears at most once in the expression.
- Contributions: Monotone expression trees provide a unique decomposition that determines arithmetic operations between identified quantities.Classifiers and constrained inference exploit redundancy in this decomposition.
- Future direction: Allowing expression-tree leaves to represent variables could extend the framework from numerical expressions to algebraic expressions and equations.The paper identifies algebra word problems as future work.
- Resources: The datasets used in the paper are available for download.The paper provides a download link for the datasets.