Compositional Generalization in Semantic Parsing (EMNLP 2021 paper notes)

Compositional generalization refers to the ability of systems to re-use elements in novel contexts. The recent few years saw several papers emerging on this topic. In this post, continuing from my previous posts, I’ll list some papers from EMNLP 2021 that focused on compositional generalization in semantic parsing and provide notes that summarize their findings. Note that other papers on compositional generalization, for example those in language grounding, are not included.

Finding needles in a haystack: Sampling Structurally-diverse Training Sets from Synthetic Data for Compositional Generalization

(Oren et al.) Paper PDF

This paper investigates the effect of pre-training using synthetic data on compositional generalization with real data. They show that pre-training with synthetic data is beneficial both in i.i.d. and compositionally challenging setups and then propose a method for sampling synthetic data that leads to more efficient training (using less examples). The experiments are performed using Schema2QA, a question answering dataset over tables.

The basic setup is simple: (1) train a seq2seq model on synthetic data and (2) fine-tune it on the real i.i.d. data. Then, test how well the resulting model works on a compositionally challenging test set. The authors construct the test set following an approach similar to Finegan-Dollak et al. (2018), where the queries are first abstracted to obtain templates and are then split such that the templates of the test set are never observed during training. Note that the authors start from a pre-trained model (BART, Lewis et al. 2020).

The authors experiment with different synthetic data sampling methods:

(1) uniform sampling (Uniform), where every synthetic training example is equally likely to be sampled

(2) uniform abstract template (UAT), where first an abstract template is sampled more or less uniformly and then an example that follows that template is sampled. This creates a more uniform distribution over templates, enforcing more structural diversity on the training data.

(3) compound maximum entropy (CMaxEnt), where the entropy over compounds is maximized. This can be seen as an extension of UAT. Where UAT does not take into account the similarities between templates, in terms of its substructures, CMaxEnt does.

(4) compound maximum entropy and uniform abstract template (CMaxEnt+UAT), that combines both by first sampling a template uniformly and then using CMaxEnt.

Test accuracies in different settings (this is Table 5 from paper)

From the results, we can see some interesting findings:

(1) more synthetic data help more for compositional generalization,

(2) overall, the simple UAT data sampling procedure yields the best results,

(3) using smarter data sampling, we can achieve larger gains in compositional generalization using much less data.

Some thoughts: While the findings are interesting, it is not clear how this compares in the context of other work on compositional generalization. The GECA baseline is extremely simple and is only one of many approaches developed in recent years. Another possible limitation is the assumption that it is practically feasible to generate high-quality synthetic data.

Inducing Transformer’s Compositional Generalization Ability via Auxiliary Sequence Prediction Tasks

(Jiang and Bansal) Paper PDF

Some of the earlier works using the SCAN dataset (Russin et al. 2020, Li et al. 2019) proposed a model that separates the syntactic and semantic information about tokens to achieve better generalization to primitives that are not observed in context during training. In this work, the authors extend the CGPS approach of Li et al. to transformers.

Here, the model is a transformer where the input is processed in two parallel streams: (1) contextualized and (2) un-contextualized. In the first stream, the input is first embedded, then encoded using a transformer to form a contextualized representation and finally used in the decoder as usual. The decoder builds up its output representation vectors using the contextualized input representation. However, instead of also predicting the output relying on the contextualized input representations, we actually use the decoder states in an additional layer of multi-head cross-attention. This is where the second, un-contextualized input representations come in (these are simply tokens embedded using a separate embedding matrix; they are not further encoded). The decoder representations are the queries, the contextualized encoder representations are the keys and the un-contextualized encoder representations are used as values. So in the end, the contextualized (“syntactic”) input representations are used for attending to the input while the un-contextualized (“semantic”) representations are used for the selection of the decoded token. This basic model already solves the primitive generalization problem where we need to generalize to using tokens that have previously only been observed in isolation (Add_Jump in SCAN). However, it still performs poorly on MCD splits and length-based splits.

