A Linear-Time Bottom-Up Discourse Parser
with Constraints and Post-Editing

The HILDA discourse parser by Hernault et al. (2010) is the first attempt at RST-style text-level discourse parsing. It adopts a pipeline framework, and greedily builds the discourse tree from the bottom up. In particular, starting from EDUs, at each step of the tree-building, a binary SVM classifier is first applied to determine which pair of adjacent discourse constituents should be merged to form a larger span, and another multi-class SVM classifier is then applied to assign the type of discourse relation that holds between the chosen pair.

The strength of HILDA’s greedy tree-building strategy is its efficiency in practice. Also, the employment of SVM classifiers allows the incorporation of rich features for better data representation [4]. However, HILDA’s approach also has obvious weakness: the greedy algorithm may lead to poor performance due to local optima, and more importantly, the SVM classifiers are not well-suited for solving structural problems due to the difficulty of taking context into account.

Joty et al. (2013) approach the problem of text-level discourse parsing using a model trained by Conditional Random Fields (CRF). Their model has two distinct features.

First, they decomposed the problem of text-level discourse parsing into two stages: intra-sentential parsing to produce a discourse tree for each sentence, followed by multi-sentential parsing to combine the sentence-level discourse trees and produce the text-level discourse tree. Specifically, they employed two separate models for intra- and multi-sentential parsing. Their choice of two-stage parsing is well motivated for two reasons: (1) it has been shown that sentence boundaries correlate very well with discourse boundaries, and (2) the scalability issue of their CRF-based models can be overcome by this decomposition.

Second, they jointly modeled the structure and the relation for a given pair of discourse units. For example, Figure 2 shows their intra-sentential model, in which they use the bottom layer to represent discourse units; the middle layer of binary nodes to predict the connection of adjacent discourse units; and the top layer of multi-class nodes to predict the type of the relation between two units. Their model assigns a probability to each possible constituent, and a CKY-like parsing algorithm finds the globally optimal discourse tree, given the computed probabilities.

The strength of Joty et al.’s model is their joint modeling of the structure and the relation, such that information from each aspect can interact with the other. However, their model has a major defect in its inefficiency, or even infeasibility, for application in practice. The inefficiency lies in both their DCRF-based joint model, on which inference is usually slow, and their CKY-like parsing algorithm, whose issue is more prominent. Due to the $O\left(n^3\right)$ time complexity, where $n$ is the number of input discourse units, for large documents, the parsing simply takes too long¹¹The largest document in the RST-DT contains over 180 sentences, i.e., $n>180$ for their multi-sentential CKY parsing. Intuitively, suppose the average time to compute the probability of each constituent is 0.01 second, then in total, the CKY-like parsing takes over 16 hours. It is possible to optimize Joty et al.’s CKY-like parsing by replacing their CRF-based computation for upper-level constituents with some local computation based on the probabilities of lower-level constituents. However, such optimization is beyond the scope of this paper..

Now we describe the local models we use to make decisions for a given pair of adjacent discourse constituents in the bottom-up tree-building. There are two dimensions for our local models: (1) scope of the model: intra- or multi-sentential, and (2) purpose of the model: for determining structures or relations. So we have four local models, $M_{intra}^{struct}$, $M_{intra}^{rel}$, $M_{multi}^{struct}$, and $M_{multi}^{rel}$.

While our bottom-up tree-building shares the greedy framework with HILDA, unlike HILDA, our local models are implemented using CRFs. In this way, we are able to take into account the sequential information from contextual discourse constituents, which cannot be naturally represented in HILDA with SVMs as local classifiers. Therefore, our model incorporates the strengths of both HILDA and Joty et al.’s model, i.e., the efficiency of a greedy parsing algorithm, and the ability to incorporate sequential information with CRFs.

As shown by Feng and Hirst (2012), for a pair of discourse constituents of interest, the sequential information from contextual constituents is crucial for determining structures. Therefore, it is well motivated to use Conditional Random Fields (CRFs) [10], which is a discriminative probabilistic graphical model, to make predictions for a sequence of constituents surrounding the pair of interest.

