Mapping to Declarative Knowledge for Word Problem Solving
Subhro Roy Dan Roth
cs.CL




















    



















































































definition[1][Definition]

  #1
theoremTheorem[section]

















Mapping to Declarative Knowledge for Word Problem Solving
    Subhro Roy^* 

  Massachusetts Institute of Technology 

  subhro@csail.mit.edu 
Dan Roth^*

  University of Pennsylvania 

  danroth@seas.upenn.edu 

    
==========================================================================================================================================================

^*Most of the work was done when the authors were at the University of Illinois, Urbana Champaign. 

Math word problems form a natural abstraction to a range of
quantitative reasoning problems, such as understanding financial news,
sports results, and casualties of war. Solving such problems requires
the understanding of several mathematical concepts such as dimensional
analysis, subset relationships, etc.









In this paper, we develop declarative rules which govern the
translation of natural language description of these concepts to math
expressions. We then present a framework for incorporating such
declarative knowledge into word problem solving. Our method learns to
map arithmetic word problem text to math expressions, by learning to
select the relevant declarative knowledge for each operation of the
solution expression.

This provides a way to handle multiple concepts in the same problem
while, at the same time, support interpretability of the answer
expression.




Our method models the mapping to declarative knowledge as a
latent variable, thus removing the need for expensive annotations.
Experimental evaluation suggests that our domain knowledge based
solver outperforms all other systems, and that it generalizes better
in the realistic case where the training data it is exposed to is
biased in a different way than the test data.






§ INTRODUCTION


Many natural language understanding situations require reasoning with
respect to numbers or quantities – understanding financial news,
sports results, or the number of casualties in a bombing. Math word
problems form a natural abstraction to a lot of these quantitative
reasoning problems. Consequently, there has been a growing interest in
developing automated methods to solve math word
problems <cit.>.



Understanding and solving math word problems involves interpreting
natural language description of mathematical concepts, as well as
understanding their interaction with the physical world. Consider the
elementary school level arithmetic word problem shown in
Fig <ref>.  To solve the problem, one needs to understand
that “apple pies” and “pecan pies” are kinds of “pies”, and
hence, the number of apple pies and pecan pies needs to be summed up
to get the total number of pies.  Similarly, detecting that “5”
represents “the number of pies per row” and applying dimensional
analysis or unit compatibility knowledge, helps us infer that the
total number of pies needs to be divided by 5 to get the
answer. Besides part-whole relationship and dimensional analysis,
there are several other concepts that are needed to support reasoning
in math word problems. Some of these involve understanding
comparisons, transactions, and the application of math or physics
formulas. Most of this knowledge can be encoded as declarative rules,
as illustrated in this paper.



This paper introduces a framework for incorporating this “declarative
knowledge” into word problem solving. We focus on arithmetic word
problems, whose solution can be obtained by combining the numbers in
the problem with basic operations (addition, subtraction,
multiplication or division). For combining a pair of numbers or math
sub-expressions, our method first predicts the math concept that
is needed for it (e.g., subset relationship, dimensional analysis,
etc.), and then predicts a declarative rule under that concept
to infer the mathematical operation. We model the selection of
declarative rules as a latent variable, which removes the need for
expensive annotations for the intermediate steps.

The proposed approach has some clear advantages compared to existing
work on word problem solving. 






First, it provides interpretability of the solution, without expensive
annotations. Our method selects a declarative knowledge based
inference rule for each operation needed in the solution. These rules
provide an explanation for the operations performed. In particular, it
learns to select relevant rules without explicit annotations for them.


Second, each individual operation in the solution expression can
be generated independently by a separate mathematical concept. This
allows our method to handle multiple concepts in the same problem.

We show that existing datasets of arithmetic word problems suffer from
significant vocabulary biases and, consequently, existing solvers do
not do well on conceptually similar problems that are not biased in
the same way. Our method, on the other hand, learns the right
abstractions even in the presence of biases in the data. We also
introduce a novel approach to gather word problems without these
biases, creating a new dataset of 1492 problems.

The next section discusses related work. We next introduce the
mathematical concepts required for arithmetic word problems, as well
as the declarative rules for each concept. Section <ref>
describes our model – how we predict answers using declarative
knowledge – and provides the details of our training
paradigm. Finally, we provide experimental evaluation of our proposed
method in Section <ref>, and then conclude with a discussion
of future work.




