Solving General Arithmetic Word Problems

In plain words

The paper is about word problems of the kind found in school arithmetic: a short story with numbers in it and a question such as "how many books in total?". The system reads the story and works out the arithmetic expression that answers the question. It handles problems that need several steps and mix addition, subtraction, multiplication and division. It does not use predefined equation templates.

The trick is to break the big job into small yes-or-no and "which operation joins these two numbers" questions. For every pair of numbers in the story, a classifier guesses which operation joins them in the final expression. A second classifier guesses whether each number is needed at all. The system then searches for the expression that agrees best with these guesses, while respecting common sense: a count of things should be a whole number, and an amount of money should not be negative.

To make the classifiers focus on the right words, the authors extract a short "schema" for each number: the verb it attaches to, the unit it measures, and whether it is a rate such as "per hour". The reported results are the authors' own, on three datasets of different difficulty. The multi-step dataset is the hardest, and accuracy there is much lower.

TL;DR

Multi-step arithmetic word problems are solved by predicting a read-once expression tree. Two SVM classifiers score (a) whether each quantity is relevant and (b) which operation sits at the lowest common ancestor (LCA) of each pair of quantities in a monotone tree. A beam search (k = 200) combines these scores under two constraints: the answer is positive, and the answer is an integer for "how many" questions. The authors report 78.0% on AI2 (positive constraint only), 73.9% on IL and 45.2% on the new Commoncore set with all constraints. No official code is published.

Problem

Word problems can be solved by an expression built from the numbers in the text, provided each number is used at most once §1 §3. Earlier systems covered only some operations §2 or needed extra annotation §2. Template systems assume the test equations look like training equations, which breaks on unseen multi-step types §2 §5.4. The paper therefore asks for a method that handles all four operations, multi-step problems and unseen problem types, without extra annotation §1 §2.

Method

The pipeline has four parts §4:

1. Detect the quantities q_1 ... q_n in the problem text §4.
2. Extract a quantity schema for each quantity: the associated verb, its subject, its unit, related noun phrases and any rate §4.2.
3. Predict, with two classifiers, the relevance of each quantity §4.3 and the LCA operation of each pair §4.4.
4. Combine the predictions with a constrained beam search that outputs one expression tree §4.1.

Expression trees and the decomposition

An expression tree for a valid expression has quantities at the leaves and operations at internal nodes. Each node's value is the value of its left child combined with its right child under that node's operation eq. 1 §3. A tree is monotonic if (i) when an addition node and a subtraction node are adjacent, the subtraction node is the parent, (ii) when a multiplication and a division node are adjacent, the division node is the parent, and (iii) two subtraction nodes and two division nodes are never adjacent §3, Definition. Every valid expression has a monotonic tree [Theorem 3.1]. Two monotonic trees for the same expression agree on the LCA operation of every quantity pair [Theorem 3.3]. The LCA label takes one of six values: +, ×, −, −reverse, ÷, ÷reverse, where the "reverse" labels say which side of the subtraction or division the first quantity lies on eq. 2 §3.

Because that label is unique per pair, the problem reduces to predicting one label per pair plus a relevance score per quantity. The paper also points out that any single correct pairwise label is enough to pin down the expression, which is why the redundant pairwise predictions are useful §4.

Scoring and inference

Let I(E) be the set of quantities that E does not use, and let Pair(q_i, q_j, op) and Rel(q) be the classifier scores. The score of an expression E is a weighted sum of the Rel scores of unused quantities, plus the Pair scores of all pairs of used quantities at the LCA operation read from a monotonic tree for E eq. 3 §4.1. Inference returns the highest-scoring expression that satisfies the constraints, using the argmax in eq. 4 §4.1.

The search is a bottom-up beam search. It first enumerates every subset of quantities to call irrelevant, keeping only subsets that leave at least two relevant quantities. Each relevant quantity is a term. From each state the search combines any two terms with any of the four operations, keeps the top k states, and stops when every state has one term §4.1.