The authors propose to extend this simple approach to also include the modeling of auxiliary sequences that explicitly encode the query structure. The first auxiliary sequence tracks the progress of repeated action sequences while the second auxiliary sequence tracks the progress inside action sequences. See table below for examples.

The model is accordingly adapted in order to incorporate and produce the auxiliary sequences. Two additional embedding matrices are included in the decoder (the three embeddings are simply summed up). An additional multi-head attention is added that uses the outputs of the first (!) decoder layer as queries, input embeddings (before encoder) as keys and contextualized input representations as values.

From the experimental results, we can see that the Add_Jump primitive generalization setting is solved rather well using the simple CGPS-Transformer. However, it fails on other generalization types. When using the auxiliary sequence prediction though, it solves all tested tasks nearly perfectly. From few-show learning ablation studies, it appears that using only 5% of the training data already yields high dev accuracies.

Some thoughts: while the results, especially the few-shot performance are very compelling given the simplicity of the approach, it is unclear how to extend the presented approach to improve compositional generalization to more realistic settings like CFQ. The auxiliary sequences designed in this paper seems very specifically tailored to the SCAN task.

Grounded Graph Decoding Improves Compositional Generalization in Question Answering

(Gai et al.) Paper PDF

First, the authors point out that conjunctive queries (like in the CFQ dataset) can be represented as a graph where nodes are entities or variables and edges are predicates. For example, “direct(x, Inception) AND produce(x, Inception)” can be represented as a graph with the variable node “x”, entity node “Inception” and edges “x — produce→ Inception” and “x — direct→ Inception”.

The authors propose a graph decoder that computes embeddings for nodes and predicts edges. So, given a question, its tokens q_i are concatenated together with the variable tokens x_i, as follows:

Then, this is encoded using a sequence encoder model.

The probability of an edge is modeled simply as

where h_s and h_o are the contextualized embeddings of the subject and object entities.

Then the authors argue that the encoder lacks compositionality and can not model syntactic compositions. Because the authors found syntactic parses by the Stanford parser to have a high error rate, they instead build groups based on the simple pattern “A and B” where A and B share the same POS tag. After detecting such groups, the embeddings of each group are computed as the sum of the vectors for their elements:

It is then these groups that are fed to the encoder instead of words:

The probability of an edge is now modeled as:

Eq 3 from paper

where an entity is represented by its group’s vector.

To further improve results, the authors propose to use an attention-based grounding mechanism:

Unnumbered eq (let’s call it Eq 3)*

where z_{s,o} is an attention-based summary of the sequence. The attention uses both h_s and ho as query and seems to attend over groups (I found the notation in this part confusing and inconsistent with earlier explanation, e.g. Eq. 3* is using h’s instead of g’s while the text says we only add z{s,o} to Eq. 3).

The authors present final results in two settings: (1) not tuning on validation set and (2) with tuning on validation set. The authors note that Keysers et al. provide a validation set from the same distribution as the test set. Keysers et al. argue against using the validation set for model selection because we should not have any knowledge of the specific correlations in the test data. Nevertheless, according to the authors of the discussed paper, it appears that many previous works (incl. Herzig et al. 2021, Das et al. 2021, Guo et al. 2020) used this development set.

The results comparing to other work are displayed below. The proposed method appears to solve the MCD1 split nearly perfectly. It must be noted that the other methods that are compared are general-purpose decoders that are not limited to decoding conjunctive query graphs, and were, for example also evaluated on SCAN.

Comparison against more recent work that uses the development set (see table below) shows that the obtained results are competitive with previous work. While the proposed work appears to be solving MCD1 nearly perfectly, it performs worse on the other MCD splits of CFQ. It is not clear what the variance on these results is since the authors do not report standard deviation and there is no mention of seeds in the paper. Another point to note is that when averaged over the three MCD splits, the proposed method obtains 81.3% accuracy, which is worse than the best listed method of Herzig et al. (2021) at 83.9%.

