Year: 2018

Abstract:
In this paper we introduce the Scratchpad Encoder, a novel addition to the sequence to sequence (seq2seq) framework and explore its effectiveness in generating natural language questions from a given logical form. The Scratchpad Encoder enables the decoder at each time step to modify all the encoder outputs, thus using the encoder as a “scratchpad” memory to keep track of what has been generated so far and to guide future generation. Experiments on a knowledge based question generation dataset show that our approach generates more fluent and expressive questions according to quantitative metrics and human judgments.

heading: 1 INTRODUCTION
text: Given the data driven nature of today’s question answering (QA) systems, the size and quality of training data play a major role in a system’s ability to answer questions correctly. In a knowledgebased question answering system, where the input is a natural language question and the answer generated is retrieved from the knowledge base (KB), the standard approach is to parse the question into a logical form that can query the knowledge base. (See Fig. 1 for an example.) This intermediate logical form could be Lambda-DCS (Liang (2013)), SPARQL (Harris et al. (2013)), or any other form interpretable by the knowledge base’s query engine.
One of the main challenges in training robust knowledge-based QA models is acquiring a large amount of diverse labeled data. Currently, the largest publicly available datasets for knowledgebased QA are on the order of 5-6 thousand queries 1 (tau Yih et al. (2016); Berant et al. (2013); Su et al. (2016)), which is relatively small when compared with reading comprehension datasets like SQuAD (Rajpurkar et al. (2016)) that have on the order of 100,000 examples, or machine translation datasets containing millions to tens of millions of parallel sentences.
Several complications arise when constructing labeled corpora for knowledge-based QA. Namely, since non-expert crowd workers are not familiar with logical form languages, collecting (query, logical form) pairs can be a difficult and slow process (Liang et al. (2016); Reddy et al. (2014)) 2. One could bypass crowd sourcing logical forms by training a model on (question, answer) pairs, treating the intermediate logical as a latent variable (Berant et al. (2013); Kwiatkowski et al. (2013); Yao & Van Durme (2014). Unfortunately, collecting only (query, answer) pairs is also difficult. To create the WebQuestions dataset Berant et al. (2013), judges were given 100,000 questions and asked to find the answers in Freebase. However, in only∼6,000 questions of these 100,000 (6%) were two judges able to arrive at the same answer.
In order to collect arbitrarily large datasets, we need methods requiring less human intervention and expertise. In this paper we explore the feasibility of generating meaningful questions given a logical form (i.e. SPARQL). The intuition is that it is easier to have a programmer with domain expertise generate a large set of programs, rather than train an average human judge to master SPARQL.
1The SimpleQuestions dataset (Bordes et al. (2015)) contains 100,000 examples, but cannot be considered as a general knowledge-base QA or semantic parsing dataset because all the questions have one logical form only: “Select Entity.Attribute from KB”. Here the parser’s job is to only fill out the values of Entity and Attribute. Our goal is to be able to answer more complex questions that require logical forms beyond those that can be described as only triple selection (See Fig 1).
2WebQuestionsSP tau Yih et al. (2016) dataset used crowdsourcing to collect (query, logical form) pairs, but the judges were familiar with Freebase, and a special interface was created for them
Recent work has even shown question generation from a logical form leads to improvements in semantic parsing (Guo et al. (2018)). We adapt the sequence to sequence (seq2seq) framework (Sutskever et al. (2014)) given its success in tasks such as machine translation (Bahdanau et al. (2014)) and traditional semantic parsing (Dong & Lapata (2016)). Despite their success, seq2seq with attention models fail to produce fluent output to the level of specificity and quality necessary for our task. Furthermore, they often fail to keep track of what has already been generated by the decoder, or copied from the input tokens in the case of Copynet (He et al. (2017) (see Table 7) often leading to erroneous repetitions. Our approach is aimed at mitigating these issues.
We introduce a novel write mechanism to the seq2seq framework that significantly outperforms several baselines termed the Scratchpad Encoder. Put simply, we allow the decoder to keep notes as it decodes; we keep the standard seq2seq encoder (Sutskever et al. (2014)), but at each time step allow the decoder to attentively write to the encoder outputs. In this way, we use the encoder as a “scratchpad” to direct future generation. In both quantitative evaluations of the generated questions and human judgments of their fluency and adequacy, our model attains significant improvement over standard seq2seq, Copynet (Gu et al. (2016)), and a coverage-enhanced approaches Tu et al. (2016); See et al. (2017). Furthermore, human judges strongly prefer questions generated using the Scratchpad Encoder over those produced using Copynet and a coverage-enhanced approaches — 89.44% and 61.36% of the time, respectively.
The contributions of this work are two-fold:
1. We introduce Scratchpad Encoder, a novel enhancement to the seq2seq framework allowing the decoder to see what has been generated thus far, and outperforming multiple baselines on quantitative and qualitative metrics.
2. We use Scratchpad Encoder to automatically generate questions given a corresponding SPARQL query, making it possible to generate a large high quality dataset of knowledge base (query, logical form) pairs.

heading: 2 MODEL BASICS/BACKGROUND
text: We build off of a standard seq2seq setup with (a) an encoder operating off the logical form, (b) a decoder outputting the generated question, and (c) a task-specific attention mechanism so that the decoder may focus on different parts of the logical form as it decodes. We describe these components below before detailing the copy mechanism and Scratchpad Encoder.
Encoder Let the input sequence (tokens of the logical form) of length T be indexed by the subscript t, so that the sequence of word vectors input into the model is x0...xT = x0..T. We encode the input via a bidirectional 2 layer GRU (Cho et al. (2014)), resulting in encoder outputs h0..T.
Decoder Let the decoding sequence (tokens of the question) be indexed by the superscript i such that si is the state of the decoder at decoding timestep i. The decoder’s initial state s0 is set to the final output of the encoder in both directions. The decoder uses a recurrence new state = f(2)(current state, input), where we use f(l) to refer to an l-layer GRU from now on.
Attention At every decoding step i, the decoder computes an attentive read (attniread) over the encoder states (h0..T) (as in Bahdanau et al. (2014)). This is computed by first computing a score for each encoder output (ht) via an MLP as follows. (We denote the concatenation of vectors z0, ..., zn as [z0; ...; zn].)
scoreit = W 1(W2[si; ht] T) (1) where W1 and W2 are learned parameters. These scores (scorei0..T) are then normalized into a probability distribution and used as the weights to compute a weighted average of encoder outputs (termed the attentive read), allowing the decoder to focus on different parts of the input at different timesteps i:
ai0..T = softmax(score i 0..T) (2)
attniread = T∑ t=0 (ait ∗ ht) (3)
Update The decoder then computes its new state using the word vector ŷi−1 for the previous output yi−1 along with the attentive read (attniread) to obtain the post-read state (s i post read):
si+1 = sipost read = f (2)(si, [ŷi−1; attniread]) (4)
Generation At every step, the decoder computes a distribution over output tokens from the postread state (sipost read):
yi = softmax(Woutsipost read) (5)
where Wout is a learned parameter.
Cross-Vocabulary Copying We noticed that many tokens that appear in the logical form are also present in the natural language form for each example. In fact, nearly half of the tokens in the question appear in the corresponding SPARQL of the WebQuestionSP dataset (tau Yih et al. (2016)) Hence, we give the network the ability to copy (Gu et al. (2016)) from its input by redefining the output distribution yi as a mixture between the generation distribution described previously (Eq. 5) and a copy distribution (Eq. 7).
yi = pigen ∗ softmax(Woutsipost read) + (1− pigen) ∗ copy(sipost read,h0..T, x0..T) (6) where copy is a distribution over the vocabulary V. We only consider “copyable” tokens (Vc) that appear in both the logical form input vocabulary (Vi) and question output vocabulary (Vo) (Vc = Vi ∩Vo). We define copy as:
copy(sipost read,h0..T, x0..T)v = T∑ t=0 (cit ∗ 1xt==v) (7)
The copy-attention distribution ci0..T is computed in a similar fashion to the attentive-read distribution (ai0..T) computed earlier (Eq. 3), except we use the post-read decoder state (s i post read) so the network can take into account the attentive read (attniread) as well as the previously generated token (ŷi−1) when computing copy scoreit.
copy scoreit = W 1(W2[sipost read; ht] T)) (8)
ci0..T = softmax(copy score i 0..T) (9)
attnicopy = T∑ t=0 (cit ∗ ht) (10)
where W1 and W2 are learned parameters with the same dimensionalities as in the previous case.
Finally, we need to compute “how much” we are generating vs. copying (pigen), again using the postread decoder state (sipost read) and the copy read (attn i copy) so the network can take the attentive read (attniread) and previously generated token (ŷ i−1) into account.
pigen = σ(W 1ReLU(W2[sipost read; attn i copy] T)) (11)

heading: 3 KEEPING NOTES WITH A SCRATCHPAD ENCODER
text: Although modern seq2seq models (including common extensions like Copynet tend to do well on multiple tasks and have led to promising improvements across the board (Bahdanau et al. (2014); Sutskever et al. (2014); Dong & Lapata (2016)), they often have issues with over and undergeneration, particularly with regards to repetition or copying (See et al. (2017); Tu et al. (2016), as well as integrating new information (See Eric & Manning (2017)). We propose a method that allows the network to update its encoding of the input at every step of decoding. Intuitively, we add one simple step to the decoder: treat the encoder states as a scratchpad, writing to it as if it were an external memory.
Up until now, the decoder’s workflow at every step i is as follows:
1. Reads attentively from the encoder outputs (attniread) (See Eq. 3) 2. Updates its state (sipost read) (See Eq. 4) 3. Outputs a distribution (yi) over the output vocabulary (See Eq. 6)
With the Scratchpad Encoder we add a fourth step:
4. Write an update (ui) to the encoder states (h0..T) in an attentive fashion (αi0..T) using the post-read decoder state (sipost read), treating the encoder states (h0..T) as if they were cells in an external memory:
hi+1t = α i th i t + (1− αit)ui (12)
αit = σ(W 1(W2[sipost read; attn i copy; h i t] T)) (13)
ui = Tanh(W3ReLU(W4[sipost read; attn i copy] T)) (14)
Tanh is used to ensure that hi+1t remains in the range [−1, 1], since hit ∈ [−1, 1] as h0t is the output of a GRU. αit can be understood as an update gate for the representation of the input sequence h0..T, signifying how much to overwrite a cell versus keeping past information.
While decoding, it is advantageous for the network to keep track of which tokens have been generated and which locations have been attended. By allowing the decoder to write to the encoder we can easily track this information. By keeping the information outside of the decoder GRU we also preserve capacity in the decoder for other subtasks like smoothing.
The Scratchpad Encoder is independent of the copy mechanism that we present here, meaning it can be an addition to any seq2seq with attention framework. To use the Scratchpad Encoder without the copy mechanism replace attnicopy with attn i read in the equations above.

heading: 4 PREPROCESSING AND TRAINING
text: Preprocessing We split on special characters and camelCasing (see Fig. 2). Since many of these strings are compositional, tokenizing in this fashion allows the network to take advantage of this fact. This results in a large variance in sequence lengths (min 20, max 338), with an average sequence length of 80.84 tokens.
Training All models were trained for 75 epochs with a batch size of 32, a hidden size of 512, and a word vector size of 300. Dropout is used on every layer of all GRUs except the output layer, with a drop probability of 0.5. Where Glove vectors (Pennington et al. (2014)) are used to initialize word vectors, we use 300-dimensional vectors trained on Wikipedia and Gigaword (6B.300D). The Adam optimizer (Kingma & Ba (2014)) was used, with a learning rate of 1e−4 and a teacher forcing (Williams & Zipser (1989) probability of 0.5. These hyperparameters were tuned for our Seq2Seq baselines and held constant for the rest of the models (Copynet, Coverage, Scratchpad). The vocabulary consists of all tokens appearing at least once in the training set.

heading: 5 EXPERIMENTAL RESULTS

heading: 5.1 DATA
text: We use a standard dataset for semantic parsing, WebQuestionsSP (tau Yih et al. (2016)), which consists of (question, logical form) pairs where the logical form is in SPARQL. The dataset contains 3098 training examples, with additional 1639 for testing. All the following results are reported for the test fold.
In addition to knowledge base question generation, we evaluate our approach on the task of generating questions from SQL statements. For this we use the WikiSQL dataset (Zhong et al. (2017)), and report the results in Appendix A.

heading: 5.2 BASELINES
text: We compare our Scratchpad Encoder against 4 baselines: (1) Seq2Seq, (2) Seq2Seq with Priors, (3) Copynet, and (4) Coverage which is a method from machine translation that aims to solve attention-based coverage problems (Tu et al. (2016)). Seq2Seq is the standard approach introduced in (Sutskever et al. (2014)), whereas “Seq2Seq + Priors” has word vectors initialized from glove embeddings, uses beam search, and uses smarter preprocessing (replace entity IDs with full entity names). Copynet (He et al. (2017)) baseline gives the Seq2Seq model the ability to copy vocabulary from the source to the target, as detailed in equation 7. Table 1 provides a comparison of all the baselines.
Coverage Baseline Our final baseline is a copy-enhanced seq2seq model with attention with a neural “coverage” mechanism added as in Tu et al. (2016). It was originally introduced for the task of machine translation to address the problems of over and under translation. To do so, they add a “coverage vector” (covit) for each position (ht) in the encoder outputs, to keep track of the history of (copy) attentions (c0t ..c i−1 t ) so far.:
covit = f (1)(covi−1t , [s i post read; ht; c i t]) (15)
This requires adding an additional RNN to the model (f(1)). Each coverage vector (covit) is now taken into account when calculating the distribution for copying (cit, Eq. 9), which also affects the calculation of the copy-read (attnicopy, Eq. 10). This is done by modifying the calculation of copy scoreit from Eq. 8 to:
copy scoreit = W 1(W2[sipost read; ht; cov i−1 t ] T) (16)
For a fair comparison, we compare against a coverage vector of size 10, the largest used in Tu et al. (2016).

heading: 5.3 QUANTITATIVE EVALUATIONS
text: In order to quantitatively evaluate the performance of methods, we compute BLEU (for a precisionbased metric), ROUGE-LCS (for a recall-based metric), and METEOR (to deal with stemming and synonyms). We run these metrics at both a corpus level (i.e. how natural are output questions), and at a per-sentence level (i.e. how well do output questions exactly match the gold question). We evaluate on examples in the test set that do not contain out of vocabulary tokens. Table 2 shows the performance of each baseline on all three metrics. From the table it is clear that our approach, Scratchpad Encoder, outperforms all baselines on all the metrics.

heading: 5.4 HUMAN EVALUATION
text: Although quantitative metrics such as BLEU tend to correlate with human judgments for machine translation tasks (Bojar et al. (2017)), they do not always correlate with the human assessed quality of generated text for all tasks (Stent et al. (2005); Liu et al. (2016)). We use two standard human evaluation metrics from the machine translation community: (1) Adequacy, and (2) Fluency (Bojar et al. (2017)). In computing the adequacy metric, human judges are presented with a reference translation and the system proposed translation, and are asked to rate the adequacy of the proposed translation in conveying the meaning of the reference translation on a scale from 0-10. For fluency, the judges are asked to rate, on a scale from 0-10, whether the proposed translation is a fluent English sentence. Table 4 summarizes the human evaluation results for our Scratchpad Encoder and two more baselines. As the table shows, the judges assigned higher fluency and adequacy scores to our approach than the coverage based decoder and the copynet one. In the table we also report the fluency score of the gold questions as a way to measure the gap between the generate questions and
the expected ones. Our approach is nearly 2 full points behind the gold when it comes to generation fluency.
In addition to adequacy and fluency, we design a side-by-side experiment to find out which approach generates better questions in pairwise comparison fashion. In the study, judges are presented with 2 generated questions from 2 different systems, along with the reference question and are asked which of the two systems presents a better paraphrase to the reference question. The judges took into consideration the grammatical correctness of the question and its ability to capture the meaning of the reference question fluently. Table 5 shows the result of running the head-to-head evaluation between scratchpad output and both copynet and coverage baselines. As the table shows, human judges are four times as likely to prefer scratchpad generated questions over copynet, and nearly two times over coverage. Table 7 shows examples of generated questions by the different approaches.

heading: 6 RELATED WORK
text: In the question generation domain, there has been a recent surge in research on generating questions for a given paragraph of text (Song et al. (2017); Du et al. (2017); Tang et al. (2017); Duan et al. (2017); Wang et al. (2018); Yao et al. (2018)). This work focuses on applications for machine reading comprehension where a paragraph coupled with a snippet containing the answer are used to generate questions. This approach arguably contains more contextual information to help guide the
model than using only a logical form, sometimes syntactic manipulation of the answer paragraph alone is sufficient to generate a question. In general, most of the work in this area has been a variant of the seq2seq approach. In Song et al. (2017), a seq2seq model with copynet and a coverage mechanism (Tu et al. (2016)) is used to achieve state-of-the-art results. We have demonstrated that our Scratchpad Encoder outperforms this approach in both quantitative and qualitative evaluations.
In the knowledge based question generation domain, early work on translating SPARQL queries into natural language focused on generating a human readable description of SPARQL queries to guide query writers (Ngonga Ngomo et al. (2013a;b))). However, that approach relied on hand-crafted rules to translate certain words appearing in the SPARQL query. Later work on automatically generating questions from SPARQL queries have also relied on manually crafted templates to map selected categories of SPARQL queries to questions (Trivedi et al. (2017); Seyler et al. (2017)). In Serban et al. (2016) knowledge base triplets are used to generate questions using encoder-decoder framework that operates on entity and predicate embeddings trained using TransE (Bordes et al. (2011)). Later, Elsahar et al. (2018) extended this approach to support unseen predicates. Both approaches operate on triplets, meaning they have limited capability beyond generating simple questions. Since our approach operates on the more expressive SPARQL query (logical form) we can produce far more complex questions.
Summarizing source code is another area where we draw inspiration (Iyer et al. (2016)). Approaches in this area are largely based on attentive seq2seq models, although an Abstract Syntax Tree aware encoder was introduced recently (Alon et al. (2018)). Code summaries tend to be more descriptive than our factoidal question generation. In the dataset provided by (Iyer et al. (2016)) the examples were collected from StackOverFlow, where the questions are generally about how to fix a piece of code. SQL queries bear a striking resemblance to SPARQL, so we test approach on the Zhong et al. (2017) dataset, where we to generate questions from SQL statements. The experiments presented in Appendix A, demonstrate the same performance gains obtained on the WebQuestionsSP dataset, outperforming all baselines.
Closest to our work, in the general paradigm of seq2seq learning, is the coverage mechanism introduced in Tu et. al Tu et al. (2016) and later adapted for summarization in See et al. (2017). Both works try to minimize erroneous repetitions generated by a copy mechanism by introducing a new vector to keep track of what has been used from the encoder thus far. In Tu et al. (2016), for example, use an extra GRU to keep track of this information, whereas See et al. (2017) keeps track of the sum of attention weights and adds a penalty to the loss function based on it to discourage repetition. Our approach is much simpler than either solution since it does not require any extra vectors or an additional loss term; rather, the encoder vector itself is being used as scratch memory. Our experiments also show that for the question generation task, the Scratchpad Encoder performs better than coverage based approaches.
Our idea was inspired by the dialogue generation work of Eric & Manning (2017) in which the entire sequence of interactions is re-encoded every time a response is generated by the decoder. This has also been explored in Elbayad et al. (2018) to great effect. Unfortunately, all of these methods have an O(n2) runtime, which scales poorly with long sequences and large input examples. In addition, vast amounts of memory are required during training to implement Eric & Manning (2017) or Elbayad et al. (2018)). Whereas our module isO(n) in runtime, and does not add memory beyond a constant factor. Finally, our work is very similar to the research done on using external memories for generation (e.g., Bordes et al. (2016); Eric et al. (2017)) and could be viewed as more efficient way to initialize such an external memory.

heading: 7 CONCLUSION
text: In this paper, we addressed the task of generating factoidal questions from a knowledge base using SPARQL queries as input. We introduced a novel write operator to the seq2seq framework, which we call a Scratchpad Encoder. The Scratchpad Encoder helps the decoder to keep track of what tokens have been generated so far, and guide future generation. It outperforms multiple baselines including Seq2Seq, Copynet, and Coverage, in both quantitative evaluations and in human judgments Our module is conceptually simple and easy to add to any seq2seq model with attention.

heading: APPENDIX A GENERATING QUESTIONS FROM SQL
text: To demonstrate the generalizable nature of this approach we also evaluate the Scratchpad Encoder on the WikiSQL dataset Zhong et al. (2017), where our task becomes generating natural language questions from SQL statements. We perform the same preprocessing applied to the WebQuestionsSP dataset, and train along with the same baselines from before (Seq2Seq with priors, Copynet, and Coverage). The quantitative results are given in Table 6. From the table it is clear that our approach outperforms all baselines on all metrics. Furthermore, the improvement is consistent with the performance gains obtained on the WebQuestionsSP, indicating the efficacy of this approach across logical form formats.

heading: APPENDIX B ANALYSIS OF OVERCOPYING
text: As our approach was introduced to help the decoder keep track of what has been generated (and copied) so far, we introduce a metric for over copying which is defined as the difference between the number of times a word type (w) is present in reference text (r) compared to the generated text (g)
OverCopy(corpus) =
∑ ExampleOverCopy(r, g)
Size(corpus) (17)
ExampleOverCopy(r, g) = ∑ w max(delta[w], 0) (18)
delta[w] = Countp[w]− Countg[w] (19)
On the WebQuestionsSP dataset, our approach achieves an average corpus wide over copying score of 0.23, whereas coverage and copynet achieve 0.32 and 0.66, respectively. Our approach reduces over copying by 28% over the next best approach.
Recall that copying was found very useful for question generation since a question typically shares the same vocabulary with the logical form. Table 8 shows examples highlighting the shared tokens between questions and logical forms.

heading: APPENDIX C MODEL DIAGRAM
text: The following diagram outlines the interactions between the different components of the system. Boxes are annotated with the corresponding equation where applicable.

Review summaries:
The paper studies the problem of question generation from sparql queries. The motivation is to generate more training data for knowledge base question answering systems to be trained on. However, this task is an instance of natural language generation: given a meaning representation (quite often a database record), generate the natural language text correspoding to it. And previous work on this topic has proposed very similar ideas to the scratchpad proposed here in order to keep track of what the neural decoder has already generated, here are two of them: