StructFormer: Joint Unsupervised Induction of Dependency and Constituency Structure from Masked Language Modeling
Authors: Yikang Shen
Yi Tay
Che Zheng
Dara Bahri
Donald Metzler
Aaron Courville
Venue:  (2021)
Keywords: Unsupervised Dependency Parsing
Unsupervised Constituency Parsing
Masked Language Model

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 generates constituency tree and dependency graph. Then we integrate the induced dependency relations into 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.

Under review as a conference paper at ICLR 2021
STRUCTFORMER: JOINT UNSUPERVISED INDUCTION OF DEPENDENCY AND CONSTITUENCY STRUCTURE FROM MASKED LANGUAGE MODELING
Anonymous authors Paper under double-bling review
ABSTRACT
There are two major classes of natural language grammars the dependency grammar that models one-to-one correspondences between words and the con- stituency grammar that models assembly of one or several corresponded words. While previous unsupervised parsing methods mostly focus only in- ducing one class of grammars, we introduce novel model, StructFormer, that can induce dependency and constituency structure at the same time. To achieve this, we propose new parsing framework that can jointly generates constituency tree and dependency graph. Then we integrate the induced dependency relations into transformer, in a differentiable manner, through a novel dependency-connsträine 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 have been exciting breath of recent work that are targeted at learning this structure in data-driven unsupervised fashion. 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 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 (Shen et al.) 2018a C Wang et al.) 2019) Kim et al.) 2019b a). However, most of these works focus on learning constituency structures alone. To the best of our knowledge, there have been no prior model or work that is able to induce, in an unsupervised fashion, more than one grammar structure at once.
In this paper, make two important technical contributions. First, we introduce the neural model that is able to induce dependency structures from raw data in an end-to-end unsupervised fashion. Most of existing approaches induce dependency structures from other syntactic information like gold POS tags (Klein Manning 2004 Cohen & Smith (2009 Jiang et af.] 2016). Previous works, that have trained from words alone, often requires additional information. like pre-trained word clustering (Spitkovsky et al.) 2011), pre-trained word embedding (He et al. 2018). acoustic cues (Pate Goldwater 2013). Second, we introduce the first neural model that is able to induce both dependency structure and constituency structure at the same time. Specifically, our approach aims unify latent structure induction of different types of grammar within the same framework.
annotated data from related languages (Cohen al.) (01T).
We introduce a new inductive bias that enables the Transformer models induce a directed depen- dency graph in fully unsupervised manner. To avoid the need of grammar labels during training, we use a distance-based parsing mechanism. The key idea is that predicts a sequence of Syntactic Distances T (Shen et al.) 2018b) and sequence of Syntactic Heights A (Luo et al. 2019) to repre- sent dependency graph and constituency trees at the same time. Examples of A and T are illustrated in Figure Ta Based on the syntactic distances (T) and syntactic heights (A), provide new aopenddecy-coostrainee
dependency constrained self-attention layer to replace the multi-head self-attention layer in stan- dard transformer model. More concretely, each attention head only attend on its parent (to avoid

---

Under review as a conference paper at ICLR 2021
like
cats
h2
cats
calss
h1
d1
like
d2
h3
2
Parent distribution
Dependent distribution
(b) Two types of dependency relations. The parent dis- tribution allows each token attend its parent. The dependent distribution allows token to attend its dependents. For example the parent of cat is like. Cat and I are dependents of 1 like Each attention head will receive different weighted sum of these lations.
like
cats
(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).
An example of our parsing mechanism and pnpeeddency-contrrainn self-attention mecha- nism. The parsing network first predicts the syntactic distance ' and syntactic height A to represent the latent structure of the input sentence I like cats. Then the parent and dependent relations computed in differentiable manner from T and A.
Figure I:
confusion with self-attention head, we use "parent" to note "head" in dependency graph) or its de- pendents in the predicted dependency structure, through weighted sum of different relations shown in Figure [b. In this way, replace the complete graph in the standard transformer model with differentiable directed dependency graph. During the process of training on a downstream task (c.g. masked language model), the model will gradually converge to reasonable dependency graph via gradient descent. Thus, the parser can be trained an unsupervised manner as a component of the model.
Incorporating the new parsing mechanism, the former architecture, introduce model named StructFormer. The proposed model can per- form unsupervised dependency and constituency parsing at the same time, and can leverage the parsing results to achieve strong performance masked language model tasks.
constrained self-attention, and the Trans-
RELATED WORK
Previous works on unsupervised dependency parsing are primarily based on the dependency model with valence (DMV) (Klein & Manning. 2004) and its extension (Daumé III] 2009 Gillenwater al. 20T0). To effectively learn the DMV model for better parsing accuracy, a variety inductive biases and handerafted features, such as correlations between parameters of grammar rules involv- ing different part-of-speech (POS) tags, have been proposed to incorporate prior information into learning. The most recent progress is the neural DMV model (Jiang al. 2016), which uses ral network model to predict the grammar rule probabilities based on the distributed representation of POS tags. However, most previous unsupervised dependency parsing algorithms require the gold POS tags as input, which are labeled by humans and can be potentially difficult (or prohibitively expensive) obtain for large corpora. [Spitkovsky al. (20TT) proposed overcome this problem with unsupervised word clustering that can dynamically assign tags to each word considering its context.
Unsupervised constituency parsing has recently received more attention. PRPN (Shen et al. 2018 Sa) and ON-LSTM (Shen et al. 20T8c) induce tree structure by introducing an inductive bias recur- rent neural networks. PRPN proposes parsing network to compute the syntactic distance of all word pairs, and a reading network utilizes the syntactic structure to attend to relevant memories. ON-LSTM allows hidden neurons to learn long-term short-term information by novel gating mechanism and activation function. In URNNG (Kim et al. 2019b), amortized variational infer- applied between recurrent neural network grammar (RNNG) (Dyer et al. 2016) decoder and a tree structure inference network. which encourages the decoder to generate reasonable tree structures. DIORA (Drozdov al. 2019) proposed using inside-outside dynamic programming
2

---

Under review as a conference paper at ICLR 2021
compose latent representations from all possible binary trees. The representations of inside and out- side passes from the same sentences are optimized to be close to each other. Compound PCFG (Kim et al. 2019a) achieves grammar induction maximizing the marginal likelihood of the sentences which are generated by probabilistic context-free grammar (PCFG) in a corpus. Tree Transformer (Wang et al., (219) adds extra locality constraints the Transformer encoder's self-attention courage 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 further tokens when climbing to higher layers.
Though large scale pre-trained models have dominated most natural language processing tasks, some recent work indicates that neural network models can see accurarey gains by leveraging syntactic information rather then ignoring it (Marcheggiani
Titov 2017 Strubell al.] 2018). [Strubel] self-attention that force one attention head to attend
er al. (218)) introduces syntactically-inforie on the syntactic governor of input token. [Omote al. (2019) and Deguchi et al. (2019) argue that dependencc-informet
self-attention can improve Transformer's performance tion. Kuncoro et al. (2020) shows that syntactic biases help large scale pre-trained models, like BERT, to achieve better language understanding.
machine transla-
SYNTACTIC DISTANCE AND HEIGHT
In this section, we first reintroduce the concepts of syntactic distance and height, then discuss their relations the context of StructFormer.
Algorithm 2 Converting binary constituency tree to dependency graph
function DEPENDENT(T, A)
Algorithm Distance to binary constituency
2:
if T then
tree
D D. parent + w
1: function CONSTITUENT(W, d)
4:
else
2: if = then
child, child, T
3:
T = Leaf(w)
6:
Di, parent, Dependent (child,, A)
4:
else
7:
Dr. parent, + Dependent(child,,
5:
i + arg arg (d)
8:
D = Union (D.. D,)
6:
child, < Constituent( dev)
9:
if A(parent,) > A(parent,) then
7:
child, + Constituent(w w dsi)
D.add(parent) parent < parenty else
parent,))
8:
T 4= Node(child, child,)
11:
9:
return T
12:
13:
D.add(parent, + parent,) parent & parent,
14:
15:
return D, parent
3.1 SYNTACTIC DISTANCE
Syntactic distance is proposed in Shen et (2018b) quantify the process of splitting sentences into smaller constituents.
Definition 3.1. Let be constituency tree for sentence (wo. w.)) The height of the lowest common ancestor for consecutive words æ; and 21+1 Å. Syntactic distances T (70. Tn Tn-1) are defined as a sequence of n real scalars that share the same rank as -n.....7n11).
In other words, each syntactic distance d; associated with a split point (i, 1) and specify the relative order in which the sentence will be split into smaller components. Thus, any sequence of n real values can unambiguously map to an unlabeled binary constituency tree with n leaves through the Algorithm (Shen al. 2018b). As Shen al. (201 8c a); Wang et al. (2019) pointed out, the syntactic distance reflects the information communication between constituents. More con- cretely, large syntactic distance т; represents that less short-term local information should be communicated between (x<z) and (x>x). While cooperating with correct inductive bias, we can leverage this feature build unsupervised dependency parsing models.
3

