Compositional Generalization without Trees using Multiset Tagging and Latent Permutations

Matthias Lindemann, Alexander Koller, Ivan Titov


Abstract
Seq2seq models have been shown to struggle with compositional generalization in semantic parsing, i.e. generalizing to unseen compositions of phenomena that the model handles correctly 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 predicting permutations. We formulate predicting a permutation as solving a regularized linear 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 examples. We also outperform non-tree-based models 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.
Anthology ID:
2023.acl-long.810
Volume:
Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
Month:
July
Year:
2023
Address:
Toronto, Canada
Editors:
Anna Rogers, Jordan Boyd-Graber, Naoaki Okazaki
Venue:
ACL
SIG:
Publisher:
Association for Computational Linguistics
Note:
Pages:
14488–14506
Language:
URL:
https://aclanthology.org/2023.acl-long.810
DOI:
10.18653/v1/2023.acl-long.810
Award:
 Outstanding Paper Award
Bibkey:
Cite (ACL):
Matthias Lindemann, Alexander Koller, and Ivan Titov. 2023. Compositional Generalization without Trees using Multiset Tagging and Latent Permutations. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 14488–14506, Toronto, Canada. Association for Computational Linguistics.
Cite (Informal):
Compositional Generalization without Trees using Multiset Tagging and Latent Permutations (Lindemann et al., ACL 2023)
Copy Citation:
PDF:
https://aclanthology.org/2023.acl-long.810.pdf
Video:
 https://aclanthology.org/2023.acl-long.810.mp4