Neural Symbolic Reader: Scalable Integration of Distributed and Symbolic Representations for Reading Comprehension
Authors: Xinyun Chen
Chen Liang
Adams Wei Yu
Denny Zhou
Dawn Song
Quoc V. Le
Venue:  (2020)
Keywords: neural symbolic
reading comprehension
question answering

Abstract: Integrating distributed representations with symbolic operations is essential for reading comprehension requiring complex reasoning, such as counting, sorting and arithmetics, but most existing approaches are hard to scale to more domains or more complex reasoning. In this work, we propose the Neural Symbolic Reader (NeRd), which includes a reader, e.g., BERT, to encode the passage and question, and a programmer, e.g., LSTM, to generate a program that is executed to produce the answer. Compared to previous works, NeRd is more scalable in two aspects: (1) domain-agnostic, i.e., the same neural architecture works for different domains; (2) compositional, i.e., when needed, complex programs can be generated by recursively applying the predefined operators, which become executable and interpretable representations for more complex reasoning. Furthermore, to overcome the challenge of training NeRd with weak supervision, we apply data augmentation techniques and hard Expectation-Maximization (EM) with thresholding. On DROP, a challenging reading comprehension dataset that requires discrete reasoning, NeRd achieves 1.37%/1.18% absolute improvement over the state-of-the-art on EM/F1 metrics. With the same architecture, NeRd significantly outperforms the baselines on MathQA, a math problem benchmark that requires multiple steps of reasoning, by 25.5% absolute increment on accuracy when trained on all the annotated programs. More importantly, NeRd still beats the baselines even when only 20% of the program annotations are given.

Published as a conference paper at ICLR 2020
NEURAL SYMBOLIC READER: SCALABLE INTEGRA- TION OF DISTRIBUTED AND SYMBOLIC REPRESENTA- TIONS FOR READING COMPREHENSION
Xinyun Chen
Chen Liang, Adams Wei Yu, Denny Zhou
UC Berkeley xinyun. wta.yynn.ccetbbbeeee..yooo edu
Google Brain
(crazydonkey, adamsyuwei, demnyyhoa)@oooggl.......
Dawn Song
Quoc V. Le
UC Berkeley manssongess.bereeeey..
Google Brain
gvlegoogle.com
ABSTRACT
Integrating distributed representations with symbolic operations is essential for reading comprehension requiring complex reasoning, such as counting, sorting and arithmetics, but most existing approaches rely specialized neural modules and are hard to adapt to multiple domains or multi-step reasoning. this work, we propose the Neural Symbolic Reader (NeRd), which includes reader, e.g.. BERT, to encode the passage and question, and a programmer, e.g., LSTM, to generate program for multi-step reasoning. By using operators like span selec- tion, the program can be executed over text to generate the answer. Compared to previous works. NeRd is more scalable in two aspects: (I) domain-agnostic i.e., the same neural architecture works for different domains; (2) compositional, i.e., complex programs can generated by compositionally applying the sym- bolic operators. Furthermore, to overcome the challenge of training NeRd with weak supervision, we apply data augmentation techniques and hard Expectation- Maximization (EM) with thresholding. On DROP, challenging reading com- prehension dataset requiring discrete reasoning. NeRd achieves 1.37% 18% ab- solute gain over the state-of-the-art architecture, NeRd significantly outperforms the baselines on MathQA, a math problem benchmark that requires multiple steps of reasoning, by 25.5% absolute gain on accuracy when trained on all the annotated programs, and more impor- tantly, still beats the baselines even with only 20% of the program annotations.
Exact-MatchFF1 metrics. With the
INTRODUCTION
Deep neural networks have achieved remarkable successes in natural language processing recently. In particular, pretrained language models, e.g., BERT (Devlin et al., 2019), have significantly ad- vanced the state-of-the-art in reading comprehension. While neural models have demonstrated per- formance superior humans on some benchmarks, e.g., SQuAD (Rajpurkar al. 2016), so far such progress is mostly limited to extractive question answering, in which the answer is a single span from the text. In other words, this type of benchmarks usually test the capability of text pattern matching, but not of reasoning. Some recent datasets, e.g., DROP (Dua et al. 2019) and MathQA (Amini et al., 2019), are collected to examine the capability of both language understanding and discrete reason- ing, where the direct application of the state-of-the- art pre-trained language models, such as BERT or QANet (Yu et al.) 2018), achieves very low accuracy. This especially challenging for pure neu- ral network approaches, because discrete operators learned by neural networks, such addition and sorting, can hardly generalize to inputs of arbitrary size without specialized design (Reed & de Fre- Cai et al. 2017 Kaiser & Sutskever 2015). Therefore, integrating neural networks with symbolic reasoning is crucial for solving those new tasks.
itas 2016
Liang al.) 2017 is sparked to address this problem. However, such success is mainly restricted to question answering with structured data sources, e.g., knowledge graphs (Berant al. 2013) or tabular databases (Pasupat
The recent progress neural semantic parsing (Jia & Liang 2016
Work was done while interning Google Brain.

---

Published as a conference paper at ICLR 2020
Answer
Answer
Answer
Execution
Execution
Compositional
Compositional Programs
Programs
Add/Sub
Count
Span
Neural
Structured table
Programmer
Answer Type
Negation
Semantic
Parser
Reader
Reader
Structured Parser: SAL...
Passage
Question
Passage
Question
Passage
Question
NeRd
Specialized Modules
Neural Semantic Parser
Figure 1: Comparison of NeRd with previous approaches for reading comprehension requiring com- plex reasoning. The components in grey boxes are the neural architectures. Previous works mainly take two approaches: (I) augmenting pre-trained language model such BERT with specialized modules for each type of questions, which is hard to scale to multiple domains or multi-step complex reasoning; (2) applying neural semantic parser to the structured parses of the passage. which suffers severely from the cascade error. In contrast, the neural architecture of NeRd is domain-agnostic, which includes reader, e.g., BERT, and programmer, e.g., LSTM, to generate compositional programs that are directly executed over the passages.
Extending it to reading comprehension by parsing the text into structured repre- sentations suffers severely from the cascade errors, i.e., the issues the structured parsing for data preprocessing account for the poor performance of the learned neural model Duua et al. 2019).
& Liang 2015).
recent line of work (Dua al. 2019 Hu et al. 2019 Andor al. 2019) extends BERT/Q to perform reasoning on the DROP dataset. However, they cannot easily scale to multiple domains or multi-step complex reasoning because: (1) they usually rely on handcrafted and specialized modules for each type of questions; (2) they don't support compositional applications of the operators, so it hard to perform reasoning of more than one step.
In this work, we propose the Neural Symbolic Reader (NeRd) for reading comprehension, which consists of (1) a reader that encodes passages and questions into vector representations; and (2) programmer that generates programs, which are executed to produce answers. The key insights behind NeRd are as follows: (1) by introducing a set of span selection operators, the compositional programs, usually executed against structured data such as databases in semantic parsing, can now be executed over text; (2) the same architecture can be applied to different domains by simply extending the of symbolic operators.
main challenge of training NeRd is that it is often expensive to collect program annotations, so the model needs to learn from weak supervision, i.c., with access only the final answers. This raises two problems for learning: (1) cold start problem. There are no programs available at the beginning of training, so the training cannot proceed. We address this problem through data augmentation that generates noisy training data to bootstrap the training; (2) spurious program problem, where some programs produce the right answer for wrong rationales. We propose an iterative process using hard EM with thresholding, which filters out the spurious programs during training.
In our evaluation, NeRd demonstrates three major advantages over previous methods: (1) better ac- curacy. It outperforms the previous state-of-the--rt on DROP by 1.37% on EM/F1, and the baselines on MathQA by large margin of 25.5% on accuracy if trained with all annotated programs. Notably, it still outperforms the MathQA baselines using only 20% of the program annotations; (2) more scalable coomain-agnosti and compositional). Unlike previous approaches, which rely on specialized modules that do not support compositional application of the operators, NeRd can be applicd to tasks of different domains, e.g., DROP and MathQA, without changing the architecture, and more complex programs be simply generated by extending the set of operators and compo-
2

---

