Compositional Generalization without Trees using Multiset Tagging and Latent Permutations

Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics Volume 1: Long Papers, pages 14488–14506 July 9-14, 2023 ©2023 Association for Computational Linguistics Compositional Generalization without Trees using Multiset Tagging and Latent Permutations Matthias Lindemann1 and Alexander Koller2 and Ivan Titov1,3 1 ILCC, University of Edinburgh, 2 LST, Saarland University, 3 ILLC, University of Amsterdam m.m.lindemann@sms.ed.ac.uk, koller@coli.uni-saarland.de, ititov@inf.ed.ac.uk Abstract Seq2seq models have been shown to struggle with compositional generalization in semantic parsing, i.e. generalizing to unseen composi- tions of phenomena that the model handles cor- rectly in isolation. We phrase semantic parsing as a two-step process: we first tag each input token with a multiset of output tokens. Then we arrange the tokens into an output sequence using a new way of parameterizing and pre- dicting permutations. We formulate predict- ing a permutation as solving a regularized lin- ear program and we backpropagate through the solver. In contrast to prior work, our approach does not place a priori restrictions on possible permutations, making it very expressive. Our model outperforms pretrained seq2seq models and prior work on realistic semantic parsing tasks that require generalization to longer exam- ples. We also outperform non-tree-based mod- els on structural generalization on the COGS benchmark. For the first time, we show that a model without an inductive bias provided by trees achieves high accuracy on generalization to deeper recursion depth.1 1 Introduction Sequence-to-sequence models have been very suc- cessfully applied to many structural tasks in NLP such as semantic parsing. However, they have also been shown to struggle with compositional gener- alization (Lake and Baroni, 2018; Finegan-Dollak et al., 2018; Kim and Linzen, 2020; Hupkes et al., 2020), i.e. the model fails on examples that contain unseen compositions or deeper recursion of phe- nomena that it handles correctly in isolation. For example, a model which correctly parses ‘Mary knew that Jim slept’ should also be able to parse sentences with deeper recursion than it has seen during training such as ‘Paul said that Mary knew that Jim slept’. This sort of generalization is easy for humans but challenging for neural models. 1https://github.com/namednil/multiset-perm Figure 1: We model seq2seq tasks by first predicting a multiset (dashed boxes) for every input token, and then permuting the tokens to put them into order. We realize the permutation using the red edges: if there is an edge from token i to j, then i is the predecessor of j in the output. Every token is visited exactly once. In order for a model to generalize composition- ally in semantic parsing, it has to identify reusable ‘fragments’ and be able to systematically combine them in novel ways. One way to make a model sen- sitive to fragments is to make it rely on a tree that makes the compositional structure explicit. How- ever, this complicates the training because these trees need to be obtained or induced. This is compu- tationally demanding or at least requires structural preprocessing informed by domain knowledge. In this paper, we propose a two-step …

Content truncated to 500 words