nice empty nodes/.style= for tree= s sep=0.1em, l sep=0.33em, inner
ysep=0.4em, inner xsep=0.05em, l=0, calign=midpoint, fit=tight, where n
children=0 tier=word, minimum height=3em, , where n children=2 l-=0em, ,
parent anchor=south, child anchor=north, delay=if content= inner sep=0pt, edge
path=[edge] (!u.parent anchor) – (.south)edge label; , ,

# StructFormer: Joint Unsupervised Induction of Dependency and Constituency
Structure from Masked Language Modeling

Yikang Shen
Mila/Université de Montréal
&Yi Tay
Google Research
&Che Zheng
Google Research
Dara Bahri
Google Research
&Donald Metzler
Google Research
&Aaron Courville
Mila/Université de Montréal
Corresponding author<EMAIL_ADDRESS>Work done while interning at
Google Reseach.

###### 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 simultaneously induce dependency and constituency structure. To achieve
this, we propose a new parsing framework that can jointly generate a
constituency tree and dependency graph. Then we integrate the induced
dependency relations into the transformer, in a differentiable manner, through
a novel dependency-constrained self-attention mechanism. Experimental results
show that our model can achieve strong results on unsupervised constituency
parsing, unsupervised dependency parsing, and masked language modeling at the
same time. 111Published as a conference paper at ACL 2021.

##  1 Introduction

Human languages have a rich latent structure. This structure is multifaceted,
with the two major classes of grammar being dependency and constituency
structures. There has been an exciting breath of recent work targeted at
learning this structure in a data-driven unsupervised fashion (Klein and
Manning, 2002; Klein, 2005; Le and Zuidema, 2015; Shen et al., 2018c; Kim et
al., 2019a). The core principle behind recent methods that induce structure
from data is simple - provide an inductive bias that is conducive for
structure to emerge as a byproduct of some self-supervised training, e.g.,
language modeling. To this end, a wide range of models have been proposed that
are able to successfully learn grammar structures (Shen et al., 2018a, c; Wang
et al., 2019; Kim et al., 2019b, a). However, most of these works focus on
inducing either constituency or dependency structures alone.

In this paper, we make two important technical contributions. First, we
introduce a new neural model, StructFormer, that is able to simultaneously
induce both dependency structure and constituency structure. Specifically, our
approach aims to unify latent structure induction of different types of
grammar within the same framework. Second, StructFormer is able to induce
dependency structures from raw data in an end-to-end unsupervised fashion.
Most existing approaches induce dependency structures from other syntactic
information like gold POS tags (Klein and Manning, 2004; Cohen and Smith,
2009; Jiang et al., 2016). Previous works, having 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 and Goldwater, 2013), or annotated data from related
languages (Cohen et al., 2011).

(a) An example of Syntactic Distances $\mathrm{T}$ (grey bars) and Syntactic
Heights $\Delta$ (white bars). In this example, like is the parent (head) of
constituent (like cats) and (I like cats).

(b) Two types of dependency relations. The parent distribution allows each
token to attend on its parent. The dependent distribution allows each token to
attend on its dependents. For example the parent of cats is like. Cats and I
are dependents of like Each attention head will receive a different weighted
sum of these relations.

Figure 1: An example of our parsing mechanism and dependency-constrained self-
attention mechanism. The parsing network first predicts the syntactic distance
$\mathrm{T}$ and syntactic height $\Delta$ to represent the latent structure
of the input sentence I like cats. Then the parent and dependent relations are
computed in a differentiable manner from $\mathrm{T}$ and $\Delta$.

We introduce a new inductive bias that enables the Transformer models to
induce a directed dependency graph in a fully unsupervised manner. To avoid
the necessity of using grammar labels during training, we use a distance-based
parsing mechanism. The parsing mechanism predicts a sequence of Syntactic
Distances $\mathrm{T}$ (Shen et al., 2018b) and a sequence of Syntactic
Heights $\Delta$ (Luo et al., 2019) to represent dependency graphs and
constituency trees at the same time. Examples of $\Delta$ and $\mathrm{T}$ are
illustrated in Figure 1(a). Based on the syntactic distances ($\mathrm{T}$)
and syntactic heights ($\Delta$), we provide a new dependency-constrained
self-attention layer to replace the multi-head self-attention layer in
standard transformer model. More specifically, the new attention head can only
attend its parent (to avoid confusion with self-attention head, we use
“parent” to denote “head” in dependency graph) or its dependents in the
predicted dependency structure, through a weighted sum of relations shown in
Figure 1(b). In this way, we replace the complete graph in the standard
transformer model with a differentiable directed dependency graph. During the
process of training on a downstream task (e.g. masked language model), the
model will gradually converge to a reasonable dependency graph via gradient
descent.

Incorporating the new parsing mechanism, the dependency-constrained self-
attention, and the Transformer architecture, we introduce a new model named
StructFormer. The proposed model can perform unsupervised dependency and
constituency parsing at the same time, and can leverage the parsing results to
achieve strong performance on masked language model tasks.

##  2 Related Work

Previous works on unsupervised dependency parsing are primarily based on the
dependency model with valence (DMV) (Klein and Manning, 2004) and its
extension (Daumé III, 2009; Gillenwater et al., 2010). To effectively learn
the DMV model for better parsing accuracy, a variety of inductive biases and
handcrafted features, such as correlations between parameters of grammar rules
involving different part-of-speech (POS) tags, have been proposed to
incorporate prior information into learning. The most recent progress is the
neural DMV model (Jiang et al., 2016), which uses a neural network model to
predict the grammar rule probabilities based on the distributed representation
of POS tags. However, most existing unsupervised dependency parsing algorithms
require the gold POS tags to ge provided as inputs. These gold POS tags are
labeled by humans and can be potentially difficult (or prohibitively
expensive) to obtain for large corpora. Spitkovsky et al. (2011) proposed to
overcome this problem with unsupervised word clustering that can dynamically
assign tags to each word considering its context. He et al. (2018) overcame
the problem by combining DMV model with invertible neural network to jointly
model discrete syntactic structure and continuous word representations.

Unsupervised constituency parsing has recently received more attention. PRPN
(Shen et al., 2018a) and ON-LSTM (Shen et al., 2018c) induce tree structure by
introducing an inductive bias to recurrent neural networks. PRPN proposes a
parsing network to compute the syntactic distance of all word pairs, while a
reading network uses the syntactic structure to attend to relevant memories.
ON-LSTM allows hidden neurons to learn long-term or short-term information by
a novel gating mechanism and activation function. In URNNG (Kim et al.,
2019b), amortized variational inference was applied between a 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 et al., 2019) proposed using inside-outside dynamic
programming to compose latent representations from all possible binary trees.
The representations of inside and outside passes from the same sentences are
optimized to be close to each other. The compound PCFG (Kim et al., 2019a)
achieves grammar induction by maximizing the marginal likelihood of the
sentences which are generated by a probabilistic context-free grammar (PCFG).
Tree Transformer (Wang et al., 2019) adds extra locality constraints to the
Transformer encoder’s self-attention to encourage the attention heads to
follow a tree structure such that each token can only attend on nearby
neighbors in lower layers and gradually extend the attention field to further
tokens when climbing to higher layers. Neural L-PCFG (Zhu et al., 2020)
demonstrated that PCFG can benefit from modeling lexical dependencies. Similar
to StructFormer, the Neural L-PCFG induces both constituents and dependencies
within a single model.

Though large scale pre-trained models have dominated most natural language
processing tasks, some recent work indicates that neural network models can
see accuracy gains by leveraging syntactic information rather than ignoring it
(Marcheggiani and Titov, 2017; Strubell et al., 2018). Strubell et al. (2018)
introduces syntactically-informed self-attention that force one attention head
to attend on the syntactic governor of the input token. Omote et al. (2019)
and Deguchi et al. (2019) argue that dependency-informed self-attention can
improve Transformer’s performance on machine translation. Kuncoro et al.
(2020) shows that syntactic biases help large scale pre-trained models, like
BERT, to achieve better language understanding.

##  3 Syntactic Distance and Height

In this section, we first reintroduce the concepts of syntactic distance and
height, then discuss their relations in the context of StructFormer.

###  3.1 Syntactic Distance

Syntactic distance is proposed in Shen et al. (2018b) to quantify the process
of splitting sentences into smaller constituents.

######  Definition 3.1.

Let $\mathbf{T}$ be a constituency tree for sentence $(w_{1},...,w_{n})$. The
height of the lowest common ancestor for consecutive words $x_{i}$ and
$x_{i+1}$ is $\tilde{\tau}_{i}$. Syntactic distances
$\mathrm{T}=(\tau_{1},...,\tau_{n-1})$ are defined as a sequence of $n-1$ real
scalars that share the same rank as
$(\tilde{\tau}_{1},...,\tilde{\tau}_{n-1})$.

In other words, each syntactic distance $d_{i}$ is associated with a split
point $(i,i+1)$ and specify the relative order in which the sentence will be
split into smaller components. Thus, any sequence of $n-1$ real values can
unambiguously map to an unlabeled binary constituency tree with $n$ leaves
through the Algorithm 1 (Shen et al., 2018b). As Shen et al. (2018c, a); Wang
et al. (2019) pointed out, the syntactic distance reflects the information
communication between constituents. More concretely, a large syntactic
distance $\tau_{i}$ represents that short-term or local information should not
be communicated between $(x_{\leq i})$ and $(x_{>i})$. While cooperating with
appropriate neural network architectures, we can leverage this feature to
build unsupervised dependency parsing models.

