A Span-based Linearization for Constituent Trees (2020)

Abstract: We propose a novel linearization of a constituent tree, together with a new locally normalized model. For each split point in a sentence, our model computes the normalizer on all spans ending with that split point, and then predicts a tree span from them. Compared with global models, our model is fast and parallelizable. Different from previous local models, our linearization method is tied on the spans directly and considers more local features when performing span prediction, which is more interpretable and effective. Experiments on PTB (95.8 F1) and CTB (92.4 F1) show that our model significantly outperforms existing local models and efficiently achieves competitive results with global models.

## introduction constituent parsers map natural language sentences to hierarchically organized spans @xcite . according to the complexity of decoders, two types of parsers have been studied, globally normalized models which normalize probability of a constituent tree on the whole candidate tree space (e.g. chart parser @xcite ) and locally normalized models which normalize tree probability on smaller subtrees or spans. it is believed that global models have better parsing performance @xcite . but with the fast development of neural-network-based feature representations @xcite , local models are able to get competitive parsing accuracy while enjoying fast training and testing speed, and thus become an active research topic in constituent parsing. locally normalized parsers usually rely on tree decompositions or linearizations. from the perspective of decomposition, the probability of trees can be factorized, for example, on individual spans. @xcite investigates such a model which predicts probability on each candidate span. it achieves quite promising parsing results, while the simple local probability factorization still leaves room for improvements. from the perspective of linearization, there are many ways to transform a structured tree into a shallow sequence. as a recent example, @xcite linearizes a tree with a sequence of numbers, each of which indicates words' syntactic distance in the tree (i.e., height of the lowest common ancestor of two adjacent words). similar ideas are also applied in @xcite , @xcite and transition-based systems @xcite . with tree linearizations, the training time can be further accelerated to o(n), but the parsers often sacrifice a clear connection with original spans in trees, which makes both features and supervision signals from spans hard to use. in this work, we propose a novel linearization of constituent trees tied on their span representations. given a sentence w and its parsing tree t , for each split point after w i in the sentence, we assign it a parsing target d i , where (d i , i) is the longest span ending with i in t . we can show that, for a binary parsing tree, the set {(d i , i)} includes all left child spans in t . thus the linearization is actually sufficient to recover a parsing tree of the sentence. compared with prior work, the linearization is directly based on tree spans, which might make estimating model parameters easier. we also build a different local normalization compared with the simple per-span-normalization in @xcite . specifically, the probability p (d i |i) is normalized on all candidate split points on the left of i. the more powerful local model can help to further improve parsing performance while retaining the fast learning and inference speed (with a greedy heuristic for handling illegal sequences, we can achieve o(n log n) average inference complexity). s vp s np prp she vbz loves vbg writing nn code . . vp np (a) original parsing tree. s np prp she nn code . .   vp  s-vp  np vbz loves vbg writing (b) right binary tree. ## tree linearization we first prepare some notations. let @xmath0, w 2 , . . . , w n ) be a sentence, t be its binary constituent tree and a @xmath1. denote (i, j)(0 ≤ @xmath2, we ignore the label of a span). definition 1. given a sentence w and its tree t , we call @xmath3, d 2 , . . . , d n ) a linearization of t , where d @xmath4, 1, . . . , i -1} and (d i , i) is the longest span ending with i in t . clearly, there is only one such linearization for a tree. we have an equal definition of d, which shows the span (d i , i) is a left child span. proposition 1. given a tree t , the set of spans proof. first, for each j, there is only one left child span (i, j) ending with j, otherwise if (i , j) is a left child span with @xmath5.g. @xmath6, (i, j) must also be a right child span. therefore |s| = n. similarly, if @xmath7, (i, j) should be a right child span of (d j , j). thus we can generate the linearization using algorithm 1. for span (i, j) and its gold split k, we can get d @xmath8. then we recursively calculate the linearization of span (i, k) and (k, j). note that the returned linearization d does not contain d n , so we append zero (d @xmath9. figure 1 is a generation process of sentence "she loves writing code .". from the span table, it is obvious that there is only one left child span (green circles) ending with the same right boundary. in the following discussions, we will use d and s interchangeably. next, we show two properties of a legal d. proposition 2. a linearization d can recover a tree t iff. the root node is also regarded as a left child span. algorithm 1 tree linearization. proof. the necessity is obvious. we show the sufficiency by induction on the sentence length. when @xmath10, the conclusion stands. assuming for all linearizations with length less than n, property 1 and 2 lead to a well-formed tree, and now consider a linearization with length n. define @xmath11, @xmath12. since d 1 = 0 (by property 1), k is not none. we split the sentence into (0, k), (k, n), and claim that after removing (0, n), the spans in d are either in (0, k) or (k, n), thus by induction we obtain the conclusion. to validate the claim, for @xmath13, by property 1, we have d @xmath14, thus (d k , k ) is in (0, k). for @xmath15, by property 2, either d @xmath16. since k is the largest index with d @xmath17, we have therefore, we show the existence of a tree from d. the tree is also unique, because if two trees t and t have the same linearization, by proposition 1, we have @xmath18. proposition 2 also suggests a top-down algorithm (algorithm 2) for performing tree inference given a legal linearization. for span (i, j) (with label ℓ(i, j)), we find the rightmost split k satisfying d @xmath19, and then recursively decode the two subtrees rooted at span (i, k) and (k, j), respectively. when d does not satisfy property 2 (our model can ensure property 1), one solution is to seek a minimum change of d to make it legal. however, it is reduced to a minimum vertex cover problem (regarding each span (d i , i) as a point, if two spans violate property 2, we connect an edge between them. ). we can also slightly modify algorithm 2 to perform an approximate inference (section 3.4). algorithm 2 tree reconstruction. ## the parser in this section, we introduce our encoder, decoder and inference algorithms in detail. then we compare our normalization method with two other methods, globally normalized and existing locally normalized methods. ## related work globally normalized parsers often have high performance on constituent parsing due to their search on the global state space @xcite @xcite . however, they suffer from high time complexity and are difficult to parallelize. thus many efforts have been made to optimize their efficiency @xcite . recently, the rapid development of encoders @xcite and pre-trained language models @xcite have enabled local models to achieve similar performance as global models. @xcite propose two local models, one does normalization on each candidate span and one on each grammar rule. their models even outperform the global model in @xcite thanks to the better representation of spans. however, they still need an o(n 3 ) complexity inference algorithm to reconstruct the final parsing tree. meanwhile, many work do research on faster sequential models. transition-based models predict a sequence of actions and achieve an o(n) complexity @xcite @xcite . however, they suffer from the issue of error propagation and cannot be parallel. sequence labeling models regard tree prediction as sequence prediction problem @xcite . these models have high efficiency, but their linearizations have no direct relation to the spans, so the performance is much worse than span-based models. we propose a novel linearization method closely related to the spans and decode the tree in o(n log n) complexity. compared with @xcite , we do normalization on more spans, thus achieve a better performance. in future work, we will apply graph neural network @xcite @xcite to enhance the span representation. due to the excellent properties of our linearization, we can jointly learn constituent parsing and dependency parsing in one graph-based model. in addition, there is also a right linearization defined on the set of right child spans. we can study how to combine the two linear representations to further improve the performance of the model. ## conclusion in this work, we propose a novel linearization of constituent trees tied on the spans tightly. in addition, we build a new normalization method, which can add constraints on all the spans with the same right boundary. compared with previous local normalization methods, our method is more accurate for considering more span information, and reserves the fast running speed due to the parallelizable linearization model. the experiments show that our model significantly outperforms existing local models and achieves competitive results with global models.