Coarse-to-Fine Decoding for Neural Semantic Parsing

Introduction

Semantic parsing maps natural language utterances onto machine interpretable meaning representations (e.g., executable queries or logical forms). The successful application of recurrent neural networks to a variety of NLP tasks Bahdanau et al. (2015); Vinyals et al. (2015) has provided strong impetus to treat semantic parsing as a sequence-to-sequence problem Jia and Liang (2016); Dong and Lapata (2016); Ling et al. (2016). The fact that meaning representations are typically structured objects has prompted efforts to develop neural architectures which explicitly account for their structure. Examples include tree decoders Dong and Lapata (2016); Alvarez-Melis and Jaakkola (2017), decoders constrained by a grammar model Xiao et al. (2016); Yin and Neubig (2017); Krishnamurthy et al. (2017), or modular decoders which use syntax to dynamically compose various submodels Rabinovich et al. (2017).

In this work, we propose to decompose the decoding process into two stages. The first decoder focuses on predicting a rough sketch of the meaning representation, which omits low-level details, such as arguments and variable names. Example sketches for various meaning representations are shown in Table 1. Then, a second decoder fills in missing details by conditioning on the natural language input and the sketch itself. Specifically, the sketch constrains the generation process and is encoded into vectors to guide decoding.

We argue that there are at least three advantages to the proposed approach. Firstly, the decomposition disentangles high-level from low-level semantic information, which enables the decoders to model meaning at different levels of granularity. As shown in Table 1, sketches are more compact and as a result easier to generate compared to decoding the entire meaning structure in one go. Secondly, the model can explicitly share knowledge of coarse structures for the examples that have the same sketch (i.e., basic meaning), even though their actual meaning representations are different (e.g., due to different details). Thirdly, after generating the sketch, the decoder knows what the basic meaning of the utterance looks like, and the model can use it as global context to improve the prediction of the final details.

Our framework is flexible and not restricted to specific tasks or any particular model. We conduct experiments on four datasets representative of various semantic parsing tasks ranging from logical form parsing, to code generation, and SQL query generation. We adapt our architecture to these tasks and present several ways to obtain sketches from their respective meaning representations. Experimental results show that our framework achieves competitive performance compared with previous systems, despite employing relatively simple sequence decoders.

Related Work

Various models have been proposed over the years to learn semantic parsers from natural language expressions paired with their meaning representations Tang and Mooney (2000); Ge and Mooney (2005); Zettlemoyer and Collins (2007); Wong and Mooney (2007); Lu et al. (2008); Kwiatkowski et al. (2011); Andreas et al. (2013); Zhao and Huang (2015). These systems typically learn lexicalized mapping rules and scoring models to construct a meaning representation for a given input.

More recently, neural sequence-to-sequence models have been applied to semantic parsing with promising results Dong and Lapata (2016); Jia and Liang (2016); Ling et al. (2016), eschewing the need for extensive feature engineering. Several ideas have been explored to enhance the performance of these models such as data augmentation Kočiský et al. (2016); Jia and Liang (2016), transfer learning Fan et al. (2017), sharing parameters for multiple languages or meaning representations Susanto and Lu (2017); Herzig and Berant (2017), and utilizing user feedback signals Iyer et al. (2017). There are also efforts to develop structured decoders that make use of the syntax of meaning representations. Dong and Lapata (2016) and Alvarez-Melis and Jaakkola (2017) develop models which generate tree structures in a top-down fashion. Xiao et al. (2016) and Krishnamurthy et al. (2017) employ the grammar to constrain the decoding process. Cheng et al. (2017) use a transition system to generate variable-free queries. Yin and Neubig (2017) design a grammar model for the generation of abstract syntax trees Aho et al. (2007) in depth-first, left-to-right order. Rabinovich et al. (2017) propose a modular decoder whose submodels are dynamically composed according to the generated tree structure.

