Quantity Tagger: A Latent-Variable Sequence Labeling Approach to Solving Addition-Subtraction Word Problems
August 31, 2019
Abstract
An arithmetic word problem typically includes a textual description containing several constant quantities. The key to solving the problem is to reveal the underlying mathematical relations (such as addition and subtraction) among quantities, and then generate equations to find solutions. This work presents a novel approach, Quantity Tagger, that automatically discovers such hidden relations by tagging each quantity with a sign corresponding to one type of mathematical operation. For each quantity, we assume there exists a latent, variable-sized quantity span surrounding the quantity token in the text, which conveys information useful for determining its sign. Empirical results show that our method achieves 5 and 8 points of accuracy gains on two datasets respectively, compared to prior approaches.
1 Introduction↩︎
Teaching machines to automatically solve arithmetic word problems, exemplified by two problems in Figure 1, is a long-standing Artificial Intelligence (AI) task [1], [2]. Recent research [3]–[8] focused on designing algorithms to automatically solve arithmetic word problems. One line of prior works designed rules [2], [3] or templates [4], [9], [10] to map problems to expressions, where rules or templates are collected from training data.
However, it would be non-trivial and expensive to acquire a general set of rules or templates. Furthermore, such approaches typically require additional annotations. The addition-subtraction problems, which constitute the most fundamental class of arithmetic word problems, have been the focus for many previous works [3], [10]. We also focus on this important task in this work. Our key observation is that essentially solving such a class of problems can be tackled from a sequence labeling perspective. This motivates us to build a novel sequence labeling approach, namely Quantity Tagger. The approach tags each quantity in the text with a label that indicates a specific mathematical operation.
Taking Problem 1 from Figure 1 as an example, three constant quantities “\({2}\)”,“\({7341}\)” and “\({4221}\)” sequentially appear in the problem text. We further introduce an unknown quantity \(x\) corresponding to the question sentence. From the problem description, one can form an equation “\(7341-4221-x=0\)", based on which we can obtain the solution to \(x\). This equation is mathematically equivalent to”\({\mathbb{0}\times}2+{(\mathbb{+1})\times}7341+{(\mathbb{-1})\times}4221+{\mathbb{(-1)}\times}x=0\)” where “\(\mathbb{0},\mathbb{+1},\mathbb{-1},\mathbb{-1}\)” are signs associated with the quantities “\(2,7341,4221,x\)”.
Solving arithmetic word problem can thus be casted as a sequence labeling problem where we assign every quantity appearing in the problem text a sign (in the form of a tag) from the set \(\{\mathbb{+1},\mathbb{0},\mathbb{-1}\}\). We further assume there exists a latent quantity span that needs to be learned – a sequence of words surrounding each quantity, based on which tagging decisions could be made.
We demonstrate through experiments on benchmark data that, despite its relatively simple assumptions involved, our novel sequence labeling approach is able to yield significantly better results than various state-of-the-art models. To the best of our knowledge, this is the first work that tackles the problem from a sequence labeling perspective. Our code is publicly available at https://github.com/zoezou2015/quantity_tagger.
2 Our Approach↩︎
2.1 A Tagging Problem↩︎
We define \(\mathbf{Q}\) = \((q_1, q_2, \dots, q_i, x, q_{i+1}, \cdots q_m)\) (0\(<\) \(i\) \(<\) \(m\), \(m\) \(\geq\)2 in arithmetic word problems) as an ordered quantity sequence for a problem text \(T\), where \(q_i \in \mathbf{Q}\) represents a constant quantity appearing in \(T\), and \(x\) stands for the unknown quantity assigned to the question sentence. \(\mathbf{Q}\) maintains the same order as the quantities appearing in \(T\). The goal is to construct a valid math equation \(E\). This research investigates such a problem by sequentially tagging each quantity \(q\in\mathbf{Q}\) with the most likely sign from set \(\mathcal{S}=\{\mathbb{+1},\mathbb{0},\mathbb{-1}\}\), where “\(\mathbb{+(-)1}\)" means a quantity is positively (negatively) related to the question, i.e., the sign of the quantity should be +(-) when forming part of the equation;”\(\mathbb{0}\)" means a quantity is irrelevant to the question and should be ignored.
Given a specific prediction of the signs to the quantities, we can form an equation as follows: \[\begin{align} \sum_{q_i \in \mathbf{Q}/\{x\}} s_iq_i + s_xx = 0 \end{align}\] where \(s_i \in \{\mathbb{+1},\mathbb{0},\mathbb{-1}\}\) is the sign for the \(i\)-th constant quantity \(q_i\), and \(s_x \in \{\mathbb{+1},\mathbb{-1}\}\) is the sign for \(x\). The solution can be easily obtained.
2.2 Quantity Tagger↩︎
Our primary assumption is that, for each quantity, there exists an implicit quantity span that resides in the problem text and can convey relevant information useful for determining the signs of the quantities. The quantity span of a quantity is essentially a contiguous token sequence from the problem text that consists of the quantity itself and some surrounding word tokens.
Formally, our model needs to learn how to sequentially assign each quantity \(q\in\mathbf{Q}\) its optimal sign \(s\in\mathcal{S}\). This is a sequence labeling problem [11], [12]. Common sequence labeling tasks, such as NER and POS tagging, mainly consider one sentence at a time, and tag each token in the sentence. However, our tagging problem typically involves multiple sentences where relatively unimportant information may be potentially included. For instance, the second sentence of Problem 2 in Figure 1, “Park workers will plant walnut trees today" describes background knowledge of the problem, but such information may not be useful for solving problems, yet even obstructive.
For each quantity \(q\in \mathbf{Q}\), we first consider a token window consisting of \(q\) and \(J-1\) surrounding tokens located immediately to the left and right of \(q\). This gives us a window of word tokens in the size of \(2J-1\). Next, such token windows for all quantities in \(\mathbf{Q}\) are merged to form a new token sequence, denoted as \(\boldsymbol{t}\). Note that \(\boldsymbol{t}\) is formed by concatenating token subsequences taken from \(T\) and is in the length of \(n\) (1\(\leq\) \(n\) \(\leq\) \(N\), where \(N\) is the length of \(T\)). We assume the quantity spans are defined over such a token sequence \(\boldsymbol{t}\) (rather than \(T\)), which we believe convey most relevant information for determining the signs for the quantities. Exemplified by Problem 2 in Figure 1, we show an example token sequence \(\boldsymbol{t}\) with \(J=3\) in Figure 2.
To capture quantity span information, we design 9 different labels with different semantics: \(\mathcal{H}\)={\(\mathbf{L}_\mathbf{+}\), \(\mathbf{L}_\mathbf{0}\), \(\mathbf{L}_\mathbf{-}\); \(\mathbf{N}_\mathbf{+}\), \(\mathbf{N}_\mathbf{0}\), \(\mathbf{N}_\mathbf{-}\); \(\mathbf{R}_\mathbf{+}\), \(\mathbf{R}_\mathbf{0}\), \(\mathbf{R}_\mathbf{-}\)}.
\(\bullet\)
The \(\mathbf{N}\) nodes are used to indicate that the current token is a quantity.
The \(\mathbf{L}\) (\(\mathbf{R}\)) nodes are used to indicate that the current token appears within a quantity span of a given quantity but to the left (right) of the quantity.
The subscripts “\(\mathbf{+}\)”, “\(\mathbf{0}\)”, and “\(\mathbf{-}\)” are used to denote the sign (\(\mathbb{+1}\), \(\mathbb{0}\) and \(\mathbb{-1}\) respectively) associated with the quantities (and quantity spans).
All quantities are explicitly given in the problem text. Therefore, the \(\mathbf{N}\) node is used to tag a word token if and only if the token represents a quantity. Otherwise, \(\mathbf{L}\) and \(\mathbf{R}\) nodes are considered. Furthermore, the unknown quantity is always relevant to the problem. We thus tag it with either \(\mathbf{N_\mathbf{+}}\) or \(\mathbf{N_\mathbf{-}}\), while three types of \(\mathbf{N}\) nodes are for all constant quantities. As illustrated in Figure 2, only one node from \(\mathcal{H}\) will be selected at each position. Sequentially connecting all such nodes will form a single path that reveals information about quantity spans selected for all quantities.
Following CRF [13], we formulate our method as a log-linear model with latent variables. Formally, given the problem text \(T\), let \(\boldsymbol{t} = (t_1,t_2,\dots,t_{n})\) be a token sequence as defined above, \(\boldsymbol{y}\) be the corresponding label sequence, and \(\boldsymbol{h}\) be a latent variable that provides specific quantity span information for the (\(\boldsymbol{t,y}\)) tuple, we define: \[\begin{align} p(\boldsymbol{y}|\boldsymbol{t}) = \frac{\sum_{\mathbf{h}}\exp(\mathbf{w}^T \mathbf{f}(\boldsymbol{t},\boldsymbol{y},\boldsymbol{h}))}{ \sum_{\boldsymbol{y'},\boldsymbol{h}'}\exp(\mathbf{w}^T \mathbf{f}(\boldsymbol{t},\boldsymbol{y'},\boldsymbol{h}'))} \end{align}\] where \(\mathbf{w}\) is the feature weight vector, i.e., model parameters, and \(\mathbf{f}\) is the feature vector defined over the triple (\(\boldsymbol{t,y,h}\)), \(\mathbf{f}(\boldsymbol{t},\boldsymbol{y},\boldsymbol{h})\) returns a list of discrete features (refer to supplementary materials).
During training, we would like to minimize the negative log-likelihood of the training set: \[\begin{align} &\mathcal{L}(\mathbf{w}) = \sum_{i}\log\sum_{\boldsymbol{y'},\boldsymbol{h'}}\exp{(\mathbf{w}_{f}^{T}\mathbf{f}(\boldsymbol{t}^{(i)},\boldsymbol{y'},\boldsymbol{h'}))} \notag \\ &-\sum_{i}\log\sum_{\boldsymbol{h}}\exp{(\mathbf{w}_{f}^{T}\mathbf{f}(\boldsymbol{t}^{(i)},\boldsymbol{y}^{(i)},\boldsymbol{h}))} \end{align}\] where the \((\boldsymbol{t}^{(i)},\boldsymbol{y}^{(i)})\) is the \(i\)-th training instance. The standard gradient-based methods can be used to optimize the above objective, such as L-BFGS [14]. Gradients of the above function is given by: \[\begin{align} &\frac{\partial\mathcal{L}(\mathbf{w})}{\partial w_{k}} = \sum_{i}\mathbf{E}_{p(\boldsymbol{y'},\boldsymbol{h}|\boldsymbol{t}^{(i)})}[f_k(\boldsymbol{t}^{(i)},\boldsymbol{y'},\boldsymbol{h})] \notag \\ &-\sum_{i}\mathbf{E}_{p(\boldsymbol{h}|\boldsymbol{t}^{(i)},\boldsymbol{y}^{(i)})}[f_k(\boldsymbol{t}^{(i)},\boldsymbol{y}^{(i)},\boldsymbol{h})] \end{align}\] where \(\mathbf{E}_p[\cdot]\) is the expectation under distribution \(p\).
We can construct a lattice representation on top of the nodes shown in Figure 2. The representation compactly encodes exponentially many paths, where each path corresponds to one possible label sequence. Note that there exists a topological ordering amongst all nodes. This allows us to apply a generalized forward-backward algorithm to perform exact marginal inference so as to calculate both objective and expectation values efficiently [15], [16]. The MAP inference procedure can be done analogously, which is called during the decoding time.
2.3 Model Variants↩︎
We further consider two variants of our model. Semi-Markov Variant: Our first variant, namely QT(s), employs the semi-Markov assumption [17], where \(\mathbf{N}\) nodes are removed. Different from QT which makes the first-order Markov assumption, QT(s) assumes \(\mathbf{L}\) and \(\mathbf{R}\) nodes are used to indicate the left and right boundaries of a quantity span respectively. Thus the model constructs edges (where non-Markovian features can be defined) by directly connecting the exactly first \(\mathbf{L}\) and the last \(\mathbf{R}\) nodes of a span.
Relaxed Variant: One assumption made by QT is: each word in \(\boldsymbol{t}\) strictly belongs to a certain quantity span. The variant QT(r) relaxes such a constraint. In this variant, some tokens in \(\boldsymbol{t}\) may not belong to any quantity spans. Considering the example shown in Figure 2, the token “There" in \(\boldsymbol{t}\) may not belong to any spans.
3 Experiments↩︎
We conduct experiments on two datasets, AddSub [3], consisting of 395 addition-subtraction problems in English, and AS_CN with 1,049 addition-subtraction problems in Chinese [6]. For all of our experiments, we use the L-BFGS algorithm [14] for learning model parameters with \(\ell2\) regularization coefficient of 0.01. To tune the hyperparameter \(J\), we randomly select \(80\%\) instances of the training set for training and the rest \(20\%\) for development. We tune \(J\) on the development set.
| Model | AddSub | AS_CN |
|---|---|---|
| [3] | 77.70 | - |
| [4] | 64.00 | - |
| [18] | 77.00 | - |
| [5] | 78.00 | 47.57 |
| [9] | 53.14 | 51.48 |
| [10] | 86.07 | - |
| [19] | 60.99 | 47.71 |
| [6] | - | 20.64 |
| [7] | 78.50 | - |
| QT(fix) | 87.73 | 53.19 |
| QT | 90.79 | 58.72 |
| QT(s) | 87.30 | 54.81 |
| QT(r) | 88.69 | 59.10 |
| QT(-ef) | 60.44 | 56.53 |
| QT(s-ef) | 63.49 | 52.62 |
| QT(r-ef) | 67.52 | 57.48 |
3.1 Analysis↩︎
Following standard evaluation procedures used in previous works [3], [10], we conduct 3-fold cross validation on AddSub and AS_CN, and report accuracies in Table 1. We make comparisons with a list of recent works1 and two baselines. Another is QT(fix) where the quantity span for each quantity is a fixed-size token window. All of our proposed models consistently outperform previous research efforts. These figures confirm the capability of our approach to provide more promising solutions to addition-subtraction problems. We do not require any additional annotations which can be expensive, while annotations like variable-word alignments and formulas are necessary for works of [4], [10].
To investigate the power of features extracted by external tools, such as ConceptNet [20] and Stanford CoreNLP tool [21], we conduct additional experiments on the afore-mentioned datasets, where we call such features external features (see supplementary material), indicated as “-ef". It is expected that the performance drops because such features are necessary for capturing evidence across sentences. Especially, for the AddSub dataset, it affects a lot. As discussed before [3], [10], there exists lots of irrelevant information and information gaps in AddSub. We thus can infer the external features support our approach to be capable of bridging information gaps and recognizing irrelevant information for solving arithmetic problems. Poor performance shows challenges to solve such problems in Chinese.
Which of our variants works the best? We observe that models with variable-sized quantity spans, namely QT, QT(s) and QT(r), generally perform better than QT(fix) where the quantity spans are fixed token windows. This shows the effectiveness of introducing the quantity span as a latent variable. QT obtains the highest average accuracy on the AddSub and QT(r) outperforms other two variants on the AS_CN.
| Model | AddSub | AS_CN | ||||||||
| \(A_{S.S.}\) | \(A_{M.S.}\) | \(F_{\mathbb{+}}\) | \(F_{\mathbb{0}}\) | \(F_{\mathbb{-}}\) | \(A_{S.S.}\) | \(A_{M.S.}\) | \(F_{\mathbb{+}}\) | \(F_{\mathbb{0}}\) | \(F_{\mathbb{-}}\) | |
| QT | 89.5 | 97.3 | 96.0 | 86.4 | 96.5 | 56.9 | 60.3 | 85.5 | 62.2 | 85.0 |
| QT(s) | 86.5 | 91.2 | 95.0 | 82.8 | 95.6 | 53.6 | 56.3 | 85.3 | 62.9 | 84.3 |
| QT(r) | 87.5 | 92.6 | 95.4 | 82.5 | 96.0 | 57.03 | 60.9 | 86.5 | 62.9 | 85.6 |
How does our approach perform on different types of problems? We divide problems into two categories: single-step and multi-step problems. The equation of a single-step problem contains at most two constant quantities tagged with either “\(\mathbb{+1}\)" or”\(\mathbb{-1}"\), while the equation for a multi-step problem has more than two constant quantities with signs of “\(\mathbb{+1}"\) or”\(\mathbb{-1}\)". We report accuracy and \(F1\) score in Table 2. According to empirical results illustrated in Table 2, our approach is able to give more accurate answers to multi-step problems, while the accuracy of single-step problems is lower. On the other hand, three models have similar patterns in terms of performance for three types of signs. The \(F1\) scores for signs of “\(\mathbb{+1}\)" and”\(\mathbb{-1}\)" are higher than scores of “\(\mathbb{0}\)". After examining outputs, we found that problem texts of single-step problems often contain more than two constant quantities, among which only two of them are supposed to be labeled as”\(\mathbb{+1}\)" or “\(\mathbb{-1}\)" and the rest should be tagged as”\(\mathbb{0}\)". However, incorrectly labeling an irrelevant quantity with “\(\mathbb{+1}\)" or”\(\mathbb{-1}\)" leads to wrong solutions to single-step problems. This also reveals that one main challenge for automatically solving arithmetic word problems is to recognize the irrelevant quantities. Failures in identifying irrelevant information may due to implicit information of problem text or the external tool issues.
Does \(J\) really matter? We further investigate the effects of \(J\) on the three proposed models. Figure 3 plots how performance varies with \(J\) (\(J\in\{1,2,3,4,5,6,N\}\)2) on datasets AddSub (above) and AS_CN (below). On AddSub, three models have similar patterns that performance tends to be worse with a larger \(J\). As for the AS_CN dataset, three models achieve relatively higher accuracies with \(J\in\{2,3,6\}\) compared to other scenarios. Interestingly, it seems that QT and QT(r) performs better than the semi-Markov variant QT(s). We tracked outputs from three models and found that QT(s) made more mistakes in predictions for unknown. The fact that models with \(J=N\) perform do not perform well confirms our assumption that taking token windows into account rather than the whole text is reasonable and effective.
Evaluation on different types of signs: We investigate the capability of proposed approach to predict three types of signs (\(\{\mathbb{+1,0,-1}\}\)), as illustrated in Table 3. Three models have similar patterns on two datasets. Predictions of “\(\mathbb{+1}\)" and”\(\mathbb{-1}\)" are more promising, compared to “\(\mathbb{0}\)". This reveals that one main challenge for automatically solving arithmetic word problems is to recognize the irrelevant information that should be labeled with”\(\mathbb{0}\)". Like what we discussed, failure on detecting irrelevant knowledge could be resulted from inevitably errors introduced by external resources and the lack of presence of crucial information in problem text.
Error Analysis The leading sources of errors can be categorized into three types: 1) The description of the problem is incomplete and implicit, which is challenging for machine to understand. 2) Failing in recognizing relevant quantities caused missing quantities or introducing irrelevant information. 3) Incomplete information or errors from external tools, such as ConceptNet [20] and Standford CoreNLP tool [21], are another source of errors leading to wrong predictions, which are inevitable.
| Model | AddSub | AS_CN | |||||
| \(P.\)\(\ast\) | \(R.\)\(\ast\) | \(F.\)\(\ast\) | \(P.\)\(\ast\) | \(R.\)\(\ast\) | \(F.\)\(\ast\) | ||
| QT | \(\mathbb{+}\) | 95.21\(\ast\) | 96.70\(\ast\) | 95.95\(\ast\) | 81.86\(\ast\) | 89.54\(\ast\) | 85.53\(\ast\) |
| \(\mathbb{0}\) | 88.88\(\dagger\) | 83.96\(\ast\) | 86.35\(\dagger\) | 75.83\(\ast\) | 52.74\(\ast\) | 62.21\(\ast\) | |
| \(\mathbb{-}\) | 96.65\(\ast\) | 96.38\(\star\) | 96.51\(\star\) | 88.17\(\ast\) | 82.04\(\ast\) | 84.99\(\ast\) | |
| QT(s) | \(\mathbb{+}\) | 93.97\(\ast\) | 96.01\(\ast\) | 94.98\(\ast\) | 80.74\(\ast\) | 90.30\(\ast\) | 85.26\(\ast\) |
| \(\mathbb{0}\) | 81.06\(\ast\) | 84.50\(\dagger\) | 82.75\(\ast\) | 75.00\(\ast\) | 54.22\(\dagger\) | 62.94\(\dagger\) | |
| \(\mathbb{-}\) | 96.97\(\ast\) | 94.18\(\ast\) | 95.55\(\ast\) | 88.66\(\star\) | 80.25\(\ast\) | 84.25\(\ast\) | |
| QT(r) | \(\mathbb{+}\) | 94.37\(\ast\) | 96.42\(\ast\) | 95.38\(\ast\) | 83.79\(\ast\) | 89.39\(\ast\) | 86.50\(\ast\) |
| \(\mathbb{0}\) | 80.55\(\ast\) | 84.50\(\dagger\) | 82.48\(\ast\) | 78.02\(\dagger\) | 52.72\(\ast\) | 62.92\(\ast\) | |
| \(\mathbb{-}\) | 97.48\(\star\) | 94.65\(\ast\) | 96.04\(\ast\) | 86.67\(\ast\) | 84.61\(\star\) | 85.63\(\star\) | |
4 Conclusion and Future Work↩︎
This work proposes the Quantity Tagger that regards solving addition-subtraction problem as a sequence labeling task by introducing the quantity span for each quantity. Despite its simplicity, it yields better performance. In the future, we would also like to investigate better models that are capable to address general arithmetic word problems, including addition, subtraction, multiplication and division.
Acknowledgments↩︎
We would like to thank the three anonymous reviewers for their thoughtful and constructive comments. We would also like to thank Yan Wang for his help on this work. This work is supported by Singapore Ministry of Education Academic Research Fund (AcRF) Tier 2 Project MOE2017-T2-1-156, and is partially supported by SUTD project PIE-SGP-AI-2018-01.