§ RELATED WORK


Our work is primarily related to three major strands of research -
automatic word problem solving, semantic parsing, as well as 
approaches incorporating background knowledge in learning.




 §.§ Automatic Word Problem Solving

There has been a growing interest in automatically solving math word
problems, with various systems focusing on particular types of
problems. These can be broadly categorized into two types: arithmetic
and algebra.

Arithmetic Word Problems Arithmetic problems involve
combining numbers with basic operations (addition, subtraction,
multiplication and division), and are generally directed towards
elementary school students.  RoyRo15, RoyRo17 as
well as this work focus on this class of word problems. The works of
HHEK14 and MitraBa16 focus on arithmetic problems
involving only addition and subtraction. Some of these approaches also
try to incorporate some form of declarative or domain
knowledge. HHEK14 incorporates the transfer phenomenon by
classifying verbs; MitraBa16 maps problems to a set of
formulas. Both require extensive annotations for intermediate steps
(verb classification for HHEK14, alignment of numbers to
formulas for MitraBa16, etc). In contrast, our method can
handle a more general class of problems, while training only requires
problem-equation pairs coupled with rate component annotations.
RoyRo17 focuses only on using dimensional analysis knowledge,
and handles the same class of problems as we do. In contrast, our
method provides a framework for including any form of declarative
knowledge, exemplified here by incorporating common concepts required
for arithmetic problems.

Algebra Word Problems Algebra word problems are characterized
by the use of (one or more) variables in contructing (one or more)
equations. These are typically middle or high school
problems. KHSEA15 looks at single equation problems, and
SWLLR15 focuses on number word problems. KZBA14
introduces a template based approach to handle general algebra word
problems and several works have later proposed improvements over this
approach <cit.>. There has also been work
on generating rationale for word problem solving <cit.>. More
recently, some focus turned to pre-university exam questions
<cit.>, which requires handling a wider range of
problems and often more complex semantics.



 §.§ Semantic Parsing

Our work is also related to learning semantic parsers from indirect
supervision <cit.>. The general approach here is to
learn a mapping of sentences to logical forms, with the only
supervision being the response of executing the logical form on a
knowledge base. Similarly, we learn to select declarative rules from
supervision that only includes the final operation (and not which rule
generated it). However, in contrast to the semantic parsing work, in
our case the selection of each declarative rule usually requires
reasoning across multiple sentences.  Also, we do not require an
explicit grounding of words or phrases to logical variables.



 §.§ Background Knowledge in Learning

Approaches to incorporate knowledge in learning started with
Explanation based Learning (EBL) <cit.>. EBL uses
domain knowledge based on observable predicates, whereas we learn to
map text to predicates of our declarative knowledge. More recent
approaches tried to incorporate knowledge in the form of constraints
or expectations from the output
<cit.>.

Finally, we note that there has been some work in the context of
Question Answering on perturbing questions or answers as a way to test
or assure the robustness of the approach or lack
of <cit.>. We make used of similar ideas in order to
generate an unbiased test set for Math word problems
(Sec. <ref>).





§ KNOWLEDGE REPRESENTATION


We introduce here our representation of domain knowledge. We organize
the knowledge hierarchically in two levels – concepts and declarative
rules. A math concept is a phenomenon which needs to be
understood to apply reasoning over quantities. Examples of concepts
include part-whole relations, dimensional analysis, etc.  Under each
concept, there are a few declarative rules, which dictate which
operation is needed in a particular context. An example of a
declarative rule under part-whole concept can be that “if two
numbers quantify “parts" of a larger quantity, the operation between
them must be addition". These rules use concept specific predicates,
which we exemplify in the following subsections.