Our own work also aims to model the structure of meaning representations more faithfully. The flexibility of our approach enables us to easily apply sketches to different types of meaning representations, e.g., trees or other structured objects. Coarse-to-fine methods have been popular in the NLP literature, and are perhaps best known for syntactic parsing Charniak et al. (2006); Petrov (2011). Artzi and Zettlemoyer (2013) and Zhang et al. (2017) use coarse lexical entries or macro grammars to reduce the search space of semantic parsers. Compared with coarse-to-fine inference for lexical induction, sketches in our case are abstractions of the final meaning representation.

The idea of using sketches as intermediate representations has also been explored in the field of program synthesis Solar-Lezama (2008); Zhang and Sun (2013); Feng et al. (2017). Yaghmazadeh et al. (2017) use Sempre Berant et al. (2013) to map a sentence into SQL sketches which are completed using program synthesis techniques and iteratively repaired if they are faulty.

Problem Formulation

Our goal is to learn semantic parsers from instances of natural language expressions paired with their structured meaning representations. Let $x=x_{1}\cdots x_{|x|}$ denote a natural language expression, and $y=y_{1}\cdots y_{|y|}$ its meaning representation. We wish to estimate $p\left(y|x\right)$, the conditional probability of meaning representation $y$ given input $x$. We decompose $p\left(y|x\right)$ into a two-stage generation process:

where $a=a_{1}\cdots a_{|a|}$ is an abstract sketch representing the meaning of $y$. We defer detailed description of how sketches are extracted to Section 4. Suffice it to say that the extraction amounts to stripping off arguments and variable names in logical forms, schema specific information in SQL queries, and substituting tokens with types in source code (see Table 1).

As shown in Figure 1, we first predict sketch $a$ for input $x$, and then fill in missing details to generate the final meaning representation $y$ by conditioning on both $x$ and $a$. The sketch is encoded into vectors which in turn guide and constrain the decoding of $y$. We view the input expression $x$, the meaning representation $y$, and its sketch $a$ as sequences. The generation probabilities are factorized as:

where $a_{<t}=a_{1}\cdots a_{t-1}$, and $y_{<t}=y_{1}\cdots y_{t-1}$. In the following, we will explain how $p\left(a|x\right)$ and $p\left(y|x,a\right)$ are estimated.

An encoder is used to encode the natural language input $x$ into vector representations. Then, a decoder learns to compute $p\left(a|x\right)$ and generate the sketch $a$ conditioned on the encoding vectors.

Coarse Meaning Decoder

where $Z_{t}=\sum_{j=1}^{|x|}{\exp\{{\mathbf{d}}_{t}\cdot{\mathbf{e}}_{j}\}}$ is a normalization term. Then we compute $p\left(a_{t}|a_{<t},x\right)$ via:

2 Meaning Representation Generation

Meaning representations are predicted by conditioning on the input $x$ and the generated sketch $a$. The model uses the encoder-decoder architecture to compute $p\left(y|x,a\right)$, and decorates the sketch $a$ with details to generate the final output.

As shown in Figure 1, a bi-directional LSTM encoder maps the sketch sequence $a$ into vectors $\{\mathbf{v}_{k}\}_{k=1}^{|a|}$ as in Equation (6), where $\mathbf{v}_{k}$ denotes the vector of the $k$-th time step.

Fine Meaning Decoder

The final decoder is based on recurrent neural networks with an attention mechanism, and shares the input encoder described in Section 3.1. The decoder’s hidden states $\{\mathbf{h}_{t}\}_{t=1}^{|y|}$ are computed via:

where ${\mathbf{h}}_{0}=[\overrightarrow{\mathbf{e}}_{|x|},\overleftarrow{\mathbf{e}}_{1}]$, and ${\mathbf{y}}_{t-1}$ is the embedding of the previously predicted token. Apart from using the embeddings of previous tokens, the decoder is also fed with $\{\mathbf{v}_{k}\}_{k=1}^{|a|}$. If $y_{t-1}$ is determined by $a_{k}$ in the sketch (i.e., there is a one-to-one alignment between $y_{t-1}$ and $a_{k}$), we use the corresponding token’s vector $\mathbf{v}_{k}$ as input to the next time step.

