Learning Algebraic Recombination for Compositional Generalization

Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pages 1129–1144 August 1–6, 2021. ©2021 Association for Computational Linguistics 1129 Learning Algebraic Recombination for Compositional Generalization Chenyao Liu1∗ Shengnan An2∗ Zeqi Lin3† Qian Liu4∗ Bei Chen3 Jian-Guang LOU3 Lijie Wen1† Nanning Zheng 2 Dongmei Zhang3 1 School of Software, Tsinghua University 2 Xi’an Jiaotong University 3 Microsoft Research Asia 4 Beihang University {liucy19@mails, wenlj@}.tsinghua.edu.cn {an1006634493@stu, nnzheng@mail}.xjtu.edu.cn {Zeqi.Lin, beichen, jlou, dongmeiz}@microsoft.com qian.liu@buaa.edu.cn Abstract Neural sequence models exhibit limited com- positional generalization ability in semantic parsing tasks. Compositional generalization requires algebraic recombination, i.e., dynam- ically recombining structured expressions in a recursive manner. However, most previ- ous studies mainly concentrate on recombin- ing lexical units, which is an important but not sufficient part of algebraic recombination. In this paper, we propose LEAR, an end-to- end neural model to learn algebraic recombi- nation for compositional generalization. The key insight is to model the semantic pars- ing task as a homomorphism between a la- tent syntactic algebra and a semantic alge- bra, thus encouraging algebraic recombination. Specifically, we learn two modules jointly: a Composer for producing latent syntax, and an Interpreter for assigning semantic operations. Experiments on two realistic and compre- hensive compositional generalization bench- marks demonstrate the effectiveness of our model. The source code is publicly available at https://github.com/microsoft/ContextualSP. 1 Introduction The principle of compositionality is an essential property of language: the meaning of a complex expression is fully determined by its structure and the meanings of its constituents (Pelletier, 2003; Szab´o, 2004). Based on this principle, human in- telligence exhibits compositional generalization — the algebraic capability to understand and pro- duce a potentially infinite number of novel expres- sions by dynamically recombining known compo- nents (Chomsky, 1957; Fodor and Pylyshyn, 1988; Fodor and Lepore, 2002). For example, people who know the meaning of “John teaches the girl” and ∗ Work done during an internship at Microsoft Research. The first two authors contributed equally to this paper. † Corresponding author. Tom teaches John’s daughter’s daughter. � John teaches the girl. Tom’s daughter. (a) Compositional generalization requires al- gebraic recombination, i.e., dynamically re- combining structured expressions in a recursive manner. John teaches the girl. The girl teaches John. (b) Most previous studies mainly concentrate on recombin- ing lexical units, which is an important but not sufficient part of algebraic recombination. Figure 1: Compositional generalization. “Tom’s daughter” must know the meaning of “Tom teaches John’s daughter’s daughter” (Figure 1a), even though they have never seen such complex sentences before. In recent years, there has been accumulating evidence that end-to-end deep learning models lack such ability in semantic parsing (i.e., trans- lating natural language expressions to machine in- terpretable semantic meanings) tasks (Lake and Ba- roni, 2018; Keysers et al., 2019; Kim and Linzen, 2020; Tsarkov et al., 2020). Compositional generalization requires algebraic recombination, i.e., dynamically recombining structured expressions in a recursive manner. In the example in Figure 1a, understanding “John’s daughter’s daughter” is a prerequisite for under- standing “Tom teaches John’s daughter’s daugh- ter”, while “John’s …

Content truncated to 500 words