A Goal-Oriented Meaning-based Statistical Multi-Step Math Word Problem Solver with Understanding, Reasoning and Explanation

1 Introduction

The math word problem (MWP) was frequently chosen to study the task of natural language understanding and simulate human problem solving procedure [Bakman, 2007; Kushman et al., 2014; Liang et al., 2016]. However, many previous approaches either only handled MWPs that involve one arithmetic operation [Mukherjee and Garain, 2008; Roy et al., 2015] or solved multi-step arithmetic operations with various limitations (e.g., only handling Addition and Subtraction sequence [Ma et al., 2010; Hosseini et al., 2014; Mitra and Baral, 2016]). Only [Roy and Roth, 2015] and [Koncel-Kedziorski et al., 2015] proposed bottom-up tree construction approaches to handle general multi-step arithmetic MWPs. But both of them lacked intermediate understanding and explanation. It thus belongs to the worse direct translation approach [Pape, 2004]. In contrary, previous goal-oriented approaches [Slagle, 1965; Ma et al., 2010] largely aligned with the human comprehension process, though they could not handle general cases and suffered from the difficulty of constructing a wide coverage rule-set.

A goal-oriented meaning-based statistical approach is thus proposed in this paper to avoid the problems mentioned above via combining the goal-oriented approach with a statistical framework. Except the ultimate goal, all the desired operations and operands (including sub-goals) will be identified by statistical classifiers. Moreover, each quantity is associated with various role-tags (e.g., nsubj, verb, modifier, time, place, etc.) for denoting its contextual relationship. Since the physical meaning (represented by role-tags) of each quantity is explicitly used in selecting both operations and operands, it allows us to examine the problem in an incremental and intuitive manner. In each step of the process, we know the meaning of the associated sub-goals/operands, and are thus able to explain the procedure in a human-comprehensible way [Mayer, 1987; 1992].

2 System Architecture

The block diagram of the proposed MWP solver is shown in Figure 1. The sentences in an MWP are first analyzed by the Language Analyzer (LA) (i.e., Stanford CoreNLP suite [Manning et al., 2014]) to obtain corresponding linguistic representation (i.e., dependency trees and co-reference chains). The Logic Form Converter (LFC) then transforms the linguistic representation into logic forms and constructs the final operation tree. Besides, the LFC also calls the Solution Type Classifier (STC) to determine the solution type and calls the Inference Engine (IE) [Liang et al., 2016] to evaluate the given operation tree and generate the answer for the question. Lastly, the Explanation Generator (EG) [Huang et al., 2015] generates the explanation text to explain how the answer is obtained according to the given reasoning chain.

We adopt the same STC, IE and EG modules used in [Liang et al., 2016], and only describe new modules below.

2.1 Logical Form Converter

The LFC transforms each quantity into its first-order logic form [Lin et al., 2015; Russell and Norvig, 2009]. All quantities and the main-goal are first identified by rules and explicitly associated with their role-tags, which carries context information and specifies the physical meaning of that quantity. For example, "quan(q1,#,apple)=3 & verb(q1, eat) & nsub(q1, Mary)" is generated to state 'Mary ate 3 apples'. In contrast with the bottom up approach adopted in [Roy and Roth, 2015; Koncel-Kedziorski et al., 2015], the LFC constructs the operation tree [Roy and Roth, 2015] in a top-down manner. It initializes a recursive procedure by first pushing the main-goal into a stack. Afterwards, it pops the current working goal from the stack, and then asks the STC to decide the desired solution type (i.e., the operator) associated with the goal. It then generates all possible candidates of sub-goals (via the rule-based Sub-goal Candidates Generator sub-module), and selects associated operands (via the statistical Operands Identifier sub-module) among all available known quantities and those sub-goal candidates just generated. Afterwards, it spawns a new level of recursion if the selected operand is an unknown quantity (i.e., a sub-goal candidate generated above), which will be regarded as a new sub-goal and pushed into the stack. The above procedure will keep going until the stack is empty. Lastly, the LFC identifies the corresponding IE utility (associated with the solution type), and calls the IE to get the answer.

2.2 Operands Identifier

The Operand Identifier selects the appropriate operands from the Operand-Candidate-Set, which is a set formed by newly generated sub-goals and currently available known quantities. An SVM classifier with linear kernel [Chang and Lin, 2011] is used. We adopt three different kinds of features: (1) Math fact pattern features (e.g., "if the operand is a known quantity", etc.); (2) NP-matching features (e.g., "if the noun-phrases of the operand-candidate and the goal are in entailment relationship", etc.); (3) Role-tag-matching features (e.g. "if the role-tags of operand-candidate and that of goal are matched", etc.).

3 Experimental Results

We evaluate our system on two publicly available datasets: IL-562 and CC-600. IL-562 is a collection of 562 MWPs (with single arithmetic operation) released by [Roy et al., 2015]. CC-600 is a dataset of 600 MWPs released by [Roy and Roth, 2015] to cover multi-step MWPs with four different arithmetic operations. We compare our system with the KAZB [Kushman et al., 2014] and the system proposed by [Roy and Roth, 2015]. Since exactly the same n-fold cross-validation evaluation setting is adopted, the performances can be directly compared. Table 1 shows that our system significantly outperforms theirs in overall performance. We believe the improvement is mainly due to

Answer and Explanation:

3 apples vs. 1 apple is: 3 ÷ 1 = 3-times

3-times and 20 USDs is: 3 * 20 = 60 USDs

2 oranges vs. 1 orange is: 2 ÷ 1 = 2-times

2-times and 12 USDs is: 2 * 12 = 24 USDs

60 USDs - 24 USDs = 36 USDs

• ∴ 3 apples cost 36 USDs more expensive than 2 oranges.

Figure 2: The reasoning chain and explanation text

that the system explicitly checks the physical meaning of the selected quantities against the meaning of the given sub-goal.

4 Demonstration Outline

The MWP solver comprises a web user interface and a processing server. The web interface is used to input the problem and display various outputs generated from the submitted MWP. The server will process the submitted problem to get the answer. After an MWP is submitted, various processing modules will be invoked in a recursion manner to solve the problem. Once the process is finished, the user can browse the outputs generated from each module: (1) Dependency relations, co-reference chains and linguistic representations generated from the LA. (2) Logic forms transformed from the linguistic representation and the specified solution type. (3) Reasoning chain and explanation text (Figure 2), which explains how the problem is solved. An online demo is available via the following web address: http://nlul.iis.sinica.edu.tw/EnglishMathSolver/mathDemo MS.py.

5 Conclusion

A goal-oriented meaning-based statistical framework is proposed to solve multi-step MWPs in a top-down, recursive manner. The approach resembles the human cognitive understanding of math word problems, and thus allows us to provide an intuitive human-comprehensible explanation to the problem-solving process.