---

Under review as a conference paper at ICLR 2021
3.2 SYNTACTIC HEIGHT
Syntactic height is proposed in Luo et al. (2019), where the syntactic height is used to capture the distance to the root node in dependency graph. A word with high syntactic height means it is close to the root node. In this paper, to match the definition of syntactic distance, we redefine syntactic height as:
Definition 3.2. Let D be dependency graph for sentence (Wo, .... wn). The height of token wa in D is o;. The syntactic heights of D can be any sequence of real scalars A (ōa: -... 6n) that share the same rank as (ōu.... 8n-1).
Although the syntactic height is defined based on the dependency structure, we cannot rebuild the original dependency structure just by syntactic heights, since there is no information about whether token should be attached to the left side or the right side. However, given unlabelled constituent tree, we can convert it into a dependency graph with the help of syntactic distance. The convert- ing process is similar to the standard process of converting constituency treebank dependency treebank (Gelbukh et al. 2005). Instead of using the constituent labels and POS tags to identify the parent of each constituent, ent of each constituent. The converting algorithm is described in Algorithm 2 In Appendix [ also proposed joint algorithm, that takes T and A inputs and output constituency tree and dependency graph at the same time.
simply assign the token with largest syntactic height as the par-
3.3 THE RELATION BETWEEN SYNTACTIC DISTANCE AND HEIGHT
As discussed previously, the syntactic distance controls information communication between the two side of the split point. The syntactic height quantifies the centrality of each token in the dependency graph. A token with large syntactic height tend to have more long-term dependency relations to connect different part of the sentence together. In StructFormer, and height in the same scale. Given a split point (i, + 1) and it's syntactic distance 6, only tokens ry with 7, ó; can have connections across the split point (i, + 1). Thus tokens with small syntactic height will be limited to mostly attend on near tokens.
quantify the syntactic distance
4 STRUCTFORMER
In this section, we present the StructFormer model. Figure Former, which includes parser network and Transformer module. The parser network predicts and A, then passes them to a set of differentiable functions to generate dependency distributions. The Transformer module takes these distributions and the sentence input to computes contextual embedding for each position. The StructFormer can be trained in an end-to-end fashion on a Masked Language Model task. In this setting, the gradient back propagates through the relation distributions into the parser.
2a shows the architecture of Struct-
4.1 PARSING NETWORK
shown Figure 2b the parsing network takes word embeddings as input and feeds them into several convolution layers:
81,5 = tanh (Conv (81-1. 81 -..,, ((-1,+
(1)
where $t,; is the output of 1-th layer at i-th position, $0,6 is the input embedding of token w,, and 2W - is the convolution kernel size.
Given the output of the convolution stack 8N,i, parameterize the syntactic distance T as:
T WT tanh
WT
8N,i 8N.+1
+
b
(2)
where 8, is the contextualized distance for the i-th split point between token w, and w.41- The syntactic height A is parameterized in a similar way:
ó; wi tanh (W SNN (9) bq.
(3)
4

---

Under review as a conference paper at ICLR 2021
p(x)
Distance d
Height h
Dependency distributions
Transformer Layers
Parser
Convolution layers x N
Embeddings
Embeddings
(a) Model Architecture
(b) Parsing Network
The Architecture of StructFormer. The parser takes shared word embeddings input, outputs syntactic distances T, syntactic heights A, and dependency distributions hetween tokens. The transformer layers take word embeddings and dependency distributions input, output contex- tualized embeddings for input words.
Figure 2:
4.2
ESTIMATE THE DEPENDENCY DISTRIBUTION
Given T and A, we now explain how esti- mate the probability ((;y);;) that the j-th token the parent of the i-th token. The first step is identifying the smallest legit constituent C(a:), that contains 2; and æ;; not C(zx)'s parent. The second step is identifying the parent of the constituent zÿ = Pr(C((z)). Given the discus- sion in section 3.2 the parent of C(a))) must be the parent æ;. Thus, the two-stages of identi- fying the parent of x; can be formulated as:
Heights A:
x3
5
x4
3
2.5
x5
2
1.5
x1
x8
D(x,) Pr(C(z:))
(4)
0.5
x2
x7
In StructFormer, C(x:)) is represented as con-
Distonces T:
0
3
2
0
stituent [1, r). where 1 is the starting index (1 S
((x1
x2)
x3)
(x4
(45
(X6
x8)I))
i) of C(x,) and is the ending index (r 2 i) of C(a,). For example, in Figure C(xa) =
Figure 3: An example of T, A and respective de- pendency graph D.
[4, 8] and the parent of constituent Pr([4, 8))
Ig. thus D(x.)= Zg.
In dependency graph, æ, is only connected its parent and dependents. It means that æ; don't 't have direct connection to the outside of C(x.). In other words, C(xx)) = [1.r] is the smallest constituent that satisfies:
(5) where 7:-1 is the first Tei that is larger then 8; while looking backward, and T, is the first T2i that larger then 5, while looking forward. In the previous, ó4 3.5, 73 = 4 > dg and Ts = 00 84 thus C(ra) [4, 8). To make this process differentiable, we define ты as real value and 8; a probability distribution p(5.). For the simplicity and efficiency of computation, parameterize the cumulative distribution function p(o; > Tk) with sigmoid function:
8, <-T1 8, <
directly
p(o. > Tx) o(6, Tx)/P1)
(6)
where is the sigmoid function, 8, is the mean of distribution p(..) and μr is a learnable temperature term. Thus the probability that the 1-th < i) token is inside C(x,) is equal to the probability that is larger then the maximum distance 7 between / and i:
p(1 E C(x:)) p(ō, > max(7:-1 7)) o( max max ((-1))/m)
Then we can compute the probability distribution for I:
(llf)()l)) = Σ
(k(l))
Σ
(kefe(kl)) = p(1 E C(x,)) - p(1 1E C(x,))
kE|U.
kE[1,1-1
a((6: max(mi Te- 1)/mm) o(6;; max(7=1,-.,,
(8)
5

---

Under review as a conference paper at ICLR 2021
Similarly, compute the probability distribution for
Pright (rli) ( Tr- - -o((;; max max
(9)
The probability distribution for r (2²) can be computed as:
(i)rss(()))righhel (rl)), Isisr otherwise
PC r((i)
(10)
0,
The second step is to identify the parent of [., For any constituent [1, choose the j = argmaxse((.r) (6x) as the parent of r] In the previous example, given constituent [4, 8],
the maximum syntactic height is ó6 = 4.5, thus Pr([4,8) = I6. We use softmax function to parameterize the probability ppr ppr(il((r])
exp(h:/H2) Eieker exp(ht/pp) 0,
ppr (i((,)
(11)
otherwise
Given probability p( rl) and p([(rr]1)), compute the probability that 2, is the parent of zz
PD(11) ( Ppr (0w.eeii0..rr(0(.11 i itj
(12)
i=
4.3 DEPENDENCY- MULTI-HEAD SELF ATTENTION
The multi-head self-attention transformer can be seen as information propagation mechanism on the complete graph G = (X, E), where the set of vertices X contains all n. tokens in the sentence, and the set of edges E' contains all possible word pairs (I,, 22). StructFormer replace the complete graph G with soft dependency graph D (Xx A), where A is the set of probability distribution (pD(j)) (j(t} that represent the probability of existing and directed edge between the dependent and the parent j. The reason that called it directed edge is that each specific head is only allow to propagate information either from parent to dependent or from from dependent to parent. To do so, structformer associate each attention head with probability distribution over parent or dependent relation.
(w parentt Ppaaent expl Mparens +
Pdep
Wripp) exp (Wpppeee Hexpp Wide
(13)
where Wparent and Wdep are learnable parameters that associated with each attention head, Pparent is the probability that this head will propagate information from parent to dependent, vice versa. The model will learn to assign this association from the downstream task via gradient descent. Then we can compute the probability that information can propagated from node j to node i via this head:
Pijj Pparent (j(i) + PdepPD (ilj)
(14)
However, Htut et al. (2019) pointed out that different heads tend to associate with different type of universal dependency relations (including nsub j. obj. advmod, etc), but there no generalist head can that work with all different relations. To accommodate this observation, we compute a individual probability for each head and pair of tokens (z),
QKT
Ji.j = sigmoid
(15)
dd
where Q and K are query and key matrix in standard transformer model and dy is the dimension of attention head. The equation is inspired by the scaled dot-product attention in transformer. We replace the original softmax function with sigmoid function, so (i.j became an independent proba- bility that indicate whether the specific could work with the work (,;,,;) In the end, we propose to replace transformer's scaled dot- produut attention with our dependencyy
self-attention:
Attention (Q,, K2, Vj. D) Pi.jiisV
(16)

---

Under review as a conference paper at ICLR 2021
5 EXPERIMENTS
We evaluate the proposed model on three tasks: Masked Language Modeling, Unsupervised Con- situency Parsing and Unsupervised Dependency Parsing.
Our implementation of StructFormer is close to the original Transformer encoder (Vaswani et al, 2017). Except that we put the layer normalization in front of each layer, similar the T5 model (Raffel et al. 2019). We found that this modification allows the model to converges faster. For all experiments, we set the number of layers
8, the embedding size and hidden size to be dmodel = 512, the number of self-attention heads h = 8, the feed-forward size djf = 2048, dropout rate as 0.1, and the number of convolution layers in the parsing network as I,p 1p==3 =3
5.1 MASKED LANGUAGE MODEL.
Masked Language Modeling (MLM) has been widely used as pretraining object for larger scale pre- training models. In BERT (Devlin et al. 2018) and RoBERTa (Liu et al. 2019). authors found that MLM perplexities
held-out evaluation set have a positive correlation with the end-task perfor- mance. We trained and evaluated our model on different datasets: the Penn TreeBank (PTB) and BLLIP. In our MLM experiments, each individual token has independent chance be replaced by a mask token <mask>, except that we never replace < unk > token. The training and evaluation object for Masked Language Model is to predict the replaced tokens. The performance MLM is evaluated measuring perplexity on masked words.
PTB is a standard dataset for language modeling (Mikolov et al. 2012) and unsupervised con- stituency parsing (Shen et al., 2018c) Kim et al., 2019a). Following the setting proposed in Shen al. (2018c), we use Mikolov et al. 22012's prepossessing process, which removes all punctua- tions, and replaces low frequency tokens with <unk>. The preprocessing results in vocabulary size 10001 (including <unk>, <pad> and <mask>). For PTB, we use 30% mask rate.
BLLIP is a large Penn Treebank-style parsed corpus of approximately 24 million sentences. We train and evaluate StructFormer on three splits of BLLIIP: BLLIP-XS (40k sentences, 1M tokens), BLLIP-SM (200K sentences, 5M tokens), and BLLIP-MD (600K sentences, 14M tokens). They obtained by randomly sampling sections from BLLIP 1987-89 Corpus Release 1. All models are tested shared held-out test set (20k sentences, 500k tokens). Following the settings provided in (Hu et al., 2020), we use subword-level vocabulary extracted from the GPT-2 pre-trained model rather than the BLLIP training corpora. For BLLIP,
15% mask rate.
5.2 UNSUPERVISED CONSTITUENCY PARSING
The unsupervised constituency parsing task compares the latent tree structure induced by the model with those annotated by human experts. We use the Alogrithm to predict the constituency trees from T predicted by StructFormer. Following the experiment settings proposed in Shen et al. (0188),, we take the model trained on PTB dataset, and evaluate on WSJ test set. The WSJ test set is the section 23 of WSJ corpus, it contains 2416 human expert labeled sentences. Punctuation is ignored during the evaluation.
5.3 UNSUPERVISED DEPENDENCY PARSING
The unsupervised dependency parsing evaluation compares the induced dependency relations with those in the reference dependency graph. The most common metric is Unlabeled Attachment Score (UAS), which measures the percentage that a token correctly attached to its parent in the reference tree. Another widely used metric for unsupervised dependency parsing is Undirected Unlabeled Attachment Score (UUAS) measures the percentage that the reference undirected and unlabeled connections are recovered by the induced tree. Similar to the unsupervised constituency parsing, we take the model trained on PTB dataset, and evaluate it on WSJ test set (section 23). For the WSJ test set, reference dependency graphs are converted from its human annotated constituency trees. However, there are two different sets of rules for the conversion: the Stanford dependencies and the CoNLL dependencies. While Stanford dependencies unsupervised parsing papers, we noticed that our model sometimes output dependency structures that are closer the CoNLL dependencies. Therefore, report UAS and UUAS for both Stanford
used reference dependencies in previous

---

Under review as a conference paper at ICLR 2021
Model
PTB
BLLIP-XS
BLLIP-SM
BLLIP-MD
Transformer
64.05
93.90 57.28
19.92 18.70
14.31
StructFormer
60.94
13.70
Table 1: Masked Language Model perplexities on BLLIP datasets of different models.
Methods
UAS
w/o gold POS tags
Methods
UFI
DMV (Klein & Manning 2004
35.8
RANDOM
21.6
E-DMV (Headden III et al
2009
38.2
LBRANCH
9.0
UR-A E-DMV &Tu Honavar
2012
46.1
RBRANCH
39.8
CS* (Spitkovsky et al 2013)
64.4
Neural E-DM (Jang
42.7
Pre-trained LMy
Gaussian DMV (He (He ct al. 2018)
43.1 (1.2)
BERT-large
34.2
INP (Hc ct al. 2018
47.9 (1.2)
GPT2*
37.1
Structlormer
46.2 (0.4)
XLNet-base*
40.1
w/ gold POS tags (for reference only)
Unsupervised Parsing Models
DMV (Klein & Manning 2004)
39.7
PRPN (Shen et al.
2018a)
37.4 (0.3)
UR-A E-DMV (Iu & Honavar 2012
57.0
ON-LSTM (Shen ct al.
20T8c
47.7 (1.5)
MaxEnc (Le Zundemal 2015
65.8
Tree-T [Wang et al. 2019)
49.5
Neural E-DMV (Jiang el al 2016
57.6
URNNG (Km et al.
2019b
52.4
CRFAE (Cai et al. 2017
55.7
C-PCFG (Kim el al.
2019a
55.2
L-NDMV" (Han et al.
2017
63.2
StructFoommr
54.0 (0.3)
(b) Dependency Parsing Results on WSJ testset. Starred entries (+) benefit from additional punctuation- constraints. Daggered entries (*) benefit from larger ad- ditional training data. Baseline results are from He et al.) (2018).
(a) Constituency Parsing Results.
results are
from Kim et al. 2220))
Table 2: The unsupervised parsing performance of different models.
and CONLL dependencies. Following the setting previous papers (Jiang et al. 2016), we ignored the punctuation during evaluation. To obtain the dependency relation from our model, compute the argmax for dependency distribution:
k (
(17)
and assign the k-th token as the parent of i-th token.
5.4 EXPERIMENTAL RESULTS
The masked language model results are shown in Table StructFormer consistently outperform our Transformer baseline. This result aligns with previous observations that linguistic informed self- attention can help Transformers achieve stronger performance. We also observe that StructFormer converges much faster than the standard Transformer model.
Table 2a shows that our model achieves strong results on unsupervised constituency parsing. While the C-PCFG (Kim al., 2019a) achieve stronger parsing performance with its strong linguistic constraints (e.g. finite set of production rules), StructFormer may have border domain of appli- cation. For example, can replace standard transformer encoder in most of popular large-scale pretrained language models (e.g. BERT and ReBERTa) and transformer based machine translation models. It's also interesting to notice that, different from Tree-T (Wang et al., 2019), we didn't. directly constituents restrict the self-attention receptive field. But eventually achieve stronger constituency parsing performance with same experiment setting. This result may suggest that the dependency relations els. Table 3 shows that our model achieve strong accuracy while predicting Noun Phrase (NP), Preposition Phrase (PP), Adjective Phrase (ADJP), and Adverb Phrase (ADVP).
suitable for grammar induction in transformer-based mod-
Table 2b shows that our model achieves competitive dependency parsing performance while com- paring to other models that do not require gold POS tags. While most of baseline models still relies
8

---

Under review as a conference paper at ICLR 2021
PRPN
ON
C-PCFG
Tree-T
StructFormer
SBAR
50.0%
52.5%
56.1 %
36.4%
48.7%
NP
59.2%
64.5%
74.7%
67.6%
72.1%
VP
46.7%
41.0%
41.7%
38.5%
43.0%
PP 57.2%
54.4%
68.8%
52.3%
74.1 %
ADJP
44.3%
38.1%
40.4%
24.7%
51.9 %
ADVP
32.8%
31.6%
52.5%
55.1%
69.5%
Table 3: Fraction of ground truth constituents that were predicted as a constituent by the models broken down by label (i.e. label recall)
Relations
MLM
Constituency UFI
Stanford
Conll
PPL
UAS
UUAS
UAS
UUAS
parent+dep
60.9 (1.0)
54.0 (0.3)
46.2 (0.4)
61.6 (0.4)
36.2 (0.1)
56.3 (0.2)
parent
63.0 (1.2)
40.2 (3.5)
32.4 (5.6)
49.1 (5.7)
30.0 (3.7)
50.0 (5.3)
dep
63.2 (0.6)
51.8 (2.4)
15.2 (18.2)
41.6 (16.8)
20.2 (12.2)
44.7 (13.9)
Table 4: The performance of StruetFormer with different combinations of attention masks.
on some kind of latent POS tags pretrained word embeddings, StructFormer can be seen easy-to-use alternative that works in an end-to-end fashion. Table shows that our model recov- ers 61.6% of undirected dependency relations. Given the strong performances on both dependency parsing and masked language modeling. we believe that the dependency graph schema could be an viable substitute for the complete graph schema used in standard transformer.
Since our model uses a mixture of relation probability distribution for each self-attention head, we also studied how different combinations of relations effect the performance of model. Table 5) shows that the model can achieve the best performance, while using both parent and dependent relations. The model suffers more dependency parsing, if the parent relation is removed. And if the dependent relation is removed, the model will suffers more on the constituency parsing.
CONCLUSION
In this paper, we introduce novel dependency and constituency joint parsing framework. Based on the framework, propose StructFormer, supervised dependency and constituency parsing at the same time. We also introduced a novel dependencyy-constriine
unsupervised parsing algorithm that does un-
self-attention mechanism that allows each attention head to foeus spe- cific mixture of dependency relations. This brings Transformers closer to modeling a directed de- pendency graph. The experiments show premising results that StructFormer can induce meaningful dependency and constituency structures and achieve better performance on masked language model task. This research provides new path to build more linguistic bias into pre-trained language model.
REFERENCES
Jiong Cai, Yong Jiang, and Kewei Tu. Crf autoencoder for unsupervised dependency parsing. arXiv preprint arXiv:/708.0I1 01018, 2017.
Shay B Cohen and Noah A Smith. Shared logistic normal distributions for soft parameter tying in unsupervised grammar induction. Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pp. 74-82, 2009.
Shay B Cohen, Dipanjan Das, and Noah A Smith. Unsupervised structure prediction with non- parallel multilingual guidance. In Proceedings of the 2011 Conference Empirical Methods in Natural Language Processing, pp. 50-61, 2011.
Hal Daumé III. Unsupervised search-based structured prediction. In Proceedings of the 26th Annual International Conference Machine Learning, pp. 209-216, 2009.

---

Under review as a conference paper at ICLR 2021
Hiroyuki Deguchi, Akihiro Tamura, and Takashi Ninomiya. Dependency- based self-attention for transformer nmt. In Proceedings of the International Conference on Recent Advances in Natural Language Processing (RANLP 2019), pp. 239-246, 2019.
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805. 2018.
Andrew Drozdov, Patrick Verga, Mohit Yadav, Mohit lyyer, and Andrew McCallum. Unsupervised latent tree induction with deep inside-outside recursive auto-encoders. In Proceedings the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume / (Long and Short Papers), pp. 1129-1141, 2019.
Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah Smith. Recurrent neural network grammars. In Proceedings of NAACL-HIT,, pp- 199-209, 2016.
Alexander Gelbukh, Sulema Torres, and Hiram Calvo. Transforming a constituency treebank into a dependency treebank. Procesamiento del lenguaje natural, (35):145-152, 2005.
Jennifer Gillenwater, Kuzman Ganchev, João Graça Fernando Pereira, and Ben Taskar. Sparsity in dependency grammar induction. ACL 2010, pp. 194, 2010.
Wenjuan Han, Yong Jiang, and Kewei Tu. Dependency grammar induction with neural lexicalization and big training data, arXiv preprint arXiv:1788.0088 2017.
Junxian He, Graham Neubig, and Taylor Berg-Kirkpatrick Unsupervised learning of syntactic structure with invertible neural projections. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 1292-1302, 2018.
William Headden III. Mark Johnson, and David McClosky. Improving unsupervised dependency parsing with richer contexts and smoothing. In Proceedings of human language technologies: the 2009 annual conference of the North American chapter of the association for computational linguistics, pp. 101-109, 2009.
Phu Mon Htut, Jason Phang, Shikha Bordia, and Samuel R Bowman. Do attention heads in bert track syntactic dependencies? arXiv preprint arXiv: 1911.2266,, 2019.
Jennifer Hu, Jon Gauthier, Peng Qian, Ethan Wilcox, and Roger P Levy. systematic assessment of syntactic generalization in neural language models. arXiv preprint arXiv:2005.03692 2020.
Yong Jiang, Wenjuan Han, Kewei Tu, et al. Unsupervised neural dependency parsing. Association for Computational Linguistics (ACL), 2016.
Taeuk Kim, Jihun Choi, Daniel Edmiston, and Sang-goo Lee. Are pre-trained language mod- els aware of phrases? simple but strong baselines for grammar induction. arXiv preprint arXiv:2002.00737, 2020.
Yoon Kim, Chris Dyer, and Alexander M Rush. Compound probabilistic context-free grammars for grammar induction. In Proceedings of the 57th Annual Meeting of the Association for Computa- tional Linguistics, pp. 2369-2383 2019a.
Yoon Kim, Alexander M Rush, Lei Yu, Adhigunaa Kuncoro, Chris Dyer, and Gábor Melis. Un- supervised recurrent neural network grammars. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies. Volume I (Long and Short Papers), pp. 1105-1117, 2019b.
Dan Klein and Christopher D Manning. Corpus-based induction of syntactic structure: Models of dependency and constituency. In Proceedings of the 42nd annual meeting of the association for computational linguistics (ACL-04), pp. 478-485, 2004.
Adhiguna Kuncoro, Lingpeng Kong, Daniel Fried, Dani Yogatama, Laura Rimell, Chris Dyer, and Phil Blunsom. Syntactic structure distillation pretraining for bidirectional encoders. arXiv preprint arXiv:2005. 10220005.34484 13482, 2020.
10

---

Under review as a conference paper at ICLR 2021
Phong Le and Willem Zuidema. Unsupervised dependency parsing: Let's use supervised parsers. arXiv preprint arXiv: 52..0004666..6 2015.
Yinhan Liu, Myle Ou, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprini arXiv: 1692, 2019.
Hongyin Luo, Lan Jiang, Yonatan Belinkov, and James Glass. Improving neural language models by segmenting, attending, and predicting the future. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 1483-1493, 2019.
Diego Marcheggiani and Ivan Titov. Encoding sentences with graph convolutional networks for semantic role labeling. arXiv preprint arXiv: (el.::/703048266 2017.
Tomáš Mikolov et al. Statistical language models based on neural networks. Presentation at Google, Mountain View 2nd April, 80:26, 2012.
Yutaro Omote, Akihiro Tamura, and Takashi Ninomiya. Dependency-basee relative positional en- coding for transformer nmt. In Proceedings of the International Conference on Recent Advances in Natural Language Processing (RANLP 2019), pp. 854-861, 2019.
John K Pate and Sharon Goldwater. Unsupervised dependency parsing with acoustic cues. Trans- actions of the Association for Computational Linguistics, 1:63-74, 2013.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint 1rXiv: 10683, 2019.
Yikang Shen, Zhouhan Lin, Chin-wei Huang, and Aaron Courville. Neural language modeling by jointly learning syntax and lexicon. In International Conference Learning Representations, 2018a.
Yikang Shen, Zhouhan Lin, Athul Paul Jacob, Alessandro Sordoni, Aaron Courville, and Yoshua Bengio. Straight to the tree: Constituency parsing with neural syntactic distance. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1171-1180, 2018b.
Yikang Shen, Shawn Tan, Alessandro Sordoni, and Aaron Courville, Ordered neurons: Integrating tree structures into recurrent neural networks. In International Conference on Learning Repre- sentations, 2018c.
Valentin Spitkovsky, Hiyan Alshawi, Angel Chang, and Dan Jurafsky. Unsupervised dependency parsing without gold part-of-speech tags. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pp. 1281-1290, 2011.
Valentin Spitkovsky, Daniel Jurafsky, and Hiyan Alshawi Breaking out of local optima with count transforms and model recombination: A study in grammar induction. 2013.
Emma Strubell, Patrick Verga, Daniel Andor, David Weiss, and Andrew McCallum. Linguistically- informed self-attention for semantic role labeling. arXiv preprint arXiv: 1
2018.
Kewei Tu and Vasant Honavar. Unambiguity regularization for unsupervised learning of probabilis- tic grammars. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 1324-1334, 2012.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-599900 2017.
Yaushian Wang, Hung-Yi Yi Lee, and Yun-Nung Chen. Tree transformer: Integrating tree structures into self-attention. In Proceedings of the 2019 Conference Empirical Methods in Natural Lan- guage Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP- pp. 1070, 2019.
11

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.1 JOINT DEPENDENCY AND CONSTITUENCY PARSING
Algorithm The joint dependency and constituency parsing algorithm. Inputs are sequence of words w, syntactic distances d, syntactic heights h. Outputs are a binary constituency tree T, dependeney graph D that is represented as set of dependency relations, the parent of dependency graph D, and the syntactic height of parent.
1: function BUILDTREE(W, d, h) if d = [ and w [w] and h [hi] then
2:
3:
T Lwa D = [. parent + w, height +
4:
else
5:
= arg max(d)
6:
Tí, Di, parenty, height, BuildTreedde;, Wis,, hes) hss)
7:
T Dr, parent,. height, = BuildTree(ds., Wat hys)
8:
T Node(child, < Tr, child, + T,)
9:
D + Union(D,, D,)
if height, > height, then
11:
D.add(parent, <- parent,)
12:
parent < parent,, height < height,
13:
else
14:
D.add(parent, + parent;) parent + parent,, height + height, return T, D. parent, height
15:
12

---

Under review as a conference paper at ICLR 2021
B DEPENDENCY RELATION WEIGHTS FOR SELF-ATTENTION HEADS
0
4
5
6
7
0.5
0.0
0.0
0.5
0.0
0.5
0.0
0.5
0.0
0.0
(a) Dependency relation weights learnt PTB
5
0.5
0.0
0.5
0.5
0.0
0.5
0.0
0.0
0.5
0.5
0.0
(b) Dependency relation weights learnt on BLLIP-SM
Figure 4: Dependency relation weights learnt on different datasets. Row i constains relation weights for all attention heads in the i-th transformer layer. p represents the parent relation. d represents the dependent relation. We observe clearer preference for each attention head in the model trained on BLLIP-SM. This probably due to BLLIP-SM has signficantly more training data. It's also interesting to notice that the first layer tend focus parent relations.
13

---

Under review as a conference paper at ICLR 2021
C
DEPENDENCY DISTRIBUTION EXAMPLES
hooker
0.00
0.05
0.26
0.07
0.04
0.07
0.02
0.11
0.22
0.00
0.28
0.04
0.02
0.04
0.01
0.06
philosophy
0.17
0.06
0.00
0.09
0.05
0.08
0.03
0.14
was
0.11
0.03
0.20
0.00
0.05
0.09
0.03
0.15
to
0.12
0.00
0.04
build
0.09
0.03
0.16
0.0%
0.07
0.00
0.05
0.25
and
0.04
0.01
0.07
0.03
0.06
0.00
0.10
0.03
0.18
0.08
0.06
0.12
0.04
0.00
hooker
philosophy
was
1
build
and
Sell
there
0.00
0.02
0.05
0.13
0.06
0.02
0.07
0.02
0.10
0.13
0.00
0.11
0.19
0.03
0.01
0.03
0.01
0.04
nothing
0.14
0.09
0.00
0.24
0.05
0.02
0.05
0.02
0.07
rational
0.14
0.05
0.10
0.00
0.08
0.03
0.09
0.03
0.13
about
0.09
0.02
0.05
0.13
0.00
0.04
0.10
0.04
0.14
this
0.05
0.01
0.02
0.07
0.06
0.00
0.17
0.06
0.14
kind
0.08
0.02
0.04
0.11
0.08
0.07
0.00
0.07
0.21
0.04
0.01
0.02
0.06
0.05
0.05
0.16
0.00
0.20
action
0.08
0.02
0.04
0.12
0.08
0.04
0.12
0.04
0.00
there
nothing
rational
about
this
kind
action
Figure 5: Dependency distribution examples from WSJ test set. Each row is the parent distribution for the respective word. The sum of each distribution may not equal to
14

---

Under review as a conference paper at ICLR 2021
D
THE PERFORMANCE OF STRUCTFORMER WITH DIFFERENT MASK RATES
Mask rate
MLM PPL
Constituency UFI
Stanford
Conll
UAS
UUAS
UAS
UUAS
0.1
45.3 (1.2)
51.45 (2.7)
31.4 (11.9)
51.2 (8.1)
32.3 (5.2)
52.4 (4.5)
0.2
50.4 (1.3)
(0.6)
312.6)
(8.8)
33.0
53.5 (4.7)
0.3
60.9 (1.0)
(0.3
46.2 (0.4)
61.6 (0.4)
(0.1
56.3 (0.2)
0.4
76.9 (1.2)
53.5
34.0 (10.3)
(7.4)
(5.4)
50.6 (4.1)
0.5
100.3 (1.4)
53.2
36.3 (9.8)
53.6
30.6 (4.2)
51.3 (3.2)
Table 5: The performance of StructFormer on PTB dataset with different mask rates. Dependency parsing is especially affected by the masks. Mask rate 0.3 provides the best and the most stable performance.
15


Reviews:
[{"review_id": "Z9WCzHGdU2O", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Updates after discussion/revision period:\n\nIt appears that the paper has improved. However, the changes appear to be so substantial that the paper is now essentially a different paper which would require a new review process. \n\n---------\n\nThis paper describes a neural architecture that resembles the transformer but includes explicit representations of constituency and dependency structure. The model is trained for masked language modeling (MLM) and evaluated via MLM on held-out data and its ability to induce constituency and dependency trees. The results are better than trivial baselines for unsupervised constituency and dependency parsing but not as strong as related recent work. \n\nThis paper has an interesting idea at its core: stemming from the success of models like ordered neurons, can we define a neural architecture that uses both constituency and dependency structure? The related notions of height and distance, combined with the syntactically-inspired attention masks, also seem interesting. \n\nUnfortunately, however, the current submission needs a lot of work before it will be ready for publication. There are three types of concerns I have about the paper in its current form:\n\n1. The description of the method is dense and difficult to understand, and has at least a few notational issues (details below). \n\n2. There are very few experimental details provided. Yes, space is limited in the main paper, but appendices are permitted as well and there were no appendices included in the submission. Basic questions about the experiments are not included, making it difficult to assess the paper. \n\n3. The experimental results are difficult to evaluate, as there are different datasets and assumptions made by different work, so there does not appear to be a baseline that the new model can be compared to fairly. it's unclear what the take-home message is. It would be beneficial to have some simpler baselines run by the authors on the same data they are using for training, in order to have a comparison that is fair. \n\nI'll discuss these three points below.\n\n 1. Clarity of model description and notational issues. \nFirst, I had some confusion about Alg. 1. \n- The BuildTree function call in line 8 does not match the function signature in line 1. Or is it supposed to be calling some other function that's not part of this algorithm?\n- What is k on line 12? k only seems to be defined in line 13.\n- I don't understand the notation in this part of line 14: \"head_i \\in {head_i}\\head_k\". I think it's confusing to use i in both head_i and {head_i}, because i is (I think) being used as an index which is iterated over. It would be more clear to use a different index (e.g., j) for one of these two instances of i. \n\nI also had some confusion about the StructFormer description. \n- Eq. (5) contains p_j^{C(i)} but then right below it when the equation is being described, there is a p_{i,j}^{ct} -- are these two related in some way? It's not clear to me how the notation should line up here. \n- Why does Eq. (9) have p(i \\leftarrow k) repeated twice? I think one of them should have a j. \n\nIn addition to my confusion about the uncertainties above, I found it difficult to follow the description of the StructFormer due to its density. Sec 4 would benefit from a more leisurely exposition, along with figures and potentially an example. \n\n2. The experiments are difficult for me to assess because many details are missing. For example:\n(a) How is masking done during training with masked language modeling? That is, what is the masking rate? Are whole words masked or subword units? Are any words that were selected to be masked left unchanged or swapped to be other words as in BERT? \n(b) What optimizer was used and how were learning rates selected? Was any early stopping done? If so, what criterion was used?\n(c) What is the value of the convolution kernel parameter W?\n(d) How was the gap value of 0.1 selected? How sensitive is the performance to this value?\n(e) It's not clear to me whether the masked language modeling comparison between the transformer and structformer is fair. Is the number of parameters comparable between those two models? Were they trained in similar ways?\n(f) UUAS is never actually defined (though I was able to figure it out based on context). \n\n3. The empirical comparison leaves something to be desired. The StructFormer reaches higher parsing accuracies than trivial baselines, but not as high as related recent work. However, the paper notes that it does not consider that related work as perfectly comparable. Some results that I think would be more comparable are not included in the results tables. Page 1 has the following text: \"Previous works, that have trained from words alone, often requires additional information, like pre-trained word clustering (Spitkovsky et al., 2011), pre-trained word embedding (He et al., 2018),...\".  Pretrained clusters or embeddings are unsupervised and therefore would be reasonable to compare to. The results tables omit results from these papers, instead reporting results from papers that use gold POS tags and other such information. But I would argue that a system that uses unsupervised word clusters or unsupervised word embeddings is fair to compare to. Why aren't the results from Spitkovsky et al and He et al included in the results tables?  In addition to comparing to prior work, it would help to characterize the performance of the StructFormer to include baselines that are trained on the same dataset as that used by the authors, so that we can disentangle the impact of some of the choices made here. \n\n\nBelow are typos and minor things:\n\n- p. 5: \"higher then all\" --> \"higher than all\"\n- p. 5: \"a unsupervised\" --> \"an unsupervised\"\n- p. 6: \"to converges faster\" --> \"to converge faster\"\n- p. 6: \"Alogrithm\" --> \"Algorithm\"\n- p. 7: The sentence starting with \"Since POS tags\" is not a complete sentence. \n- p. 7: \"infering\" --> \"inferring\"\n- p. 7: \"effect\" --> \"affect\"\n- p. 7: The sentence starting with \"Because it is\" is not a complete sentence. \n- p. 7: \"only have\" --> \"only having\"\n- p. 8: The caption of Fig 4 mentions s, but I think c was meant instead, as c is present in the figure while s is not.\n- p. 8: \"premising\" --> \"promising\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "VK4oHunUfi", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: this paper introduces a new deep-learning architecture for unsupervised parsing.  From a CNN on the input sentence, the model predicts a syntactic \"height\" for every word in the sentence and a syntactic \"distance\" for every inter-word position; these heights and distances determine the joint constituency & dependency parse of the sentence.  The parse in turn determines a soft attention mask for a Transformer encoder module.  The model is trained end-to-end on masked language modeling (MLM).  The model shows improvements in MLM perplexity over a standard Transformer baseline, and the authors present it as offering competitive unsupervised parsing scores relative to other models.\n\nEvaluation: the architecture is interesting and different enough to my knowledge from previous architectures that have been proposed that, together with competitive results on unsupervised parsing, would make for a compelling submission.  However, there are a number of unclarities in the paper that make it difficult to determine whether the results on unsupervised parsing are actually comparable to prior work.  It is essential that these unclarities be satisfactorily addressed in order to determine whether the paper is actually a candidate for acceptance.  I list the issues below; I am open to revising my score more positively if the authors are able to provide a compelling response.\n\n* The start of Section 5 states that the model is trained on BLLIP datasets and unsupervised parsing evaluation is on the WSJ testset.  Sections 5.2 and 5.3 don't say anything about using a different training set (e.g., the standard WSJ training set sections 2–21 as in Kim et al. 2019a), so I assume that the present paper is using BLLIP as a training set here (though the paper doesn't say which BLLIP dataset).  If that's the case, then unless the authors have re-trained all the competitor models listed in Table 1 on the BLLIP dataset, the StructFormer results are not comparable to any prior work because the training dataset isn't the same.  If I'm correct about this, it constitutes clear grounds for rejection of the paper.\n\n* The dependency results in Figure 1b are also confusing.  RANDOM and RBRANCH/LHEAD results are implausibly low (RBRANCH/LHEAD should be better than LBRANCH/RHEAD for English).  I don't see where the DMV or Shared LN results come from either.  Note also that Klein & Manning 2004 include results that don't use gold POS tags but rather word classes using a simple distributional clustering technique, and DMV takes only a fairly small performance hit from this, so it is not true that none of the * models can be directly compared with StructFormer.\n\n* Table 3 doesn't seem consistent with Table 1b: none of the dependency results in Table 3 match the 41.0 result for StructFormer listed in 1b.  Likewise, Table 4 MLM perplexities aren't consistent with Table 2.\n\n* Section 4.2 is very difficult for me to follow.  Since the tree is determined given {d} and {h}, it is odd for the authors write of probabilities of constitutents and relative word heights.  If the \\beta_{i,k} and p_j^{C(i)} are taken as probabilities, it doesn't look like the distribution over resulting trees will in general be proper.  And I am not even sure how it makes sense given the tree topology. For example, if j is in between i and head(i), then j *must* be in the smallest constituent that contains both w_i and w_head(i).  But head(i) is not even referred to in Equations 4 and 5.  Also note I, thattt can make all the { p_j^{C(i)} } arbitrarily large by setting the bias term to a large positive number, or arbitrarily small by setting the bias term to a large negative number.  I was confused enough after the first paragraph of Section 4.2 that I could not make sense of the second paragraph.  I would recommend a careful and comprehensive rewrite of this section.\n\n* in line 6 of Algorithm 1, it looks like the order in which the {d_i} are evaluated will matter for the resulting tree, and the i should be considered either in the order 1 to len(w) or len(w) to 1.  Clarification needed.\n\n* The only time that the \"gap\" argument in Algorithm 1 is mentioned in the paper is at the bottom of line 6, where they say they set gap = 0.1.  How was this determined?  Was this value optimized on held-out data (not the test set)? \n\n* is tie-breaking on distances or heights ever needed for Algorithm 1?  If so, how is tie-breaking done -- randomly?\n\n* in section 4.2, are \\tau and b learned?\n\n* Section 5.4: \"We also observe that StructFormer converges much faster than the standard Transformer model\" -- can you report this more precisely?\n\nErrors:\n\n* in Algorithm 1, the \"gap\" argument is missing in the call to BuildTree in line 8.\n\n* also in Algorithm 1, lines 12 and 13 seem to be reversed.\n\n* equation 9 seems wrong: I believe that the summand should be p(i -> k) p(j -> k).\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "GFfMiUlj8o7", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "SUMMARY\n\nThe paper extends PRPN with the syntactic height in Luo et al. (2019) to do dependency parsing simultaneously with constituency parsing. The main idea is to exploit constituents to infer dependencies. The heights and distances are learned by a masking scheme similar to PRPN, but the model is a tranformer MLM rather than a recurrent memory network. The proposed model achieves nontrivial parsing performance. \n\n\nSTRENGTHS\n- The observation that dependencies can be recovered from syntactic heights given constituents is insightful and motivates a natural joint parsing algorithm (Algorithm 1). \n\n- The new masking scheme that explicitly enforces MLM to be sensitive to dependency structure is interesting.\n\n- The experimental results are interesting. The model outperforms ON-LSTM in constituency parsing and is competitive with classical NLP methods that use gold POS tags in dependency parsing. Perplexity, while less helpful to look at in MLM than in LM, also improves substantially especially with small data. \n\n\nWEAKNESSES\n\n- Some derivations feel too terse. In the central equations (4) and (5), it is difficult to reason what it means for a word to be higher than the all the boundaries in a constituent. Intuitively this corresponds to the word being in the constituent, but some more rigorous explanation will be helpful.  \n\n- The paper is a bit sloppy in writing. The issues I had include: how is Definition 3.1 different from \"close to the root node\" (and why n-1)? In Algorithm 1 I will get an undefined variable error for k (line 13 should be above 12). How are the attention masks defined in equation (10) used? In fact, I still have difficulty understanding how the MLM is trained, as there is no mention of loss or objective (Section 5.1 is not about MLM: it is about data). I guess it is just standard MLM, but this seems to require some acknowledgement. \n\n- The dependency parsing performance is far behind the current SOTA (neural DMVs), even when we account for the fact that it does not use the POS information. It is still not much better than the left-branching baseline (33.3 vs 41). While this is probably due to the inherent difficulty of dependency induction, it is a bit underwhelming.  \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "9s_6eVvBvla", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a neural network optimized by MLM loss that has inductive bias to be useful for unsupervised constituency and dependency parsing. The core component of the neural net is \"parser\" that predicts a syntactic height and syntactic distance for each token. Following previous work, the distances yield constituency parse while the heights, in conjunction with the constituency parse yield the dependency tree.\n\nThe attention heads of the model focus on different dependency based masks for training.\n\nThe experimental results show that the method is effective to train a model in an unsupervised manner using just the raw data to predict dependency and constituency parses and performs better than the relevant baselines.\n\nMoreover, the ablation study shows that the different kinds of proposed dependency masks are important for obtaining good performance.\n\nWhile the paper claims that Figure 4 shows that attention heads learn to focus on different kinds of masks, I do not see a great difference between different attention heads and none of them seem to be biased toward one particular kind of mask. However, attention heads 1,2, and 5 do look interesting. Further analysis of attention heads would make the paper stronger.\n\nOne area where the paper suffers the most is readability. The math is broken at several spots and I am not sure if I understand the training objective (section 4.2) correctly.\n\n-- In the algorithm: line 8 -- the buildtree module seems to be taking different arguments than the procedure defined. The algorithm itself could be more clearly written down (the iterator symbols i is inconsistently used and is very confusing)\n\n-- Section 4.2: Maybe it would be helpful to describe the math with an example. But abuse of notation makes the paper incredibly unclear. \n\n-- -- For example what is p_j^{C_i} and p_{ij}^{ct} -- do they refer to similar quantities?\n\n-- -- How can a \"token\" w_j be a constituent spanning w_i and w_{head_i}?\n\n-- --Equation 9 doesn't look right. Equation 8 should be explained more clearly.\n\nThese examples of inaccessible writing (Algorithm and section 4.2) make the core part of the paper difficult to understand and hence I think this paper can be better with another round of thorough revision.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a novel approach to grammar induction. Like older work by Klein and Manning, the paper finds benefit in jointly inducing both constituency and dependency structure. However, unlike most approaches to grammar induction, the model is not generative -- rather, it is a transformer-based architecture that is trained to optimize a masked language modeling objective. The resulting parses appear to beat non-trivial baselines, but direct comparisons with several relevant state-of-the-art systems are not drawn. Reviewers overall found the approach interesting and novel. However, nearly all reviewers raised serious concerns about experimental comparisons with related work and brought up several missing state-of-the-art baselines that, like the proposed system, do not require gold POS. Reviewers also pointed out issues with clarity in several sections. In rebuttal, authors provide a substantial update to the original draft. So substantial that all reviewers mentioned in discussion that the new draft would effectively require an entirely new review. While I applaud authors for the substantial revisions, and while ICLR guidelines do not explicitly limit the amount change to a draft allowed in rebuttal, in this case the revisions are sufficiently drastic that I agree with reviewers that a new review process is required. Thus, I recommend rejection but strongly encourage authors to resubmit. 
Decision: Reject