Since this work focuses on arithmetic word problems, we consider 4
math concepts which are most common in these problems, as follows:


  * Transfer: This involves understanding the transfer of 
  objects from one person to another. For example, the action
  described by the sentence “Tim gave 5 apples to Jim”, results in
  Tim losing “5 apples” and Jim gaining “5 apples”.

  * Dimensional Analysis: This involves understanding
  compatibility of units or dimensions. For example, “30
  pies” can be divided by “5 pies per row” to get the number of
  rows.

  * Part-Whole Relation: This includes asserting that if
  two numbers quantify parts of a larger quantity, they are to be
  added. For example, the problem in Section <ref> involves
  understanding “pecan pies” and “apple pies” are parts of
  “pies”, and hence must be added.

  * Explicit Math:  Word problems often mention explicit 
  math relationships among quantities or entities in the problem.  For
  example, “Jim is 5 inches taller than Tim”. This concept captures
  the reasoning needed for such relationships.


Each of these concepts comprises a small number of declarative rules
which determine the math operations; we describe them below.



 §.§ Transfer
 

Consider the following excerpt of a word problem exhibiting a transfer
phenomenon: “Stephen owns 5 books. Daniel gave him 4 books.
The goal of the declarative rules is to determine which operation is
required between 5 and 4, given that we know that a transfer is
taking place. We note that a transfer usually involves two entities,
which occur as subject and indirect object in a sentence. Also, the
direction of transfer is determined by the verbs associated with the
entities. We define a set of variables to denote these properties; we
define as Subj1, Verb1, IObj1 the subject, verb and indirect object
associated with the first number, and as Subj2, Verb2, IObj2 the
subject, verb and indirect object related to the second number. For
the above example, the assignment of the variables are shown below:
[Stephen]_Subj1 [owns]_Verb1 5 books. [Daniel]_Subj2 
[gave]_Verb2 [him]_IObj2 4 books. 
 
In order to determine the direction of transfer, we require some
classification of verbs. In particular, we classify each verb into one
of five classes: HAVE, GET, GIVE, CONSTRUCT and DESTROY. The HAVE
class consists of all verbs which signify the state of an entity, such
as “have”, “own”, etc. The GET class contains verbs which indicate
the gaining of things for the subject. Examples of such verbs are
“acquire”, “borrow”, etc. The GIVE class contains verbs which
indicate the loss of things for the subject.  Verbs like “lend”,
“give” belong to this class. Finally CONSTRUCT class constitutes
verbs indicating construction or creation, like “build”, “fill”,
etc., while DESTROY verbs indicate destruction related verbs like
“destroy”, “eat”, “use”, etc. This verb classification is
largely based on the work of <cit.>.

Finally, the declarative rules for this concept have the
following form:
[Verb1∈HAVE] ∧ [Verb2∈GIVE] 
∧ [(Subj1, IObj2)] ⇒Addition
where (A, B) is true when A and B represent the same
entity or are coreferent, and is false otherwise. In the examples
above, Verb1 is “own” and hence [Verb1∈HAVE] is
true. Verb2 is “give” and hence [Verb2∈GIVE] is
true. Finally, Subj1 and IObj2 both refer to Stephen, so
[(Subj1, IObj2)] returns true. As a result, the
above declarative rule dictates that addition should be performed
between 5 and 4.

We have 18 such inference rules for transfer, covering all
combinations of verb classes and () values. All these rules
generate addition or subtraction operations.



 §.§ Dimensional Analysis

We now look at the use of dimensional analysis knowledge in word
problem solving. To use dimensional analysis, one needs to extract the
units of numbers as well as the relations between the units. Consider
the following excerpt of a word problem: “Stephen has 5
bags. Each bag has 4 apples. Knowing that the unit of 5 is
“bag” and the effective unit of 4 is “apples per bag”, allows us
to infer that the numbers can be multiplied to obtain the total number
of apples.

To capture these dependencies, we first introduce a few
terms. Whenever a number has a unit of the form “A per B”, we refer
to “A” as the unit of the number, and refer to “B” as the
rate component of the number. In our example, the unit of 4 is
“apple”, and the rate component of 4 is “bag”. We define
variables Unit1 and Rate1 to denote the unit and the rate component of
the first number respectively. We similarly define Unit2 and
Rate2. For the above example, the assignment of variables are shown
below:
Stephen has 5 [bags]_Unit1. Each [bag]_Rate2 has 4
[apples]_Unit2.
Finally, the declarative rule applicable for our example has the
following form:
[(Unit1, Rate2)] ⇒Multiplication
We only have 3 rules for dimensional analysis. They generate
multiplication or division operations.




 §.§ Explicit Math