The sketch constrains the decoding output. If the output token $y_{t}$ is already in the sketch, we force $y_{t}$ to conform to the sketch. In some cases, sketch tokens will indicate what information is missing (e.g., in Figure 1, token “flight@1” indicates that an argument is missing for the predicate “flight”). In other cases, sketch tokens will not reveal the number of missing tokens (e.g., “STRING” in Django) but the decoder’s output will indicate whether missing details have been generated (e.g., if the decoder emits a closing quote token for “STRING”). Moreover, type information in sketches can be used to constrain generation. In Table 1, sketch token “NUMBER” specifies that a numeric token should be emitted.

For the missing details, we use the hidden vector $\mathbf{h}_{t}$ to compute $p\left(y_{t}|y_{<t},x,a\right)$, analogously to Equations 7–10.

3 Training and Inference

The model’s training objective is to maximize the log likelihood of the generated meaning representations given natural language expressions:

where $\mathcal{D}$ represents training pairs.

At test time, the prediction for input $x$ is obtained via $\hat{a}=\operatorname*{arg\,max}_{a^{\prime}}{p\left(a^{\prime}|x\right)}$ and $\hat{y}=\operatorname*{arg\,max}_{y^{\prime}}{p\left(y^{\prime}|x,\hat{a}\right)}$, where $a^{\prime}$ and $y^{\prime}$ represent coarse- and fine-grained meaning candidates. Because probabilities $p\left(a|x\right)$ and $p\left(y|x,a\right)$ are factorized as shown in Equations 2–3, we can obtain best results approximately by using greedy search to generate tokens one by one, rather than iterating over all candidates.

Semantic Parsing Tasks

In order to show that our framework applies across domains and meaning representations, we developed models for three tasks, namely parsing natural language to logical form, to Python source code, and to SQL query. For each of these tasks we describe the datasets we used, how sketches were extracted, and specify model details over and above the architecture presented in Section 3.

For our first task we used two benchmark datasets, namely Geo ($880$ language queries to a database of U.S. geography) and Atis ($5,410$ queries to a flight booking system). Examples are shown in Table 1 (see the first and second block). We used standard splits for both datasets: $600$ training and $280$ test instances for Geo Zettlemoyer and Collins (2005); $4,480$ training, $480$ development, and $450$ test examples for Atis. Meaning representations in these datasets are based on $\lambda$-calculus Kwiatkowski et al. (2011). We use brackets to linearize the hierarchical structure. The first element between a pair of brackets is an operator or predicate name, and any remaining elements are its arguments.

Algorithm 1 shows the pseudocode used to extract sketches from $\lambda$-calculus-based meaning representations. We strip off arguments and variable names in logical forms, while keeping predicates, operators, and composition information. We use the symbol “@” to denote the number of missing arguments in a predicate. For example, we extract “from@2” from the expression “(from 0 dallas:ci)” which indicates that the predicate “from” has two arguments. We use “?” as a placeholder in cases where only partial argument information can be omitted. We also omit variable information defined by the lambda operator and quantifiers (e.g., exists, count, and argmax). We use the symbol “#” to denote the number of omitted tokens. For the example in Figure 1, “lambda0 e” is reduced to “lambda#2”.

The meaning representations of these two datasets are highly compositional, which motivates us to utilize the hierarchical structure of $\lambda$-calculus. A similar idea is also explored in the tree decoders proposed in Dong and Lapata (2016) and Yin and Neubig (2017) where parent hidden states are fed to the input gate of the LSTM units. On the contrary, parent hidden states serve as input to the softmax classifiers of both fine and coarse meaning decoders.

