Translate First Reorder Later: Leveraging Monotonicity in Semantic Parsing (2023)

Abstract: Prior work in semantic parsing has shown that conventional seq2seq models fail at compositional generalization tasks. This limitation led to a resurgence of methods that model alignments between sentences and their corresponding meaning representations, either implicitly through latent variables or explicitly by taking advantage of alignment annotations. We take the second direction and propose TPol, a two-step approach that first translates input sentences monotonically and then reorders them to obtain the correct output. This is achieved with a modular framework comprising a Translator and a Reorderer component. We test our approach on two popular semantic parsing datasets. Our experiments show that by means of the monotonic translations, TPol can learn reliable lexico-logical patterns from aligned data, significantly improving compositional generalization both over conventional seq2seq models, as well as over other approaches that exploit gold alignments.

## introduction the goal of a semantic parser is to map natural language sentences (nls) into meaning representations (mrs). most current semantic parsers are based on deep sequence-to-sequence (seq2seq) approaches and presume that it is unnecessary to model token alignments between nls and mrs because the attention mechanism can automatically learn the correspondences @xcite . however, recent work has shown that such seq2seq models find compositional generalization challenging, i.e., they struggle to predict unseen structures made up of components observed at training @xcite . this limitation motivated the resurgence of approaches that model alignments between nl sentences and their corresponding mrs more similarly to classical grammar and translation-based parsers @xcite . alignments can be modeled either implicitly through latent variables @xcite , or explicitly by leveraging gold alignment annotations @xcite . we take the second direction and exploit a recently released multilingual dataset for semantic parsing annotated with word alignments: geoaligned @xcite , which augments the popular geo benchmark @xcite . ## related work recently, the semantic parsing community has raised the question of whether current models can generalize compositionally, along with an effort to test for it @xcite @xcite . the consensus is that conventional seq2seq models struggle to generalize compositionally @xcite . moreover, large pre-trained language models have been shown not to improve compositional generalization @xcite . this has prompted the community to realize that parsers should be designed intentionally with compositionality in mind @xcite @xcite . it has also been pointed out that compositional architectures are often designed for synthetic datasets and that compositionality on non-synthetic data is under-tested @xcite . data augmentation techniques have been proposed to improve compositional generalization @xcite @xcite . another strategy is to exploit some level of word alignments. in general, there has been a resurgent interest in alignments as it has been shown that they can be beneficial to neural models @xcite . it has also been conjectured that the lack of alignment information might hamper progress in semantic parsing @xcite . as a result, the field has seen some annotation efforts in this regard @xcite @xcite . alignments have been modeled implicitly: @xcite treat alignments as discrete structured latent variables within a neural seq2seq model, employing a framework that first reorders the nl and then decodes the mr. explicit use of alignment information has also been explored: herzig and berant (2021) use alignments and predict a span tree over the nl. @xcite recently proposed an approach to data augmentation via sub-tree substitutions. in text-to-sql, attention-based models that try to capture alignments have been proposed @xcite , as well as attempts that try to leverage them directly @xcite . our two-step approach resembles statistical machine translation, which decomposes the translation task into lexical translation and reordering @xcite . machine translation techniques have previously been applied to semantic parsing. the first attempt was by @xcite , who argued that a parsing model can be viewed as a syntax-based translation model and used a statistical word alignment algorithm. later a machine translation approach was used on the geo dataset, obtaining what was at the time state-of-the-art results @xcite . more recently, @xcite employed machine translation to aid semantic parsing. ## preliminaries: word alignments this section briefly explains word alignments, showing the difference between monotonic and non-monotonic alignments, and illustrates the notion of monotonic translations. assume that we have a pair of sequences @xmath0, . . . , x n and @xmath1, . . . , y m , where n and m are the respective sequence lengths. a bi-sequence is defined as the tuple (x, y). in our application, x is a nl sentence, and y is its corresponding mr. for example: a word alignment is a set of bi-symbols a, where each bi-symbol defines an alignment from a token in the nl to a token in the mr. for instance, the bi-symbol (x i , y j ) aligns token x i to token y j . in our example, the tokens "which" and "answer" could be paired by a bi-symbol (which, answer). if a token x i does not align to anything in y, an ε is introduced in y: the resulting bi-symbol (x i , ε) corresponds to a deletion. in our example, the token "has" in the nl can be deleted with a bi-symbol (has, ε). similarly, if a token y j is not aligned to a token in x, an ε is introduced in x: (ε, y j ) is an insertion. in our example, the token "all" in the mr is inserted with bi-symbol (ε, all). the bi-symbols in a are all one-to-one. hence, to map a single token to a phrase, i.e., to multiple tokens, it is necessary to choose a head token in the phrase, while the remaining tokens require insertion or deletion. in our example, the token "density" in the mr corresponds to "population density" in the nl, and, if "density" is chosen as the head token in the nl, "population" needs a deletion: the alignment will be given by the bi-symbols (population, ε) and (density, density). 1 following this strategy, this notation can account for one-tomany and many-to-one alignments with deletion and insertion operations. figure 2a shows a possible bi-sequence word alignment for the aforementioned example. each bi-symbol is conveniently represented by a horizontal line connecting the tokens it aligns. alignments can be monotonic or non-monotonic. an alignment is monotonic if it does not involve any crossing, i.e., a mapping that does not require reordering tokens. in our example, the alignment is non-monotonic because the bi-symbol (city,city) crosses over others. by permuting the mr, we can obtain a monotonic translation of the nl: figure 1 locatelli and quattoni (2022) showed that annotators are consistent in the way they pick head-tokens, and reported high inter-annotator agreement scores on geoaligned. 2b shows such permutation. the next section illustrates how tpol can leverage these translations. ## translate first reorder later we propose tpol, a two-step parsing approach with a modular framework made up of two components: a monotonic translator and a reorderer. figure 3 shows how our semantic parser takes an input sentence x and predicts the corresponding mr y. in the first step, x is fed to the translator, which outputs a monotonic translation z. in other words, z is the target mr that has been permuted so that it aligns monotonically to the input nl. then, in a second step, z is fed to the reorderer, which is trained to place the mr tokens back into the correct order to produce the final prediction y. the main idea behind tpol is decomposing the task into lexical translation and reordering, to learn more reliable translation patterns. we purport that modeling monotonic alignments eases the learning of novel pattern combinations of seen structures, improving compositional generalization. an alternative approach would be to permute the nl inputs rather than the mrs monotonically. we do not follow this direction due to the observation that in semantic parsing, multiple nls can map to the same mr. in other words, the nl domain is larger than that of the mrs, and thus we believe that learning to reorder the mrs is more feasible. ## error analysis the results indicate the exact-match accuracy achieved by the two modules: we can check whether the model struggles more with the trans-lation or reordering step. to analyze the translator's performance, we regard the monotonically aligned mrs as the gold truth. for the reorderer, we provide it with the monotonically aligned mrs in input. in other words, the evaluation of the reorderer assumes that the translator makes a correct prediction. the performance of the two modules is fairly similar, and, by comparing these results with surprisingly, mbart shows the opposite trend on the query partition, with the non-monotonic accuracy being higher than the monotonic one. by contrast, most of tpol's improved performance comes from better modeling of the monotonic sequences (67.1% → 93.7%). tpol's results suggest that regular patterns in the non-monotonic sequences can be learned. its generalization problems can be attributed to the difficulty of learning the more challenging non-regular patterns in a small dataset. on the other hand, mbart appears to have the capacity to model these challenging reorderings better. still, this comes at the cost of failing on the regular monotonic ones, leading to a lower performance overall. interestingly, the spanbased approach shows a similar improvement on monotonic sequences compared to mbart (67.1% → 89.6%). this suggests that exploiting lexico-logical alignments allows models to capture the simpler patterns that mbart fails to learn. most of tpol's gains over spanbased come from better modeling the non-monotonic examples in the query partition (39.8% → 69.9%). this shows that the two-step approach offers the best of both worlds: it can capture the simple monotonic patterns while maintaining reasonable performance over the more complex alignments on which spanbased fails. figure 4 shows the average drop in performance of the different models trained with automatic ibm alignments compared to the same model trained with gold alignments. we also report the corresponding alignment error, calculated as the percentage of bi-symbols that differ from the gold annotations from geoaligned. we observe that, in general, higher alignment error is associated with a higher drop in performance. this validates the importance of the alignment information and points to improving the unsupervised alignment algorithm as a natural line of future work. we believe that one possible reason for the drop in performance when training with ibm alignments might be because the geo dataset is of relatively small size, and the ibm models might have difficulty learning good alignments. that would explain why in contrast to geo, the performance over scan is not affected by automatic alignments since scan is a much larger dataset. ## architecture study we emphasize here that our approach is an abstract, high-level methodology and does not place any constraint on the underlying architectures of the two components. we believe that different architectures, particularly specialized ones for each module, could be beneficial for parsing performance. we encourage further work to be carried out in this regard. to this purpose, we present some architectural studies using bert @xcite and mbart @xcite as components. we employ them as both translator and reorderer, examining all possible combinations. as explained in section 4.1, mbart is used as a standard seq2seq model, and bert is employed with a classification head to function as a tagger for every input token. additionally, when mbart is used as a reorderer, we introduce a silver training setting. in the normal setting, the reorderer is trained by taking the gold alignment annotations and outputting the meaning representation. in the silver setting, we use the predictions of the translator model as training input. by doing so, the reorderer trains on inputs that mimic more closely what it will actually receive at test time: this is done straightforwardly for a seq2seq model like mbart, while for our bert tagger, every token in input needs to be aligned with a token in output, and when the input is corrupt it is not possible to achieve the same training technique. in we can discern trends in different architecture combinations, which can be helpful when choosing an architecture for a specific task. one important observation is that the architectures that use bert as a translator are consistently better than the ones using mbart over the compositional partitions. we hypothesize that the bert translator can achieve higher compositional generalization because it can better leverage alignment information to predict unseen combinations of observed training patterns. we believe this is because a tagger's predictions can be more naturally broken into parts that can be recombined. in contrast, encoderdecoder architectures fare better on the iid partition but struggle to generalize to unseen patterns. one possible reason is that these models have a harder time inducing local patterns that can be recombined since they encode and decode complete structures all at once. ## conclusion seq2seq models have become increasingly popular in semantic parsing. however, they are limited in their abilities to generalize to unobserved structures. here, we proposed tpol: a two-step parsing approach that leverages alignment annotations with a modular framework composed of a translator and a reorderer. we showed that tpol improves compositional generalization over conventional seq2seq models and over competing models that also leverage alignment information. our results also showed that our approach is robust when trained with automatically generated alignments, demonstrating competitive results on two semantic parsing datasets. we have experimented with two possibilities for the translator and reorderer, but we believe that different architectural components could further improve performance. the divide-and-conquer strategy of breaking the problem into two simpler sub-tasks is designed to enable further component specialization.