S truct F ormer: Joint Unsupervised Induction of Dependency and Constituency Structure from Masked Language Modeling (2021)

Abstract: There are two major classes of natural language grammars — the dependency grammar that models one-to-one correspondences between words and the constituency grammar that models the assembly of one or several corresponded words. While previous unsupervised parsing methods mostly focus on only inducing one class of grammars, we introduce a novel model, StructFormer, that can induce dependency and constituency structure at the same time. To achieve this, we propose a new parsing framework that can jointly generate a constituency tree and dependency graph. Then we integrate the induced dependency relations into the transformer, in a differentiable manner, through a novel dependency-constrained self-attention mechanism. Experimental results show that our model can achieve strong results on unsupervised constituency parsing, unsupervised dependency parsing, and masked language modeling at the same time.

## introduction human languages have a rich latent structure. this structure is multifaceted, with the two major classes of grammar being dependency and constituency structures. there has been an exciting breath of recent work targeted at learning this structure in a data-driven unsupervised fashion @xcite @xcite @xcite . the core principle behind recent methods that induce structure from data is simple -provide an inductive bias that is conducive for structure to emerge as a byproduct of some self-supervised training, e.g., language modeling. to this end, a wide range of models have been proposed that are able to successfully learn grammar structures @xcite @xcite . however, most of these works focus on inducing either constituency or dependency structures alone. in this paper, we make two important technical contributions. first, we introduce a new neural model, structformer, that is able to simultaneously induce both dependency structure and constituency structure. specifically, our approach aims to unify latent structure induction of different types of grammar within the same framework. second, structformer is able to induce dependency structures from raw data in an end-to-end unsupervised fashion. most existing approaches induce dependency structures from other syntactic information like gold pos tags @xcite @xcite . previous works, having trained from words alone, often requires additional information, like pre-trained word clustering @xcite , pre-trained word embedding @xcite , acoustic cues @xcite , or annotated data from related languages @xcite . we introduce a new inductive bias that enables the transformer models to induce a directed dependency graph in a fully unsupervised manner. to avoid the necessity of using grammar labels during training, we use a distance-based parsing mechanism. the parsing mechanism predicts a sequence of syntactic distances t @xcite and a sequence of syntactic heights ∆ @xcite to represent dependency graphs and constituency trees at the same time. examples of ∆ and t are illustrated in figure 1a . based on the syntactic distances (t) and syntactic heights (∆), we provide a new dependency-constrained self-attention layer to replace the multi-head self-attention layer in standard transformer model. more specifically, the new attention head can only attend its parent (to avoid confusion with self-attention head, we use "parent" to denote "head" in dependency graph) or (a) an example of syntactic distances t (grey bars) and syntactic heights ∆ (white bars). in this example, like is the parent (head) of constituent (like cats) and (i like cats). incorporating the new parsing mechanism, the dependency-constrained self-attention, and the transformer architecture, we introduce a new model named structformer. the proposed model can perform unsupervised dependency and constituency parsing at the same time, and can leverage the parsing results to achieve strong performance on masked language model tasks. ## related work previous works on unsupervised dependency parsing are primarily based on the dependency model with valence (dmv) @xcite and its extension @xcite . to effectively learn the dmv model for better parsing accuracy, a variety of inductive biases and handcrafted features, such as correlations between parameters of grammar rules involving different part-of-speech (pos) tags, have been proposed to incorporate prior information into learning. the most recent progress is the neural dmv model @xcite , which uses a neural network model to predict the grammar rule probabilities based on the distributed representation of pos tags. however, most existing unsupervised dependency parsing algorithms require the gold pos tags to ge provided as inputs. these gold pos tags are labeled by humans and can be potentially difficult (or prohibitively expensive) to obtain for large corpora. @xcite proposed to overcome this problem with unsupervised word clustering that can dynamically assign tags to each word considering its context. @xcite overcame the problem by combining dmv model with invertible neural network to jointly model discrete syntactic structure and continuous word representations. unsupervised constituency parsing has recently received more attention. prpn @xcite and on-lstm @xcite induce tree structure by introducing an inductive bias to recurrent neural networks. prpn proposes a parsing network to compute the syntactic distance of all word pairs, while a reading network uses the syntactic structure to attend to relevant memories. on-lstm allows hidden neurons to learn longterm or short-term information by a novel gating mechanism and activation function. in urnng @xcite , amortized variational inference was applied between a recurrent neural network grammar (rnng) @xcite decoder and a tree structure inference network, which encourages the decoder to generate reasonable tree structures. diora @xcite proposed using inside-outside dynamic programming to compose latent representations from all possible binary trees. the representations of inside and outside passes from the same sentences are optimized to be close to each other. the compound pcfg @xcite achieves grammar induction by maximizing the marginal likelihood of the sentences which are generated by a probabilistic context-free grammar (pcfg). tree transformer @xcite adds extra locality constraints to the transformer encoder's self-attention to encourage the attention heads to follow a tree structure such that each token can only attend on nearby neighbors in lower layers and gradually extend the attention field to further tokens when climbing to higher layers. neural l-pcfg @xcite demonstrated that pcfg can benefit from modeling lexical dependencies. similar to structformer, the neural l-pcfg induces both constituents and dependencies within a single model. though large scale pre-trained models have dominated most natural language processing tasks, some recent work indicates that neural network models can see accuracy gains by leveraging syntactic information rather than ignoring it @xcite . @xcite introduces syntacticallyinformed self-attention that force one attention head to attend on the syntactic governor of the input token. @xcite and @xcite argue that dependency-informed selfattention can improve transformer's performance on machine translation. @xcite shows that syntactic biases help large scale pretrained models, like bert, to achieve better language understanding. ## syntactic distance and height in this section, we first reintroduce the concepts of syntactic distance and height, then discuss their relations in the context of structformer. ## conclusion in this paper, we introduce a novel dependency and constituency joint parsing framework. based on the framework, we propose structformer, a new unsupervised parsing algorithm that does unsupervised dependency and constituency parsing at the same time. we also introduced a novel dependencyconstrained self-attention mechanism that allows each attention head to focus on a specific mixture of dependency relations. this brings transformers closer to modeling a directed dependency graph. the experiments show promising results that struct-former can induce meaningful dependency and constituency structures and achieve better performance on masked language model tasks. this research provides a new path to build more linguistic bias into a pre-trained language model.