In this subsection, we want to capture the reasoning behind explicit
math relationships expressed in word problems such as the one
described in: “Stephen has 5 apples. Daniel has 4 more apples
than Stephen”. 






We define by Math1 and Math2 any explicit math term associated with
the first and second numbers respectively. As was the case for
transfers, we also define Subj1, IObj1, Subj2, and IObj2 to denote the
entities participating in the math relationship. The assignment of
these variables in our example is:
[Stephen]_Subj1 has 5 apples. [Daniel]_Subj2 has 4 [more
apples than]_Math2 [Stephen]_IObj2.

We classify explicit math terms into one of three classes - ADD, SUB
and MUL. ADD comprises terms for addition, like “more than”,
“taller than” and “heavier than”. SUB consists of terms for
subtraction like“less than”, “shorter than”, etc., and MUL
contains terms indicating multiplication, like “times”, “twice”
and “thrice”. Finally, the declarative rule that applies for our
example is:
[(Subj1, IObj2)] ∧ [Math2∈ADD]
⇒Addition
We have only 7 rules for explicit math.




 §.§ Part-Whole Relation

Understanding part-whole relationship entails understanding whether
two quantities are hyponym, hypernym or siblings (that is, co-hyponym,
or parts of the same quantity). For example, in the excerpt “Mrs. Hilt has 5 pecan pies and 4 apple pies”, determining that
pecan pies and apple pies are parts of all pies, helps inferring that
addition is needed. We have 3 simple rules which directly map from
Hyponym, Hypernym or Sibling detection to the corresponding math
operation. For the above example, the applicable declarative rule is:
[Sibling(Number1, Number2)] ⇒Addition

The rules for part-whole concept can generate addition and subtraction
operations. 



Table <ref> gives a list of all the declarative rules. 
Note that all the declarative rules are designed to determine an
operation between two numbers only. We introduce a strategy in
Section <ref>, which facilitates combining sub-expressions
with these rules.







§ MAPPING OF WORD PROBLEMS TO DECLARATIVE KNOWLEDGE



Given an input arithmetic word problem x, the goal is to predict the
math expression y, which generates the correct answer. In order to
derive the expression y from the word problem x, we leverage math
concepts and declarative rules that we introduced in Section
<ref>. In order to combine two numbers mentioned in x, we
first predict a concept k, and then we choose a declarative
knowledge rule r from k. The rule r generates the math operation
needed to combine the two numbers. Consider the first example in
Table <ref>. To combine 6 and 9, we first decide on
the transfer concept, and then choose an appropriate rule under
transfer to generate the operation.

Next we need to combine the sub-expression (6+9) with the number
3.  However, our inference rules were designed for the combination
of two numbers only. In order to combine a sub-expression, we choose
a representative number from the sub-expression, and use that
number to determine the operation. In our example, we choose the
number 6 as the representative number for (6+9), and decide the
operation between 6 and 3, following a similar procedure as
before. This operation is now used to combine (6+9) and 3.

The representative number for a sub-expression is chosen such
that it preserves the reasoning needed for the combination of this
sub-expression with other numbers. We follow a heuristic to
choose a representative number from a sub-expression:


  * For transfers and part-whole relationship, we choose the
  representative number of the left subtree.

  * In case of rate relationship, we choose the number which does
  not have a rate component.

  * In case of explicit math, we choose the number which is not
  directly associated with the explicit math expression.




 §.§ Scoring Answer Derivations


Given the input word problem x, the solution math expression y is
constructed by combining numbers in x with operations. We refer to
the set of operations used in an expression y as (y). Each
operation o in (y) is generated by first choosing a concept
k^o, and then selecting a declarative rule r^o from that concept.

In order to discriminate between multiple candidate solution
expressions of a word problem x, we score them using a linear 
model over features extracted from the derivation of the solution.
Our scoring function has the following form:

    (x, y) = ∑_o ∈(y) w_kϕ_k(x, k^o) + w_rϕ_r(x, r^o)
 