In this sense, our local models appear similar to Joty et al.’s non-greedy parsing models. However, the major distinction between our models and theirs is that we do not jointly model the structure and the relation; rather, we use two linear-chain CRFs to model the structure and the relation separately. Although joint modeling has shown to be effective in various NLP and computer vision applications [17, 19, 18], our choice of using two separate models is for the following reasons:

First, it is not entirely appropriate to model the structure and the relation at the same time. For example, with respect to Figure 2, it is unclear how the relation node $R_j$ is represented for a training instance whose structure node $S_j=0$, i.e., the units $U_{j-1}$ and $U_j$ are disjoint. Assume a special relation NO-REL is assigned for $R_j$. Then, in the tree-building process, we will have to deal with the situations where the joint model yields conflicting predictions: it is possible that the model predicts $S_j=1$ and $R_j=\mathrm{\text{NO-REL}}$, or vice versa, and we will have to decide which node to trust (and thus in some sense, the structure and the relation is no longer jointly modeled).

Secondly, as a joint model, it is mandatory to use a dynamic CRF, for which exact inference is usually intractable or slow. In contrast, for linear-chain CRFs, efficient algorithms and implementations for exact inference exist.

The local models, $P_{\left\{intra|multi\right\}}^{\left\{struct|rel\right\}}$, for post-editing is almost identical to their counterparts of the bottom-up tree-building, except that the linear-chain CRFs in post-editing includes additional features to represent information from constituents on higher levels (to be introduced in Section 7).

Suppose the input document is segmented into $n$ sentences, and each sentence $S_k$ contains $m_k$ EDUs. For each sentence $S_k$ with $m_k$ EDUs, the overall time complexity to perform intra-sentential parsing is $O\left(m_k^2\right)$. The reason is the following. On level $i$ of the bottom-up tree-building, we generate a single chain to represent the structure or relation for all the $m_k-i$ constituents that are currently in the sentence. The time complexity for performing forward-backward inference on the single chain is $O\left(\left(m_k-i\right)\times M^2\right)=O\left(m_k-i\right)$, where the constant $M$ is the size of the output vocabulary. Starting from the EDUs on the bottom level, we need to perform inference for one chain on each level during the bottom-up tree-building, and thus the total time complexity is ${\mathrm{\Sigma }}_{i=1}^{m_k}O\left(m_k-i\right)=O\left(m_k^2\right)$.

The total time to generate sentence-level discourse trees for $n$ sentences is ${\mathrm{\Sigma }}_{k=1}^{n}O\left(m_k^2\right)$. It is fairly safe to assume that each $m_k$ is a constant, in the sense that $m_k$ is independent of the total number of sentences in the document. Therefore, the total time complexity ${\mathrm{\Sigma }}_{k=1}^{n}O\left(m_k^2\right)\le n\times O\left({max}_{1\le j\le n}\left(m_j^2\right)\right)=n\times O\left(1\right)=O\left(n\right)$, i.e., linear in the total number of sentences.

For multi-sentential models, $M_{multi}^{struct}$ and $M_{multi}^{rel}$, as shown in Figures 6 and 9, for a pair of constituents of interest, we generate multiple chains to predict the structure or the relation.

By including a constant number $k$ of discourse units in each chain, and considering a constant number $l$ of such chains for computing each adjacent pair of discourse constituents ($k=4$ for $M_{multi}^{struct}$ and $k=3$ for $M_{multi}^{rel}$; $l=3$), we have an overall time complexity of $O\left(n\right)$. The reason is that it takes $l\times O\left(k{M}^2\right)=O\left(1\right)$ time, where $l,k,M$ are all constants, to perform exact inference for a given pair of adjacent constituents, and we need to perform such computation for all $n-1$ pairs of adjacent sentences on the first level of the tree-building. Adopting a greedy approach, on an arbitrary level during the tree-building, once we decide to merge a certain pair of constituents, say $U_j$ and $U_{j+1}$, we only need to recompute a small number of chains, i.e., the chains which originally include $U_j$ or $U_{j+1}$, and inference on each chain takes $O\left(1\right)$. Therefore, the total time complexity is $\left(n-1\right)\times O\left(1\right)+\left(n-1\right)\times O\left(1\right)=O\left(n\right)$, where the first term in the summation is the complexity of computing all chains on the bottom level, and the second term is the complexity of computing the constant number of chains on higher levels.