The Devil is in the Detail: Simple Tricks Improve Systematic Generalization of Transformers

(Csordás et al.) Paper PDF

In this work, the authors revisit some compositional generalization datasets (including COGS, SCAN and CFQ), and transformer baselines, and show that (1) using relative positioning improves results (especially on EOS prediction with SCAN), (2) early stopping on IID data can result in poor performance on the generalization set and in general, the lack of a OOD dev set makes proper model selection and early stopping difficult, and finally (3) embedding scaling can result in significant differences in performance.

ONLY switching to relative positioning instead of absolute positions in the transformers appears to solve SCAN’s length generalization task for splits at length 26 or longer. Recall that SCAN’s length-based split simply uses the shortest examples for training and the longest for testing generalization, and the cutoff length determines if an example belongs in training or test. Splits at a shorter length appear to suffer from missing compositions, as already noted by previous work.

The authors also show that early stopping based on IID performance can result in dramatic drops in measured performance on the generalization set. When they disabled early stopping in their COGS experiments, the generalization set accuracy increased from 35% to 81%:

The authors point to the general problem that the existing datasets typically do not provide an OOD dev set that could be used for proper model selection and early stopping. In fact, many models and configurations achieve near-100% accuracy on IID data, and thus do not provide much empirical reason to select any model or hyperparameter configuration over the other. In addition, the accuracy on IID and OOD data does not need to correlate, as shown in the last figure above, where the IID-based early stopping terminates training at a point where the accuracy on the generalization set is still much lower.

This figure also shows the effects of embedding scaling. Since the range of the sinusoidal absolute position embeddings in the original transformers is between -1 and +1, and thus larger than that of the token embeddings, the token embeddings are usually up-scaled in transformers (this is TEU or Token Emb. Up.). The authors show in their paper that actually down-scaling the position embeddings behaves better and leads to better accuracy.

The authors provide more findings in the paper and I think it’s worth reading.

Some thoughts: this paper points to a flaw in the current state of evaluation in compositional generalization for semantic parsing. Most commonly used datasets, such as CFQ and COGS, do not provide OOD dev sets that can be used for model selection and early stopping. The OOD dev set of CFQ is from exactly the same data distribution as the test set, and thus should not be used during model training. On the other hand, as shown in this paper, using an IID dev set for hyperparameter tuning and comparison is difficult because many configurations reach very high accuracy and early stopping can result in a poorly generalizing model.

Compositional Generalization via Semantic Tagging

(Zheng and Lapata) Paper PDF

In this paper, a two-stage decoding approach is presented, where first, the input sequence is annotated with semantic (output) symbols and then, the output query is generated based on both the input sequence and its tags. The approach is illustrated in the figure below.

The input tagging model is a simple sequence tagging model that uses bidirectional LSTM’s and produces one token from the output vocabulary for every input token. Note that transformers could have been used here too.

For the second step, a seq2seq model is used that takes both the embeddings of the input words, as well as the previously produced tags as the representatinos for every input position.

The proposed approach is relatively straightforward, however, a complication arises in the training of the tagger model for the first decoding stage. We only have supervision in the form of sequence pairs, but we usually don’t have alignment information available. For this reason, the authors rely on entity linking and expectation maximization. Entity linking can be used to align some “obvious” cases, for which the authors develop a set of rules. However, this is not always possible for all input positions, so the authors also develop a training method based on expectation maximization (EM). Treating the alignments between input and output sequences as latent variables, in simple terms, EM-based training infers the most probable alignments and then uses these alignments to supervise the training of the tagger. Training the seq2seq model for the second decoding step is straightforward as both input and output sequences are provided.

The approach is evaluated on ATIS, GeoQuery and WikiSQL. Splits from Finegan-Dollak et al. (2018) are used for ATIS and GeoQuery in the SQL setting, and the authors also use query-based splits for the lambda-expressions settings.

From the results, it appears that the semantic tagging helps compositional generalization.

I think these were all the papers at EMNLP last year. If you have any suggestions, please let me know.