where ϕ_k(x, k^o) and ϕ_r(x, r^o) are feature vectors
related to concept k^o, and declarative rule r^o,
respectively, and w_k and w_r are the corresponding weight
vectors. The term w_kϕ_k(x, k^o) is the score for the selection
of k^o, and the term w_rϕ_r(x, r^o) is the score for the
selection of r^o. Finally, the total score is the sum of the scores
of all concepts and rule choices, over all operations of y.



 §.§ Learning


We wish to estimate the parameters of the weight vectors w_k and
w_r, such that our scoring function assigns a higher score to the
correct math expression, and a lower score to other competing math
expressions.  For learning the parameters, we assume access to word
problems paired with the correct math expression. We show in Section
<ref> that certain simple heuristics and rate component
annotations can be used to create somewhat noisy annotations for the
concepts needed for individual operations.  Hence, we will assume for
our formulation access to concept supervision as well. We thus assume
access to m examples of the following form: {(x_1, y_1, {k^o}_o
  ∈(y_1)), (x_2, y_2, {k^o}_o ∈(y_2)), …,
(x_m, y_m, {k^o}_o ∈(y_m)) }.

We do not have any supervision for declarative rule selection, which
we model as a latent variable.

Two Stage Learning: A straightforward solution for our
learning problem could be to jointly learn w_k and w_r using
latent structured SVM. However, we found that this model does not
perform well. Instead, we chose a two stage learning protocol. At the
first stage, we only learn w_r, the weight vector for scoring the
declarative rule choice. Once learned, we fix the parameters for
w_r, and then learn the parameters for w_k.

In order to learn the parameters for w_r, we solve:

    min_w_r1/2||w_r||^2 + C ∑_i=1^m ∑_o ∈(y_i)[ max_r̂∈ k^o, r̂⇒ô 
    w_r ·ϕ_r(x, r̂) + 
    Δ(ô, o) ] - 
    max_r̂∈ k^o, r̂⇒ o 
    w_r ·ϕ_r(x, r̂),

where r̂∈ k^o implies that r̂ is a declarative rule
for concept k^o, r̂⇒ o signify that the
declarative rule r̂ generates operation o, and
Δ(ô, o) represents a measure of dissimilarity between
operations o and ô. The above objective is similar to that
of latent structured SVM. For each operation o in the solution
expression y_i, the objective tries to minimize the difference
between the highest scoring rule from its concept k^o, and highest
scoring rule from k^o which explains or generates the operation o.

Next we fix the parameters of w_r, and solve:

    min_w_k1/2||w_k||^2 + C ∑_i=1^m 
                    
    max_y ∈𝒴[ (x_i, y) + Δ(y, y_i) ] 
    - (x_i, y_i).

This is equivalent to a standard structured SVM objective. We use a
0-1 loss for Δ(ô, o). Note that fixing the parameters
of w_r determines the scores for rule selection, removing the need
for any latent variables at this stage.




 §.§ Inference

Given an input word problem x, inferring the best math expression
involves computing max_y ∈𝒴(x, y), where
𝒴 is the set of all math expressions that can be created
by combining the numbers in x with basic math operations.

The size of 𝒴 is exponential in the number of quantities
mentioned in x. As a result, we perform approximate inference using
beam search. We initialize the beam with the set E of all numbers
mentioned in the problem x.  At each step of the beam search, we
choose two numbers (or sub-expressions) e_1 and e_2 from E, and
then select a math concept and a declarative rule to infer an
operation o. We create a new sub-expression e_3 by combining the
sub-expressions e_1 and e_2 with operation o. We finally create
a new set E' from E, by removing e_1 and e_2 from it, and
adding e_3 to it. We remove E from the beam, and add all such
modified sets E' to the beam. We continue this process until all
sets in the beam have only one element in them. We choose the highest
scoring expression among these elements as the solution expression.




§ MODEL AND IMPLEMENTATION DETAILS




 §.§ Supervision


Each word problem in our dataset is annotated with the solution math
expression, along with alignment of numbers from the problem to the
solution expression. In addition, we also have annotations for the
numbers which possess a rate component. An example is shown in Fig 
<ref>.

This is the same level of supervision used in <cit.>. Many of
the annotations can be extracted semi-automatically. The number list
is extracted automatically by a number detector, the alignments
require human supervision only when the same numeric value is
mentioned multiple times in the problem. Most of the rate component
annotations can also be extracted automatically, see <cit.> for
details.

