Unsupervised Dependency Graph Network (2022)

Abstract: Recent work has identified properties of pretrained self-attention models that mirror those of dependency parse structures. In particular, some self-attention heads correspond well to individual dependency types. Inspired by these developments, we propose a new competitive mechanism that encourages these attention heads to model different dependency relations. We introduce a new model, the Unsupervised Dependency Graph Network (UDGN), that can induce dependency structures from raw corpora and the masked language modeling task. Experiment results show that UDGN achieves very strong unsupervised dependency parsing performance without gold POS tags and any other external information. The competitive gated heads show a strong correlation with human-annotated dependency types. Furthermore, the UDGN can also achieve competitive performance on masked language modeling and sentence textual similarity tasks.

## introduction the goal of unsupervised dependency parsing is to induce dependency grammar from corpora that don't have annotated parse trees @xcite . although the task is difficult, one advantage of unsupervised methods is that they can leverage vast amount of unannotated raw corpus @xcite . thus, adapting the task into a pretraining framework is increasingly tempting. the induced dependency trees can also help solve other nlp problems such as unsupervised discourse parsing @xcite , aspect-based sentiment analysis @xcite and intent discovery @xcite . furthermore, the task can also be used as a probe to verify cognitive theories for human language acquistition @xcite figure 1 : the architecture of unsupervised dependency graph network (udgn). given an input sentence, the parser can predict the dependency relation between tokens and generate a soft mask to approximate the undirected dependency graph. conditioning on the mask, the dgn computes contextual word embeddings for the training task. since the mask is soft, the gradient can be backpropagated from the dgn into the parser. thus udgn can induce grammar while training on masked language modeling or other downstream tasks. @xcite @xcite . pretrained language models (plms) have become the foundation of modern natural language processing in the last few years @xcite . they dominate the most if not all nlp tasks. but recent works show that, beyond pretraining big models on large-scale corpora, deep learning methods can improve performance by increasing models' awareness of syntactic information @xcite . these methods either include known structural information as input to the model @xcite , or incorporate structural prediction tasks into the training process @xcite . however, these attempts require access to large datasets with supervised parses, which may be complicated and expensive. recent work also identified properties of pretrained self-attention models that mirror those of dependency parse structures @xcite @xcite . struct-former @xcite shows that a transformerbased model can induce a good dependency structure. the belief that linguistic structure may be embedded in these models is of interest to the community. furthermore, @xcite shows that the induced trees from finetuned roberta outperform parser-provided trees on aspect-based sentiment analysis tasks. this result brings interest to study task-specific structures. from this perspective, the unsupervised acquisition of dependency structure from raw data or downstream tasks appears important and feasible. traditionally, dependency grammars consider the dependency types (a.k.a. syntactic functions) as primitive and then derive the dependency graph @xcite . every head-dependent dependency bears a syntactic function @xcite . @xcite shows that some attention heads in bert @xcite and roberta @xcite track individual dependency types. in other words, these heads model different syntactic functions. inspired by this observation and syntactic functions, we introduce competitive gated heads to model different syntactic parts and the process of selecting the proper syntactic function for each edge. these heads include two key components: building on these components, we propose a novel architecture, the unsupervised dependency graph network (udgn). as shown in figure 1 , the udgn is composed of two networks: a parser that computes the dependency head distribution p i for each word w i in the input sentence and then converts it to a matrix of edge probability m ij that approximates an undirected dependency graph; a dependency graph network (dgn) that uses the edge probabilities {m ij } and competitive gated heads to propagate information between words to compute a contextualized embedding h i for each word w i . while training with the masked language modeling or other objectives, the gradient can flow through the dgn to the parser network through its dependence on m ij . as a result, udgn can induce a dependency grammar while solely relying on the masked language modeling objective. in the experiment section, we first train the udgn with masked language modeling, then evaluate it on unsupervised dependency parsing. our experimental results show that udgn can: 1) achieve very strong unsupervised parsing results among models that don't have access to extra annotations (including pos tags); 2) learn attention heads that are strongly correlated to humanannotated dependency types; 3) achieve competitive performance on language modeling tasks. we also finetune the pretrained udgn on semantic textual similarity (sts) tasks. our experiments show that udgn outperforms a transformer baseline trained on the same corpus. ## related work unsupervised dependency parsing unsupervised dependency parsing is a long-standing task for computational linguistics. dependency model with valence (dmv; @xcite is the basis of several unsupervised dependency parsing methods @xcite . @xcite updates the method using neural networks to predict grammar rule probabilities. while previous methods mostly require additional part-of-speech (pos) information, @xcite tackled the issue by performing clustering based on word context information and then assigning the cluster id to each word as their tag. @xcite incorporate an invertible neural network into dmv model to jointly model dependency grammar and word embeddings. recently, nl-pcfg @xcite and nbl-pcfg @xcite combined neural network and l-pcfg to achieve good performance in a joint unsupervised dependency and constituency parsing setting. structformer @xcite proposes a joint constituency and dependency parser and uses the dependency distribution to regularize the self-attention heads in the transformer model. this joint parser-language model framework can induce grammar from masked language modeling tasks. the udgn's architecture is similar to struct-former, both models include a parser and masked language model. our model, however, has three major differences: 1) it uses competitive gated heads to improve models performance on grammar induction; 2) it uses a neural head selective parser that can produce both projective and nonprojective dependency trees, whereas the distance parser in structformer can only produce projective trees; 3) it uses a simplified method to generate an undirected dependency mask. transformers, graph neural networks and dependency graphs in many transformer-based models, attention masks are often used to limit the input tokens that a particular timestep can attend over. in @xcite , for example, a mask derived from the permutation of inputs is used to induce a factorization over the tokens so that the resulting model is a valid probabilistic model. this attention mask can be viewed as an adjacency matrix over a graph whose nodes are the input tokens. from this perspective, transformers are a form of graph neural network @xcite -specifically, a graph attention network (gat; @xcite , as it attends over the features of its neighbors. several works have made this connection, and integrated dependency structures into transformers @xcite @xcite . results from @xcite and @xcite suggest that embedding these structures can improve translation models. however, these dependency parses may not always be present to be used as input to the model. @xcite trains the self-attention to attend the syntactic governor (head) of a particular token, resulting in a model that does not require dependency structure as input during inference time. we take a further step in our work and attempt to learn these structures in an unsupervised fashion from the mlm objective. ## model architecture as shown in figure 2 , the parser computes a dependency head distribution for each token and then converts it to a soft dependency mask m ij . the dgn takes m ij and the sentence as input and uses a competitive mechanism to propagate information between tokens. ## conclusion in this paper, we proposed the unsupervised dependency graph network (udgn), a novel architecture to induce and accommodate dependency graphs in a transformer-like framework. the model is inspired by linguistic theories. experiment results show that udgn achieves state-of-the-art dependency grammar induction performance. the competitive gated heads show a strong correlation to human-annotated dependency types. we hope these interesting observations will build new connections between classic linguistic theories and modern neural network models. another interesting future research direction is exploring how the newly proposed components can help large-scale pretrained languages models. figure 6 : relationship between the parsing performance and the mask rate for mlm.