RST Parsing from Scratch

In this work, we adopt a structure-then-label framework. Specifically, we factorize the probability of a DT into the probability of the tree structure and the probability of the relations (i.e., the node labels) as follows:

As discussed, we consider the structure prediction problem as a sequence of splitting decisions to generate the tree in a top-down manner. We use a seq2seq pointer network (Vinyals et al., 2015) to model the sequence of splitting decisions (Fig. 3). We adopt a depth-first order of the decision sequence, which showed more consistent performance in our preliminary experiments than other alternatives, such as breath-first order.

First, we encode the tokens in a document ${\bm{x}}=(x_{0},\ldots,x_{n}$) with a document encoder and get the token-boundary representations (${\bm{h}}_{0},\ldots,{\bm{h}}_{n}$). Then, at each decoding step $t$, the model takes as input an internal node $(i_{t},j_{t})$, and produces an output $y_{t}$ (by pointing to the token boundaries) that represents the splitting decision $(i_{t},j_{t})\!\mathrel{\vbox{\hbox{\rule[0.0pt]{4.0pt}{0.0pt}}}\mkern-4.0mu\hbox{\char 41\relax}}\!k_{t}$ to split it into two child constituents $(i_{t},k_{t})$ and $(k_{t},j_{t})$. For example, the initial span $(0,44)$ in Fig. 1 is split at boundary position $4$, yielding two child spans $(0,4)$ and $(4,44)$. If the span $(0,4)$ is given as an EDU (i.e.,  segmentation given), the splitting stops at $(0,4)$, thus omitted in ${\mathbb{S}}_{\text{edu}}$ (Fig. 1). Otherwise, an extra decision $(0,4)\!\mathrel{\vbox{\hbox{\rule[0.0pt]{4.0pt}{0.0pt}}}\mkern-4.0mu\hbox{\char 41\relax}}\!4\in{\mathbb{S}}$ needs to be made to mark the EDUs for end-to-end parsing. With this, the probability of ${\mathbb{S}}$ can be expressed as:

Given an input document of $n$ words ${\bm{x}}=(x_{1},\ldots,x_{n})$, we first add $<$sod$>$ and $<$eod$>$ markers to the sequence. After that, each token $x_{i}$ in the sequence is mapped into its dense vector representation ${\bm{e}}_{i}$ as: ${\bm{e}}_{i}=[{\bm{e}}_{i}^{\text{char}},{\bm{e}}_{i}^{\text{word}}]$, where ${\bm{e}}_{i}^{\text{char}}$, and ${\bm{e}}_{i}^{\text{word}}$ are respectively the character and word embeddings of token $x_{i}$. For word embedding, we experiment with (i) randomly initialized, (ii) pretrained static embeddings ,e.g., GloVe (Pennington et al., 2014)). To represent the character embedding of a token, we apply a character bidirectional LSTM i.e., Bi-LSTM (Hochreiter and Schmidhuber, 1997) or pretrained contextualized embeddings, e.g., XLNet (Yang et al., 2019). The token representations are then passed to a sequence encoder of a three-layer Bi-LSTM to obtain their forward ${\bm{f}}_{i}$ and backward ${\bm{b}}_{i}$ contextual representations.

To represent each token-boundary position $k$ between token positions $k$ and $k+1$, we use the fencepost representation (Cross and Huang, 2016):

where ${\bm{f}}_{k}$ and ${\bm{b}}_{k+1}$ are the forward and backward LSTM hidden vectors of positions $k$ and $k+1$ respectively, and $[\cdot;\cdot]$ is the concatenation operation.

Then, to represent the token-boundary span $(i,j)$, we use the linear combination of the two endpoints $i$ and $j$ as:

where ${\bm{W}}_{1}$ and ${\bm{W}}_{2}$ are trainable weights. These span representations will be used as input to the decoder or the label classifier. Fig. 4 illustrates an example boundary span representation.

Our model uses a unidirectional LSTM as the decoder. At each decoding step $t$, the decoder takes as input the corresponding span $(i,j)$ (i.e., ${\bm{h}}_{i,j}$) and its previous LSTM state ${\bm{d}}_{t-1}$ to generate the current state ${\bm{d}}_{t}$ and then the biaffine function (Dozat and Manning, 2017) is applied between ${\bm{d}}_{t}$ and all the encoded token-boundary representations $({\bm{h}}_{0},{\bm{h}}_{1},\ldots,{\bm{h}}_{n})$ as follows:

We perform label assignment after decoding the entire tree structure. Each assignment takes into account the splitting decision that generated it since the label represents the relation between the child spans. Specifically, for a constituent $(i,j)$ that was split into two child constituents $(i,k)$ and $(k,j)$, we determine the coherence relation between them as follows:

Our parsing model is trained by minimizing the total loss defined as:

where structure $\mathcal{L}_{s}$ and label $\mathcal{L}_{l}$ losses are cross-entropy losses computed for the splitting and labeling tasks respectively, and $\theta_{e}$, $\theta_{d}$ and $\theta_{l}$ denote the encoder, decoder and labeling parameters.

As mentioned, previous work for end-to-end parsing assumes a separate segmenter that provides EDU-segmented texts to the parser. Our method, however, is an end-to-end framework that produces both the EDUs as well as the parse tree in the same inference process. To guide the search better, we incorporate an inductive bias into our inference based on the finding that most sentences have a well-formed subtree in the document-level tree (Soricut and Marcu, 2003), i.e., discourse structure tends to align with the text structure (sentence boundary in this case); for example, Fisher and Roark (2007); Joty et al. (2013) found that more than $95\%$ of the sentences have a well-formed subtree in the RST discourse treebank.

Our goal is to ensure that each sentence corresponds to an internal node in the tree. This can be achieved by a simple adjustment in our inference. When decoding at time step $t$ with the span $(i_{t},j_{t})$ as input, if the span contains $M>0$ sentence boundaries within it, we pick the one that has the highest pointing score (Eq. 7) among the $M$ alternatives as the split point $k_{t}$. If there is no sentence boundary within the input span ($M=0$), we find the next split point as usual. In other words, sentence boundaries in a document get the chance to be split before the token boundaries inside a sentence. This constraint is indeed similar to the 1S-1S (1 subtree for 1 sentence) constraint of Joty et al. (2013)’s bottom-up parsing, and is also consistent with the property that EDUs are always within the sentence boundary. Algorithm 1 illustrate the end-to-end inference algorithm.

When segmentation information is provided, we can have a better encoding of the EDUs to construct the tree. Specifically, rather than simply taking the token-boundary representation corresponding to the EDU boundary as the EDU representation, we adopt a hierarchical approach, where we add another Bi-LSTM layer (called “Boundary LSTM”) that connects EDU boundaries (a figure of this framework is in the Appendix). In other words, the input sequence to this LSTM layer is $(\overline{{\bm{h}}}_{0},\ldots,\overline{{\bm{h}}}_{m})$, where $\overline{{\bm{h}}}_{0}={\bm{h}}_{0}$, $\overline{{\bm{h}}}_{m}={\bm{h}}_{n}$ and $\overline{{\bm{h}}}_{j}\in\{{\bm{h}}_{1},\ldots,{\bm{h}}_{n-1}\}$ such that $\overline{{\bm{h}}}_{j}$ is an EDU boundary. For instance, for the example in Fig. 1, the input to the Boundary LSTM layer is $({\bm{h}}_{0},{\bm{h}}_{4},{\bm{h}}_{17},{\bm{h}}_{25},{\bm{h}}_{33},{\bm{h}}_{37},{\bm{h}}_{44})$.

This hierarchical representation facilitates better modeling of relations between EDUs and higher order spans, and can capture long-range dependencies better, especially for long documents.

Previous work (Lin et al., 2019; Zhang et al., 2020) which also uses a seq2seq architecture, computes the pointing scores over the token or span representations only within the input span. For example, for an input span $(i,j)$, the pointing scores are computed considering only $({\bm{h}}_{i},\ldots,{\bm{h}}_{j})$ as opposed to $({\bm{h}}_{1},\ldots,{\bm{h}}_{n})$ in our Eq. 7. This makes the scales of the scores uneven across different input spans as the lengths of the spans vary. Thus, such scores cannot be objectively compared across sub-trees globally at the full-tree level. In addition, since efficient global search methods like beam search cannot be applied properly with non-uniform scores, these previous methods had to remain greedy at each decoding step. In contrast, our decoder points to all the encoded token-boundary representations in every step (Eq. 7). This ensures that the pointing scores are evenly scaled, allowing fair comparisons between the scores of all candidate sub-trees. Therefore, our method enables the effective use of beam search through highly probable candidate trees. Algorithm 2 illustrates the beam search inference when EDUs are given.