We apply a few heuristics to obtain noisy annotations for the
math concepts for operations. Consider the case for combining two
numbers num1 and num2, by operation o. We apply the following rules:


  * If we detect an explicit math pattern in the neighborhood of
  num1 or num2, we assign concept k^o to be Explicit Math.

  * If o is multiplication or division, and one of num1 or num2
  has a rate component, we assign k^o to be Dimensional Analysis.

  * If o is addition or subtraction, we check if the dependent
  verb of both numbers are identical. If they are, we assign k^o to
  be Part-Whole relationship, otherwise, we assign it to be Transfer.
  We extract the dependent verb using the Stanford dependency parser
  <cit.>.

The annotations obtained via these rules are of course not perfect. We
could not detect certain uncommon rate patterns like “dividing the
cost 4 ways”, and “I read same number of books 4 days running”.
There were part-whole relationships exhibited with complementary
verbs, as in “I won 4 games, and lost 3.”. Both these cases lead
to noisy math concept annotations.

However, we tested a small sample of these annotations, and
found less than 5% of them to be wrong. As a result, we assume
these annotations to be correct in our problem formulation.



 §.§ Features

We use dependency parse labels and a small set of rules to extract
subject, indirect object, dependent verb, unit and rate component of
each number mentioned in the problem. Details of these extractions can
be found in the released codebase. Using these extractions, we define
two feature functions ϕ_k(x, k^o) and ϕ_r(x, r^o), where x
is the input word problem, and k^o and r^o are the concept and the
declarative rule for operation o respectively. ϕ_r(x, r^o)
constitutes the following features:


  * If r^o contains (·) function, we add features
  related to similarity of the arguments of (·) (jaccard
  similarity score and presence of pronoun in one of the arguments).

  * For part-whole relationships, we add indicators for a list of
  words like “remaining”, “rest”, “either”, “overall”,
  “total”, conjoined with the part-whole function in r^o 
  (Hyponymy, Hypernymy, Sibling).

  * Unigrams from the neighborhood of numbers being combined.

Finally, ϕ_k(x, k^o) generates the following features:


  * If k^o is related to dimensional analysis, we add features
  indicating the presence of a rate component in the combining
  numbers.

  * If k^o is part-whole, we add features indicating whether the
  verbs of combining numbers are identical.

Note that these features capture several interpretable functions like
coreference, hyponymy, etc.

We do not learn three components of our system – verb classification
for transfer knowledge, categorization of explicit math terms, and
irrelevant number detection. For verb classification, we use a seed
list of around 10 verbs for each category. Given a new verb v, we
choose the most similar verb v' from the seed lists according to
Glove vector <cit.> based similarity .  We assign v the
category of v'. This can be replaced by a learned component
<cit.>. However we found seed list based categorization to work
well in most cases. For explicit math, we check for a small list of
patterns to detect and categorize math terms. Note that for both the
cases above, we still have to learn (·) function to
determine the final operation. Finally, to detect irrelevant numbers
(numbers which are not used in the solution), we use a set of rules
based on the units of numbers. Again, this can be replaced by a
learned model <cit.>.




§ EXPERIMENTS




 §.§ Results on Existing Dataset

We first evaluate our approach on the existing datasets of AllArith,
AllArithLex, and AllArithTmpl <cit.>. AllArithLex and
AllArithTmpl are subsets of the AllArith dataset, created to test the
robustness to new vocabulary, and new equation forms respectively.  We
compare to the top performing systems for arithmetic word
problems. They are as follows:


  *  : Template based algebra word problem solver of
  <cit.>.

  * LCA++ : System of <cit.> based on lowest common
  ancestors of math expression trees.

  * : Unit dependency graph based solver of
  <cit.>.

  
We refer to our approach as . For all solvers, we use the
system released by the respective authors. The system of 
expects an equation as the answer, whereas our dataset contains only
math expressions. We converted expressions to equations by introducing
a single variable, and assigning the math expression to it.  For
example, an expression “(2 + 3)” gets converted to “X = (2 + 3)”.

The first few columns of Table <ref> shows the performance of
the systems on the aforementioned datasets[Results on the 
AllArith datasets are slightly different from <cit.>, since we 
fixed several ungrammatical sentences in the dataset]. The performance of
 is on par or lower than some of the existing systems.
