Recursive Top-Down Production for Sentence Generation with Latent Trees (2020)

Abstract: We model the recursive production property of context-free grammars for natural and synthetic languages. To this end, we present a dynamic programming algorithm that marginalises over latent binary tree structures with N leaves, allowing us to compute the likelihood of a sequence of N tokens under a latent tree model, which we maximise to train a recursive neural function. We demonstrate performance on two synthetic tasks: SCAN, where it outperforms previous models on the LENGTH split, and English question formation, where it performs comparably to decoders with the ground-truth tree structure. We also present experimental results on German-English translation on the Multi30k dataset, and qualitatively analyse the induced tree structures our model learns for the SCAN tasks and the German-English translation task.

## introduction given the hierarchical nature of natural language, tree structures have long been considered a fundamental 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 language tasks @xcite @xcite . various work has explored the introduction of syntactic structures into recursive encoders, either with explicit syntactic information @xcite @xcite or by means of unsupervised latent tree learning @xcite @xcite . some attempts at formulating structured decoders are @xcite and alvarez-melis and * equal contribution figure 1 : our generative model is a recursive top-down neural network that recursively splits a root node embedding with some node-dependent probability. when the splitting stops, it emits a word with some probability. the joint probability of a sentence and its associated binary tree is the product of the probability of the tree (1 -l 1 )(1 -l 3 )(1 -l 5 )l 2 l 4 l 6 l 7 and the probabilities of the word emitted at its leaves. we devise a novel marginalisation algorithm over binary trees to compute the likelihood of a sentence. @xcite which propose binary top-down tree lstm architectures for natural language. @xcite proposes a tree-structured decoder for code generation. these methods require groundtruth trees from an external source, and this extra input may not be available for all languages or data sources. in this work, we propose a tree-based probabilistic decoder model for sequence-to-sequence tasks. our model generates sentences from a latent tree structure that aims to reflect natural language syntax. the method assumes that each token in a sentence is emitted at the leaves of a full but latent binary tree (fig. 1 ). the tree is obtained by recursively producing node embeddings from a root embedding with a recursive neural network. word emission probabilities are function of the leaf embeddings. we describe a novel dynamic programming algorithm for exact marginalisation over the large number of latent binary trees. our generative model parametrizes a prior over binary trees with a stick-breaking process, similar to the "penetration probabilities" defined in @xcite . it is related to a long tradition of unsupervised grammar induction models that formulate a generative model of sentences @xcite @xcite . unlike more recent bottom-up approaches such as @xcite which require the insideoutside algorithm @xcite to marginalise over tree structures, our approach is top-down and comes with an efficient algorithm to perform marginalisation. top-down models can be useful, as the decoder is encouraged by design to keep global context while generating sentences @xcite . in the next section, we will describe the algorithm that marginalises over latent tree structures under some independence assumptions. we first introduce these assumptions and show that by introducing the notion of successive leaves, we can efficiently sum over different tree structures. we then introduce the details of the recursive architecture used. finally, we present the experimental results of the model in section 5. ## related work non-parametric bayesian approaches to learning a hierarchy over the observed data has been proposed in the past @xcite . these works generally learn a prior on tree-structured data, and assumes a common superstructure that generated the corpus instead of assuming that each observed datapoint may have been produced by a different hierarchical structure. our generative assumptions are generally stronger but they allow us for tractable marginalisation without costly iterative inference procedures, e.g. mcmc. our method shares similarities with the forward algorithm @xcite ) which computes likelihoods for hidden markov models (hmm), and ctc @xcite . while the forward algorithm factors in the transition probabilities, both ctc and our algorithm have placed a conditional independence assumption in the factorisation of the likelihood of the output sequence. the inside-outside algorithm @xcite is usually employed when it comes to learning parameters for pcfgs. @xcite gives a modern treatment to pcfgs by introducing compound pcfgs. in this work, the cfg production probabilities are conditioned on a continuous latent variable, and the entire model is trained using amortized variational inference @xcite . this allows the production rules to be conditioned on a sentencelevel random variable, allowing it to model correlations over rules that were not possible with a standard pcfg. however, all co-dependence between the rules can only be captured through the global latent variable. in ctc, compound pcfgs, and our work, the fact that the dynamic programming algorithm is differentiable is exploited to train the model. while typical language modelling is done with a left-to-right autoregressive structure, there has been recent work that change the conditional factorisation order @xcite , and even learn a good factorisation order @xcite . for hierarchical text generation, @xcite and @xcite have attempted to model this hierarchy using ground-truth parse trees from a parser. however, the parser was trained based on parses annotated using rules designed by linguists, which presents two challenges: (1) we may not always have these rules, particularly when it comes to lowresource languages, and (2) it may be possible that the structure required for different tasks are slightly different, enforcing the structure based on a universal parse structure may not be optimal. @xcite attempts to learn a tree structure using discrete split and merge with reinforce @xcite . however, the method is known to have high variance @xcite . there has also been some work that use sequential models for learning a latent hierarchy. @xcite again uses discrete binary sampling units to learn a hierarchy. @xcite enforces an ordering to the hidden state of the lstm @xcite that allows the hidden representations to be interpreted as a tree structure. in their follow up work, @xcite encodes sequences to a single vector representation, which we use in this work as the encoder. ## experiments we evaluate our method on three different sequence-to-sequence tasks. unless otherwise stated, we are using the ordered memory (om) @xcite as our encoder. further details can be found in appendix d.1. ## conclusion in this paper, we propose a new algorithm for learning a latent structure for sequences of tokens. given the current interest in systematic generalisation and compositionality, we hope our work will lead to interesting avenues of research in this direction. firstly, the connectionist tree decoding framework allows for different architectural designs for the recurrent function used. secondly, while the dynamic programming algorithm is an improvement over a naive enumeration over different trees, there is room for improvement. for one, exploiting the sparsity of the m (•, •) table can perhaps result in some memory and time gains. finally, the need to recursively expand to a complete tree results in exponential growth with respect to the input length. these results, while preliminary, suggests that the method holds some potential. the experimental results reveal some interesting behaviours that require further study. nevertheless, we demonstrate that it performs comparably to current algorithms, and surpasses current models in synthetic tasks that have been known to require structure in the models to perform well.