# Constrained beam search over expressions  [§4.1] [eq. 3] [eq. 4]
# Input:  quantities (n); rel_scores (n,); pair_scores (n, n, 6)
# Output: one expression tree

def solve(quantities, rel_scores, pair_scores, w_rel, beam_size):
    # 1. Enumerate every set of irrelevant quantities; keep only
    #    sets that leave at least two relevant quantities  [§4.1]
    start_states = irrelevant_subsets(quantities, min_relevant=2)

    # 2. Grow expressions bottom-up: join any two terms with any of
    #    the four operations  [§4.1]
    beam = start_states
    while any(len(state.terms) > 1 for state in beam):
        candidates = []
        for state in beam:
            for term_a, term_b in pairs_of(state.terms):
                for operation in ["+", "-", "*", "/"]:
                    candidates.append(join(state, term_a, term_b,
                                           operation))
        # 3. Keep the top k candidates (k = 200 in the paper)  [§4.1]
        #    Scoring of partial states is not stated in the paper.
        beam = top_k(candidates, beam_size, key=score)

    # 4. Return the best complete tree that meets the constraints,
    #    otherwise the best tree in the beam  [§4.1]
    return best_valid(beam) or beam[0]

Constraints §4.1:

• Positive answer: reject expressions whose value is negative.
• Integral answer: for "how many" questions, accept only integer values.

If no tree in the final beam passes the constraints, the top beam tree is used instead §4.1.

Quantity schema

For each quantity the paper extracts §4.2:

• Associated verb: the first verb reached by walking up the dependency tree from the number, using the easy-first parser §4.2.
• Subject of the verb: the noun phrase acting as subject, if any §4.2.
• Unit: the tokens of the shallow-parser phrase that contains the number (excluding the number), plus the noun phrase after "of" if present. If no unit token is found, the unit of the neighbouring quantities is used §4.2.
• Related noun phrases: noun phrases attached to that phrase by an NP-PP-NP pattern. If a sentence has only one quantity, all its noun phrases count §4.2.
• Rate: whether the number is a rate, with two unit components, for example "7 kilometers per hour" or "each egg costs 2 dollars" §4.2.

The question is also reduced to a surface span, for example "How much will John have to pay" §4.2.

Relevance classifier

A binary SVM predicts whether a quantity is needed for the solution. Its score is Rel(q) §4.3. Features §4.3.1:

• Unit features: whether the quantity's unit appears in the question; whether other quantities match the question better; how many quantities tie for the best match §4.3.1.
• Related noun phrase features: whether a related noun phrase appears in the question, and whether other quantities' phrases match better §4.3.1 tab. 3.
• Miscellaneous: the number of quantities in the text (two-quantity problems usually keep both) §4.3.1.
• Pairwise conjunctions of all features §4.3.1.

LCA operation classifier

A multiclass SVM predicts one of the six LCA labels for a pair. Its confidence scores are Pair(q_i, q_j, op) §4.4. Features §4.4.1:

• Individual quantity: the dependent verb; whether the quantity is a rate and whether a rate unit appears in the question; adverbs and comparative adjectives within 5 tokens of the quantity §4.4.1.
• Quantity pair: same dependent verb; same verb mention; same unit; for a rate, which unit component matches the other quantity; whether the first value is larger §4.4.1.
• Question: comparison words ("more", "less", "than") and rate words ("each", "one") §4.4.1.
• Pairwise conjunctions of all features §4.4.1.

Hyperparameters

Results

Author-reported. Setup: three datasets (AI2, IL, Commoncore), accuracy of the full pipeline per dataset §5.1 §5.4. Baselines were run by the authors (IL, Commoncore) or taken from prior work (AI2) §5.4. Best numbers are in bold in tab. 6.

Full system and baselines tab. 6 §5.4:

Relevance classifier, accuracy tab. 5 §5.2. "Relax" is the fraction of quantities labelled correctly; "Strict" is the fraction of problems with all quantities labelled correctly:

LCA operation classifier, accuracy tab. 4 §5.3. Relax is per quantity pair; Strict is per problem:

Error analysis §5.5: most errors come from wrong quantity-schema extraction (IL: 57% of relevance errors, 39% of LCA errors) and from unknown or rare verbs (AI2 relevance: 20%; AI2 LCA: 16%). Non-standard rate phrasings are a named failure mode §5.5.

Paper vs code

No official code. The paper gives no code link, and its only pointer is a dataset resource page §6. A GitHub search for the title returned one repository, a fork by a third-party account, which is not used. No project page was linked.

Pitfalls

• Partial-state scoring is undefined. eq. 3 scores complete expressions, but the beam keeps the top k states at every step §4.1. How partial states are scored (and how Rel and Pair contribute to them) is not stated. Implementers must choose this, and the choice will change results.
• The relevance weight is sensitive. w_Rel is searched over a grid spanning twelve orders of magnitude and picked on training accuracy §4.1. Whether this search runs inside each cross-validation fold is not stated, and no sensitivity curve is reported.
• Constraint fallbacks are silent. If no beam tree passes the constraints, the top tree is returned without a flag §4.1. Count these cases when evaluating.
• Question-type detection is not described. The integral constraint depends on spotting "how many" questions, and the positive constraint on spotting amount questions §4.1. Neither detector is specified.
• Monotonic trees are required for the labels. Without a monotonic tree, LCA labels can disagree between trees for the same expression §3 (illustrated by the two trees in Figure 2 fig. 2). Enforce the four monotonicity rules before reading labels.
• Read-once only. The method solves only problems whose answer uses each quantity at most once §1 §3. Problems that reuse a number are out of scope, and the paper does not measure how common they are.
• Feature engineering dominates. Quantity-schema extraction errors cause most classifier errors on IL §5.5. Dropping individual-quantity features on CC drops the strict LCA accuracy to 0.0 tab. 4. Budget effort for the parser and shallow-parser output, not only the classifier.
• Headline AI2 number depends on the constraint setting. The text claims state of the art on AI2 §5.4. The best AI2 value in tab. 6 (78.0) is the positive-constraint-only setting, not the all-constraints full system (72.0). Report which setting you compare with.
• Dataset construction changes the IL task. The authors cluster and prune IL to avoid template repeats, and the IL result is on their modified set §5.1. Compare numbers only against this version.
• CC question features do not help. Multi-step problems rarely state every operation in the question, so question features contribute nothing on CC §5.3. Don't assume they transfer to multi-step text.
• Feature conjunctions are unbounded. Pairwise conjunctions of all feature groups are used §4.3.1 §4.4.1, but the number of features, the kernels, C and regularisation are not stated. Results depend on these Illinois-SL defaults, which are not written out in the paper.
• Pair features need numeric values. The "first value is larger" feature §4.4.1 needs quantities parsed as numbers. How number words and fractions are parsed is not stated.

Lineage

• Builds on: the constrained conditional model framework with an L+I scheme (independent classifiers combined at inference) §2, using Chang et al. (2012) for the framework and Roth and Yih for the constrained-optimisation setup §4.1. Concept: [[constrained-conditional-models]].
• Compared against: Hosseini et al. (2014) on AI2 §5.4; Roy et al. (2015) on IL, run by the authors §5.4; Kushman et al. (2014), a template-based system, on all three §5.4.
• Superseded by: not stated in this card. No later paper in this wiki is linked to it.

Attribution

Compiled from the arXiv LaTeX source (v2, CC BY 4.0). Authors: Subhro Roy and Dan Roth. This card condenses the paper, restates its tables and equations, and adds pseudocode and a pitfalls list. It is not endorsed by the authors.