We analyzed the systems, and found most of them to be not robust to
perturbations of the problem text; Table <ref> shows a few
examples. We further analyzed the datasets, and identified several
biases in the problems (in both train and test). Systems which
remember these biases get an undue advantage in evaluation. For
example, the verb “give” only appears with subtraction, and hence
the models are learning an erroneous correlation of “give” with
subtraction. Since the test also exhibit the same bias, these systems
get all the “give”-related questions correct.  However, they fail to
solve the problem in Table <ref>, where “give” results in
addition.



We also tested  on the addition subtraction problems
dataset released by <cit.>. It achieved a cross validation
accuracy of 77.19%, which is competitive with the state of the art
accuracy of 78% achieved with the same level of supervision. The
system of <cit.> achieved 86.07% accuracy on this
dataset, but requires rich annotations for formulas and alignment of
numbers to formulas.



 §.§ New Dataset Creation


In order to remove the aforementioned biases from the dataset, we
augment it with new word problems collected via a crowdsourcing
platform. These new word problems are created by perturbing the
original problems minimally, such that the answer is different from
the original problem. For each word problem p with an answer
expression a in our original dataset AllArith, we replace one
operation in a to create a new math expression a'. We ask
annotators to modify problem p minimally, such that a' is now the
solution to the modified word problem.

We create a' from a either by replacing an addition with
subtraction or vice versa, or by replacing multiplication with
division or vice versa. We do not replace addition and subtraction
with multiplication or division, since there might not be an easy
perturbation that supports this conversion. We only allowed perturbed
expressions which evaluate to values greater than 1. For example, we
generate the expression “(3+2)” from “(3-2)”, we generated
expressions “(10+2)/4” and “(10-2)*4” for the expression
“(10-2)/4”. We generate all possible perturbed expressions for a
given answer expression, and ask for problem text modification for
each one of them.

We show the annotators the original problem text p paired with a
perturbed answer a'. The instructions advised them to copy over the
given problem text, and modify it as little as possible so that the
given math expression is now the solution to this modified
problem. They were also instructed to not add or delete the numbers
mentioned in the problem. If the original problem mentions two
“3”s and one “2”, the modified problem should also contain two
“3”s and one “2”.

We manually pruned problems which did not yield the desired solution
a', or were too different from the input problem p.  This
procedure gave us a set of 661 new word problems, which we refer to
as Perturb. Finally we augment AllArith with the
problems of Perturb, and call this new dataset
Aggregate. Aggregate has a total of 1492 problems.

The addition of the Perturb problems ensures that the dataset
now has problems with similar lexical items generating different
answers. This minimizes the bias that we discussed in subsection
<ref>. To quantify this, consider the probability
distribution over operations for a quantity q, given that word w
is present in the neighborhood of q. For an unbiased dataset, you
will expect the entropy of this distribution to be high, since the
presence of a single word in a number neighborhood will seldom be
completely informative for the operation. We compute the average of
this entropy value over all numbers and neighborhood words in our
dataset.  AllArith and Perturb have an average entropy of 0.34 and
0.32 respectively, whereas Aggregate's average entropy is 0.54,
indicating that, indeed, the complete data set is significantly less
biased.



 §.§ Generalization from Biased Dataset

First, we evaluate the ability of systems to generalize from biased
datasets. We train all systems on AllArith, and test them on Perturb
(which was created by perturbing AllArith problems). The last column
of Table <ref> shows the performance of systems in this
setting.  outperforms all other systems in this setting
with around 19 % absolute improvement over . This shows
that declarative knowledge allows the system to learn the correct
abstractions, even from biased datasets. 




 §.§ Results on the New Dataset

Finally, we evaluate the systems on the Aggregate dataset. Following
previous work <cit.>, we compute two subsets of Aggregate
comprising 756 problems each, using the MAWPS <cit.>
system. The first, called AggregateLex, is one with low lexical
repetitions, and the second called AggregateTmpl is one with low
repetitions of equation forms. We also evaluate on these two subsets
on a 5-fold cross-valiation. Columns 4-6 of Table <ref> show
the performance of systems on this setting.  
significantly outperforms other systems on Aggregate and AggregateLex,
and is similar to  on AggregateTmpl. There is a 9 %
absolute improvement on AggregateLex, showing that  is
significantly more robust to low lexical overlap between train and
test. The last column of Table <ref> also shows that the
other systems do not learn the right abstraction, even when trained on
Aggregate.




 §.§ Analysis

