A Conditional Splitting Framework for Efficient Constituency Parsing (2021)

Abstract: We introduce a generic seq2seq parsing framework that casts constituency parsing problems (syntactic and discourse parsing) into a series of conditional splitting decisions. Our parsing model estimates the conditional probability distribution of possible splitting points in a given text span and supports efficient top-down decoding, which is linear in number of nodes. The conditional splitting formulation together with efficient beam search inference facilitate structural consistency without relying on expensive structured inference. Crucially, for discourse analysis we show that in our formulation, discourse segmentation can be framed as a special case of parsing which allows us to perform discourse parsing without requiring segmentation as a pre-requisite. Experiments show that our model achieves good results on the standard syntactic parsing tasks under settings with/without pre-trained representations and rivals state-of-the-art (SoTA) methods that are more computationally expensive than ours. In discourse parsing, our method outperforms SoTA by a good margin.

## introduction a number of formalisms have been introduced to analyze natural language at different linguistic levels. this includes syntactic structures in the form of phrasal and dependency trees, semantic structures in the form of meaning representations @xcite , and discourse structures with rhetorical structure theory (rst) @xcite or discourse-ltag @xcite . many of these formalisms have a constituency structure, where textual units (e.g., phrases, sentences) are organized into nested constituents. for example, figure 1 shows examples of a phrase structure tree and a sentence-level discourse tree (rst) that respectively represent how the phrases and clauses are hierarchically or-ganized into a constituency structure. developing efficient and effective parsing solutions has always been a key focus in nlp. in this work, we consider both phrasal (syntactic) and discourse parsing. in recent years, neural end-to-end parsing methods have outperformed traditional methods that use grammar, lexicon and hand-crafted features. these methods can be broadly categorized based on whether they employ a greedy transition-based, a globally optimized chart parsing or a greedy topdown algorithm. transition-based parsers @xcite @xcite generate trees auto-regressively as a form of shift-reduce decisions. though computationally attractive, the local decisions made at each step may propagate errors to subsequent steps due to exposure bias @xcite . moreover, there may be mismatches in shift and reduce steps, resulting in invalid trees. chart based methods, on the other hand, train neural scoring functions to model the tree structure globally @xcite @xcite @xcite . by utilizing dynamic programming, these methods can perform exact inference to combine these constituent scores into finding the highest probable tree. however, they are generally slow with at least o(n 3 ) time complexity. greedy top-down parsers find the split points recursively and have received much attention lately due to their efficiency, which is usually o(n 2 ) @xcite @xcite . however, they still suffer from exposure bias, where one incorrect splitting step may affect subsequent steps. discourse parsing in rst requires an additional step -discourse segmentation which involves breaking the text into contiguous clause-like units called elementary discourse units or edus (figure 1 ). traditionally, segmentation has been considered separately and as a prerequisite step for the parsing task which links the edus (and larger spans) into a discourse tree @xcite @xcite . in this way, the errors in discourse segmentation can propagate to discourse parsing @xcite . in this paper, we propose a generic top-down neural framework for constituency parsing that we validate on both syntactic and sentence-level discourse parsing. our main contributions are: the beam-search inference along with the structural consistency from the modeling makes our approach competitive with existing structured chart methods for syntactic @xcite and discourse parsing @xcite . moreover, our parser does not rely on any handcrafted features (not even part-of-speech tags), which makes it more efficient and be flexible to different domains or languages. in the experiments with english penn treebank, our model without pre-trained representations achieves 93.8 f1, outperforming all existing methods with similar time complexity. with pre-training, our model pushes the f1 score to 95.7, which is on par with the sota while supporting faster decoding with a speed of over 1,100 sentences per second (fastest so far). our model also performs competitively with sota methods on the multilingual parsing tasks in the spmrl 2013/2014 shared tasks. in discourse parsing, our method establishes a new sota in end-to-end sentence-level parsing performance on the rst discourse treebank with an f1 score of 78.82. we make our code available at https://ntunlpsg.github.io/project/conditionconstituency-style-parser/ 2 parsing as a splitting problem constituency parsing (both syntactic and discourse) can be considered as the problem of finding a set of labeled spans over the input text @xcite . let s(t ) denote the set of labeled spans for a parse tree t , which can formally be expressed as (excluding the trivial singleton span layer): previous approaches to syntactic parsing @xcite @xcite train a neural model to score each possible span and then apply a greedy or dynamic programming algorithm to find the parse tree. in other words, these methods are span-based formulation. in contrary, we formulate constituency parsing as the problem of finding the splitting points in a recursive, top-down manner. for each parent node in a tree that spans over (i, j), our parsing model is trained to point to the boundary between the tokens at k and k + 1 positions to split the parent span into two child spans (i, k) and (k + 1, j). this is done through the pointing mechanism @xcite , where each splitting decision is modeled as a multinomial distribution over the input elements, which in our case are the token boundaries. the correspondence between token-and boundary-based representations of a tree is straightforward. after including the start (<@xmath0, the token-based span (i, j) is equivalent to the boundary-based span (i -1, j) labeled span representation s(t ) = {((1, 5), s), ((2, 5), ∅), ((2, 4), vp), ((3, 4), s-vp)} boundary-based splitting representation and the boundary between i-th and (i+1)-th tokens is indexed as i. for example, the (boundary-based) span "enjoys playing tennis" in figure 1 is defined as (1, 4). similarly, the boundary between the tokens "enjoys" and "playing" is indexed with 2. 1 following the common practice in syntactic parsing, we binarize the n-ary tree by introducing a dummy label ∅. we also collapsed the nested labeled spans in the unary chains into unique atomic labels, such as s-vp in figure 1 . every span represents an internal node in the tree, which has a left and a right child. therefore, we can represent each internal node by its split into left and right children. based on this, we define the set of splitting decisions c(t ) for a syntactic tree t as follows. proposition 1 a binary syntactic tree t of a sentence containing n tokens can be transformed into a set of splitting decisions c(t ) = {(i, j) ) k : @xmath1, j) is split into two child spans (i, k) and (k, j). an example of the splitting representation of a tree is shown in figure 1 (without the node labels). note that our transformed representation has a one-toone mapping with the tree since each splitting decision corresponds to one and only one internal node in the tree. we follow a depth-first order of the decision sequence, which in our preliminary experiments showed more consistent performance than other alternatives like breadth-first order. extension to end-to-end discourse parsing note that in syntactic parsing, the split position must be within the span but not at its edge, that is, k must satisfy @xmath2, j). otherwise, it will not produce valid sub-trees. in this case, we keep splitting until each span contains a single leaf token. however, for discourse trees, each leaf is an edu -a clause-like unit that can contain one or multiple tokens. unlike previous studies which assume discourse segmentation as a pre-processing step, we propose a unified formulation that treats segmentation as one additional step in the top-down parsing process. to accommodate this, we relax proposition 1 as: proposition 2 a binary discourse tree dt of a text containing n tokens can be transformed into a set of splitting decisions c(dt ) = {(i, j) ) k : @xmath3, j) gets split into two child spans (i, k) and (k, j) for @xmath4. we illustrate it with the dt example in figure 1 . each splitting decision in c(dt ) represents either the splitting of the parent span into two child spans (when the splitting point is strictly within the span) or the end of any further splitting (when the splitting point is the right endpoint of the span). by making this simple relaxation, our formulation can not only generate the discourse tree (in the former case) but can also find the discourse segments (edus) as a by-product (in the latter case). ## seq2seq parsing framework let c(t ) and l(t ) respectively denote the structure (in split representation) and labels of a tree t (syntactic or discourse) for a given text x. we can express the probability of the tree as: p θ (t |x) = p θ (l(t ), c(t )|x) = p θ (l(t )|c(t ), x)p θ (c(t )|x) (2) this factorization allows us to first infer the tree structure from the input text, and then find the corresponding labels. as discussed in the previous section, we consider the structure prediction as a sequence of splitting decisions to generate the tree in a top-down manner. specifically, at each decoding step t, the output y t represents the splitting decision (i t , j t ) ) k t and @xmath5. thus, we can express the probability of the tree structure as follows: this can effectively be modeled within a seq2seq pointing framework as shown in figure 2 . at each step t, the decoder autoregressively predicts the split point k t in the input by conditioning on the current input span (i t , j t ) and previous splitting decisions (i, j) ) k) <t . this conditional splitting formulation (decision at step t depends on previous steps) can help our model to find better trees compared to non-conditional top-down parsers @xcite @xcite , thus bridging the gap between the global (but expensive) and the local (but efficient) models. the labels l(t ) can be modeled by using a label classifier, as described later in the next section. ## experiment datasets and metrics to show the effectiveness of our approach, we conduct experiments on both syntactic and sentence-level rst parsing tasks. 2 we use the standard wall street journal (wsj) part of the penn treebank (ptb) @xcite for syntactic parsing and rst discourse treebank (rst-dt) @xcite for discourse parsing. for syntactic parsing, we also experiment with the multilingual parsing tasks on seven different languages from the spmrl 2013-2014 shared task @xcite : basque, french, german, hungarian, korean, polish and swedish. for evaluation on syntactic parsing, we report the standard labeled precision (lp), labeled recall (lr), and labelled f1 computed by evalb 3 . for evaluation on rst-dt, we report the standard span, nuclearity label, relation label f1 scores, computed using the implementation of (lin et al., 2019). 4 4.1 english (ptb) syntactic parsing setup we follow the standard train/valid/test split, which uses sections 2-21 for training, section 22 for development and section 23 for evaluation. this results in 39,832 sentences for training, 1,700 for development, and 2,416 for testing. for our model, we use an lstm encoder-decoder framework with a 3-layer bidirectional encoder and 3layer unidirectional decoder. the word embedding size is 100 while the character embedding size is 50; the lstm hidden size is 400. the hidden dimension in mlp modules and biaffine function for split point prediction is 500. the beam width b is set to 20. we use the adam optimizer (kingma and ba, 2015) with a batch size of 5000 tokens, and an initial learning rate of 0.002 which decays at the rate 0.75 exponentially at every 5k steps. model selection for final evaluation is performed based on the labeled f1 score on the development set. results without pre-training from the results shown in ## related work with the recent popularity of neural architectures, such as lstms @xcite and transformers @xcite , various neural models have been proposed to encode the input sentences and infer their constituency trees. to enforce structural consistency, such methods employ either a greedy transition-based @xcite , a globally optimized chart parsing @xcite , or a greedy top-down algorithm @xcite . meanwhile, researchers also tried to cast the parsing problem into tasks that can be solved differently. for example, @xcite ; @xcite proposed to map the syntactic tree of a sentence containing n tokens into a sequence of n -1 labels or scalars. however, parsers of this type suffer from the exposure bias during inference. beside these methods, seq2seq models have been used to generate a linearized form of the tree @xcite @xcite . however, these methods may generate invalid trees when the open and end brackets do not match. in discourse parsing, existing parsers receive the edus from a segmenter to build the discourse tree, which makes them susceptible to errors when the segmenter produces incorrect edus @xcite @xcite @xcite . there are also attempts which model constituency and discourse parsing jointly @xcite and do not need to perform edu preprocessing. it is based on the finding that each edu generally corresponds to a constituent in constituency tree, i.e., discourse structure usually aligns with constituency structure. however, it has the drawback that it needs to build joint syntactodiscourse data set for training which is not easily adaptable to new languages and domains. our approach differs from previous methods in that it represents the constituency structure as a series of splitting representations, and uses a seq2seq framework to model the splitting decision at each step. by enabling beam search, our model can find the best trees without the need to perform an expensive global search. we also unify discourse segmentation and parsing into one system by generalizing our model, which has been done for the first time to the best of our knowledge. our splitting mechanism shares some similarities with pointer network @xcite @xcite or head-selection approaches @xcite , but is distinct from them that in each decoding step, our method identifies the splitting point of a span and generates a new input for future steps instead of pointing to generate the next decoder input. ## conclusion we have presented a novel, generic parsing method for constituency parsing based on a seq2seq framework. our method supports an efficient top-down decoding algorithm that uses a pointing function for scoring possible splitting points. the pointing mechanism captures global structural properties of a tree and allows efficient training with a cross entropy loss. our formulation, when applied to discourse parsing, can bypass discourse segmentation as a pre-requisite step. through experiments we have shown that our method outperforms all existing top-down methods on english penn treebank and rst discourse treebank sentence-level parsing tasks. with pre-trained representations, our method rivals state-of-the-art methods, while being faster. our model also establishes a new state-ofthe-art for sentence-level rst parsing.