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 1 . The goal of unsupervised dependency parsing is to induce dependency grammar from corpora that don't have annotated parse trees (Marecek, 2016). Although the task is difficult, one advantage of unsupervised methods is that they can leverage vast amount of unannotated raw corpus (Han et al., 2020). 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 (Nishida and Nakayama, 2020), aspect-based sentiment analysis (Dai et al., 2021) and intent discovery (Liu et al., 2021). Furthermore, the task can also be used as a probe to verify cognitive theories for human language acquistition (Yang et al., 2020; 1 Our code is publicly available at https://github. Pretrained Language Models (PLMs) have become the foundation of modern natural language processing in the last few years (Bommasani et al., 2021). 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 (Kuncoro et al., 2020). These methods either include known structural information as input to the model (Sundararaman et al., 2019; Bai et al., 2021), or incorporate structural prediction tasks into the training process (Wang et al., 2019a). 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 (Htut et al., 2019; Hewitt 4767 and Manning, 2019; Jawahar et al., 2019). StructFormer (Shen et al., 2020) shows that a transformer-based 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, Dai et al. (2021) 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 (Debusmann, 2000). Every head-dependent dependency bears a syntactic function (Mel'cuk et al., 1988). Htut et al. (2019) shows that some attention heads in BERT (Devlin et al., 2018) and RoBERTa (Liu et al., 2019) 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:  A set of gated heads that model different information propagation processes between tokens;  A competitive controller that selects the most suitable gated head for each pair of tokens. 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 human-annotated 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. Unsupervised dependency parsing Unsupervised dependency parsing is a long-standing task for computational linguistics. Dependency Model with Valence (DMV; Klein and Manning 2004) is the basis of several unsupervised dependency parsing methods (Daum III, 2009; Gillenwater et al., 2010). Jiang et al. (2016) updates the method using neural networks to predict grammar rule probabilities. While previous methods mostly require additional Part-of-Speech (POS) information, Spitkovsky et al. (2011) tackled the issue by performing clustering based on word context information and then assigning the cluster ID to each word as their tag. He et al. (2018) incorporate an invertible neural network into DMV model to jointly model dependency grammar and word embeddings. Recently, NL-PCFG (Zhu et al., 2020) and NBL-PCFG (Yang et al., 2021) combined neural network and L-PCFG to achieve good performance in a joint unsupervised dependency and constituency parsing setting. StructFormer (Shen et al., 2020) 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 StructFormer, 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 4768 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 Yang et al. (2019), 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 (Scarselli et al., 2008)  specifically, a Graph Attention Network (GAT; Velickovic et al. 2017), as it attends over the features of its neighbors. Several works have made this connection, and integrated dependency structures into transformers (Ahmad et al., 2021; Wang et al., 2019b; Tang et al., 2020). Results from Omote et al. (2019) and Deguchi et al. (2019) 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. Strubell et al. (2018) 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. Differentiable Structured Prediction While the head selection is a good approximation of a tree structure, there are methods to obtain a relaxed adjacency matrix as the output of the parser. Previous work have used such methods for predicting structure. Koo et al. (2007) proposed using the Kirchoff matrix tree theorem for dependency parsing. They explain how the marginals of the edge potentials are computed, and these marginals have properties similar to a tree adjacency matrix (sum over the marginals are equal to N  1 for example, where N is the length of the sentence). Eisner (2016) describes how backpropagation can be used to compute marginals of some structured prediction algorithm. We also tried using the Kirchhoff method to normalize our dependency distributions in Appendix A.3. Corro and Titov (2018) uses similar notions but relaxes projective trees using Gumbel-softmax. Kim et al. (2017) proposed a structured form of attention and show that they are useful for certain sequence-to-sequence tasks. Mensch and Blondel (2018) gives a general theoretical treatment for these types of relaxations, while Paulus et al. (2020) gives a practical treatment of possible applications for these methods. 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. We use a simplified version of the Dependency Neural Selection parser (DENSE ; Zhang et al. 2016) that only predicts unlabelled dependency relations. The parser takes the sentence s = w 1 w 2 ...w T as input, and, for each token w i , it produces a distribution p i over all tokens in the sentence, resulting in a T  T weight matrix. The parser first maps the sequence of tokens w 1 w 2 ...w T into a sequence of embeddings [ x 1 , x 2 , ..., x T ] . Then the word embeddings are fed into a stack of a bidirectional LSTM (BiLSTM): h i = BiLSTM( x i ) (1) where h i is the output of the BiLSTM at i -th timestep. Linear transforms are applied to the output of the BiLSTM to extract head and dependent information. where p ij is the probability that w i depends on w j , D is the dimension of hidden states. During the inference for parsing, the Chu-Liu/Edmonds' algorithm (Chu and Liu, 1965b) is used to extract the most likely directed dependency graph from the matrix p . Given the dependency probabilities, StructFormer (Shen et al., 2020) uses a weighted sum of matrix p and p (cid:62) to produce a mask for self-attention layers in the transformer. We found that simply using the adjacency matrix of the undirected dependency graph provides better parsing results and perplexities. However, simply using the sum of the matrix and its transpose to create a symmetric weight matrix does not ensure that the attention mask has values < 1. When p ij = 1 and p ji = 1 , for instance, the mask violates the constraints of a dependency mask. Thus, we treat p ij and p ji as parameters for independent Bernoulli variables, and we compute the probability that either w i depends on w j or w j depends on w i . To better induce and model the dependency relations, we propose a new Dependency Graph Network (DGN). One DGN layer includes several gated heads and a competitive controller. A gated head can process and propagate information from one node to another. Different heads can learn to process and propagate different types of information. The competitive controller is designed to select the correct head to propagate information between a specific pair of nodes. We take inspiration from the linguistic theory that dependencies are associated with different syntactic functions. These functions can appear as labels, e.g. ATTR (attribute), COMP-P (complement of preposition), and COMP-TO (complement of to). However, DGN learns these functions from training tasks, which in our experiments is the masked language model objective. Since these objectives tend to be statistical in nature, these functions may not be correlated with ground truth labels given by human experts. Inside each layer, the input vector h l  1 i is first projected into N groups of vectors, where N is the number of heads. Each group contains four different vectors, namely, query q , key k , value v and gate g :   q ik k ik v ik g ik   = W head k h l  1 i + b head k (7) Gated Head To model the information propagation from node j to node i , we proposed a gated head: c ijk =  ( v jk ) (cid:12) sigmoid( g ik ) (8) where  is a non-linear activation function, and gates sigmoid( g ) allows the i -th token to filter the extracted information. We also found that the gate effectively improves the model's ability to induce 4770 Figure 3: Competitive Gated Heads. latent dependency structures that are coherent to human-annotated trees. The activation function can be chosen from a wide variety of functions, including the identity function, tanh, ReLU, and ELU, etc. In our experiment, we found that tanh function provides the best overall performance. This is probably due to two reasons: a) tanh function provides a bounded output (between -1 and 1), and b) gates and head weights are more effective while controlling a bounded value. Competitive Controller Lamb et al. (2021) proposed the idea of using a competition method to encourage heads to specialize over training iterations to learn different functions. This idea is coherent with our intuition different heads should model different dependency relations. In UDGN, a competitive controller is designed to select a head for each pair of nodes ( i, j ) . However discrete assignment is hard to optimize, we replace it with a soft relaxation: e ijk = q ik k jk  D (9)  a ijk = softmax k ( e ijk ) (10) where  a ijk is the probability that the k -th head is assigned to propagate information from the j th token to the i -th token. To obtain the actual head weights, we multiply the probability of edge existence with the probability of choosing a specific attention head: a ijk =  a ijk  m ij (11) where a ijk is the weight from the node j to the node i for k -th attention head. Relative Position Bias Transformer models use positional encoding to represent the absolute position for each token. In DGN, we only model whether the token is before or after the current token. The motivating intuition is the association of different heads with different directions. In equation 10, we can introduce a relative position bias:  a ijk = softmax k ( e ijk + b lrk ) (12) b lr k = (cid:40) b lk , i > j b rk , i < j (13) where b lk and b rk are trainable parameters. The relative position bias allows the attention head k to prioritize forward or backward directions. A mere forward and backward differentiation may seem weak compared to other parameterizations of positional encoding (Vaswani et al., 2017; Shaw et al., 2018), but in conjunction with the dependency constraints, this method is a more effective way to model the relative position in a tree structure. As shown in Table 4, the relative position bias achieves stronger masked language modeling and parsing performance than positional encoding. At the end, a matrix multiplication is used to aggregate information from different positions. Then, the output o from different heads are concatenated, and then projected back to the hidden state space with a linear layer. where h li is the output of the l -th gated self attention layers. The shared hidden state space can be seen as the shared global workspace (Goyal et al., 2021) for different independent mechanisms (heads). Language Modeling tasks evaluate the model's general ability to model different semantic and syntactic phenomena (e.g., words co-occurrence, verb-subject agreement, etc.). The performance of MLM is evaluated by measuring perplexity on masked words. We perform experiments on two corpora: the Penn TreeBank (PTB) and Brown Laboratory for Linguistic Information Processing (BLLIP). In this experiment, we randomly replace each token with a mask token <mask> , such that the model is required to predict the original token. But we never replace <unk> token. PTB The Penn Treebank (Marcus et al., 1993) is a standard dataset for language modeling (Mikolov et al., 2012) and unsupervised constituency parsing (Shen et al., 2018; Kim et al., 2019). It contains 1M words (2499 stories) from Wall Street Journal. Following the setting proposed in Shen et al. (2020), we preprocess the Penn Treebank dataset by removing all punctuations, lower case all letters, and replaces low frequency tokens (< 5) with <unk> . The preprocessing results in a vocabulary size of 10798 (including <unk> , <pad> and <mask> ). BLLIP The Brown Laboratory for Linguistic Information Processing dataset is a large corpus, parsed in the same style as the PTB dataset. It contains 24 million sentences from Wall Street Journal. We perform experiments on four subsets of BLLIP: BLLIP-XS (40k sentences, 1M tokens), BLLIP-SM (200K sentences, 5M tokens), BLLIP-MD (600K sentences, 14M tokens), and BLLIP-LG (2M sentences, 42M tokens). Following the same setting proposed in Hu et al. (2020) for sentence selection, each subset is a superset of smaller subsets. Models trained on different subsets are tested on a shared held-out test set (20k sentences, 500k tokens). We use a shared vocabulary for all splits to make the mask language modeling and parsing results comparable. Like the PTB dataset, we preprocess the BLLIP dataset by removing all Methods DDA UDA DMV (Klein and Manning, 2004) 35.8 E-DMV (Headden III et al., 2009) 38.2 UR-A E-DMV (Tu and Honavar, 2012) 46.1 Neural E-DMV (Jiang et al., 2016) 42.7 Gaussian DMV (He et al., 2018) 43.1 INP (He et al., 2018) 47.9 NL-PCFGs (Zhu et al., 2020) 40.5 55.9 NBL-PCFGs (Yang et al., 2021) 39.1 56.1 StructFormer (Shen et al., 2020) 46.2 61.6 UDGN 49.9 61.8 Table 2: Dependency Parsing Results on WSJ test set without gold POS tags. punctuations and lower case letters. The shared vocabulary is obtained by counting word frequencies on the BLLIP-LG dataset and selecting the words that appear more than 27 times. The resulting vocabulary size is 30232 (including <unk> , <pad> and <mask> ), and covers more than 98% tokens in BLLIP-LG split. The mask rate is 30% when training on both corpora. In Section A.4, we further explore the relationship between mask rate and parsing results. Other hyperparameters are tuned separately for each model and dataset. Details are further described in Section A.1. Table 1 shows The masked language model results. UDGN outperforms the baselines on smaller datasets (PTB, BLLIP-SM), but underperforms against baselines trained on large datasets (BLLIP-MD, BLLIP-LG). However, in Section 4.5, we find that the UDGN pretrained on BLLIP-LG dataset can achieve stronger performance when finetuned on a downstream task. This result may suggest that our model learns more generic contextual embeddings. Following previous research (Shen et al., 2020), we use the model trained on the PTB training set (section 0-20, no punctuations) and test its parsing accuracy on section 23 of the PTB corpus. Punctuations are ignored during the evaluation. We convert the human-annotated constituency trees in the PTB test set (Marcus et al., 1993) to dependency trees with Stanford CoreNLP (Manning et al., 2014) and use the Directed Dependency Accuracy (DDA) as our metric. To derive valid trees from the attention 4772 Models prep pobj det compound nsubj amod dobj aux UDGN 0.65(0.12) 0.60(0.11) 0.68(0.15) 0.42(0.04) 0.50(0.06) 0.39(0.07) 0.39(0.07) 0.62(0.10) StructFormer 0.39(0.05) 0.38(0.07) 0.57(0.03) 0.33(0.01) 0.25(0.06) 0.26(0.01) 0.22(0.05) 0.23(0.04) Transformer 0.43(0.00) 0.46(0.03) 0.46(0.12) 0.30(0.01) 0.39(0.15) 0.26(0.02) 0.28(0.01) 0.30(0.10) Table 3: The pearson correlation coefficients between most frequent dependency types and their most correlated head. mask, we use the Chu-Liu (Chu and Liu, 1965b) (or Edmonds' (Edmonds, 1967)) algorithm to obtain the maximum directed spanning tree. Table 2 shows that our model outperforms baseline models. This result suggests that, given our minimum inductive bias (a token must attach to another, but the graph is not necessarily a tree), predicting missing tokens implicitly learns a good graph that correlates well with human-annotated dependency trees. In other words, some of the dependency relations proposed by linguists may correspond with efficient ways of propagating information through the sentence. Parsing examples of our model can be found in Appendix A.5. In this section, we test the correlation between heads and dependency types. We consider each dependency edge i  j ( i depends on j ) in the ground truth structure as a data point. Given all the edges, we can obtain three sets of quantities: head probabilities A k = {  a kji } and type values Y l = { y lij } . a kij is a real value between 0 and 1, represents the probability that heads k is used to model the information propagation from the child i to the parent j . Details about this value can be found at Equation 12. y lij is a binary value, represents whether the label l is assigned to edge i  j . We can then compute Pearson Correlation Coeffi-cient (PCC) for every pair of A k and Y l across all ground truth edges { i  j } :  A k ,Y l = cov( A k , Y l )  A k  Y l (16) where cov(  ) is the covariance function,   is the standard deviation of the respective variable. Hence,  A k ,Y l measures the correlation between head k and dependency type l . A k ,Y l > 0 means that the model tends to use head k for propagating information from child to parent for dependency edges of the type l . Here, we only consider the Figure 4: Relationship between the parsing performance and the number of heads in each layer. information propagation from child to parent even though information can propagate in both directions in masked language models. In Appendix A.2, we also computed the PCC for the parent to child direction. Table 3 shows the PCC between the most frequent dependency types and their most correlated heads. We can observe that all three models have heads that are positively correlated to human-annotated dependency types. This result is coherent with the observation of Htut et al. (2019). Meanwhile, the UDGN achieves a significantly better correlation than the StructFormer and the Transformer. This confirms our intuition that competitive gated heads can better induce dependency types. Figure 4 shows the relation between the number of heads in each UDGN layer and the model's unsupervised parsing performance. Table 4 shows the model's performance when individual components are removed. We can observe that the number of heads has the most significant influence on unsupervised parsing performance. While this is only one head, the model fails to learn any meaningful structure. Then the parsing performance increase as the number of heads increase. And we observe 4773 Model MLM Argmax Chu-Liu PPL DDA UDA DDA UDA UDGN 59.3(0.5) 52.7(0.9) 58.3(0.7) 49.9(1.6) 61.8(0.9) Gates 69.5(1.9) 31.5(2.2) 40.7(0.3) 26.1(2.1) 48.9(0.5) Competition 73.6(3.1) 44.7(1.9) 54.4(1.9) 40.4(1.6) 56.6(2.1) relative pos bias 62.1(1.0) 51.6(1.6) 59.8(0.8) 47.4(2.6) 62.1(1.1) Table 4: The performance of UDGN after removing different components. marginal improvement after the number of heads reaching 8. The second most significant parsing performance decrease is caused by removing the gating mechanism. This change forces each head to always extract the same information from a given key node h j , regardless of the query node h i . This has a similar effect as the previous change, reducing the diversity of different functions that can be modeled by heads. These two observations may suggest that the diversity of information propagation function (multiple heads) is essential to induce a meaningful structure. The competitive controller also has an important influence on parsing performance. Its noncompetitive version is the sigmoid controller used in StructFormer. If we replace it with the noncompetitive controller, the DDA decreases to 44.7 which is similar to the result of StructFormer (46.2). Another interesting observation is that removing relative position bias has the least influence on parsing and language modeling. This may suggest that the dependency structure already encoded certain positional information. More ablation experiment results can be found in Appendix A.3. In this experiment, the goal was to determine if a better representation of semantics can be encoded if the model was constrained for structure. We pretrain a UDGN model on the BLLIP-XL dataset, and then finetune it on the STS-B (Cer et al., 2017) dataset. For a controlled experiment, we compare the results we attain with the previously mentioned Transformer model. We then evaluate the resulting classifier on the STS 2012-2016 (Agirre et al., 2012, 2013, 2014, 2015, 2016), the SICK-Relatedness (Marelli et al., 2014) dataset, and STS-B (Cer et al., 2017). We then report the Spearman correlation score for each dataset (the all' setting in Gao et al. 2021). We find that the UDGN model performs better overall than the transformer model. While these are not state-of-the-art results for these tasks, our comparison aimed to examine the benefit of the UDGN model over the Transformer architecture. It's also interesting to notice that if parameters in the parser are frozen during the finetuning, the model will get worse performance. This result suggests that fine-tuning on STS forces pretrained language models to learn more task-oriented trees. Dai et al. (2021) observed similar results with finetuned RoBERTa on Aspect-Based Sentiment Analysis tasks. 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 4774 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.
abstain abstain objective objective abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain objective other abstain abstain objective result method result other other other other other other other other other abstain other other other other other other other other objective other other other other other method other other other abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain method abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result other abstain abstain abstain abstain abstain abstain abstain abstain abstain result result abstain abstain abstain other result result result abstain result abstain method abstain abstain abstain abstain method abstain abstain method abstain method abstain abstain abstain abstain method abstain abstain result abstain abstain result abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain result result abstain result abstain abstain abstain abstain objective abstain abstain abstain objective abstain