Algorithm 1 Distance to binary constituency tree

1:function Constituent($\mathbf{w}$, $\mathbf{d}$)

2: if $\mathbf{d}=[]$ then

3: $\mathbf{T}\Leftarrow$ Leaf($\mathbf{w}$)

4: else

5: $i\Leftarrow\mathrm{arg}\max_{i}(\mathbf{d})$

6: $\mathrm{child}_{l}$ $\Leftarrow$ Constituent($\mathbf{w}_{\leq i}$,
$\mathbf{d}_{<i}$)

7: $\mathrm{child}_{r}$ $\Leftarrow$ Constituent($\mathbf{w}_{>i}$,
$\mathbf{d}_{>i}$)

8: $\mathbf{T}\Leftarrow\mathrm{Node}(\mathrm{child}_{l},\mathrm{child}_{r})$

9: return $\mathbf{T}$

Algorithm 2 Converting binary constituency tree to dependency graph

1:function Dependent($\mathbf{T}$, $\Delta$)

2: if $\mathbf{T}=w$ then

3: $\mathbf{D}\Leftarrow[],\mathrm{parent}\Leftarrow w$

4: else

5: $\mathrm{child}_{l},\mathrm{child}_{r}\Leftarrow\mathbf{T}$

6:
$\mathbf{D}_{l},\mathrm{parent}_{l}\Leftarrow\mathrm{Dependent}(\mathrm{child}_{l},\Delta)$

7:
$\mathbf{D}_{r},\mathrm{parent}_{r}\Leftarrow\mathrm{Dependent}(\mathrm{child}_{r},\Delta)$

8: $\mathbf{D}\Leftarrow\mathrm{Union}(\mathbf{D}_{l},\mathbf{D}_{r})$

9: if $\Delta(\mathrm{parent}_{l})>\Delta(\mathrm{parent}_{r})$ then

10:
$\mathbf{D}.\mathrm{add}(\mathrm{parent}_{l}\leftarrow\mathrm{parent}_{r}$)

11: $\mathrm{parent}$ $\Leftarrow\mathrm{parent}_{l}$

12: else

13:
$\mathbf{D}.\mathrm{add}(\mathrm{parent}_{r}\leftarrow\mathrm{parent}_{l}$)

14: $\mathrm{parent}$ $\Leftarrow\mathrm{parent}_{r}$

15: return $\mathbf{D},\mathrm{parent}$

###  3.2 Syntactic Height

Syntactic height is proposed in Luo et al. (2019), where it is used to capture
the distance to the root node in a 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 $\mathbf{D}$ be a dependency graph for sentence $(w_{1},...,w_{n})$. The
height of a token $w_{i}$ in $\mathbf{D}$ is $\tilde{\delta}_{i}$. The
syntactic heights of $\mathbf{D}$ can be any sequence of $n$ real scalars
$\Delta=(\delta_{1},...,\delta_{n})$ that share the same rank as
$(\tilde{\delta}_{1},...,\tilde{\delta}_{n})$.

Although the syntactic height is defined based on the dependency structure, we
cannot rebuild the original dependency structure by syntactic heights alone,
since there is no information about whether a token should be attached to the
left side or the right side. However, given an unlabelled constituent tree, we
can convert it into a dependency graph with the help of syntactic distance.
The converting process is similar to the standard process of converting
constituency treebank to dependency treebank (Gelbukh et al., 2005). Instead
of using the constituent labels and POS tags to identify the parent of each
constituent, we simply assign the token with the largest syntactic height as
the parent of each constituent. The conversion algorithm is described in
Algorithm 2. In Appendix A.1, we also propose a joint algorithm, that takes
$\mathrm{T}$ and $\Delta$ as inputs and jointly outputs a constituency tree
and dependency graph.

Figure 2: An example of $\mathrm{T}$, $\Delta$ and respective dependency graph
$\mathbf{D}$. Solid lines represent dependency relations between tokens.
StructFormer only allow tokens with dependency relation to attend on each
other.

###  3.3 The relation between Syntactic Distance and Height

As discussed previously, the syntactic distance controls information
communication between the two sides of the split point. The syntactic height
quantifies the centrality of each token in the dependency graph. A token with
large syntactic height tends to have more long-term dependency relations to
connect different parts of the sentence together. In StructFormer, we quantify
the syntactic distance and height on the same scale. Given a split point
$(i,i+1)$ and it’s syntactic distance $\delta_{i}$, only tokens $x_{j}$ with
$\tau_{j}>\delta_{i}$ can attend across the split point $(i,i+1)$. Thus tokens
with small syntactic height are limited to attend to nearby tokens. Figure 2
provides an example of $\mathrm{T}$, $\Delta$ and respective dependency graph
$\mathbf{D}$.

However, if the left and right boundary syntactic distance of a constituent
$[l,r]$ are too large, all words in $[l,r]$ will be forced to only attend to
other words in $[l,r]$. Their contextual embedding will not be able to encode
the full context. To avoid this phenomena, we propose calibrating $\mathrm{T}$
according to $\Delta$ in Appendix A.2

##  4 StructFormer

In this section, we present the StructFormer model. Figure 3(a) shows the
architecture of StructFormer, which includes a parser network and a
Transformer module. The parser network predicts $\mathrm{T}$ and $\Delta$,
then passes them to a set of differentiable functions to generate dependency
distributions. The Transformer module takes these distributions and the
sentence as input to computes a 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.

###  4.1 Parsing Network

(a) Model Architecture

(b) Parsing Network

Figure 3: The Architecture of StructFormer. The parser takes shared word
embeddings as input, outputs syntactic distances $\mathrm{T}$, syntactic
heights $\Delta$, and dependency distributions between tokens. The transformer
layers take word embeddings and dependency distributions as input, output
contextualized embeddings for input words.

As shown in Figure 3(b), the parsing network takes word embeddings as input
and feeds them into several convolution layers:

$\displaystyle
s_{l,i}=\tanh\left(\mathrm{Conv}\left(s_{l-1,i-W},...,s_{l-1,i+W}\right)\right)$
(1)

where $s_{l,i}$ is the output of $l$-th layer at $i$-th position, $s_{0,i}$ is
the input embedding of token $w_{i}$, and $2W+1$ is the convolution kernel
size.

Given the output of the convolution stack $s_{N,i}$, we parameterize the
syntactic distance $\mathrm{T}$ as:

$\displaystyle\tau_{i}=\left\\{\begin{array}[]{r}\mathbf{W}^{\tau}_{1}\tanh\left(\mathbf{W}^{\tau}_{2}\left[\begin{matrix}s_{N,i}\\\
s_{N,i+1}\end{matrix}\right]\right),\\\ 1\leq i\leq n-1\\\ \infty,\quad
i=0\quad\mathrm{or}\quad i=n\end{array}\right.$ (5)

where $\tau_{i}$ is the contextualized distance for the $i$-th split point
between token $w_{i}$ and $w_{i+1}$. The syntactic height $\Delta$ is
parameterized in a similar way:

$\displaystyle\delta_{i}=\mathbf{W}^{\delta}_{1}\tanh\left(\mathbf{W}^{\delta}_{2}s_{N,i}+b^{\delta}_{2}\right)+b^{\delta}_{1}$
(6)

###  4.2 Estimate the Dependency Distribution

Given $\mathrm{T}$ and $\Delta$, we now explain how to estimate the
probability $p(x_{j}|x_{i})$ such that the $j$-th token is the parent of the
$i$-th token. The first step is identifying the smallest legal constituent
$\mathbf{C}(x_{i})$, that contains $x_{i}$ and $x_{i}$ is not
$\mathbf{C}(x_{i})$’s parent. The second step is identifying the parent of the
constituent $x_{j}=\mathbf{Pr}(\mathbf{C}(x_{i}))$. Given the discussion in
section 3.2, the parent of $\mathbf{C}(x_{i})$ must be the parent of $x_{i}$.
Thus, the two-stages of identifying the parent of $x_{i}$ can be formulated
as:

$\mathbf{D}(x_{i})=\mathbf{Pr}(\mathbf{C}(x_{i}))$ (7)

In StructFormer, $\mathbf{C}(x_{i})$ is represented as constituent $[l,r]$,
where $l$ is the starting index ($l\leq i$) of $\mathbf{C}(x_{i})$ and $r$ is
the ending index ($r\geq i$) of $\mathbf{C}(x_{i})$.

In a dependency graph, $x_{i}$ is only connected to its parent and dependents.
This means that $x_{i}$ does not have direct connection to the outside of
$\mathbf{C}(x_{i})$. In other words, $\mathbf{C}(x_{i})=[l,r]$ is the smallest
constituent that satisfies:

$\displaystyle\delta_{i}<\tau_{l-1},$ $\displaystyle\delta_{i}<\tau_{r}$ (8)

where $\tau_{l-1}$ is the first $\tau_{<i}$ that is larger then $\delta_{i}$
while looking backward, and $\tau_{r}$ is the first $\tau_{\geq i}$ that is
larger then $\delta_{i}$ while looking forward. For example, in Figure 2,
$\delta_{4}=3.5$, $\tau_{3}=4>\delta_{4}$ and $\tau_{8}=\infty>\delta_{4}$,
thus $\mathbf{C}(x_{4})=[4,8]$. To make this process differentiable, we define
$\tau_{k}$ as a real value and $\delta_{i}$ as a probability distribution
$p(\tilde{\delta}_{i})$. For the simplicity and efficiency of computation, we
directly parameterize the cumulative distribution function
$p(\tilde{\delta}_{i}>\tau_{k})$ with sigmoid function:

$\displaystyle
p(\tilde{\delta}_{i}>\tau_{k})=\sigma((\delta_{i}-\tau_{k})/\mu_{1})$ (9)

where $\sigma$ is the sigmoid function, $\delta_{i}$ is the mean of
distribution $p(\tilde{\delta}_{i})$ and $\mu_{1}$ is a learnable temperature
term. Thus the probability that the $l$-th ($l<i$) token is inside
$\mathbf{C}(x_{i})$ is equal to the probability that $\tilde{\delta}_{i}$ is
larger then the maximum distance $\tau$ between $l$ and $i$:

$\displaystyle p(l\in\mathbf{C}(x_{i}))$ $\displaystyle=$ $\displaystyle
p(\tilde{\delta}_{i}>\max(\tau_{i-1},...,\tau_{l}))$ $\displaystyle=$
$\displaystyle\sigma((\delta_{i}-\max(\tau_{l},...,\tau_{i-1}))/\mu)$

Then we can compute the probability distribution for $l$:

$\displaystyle p(l|i)$ $\displaystyle=$ $\displaystyle
p(l\in\mathbf{C}(x_{i}))-p(l-1\in\mathbf{C}(x_{i}))$ (11) $\displaystyle=$
$\displaystyle\sigma((\delta_{i}-\max(\tau_{l},...,\tau_{i-1}))/\mu)-$
$\displaystyle\sigma((\delta_{i}-\max(\tau_{l-1},...,\tau_{i-1}))/\mu)$

Similarly, we can compute the probability distribution for $r$:

$\displaystyle p(r|i)$ $\displaystyle=$
$\displaystyle\sigma((\delta_{i}-\max(\tau_{i},...,\tau_{r-1}))/\mu)-$ (12)
$\displaystyle\sigma((\delta_{i}-\max(\tau_{i},...,\tau_{r}))/\mu)$

The probability distribution for $[l,r]=\mathbf{C}(x_{i})$ can be computed as:

$\displaystyle p_{\mathbf{C}}([l,r]|i)$ $\displaystyle=$
$\displaystyle\left\\{\begin{matrix}p(l|i)p(r|i),&l\leq i\leq r\\\
0,&\mathrm{otherwise}\end{matrix}\right.$ (13)

The second step is to identify the parent of $[l,r]$. For any constituent
$[l,r]$, we choose the $j=\mathrm{argmax}_{k\in[l,r]}(\delta_{k})$ as the
parent of $[l,r]$. In the previous example, given constituent $[4,8]$, the
maximum syntactic height is $\delta_{6}=4.5$, thus $\mathbf{Pr}([4,8])=x_{6}$.
We use softmax function to parameterize the probability
$p_{\mathbf{Pr}}(j|[l,r])$:

$\displaystyle
p_{\mathbf{Pr}}(j|[l,r])=\left\\{\begin{matrix}\frac{\exp(h_{j}/\mu_{2})}{\sum_{l\leq
k\leq r}\exp(h_{k}/\mu_{2})},&l\leq t\leq r\\\
0,&\mathrm{otherwise}\end{matrix}\right.$ (14)

Given probability $p(j|[l,r])$ and $p([l,r]|i)$, we can compute the
probability that $x_{j}$ is the parent of $x_{i}$:

$p_{\mathbf{D}}(j|i)=\left\\{\begin{matrix}\sum_{[l,r]}p_{\mathbf{Pr}}(j|[l,r])p_{\mathbf{C}}([l,r]|i),&i\neq
j\\\ 0,&i=j\end{matrix}\right.$ (15)

###  4.3 Dependency-Constrained Multi-head Self-Attention

The multi-head self-attention in the transformer can be seen as a information
propagation mechanism on the complete graph $\mathbf{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 $(x_{i},x_{j})$. StructFormer replace the
complete graph $\mathbf{G}$ with a soft dependency graph $\mathbf{D}=(X,A)$,
where $A$ is the matrix of $n\times n$ probabilities.
$A_{ij}=p_{\mathbf{D}}(j|i)$ is the probability of the $j$-th token depending
on the $i$-th token. The reason that we called it a 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 a probability distribution over parent or dependent
relation.

$\displaystyle p_{\mathrm{parent}}$ $\displaystyle=$
$\displaystyle\frac{\exp(w_{\mathrm{parent}})}{\exp(w_{\mathrm{parent}})+\exp(w_{\mathrm{dep}})}$
(16) $\displaystyle p_{\mathrm{dep}}$ $\displaystyle=$
$\displaystyle\frac{\exp(w_{\mathrm{dep}})}{\exp(w_{\mathrm{parent}})+\exp(w_{\mathrm{dep}})}$
(17)

where $w_{\mathrm{parent}}$ and $w_{\mathrm{dep}}$ are learnable parameters
that associated with each attention head, $p_{\mathrm{parent}}$ 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 be propagated from node $j$ to node $i$ via this head:

$\displaystyle
p_{i,j}=p_{\mathrm{parent}}p_{\mathbf{D}}(j|i)+p_{\mathrm{dep}}p_{\mathbf{D}}(i|j)$
(18)

However, Htut et al. (2019) pointed out that different heads tend to associate
with different type of universal dependency relations (including nsubj, obj,
advmod, etc), but there is 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 $(x_{i},x_{j})$:

$q_{i,j}=\mathrm{sigmoid}\left(\frac{QK^{T}}{\sqrt{d_{k}}}\right)$ (19)

where $Q$ and $K$ are query and key matrix in a standard transformer model and
$d_{k}$ 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 a sigmoid function, so $q_{i,j}$ became an independent
probability that indicates whether $x_{i}$ should attend on $x_{j}$ through
the current attention head. In the end, we propose to replace transformer’s
scaled dot-product attention with our dependency-constrained self-attention:

$\mathrm{Attention}(Q_{i},K_{j},V_{j},\mathbf{D})=p_{i,j}q_{i,j}V_{j}$ (20)

##  5 Experiments

We evaluate the proposed model on three tasks: Masked Language Modeling,
Unsupervised Constituency 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 to 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 $L=8$, the embedding size and hidden
size to be $d_{model}=512$, the number of self-attention heads $h=8$, the
feed-forward size $d_{ff}=2048$, dropout rate as $0.1$, and the number of
convolution layers in the parsing network as $L_{p}=3$.

###  5.1 Masked Language Model

Masked Language Modeling (MLM) has been widely used as a pretraining object
for larger-scale pretraining models. In BERT (Devlin et al., 2018) and RoBERTa
(Liu et al., 2019), authors found that MLM perplexities on held-out evaluation
set have a positive correlation with the end-task performance. We trained and
evaluated our model on 2 different datasets: the Penn TreeBank (PTB) and
BLLIP. In our MLM experiments, each token, including $<unk>$ token, has an
independent chance to be replaced by a mask token <mask>. The training and
evaluation object for Masked Language Model is to predict the replaced tokens.
The performance of MLM is evaluated by measuring perplexity on masked words.

PTB is a standard dataset for language modeling (Mikolov et al., 2012) and
unsupervised constituency parsing (Shen et al., 2018c; Kim et al., 2019a).
Following the setting proposed in Shen et al. (2018c), we use Mikolov et al.
(2012)’s prepossessing process, which removes all punctuations, and replaces
low frequency tokens with <unk>. The preprocessing results in a vocabulary
size of 10001 (including <unk>, <pad> and <mask>). For PTB, we use a 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 BLLIP: BLLIP-
XS (40k sentences, 1M tokens), BLLIP-SM (200K sentences, 5M tokens), and
BLLIP-MD (600K sentences, 14M tokens). They are obtained by randomly sampling
sections from BLLIP 1987-89 Corpus Release 1. All models are tested on a
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,
we use a 15% mask rate.

Model | PTB | BLLIP | BLLIP | BLLIP
---|---|---|---|---
-XS | -SM | -MD
Transformer | 64.05 | 93.90 | 19.92 | 14.31
StructFormer | 60.94 | 57.28 | 18.70 | 13.70
Table 1: Masked Language Model perplexities on different datasets.

The masked language model results are shown in Table 1. StructFormer
consistently outperforms our Transformer baseline. This result aligns with
previous observations that linguistically informed self-attention can help
Transformers achieve stronger performance. We also observe that StructFormer
converges much faster than the standard Transformer model.

###  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
Algorithm 1 to predict the constituency trees from $\mathrm{T}$ predicted by
StructFormer. Following the experiment settings proposed in Shen et al.
(2018c), we take the model trained on PTB dataset and evaluate it on WSJ test
set. The WSJ test set is section 23 of WSJ corpus, it contains 2416 human
expert labeled sentences. Punctuation is ignored during the evaluation.

Methods | UF1
---|---
RANDOM | 21.6
LBRANCH | 9.0
RBRANCH | 39.8
PRPN (Shen et al., 2018a) | 37.4 (0.3)
ON-LSTM (Shen et al., 2018c) | 47.7 (1.5)
Tree-T (Wang et al., 2019) | 49.5
URNNG (Kim et al., 2019b) | 52.4
C-PCFG (Kim et al., 2019a) | 55.2
Neural L-PCFGs (Zhu et al., 2020) | 55.31
StructFormer | 54.0 (0.3)
Table 2: Unsupervised constituency parsing tesults. * results are from Kim et al. (2020). UF1 stands for Unlabeled F1. | PRPN | ON | C-PCFG | Tree-T | Ours
---|---|---|---|---|---
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)

Table 2 shows that our model achieves strong results on unsupervised
constituency parsing. While the C-PCFG (Kim et al., 2019a) achieve a stronger
parsing performance with its strong linguistic constraints (e.g. a finite set
of production rules), StructFormer may have a border domain of application.
For example, it can replace the standard transformer encoder in most of the
popular large-scale pre-trained language models (e.g. BERT and ReBERTa) and
transformer based machine translation models. Different from the transformer-
based Tree-T (Wang et al., 2019), we did not directly use constituents to
restrict the self-attention receptive field. But StructFormer achieves a
stronger constituency parsing performance. This result may suggest that
dependency relations are more suitable for grammar induction in transformer-
based models. Table 3 shows that our model achieves strong accuracy while
predicting Noun Phrase (NP), Preposition Phrase (PP), Adjective Phrase (ADJP),
and Adverb Phrase (ADVP).

###  5.3 Unsupervised Dependency Parsing

Relations | MLM | Constituency | Stanford | Conll
---|---|---|---|---
| PPL | UF1 | 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 StructFormer with different combinations of
attention masks. UAS stands for Unlabeled Attachment Score. UUAS stands for
Undirected Unlabeled Attachment Score.

The unsupervised dependency parsing evaluation compares the induced dependency
relations with those in the reference dependency graph. The most common metric
is the Unlabeled Attachment Score (UAS), which measures the percentage that a
token is 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
are used as reference dependencies in previous unsupervised parsing papers, we
noticed that our model sometimes output dependency structures that are closer
to the CoNLL dependencies. Therefore, we report UAS and UUAS for both Stanford
and CoNLL dependencies. Following the setting of previous papers (Jiang et
al., 2016), we ignored the punctuation during evaluation. To obtain the
dependency relation from our model, we compute the argmax for dependency
distribution:

$k=\mathrm{argmax}_{j\neq i}p_{\mathbf{D}}(j|i)$ (21)

and assign the $k$-th token as the parent of $i$-th token.

Methods | UAS
---|---
_w/o gold POS tags_
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
CS* (Spitkovsky et al., 2013) | 64.4*
Neural E-DMV (Jiang et al., 2016) | 42.7
Gaussian DMV (He et al., 2018) | 43.1 (1.2)
INP (He et al., 2018) | 47.9 (1.2)
Neural L-PCFGs (Zhu et al., 2020) | 40.5 (2.9)
StructFormer | 46.2 (0.4)
_w/ gold POS tags (for reference only)_
DMV (Klein and Manning, 2004) | 39.7
UR-A E-DMV (Tu and Honavar, 2012) | 57.0
MaxEnc (Le and Zuidema, 2015) | 65.8
Neural E-DMV (Jiang et al., 2016) | 57.6
CRFAE (Cai et al., 2017) | 55.7
L-NDMV† (Han et al., 2017) | 63.2
Table 5: Dependency Parsing Results on WSJ testset. Starred entries (*)
benefit from additional punctuation-based constraints. Daggered entries (†)
benefit from larger additional training data. Baseline results are from He et
al. (2018).

Table 5 shows that our model achieves competitive dependency parsing
performance while comparing to other models that do not require gold POS tags.
While most of the baseline models still rely on some kind of latent POS tags
or pre-trained word embeddings, StructFormer can be seen as an easy-to-use
alternative that works in an end-to-end fashion. Table 4 shows that our model
recovers 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 a viable substitute for the
complete graph schema used in the standard transformer. Appendix A.4 provides
examples of parent distribution.

Since our model uses a mixture of the relation probability distribution for
each self-attention head, we also studied how different combinations of
relations affect the performance of our model. Table 4 shows that the model
can achieve the best performance while using both parent and dependent
relations. The model suffers more on dependency parsing if the parent relation
is removed. And if the dependent relationship is removed, the model will
suffer more on the constituency parsing. Appendix A.3 shows the weight for
parent and dependent relations learnt from MLM tasks. It’s interesting to
observe that Structformer tends to focus on the parent relations in the first
layer, and start to use both relations from the second layer.

##  6 Conclusion

In this paper, we introduce a novel dependency and constituency joint parsing
framework. Based on the framework, we propose StructFormer, a new unsupervised
parsing algorithm that does unsupervised dependency and constituency parsing
at the same time. We also introduced a novel dependency-constrained self-
attention mechanism that allows each attention head to focus on a specific
mixture of dependency relations. This brings Transformers closer to modeling a
directed dependency graph. The experiments show promising results that
StructFormer can induce meaningful dependency and constituency structures and
achieve better performance on masked language model tasks. This research
provides a new path to build more linguistic bias into a pre-trained language
model.

## References

  * Cai et al. (2017) Jiong Cai, Yong Jiang, and Kewei Tu. 2017.  Crf autoencoder for unsupervised dependency parsing.  _arXiv preprint arXiv:1708.01018_.
  * Cohen et al. (2011) Shay B Cohen, Dipanjan Das, and Noah A Smith. 2011.  Unsupervised structure prediction with non-parallel multilingual guidance.  In _Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing_ , pages 50–61.
  * Cohen and Smith (2009) Shay B Cohen and Noah A Smith. 2009.  Shared logistic normal distributions for soft parameter tying in unsupervised grammar induction.  In _Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics_ , pages 74–82.
  * Daumé III (2009) Hal Daumé III. 2009.  Unsupervised search-based structured prediction.  In _Proceedings of the 26th Annual International Conference on Machine Learning_ , pages 209–216.
  * Deguchi et al. (2019) Hiroyuki Deguchi, Akihiro Tamura, and Takashi Ninomiya. 2019.  Dependency-based self-attention for transformer nmt.  In _Proceedings of the International Conference on Recent Advances in Natural Language Processing (RANLP 2019)_ , pages 239–246.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Drozdov et al. (2019) Andrew Drozdov, Patrick Verga, Mohit Yadav, Mohit Iyyer, and Andrew McCallum. 2019\.  Unsupervised latent tree induction with deep inside-outside recursive auto-encoders.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 1129–1141.
  * Dyer et al. (2016) Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah A Smith. 2016.  Recurrent neural network grammars.  In _Proceedings of NAACL-HLT_ , pages 199–209.
  * Gelbukh et al. (2005) Alexander Gelbukh, Sulema Torres, and Hiram Calvo. 2005.  Transforming a constituency treebank into a dependency treebank.  _Procesamiento del lenguaje natural_ , (35):145–152.
  * Gillenwater et al. (2010) Jennifer Gillenwater, Kuzman Ganchev, João Graça, Fernando Pereira, and Ben Taskar. 2010.  Sparsity in dependency grammar induction.  _ACL 2010_ , page 194.
  * Han et al. (2017) Wenjuan Han, Yong Jiang, and Kewei Tu. 2017.  Dependency grammar induction with neural lexicalization and big training data.  _arXiv preprint arXiv:1708.00801_.
  * He et al. (2018) Junxian He, Graham Neubig, and Taylor Berg-Kirkpatrick. 2018.  Unsupervised learning of syntactic structure with invertible neural projections.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 1292–1302.
  * Headden III et al. (2009) William P Headden III, Mark Johnson, and David McClosky. 2009.  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_ , pages 101–109.
  * Htut et al. (2019) Phu Mon Htut, Jason Phang, Shikha Bordia, and Samuel R Bowman. 2019.  Do attention heads in bert track syntactic dependencies?  _arXiv preprint arXiv:1911.12246_.
  * Hu et al. (2020) Jennifer Hu, Jon Gauthier, Peng Qian, Ethan Wilcox, and Roger P Levy. 2020.  A systematic assessment of syntactic generalization in neural language models.  _arXiv preprint arXiv:2005.03692_.
  * Jiang et al. (2016) Yong Jiang, Wenjuan Han, Kewei Tu, et al. 2016.  Unsupervised neural dependency parsing.  Association for Computational Linguistics (ACL).
  * Kim et al. (2020) Taeuk Kim, Jihun Choi, Daniel Edmiston, and Sang-goo Lee. 2020.  Are pre-trained language models aware of phrases? simple but strong baselines for grammar induction.  _arXiv preprint arXiv:2002.00737_.
  * Kim et al. (2019a) Yoon Kim, Chris Dyer, and Alexander M Rush. 2019a.  Compound probabilistic context-free grammars for grammar induction.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 2369–2385.
  * Kim et al. (2019b) Yoon Kim, Alexander M Rush, Lei Yu, Adhiguna Kuncoro, Chris Dyer, and Gábor Melis. 2019b.  Unsupervised recurrent neural network grammars.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 1105–1117.
  * Klein (2005) Dan Klein. 2005.  _The unsupervised learning of natural language structure_.  Stanford University Stanford.
  * Klein and Manning (2002) Dan Klein and Christopher D Manning. 2002.  A generative constituent-context model for improved grammar induction.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pages 128–135.
  * Klein and Manning (2004) Dan Klein and Christopher D Manning. 2004.  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)_ , pages 478–485.
  * Kuncoro et al. (2020) Adhiguna Kuncoro, Lingpeng Kong, Daniel Fried, Dani Yogatama, Laura Rimell, Chris Dyer, and Phil Blunsom. 2020.  Syntactic structure distillation pretraining for bidirectional encoders.  _arXiv preprint arXiv:2005.13482_.
  * Le and Zuidema (2015) Phong Le and Willem Zuidema. 2015.  Unsupervised dependency parsing: Let’s use supervised parsers.  _arXiv preprint arXiv:1504.04666_.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Luo et al. (2019) Hongyin Luo, Lan Jiang, Yonatan Belinkov, and James Glass. 2019.  Improving neural language models by segmenting, attending, and predicting the future.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 1483–1493.
  * Marcheggiani and Titov (2017) Diego Marcheggiani and Ivan Titov. 2017.  Encoding sentences with graph convolutional networks for semantic role labeling.  _arXiv preprint arXiv:1703.04826_.
  * Mikolov et al. (2012) Tomáš Mikolov et al. 2012.  Statistical language models based on neural networks.  _Presentation at Google, Mountain View, 2nd April_ , 80:26.
  * Omote et al. (2019) Yutaro Omote, Akihiro Tamura, and Takashi Ninomiya. 2019.  Dependency-based relative positional encoding for transformer nmt.  In _Proceedings of the International Conference on Recent Advances in Natural Language Processing (RANLP 2019)_ , pages 854–861.
  * Pate and Goldwater (2013) John K Pate and Sharon Goldwater. 2013.  Unsupervised dependency parsing with acoustic cues.  _Transactions of the Association for Computational Linguistics_ , 1:63–74.
  * Raffel et al. (2019) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2019.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _arXiv preprint arXiv:1910.10683_.
  * Shen et al. (2018a) Yikang Shen, Zhouhan Lin, Chin-wei Huang, and Aaron Courville. 2018a.  Neural language modeling by jointly learning syntax and lexicon.  In _International Conference on Learning Representations_.
  * Shen et al. (2018b) Yikang Shen, Zhouhan Lin, Athul Paul Jacob, Alessandro Sordoni, Aaron Courville, and Yoshua Bengio. 2018b.  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)_ , pages 1171–1180.
  * Shen et al. (2018c) Yikang Shen, Shawn Tan, Alessandro Sordoni, and Aaron Courville. 2018c.  Ordered neurons: Integrating tree structures into recurrent neural networks.  In _International Conference on Learning Representations_.
  * Spitkovsky et al. (2011) Valentin I Spitkovsky, Hiyan Alshawi, Angel Chang, and Dan Jurafsky. 2011.  Unsupervised dependency parsing without gold part-of-speech tags.  In _Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing_ , pages 1281–1290.
  * Spitkovsky et al. (2013) Valentin I Spitkovsky, Daniel Jurafsky, and Hiyan Alshawi. 2013.  Breaking out of local optima with count transforms and model recombination: A study in grammar induction.
  * Strubell et al. (2018) Emma Strubell, Patrick Verga, Daniel Andor, David Weiss, and Andrew McCallum. 2018\.  Linguistically-informed self-attention for semantic role labeling.  _arXiv preprint arXiv:1804.08199_.
  * Tu and Honavar (2012) Kewei Tu and Vasant Honavar. 2012.  Unambiguity regularization for unsupervised learning of probabilistic grammars.  In _Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning_ , pages 1324–1334.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in neural information processing systems_ , pages 5998–6008.
  * Wang et al. (2019) Yaushian Wang, Hung-Yi Lee, and Yun-Nung Chen. 2019.  Tree transformer: Integrating tree structures into self-attention.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 1060–1070.
  * Zhu et al. (2020) Hao Zhu, Yonatan Bisk, and Graham Neubig. 2020.  The return of lexical dependencies: Neural lexicalized pcfgs.  _Transactions of the Association for Computational Linguistics_ , 8:647–661.

##  Appendix A Appendix

###  A.1 Joint Dependency and Constituency Parsing

Algorithm 3 The joint dependency and constituency parsing algorithm. Inputs
are a sequence of words $\mathbf{w}$, syntactic distances $\mathbf{d}$,
syntactic heights $\mathbf{h}$. Outputs are a binary constituency tree
$\mathbf{T}$, a dependency graph $\mathbf{D}$ that is represented as a set of
dependency relations, the $\mathrm{parent}$ of dependency graph $\mathbf{D}$,
and the syntactic $\mathrm{height}$ of $\mathrm{parent}$.

1:function BuildTree($\mathbf{w},\mathbf{d},\mathbf{h}$)

2: if $\mathbf{d}=[]$ and $\mathbf{w}=[w]$ and $\mathbf{h}=[h]$ then

3: $\mathbf{T}\Leftarrow\mathrm{Leaf}(w)$, $\mathbf{D}\Leftarrow[]$,
$\mathrm{parent}\Leftarrow w$, $\mathrm{height}$ $\Leftarrow h$

4: else

5: $i\Leftarrow\arg\max(\mathbf{d})$

6: $\mathbf{T}_{l},\mathbf{D}_{l},\mathrm{parent}_{l},\mathrm{height}_{l}$
$\Leftarrow$ BuildTree($\mathbf{d}_{<i},\mathbf{w}_{\leq i},\mathbf{h}_{\leq
i}$)

7: $\mathbf{T}_{r},\mathbf{D}_{r},\mathrm{parent}_{r},\mathrm{height}_{r}$
$\Leftarrow$ BuildTree($\mathbf{d}_{>i},\mathbf{w}_{>i},\mathbf{h}_{>i}$)

8:
$\mathbf{T}\Leftarrow\mathrm{Node}(\mathrm{child}_{l}\Leftarrow\mathbf{T}_{l},\mathrm{child}_{r}\Leftarrow\mathbf{T}_{r})$

9: $\mathbf{D}$ $\Leftarrow\mathrm{Union}(\mathbf{D}_{l}$, $\mathbf{D}_{r}$)

10: if $\mathrm{height}_{l}>\mathrm{height}_{r}$ then

11:
$\mathbf{D}.\mathrm{add}(\mathrm{parent}_{l}\leftarrow\mathrm{parent}_{r}$)

12: $\mathrm{parent}$ $\Leftarrow\mathrm{parent}_{l}$, $\mathrm{height}$
$\Leftarrow\mathrm{height}_{l}$

13: else

14:
$\mathbf{D}.\mathrm{add}(\mathrm{parent}_{r}\leftarrow\mathrm{parent}_{l}$)

15: $\mathrm{parent}$ $\Leftarrow\mathrm{parent}_{r}$, $\mathrm{height}$
$\Leftarrow\mathrm{height}_{r}$

16: return $\mathbf{T}$, $\mathbf{D}$, $\mathrm{parent}$, $\mathrm{height}$

###  A.2 Calibrating the Syntactic Distance and Height

In Section 3.3, we explained the relation between $\Delta$ and $\mathrm{T}$,
that if $\delta_{i}<\tau_{j}$, the $i$-th word won’t be able to attend beyond
the $j$-th split point. However, in a specific case, the constraint will
isolate a constituent $[l,r]$ from the rest of the sentence. If $\tau_{l-1}$
and $\tau_{r}$ are larger then all height ${\delta_{l,...,r}}$ in the
constituent, then all words in $[l,r]$ won’t be able to attend on the outside
of the constituent. This phenomenon will prevent their output contextual
embedding from encoding the full context. To avoid this phenomenon, we propose
to calibrate the syntactic distance $\mathrm{T}$ according to the syntactic
height $\Delta$. First, we compute the maximum syntactic height for each
constituent:

$\displaystyle\delta_{[l,r]}=\max\left(\delta_{l},...,\delta_{r}\right),\quad
l<r$ (22)

Then we compute the minimum difference between $\delta_{[l,r]}$ and $[l,r]$’s
left and right boundary distance. Since we only care about constituents that
the boundary distance is larger than its maximum height, we use a ReLU
activation function to keep only the positive values:

$\epsilon_{[l,r]}=\mathrm{ReLU}\left(\min\left(\tau_{l-1}-\delta_{[l,r]},\tau_{r}-\delta_{[l,r]}\right)\right)$
(23)

To make sure all constituent are not isolated and maintain the rank of
$\mathrm{T}$, we subtract all $\mathrm{T}$ by the maximum of $\epsilon$:

$\hat{\delta_{i}}=\delta_{i}-\max_{\\{[l,r]\\}/[1,n]}\left(\epsilon_{[l,r]}\right)$
(24)

###  A.3 Dependency Relation Weights for Self-attention Heads

(a) Dependency relation weights learnt on PTB

(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 a 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 to focus on
parent relations.

###  A.4 Dependency Distribution Examples

(a)

(b)

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 1. Against our intuition, the distribution is not very sharp.
This is partially due to the ambiguous nature of the dependency graph. As we
previously discussed, at least two styles of dependency rules (Conll and
Stanford) exist. And without extra constraint or supervision, the model seems
trying to model both of them at the same time. One interesting future work
will be finding an inductive bias that can encourage the model to converge to
a specific style of dependency graph.

###  A.5 The Performance of StructFormer with different mask rates

Mask rate | MLM | Constituency | Stanford | Conll
---|---|---|---|---
| PPL | UF1 | 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) | 54.0 (0.6) | 37.4 (12.6) | 55.6 (8.8) | 33.0 (5.7) | 53.5 (4.7)
0.3 | 60.9 (1.0) | 54.0 (0.3) | 46.2 (0.4) | 61.6 (0.4) | 36.2 (0.1) | 56.3 (0.2)
0.4 | 76.9 (1.2) | 53.5 (1.5) | 34.0 (10.3) | 52.0 (7.4) | 29.5 (5.4) | 50.6 (4.1)
0.5 | 100.3 (1.4) | 53.2 (0.9) | 36.3 (9.8) | 53.6 (6.8) | 30.6 (4.2) | 51.3 (3.2)
Table 6: 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.


\newblock Enabling counterfactual survival analysis with balanced
\newblock In \emph{Proceedings of the Conference on Health, Inference, and
Learning}, pages 133--145, 2021.

[Chen and Guestrin, 2016]
T.~Chen and C.~Guestrin.
\newblock {XGBoost}: A scalable tree boosting system.
\newblock In \emph{Proceedings of the 22nd ACM SIGKDD International Conference
on Knowledge Discovery and Data Mining}, pages 785--794, 2016.

[Chernozhukov et~al., 2018]
V.~Chernozhukov, D.~Chetverikov, M.~Demirer, E.~Duflo, C.~Hansen, W.~Newey, and
\newblock {Double/debiased machine learning for treatment and structural
\newblock \emph{The Econometrics Journal}, 21\penalty0 (1):\penalty0 C1--C68,

[Cheung et~al., 2017]
A.~K. Cheung, M.~Rahman, D.~M. Reboussin, T.~E. Craven, T.~Greene, P.~L.
Kimmel, W.~C. Cushman, A.~T. Hawfield, K.~C. Johnson, C.~E. Lewis, S.~Oparil,
M.~V. Rocco, K.~M. Sink, P.~K. Whelton, J.~T. Wright, J.~Basile, S.~Beddhu,
U.~Bhatt, T.~I. Chang, G.~M. Chertow, M.~Chonchol, B.~I. Freedman, W.~Haley,
J.~H. Ix, L.~A. Katz, A.~A. Killeen, V.~Papademetriou, A.~C. Ricardo,
K.~Servilla, B.~Wall, D.~Wolfgram, and J.~Yee.
\newblock Effects of intensive {BP} control in {CKD}.
\newblock \emph{Journal of the American Society of Nephrology}, 28\penalty0
(9):\penalty0 2812--2823, 2017.

[Collins et~al., 2015]
G.~S. Collins, J.~B. Reitsma, D.~G. Altman, and K.~G. Moons.
\newblock Transparent reporting of a multivariable prediction model for
individual prognosis or diagnosis ({TRIPOD}): the {TRIPOD} statement.
\newblock \emph{Journal of British Surgery}, 102\penalty0 (3):\penalty0
148--158, 2015.

[Cox, 1972]
D.~R. Cox.
\newblock Regression models and life-tables.
\newblock \emph{Journal of the Royal Statistical Society: Series B
(Methodological)}, 34\penalty0 (2):\penalty0 187--202, 1972.

[Crump et~al., 2009]
R.~K. Crump, V.~J. Hotz, G.~W. Imbens, and O.~A. Mitnik.
\newblock Dealing with limited overlap in estimation of average treatment
\newblock \emph{Biometrika}, 96\penalty0 (1):\penalty0 187--199, 2009.

[Cui et~al., 2022]
Y.~Cui, M.~R. Kosorok, E.~Sverdrup, S.~Wager, and R.~Zhu.
\newblock Estimating heterogeneous treatment effects with right-censored data
via causal survival forests.
\newblock \emph{arXiv preprint arXiv:2001.09887}, 2022.

[Curth and van~der Schaar, 2021]
A.~Curth and M.~van~der Schaar.
\newblock Nonparametric estimation of heterogeneous treatment effects: From
theory to learning algorithms.
\newblock In \emph{International Conference on Artificial Intelligence and
Statistics}, pages 1810--1818. PMLR, 2021.

[Curth et~al., 2021]
A.~Curth, C.~Lee, and M.~van~der Schaar.
\newblock Surv{ITE}: Learning heterogeneous treatment effects from
time-to-event data.
\newblock \emph{Advances in Neural Information Processing Systems}, 34,

[Curth et~al., 2021]
A.~Curth, D.~Svensson, J.~Weatherall, and M.~van~der Schaar.
\newblock Really doing great at estimating {CATE}? a critical look at {ML}
benchmarking practices in treatment effect estimation.
\newblock In \emph{Thirty-fifth Conference on Neural Information Processing
Systems Datasets and Benchmarks Track}, 2021{\natexlab{b}}.

[Cushman et~al., 2010]
W.~Cushman, G.~Evans, R.~Byington, D.~Jr, R.~Jr, J.~Cutler, D.~Simons-Morton,
J.~Basile, M.~Corson, J.~Probstfield, L.~Katz, K.~Peterson, W.~Friedewald,
J.~Buse, T.~Bigger, H.~Gerstein, F.~Ismail-Beigi, and E.~Siraj.
\newblock Effects of intensive blood-pressure control in type 2 diabetes
\newblock \emph{New England Journal of Medicine}, 362:\penalty0 1575--1585, 04

[Duan et~al., 2019]
T.~Duan, P.~Rajpurkar, D.~Laird, A.~Y. Ng, and S.~Basu.
\newblock Clinical value of predicting individual treatment effects for
intensive blood pressure therapy: a machine learning experiment to estimate
treatment effects from randomized trial data.
\newblock \emph{Circulation: Cardiovascular Quality and Outcomes}, 12\penalty0
(3):\penalty0 e005010, 2019.

[Feller et~al., 2019]
A.~Feller, J.~Murray, S.~Woody, and D.~Yeager.
\newblock Assessing treatment effect variation in observational studies:
Results from a data challenge.
\newblock \emph{Observational Studies}, 5:\penalty0 21--35, 01 2019.

[Foster and Syrgkanis, 2019]
D.~J. Foster and V.~Syrgkanis.
\newblock Orthogonal statistical learning.
\newblock \emph{arXiv preprint arXiv:1901.09036}, 2019.

[Friedman et~al., 2010]
J.~Friedman, T.~Hastie, and R.~Tibshirani.
\newblock Regularization paths for generalized linear models via coordinate
\newblock \emph{Journal of Statistical Software}, 33\penalty0 (1):\penalty0 1,

[Friedman et~al., 2022]
J.~Friedman, T.~Hastie, R.~Tibshirani, B.~Narasimhan, K.~Tay, N.~Simon,
J.~Qian, and J.~Yang.
\newblock \emph{glmnet: {L}asso and {E}lastic-{N}et {R}egularized {G}eneralized
{L}inear {M}odels}, 2022.
\newblock URL \url{https://glmnet.stanford.edu}.
\newblock R package version 4.1.4.

[Gao and Han, 2020]
Z.~Gao and Y.~Han.
\newblock Minimax optimal nonparametric estimation of heterogeneous treatment
\newblock \emph{Advances in Neural Information Processing Systems},
33:\penalty0 21751--21762, 2020.

[Goeman, 2010]
J.~J. Goeman.
\newblock $l_1$ penalized estimation in the {C}ox proportional hazards model.
\newblock \emph{Biometrical Journal}, 52\penalty0 (1):\penalty0 70--84, 2010.

[Goff et~al., 2014]
D.~C. Goff, D.~M. Lloyd-Jones, G.~Bennett, S.~Coady, R.~B. D’Agostino,
R.~Gibbons, P.~Greenland, D.~T. Lackland, D.~Levy, C.~J. O’Donnell, J.~G.
Robinson, J.~S. Schwartz, S.~T. Shero, S.~C. Smith, P.~Sorlie, N.~J. Stone,
and P.~W.~F. Wilson.
\newblock 2013 {ACC/AHA} guideline on the assessment of cardiovascular risk.
\newblock \emph{Circulation}, 129\penalty0 (25\_suppl\_2):\penalty0 S49--S73,

[Hahn et~al., 2020]
P.~R. Hahn, J.~S. Murray, and C.~M. Carvalho.
\newblock Bayesian regression tree models for causal inference: Regularization,
confounding, and heterogeneous effects (with discussion).
\newblock \emph{Bayesian Analysis}, 15\penalty0 (3):\penalty0 965--1056, 2020.

[Haider et~al., 2020]
H.~Haider, B.~Hoehn, S.~Davis, and R.~Greiner.
\newblock Effective ways to build and evaluate individual survival
\newblock \emph{Journal of Machine Learning Research}, 21\penalty0
(85):\penalty0 1--63, 2020.

[Harrell, 2015]
F.~E. Harrell.
\newblock \emph{Regression modeling strategies: with applications to linear
models, logistic and ordinal regression, and survival analysis}, volume~3.
\newblock Springer, 2015.

[Hastie and Tibshirani, 1993]
T.~Hastie and R.~Tibshirani.
\newblock Varying-coefficient models.
\newblock \emph{Journal of the Royal Statistical Society: Series B
(Methodological)}, 55\penalty0 (4):\penalty0 757--779, 1993.

[Hastie et~al., 2009]
T.~Hastie, R.~Tibshirani, and J.~Friedman.
\newblock \emph{The Elements of Statistical Learning: Data Mining, Inference,
and Prediction, Second Edition}.
\newblock Springer Series in Statistics. Springer New York, 2009.

[Henderson et~al., 2020]
N.~C. Henderson, T.~A. Louis, G.~L. Rosner, and R.~Varadhan.
\newblock Individualized treatment effects with censored data via fully
nonparametric bayesian accelerated failure time models.
\newblock \emph{Biostatistics}, 21\penalty0 (1):\penalty0 50--68, 2020.

[Hill, 2011]
\newblock Bayesian nonparametric modeling for causal inference.
\newblock \emph{Journal of Computational and Graphical Statistics}, 20\penalty0
(1):\penalty0 217--240, 2011.

[Hoogland et~al., 2021]
J.~Hoogland, J.~IntHout, M.~Belias, M.~M. Rovers, R.~D. Riley,
F.~E.~Harrell~Jr, K.~G. Moons, T.~P. Debray, and J.~B. Reitsma.
\newblock A tutorial on individualized treatment effect prediction from
randomized trials with a binary endpoint.
\newblock \emph{Statistics in Medicine}, 40\penalty0 (26):\penalty0 5961--5981,

[Horvitz and Thompson, 1952]
D.~G. Horvitz and D.~J. Thompson.
\newblock A generalization of sampling without replacement from a finite
\newblock \emph{Journal of the American Statistical Association}, 47\penalty0
(260):\penalty0 663--685, 1952.

[Hu et~al., 2021]
L.~Hu, J.~Ji, and F.~Li.
\newblock Estimating heterogeneous survival treatment effect in observational
data using machine learning.
\newblock \emph{Statistics in Medicine}, 40\penalty0 (21):\penalty0 4691--4713,

[Hu et~al., 2021]
L.~Hu, J.-Y. Lin, K.~Sigel, and M.~Kale.
\newblock Estimating heterogeneous survival treatment effects of lung cancer
screening approaches: A causal machine learning analysis.
\newblock \emph{Annals of Epidemiology}, 62:\penalty0 36--42,

[Imai and Ratkovic, 2013]
K.~Imai and M.~Ratkovic.
\newblock Estimating treatment effect heterogeneity in randomized program
\newblock \emph{The Annals of Applied Statistics}, 7\penalty0 (1):\penalty0
443--470, 2013.

[Ishwaran et~al., 2008]
H.~Ishwaran, U.~B. Kogalur, E.~H. Blackstone, and M.~S. Lauer.
\newblock Random survival forests.
\newblock \emph{The Annals of Applied Statistics}, 2\penalty0 (3):\penalty0
841--860, 2008.

[Jacob, 2021]
\newblock {CATE} meets {ML}--{T}he {C}onditional {A}verage {T}reatment {E}ffect
and {M}achine learning.
\newblock \emph{arXiv preprint arXiv:2104.09935}, 2021.

[Jaroszewicz and Rzepakowski, 2014]
S.~Jaroszewicz and P.~Rzepakowski.
\newblock Uplift modeling with survival data.
\newblock In \emph{ACM SIGKDD Workshop on Health Informatics (HI-KDD--14), New
York City}, 2014.

[Kennedy, 2020]
E.~H. Kennedy.
\newblock Optimal doubly robust estimation of heterogeneous causal effects.
\newblock \emph{arXiv preprint arXiv:2004.14497}, 2020.

[Kennedy et~al., 2022]
E.~H. Kennedy, S.~Balakrishnan, and L.~Wasserman.
\newblock Minimax rates for heterogeneous causal effect estimation.
\newblock \emph{arXiv preprint arXiv:2203.00837}, 2022.

[Kent et~al., 2016]
D.~Kent, J.~Nelson, P.~Rothwell, D.~Altman, and R.~Hayward.
\newblock Risk and treatment effect heterogeneity: Re-analysis of individual
participant data from 32 large clinical trials.
\newblock \emph{International Journal of Epidemiology}, 45:\penalty0 dyw118, 07

[Kent et~al., 2020]
D.~M. Kent, J.~K. Paulus, D.~van Klaveren, R.~B. D'Agostino, S.~Goodman, R.~A.
Hayward, J.~P.~A. Ioannidis, B.~Patrick-Lake, S.~C. Morton, M.~J. Pencina,
G.~Raman, J.~Ross, H.~P. Selker, R.~Varadhan, A.~J. Vickers, J.~B. Wong, and
E.~W. Steyerberg.
\newblock The predictive approaches to treatment effect heterogeneity ({PATH})
\newblock \emph{Annals of Internal Medicine}, 172\penalty0 (1):\penalty0
35--45, 2020.

[Knaus et~al., 2021]
M.~C. Knaus, M.~Lechner, and A.~Strittmatter.
\newblock Machine learning estimation of heterogeneous causal effects:
Empirical monte carlo evidence.
\newblock \emph{The Econometrics Journal}, 24\penalty0 (1):\penalty0 134--161,

[Kohler et~al., 2002]
M.~Kohler, K.~M{\'a}th{\'e}, and M.~Pint{\'e}r.
\newblock Prediction from randomly right censored data.
\newblock \emph{Journal of Multivariate Analysis}, 80\penalty0 (1):\penalty0
73--100, 2002.

[Kravitz et~al., 2004]
R.~Kravitz, N.~Duan, and J.~Braslow.
\newblock Evidence-based medicine, heterogeneity of treatment effects, and the
trouble with averages.
\newblock \emph{The Milbank Quarterly}, 82:\penalty0 661--687, 2004.

[K{\"u}nzel et~al., 2019]
S.~R. K{\"u}nzel, J.~S. Sekhon, P.~J. Bickel, and B.~Yu.
\newblock Metalearners for estimating heterogeneous treatment effects using
machine learning.
\newblock \emph{Proceedings of the national academy of sciences}, 116\penalty0
(10):\penalty0 4156--4165, 2019.

[Lazar et~al., 2010]
A.~Lazar, B.~Cole, M.~Bonetti, and R.~Gelber.
\newblock Evaluation of treatment-effect heterogeneity using biomarkers
measured on a continuous scale: Subpopulation treatment effect pattern plot.
\newblock \emph{Journal of Clinical Oncology: Official Journal of the American
Society of Clinical Oncology}, 28:\penalty0 4539--44, 2010.

[Lee et~al., 2016]
J.~D. Lee, D.~L. Sun, Y.~Sun, and J.~E. Taylor.
\newblock Exact post-selection inference, with application to the lasso.
\newblock \emph{The Annals of Statistics}, 44\penalty0 (3):\penalty0 907--927,

[Lin and Jeon, 2006]
Y.~Lin and Y.~Jeon.
\newblock Random forests and adaptive nearest neighbors.
\newblock \emph{Journal of the American Statistical Association}, 101\penalty0
(474):\penalty0 578--590, 2006.

[Ling et~al., 2021]
Y.~Ling, P.~Upadhyaya, L.~Chen, X.~Jiang, and Y.~Kim.
\newblock Heterogeneous treatment effect estimation using machine learning for
healthcare application: tutorial and benchmark.
\newblock \emph{arXiv preprint arXiv:2109.12769}, 2021.

[Naghi and Wirths, 2021]
A.~A. Naghi and C.~P. Wirths.
\newblock Finite sample evaluation of causal machine learning methods:
Guidelines for the applied researcher.
\newblock Tinbergen Institute Discussion Paper TI 2021-090/III, 2021.

[Neyman, 1923]
\newblock Sur les applications de la th'eorie des probabilit'es aux experiences
agricoles: Essai des principes.
\newblock \emph{Roczniki Nauk Rolniczych}, 10, 01 1923.

[Nie and Wager, 2021]
X.~Nie and S.~Wager.
\newblock Quasi-oracle estimation of heterogeneous treatment effects.
\newblock \emph{Biometrika}, 108\penalty0 (2):\penalty0 299--319, 2021.

[Okasa, 2022]
\newblock {M}eta-{L}earners for estimation of causal effects: Finite sample
cross-fit performance.
\newblock \emph{arXiv preprint arXiv:2201.12692}, 2022.

[Patel et~al., 2017]
K.~K. Patel, S.~V. Arnold, P.~S. Chan, Y.~Tang, Y.~Pokharel, P.~G. Jones, and
J.~A. Spertus.
\newblock Personalizing the intensity of blood pressure control: modeling the
heterogeneity of risks and benefits from {SPRINT} ({S}ystolic {B}lood
{P}ressure {I}ntervention {T}rial).
\newblock \emph{Circulation: Cardiovascular Quality and Outcomes}, 10\penalty0
(4):\penalty0 e003624, 2017.

[Phillips et~al., 2018]
R.~A. Phillips, J.~Xu, L.~E. Peterson, R.~M. Arnold, J.~A. Diamond, and A.~E.
\newblock Impact of cardiovascular risk on the relative benefit and harm of
intensive treatment of hypertension.
\newblock \emph{Journal of the American College of Cardiology}, 71\penalty0
(15):\penalty0 1601--1610, 2018.

[Powers et~al., 2017]
S.~Powers, J.~Qian, K.~Jung, A.~Schuler, N.~Shah, T.~Hastie, and R.~Tibshirani.
\newblock Some methods for heterogeneous treatment effect estimation in
\newblock \emph{Statistics in Medicine}, 37, 07 2017.

[Robins et~al., 1994]
J.~Robins, A.~G. Rotnitzky, and L.~Zhao.
\newblock Estimation of regression coefficients when some regressors are not
always observed.
\newblock \emph{Journal of The American Statistical Association}, 89:\penalty0
846--866, 09 1994.

[Robins, 2004]
J.~M. Robins.
\newblock Optimal structural nested models for optimal sequential decisions.
\newblock In \emph{Proceedings of the second Seattle Symposium in
Biostatistics}, pages 189--326. Springer, 2004.

[Robinson, 1988]
\newblock Root-$n$-consistent semiparametric regression.
\newblock \emph{Econometrica}, 56:\penalty0 931--54, 02 1988.

[Rosenbaum and Rubin, 1983]
P.~Rosenbaum and D.~Rubin.
\newblock The central role of the propensity score in observational studies for
causal effects.
\newblock \emph{Biometrika}, 70:\penalty0 41--55, 04 1983.

[Rostomian et~al., 2020]
A.~H. Rostomian, M.~C. Tang, J.~Soverow, and D.~R. Sanchez.
\newblock Heterogeneity of treatment effect in sprint by age and baseline
comorbidities: The greatest impact of intensive blood pressure treatment is
observed among younger patients without {CKD} or {CVD} and in older patients
with {CKD} or {CVD}.
\newblock \emph{The Journal of Clinical Hypertension}, 22\penalty0
(9):\penalty0 1723--1726, 2020.

[Rubin, 1974]
D.~B. Rubin.
\newblock Estimating causal effects of treatments in randomized and
nonrandomized studies.
\newblock \emph{Journal of Educational Psychology}, 66\penalty0 (5):\penalty0
688, 1974.

[Saito et~al., 2019]
Y.~Saito, H.~Sakata, and K.~Nakata.
\newblock Doubly robust prediction and evaluation methods improve uplift
modeling for observational data.
\newblock In \emph{Proceedings of the 2019 SIAM International Conference on
Data Mining}, pages 468--476. SIAM, 2019.

[Scarpa et~al., 2019]
J.~Scarpa, E.~Bruzelius, P.~Doupe, M.~Le, J.~Faghmous, and A.~Baum.
\newblock Assessment of risk of harm associated with intensive blood pressure
management among patients with hypertension who smoke: a secondary analysis
of the systolic blood pressure intervention trial.
\newblock \emph{JAMA network open}, 2\penalty0 (3):\penalty0 e190005--e190005,

[Signorovitch, 2007]
\newblock \emph{Identifying Informative biological markers in high-dimensional
genomic data and clinical trials}.
\newblock PhD thesis, Harvard University, 2007.

[Simon et~al., 2011]
N.~Simon, J.~Friedman, T.~Hastie, and R.~Tibshirani.
\newblock Regularization paths for {C}ox’s proportional hazards model via
coordinate descent.
\newblock \emph{Journal of Statistical Software}, 39\penalty0 (5):\penalty0 1,

[Soran et~al., 2015]
H.~Soran, J.~D. Schofield, and P.~N. Durrington.
\newblock Cholesterol, not just cardiovascular risk, is important in deciding
who should receive statin treatment.
\newblock \emph{European Heart Journal}, 36\penalty0 (43):\penalty0 2975--2983,

[Tabib and Larocque, 2020]
S.~Tabib and D.~Larocque.
\newblock Non-parametric individual treatment effect estimation for survival
data with random forests.
\newblock \emph{Bioinformatics}, 36\penalty0 (2):\penalty0 629--636, 2020.

[Thanassoulis et~al., 2017]
G.~Thanassoulis, M.~J. Pencina, and A.~D. Sniderman.
\newblock The benefit model for prevention of cardiovascular disease: an
opportunity to harmonize guidelines.
\newblock \emph{JAMA cardiology}, 2\penalty0 (11):\penalty0 1175--1176, 2017.

[Tian et~al., 2014]
L.~Tian, A.~Alizadeh, A.~Gentles, and R.~Tibshirani.
\newblock A simple method for estimating interactions between a treatment and a
large number of covariates.
\newblock \emph{Journal of the American Statistical Association}, 109, 2014.

[Tian et~al., 2020]
L.~Tian, H.~Jin, H.~Uno, Y.~Lu, B.~Huang, K.~Anderson, and L.~Wei.
\newblock On the empirical choice of the time window for restricted mean
survival time.
\newblock \emph{Biometrics}, 76, 02 2020.

[Tibshirani et~al., 2022]
J.~Tibshirani, S.~Athey, E.~Sverdrup, and S.~Wager.
\newblock \emph{grf: {G}eneralized {R}andom {F}orests}, 2022.
\newblock URL \url{https://github.com/grf-labs/grf}.
\newblock R package version 2.1.0.

[Tibshirani, 1996]
\newblock Regression shrinkage and selection via the lasso.
\newblock \emph{Journal of the Royal Statistical Society. Series B
(Methodological)}, 58\penalty0 (1):\penalty0 267--288, 1996.

[Tibshirani, 1997]
\newblock The lasso method for variable selection in the {C}ox model.
\newblock \emph{Statistics in medicine}, 16\penalty0 (4):\penalty0 385--395,

[Tsiatis, 2006]
A.~A. Tsiatis.
\newblock Semiparametric theory and missing data.
\newblock 2006.

[Van~der Laan and Robins, 2003]
M.~J. Van~der Laan and J.~M. Robins.
\newblock \emph{Unified methods for censored longitudinal data and causality},
\newblock Springer, 2003.

[van Houwelingen and Putter, 2011]
H.~van Houwelingen and H.~Putter.
\newblock \emph{Dynamic prediction in clinical survival analysis}.
\newblock CRC Press, 2011.

[Van~Houwelingen et~al., 2006]
H.~C. Van~Houwelingen, T.~Bruinsma, A.~A. Hart, L.~J. Van't~Veer, and L.~F.
\newblock Cross-validated {C}ox regression on microarray gene expression data.
\newblock \emph{Statistics in Medicine}, 25\penalty0 (18):\penalty0 3201--3216,

[Wager and Athey, 2018]
S.~Wager and S.~Athey.
\newblock Estimation and inference of heterogeneous treatment effects using
random forests.
\newblock \emph{Journal of the American Statistical Association}, 113\penalty0
(523):\penalty0 1228--1242, 2018.

[Wang et~al., 2007]
R.~Wang, S.~Lagakos, J.~Ware, D.~Hunter, and J.~Drazen.
\newblock Statistics in medicine — reporting of subgroup analyses in clinical
\newblock \emph{The New England Journal of Medicine}, 357:\penalty0 2189--94,
12 2007.

[Wendling et~al., 2018]
T.~Wendling, K.~Jung, A.~Callahan, A.~Schuler, N.~Shah, and B.~Gallego.
\newblock Comparing methods for estimation of heterogeneous treatment effects
using observational data from health care databases.
\newblock \emph{Statistics in Medicine}, 37, 06 2018.

[Wright et~al., 2015]
J.~Wright, J.~Williamson, P.~Whelton, J.~Snyder, K.~Sink, M.~Rocco,
D.~Reboussin, M.~Rahman, S.~Oparil, C.~Lewis, P.~Kimmel, K.~Johnson, G.~Jr,
L.~Fine, J.~Cutler, W.~Cushman, A.~Cheung, W.~Ambrosius, M.~Sabati, and
\newblock A randomized trial of intensive versus standard blood-pressure
\newblock \emph{New England Journal of Medicine}, 373:\penalty0 2103--2116,

[Wu et~al., 2022]
Y.~Wu, J.~Bai, M.~Zhang, F.~Shao, H.~Yi, D.~You, and Y.~Zhao.
\newblock Heterogeneity of treatment effects for intensive blood pressure
therapy by individual components of {FRS}: An unsupervised data-driven
subgroup analysis in {SPRINT} and {ACCORD}.
\newblock \emph{Frontiers in cardiovascular medicine}, 9, 2022.

[Xu and Yadlowsky, 2022]
Y.~Xu and S.~Yadlowsky.
\newblock Calibration error for heterogeneous treatment effects.
\newblock In \emph{International Conference on Artificial Intelligence and
Statistics}, pages 9280--9303. PMLR, 2022.

[Xu et~al., 2022]
Y.~Xu, N.~Ignatiadis, E.~Sverdrup, S.~Fleming, S.~Wager, and N.~Shah.
\newblock \emph{survlearners: {M}etalearners for {S}urvival {D}ata}, 2022.
\newblock URL \url{https://github.com/som-shahlab/survlearners}.
\newblock R package version 0.0.1.

[Yadlowsky et~al., 2021]
S.~Yadlowsky, S.~Fleming, N.~Shah, E.~Brunskill, and S.~Wager.
\newblock Evaluating treatment prioritization rules via rank-weighted average
treatment effects.
\newblock \emph{arXiv preprint arXiv:2111.07966}, 2021.

[Yang and Steingrimsson, 2021]
J.~Yang and J.~Steingrimsson.
\newblock Causal interaction trees: Finding subgroups with heterogeneous
treatment effects in observational data.
\newblock \emph{Biometrics}, 2021.

[Zhang et~al., 2017]
W.~Zhang, T.~D. Le, L.~Liu, Z.-H. Zhou, and J.~Li.
\newblock Mining heterogeneous causal effects for personalized cancer
\newblock \emph{Bioinformatics}, 33\penalty0 (15):\penalty0 2372--2378, 2017.

[Zhang et~al., 2021]
W.~Zhang, J.~Li, and L.~Liu.
\newblock A unified survey of treatment effect heterogeneity modelling and
uplift modelling.
\newblock \emph{ACM Computing Surveys (CSUR)}, 54\penalty0 (8):\penalty0 1--36,

[Zhu and Gallego, 2020]
J.~Zhu and B.~Gallego.
\newblock Targeted estimation of heterogeneous treatment effect in
observational survival analysis.
\newblock \emph{Journal of Biomedical Informatics}, 107:\penalty0 103474, 2020.

[Zou and Hastie, 2005]
H.~Zou and T.~Hastie.
\newblock Regularization and variable selection via the elastic net.
\newblock \emph{Journal of the Royal Statistical Society: Series B (Statistical
Methodology)}, 67\penalty0 (2):\penalty0 301--320, 2005.

\end{thebibliography}

\end{document}