Published as a conference paper at ICLR 2020
sitionally applying them; (3) better interpretabilityy. It is easier to interpret and verify answer by inspecting the program that produces it, especially for the questions involving complex reasoning such counting and sorting.
2 NEURAL SYMBOLIC READER
In this section, we present the design of NeRd. It consists of reader that encodes the passages and questions into vector representations, and a programmer that generates programs in a domain spe- cific language. The overall comparison between NeRd and previous works is visualized in Figure
2.1 NEURAL ARCHITECTURE
We provide overview of the two components in NeRd, and defer more details to Appendix C
Reader. Given the natural language text including question and a passage, the reader component encodes each token 4; in the text into an embedding eq. Note that our framework is agnostic to the architecture choice of the encoder, so any neural module that turns words into vectors applicable, e.g., BERT (Devlin et al. 2019).
Programmer. The programmer takes the output of the reader as input, and then decodes a program as a sequence of tokens. Again, our model is agnostic to the design of decoder. For simplicity, we use an LSTM (Hochreiter & Schmidhuber (997) decoder with attention (Bahdanau al. 2014) over the encoded text, and self-attention (aswwan et al. (017) over the previously generated tokens.
A major advantage of our architecture is that it is domain-agnostic, i.e., the same architecture can be used for different domains. Compared to previous approaches that craft separate specialized modules for each answer type, we use unified programmer component to generate programs for multi-step reasoning, and we can simply extend the operator set in the domain specific language (see the next section) to adapt to different domain. See Section 4.3 for more detailed discussion.
2.2 DOMAIN SPECIFIC LANGUAGE
In this section, we introduce our domain specific language (DSL., which used to interpret the tokens generated by the programmer component as executable program.
We list the operators in our DSL in Table T To handle discrete reasoning, the DSL includes operators that perform arithmetics (DIFF, SUM), counting (COUNT) and sorting (ARGMAX, ARGMIN, MAX, MIN). These operators have been used in previous work in semantic parsing over structured data sources such knowledge graph or a tabular database.
However, the main challenge of applying such operations for reading comprehension is that the model needs to manipulate unstructured data, i.c., natural language text, and parsing the text into structured representations may introduce a lot cascade errors. For example, Dua et al. (2019) found that their best performing semantic parsing pipeline using SRL (Carreras & Mårquez 2004) can only find the logical forms for 35% of the questions, resulting in poor performance.
To address this issue, key insight in DSL design is to introduce the span selection operators, so that all the arithmetics, counting and sorting operators can be applied to text. Specifically, we introduce PASSAGE_ PASSAGE_SPAN, SPAN, QUESTION_SPAAT SPAN, VALUE, KEY-VALUE for selecting spans or numbers from the passage and question. For example, COUNT can use PASSAGE SPAN to pick out the spans that mention the relevant entities or events, c.g., touchdowns made by a certain person, and then returns the total number; ARGMAX relies on applying KEY-VALL to pick out the spans (keys) for relevant mentions and their associated numbers (values), e.g., touchdowns and their lengths, and then returns the key with the highest value, e.g., the player kicking the longest touchdown. More examples can be found Table 2 In summary, the introduction of span selection operators in the DSL enables the application of the discrete reasoning operators to text, and the resulting programs act as executable and interpretable representations of the reasoning process.
As mentioned above, our architecture is domain-agnostic and the only change needed, apply to a different domain, is to extend the DSL with new operators. For example, MathQA benchmark requires adding more advanced mathematical operations beyond addition and subtraction, which are defined in Amini et al. (2019). We defer the details to Section 4.1
A major advantage of our DSL is its compositiinalltyy i.e., complex programs can be generated by compositionally applying the operators. Previous works (Andor et al. 2019) only allow applying the operators for one step, which requires them introduce operators mimic two-step compositions,
3

---

Published as a conference paper at ICLR 2020
Operator
Arguments
Outputs
Description
PASSAGE SPAN
v0: the start index.
span.
Select a span from the passage or question.
QUESTION_SPAL
vI: the end index.
VALUE
v0: an index.
number.
Select a number from the passage.
KEY-VALUE (KV)
v0: span.
key-value pair.
Select a key (span) value (number) pair from the passage.
vI: number.
DIFF
v0: number index.
a number.
Compute the difference sum of two numbers.
SUM
v1: a number or index.
COUNT
set of spans.
number.
Count the number of given spans.
MAX
v: set of numbers.
a number.
Select the maximum minimum among the given numbers.
MIN
ARGMAX v: set of key-value pairs.
a span.
Select the key (span) with the highest lowest value.
ARGMIN
Table 1: Overview of our domain-speciin language. See Table 2 for the sample usage.
e.g., Merge (selecting two spans) and Sum3 (summing up three numbers). However, this would not scale to more steps of reasoning, as the number of required operators will grow exponentially w.r.t the number of steps. In contrast, NeRd can compose different operators to synthesize complex programs for multi-step reasoning. For example, on MathQA, the average number of operations per question is 5, and some programs apply more than 30 operations compute the final answer.
TRAINING WITH WEAK SUPERVISION
Although it is relatively easy to collect question-ansee answer pairs, is often hard and expensive to obtain program annotations that represent the reasoning behind the answers. Thus, how to train NeRd with only weak supervision becomes a main challenge. In this section, we revisit the cold start and spurious program problems described in Section and present our solutions.
3.1 DATA AUGMENTATION FOR COLD START
The cold start problem means that the training cannot get started when there isn't any program available. For example, a question "How many touchdowns did Brady throw" annotated with only an answer "3" cannot be directly used to train our model due the lack of the target program to optimize on. To obtain program annotations from question-answer pairs, we first follow previous work find programs for questions answerable by span selection arithmetic operations via an exhaustive search, and we defer the details to Section 4.2 However, for questions involving counting or sorting operations, the space becomes too large for an exhaustive search, since these operations rely on the span selection as their sub-routines. For example, the number of possible spans in text with 200 words is in the order of 10 and what's more, counting and sorting operators usually include more than one span as their arguments.
We apply data augmentation to address the search space explosion problem for counting and sorting operations. For counting, we augment the span selection questions by replacing the interrogatives, e.g., "what" and "who", with "how many" when applicable, and adding a call to COUNT over the selected spans in the answer. For example, question "What areas have Muslim population of more than 50000 people?" is changed into "How many areas..." For sorting, we extract the key-value pairs by first applying CoreNIP (Manning al., 2014) for entity recognition, and then heuristically find an associated number for each entity. If including them as the arguments of any sorting operator yields the correct answer, then such programs are added the training set. More details can be found in Appendix D.I] Although the programs found for counting and sorting through this data augmentation process is noisy, they help bootstrap the training. Throughout the training, we also use the model to decode programs, and add those leading to correct answers into our training set.
3.2 HARD EM WITH TIRESIOOLDING AGAINST SPURIOUS PROGRAMS
After collecting a set of programs for each question-answer pair, another obstacle is the spurious program problem, the phenomenon that wrong program accidentally predicts right answer. For example, per arithmetic question in DROP, there are on average 9.8 programs that return correct answers, but usually only one of them is semantically correct.
4

---

Published as a conference paper at ICLR 2020
Algorithm 1 Hard EM with Thresholding
To filter out spurious programs, adopt hard EM (Liang et al. 2018 Min et al. 2019) due to its simplicity and efficiency. Specifically, this approach uses the current model to select the program with the high- est model probability among the ones that return the correct answer, and then max- imizes the likelihood of the selected pro- gram. In other words, it relies on the neu- ral model itself to filter out spurious pro- grams. This algorithm is usually faster than the marginalized approach (Berant et al., 2013) because at most one program per question-answer pair is used to com- pute the gradient, and the selection process is fast since it only has forward pass.
Input: question-answer pairs {(rs, M/k yi))
model pe, initial threshold cro, decay factor y for each (Iz, y1) do
Zi < DataAugmentation((r. Bi)
T T+-0 0 repeat
a + 0g * *77
D + 0
for each (Ia, yi) do
2 arr m po po(= (0([(100)) (x)), 2 E Z₁
if (x() ) > a or = 0 and |Z,| = 1 then
D 2-77 DDD (xi, 2
Update by maximizing En log pa (=
T + 1
until converge or early stop
Hard EM assumes that for any question- answer pair, at least one of the generated programs is correct. However, there exist questions with- out any semantically correct program found, e.g., when the annotated answer itself is wrong. In this case, when directly applying the hard EM algorithm, even if the model probabilities for all the programs are very small, it will still select a program for training. RL-based approaches such as MAPO iiang et al. 2018) avoid this issue by optimizing the expected return, which weighs the gradient by the model probability. Thus, when all the programs of a question-anse answer pair have very small probabilities, they will be largely ignored during training. We incorporate this intuition into hard EM by introducing a decaying threshold a in order to be included for training. Our experiments show that both hard EM and threshold- ing crucial for successful training. The pseudo-code of our training procedure is presented in Algorithm [ and we defer more details to Appendix
that program's probability has to be at least
D.2 D.2
EVALUATION
In this section, we demonstrate the effectiveness of our approach on DROP (Dua el al. 2019) and MathQA (Amini et al. 2019), two recent benchmarks that require discrete reasoning over passages.
4.1 DATASETS
DROP. DROP (Discrete Reasoning Over Paragraphs) (Dua et al. 2019) is designed to combine the challenges from both reading comprehension and semantic parsing communities. Specifically, the passages are collected from Wikipedia, each having at least twenty numbers. The question-answe answer pairs are crowdsourced in an adversarial way that they are accepted only when the questions cannot be correctly answered by the BiDAF model (Seo et al.) 2017). The dataset has 96.6K question- answer pairs from 6.7K passages. Unlike most existing datasets that are solely based on the single span selection, the questions in DROP require complex reasoning, such selecting multiple spans, arithmetic operations over numbers in the passage, counting and sorting, etc., which poses extra challenge for existing models. For example, vanilla BERT only gets around 30% Fl score. Table 2 provides some sample questions in DROP, and their corresponding programs in our DSL (Table
For evaluation, we use the same metrics in Dua is if the prediction exactly matches the ground truth, and 0 otherwise; (2) Fl score, which gives partial credits to a prediction that is not exactly the same as the ground truth, but overlaps with it.
2019): (1) Exact Match (EM), where the score
MathQA. MathQA (Amini et al. 2019) is dataset with 37K question- question-answer answer pairs selected from AQuA (Ling et al. 2017). but it is further annotated with gold programs their camain-speciffe language. The passage length in MathQA is 38 on average, much shorter than DROP with 224. However, the questions in MathQA require more complex and advanced mathematical reasoning than DROP. To this aim, they design 58 math operations, which cover various advanced math topics including geometry. physics, probability, etc. Accordingly, we augment our DSL with those op- erators support more advanced numerical reasoning. In these annotated programs, the average number of operations per question is 5, and some programs involve more than 30 steps of computa- tion. Table 3 an example from MathQA.
5

---

Published as a conference paper at ICLR 2020
Passage
Question & Answer
Multiple spans
...the population was spread out with 26.20 %
Question: Which groups in percent are larger than 16%?
under the age of 18, 9.30% from 18 to 24,
Program: SPAN(26,30),
26.50% from 25 to 44, 23.50% from 45 to 64, and 14.60% who were years of age older...
PASSAGE SPAN(46,48),
PASSAGE: SPAN(55,57)
Result: 'under the age 18, '25 44', 64'
Date
When major general Nathanael Greene took command the south, Marion and licutenant colonel Henry Lee 178I... On August 31, Marion rescued small American force trapped by 500 British diers...
Question: When did Marion rescue the American force?
Program:
ordered January
PASSAGE SPAN(71,71),
PASSAGE, SAAAGE.SPPN(72,2))
MASSAGE.SPAN(32
Result: 'August, '31', '1781'
Numerical operations
...Lassn county had a population of 34,895.
Question: How many people not either solely white
The racial makeup Lassen county 25,533
solely African American?
(73.2%) white (U.S. census). 2,834 (8.1%) African American (U.S. census)...
Program:
Result: 34895 (25532 + 2834) 6529
Counting
..tthe Bolshevik party ber through the simultaneous election soviets an organized uprising sup- ported by military mutiny...
power in Novem-
Question: How many factors involved in bringing the
Bolsheviks to power?
Program:
COUNT( PASSAGE SPAN(62, 66), PASSAGE SPAN(69, 74))
Result:
COUNT(
'simultaneous election the soviets',
'organized uprising supported by military mutiny") ) =2
Sorting
...Jaguars kicker Josh Scobee managed to get a 48-yard field goal...with with kicker Nate Kaeding getting a 23-yard field goal...
Question: Who kicked the longest field goal?
Program:
ARGMAX(
WWW.SSAAGE.SPANCOOOOO V VALUE(9)). HWW.SAAAGEE.PPANA294)AAALEE
Result:
ARGMAX( KV("Josh Scobee", 48), KV('Nate Kaeding', 23))
'Josh Scobee"
...Leftwich flipped I-yard touchdown pass
Question: How many yards was the shortest touchdown pass?
Wrighster..LLfftiic threw 16- yard touch- down pass Williams for 38-0 lead...
Program: MIN(VALU((IT) VALUE(19))
Result: MIN(I,
Table 2: Examples of correct predictions on DROP development set.
Question
Ánswer
Someone on a skateboard is traveling 8 miles per hour. How many feet does she travel in 5 seconds? mile= 5280 foet)
Program:
multiply(5.divdccmne (iit:////iiiiddmuuiily(///5585 )00p Result:
((8 5280) 3600) = 58.67
Table 3: An example in MathQA dataset.
Note that each question in MathQA is accompanied with 4 options, where 1 of them is the correct answer. However, since we do not have the full knowledge the operation semantics, we choose a conservative metric to evaluate the accuracy: predicted program is considered to be correct only is exactly the same as the annotated program. Thus, this metric is an under-estimation of the accuracy based on the exccution results. Despite that evaluation, we show that NeRd still outperforms the baselines by large margin.
much stricter measurement in our
4.2
IMPLEMENTATION DETAILS
DROP. Similar to previous work (Dua et al. 2019), for span prediction, we perform an exhaustive search to find all mentions of the ground truth spans in the passage, then include all of them candi- date programs. For numerical questions, we perform another exhaustive search over all expressions applying addition and subtraction over up to 3 numbers. In this way, able to find at least one

---

Published as a conference paper at ICLR 2020
program for over 95% of the training samples with number as the answer. Our data augmentation approach for counting and sorting questions can be seen in Section 3.1
MathQA. Besides the setting where all the ground truth programs are provided during training, we also evaluate the weak supervision setting on MathQA. Due to the lack of program executor, we are unable to perform the search similar to what we have done on DROP, To enable the first training iteration of the model, we assume that we have access to the ground truth programs for a small fraction of training samples at the beginning, and only know the final answer for the rest of training samples. In the first training iteration, the model only trains on the samples annotated with programs. In each of the following iterations, we first run beam search with beam size 64 to generate programs for each training sample that has not been annotated in previous iterations, and add the generated program only if it is exactly the same as the ground truth annotation.
For fair comparison, our reader uses the same pre-trained model as (Hu et al., 2019 Andor et al., 2019), i.e., BERTLARGE. For both benchmarks, perform greedy decoding during the evaluation.
4.3 BASELINES
DROP. We evaluate NeRd against three types of baselines: (1) previous models on DROP; (2) NeRd with and without counting and sorting operations; (3) NeRd with different training algorithms, and we discuss the details below.
Previous approaches. We compare with NAQANet (Dua al. 2019), NABERT (Hu et al. 2019) MTMSN (Hu et al. 2019). and BERT-Calc (Andor et al. 2019). We have discussed the key dif- ferences between NeRd and BERT-Cale the baseline with the best performance, in Section 2.2 On the other hand, NAQANet, NABERT, MTMSN share the same overall framework, where they augment an existing model to include individual modules for span selection, numerical expression generation, counting, negation, etc. While NAQANet is based on QANet, other baselines as well as NeRd are based on BERT. Note that the span selection modules themselves are not able to handle questions that return multiple spans as the answer, which causes the exact match accuracy to be zero on multiple-span selection questions for both NAQANet and NABERT. To tackle this issue, MTMSN adapts the non-maximum suppression algorithm (Rosenfeld & Thurston 1971) to select multiple spans from the candidates with the top prediction probabilities.
Operator variants of NeRd. To show that NeRd learns to apply counting and sorting operations appropriately, we also evaluate the following two variants: (1) NeRd without counting: we remove COUNT where the execution engine returns the number a for operation COUNT X. This counting process is the same as (Andor et al., 2019). (2) NeRd without sorting: we remove ARGMAX, ARGMIN, MAX and MIN operations, so that the model needs to use span selection operations for sorting questions.
the COUNT operation in Table 1 and introduce 10 operations COUNT_O, 0, COUNT_
Training variants of NeRd. To show the effectiveness of our training algorithm, we compare with the following baselines: (1) Hard EM described in Section 3.2, and (2) Maximum Likelihood, which maximizes the likelihood of each program that returns the correct answer for a training sample.
We compare with Seq2prog and Seq2prog+cat models in Amini et al. (2019), which LSTM- encoder-decoder architectures implemented in OpenNMT (Klein al. 2018). In particular, SeqZprog+cat extracts the category label of each question, then trains separate LSTMs to handle different categories, which improves the accuracy by 2.3%.
MathQA.
4.4 RESULTS
DROP. Table summarizes our main evaluation results on DROP dataset, with 9.5K samples in the development set and 9.6K hidden samples in the test set. Note that NABERT was not evaluated on the test set (Hu et al. 2019). Specifically, we train 10 NeRd models with the best configuration from different random initialization, present the mean and standard error of the results on the development set, and submit a single model to obtain the result on the hidden test set. We can observe that on test set, NeRd outperforms previous models by 1.37% on exact match, and 1. 181 on Fl score. Notice that in (Andor et al. 2019), they train their BERT-Cale model on CoQA (Reddy et al. 2019) in addition to DROP, and they also evaluate an ensemble with 6 models, resulting in the exact match of 78.14, and Fl score of 81.78 on test set. However, we training data and ensembling, NeRd still beats their single model, and the performance is on par with their ensemble model.
that without additional
7

---

Published as a conference paper at ICLR 2020
Overall Dev
Overall
Test
Number (62%)
Span (32%)
Spans (4.4%)
Date (1.6%)
EM
F1
EM
F1
EM
F1
EM
F1
EM
F1
EM
F1
NAQANet
46.75
50.39
44.24
47.77
44,9
45.0
58.2
64.8
0.0
27.3
32.0
39.6
NABERT
64.61
67.35
63.8
64.0
75.9
80.6
0.0
22.7
55.7
60.8
MTMSN,ARGR
76.68
80.54
75.85
79.85
80.9
81.1
77.5
82.8
25.1
62.8
55.7
69.0
BERT-Calc
78.09
81.65
76.96
80.53
82.0
82.1
78.8
83.4
5.1
45.0
58.1
61.8
78.55
81.85
82,4
82.6
76.2
81.8
51.3
77.6
58.3
67.2
NeRd
78.33
81.71
0.27
1:
0.20
1 0.3
1 0.2
1
0.4
0.2
1 0.8
1.2
1: 1.8
1 1.7
Table 4: Results DROP dataset. On the development set, we present the mean and standard emror of 10 NeRd models, and the test result of a single model. For all models, the performance breakdown of different question types is on the development set. Note that the training data of BERT-Calc model (Andor et al. 2019) for test set evaluation is augmented with CoQA (Reddy
al. 2019
with Count Op
w/o Count op
with Sort Ops
w/o Sort Ops
EM
73.1
71.2
FM
83.9
82.1
F1
73.1
71.2
F1
86.8
85.5
(a)
(h)
Table 5: Results of counting and sorting questions on DROP development where compare variants of NeRd with and without the corresponding operations. (a): counting; (b): sorting. For each setting, we present the best results development set.
To understand the strengths of NeRd, we first show examples of correct predictions in Table 2 We can observe that NeRd is able to compose multiple operations which helps boost the performance. In particular, for questions that require the selection of multiple spans, the exact match accuracy of NeRd is more than double of the best previous approach that spe- cially designed for multi-span prediction, and the Fl score also improves around 15%. Meanwhile, NeRd is able generate more complicated arithmetic expressions than Andor al. (2019). thanks to the compositionality of our approach.
to obtain the correct answer,
We further present our ablation studies of counting and sorting operations in Tables and Specif- ically, we evaluate on two subsets of DROP development set that include counting and sorting ques- tions only, using the variants of NeRd with and without the corresponding operations. We can observe that adding these advanced operations can not only boost the performance, but also enable the model to provide the rationale behind its predictions. For counting problems, NeRd able to select the spans related to the question. For sorting problems, NeRd first associates the entities with their corresponding values to compose the key-value pairs, then picks the most relevant ones for prediction. None of the previous models is able to demonstrate such reasoning processes, which suggests better interpretability of NeRd.
Finally, present the results of different training algorithms in Table 7 First, observe that by filtering spurious programs, the hard EM significantly boosts the performance of the maximum likelihood training for 10%, which may be due to the fact that the exhaustive search finds plenty of spurious programs that yield the correct answer. Adding the threshold for program selection provides further improvement of about 7%, indicating that our training algorithm can better handle the issue of spurious programs and be more tolerant to the noise of answer annotations. In Appendix D we show some examples discarded by NeRd using the threshold, which mostly have the wrong answer annotations, e.g., incorrect numerical operations or missing part of the information in the question.
MathQA. We present the results on MathQA test set with around 3K samples in Table g NeRd dramatically boosts the accuracy of the baselines by 25.5%. In addition, we also evaluate a variant of NeRd with the same model architecture, but the BERT encoder is not pre-trained and is randomly initialized. We observe that this variant still yields performance gain of 17. 17.4%. Note that NeRd is measured by the program accuracy, which is a much stricter criterion and thus is an underestimation of the execution accuracy computed in (Amini et al. 2019). Moreover, even with only 20% training data labeled with ground truth programs, NeRd still outperforms the baseline.
5 RELATED WORK
Reading comprehension and question answering have recently attracted a lot of attention from the NLP community. A plethora of datasets have been available evaluate different capabilities of
8

---

Published as a conference paper at ICLR 2020
Passage
Question & Prediction
... ...wthh field goals 38
Question: How many total field goals were kicked in the game?
and yards by kicker
Predicted Program:
fol- lowed by 43-yard field goal by Carpenter ... yard field goal
Dan Carpenter
COUNT(
PASSAGE
PASSAGE PASSACE.SPANC7,, PASSAGE.SPAN(IEES (PAN PASSAGE AAA.....A(1153111
SPAN(75,75)) MASSAGESSPAN(SSS
Result: COUNT( '38", '36 yards', '43 yard',,', '52- 52-yard")=
Predicted Program (-counting): COUNTS Result:
with the five common surgeries being breast augmentation, li-
Question: How many the live must common procedures are not done on breusts?
Predicted Program:
COUNT(
posuction, breast reduc-
PASSAGE SPAN(132,135), PASSAGE SPAN(140,142) PASSAGE SPAN(144.149)
tion, eyelid surgery and abdominoplasty.. ...
Result: COUNT( 'liposuction', 'eyelid surgery', "abdominoplasty") =3
Predicted Program (-counting) COUNT4 Result:
(a)
Passage
Question Prediction
In the third quarter, Arizona's deficit continued to climb Cas-
Question: Who threw the longest touchdown pass?
Predicted Program:
sel completed 76-yard touchdown
ARGMAX(
to wide receiver Randy Moss
KVIPASSSAE.SPANI2002222 SPAN(205,208) VALUE(18)..
quarterback Matt Leinart com-
KV(PASSAGE, SPANGEE2SAA VALUB((44))
pleted a 78 yard touchdown pass to
Result: ARGMAX(KY( I Leinart', KV) KV( Cassel, 76)) = 'Matt Leinart'
wide receiver Larry Fitzgerald... ...
Predicted Program (-sorting): MASSAGGESSPAN(22..A Result: Matt Cassel
Camey got 38-yard field goal with Camey connecting 39.
Question: How many yards was the longest field goal?
Predicted Program: MAX(VALUUE(4)
yard field goal... ...
Result: MAX(39, 38) 39
Predicted Program (-sorting): VALUE(T]) Result: 38
(b)
Table 6: Examples of counting and sorting questions on DROP development set, where NeRd with the corresponding operations gives the correct predictions, while the variants without them do not. (a): counting; (b): sorting.
EM
Fl
Accuracy
Hard EM
Seq2prog
51.9
with thresholding
80.58
83.42
Seq2prog+cat
54.2
Hard EM
73.72
77.46
NeRd
79.7
Maximum Likelihood
63.96
67.98
NeRd (-pretraining)
71.6
NeRd (20%)
56.5
Table 7: Results of different training algorithms on DROP development set. For each setting, we present the best results on the development set.
Table 8: Results on MathQA test set, with NeRd and two variants: (1) no pre-training: (2) using 20% of the program annotations in training.
the models, such as SQuAD (Rajpurkar al. 2016), CoQA (Reddy al. 2019), GLUE (Wang (et al., 2019), etc. A bunch of representative models are proposed for these benchmarks, includ- ing BiDAF (Seo al. 2017). r-net (Wang et al. 2017), DrQA (Chen al. 2017), DCN (Xiong jet al. 2016) and QA ( Yu et al. 2018). More recently, massive text pre-training techniques, e.g.. ELMo (Peters al. 2018), BERT Devlin al. 2019). XLNet (Yang al., 2019) and Roberta (Liu 2019). have achieved superior performance on these tasks. However, for more complicated tasks that require logical reasoning, pre-trained models alone are insufficient.
ct al.
On the other hand, semantic parsing has recently seen a lot of progress from the neural symbolic ap- proaches. Jia & Liang) (2016); Dong & Lapata (2016); Zhong et al. (2017) applied neural sequence- to-sequence and sequence-to to-tree models to semantic parsing with full supervision. Liang et al. G (2077): Neelakantan al. (2016); Krishnamurthy et al. (2017) Guu et al. (201)); Liang et al. (2018) have advanced the state-of oftte-of-the-art in weakly supervised semantic parsing on knowledge graphs and tabular databases. However, most of the successes of semantic parsing are limited to structured data sources. In contrast, our work naturally extends the complex reasoning in semantic parsing to reading comprehension by introducing the span selection operators. Several methods for training with weak supervision have been proposed in the context of weakly supervised semantic parsing including Maximum Marginal Likelihood (Berant et al. 2013 Krishnamurthy et al.] [017 Dasigi
al. 2019) Guu et al. 2017). RL. (Liang al. 2017 2018) and Hard EM (Liang et al. 2017 Min

---

Published as a conference paper at ICLR 2020
et al. 2019). Our approach is based on Hard EM due to its simplicity and efficiency, and extends it by adding a decaying threshold, which improves its robustness against spurious programs.
In the broader context, neural symbolic approaches have been applied Visual Question Answer- ing (Andreas et al. 2016 Mao et al., 2019 Johnson et al. 2017). where the neural architecture is composed with sub-modules based on the structured parses of the questions. Another line of work studied neural symbolic approaches to learn the execution of symbolic operations such as addition and sorting (Graves al. 20144) Reed & de Freitas 2016 Cai et al. 2017 Dong al. 2019). In this work, we study neural symbolic approaches for reading comprehension tasks that require discrete reasoning over the text (Dua et al., 2019; Hu al. 2019 Andor al. 2019 Amini al. 2019).
6 CONCLUSION
We presented the Neural Symbolic Reader (NeRd) as a scalable integration of distributed represen- tations and symbolic operations for reading comprchension. NeRd architecture consists of reader that encodes text into vector representation, and a programmer that generates programs, which will be executed to produce the answer. By introducing the span selection operators, our architecture can generate compositional programs to perform complex reasoning over text for dif- ferent domains by only extending the set of operators. We also overcome the challenge of weak supervision by applying data augmentation techniques and hard EM with thresholding. In our evalu- ation, using the same model architecture without any change, NeRd significantly surpasses previous state-of-ther tfrttsaasssss on two challenging reading comprehension tasks, DROP and MathQA. We hope to motivate future works to introduce complex reasoning other domains or other tasks in NLP, e.g., machine translation and language modeling, by extending the set of operators.
REFERENCES
Aida Amini, Saadia Gabriel, Peter Lin, Rik Koncel-Kedzionski, Yejin Choi, and Hannaneh Ha- jishirzi. Mathqa: Towards interpretable math word problem solving with operation-based for- malisms. arXiv preprint arXiv: 13319, 2019.
Daniel Andor, Luheng He, Kenton Lee, and Emily Pitler. Giving bert a calculator: Finding opera- tions and arguments with reading comprehension. arXiv preprint arXiv:1909.0011 00109, 2019.
Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Learning compose neural networks for question answering. urXiv:1601.01700 2016.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning align and translate. arXiv: 14090043, 2014.
Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang. Semantic parsing on freebase from question-answer pairs. EMNLP, 2(5):6, 2013.
Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Leveraging grammar and reinforcement learning for neural program synthesis. In International Conference on Learning Representations, 2018.
Jonathon Cai, Richard Shin, and Dawn Song. Making neural programming architectures generalize via recursion. ICLR, 2017.
Xavier Carreras and Lluís Märquez. Introduction to the conll-2004 shared task: Semantic role labeling. In Proceedings of the Eighth Conference on Computational Natural Language Learning (CoNLL-2004) at HLT-NAACL 2004, pp. 89-97, 2004.
Danqi Chen, Adam Fisch, Jason Weston, and Antoine Bordes. Reading wikipedia to answer open- domain questions. In Proceedings of the 55th Annual Meeting of the Association for Computa- tional Linguistics, ACL 2017, Vancouver, Canada, July 30 August 4, Volume 1: Longg Papers, pp. 1870-1879, 2017.
Pradeep Dasigi, Matt Gardner, Shikhar Murty, Luke Zettlemoyer, and Eduard Hovy. Iterative search for weakly supervised semantic parsing. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies, Volume (Long and Short Pupers), pp. 2689, 2019.
10

---

Published as a conference paper at ICLR 2020
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pp. 117114186, 2019.
Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural logic machines. In 7th International Conference Learning Representations, ICLR 2019, New Or- leans, LA, USA, May 6-9, 2019, 2019.
Li Dong and Mirella Lapata. Language to logical form with neural attention. ACL, 2016.
Dheeru Dua, Yizhong Wang. Pradeep Dasigi, Gabriel Stanovsky, Sameer Singh, and Matt Gardner. DROP: A reading comprehension benchmark requiring discrete reasoning over paragraphs. In Proc. of NAACL, 2019.
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. CoRR, abs/1410.5401, 2014. DRRLhttp:/aaxxiv.oom httpaabb//11...11 1.10..11..0 5401
Kelvin Guu, Panupong Pasupat, Evan Liu, and Perey Liang. From language to programs: Bridging reinforcement learning and maximum marginal likelihood. ACL, 2017.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Comput., 1997.
Minghao Hu, Yuxing Peng, Zhen Huang, and Dongsheng Li. A multi-type multi-span network for reading comprehension that requires discrete reasoning, arXiv preprint 19t.::::99000555555. 2019.
Robin Jia and Percy Liang. Data recombination for neural semantic parsing, ACL, 2016.
Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Judy Hoffman, Li Fei-Fei, C Lawrence Zitnick, and Ross Girshick. Inferring and executing programs for visual reason- ing. In Proceedings of the IEEE International Conference on Computer Vision, pp. 2989-29988 2017.
Eukasz Kaiser and Ilya Sutskever. Neural gpus learn algorithms. arXiv:1511.0822 2015.
Guillaume Klein, Yoon Kim, Yuntian Deng, Vincent Nguyen, Jean Senellart, and Alexander M Rush. Opennmt: Neural machine translation toolkit. arXiv preprint arXiv:1805.11462 2018.
Jayant Krishnamurthy, Pradeep Dasigi, and Matt Gardner. Neural semantic parsing with type con- straints for semi-structured tables. EMNLP, 2017.
Chen Liang, Jonathan Berant, Quoe Le, Kenneth D. Forbus, and Lao. Neural symbolic machines: Learning semantic parsers on freebase with weak supervision. ACL, 2017.
Chen Liang, Mohammad Norouzi, Jonathan Berant, Quoe V. Le, and Ni Lao. Memory augmented policy optimization for program synthesis and semantic parsing. In NeurlPS, pp. 10015-10027, 2018.
Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom. Program induction by rationale gener- ation: Learning to solve and explain algebraic word problems. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1; Long Papers), pp. 158-167, 2017.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized BERT pretraining approach. CoRR, abs/1907.11699 1692, 2019.
Christopher Manning, Mihai Surdeanu, John Bauer, Jenny Finkel, Steven Bethard, and David Mc- Closky. The stanford corenlp natural language processing toolkit. In Proceedings of 52nd anmual meeting of the association for computational linguistics: system demonstrations, pp. 55-60, 2014.
Jiayuan Mao, Chuang Gan, Pushmeet Kohli, Joshua B. Tenenbaum, and Jiajun Wu. The neuro- symbolic concept learner: Interpreting scenes, words, and sentences from natural supervision. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans. LA. USA, May 6-9, 2019, 2019.

---

Published as a conference paper at ICLR 2020
Sewon Min, Danqi Chen, Hannaneh Hajishirzi, and Luke Zettlemoyer. A discrete hard em approach for weakly supervised question answering. arXiv preprint (xXiv:1909.044999 2019.
Arvind Neelakantan, Quoe V Le, Martin Abadi, Andrew McCallum, and Dario Amodei. Learning natural language interface with neural programmer. arXiv preprint arXiv:1611.08943 2016.
Panupong Pasupat and Percy Liang- Compositional semantic parsing on semi-structured tables. ACL, 2015.
Matthew E. Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. Deep contextualized word representations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, NAACL-HLT 2018, New Orleans, Louisiana, USA, June 1-6, 2018, Volume I (Long Papers), pp- 2227-22222222 2237, 2018.
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. Squad: 100,000+ questions for machine comprehension of text. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, EMNLP 2016, Austin, Texas, USA, November 1-4, 2016, pp- 2392,,2392,11 2016.
Siva Reddy, Danqi Chen, and Christopher D. Manning. Coqa: A conversational question answering challenge. TACL, 7:249-266, 2019.
Scott Reed and Nando de Freitas. Neural programmerrinterppeterrs ICIR, 2016.
Azriel Rosenfeld and Mark Thurston. Edge and curve detection for visual scene analysis. IEEE Transactions on computers, (5):562-566 1971.
Min Joon Seo, Aniruddha Kembhavi, Ali Farhadi, and Hannaneh Hajishirzi. Bidirectional attention flow for machine comprehension. In ICLR, 2017.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information 2017.
processing systems, pp.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. NIPS. 2015.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. GLUE: A multi-task benchmark and analysis platform for natural language understanding. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Wenhui Wang. Nan Yang, Furu Wei, Baobao Chang, and Ming Zhou. Gated welf-matchingg networks for reading comprehension and question answering. In Proceedings the 55th Annual Meeting of the Association for Computational Linguistics, ACI.2017, Vancouver, Canada, July 30 August 4, Volume 1: Long Papers, pp. 189-198, 2017.
Caiming Xiong, Victor Zhong, and Richard Socher. Dynamic coattention networks for question answering. CORR, abs/161 1.016604 2016. URL httt:://axxiv..rgg/// wtwpa/////..........
Zhilin Yang, Zihang Dai, Yiming Yang. Jaime G. Carbonell, Ruslan Salakhutdinov, and Quoc V. Le. Xlnet: Generalized autoregressive pretraining for language understanding. CoRR, abs/1906.08237, 2019.
Adams Wei Yu, David Dohan, Minh-Thang Luong, Rui Zhao, Kai Chen, Mohammad Norouzi, and Quoc V. Le. Qanet: Combining local convolution with global self-attention for reading compre- hension. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver; BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018.
Victor Zhong, Caiming Xiong, and Richard Socher. Seq2sql: Generating structured queries from natural language using reinforcement learning. arXiv:1709.00100 2017.
12

---

Published as a conference paper at ICLR 2020
A MORE DETAILS ABOUT THE INPUT PREPROCESSING
We preprocess the input passages and questions in similar way as the input preprocessing of DROP dataset described in (Andor al. 2019). Specifically, to facilitate the usage of BERT, we split up the documents longer than L 512 tokens. Meanwhile, we extract the locations and values of the numbers, so that they can retrieved via indices when applying numerical operators. We apply the same input preprocessing MathQA well.
B MORE DISCUSSION ABOUT THE DOMAIN SPECIFIC LANGUAGE
To better support numerical reasoning. sometimes we need to leverage pre-defined constants for our computation. On MathQA, we have shown that applying the constant 3600, which is provided in their pre-defined question-agnostic constant list, is necessary for the calculation in Table Mean- while, we find that defining such constant list is also helpful on DROP benchmark. For example, a variant the sample numerical operation question in Table 2 "How many people, in terms of percentage, were either solely white solely African American?", and such questions included in DROP dataset as well. In this case, unless we are able to use the number 100 in our calculation, there is way to obtain the correct answer. Again, previous works design specialized modules to deal with such questions, which is the main role of the negation module illustrated in Figure On the contrary, we introduce a constant list that callable for every question, that the model can learn to apply any constant covered in the list, without the need of manually designing separate modules for questions requiring different constants.
In our evaluation, for DROP, we used [100, 12, 28, 20,30, 30, 1, as the constant list, which is helpful for percentage and date time calculation. For MathQA, we used the constant list provided in their public dataset, which includes 23 constants that cover common conversion between different units, comain-specifie constants for geometry, physics and probability, etc.
C MORE DETAILS ABOUT THE MODEL ARCHITECTURE
C.I READER
The reader implementation is largely the same as (Andor et al., 2019). Specifically, for the embed- ding representation of the reader component, we feed the question and passage jointly into BERT, which provides the output vector of each input token 4 as e; Unless otherwise specified, the en- coder initialized with the uncased whole-word word-masking version of BERT We denote the size of e; as Ho.
C.2 PROGRAMMER
The core architecture of the programmer is a 1-layer LSTM with the hidden size of H 512. To formally describe the input space and output space of the programmer, we denote Rt as the size of the reserved tokens, which include both operators and constants in domain-specific language, and the special start and end tokens [GO] and [EOF]; and L 512 as the total number of the question and passage tokens in single sample. Samples with fewer than L 512 tokens will be padded with [ECF] J tokens to achieve this length. the following, we discuss the details each component.
Input embedding. At each timestep, the programmer could generate program token from: (1) the reserved tokens of the domain-speciff language; and (2) the input question and passage tokens. The embedding of the i-th reserved token is
hr; 1.7
Where E, is trainable embedding matrix of size R x H. and r; is the one-hot encoding of the token.
For the i-th token in the input question and passage token list their embedding is
13

---

Published as a conference paper at ICLR 2020
ht, = Ptes
Where P, is trainable projection matrix of size H x Ho-
Attention module over the input. At each timetstep T. let [pI. Pr.,...PPPP11 denote the list of program tokens that are already generated in previous timesteps. and define [hpp, hp1, .p., hpr-1] as the decoder history, where hp is the embedding vector of the [GO] token calculated as above; [hpi, hp2...................... hpr-1] are #Hdiimeniional vectors corresponding to the generated program token list, and we will discuss how they are computed later.
Denote (hT, CT) LSTM(hpr- (hr-14 1.- cT- as the hidden state of the LSTM decoder at timestep T, where (ho, co) is the trainable initial state, and hpr-1 is the LSTM input.
For each of hp; the decoder history, we compute
vh, Wnhp
Where W, is a trainable matrix of size H x H. The attention weight of each hy; the decoder history is computed as
wh: exp(hTuhs)) ΣJ= exp(h?.uh,)
The attention vector of the decoder history is thus
att Σ why hp:
This formulation is similar the attention mechanism introduced in prior work (Bahdanau al. 2014). Correspondingly, we compute the attention vector of the passage tokens atf,, and the atten- tion vector the question tokens att..
Afterwards, we compute
W, [alla; ably; alpp; htr]
Where We is a trainable matrix of size 4H, and [a; denotes the concatenation of a and b.
Program token prediction. We compute another attention vector of the question tokens att' in similar way above, but with a different set of trainable parameters. Then for each input token, we have
ht Pd [b44 hi, all')
hr: P'rr att])
Where p' is trainable matrix of size И 2H, and is the Hadamard product.
Let Hr a (R + L) x H-dimensional matrix, where the first R rows are hr? for < R, and the next L rows are ht, for 0 i < L. Then compute
w/ H vT
Where why denotes the weight of selecting the i-th token as the next program token. This design is similar the pointer network (Vinyals al. 2015
14

---

Published as a conference paper at ICLR 2020
Note that valid program should satisfy the grammar constraints, for instance, those listed in Table on DROP dataset. Therefore, we compute a mask my as an (R + dimmenssio vector, where mr; = 1 when the i-th token is valid next program token, and mr: 0 if it is invalid. In the following, we take the DROP dataset as the example, and list some sample rules for mask generation:
(1) At the beginning of the program generation, my; iff the i-th token denotes operator;
(2) When the previous generated program token pr-1 is PASSACE, SSSSSEEEE_PA,,,, then mi; = iff the i-th token is from the passage. Similarly, if pr-1 is QUESTION SPAN, then mr; = 1 iff the i-th token is from the question.
(3) As discussed in Appendix A preprocess the data extract the locations and values of num- bers in the input question and passage, thus we can leverage to generate masks for numerical calculation operators. Specifically, when pr-1 E (DIFF, SUM, VALUE), my; = 1 iff the i-th token is from the constant list, or number from either the input question or the passage.
With the generated program mask, compute
WT w/- C(1 mp)
Where C is a large positive constant to ensure that the weight of an invalid program token is much smaller than the valid program tokens. In practice, decoding process is a common practice in order to ensure the syntactic correctness of the generated programs (Krishnamurthy et al. 2017: Liang et al. 2017 Bunel al.) 20188).
C 1e6. Such grammar-based
Afterwards, the model predicts pr arg max; (wT) as the next program token. We can also apply the beam search for decoding, but find that the greedy decoding is already sufficient provide good results, while the inference process is also much faster than the beam search.
Finally, hpt prr is the vector representation corresponding to pr. which is appended to the decoder history for generating the next program token.
D MORE DETAILS ABOUT TRAINING
D. DATA AUGMENTATION
In this section, we discuss the details of our data augmentation process for counting and sorting questions on DROP. To obtain training samples for counting questions with ground truth annotations, starting from the span selection questions in the training set, filter out those questions that either can be answered by using the QUESTION SPAN operation, or do not start with any interrogative in ["Whht",, "Which", "Who", "Where"). Afterwards, replace the interrogative with "How many", and modify the ground truth program correspondingly. In this way, we can augment 15K additional questions for counting in DROP training set.
To annotate the key-value pairs, for each entity recognized by the CoreNLP tool, we search for the numbers that in the same clause the entity, i.e., separated by any punctuation mark, and discard those entities that do not have any nearby number satisfying this constraint. Afterwards, we filter out those questions that do not include any superlative ["longest", "shortest", "largest", "smallest", "most" and "least"]. For the remaining questions, we call each of the sorting opera- tions, i.e., ARGMAX, ARGMIN, MAX, MTN, with all extracted key-value pairs as the arguments. For ARGMAX and MAX operators, the key-value pairs are sorted in the descending order of their values; for ARGMIN and MIN operators, they are sorted in the increasing order of their values. If any of the resulted sorting program yields the correct answer, the program is included into the training set. In this way, we can annotate 0.9K questions using ARCMAX or ARGMIN operations, and 1.8K questions using MAX or MIN operations in DROP training set.
D.2 TRAINING CONFIGURATION
For the training algorithm described in Algorithm I the initial threshold on = 0.5, and the decay factor 7 0.5. We perform early stopping when both exact match and F1 score on the development
15

---

Published as a conference paper at ICLR 2020
Passage
Question
Ground truth
... but had to settle for 23-yard field goal by kicker Matt Bryant...
How many field goals shorter than 30 yards did Matt Bryant kick?
from sample of 40 Sherman tanks,
How many more Sherman tanks burned out than survived in the Nor-
22
33 tanks burned (82 percent) and tanks remained unburned...
mandy Campaign?
Table 9: Some samples in DROP training set with the wrong annotations, which are discarded by NeRd because none of the annotated programs passes the threshold of our training algorithm.
Question lype Question span
Passage
Question What happened first, the Hague campaigns as field officer or he spoke with envoy of Savoy for opportuni- ties in the army?
Prediction
The campaigns 1702 and 1703 showed his limitations as a field of- ficer.. In carly 1704, he spoke with the envoy of Savoy about possible opportunities in their army... ...
Prediction:
QUESTION.SPANCE
Result: "campaigns as field offi- cer"
Ground truth: "campaigns of
1702 and 1703"
Counting
The five regions with the lowest fertility rates were Beijing (0.71).
How many areas had a fertility rate of .74?
Prediction: COUNT(
PASSAGE SPAN(216, 216),
Shanghai (0.74), Liaoning (0.74). Heilongjiang (0.75)... ...
PASSAGE_SPA
223),
PASSAGE SPAN(230, 231))
Result: (OUNT(""Beiilnn))
"Shanghai", "Liaoning") =3
Ground truth: 2
Sorting
to set up Nugent's carcer-long 54-yard field goal give a 9-3 lead ... The half ended when Brown came five yards short on a 59-yard field goal attempt...
How many yards
Program:
was the longest field goal?
MAX(VALUE(IÓ), VALUE(20)
Result: MAX(54, 59) =
Ground truth: 54
Table 10: Examples of wrong predictions on DROP dev set.
do improve for two consecutive training iterations. For both DROP and MathQA datasets, the training typically takes around 50K ~ 60K training steps.
For both tasks in our evaluation, we train the model with Adam optimizer, with an initial learning rate of 5e-5, and batch size of 32. Gradients with L2 norm larger than 1.0 are clipped.
E EXAMPLES OF WRONG ANNOTATIONS ON DROP
Table P lists some examples of wrong annotations in DROP training set. Specifically, the first anno- tation is wrong because the crowd worker simply counts the number of field goals included in the entire passage, without considering the constraints of lengths and the kicker's name; on the other hand, the second mistake comes from the wrong numerical calculations. For both samples, highest likelihood among all programs with the annotated answer is smaller than le-4, thus are not included during training, which is why the thresholding helps significantly.
F EXAMPLES OF WRONG PREDICTIONS ON DROP
Table TO presents some error cases NeRd on DROP development set.
16


Reviews:
[{"review_id": "rJlyvMZy5B", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper discusses an extended DSL language for answering complex questions from text and adding data augmentation as well as weak supervision for training an encoder/decoder model where the encoder is a language model and decoder a program synthesis machine generating instructions using the DSL. They show interesting results on two datasets requiring symbolic reasoning for answering the questions.\n\nOverall, I like the paper and I think it contains simple extensions to previous methods referenced in the paper enabling them to work well on these datasets.\n\nA few comments:\n\n1 - Would be interesting to see the performance of the weak supervision on these datasets. In other words, if the heuristics are designed to provide noisy instruction sets for training, we need to see the performance of those on these datasets to determine if the models are generalising beyond those heuristics or they perform at the same level which then may mean we don't need the model.\n\n2 - From Tab 4, it seems the largest improvements are due to span-selection cases as a result of adding span operators to the DSL. A deep dive on this would be a great insight (in addition to performance improvement statements on page 7).\n\n3 - Since the span and value operators require indices to the text location, could you please clarify in the text how that is done? Do LSTMs output the indices or are you selecting from a preselection spans as part of preprocessing?\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SkgcD3zecB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "-- define cascade errors when you first use the phrase\n-- basic english grammar could be fixed but is not interfering with understanding\n-- what is the early stopping criterion in Alg 1?\n-- did you try any other values for the initial threshold and decay factor? \n-- At the end of Section 4.1 DROP: \", but not the same.\" - I can't parse what this last clause is supposed to mean.\n--the diff sum example in table 2 is confusing; the program appears to sum up the numbers but the result is a subtraction without a sum operation in it. Would be clearer to show the sum in the result line as well rather than distribute the subtraction. Also, shouldn't it be diff(9, sum(10, 12))?\n-- I think you should pull at least some commentary about the constant used in Table 3 from Appendix B and include it in the main paper (or at least mention Appendix B is the place to look). Can you add a table in an appendix showing the complete list of operators used? \n-- Nice results in Table 4 on the dev set. Are there Test set results as well?\n-- The organization of the Baselines 4.3 section and the Results 4.4 is confusing. For example, you mention that you test different variants of NeRd, operator variants, and mathqa, but then the results are not mentioned for these experiments until the next page. I found myself immediately looking for the numbers/results when you introduce the experiment. I would pair your experiment description with the results rather than grouping all experiment descriptions and then grouping all results, especially when the order of the experiment descriptions does not match the order of the results presented. For example, in baselines you discuss training variants and then operators. Then in Results you discuss operators before variants. It is too disconnected and makes the reader jump around a bunch. Same goes for the drop baselines where you mention a bunch of models, and I would prefer the Results/discussion paired with each one, rather than having to wait for it down below.\n-- Overall it seems like a solid work; good empirical results showing improvements of each purported contribution. The model itself is a relatively simple construction of basic component, but the combination with the DSL is intuitive and makes sense. I don't think the novelty in model here is the main selling point anyways; the training variants and the demonstration of how well a DSL approach can do combined with previously introduced methods.\n-- I find the model description to be slightly unclear. In Fig 1 for example there is an arrow that connects passage to compositional programs. What does that arrow represent? I think you should elaborate on how the attention over the encoded text interacts with the attention over previously generated tokens. Equations would make this far more explicit as is I am left with a lot of questions on how to implement your model. Maybe you can add to your appendix? Or release your code? That is mentioned either.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "H1eIfQ5odH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a semantic parser that operates over passages of text instead of a structured data source.  This is the first time anyone has demonstrated such a semantic parser (Siva Reddy and several others have essentially used unstructured text as an information source for a semantic parser, similar to OpenIE methods, but this is qualitatively different).  The key insight is to let the semantic parser point to locations in the text that can be used in further symbolic operations.  This is excellent work, and it should definitely be accepted.  I have a ton of questions about this method, but they are good questions.  The rest of this review focuses on things that I thought could be more clear, or that raise new questions, and might sound negative.  Please understand them, however, in terms of my overall score and what I said above.\n\nThe three claimed contributions are (1) better numbers, (2) better compositionality / domain applicability, and (3) better interpretability.\n\n(2) and (3) sound a bit like overclaiming in the introduction to me, as there isn't a whole lot of nested composition in the language used by NeRd, and the BERT calculator in principle is almost as compositional and interpretable (also, e.g., NAQANet can add and subtract an arbitrary number of numbers, also, and it tells you which ones they are, just as NeRd does).  Later in the paper the specifics of those claims are made more clear, and while they are justified, they are very narrow claims.  To me, someone who is intimately familiar with this research area, the key contributions (the things that I learned) are (1) using passage-span and key-value predicates actually works, (2) how much difference hard EM and thresholding make, and (3) the data augmentation in this work is pretty clever.  (2) was intuitively clear to me after seeing Dasigi's iterative search paper and Min's hard EM paper, but the difference in results presented here is pretty striking.\n\nCompositionality:\n\nThe authors claim that their method is compositional and domain agnostic, while all previous methods had hand-crafted modules for specific question types.  However, I see little reason to believe there's much of a difference here.  You also defined operations that are tailored to the dataset, and are basically identical to the operations that others have used.  I see no evidence that NeRd actually generalizes to program types that are beyond what is captured by other methods.  It's possible that this happens, but there is no evaluation that discusses this, and from all of the examples I'm led to believe that this is basically also just learning a few program templates, the same ones learned by previous methods.  With the weak supervision that you have, are you actually able to find more complex programs during your search?  Some kind of demonstration of actual compositionality on the more complex questions in DROP would make a very strong argument for your claims; without that, they ring a little hollow.\n\nInterpretability:\n\nThe use of passage-span as a predicate is really interesting, and it raises a lot of questions.  This predicate lets the model shortcut any interpretable reasoning and do operations entirely inside the encoder/parser.  For example, your first example in table 2 ostensibly requires filtering the numbers in the passage to those that are percentages associated with groups, then filtering them again to those where the percentage is larger than 16, then returning the associated groups. But your method jumps straight to returning a set of passage spans.  This is hardly interpretable.  (In fairness, no prior method provides interpretable reasoning for this kind of operation either.)  But the fact that you have this predicate lets the model do these filters and greater-than comparisons inside the network in an opaque way, while also getting interpretable operations for some questions (table 5 is further confirmation of this, and of the fact that you probably are not capturing many of more the complex, compositional questions in DROP).  But how does the network decide which to do?  Any argmax or max question, and many count questions, could be answered by passage-span alone.  With only weak supervision, and with the parser having the ability to shortcut these more interpretable operations, how often are you actually getting the interpretable one, and what's causing the model to choose it?\n\nSimilarly, how often does an argmax or a max operation actually operate on the full set that you would expect it to?  Or does it just do the argmax internal to the network, and output only one item as an argument to the argmax?  If the later, this again hurts your claims of better interpretability over prior methods, as the logic is just as opaque as before.  This also seems like a really hard search problem in how you've set up your DSL - what would make your search over programs actually select all of the correct arguments?  Because you're selecting passage spans directly instead of performing some kind of matching operation, you have to have your search select all of the appropriate spans for this to be \"interpretable\", and not just hiding the logic inside of the network.  But that seems like a totally intractable search.  You found a clever way to get around this for count questions (even though that still implicitly hides a bunch of filtering logic, as noted above), but I don't know how to make it work for maxes and argmaxes.\n\nAnother question raised by the passage-span predicate: the more you use bare passage-span programs for training, the more the network learns to put all of its compositional reasoning inside, in an opaque way, instead of giving you interpretable compositionality.  At one extreme, you end up with something like NABERT (or even less compositional), where basically everything is inside the network.  At the other extreme, where you don't have passage-span, you are left with a crippled semantic parser that can't handle most of the questions.  But using the predicate introduces tension in the model between interpretability and flexibility.  How do we resolve this tension?  (This isn't something I expect your paper to address, it's just a really interesting and important question raised by your work.)\n\nParser:\n\nPrior work has found benefit in using runtime constraints on parser outputs, or grammar-based decoding.  It looks like you are doing neither of those, yet you're able to output specific token indices and number indices in your programs.  Are you really not doing anything special to handle those?  How does the decoder know token indices?  I feel like something must be missing here, or a simple LSTM decoder is more magical than I thought.\n\nEvaluation:\n\nWhy only show results on DROP dev, and not on the test set?  It's possible that your higher numbers are because you were better able to overfit to the dev set, which you presumably used during training.  (I don't think that that's likely, but it's a concern that would be easily avoided by evaluating on test.)", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Main content:

Blind review #1 summarizes it well:

This paper presents a semantic parser that operates over passages of text instead of a structured data source.  This is the first time anyone has demonstrated such a semantic parser (Siva Reddy and several others have essentially used unstructured text as an information source for a semantic parser, similar to OpenIE methods, but this is qualitatively different).  The key insight is to let the semantic parser point to locations in the text that can be used in further symbolic operations.  This is excellent work, and it should definitely be accepted.  I have a ton of questions about this method, but they are good questions.  

--

Discussion:

The reviews all agree on a generally positive assessment, and focus on details that have been addressed, rather than major problems.

--

Recommendation and justification:

This paper should be accepted. Even though novelty in terms of fundamental machine learning components is minimal, but the architecture employing neural models to do symbolic work is a good contribution in a crucial direction (especially in the theme of ICLR).
Decision: Accept (Spotlight)