We study the task of an automatic evaluation of mathematical word problems, which belongs to the category of natural language processing and has become popular in recent years. Since all the so far published methods were developed for inputs in English, our goal is to review them and propose solutions able to cope with inputs in the Czech language. We face the question whether we can achieve a competitive accuracy for a natural language with flexible word order, and with the assumption that only a relatively small dataset of training and testing data is available. We propose and evaluate two methods. One relies on a rule-based processing of dependency trees computed by UDPipe. The other method builds on machine learning. It transforms word problems into numeric vectors and trains SVM to classify them. We also show that it improves in a combination with a search for predefined sequences of words and word classes, achieving 75% accuracy on our dataset of 500 Czech word problems.
The research in an automatic evaluation of mathematical word problems has nowadays a good practical motivation. This motivation comes from the fact that a natural language is the easiest way how many people can express themselves. Hence, it is useful to have methods that analyze assignments described by words, transform them into an internal representation, calculate results and present them in a descriptive form. This is exactly what is aimed by computational knowledge engines like WolframAlpha1. Mathematical word problems can be seen as one of the most complicated text assignments. Moreover, the complexity of translating a mathematical text into symbolic math scales with the difficulty of math involved in the problem solution. Hence, from a scientific point of view, word problems represent a very suitable domain for research.
The interest in automatic evaluation of word problems
dates back to 1963. It was identified in [
The survey [
The second approach relies on syntactic analysis.
Syntactic dependencies among words are used to extract
information from a given word problem. A disadvantage might
be a dependence on linguistic tools. System ARIS [
The most efficient approach is to apply machine
learning. Kushman et al. [
We can compare the accuracy of the methods since both
were evaluated on dataset Alg514 [
All the systems discussed above were developed for word problems in English. It is therefore natural to ask how the used principles would work for inputs in other languages, especially if the language is in some sense more difficult for analysis, for example, due to more flexible word order.
In this paper, we present a study of methods suitable for processing word problems in Czech, but we also present some new linguistically independent ideas. As no suitable annotated data has existed so far, it was necessary to build a new dataset. We have collected 500 word problems intended for the first three classes of elementary schools. These word problems can be solved by substituting numbers from the problem to an arithmetic expression. Hence, the problems are not so complex as some of those in Alg514 and Dolphin18K that also include problems whose solution requires to assemble and solve systems of equations. Nevertheless, we consider our dataset to be sufficient for an initial study, which can serve as a step towards methods processing more complex word problems. Furthermore, a solver working reliably on the considered domain might be appreciated by the youngest pupils, especially if there is a possibility to provide them a step by step explanation of how to solve a given problem. This should justify enough the focus of our research.
We touch all three principles discussed before and
propose two solvers. The first one is based on a support
vector machine (SVM) classifier and it is further extended
by incorporating the patterns-based classification to
handle some of the easier inputs. The advantage of this solver
is that it does not require any knowledge of semantic
(unlike the system from [
The collected dataset and implementation of the proposed methods are freely available2.
The content of the paper is structured as follows. Section 2 describes our dataset of 500 word problems in Czech. The next three sections describe and evaluate the proposed principles. Section 3 discusses how to extract and use patterns, Section 4 explains the use of SVM, Section 5 focuses on retrieving information from dependency trees produced by UDPipe. Finally, Section 6 summarizes the achieved results, gives additional thoughts on the presented methods and outlines possible future work. 2
We have created a dataset called WP500CZ comprising
of 500 word problems taken from the schoolbook [
Let us list four samples from the dataset, together with their English translations: W1 Jana má 4 pastelky nové a 3 pastelky staré. Kolik pastelek má Jana? (Jane has 4 new crayons and 3 old crayons. How many crayons does Jane have?) W2 Pavel má 120 Kcˇ. Ota má 80 Kcˇ. Kolik korun mají dohromady? (Paul has 120 CZK. Otto has 80 CZK. How many Czech korunas do they have together?) W3 Petr prˇecˇetl 9 knih. Eva prˇecˇetla 6 krát více knih.
Kolik knih Eva prˇecˇetla? (Peter read 9 books. Eve read 6 times more books.
How many books did Eve read?) W4 Maminka koupila 20 tvarohových kolácˇku˚ a 15 makových kolácˇku˚. Deˇti 8 kolácˇu˚ sneˇdly. Kolik kolácˇu˚ zu˚stalo? (Mom bought 20 cheesecakes and 15 poppy seed cakes. The children ate 8 cakes. How many cakes are left?)
Word problem W1 is represented in a text file as follows. Jana má 4 pastelky nové a 3 pastelky staré. Kolik pastelek má Jana? | 7 | NUM1 + NUM2
As it can be seen, there are three parts separated by the pipe characters. The first part is a word problem, the second part is the answer and the third part is the expression solving the problem. Variables in the expression are strings of the form NUMx where x is the order number of the referenced numeric value in the assignment.
Note that this approach has some limitations. For example, it does not allow to reference numbers expressed by words like day (has 24 hours) or June (has 30 days). However, our dataset does not contain word problems relaying on these translations of words to numbers.
A word problem itself consists of two parts – a word problem assignment (WPA-part) and a question (QUEpart). Each word problem in WP500CZ fulfills that its QUE-part is a simple sentence asking for one detail and the expression which gives the answer is exclusively composed of addition, subtraction, multiplication and division operations.
Task 1. Given a word problem W , the goal of an automatic word problem evaluation is to find an expression E solving W . 2https://github.com/hkad98/problem_solver Remark 1. We say that W is of type E. 160 140 120 100 80 60 40 20 0
Types of the word problem in WP500CZ and their frequencies are depicted in Figure 1.
As it can be seen, approximately one-third of the
instances are of type NUM1 + NUM2, one-third are of type
NUM1 NUM2, and the remaining instances are of 11
different types (note that these types include NUM2
NUM1, which is considered as a type different to NUM1
NUM2). This corresponds to the distribution of word
problem types in [
In this section, we describe a classification of word problems based on patterns extracted from a training dataset. This approach is able to handle reliably a subset of instances (we will show that the patters extracted from WP500CZ-train apply to 54% instances of WP500CZ-test). For this reason, we later combine the method with machine learning.
A pattern is a sequence of word lemmas and classes. Patterns are extracted from WPA-parts and QUE-parts separately and we call them WPA-patterns and QUEpatterns, respectively. Given a word problem W , it matches a WPA-pattern (QUE-pattern) P if the WPA-part (QUE-part) of W contains a subsequence of words whose lemmas/word classes are in the one-to-one correspondence with the elements of P, preserving the order of the elements.
To illustrate the form of patterns, we give two examples of WPA-patterns followed by two examples of QUEpatterns.
NOUN a NUM krát málo NOUN | NUM1 / NUM2 (NOUN and NUM times little NOUN) být o NUM NOUN vysoký | NUM1 + NUM2 (to be NUM NOUN high) kolik NOUN zbýt NOUN v NOUN | NUM1 - NUM2 (how many NOUN to left NOUN in NOUN) kolik NOUN NOUN zbýt | NUM1 - NUM2 (how many NOUN NOUN to left) Note that each line contains a pattern separated by the pipe character from the expression used for classification when the pattern is matched. In addition, NOUN and NUM in the pattern part represent word classes (noun and numeral).
We propose an algorithm which obtains the patterns automatically. Let us describe how it extracts e.g. WPApatterns. Let S1; : : : ; Sk be the partition of training dataset by word problem types (i.e., each Si consists of word problems of the same type). Maps P1; : : : ; Pk are allocated to collect the found patterns (stored as keys) and their number of occurrences (stored as values). All these maps are initially empty. In the end, each Pi contains patterns extracted from Si.
The algorithm has three phases. First, it process the subsets Si one by one. For each Si, it iterates through all pairs U;V 2 Si, U 6= V . Let u and v be the WPA-part of U and V , respectively. Moreover, for a sequence of words x = (x1; : : : ; xs), let `(x) be the sequence (x10; : : : ; xs0) where xi0 = ><>8 ANDOJUN iiff xxii iiss aannaodujne,ctive, > NUM if xi is a numeral, >: the lemma of xi otherwise.
A longest common subsequence of `(u) and `(v), denoted Pu;v, is found. If Pi does not yet contain Pu;v, the sequence is inserted to Pi and its number of occurrences is set to 1. If Pu;v is already in Pi, the number of occurrences of Pu;v is incremented.
In the second phase, the algorithm discards sequences that were not detected frequently. It iterates through sets Pi and deletes from Pi each sequence P for which the number of occurrences does not exceed t jPij where t 2 (0; 1) is a suitable constant.
Finally, the third phase of the algorithm discards every sequence P which is shared by two distinct sets Pi, P j.
In terms of the time complexity, the first phase is the
most demanding. Let us assume that the number of words
in the WPA-part as well as QUE-part of considered word
problems is at most N. Moreover, let S = Sik=1 Si.
Since the basic dynamic programming algorithm finding
the longest common subsequence for two sequences of
length at most N works in O N2 time [
k
N2 å jSij2
i=1
!
= O N2jS j2 :
When WPA-patterns are available, they are ordered into a
sequence PWPA = P1; : : : ; Pn which fulfills that a pattern
Pj is a proper subsequence of a pattern Pi if and only if
j > i. Analogously, the extracted QUE-patters are ordered
into a sequence PQUE with the same property. If a word
problem W with a WPA-part u and QUE-part v is given,
the pattern-based classification iterates through elements
of PQUE until it finds a pattern PQUE that matches u, or the
end of PQUE is reached. If PQUE is found, the
classification result is the expression assigned to PQUE. Otherwise
the algorithm iterates through PWPA and tries to find a
pattern PWPA matching v, which again determines the
classification result. No result is returned if PQUE neither PWPA
is found.
3.1
The described procedures work with lemmatized inputs.
We thus used corpus SYN2015 [
The proposed pattern extraction algorithm was implemented in Python 3. It returned 28 WPA-patterns and 8 QUE-patterns for instances in WP500CZ-train. The running time was 4.9 [s] on a notebook equipped with Intel(R) Core(TM) i5-5250U CPU @ 1.60GHz, 8GB RAM and MacOS.
Table 1 shows the efficiency of the subsequent patternbased classification. Three possible classification outcomes are distinguished – a correct classification, incorrect classification and no result when the classification algorithm does not return any expression.
The collected patterns were detected in nearly onehalf of the word problems in WP500CZ-test (115 out of 250). In those cases, the reliability of classification was quite high, achieving 93% accuracy (107 correct classifications). Interestingly, the accuracy was better than in the case of training data, however, there were fewer instances matching a pattern. 4
This section proposes a solver based on machine learning.
The main idea is to come up with a suitable
transformation of a word problem into a numeric vector of fixed
dimension (a so-called feature vector) and train a multi-class
support vector machine (SVM) [
We decided to use SVM because it is a classifier able to cope with high-dimensional data and it is not prone to overfitting. A flexibility is achieved through a kernel choice, which gives a possibility to linearly separate nonlinearly separable data by mapping them into a higher dimension. It also does not require a large dataset for training, unlike neural networks.
Our method of representing word problems by numeric vectors is semantic-independent. It is based on histograms of words occurring in word problems of the same type. For this purpose we define 1. a frequency function w(w; p; E) which for a word w in its canonical form, p 2 fWPA; QUEg and a word problem type E is equal to the number of word problems of type E in the training dataset that contain a word of the canonical form w in the p-part, and 2. a weight function a(c; p) which for a word class c and p 2 fWPA; QUEg is equal to an integer determining the importance of word class c in the classification process.
The values of the frequency function are calculated based on the training dataset. For example, we obtained the following values for verb mít (to have) and adverb dohromady (together) from WP500CZ-train: w(mít; WPA; NUM1 + NUM2) = 27 ; w(mít; QUE; NUM1 + NUM2) = 28 ; w(mít; WPA; NUM1 w(mít; QUE; NUM1
NUM2) = 25 ; NUM2) = 11 ; w(dohromady; WPA; NUM1 + NUM2) = 0 ; w(dohromady; QUE; NUM1 + NUM2) = 6 ; w(dohromady; WPA; NUM1 w(dohromady; QUE; NUM1 NUM2) = 0 ; NUM2) = 0 : (1) (2) (3) (4) (5) (6) (7) (8)
Values of the weight function were learned by a genetic algorithm, taking SVM accuracy as the objective function.
When the functions w and a are known, we transform a word problem W to a numeric vector x using the following algorithm.
1. Components of x are indexed by types of word problems in the training dataset (thus the vector dimension coincides with the number of SVM classes) and all of them are initially set to 0. 2. Words of W are taken one by one. Let the current word be of a lemma w and word class c. Moreover, let it be from a p-part of W . For each word problem type E, it is checked if w(w; p; E) is defined and the expression E evaluates to a non-negative integer after substituting the numeric values from W to E (i.e., E is feasible to W ). If true, then the E-component of x is increased by a(c; p) w(w; p; E).
Let us demonstrate how the frequencies (1)-(8) are used to calculate the numeric vector for word problem W1 in Section 2. For simplicity, assume that word problems in the training dataset are only of types NUM1 + NUM2 and NUM1 NUM2, and that a(c; p) = 1 for all c and p (i.e., we will ignore the weigh function).
First, we observe that both considered expressions evaluate to a positive integer when the numbers 4 and 3 from W1 are substituted for NUM1 and NUM2, respectively, hence both expressions are feasible to W1. Since the verb mít is in the WPA-part as well as QUE-part of W1, it contributes by frequencies (1) and (2) to vector component NUM1 + NUM2, and, analogously, by frequencies (3) and (4) to the component NUM1 NUM2. The adverb dohromady appears only in the QUE-part of W1, hence it contributes by frequency (6) to component NUM1 + NUM2 (note that frequency (7) is zero, hence it does not contribute to component NUM1 NUM2). If we sum the listed contributions, we obtain the vector fNUM1 + NUM2 : 61; NUM1 NUM2 : 36g : Remark 2. It is important to notice that the proposed form of vectors suggests to use a simple classifier which only finds a component of maximum value and returns the expression assigned to it. We will consider this strategy in the experimental part where it will be shown that it performs considerably worse than SVM.
As the testing data might have a different distribution than the training data, we normalize the vectors before passing them to SVM. For the SVM training stage, the normalization modifies the training set vectors so that the mean value is 0 and the variance is 1. The same transformation is applied to each input vector before it is classified.
Figure 2 shows a visualization of an SVM trained for word problems of types NUM1 + NUM2 and NUM1 NUM2. 4.1
In the next paragraphs we use the following abbreviations to denote the proposed solvers: sSVM is SVM-based solver, sMAX is the classifier suggested by Remark 2, sSVM+PAT is sSVM combined with the pattern matching, and sMAX+PAT is sMAX combined with the pattern matching. 0.5 0.0 0.5 1.0 1.5 2.0 Classes NUM1 - NUM2 NUM1 + NUM2 input 2.5 2.0 1.5 1.0 0.5 0.0 0.5 1.0
The combined solvers sSVM+PAT and sMAX+PAT try to apply the pattern matching first. If it does not return a result, then sSVM and sMAX is called to complete the classification.
We used scikit-learn3 library to implement sSVM. Radial basis function kernel was chosen as the best performing one among tested kernels.
The accuracy of the solvers can be compared in Table 2 and Table 3. The combined solver sSVM+PAT was the best solver on the testing dataset. In addition, the strategy of sMAX solver is inferior to the SVM classification.
WP500CZ-train WP500CZ-test sSVM 87.6% 61.1% sMAX 58.0% 51.0%
All instances of WP500CZ were evaluated in 3.66 [s] by sSVM+PAT and 3.15 [s] by sMAX+PAT (the running environment was identical to that one described in Subsection 3.1).
Figures 3 and 4 show distributions of errors per word problem type for sSVM+PAT (note that only word problem types present in the training dataset are considered). 3https://scikit-learn.org/stable/ 3 M U N 2 M U N + 1 M U N 3 M U N 2 M U N + 1 M U
N 2 M U N *1 M U N + 1 M U N 2 M U N 1 M U N + 1 M U N 2 M U N / 1 M U N + 1 M U N 2 M U N + 1 M U N 3 M U N + 2 M U N + 1 M U N 2 M U N 1 M U N 2 M U N / 1 M U N 3 M U N + 2 M U N 1 M U N 2 M U N 3 M U N 2 M U N 1 M U N / 2 M U N The so far presented solvers worked as classifiers but they were not suitable to be used for a step by step explanation of how to derive a solution to a given word problem. Here we give a high-level description of a method based on syntactic analysis, which creates an internal representation of the input problem. Although our current implementation of this method lags behind the SVM-based solver, we think that there is a room for improvements and it is thus worth to analyze causes of errors.
The method uses UDPipe (with Universal Dependencies 2.5 Models 2019-12-06) to process sentences of a given word problem. UDPipe returns information on word classes, sentence elements and their dependencies in CONNL-U format4. This information allows to construct a dependency tree.
We apply several algorithms working over the tree to retrieve structured information on entities encoded in the assignment. For each number N, it is extracted which entity E1 the number refers to and which entity E2 is the owner of E1.
Let us demonstrate it for the sentence:
Alenka si koupila 5 cˇokoládových bonbónu˚.
(Alice bought 5 chocolate candies.) 4https://universaldependencies.org/format.html phrases like 3 times more than by numbers, i.e., if applicable, it computes intermediate results and passes them to the next phases. 2. Structure creation phase connects numbers and entities. This is done by traversing the dependency tree from nodes representing numbers. When a structure is extracted, a vocabulary of verbs that represent a subtraction is used to adjust sign of the number (i.e., unlike in the previous methods, verbs semantic is taken into account here). 3. Evaluation phase checks the question part and guesses which entity E the word problem queries for. The answer is derived based on the extracted structures that relate to E. 5.1
To tune the method and to analyze errors encountered during testing, we considered only a subset of WP500CZ consisting of 150 word problem instances, denoted here as WP150CZ. The reason is that to analyze error types required a manual approach, it would, therefore, be too laborious to work with the entire dataset.
The method achieved 76% accuracy on the training part of WP150CZ (formed of 75 instances) and 67.1% accuracy on the testing part. However, the performance was much worse when the method was evaluated against all instances of WP500CZ (which took 23.5 [s]), solving correctly 41% of word problems. This indicates that WP500CZ is more diverse than WP150CZ and the rules designed based on WP150CZ are not general enough.
Table 4 shows detailed analysis of errors made by the method on WP150CZ. The analysis reveals that UDPipe itself is a non-negligible cause of errors since it often returns partially incorrect outputs and our method is not able to recover from these errors.
train test
UDPipe 7 9 preproc.
3 5 creation 5 9 eval.
3 1 total 18 24 Our paper is an initial study of an automatic evaluation of math word problems in Czech. We have reviewed the state-of-the-art methods for inputs in English and proposed three solvers, based on pattern matching, SVM and syntactic analysis. We also contributed by a dataset of 500 annotated word problems in Czech.
The main findings and new ideas of our work can be summarized as follows.
The pattern extraction is a less efficient approach when used as a standalone solver for word problems entered in a language with flexible word order. It is applicable only to a portion of inputs. However, we showed that it can be well used in a combination with other solvers since a matched pattern usually results in a correct classification. Another success is that we managed to implement a fully automatic pattern extraction.
A semantic-independent representation of word problems, considering only frequencies of words, turned out to be sufficient to obtain a relatively accurate classifier. The trained SVM performed better than the straightforward sMAX classifier. This might be interpreted as meaning that the SVM was able to find nontrivial relationships in the used features vectors. We have tested the suitability of existing linguistic tools for the studied task. The method based on syntactic analysis processed dependency trees produced by UDPipe. The method was not able to recover from errors occasionally done by UDPipe. Improving the accuracy of UDPipe is thus supposed to result in a higher accuracy of the method.
The accuracy of sSVM+PAT on WP500CZ (achieving
74.9%) was not too far from the accuracy of the
stateof-the-art solvers on Alg514 (achieving 70% or 82.5% by
methods from [
It must also be noted that WP500CZ is a small dataset (however, as we explained in the introduction, the problem has not been studied for non-English languages by others and there are no publicly available datasets of word problems for e.g. Slavic languages). A worse performance can be expected if sSVM+PAT is applied to larger and more diverse datasets. A broad expansion of the dataset and a creation of multilingual versions can, therefore, be identified as the goal of our further work. Except much more thorough testing, it would allow us to apply deep learning which is expected to improve the quality of the results.
In addition to our future plans, we also hope that the presented research can inspire others to consider non-English inputs for the studied problem.
We thank anonymous reviewers whose suggestions helped improve this paper. Our work was supported by the Czech Science Foundation grant no. 19-21198S.