Discourse parsing with gold EDUs has been the standard practice in many previous studies. We compare our model with ten different baselines as shown in Table 1. We report most results from Morey et al. (2018); Zhang et al. (2020); Kobayashi et al. (2020), while we reproduce Yu et al. (2018) using their provided source code.

For our model setup, we use the encoder-decoder framework with a 3-layer Bi-LSTM encoder and 3-layer unidirectional LSTM decoder. The LSTM hidden size is 400, the word embedding size is 100 for random initialization, while the character embedding size is 50. The hidden dimension in MLP modules and biaffine function for structure prediction is 500. The beam width $B$ is 20. Our model is trained by Adam optimizer (Kingma and Ba, 2015) with a batch size of 10000 tokens. Our learning rate is initialized at $0.002$ and scheduled to decay at an exponential rate of $0.75$ for every 5000 steps. Model selection for testing is performed based on the Full F1 score on the development set. When using pretrained word embeddings, we use the 100D vectors from GloVe (Pennington et al., 2014). For pretrained model, we use the XLNet-base-cased version (Yang et al., 2019).¹¹1Our initial attempt with BERT did not offer significant gain as BERT is not explicitly designed to process long documents and has a limit of maximum $512$ tokens. The pretrained models/embeddings are kept frozen during training.

From the results in Table 1, we see that our model with GloVe (static) embeddings achieves a Full F1 score of 46.8, the highest among all the parsers that do not use pretrained models (or contextual embeddings). This suggests that a BiLSTM-based parser can be competitive with effective modeling. The model also outperforms the one proposed by Zhang et al. (2020), which is closest to ours in terms of modelling, by 3.9%, 4.1%, 2.4% and 2.5% absolute in Span, Nuclearity, Relation and Full, respectively. More importantly, our system achieves such results without relying on external data or features, in contrast to previous approaches. In addition, by using XLNet-base pretrained model, our system surpasses all existing methods (with or without pretraining) in all four metrics, achieving the state of the art with 2.9%, 4.0%, 2.4% and 2.1% absolute improvements. It also reduces the gap between system performance and human agreement. When evaluated with the RST-Parseval (Marcu, 2000) metric, our model outperforms the baselines by 0.6%, 1.4% and 1.8% in Span, Nuclearity and Relation, respectively.

Our end-to-end parsing method gets an F1 score of 96.30 for the resulting EDUs. Our result rivals existing SoTA segmentation methods – 92.20 F1 of Li et al. (2018) and 95.55 F1 of Lin et al. (2019). This shows the efficacy of our unified framework for not only discourse parsing but also segmentation.²²2We could not compare our segmentation results with the DISRPT 2019 Shared Task Zeldes et al. (2019) participants. We found few inconsistencies in the settings. First, in their “gold sentence” dataset, instead of using the gold sentence, they pre-process the text with an automatic tokenizer and sentence segmenter. Second, in the evaluation, under the same settings, they do not exclude the trivial BeginSegment label at the beginning of each sentence which we exclude in evaluating our segmentation result (following the RST standard).

Table 3 shows two ablations for parsing with gold EDUs. We see that both beam search and boundary LSTM (hierarchical encoding as shown in Fig. 7) are important to the model. The former can find better tree structure by searching a larger searching space. The latter, meanwhile, connects the EDU-boundary representations, which enhances the model’s ability to capture long-range dependencies between EDUs.

For end-to-end parsing, Table 4 shows that the sentence boundary constraint (Section 2.3) is indeed quite important to guide the model as it decodes long texts. Since sentence segmentation models are quite accurate, they can be employed if ground truth sentence segmentation is not available. We also notice that pretraining (GloVe) leads to improved performance.

We show our best parser’s (with gold EDUs) confusion matrix for the 10 most frequent relation labels in Fig. 5. The complete matrix with the 18 relations is shown in Appendix (Fig. 8). The imbalanced relation distribution in RST-DT affects our model’s performance to some extent. Also semantic similar relations tend to be confused with each other. Fig. 6 shows an example where our model mistakenly labels Summary as Elaboration. However, one could argue that the relation Elaboration is also valid here because the parenthesized text brings additional information (the equivalent amount of money). We show more error examples in the Appendix (Fig. 9 - 11), where our parser labels a Condition as Background, Temporal as Joint and Explanation as Elaboration. As we can see, all these relations are semantically close and arguably interchangeable.