Taking the meaning sketch “(and flight@1 from@2)” as an example, the parent of “from@2” is “(and”. Let $p_{t}$ denote the parent of the $t$-th time step in the decoder. Compared with Equation (10), we use the vector ${\mathbf{d}}_{t}^{att}$ and the hidden state of its parent ${\mathbf{d}}_{p_{t}}$ to compute the probability $p\left(a_{t}|a_{<t},x\right)$ via:

where $[\cdot,\cdot]$ denotes vector concatenation. The parent feeding is used for both decoding stages.

2 Natural Language to Source Code

Our second semantic parsing task used Django Oda et al. (2015), a dataset built upon the Python code of the Django library. The dataset contains lines of code paired with natural language expressions (see the third block in Table 1) and exhibits a variety of use cases, such as iteration, exception handling, and string manipulation. The original split has $16,000$ training, $1,000$ development, and $1,805$ test instances.

We used the built-in lexical scanner of Pythonhttps://docs.python.org/3/library/tokenize to tokenize the code and obtain token types. Sketches were extracted by substituting the original tokens with their token types, except delimiters (e.g., “[”, and “:”), operators (e.g., “+”, and “*”), and built-in keywords (e.g., “True”, and “while”). For instance, the expression “if s[:4].lower() == ’http’:” becomes “if NAME [ : NUMBER ] . NAME ( ) == STRING :”, with details about names, values, and strings being omitted.

Django is a diverse dataset, spanning various real-world use cases and as a result models are often faced with out-of-vocabulary (OOV) tokens (e.g., variable names, and numbers) that are unseen during training. We handle OOV tokens with a copying mechanism Gu et al. (2016); Gulcehre et al. (2016); Jia and Liang (2016), which allows the fine meaning decoder (Section 3.2) to directly copy tokens from the natural language input.

Recall that we use a softmax classifier to predict the probability distribution $p\left(y_{t}|y_{<t},x,a\right)$ over the pre-defined vocabulary. We also learn a copying gate $g_{t}\in$ to decide whether $y_{t}$ should be copied from the input or generated from the vocabulary. We compute the modified output distribution via:

3 Natural Language to SQL

The WikiSQL Zhong et al. (2017) dataset contains $80,654$ examples of questions and SQL queries distributed across $24,241$ tables from Wikipedia. The goal is to generate the correct SQL query for a natural language question and table schema (i.e., table column names), without using the content values of tables (see the last block in Table 1 for an example). The dataset is partitioned into a training set ($70\%$), a development set ($10\%$), and a test set ($20\%$). Each table is present in one split to ensure generalization to unseen tables.

WikiSQL queries follow the format “SELECT agg_op agg_col WHERE (cond_col cond_op cond) AND …”, which is a subset of the SQL syntax. SELECT identifies the column that is to be included in the results after applying the aggregation operator agg_opagg_op $\in\{empty,\texttt{COUNT},\texttt{MIN},\texttt{MAX},\texttt{SUM},\texttt{AVG}\}$. to column agg_col. WHERE can have zero or multiple conditions, which means that column cond_col must satisfy the constraints expressed by the operator cond_opcond_op $\in\{=,<,>\}$. and the condition value cond. Sketches for SQL queries are simply the (sorted) sequences of condition operators cond_op in WHERE clauses. For example, in Table 1, sketch “WHERE > AND =” has two condition operators, namely “>” and “=”.

The generation of SQL queries differs from our previous semantic parsing tasks, in that the table schema serves as input in addition to natural language. We therefore modify our input encoder in order to render it table-aware, so to speak. Furthermore, due to the formulaic nature of the SQL query, we only use our decoder to generate the WHERE clause (with the help of sketches). The SELECT clause has a fixed number of slots (i.e., aggregation operator agg_op and column agg_col), which we straightforwardly predict with softmax classifiers (conditioned on the input). We briefly explain how these components are modeled below.

Given a table schema with $M$ columns, we employ the special token “‖” to concatenate its header names as “‖$c_{1,1}\cdots c_{1,|c_{1}|}$‖$\cdots$‖$c_{M,1}\cdots c_{M,|c_{M}|}$‖”, where the $k$-th column (“$c_{k,1}\cdots c_{k,|c_{k}|}$”) has $|c_{k}|$ words. As shown in Figure 2, we use bi-directional LSTMs to encode the whole sequence. Next, for column $c_{k}$, the LSTM hidden states at positions $c_{k,1}$ and $c_{k,|c_{k}|}$ are concatenated. Finally, the concatenated vectors are used as the encoding vectors $\{\mathbf{c}_{k}\}_{k=1}^{M}$ for table columns.

SELECT Clause

WHERE Clause

We first generate sketches whose details are subsequently decorated by the fine meaning decoder described in Section 3.2. As the number of sketches in the training set is small ($35$ in total), we model sketch generation as a classification problem. We treat each sketch $a$ as a category, and use a softmax classifier to compute $p\left(a|x\right)$:

Once the sketch is predicted, we know the condition operators and number of conditions in the WHERE clause which follows the format “WHERE (cond_op cond_col cond) AND …”. As shown in Figure 3, our generation task now amounts to populating the sketch with condition columns cond_col and their values cond.

Let $\{\mathbf{h}_{t}\}_{t=1}^{|y|}$ denote the LSTM hidden states of the fine meaning decoder, and $\{\mathbf{h}_{t}^{att}\}_{t=1}^{|y|}$ the vectors obtained by the attention mechanism as in Equation (9). The condition column $\texttt{cond\_col}_{y_{t}}$ is selected from the table’s headers. For the $k$-th column in the table, we compute $p\left(\texttt{cond\_col}_{y_{t}}=k|y_{<t},x,a\right)$ as in Equation (14), but use different parameters and compute the score via $\sigma([\mathbf{h}_{t}^{att},{\mathbf{c}}_{k}])$. If the $k$-th table column is selected, we use $\mathbf{c}_{k}$ for the input of the next LSTM unit in the decoder.

Condition values are typically mentioned in the input questions. These values are often phrases with multiple tokens (e.g., Mikhail Snitko in Table 1). We therefore propose to select a text span from input $x$ for each condition value $\texttt{cond}_{y_{t}}$ rather than copying tokens one by one. Let $x_{l}\cdots x_{r}$ denote the text span from which $\texttt{cond}_{y_{t}}$ is copied. We factorize its probability as:

Experiments

We present results on the three semantic parsing tasks discussed in Section 4. Our implementation and pretrained models are available at https://github.com/donglixp/coarse2fine.

For Geo and Atis, we used the preprocessed versions provided by Dong and Lapata (2016), where natural language expressions are lowercased and stemmed with NLTK Bird et al. (2009), and entity mentions are replaced by numbered markers. We combined predicates and left brackets that indicate hierarchical structures to make meaning representations compact. We employed the preprocessed Django data provided by Yin and Neubig (2017), where input expressions are tokenized by NLTK, and quoted strings in the input are replaced with place holders. WikiSQL was preprocessed by the script provided by Zhong et al. (2017), where inputs were lowercased and tokenized by Stanford CoreNLP Manning et al. (2014).

Configuration

Model hyperparameters were cross-validated on the training set for Geo, and were validated on the development split for the other datasets. Dimensions of hidden vectors and word embeddings were selected from $\{250,300\}$ and $\{150,200,250,300\}$, respectively. The dropout rate was selected from $\{0.3,0.5\}$. Label smoothing Szegedy et al. (2016) was employed for Geo and Atis. The smoothing parameter was set to $0.1$. For WikiSQL, the hidden size of $\sigma(\cdot)$ and $\alpha(\cdot)$ in Equation (13) was set to $64$. Word embeddings were initialized by GloVe Pennington et al. (2014), and were shared by table encoder and input encoder in Section 4.3. We appended $10$-dimensional part-of-speech tag vectors to embeddings of the question words in WikiSQL. The part-of-speech tags were obtained by the spaCy toolkit. We used the RMSProp optimizer Tieleman and Hinton (2012) to train the models. The learning rate was selected from $\{0.002,0.005\}$. The batch size was $200$ for WikiSQL, and was $64$ for other datasets. Early stopping was used to determine the number of epochs.

Evaluation

We use accuracy as the evaluation metric, i.e., the percentage of the examples that are correctly parsed to their gold standard meaning representations. For WikiSQL, we also execute generated SQL queries on their corresponding tables, and report the execution accuracy which is defined as the proportion of correct answers.

2 Results and Analysis

We compare our model (Coarse2Fine) against several previously published systems as well as various baselines. Specifically, we report results with a model which decodes meaning representations in one stage (OneStage) without leveraging sketches. We also report the results of several ablation models, i.e., without a sketch encoder and without a table-aware input encoder.

Table 2 presents our results on Geo and Atis. Overall, we observe that Coarse2Fine outperforms OneStage, which suggests that disentangling high-level from low-level information during decoding is beneficial. The results also show that removing the sketch encoder harms performance since the decoder loses access to additional contextual information. Compared with previous neural models that utilize syntax or grammatical information (Seq2Tree, ASN; the second block in Table 2), our method performs competitively despite the use of relatively simple decoders. As an upper bound, we report model accuracy when gold meaning sketches are given to the fine meaning decoder ($+$oracle sketch). As can be seen, predicting the sketch correctly boosts performance. The oracle results also indicate the accuracy of the fine meaning decoder.

Table 3 reports results on Django where we observe similar tendencies. Coarse2Fine outperforms OneStage by a wide margin. It is also superior to the best reported result in the literature (snm$+$copy; see the second block in the table). Again we observe that the sketch encoder is beneficial and that there is an $8.9$ point difference in accuracy between Coarse2Fine and the oracle.

Results on WikiSQL are shown in Table 4. Our model is superior to OneStage as well as to previous best performing systems. Coarse2Fine’s accuracies on aggregation agg_op and agg_col are $90.2\%$ and $92.0\%$, respectively, which is comparable to SQLNet Xu et al. (2017). So the most gain is obtained by the improved decoder of the WHERE clause. We also find that a table-aware input encoder is critical for doing well on this task, since the same question might lead to different SQL queries depending on the table schemas. Consider the question “how many presidents are graduated from A”. The SQL query over table “‖President‖College‖” is “SELECT COUNT(President) WHERE (College = A)”, but the query over table “‖College‖Number of Presidents‖” would be “SELECT Number of Presidents WHERE (College = A)”.

We also examine the predicted sketches themselves in Table 5. We compare sketches generated by Coarse2Fine against OneStage. The latter model generates meaning representations without an intermediate sketch generation stage. Nevertheless, we can extract sketches from the output of OneStage following the procedures described in Section 4. Sketches produced by Coarse2Fine are more accurate across the board. This is not surprising because our model is trained explicitly to generate compact meaning sketches. Taken together (Tables 2–4), our results show that better sketches bring accuracy gains on Geo, Atis, and Django. On WikiSQL, the sketches predicted by Coarse2Fine are marginally better compared with OneStage. Performance improvements on this task are mainly due to the fine meaning decoder. We conjecture that by decomposing decoding into two stages, Coarse2Fine can better match table columns and extract condition values without interference from the prediction of condition operators. Moreover, the sketch provides a canonical order of condition operators, which is beneficial for the decoding process Vinyals et al. (2016); Xu et al. (2017).

Conclusions

In this paper we presented a coarse-to-fine decoding framework for neural semantic parsing. We first generate meaning sketches which abstract away from low-level information such as arguments and variable names and then predict missing details in order to obtain full meaning representations. The proposed framework can be easily adapted to different domains and meaning representations. Experimental results show that coarse-to-fine decoding improves performance across tasks. In the future, we would like to apply the framework in a weakly supervised setting, i.e., to learn semantic parsers from question-answer pairs and to explore alternative ways of defining meaning sketches.

We would like to thank Pengcheng Yin for sharing with us the preprocessed version of the Django dataset. We gratefully acknowledge the financial support of the European Research Council (award number 681760; Dong, Lapata) and the AdeptMind Scholar Fellowship program (Dong).

References