Forming Trees with Treeformers (2023)

Abstract: Human language is known to exhibit a nested, hierarchical structure, allowing us to form complex sentences out of smaller pieces. However, many state-of-the-art neural networks models such as Transformers have no explicit hierarchical structure in their architecture—that is, they don’t have an inductive bias toward hierarchical structure. Additionally, Transformers are known to perform poorly on compositional generalization tasks which require such structures. In this paper, we introduce Treeformer, a general-purpose encoder module inspired by the CKY algorithm which learns a composition operator and pooling function to construct hierarchical encodings for phrases and sentences. Our extensive experiments demonstrate the benefits of incorporating hierarchical structure into the Transformer and show significant improvements in compositional generalization as well as in downstream tasks such as machine translation, abstractive summarization, and various natural language understanding tasks.

## introduction human language is known to exhibit a nested or hierarchical structure @xcite . this structure allows humans to construct complex sentences from simple parts and is important for conveying meaning. for example, the phrase structure of the english sentence "the old man the boat." is critical for correctly determining its meaning (figure 1 ). transformer models @xcite are state-of-the-art across a wide variety of nlp tasks @xcite , and pretrained transformers have been shown to learn hierarchical structures after pretraining on large amounts of data @xcite . however, transformers do not have a hierarchical structure built into the architecture-that is, they don't have an inductive bias toward hierarchical structure @xcite the old man the boat the old man the boat figure 1 : two different parses of the text "the old man the boat" with significantly distinct meanings. while the top parse is a complete sentence (with "man" as a verb), the second is nonsense. therefore, the encodings for the subphrase "the old man" (for example) in these parses should be significantly different. our inductive bias layer, which we call treeformer, is an encoder module that constructs hierarchical phrase encodings and is inspired by the cky context-free-grammar parsing algorithm @xcite @xcite . to the best of our knowledge, this is the first study of adding a cky-style phrase-structure inductive bias into a transformer for compositional generalization and general-purpose supervised learning. prior work has used a similar cky-style neural architecture for modeling unsupervised syntactic parsing @xcite . these models are specific to unsupervised parsing and not directly applicable to supervised methods. in contrast, we focus on creating such an architecture for general-purpose supervised learning. treeformer is also simpler than similar work such as diora @xcite , and faster due to two key optimizations which improve the complexity from cubic to linear time (see § 4). we demonstrate the effectiveness of adding a treeformer module to the vanilla transformer with experiments in compositional generalization (cg) on cogs @xcite and cognition, @xcite , two challenging seq2seq datasets for testing cg. in addition, the addition of a treeformer shows significant improvements in machine translation @xcite , abstractive summarization @xcite , and tasks in natural language understanding @xcite . significantly, we find that the treeformer is much better at correctly translating predicate-argument structures (subjects vs objects, etc). predicate-argument structures require understanding the hierarchical structure of language and are very important for correctly conveying meaning. this demonstrates the benefits of the treeformer architecture. we leave to future work large-scale pretraining with our architecture. while interesting and important for practical considerations, pretraining is not within our computing budget, and we consider it out of scope for this work. our focus is on advancements purely in model architecture. the paper is organized as follows. first, we discuss some related work ( § 2). then we present our treeformer module ( § 3). we analyze the computational complexity and propose two methods for optimizing the algorithm ( §4). after describing our experimental setups ( § 5), we present our results ( § 6) and finally conclude ( § 7). ## related work there is much prior work that induces, operates over, or otherwise uses a tree structure in neural net-work models @xcite @xcite @xcite @xcite @xcite @xcite @xcite . such models are especially of interest due to the prevalence of trees in natural language. @xcite introduced tree-lstms, an lstm model generalized to work on parse trees. they suggest specific instances of the general tree-lstm architecture for particular types of trees such as dependency and constituency trees. however, tree-lstms and many other tree-or graphstructured models @xcite @xcite @xcite require a parse tree over the input text, making data expensive or difficult to obtain. unsupervised parsing methods @xcite @xcite have been of interest to solve this problem, but mostly focus on parsing rather than downstream tasks as we do in this paper. one exception is the gumbel tree-lstm @xcite , which uses an unsupervised method to generate tree structures for classification tasks. the authors showed improvement on two tasks @xcite at the time of writing, but they fall short of modern methods such as finetuning pretrained language models. most similar to our architecture is the work of @xcite , who introduced deep inside-outside recursive autoencoders (diora). diora learns tree structures using a modified inside-outside algorithm. the inside pass recursively generates a single root node, and the outside pass regenerates the leaf nodes from a root. diora focuses on unsupervised parse tree induction and demonstrates a number of trees that closely match traditionally labeled ones, suggesting the composition algorithm learns efficacious information-a fact we rely on in this paper. our treeformer layer is similar to diora's "inside" pass but simpler and faster (see § 3.2). treeformer also has no "outside" pass as it does not need to regenerate the leaf nodes, but instead uses the encoded tree structure from the inside pass directly for downstream tasks. ## treeformer the treeformer algorithm generates phrase encodings by the repeated composition of a given set of token encodings. we start with n tokens (i.e., phrases of length 1) and their representations. we recursively apply the algorithm to compute representations of phrases of length k for all lengths k where @xmath0. our approach, shown in figure 2 and algorithm 1, is inspired by the cky algorithm. ## parallelization the cky algorithm, which uses a similar chart structure to treeformer, has a worst-case runtime complexity of o(n 3 |g|) where |g| is the size of the context-free grammar. similarly, the treeformer encoding algorithm is also o(n 3 ) assuming constant model dimension and sequential operations. in this section, we show this calculation as well as two key optimizations which are necessary for tractable training and improve the time and space complexity to o(n) and o(nmh), respectively. see § 6.8 for empirical results. sequential algorithm starting with a sequence of length n, we encode phrases of length h for 1 ≤ @xmath1. there are n -h + 1 phrases of length h, each having h -1 pairs of children. each pair will be composed together exactly once in the entire algorithm, giving us parallel algorithm while encoding phrases of length h is dependent on the encodings for all lengths less than h, there is no dependency on other phrases of the same length, allowing us to compute them in parallel. parallelization removes the factor of n -h + 1 in equation 3, leaving ## experiments we conduct experiments in five settings: (1) english-chinese machine translation for cg on cognition @xcite , (2) semantic parsing for cg on cogs @xcite , (3) machine translation on iwslt'14 german-english and english-french @xcite , (4) abstractive summarization on gigaword english abstractive summarization @xcite , and (5) five natural language understanding tasks selected from glue @xcite . for full experimental details, see appendix. models referred to as "treeformer" are a transformer with a treeformer module, as described in the last paragraph in § 3.2. we test our models on two compositional generalization datasets: cognition @xcite , an english-chinese machine translation dataset designed to test cg abilities, and cogs @xcite , a semantic parsing dataset. these datasets are specifically designed to test a model's ability to generalize compositionally by testing its ability to generalize to novel combinations of predicates and arguments. a note about baselines although there is much prior work on tree structures in deep learning, we are not aware of any prior work using tree structures that is suitable as a baseline for our tasks beyond the transformer. models such as diora @xcite and related models are for unsupervised parsing but not for classification or seq2seq tasks such as the ones we consider here. gumbel tree-lstms @xcite similarly are only for classification and not for seq2seq. transformer grammars @xcite and rnngs are for parsing or language modeling @xcite , or for classification @xcite . all the above architectures would require significant changes for seq2seq tasks. ## conclusion this paper presents treeformer, a cky-inspired neural network algorithm for composing tokens into phrases and sentences. we showed that, in many cases, standard transformers are unable to effectively capture the phrase-level or hierarchical information which the treeformer module helps exploit. this information allows the treeformer to outperform a vanilla transformer in compositional generalization and many downstream tasks, including machine translation, abstractive summarization, and natural language understanding. we believe hierarchical structure is an important feature for models to have due to the prevalence of tree structures in natural language, and we are further convinced by the performance increase shown with our treeformer module across a variety of settings. while this paper and many previous works modify algorithms such as cky to induce input also ging ich von da an weiter. transformer so i went from there to further. treeformer so i went on from there. gold so i moved on from there.