Recursive Top-Down Production for Sentence Generation with Latent Trees

Findings of the Association for Computational Linguistics: EMNLP 2020, pages 2291–2307 November 16 - 20, 2020. c⃝2020 Association for Computational Linguistics 2291 Recursive Top-Down Production for Sentence Generation with Latent Trees Shawn Tan∗ Mila / University of Montreal tanjings@mila.quebec Yikang Shen∗ Mila / University of Montreal yi-kang.shen@umontreal.ca Timothy J. O’Donnell Dept. of Linguistics Mila / McGill University Canada CIFAR AI Chair Alessandro Sordoni Microsoft Research Aaron Courville Mila / University of Montreal Canada CIFAR AI Chair Abstract We model the recursive production prop- erty of context-free grammars for natural and synthetic languages. To this end, we present a dynamic programming algorithm that marginalises over latent binary tree struc- tures with N leaves, allowing us to compute the likelihood of a sequence of N tokens un- der a latent tree model, which we maximise to train a recursive neural function. We demon- strate performance on two synthetic tasks: SCAN (Lake and Baroni, 2017), where it outperforms previous models on the LENGTH split, and English question formation (McCoy et al., 2020), where it performs comparably to decoders with the ground-truth tree struc- ture. We also present experimental results on German-English translation on the Multi30k dataset (Elliott et al., 2016), and qualitatively analyse the induced tree structures our model learns for the SCAN tasks and the German- English translation task. 1 Introduction Given the hierarchical nature of natural language, tree structures have long been considered a funda- mental part of natural language understanding. In recent years, a number of studies have shown that incorporating these structures into deep learning systems can be beneficial for various natural lan- guage tasks (Socher et al., 2013; Bowman et al., 2015; Eriguchi et al., 2016). Various work has explored the introduction of syntactic structures into recursive encoders, either with explicit syntactic information (Du et al., 2020; Socher et al., 2010; Dyer et al., 2016) or by means of unsupervised latent tree learning (Williams et al., 2018; Shen et al., 2019; Kim et al., 2019b). Some attempts at formulating structured decoders are Zhang et al. (2015a) and Alvarez-Melis and ∗Equal contribution 1 2 3 4 5 7 6 Investors suffered heavy losses 1-l1 1-l3 1-l5 l7 l6 l2 l4 Figure 1: Our generative model is a recursive top-down neural network that recursively splits a root node em- bedding with some node-dependent probability. When the splitting stops, it emits a word with some probabil- ity. The joint probability of a sentence and its associ- ated binary tree is the product of the probability of the tree (1 − l1)(1 − l3)(1 − l5)l2l4l6l7 and the probabili- ties of the word emitted at its leaves. We devise a novel marginalisation algorithm over binary trees to compute the likelihood of a sentence. Jaakkola (2016) which propose binary top-down tree LSTM architectures for natural language. Chen et al. (2018) proposes a tree-structured decoder for code generation. These methods require ground- truth trees from an external source, and this extra input may not be available for all languages or data sources. In this …

Content truncated to 500 words