Coverage of the Declarative Rules We chose math concepts and
declarative rules based on their prevalance in arithmetic word
problems. We found that the four concepts introduced in this paper
cover almost all the problems in our dataset; only missing 4
problems involving application of area formulas. We also checked
earlier arithmetic problem datasets from the works of
<cit.>, and found that the math concepts and
declarative rules introduced in this paper cover all their problems.

A major challenge in applying these concepts and rules to algebra word
problems is the use of variables in constructing equations. Variables
are often implicitly described, and it is difficult to extract units,
dependent verbs, associated subjects and objects for the variables.
However, we need these extractions in order to apply our declarative
rules to combine variables. There has been some work to extract
meaning of variables <cit.> in algebra word problems; an
extension of this can possibly support the application of rules in
algebra word problems. We leave this exploration to future work. 

Higher standard word problems often require application of math
formulas like ones related to area, interest, probability,
etc. Extending our approach to handle such problems will involve
encoding math formulas in terms of concepts and rules, as well as
adding concept specific features to the learned predictors. The
declarative rules under the Explicit Math category currently handles
simple cases, this set needs to be augmented to handle complex
number word problems found in algebra datasets.

Gains achieved by Declarative Rules
Table <ref> shows examples of problems which 
gets right, but  does not. The gains can be attributed to
the injection of declarative knowledge. Earlier systems
like  try to learn the reasoning required for these problems
from the data alone. This is often difficult in the presence of
limited data, and noisy output from NLP tools. In contrast, we learn
probabilistic models for interpretable functions like coreference,
hyponymy, etc., and then use declarative knowledge involving these
functions to perform reasoning. This considerably reduces the
complexity of the target function to be learnt, and hence we end up
with a more robust model.

Effect of Beam Size
We used a beam size of 1000 in all our experiments. However, we found
that varying the beam size does not effect the performance significantly.
Even lowering the beam size to 100 reduced performance by only 1%.

Weakness of Approach
A weakness of our method is the requirement to have all relevant
declarative knowledge during training.  Many of the component
functions (like coreference) are learnt through latent alignments with
no explicit annotations. If too many problems are not explained by the
knowledge, the model will learn noisy alignments for the component
functions.
 



Table <ref> shows the major categories of errors with
examples. 26% of the errors are due to extraneous number detection.
We use a set of rules based on units of numbers, to detect such
irrelevant numbers. As a result, we fail to detect numbers which are
irrelevant due to other factors, like associated entities, or
associated verb. We can potentially expand our rule based system to
detect those, or replace it by a learned module like
<cit.>. Another major source of errors is parsing of rate
components, that is, understanding “earns $46 cleaning a home”
should be normalized to “46$ per home”. Although we learn a model
for coreference function, we make several mistakes related to
coreference. For the example in Table <ref>, we fail to
detect the coreference between “team member” and “people”.







§ CONCLUSION


In this paper, we introduce a framework for incorporating declarative
knowledge in word problem solving. Our knowledge based approach
outperforms all other systems, and also learns better abstractions
from biased datasets. Given that the variability in text is much
larger than the number of declarative rules that governs Math word
problems, we believe that this is a good way to introduce Math
knowledge to a natural language understanding system. Consequently,
future










work will involve extending our approach to handle a wider
range of word problems, possibly by supporting better grounding of
implicit variables and including a larger number of math concepts and
declarative rules. An orthogonal exploration direction is to apply
these techniques to generate summaries of financial or sports news, or
generate statistics of war or gun violence deaths from news corpora. A
straightforward approach can be to augment news documents with a
question asking for the required information, and treating this
augmented news document as a math word problem.

Code and dataset are available at <https://github.com/CogComp/arithmetic>.




§ ACKNOWLEDGMENTS

This work is funded by DARPA under agreement number
FA8750-13-2-0008, and a grant from the Allen Institute for
Artificial Intelligence (allenai.org).



acl2012