We have thus showed that the time complexity is linear in $n$, which is the number of sentences in the document. In fact, under the assumption that the number of EDUs in each sentence is independent of $n$, it can be shown that the time complexity is also linear in the total number of EDUs⁴⁴We implicitly made an assumption that the parsing time is dominated by the time to perform inference on CRF chains. However, for complex features, the time required for feature computation might be dominant. Nevertheless, a careful caching strategy can accelerate feature computation, since a large number of multi-sentential chains overlap with each other..

We compare four different models using manual EDU segmentation. In Table 1, the $j$CRF model in the first row is the optimal CRF model proposed by Joty et al. (2013). $g$SVM${}^{FH}$ in the second row is our implementation of HILDA’s greedy parsing algorithm using Feng and Hirst (2012)’s enhanced feature set. The third model, $g$CRF, represents our greedy CRF-based discourse parser, and the last row, $g$CRF${}^{PE}$, represents our parser with the post-editing component included.

In order to conduct a direct comparison with Joty et al.’s model, we use the same set of evaluation metrics, i.e., the unlabeled and labeled precision, recall, and F-score⁶⁶For manual segmentation, precision, recall, and F-score are the same. as defined by Marcu (2000). For evaluating relations, since there is a skewed distribution of different relation types in the corpus, we also include the macro-averaged F1-score (MAFS)⁷⁷MAFS is the F1-score averaged among all relation classes by equally weighting each class. Therefore, we cannot conduct significance test between different MAFS. as another metric, to emphasize the performance of infrequent relation types. We report the MAFS separately for the correctly retrieved constituents (i.e., the span boundary is correct) and all constituents in the reference tree.

As demonstrated by Table 1, our greedy CRF models perform significantly better than the other two models. Since we do not have the actual output of Joty et al.’s model, we are unable to conduct significance testing between our models and theirs. But in terms of overall accuracy, our $g$CRF model outperforms their model by 1.5%. Moreover, with post-editing enabled, $g$CRF${}^{PE}$ significantly () outperforms our initial model $g$CRF by another 1% in relation assignment, and this overall accuracy of 58.2% is close to 90% of human performance. With respect to the macro-averaged F1-scores, adding the post-editing component also obtains about 1% improvement.

However, the overall MAFS is still at the lower end of 30% for all constituents. Our error analysis shows that, for two relation classes, Topic-Change and Textual-Organization, our model fails to retrieve any instance, and for Topic-Comment and Evaluation, our model scores a class-wise $F_1$ score lower than 5%. These four relation classes, apart from their infrequency in the corpus, are more abstractly defined, and thus are particularly challenging.

We further illustrate the efficiency of our parser by demonstrating the time consumption of different models.

First, as shown in Table 2, the average number of sentences in a document is 26.11, which is already too large for optimal parsing models, e.g., the CKY-like parsing algorithm in $j$CRF, let alone the fact that the largest document contains several hundred of EDUs and sentences. Therefore, it should be seen that non-optimal models are required in most cases.

In Table 3, we report the parsing time⁸⁸Tested on a Linux system with four duo-core 3.0GHz processors and 16G memory. for the last three models, since we do not know the time of $j$CRF. Note that the parsing time excludes the time cost for any necessary pre-processing. As can be seen, our $g$CRF model is considerably faster than $g$SVM${}^{FH}$, because, on one hand, feature computation is expensive in $g$SVM${}^{FH}$, since $g$SVM${}^{FH}$ utilizes a rich set of features; on the other hand, in $g$CRF, we are able to accelerate decoding by multi-threading MALLET (we use four threads). Even for the largest document with 187 sentences, $g$CRF is able to produce the final tree after about 40 seconds, while $j$CRF would take over 16 hours assuming each DCRF decoding takes only 0.01 second. Although enabling post-editing doubles the time consumption, the overall time is still acceptable in practice, and the loss of efficiency can be compensated by the improvement in accuracy.