Efficient Constituency Parsing by Pointing (2020)

Abstract: We propose a novel constituency parsing model that casts the parsing problem into a series of pointing tasks. Specifically, our model estimates the likelihood of a span being a legitimate tree constituent via the pointing score corresponding to the boundary words of the span. Our parsing model supports efficient top-down decoding and our learning objective is able to enforce structural consistency without resorting to the expensive CKY inference. The experiments on the standard English Penn Treebank parsing task show that our method achieves 92.78 F1 without using pre-trained models, which is higher than all the existing methods with similar time complexity. Using pre-trained BERT, our model achieves 95.48 F1, which is competitive with the state-of-the-art while being faster. Our approach also establishes new state-of-the-art in Basque and Swedish in the SPMRL shared tasks on multilingual constituency parsing.

## introduction constituency or phrase structure parsing is a core task in natural language processing (nlp) with myriad downstream applications. therefore, devising effective and efficient algorithms for parsing has been a key focus in nlp. with the advancements in neural approaches, various neural architectures have been proposed for constituency parsing as they are able to effectively encode the input tokens into dense vector representations while modeling the structural dependencies between tokens in a sentence. these include recurrent networks @xcite and more recently selfattentive networks @xcite . the parsing methods can be broadly distinguished based on whether they employ a greedy transition-based algorithm or a globally optimized span representation s(t ) = {((1, 5), s), ((2, 5), ∅), ((2, 4), vp), ((3, 4), s-vp)} pointing representation p(t ) = {(1 ) 5,s), (2 ) 5,∅), (3 ) 4,s-vp), (4 ) 2,vp), (5 ) 1,s)} figure 1 : a binarized constituency tree for the sentence "she enjoys playing tennis.". the node s-vp is an example of a collapsed atomic label. we omit pos tags and singleton spans for simplicity. below the tree, we show span and pointing representations of the tree. in this paper, we propose a novel parsing approach that casts constituency parsing into a series of pointing problems (figure 1 ). specifically, our parsing model estimates the pointing score from one word to another in the input sentence, which represents the likelihood of the span covering those words being a legitimate phrase structure (i.e., a subtree in the constituency tree). during training, the likelihoods of legitimate spans are maximized using the cross entropy loss. this enables our model to enforce structural consistency, while avoiding the use of structured loss that requires expensive o(n 3 ) cky inference @xcite . the training in our model can be fully parallelized without requiring structured inference as in @xcite . our pointing mechanism also allows efficient top-down decoding with a best and worse case running time of o(n log n) and o(n 2 ), respectively. in the experiments with english penn treebank parsing, our model without any pre-training achieves 92.78 f1, outperforming all existing methods with similar time complexity. with pre-trained bert @xcite , our model pushes the f1 score to 95.48, which is on par with the state-of-the-art @xcite , while supporting faster decoding. our model also performs competitively on the multilingual parsing tasks in the spmrl 2013/2014 shared tasks and establishes new state-of-the-art in basque and swedish. we will release our code at https://ntunlpsg.github.io/project/parser/ptrconstituency-parser 2 model similar to @xcite , we view constituency parsing as the problem of finding a set of labeled spans over the input sentence. let s(t ) denote the set of labeled spans for a parse tree t . formally, s(t ) can be expressed as although our method shares the same "spanbased" view with that of @xcite , our approach diverges significantly from their framework in the way we treat the whole parsing problem, and the representation and modeling of the spans, as we describe below. ## experiments to show the effectiveness of our approach, we conduct experiments on english and multilingual parsing tasks. for english, we use the standard wall street journal (wsj) part of the penn treebank (ptb) @xcite , whereas for multilingual, we experiment with seven (7) different languages from the spmrl 2013-2014 shared task @xcite : basque, french, german, hungarian, korean, polish and swedish. for evaluation on ptb, we report the standard labeled precision (lp), labeled recall (lr), and labelled f1 computed by evalb foot_0 . for the spmrl datasets, we report labeled f1 and use the same setup in evalb as @xcite . ## related work prior to the neural tsunami in nlp, parsing methods typically model correlations in the output space through probabilistic context-free grammars (pcfgs) on top of sparse (and discrete) input representations either in a generative regime @xcite or a discriminative regime @xcite or a combination of both @xcite . beside the chart parser approach, there is also a long tradition of transition-based parsers @xcite recently, however, with the advent of powerful neural encoders such as lstms @xcite , the focus has been switched more towards effective modeling of correlations in the input's latent space, as the output structures are nothing but a function of the input @xcite . various neural network models have been proposed to effectively encode the dense input representations and correlations, and have achieved state-of-the-art parsing results. to enforce the structural consistency, existing neural parsing methods either employ a transition-based algorithm @xcite @xcite or a globally optimized chart-parsing algorithm @xcite . meanwhile, researchers also attempt to convert the constituency parsing problem into tasks that can be solved in alternative ways. for instance, @xcite transform the phrase structure into a special form of dependency structure. such a dependency structure, however, requires certain corrections while converting back to the corresponding constituency tree. @xcite and @xcite propose to map the constituency tree for a sentence of n tokens into a sequence of n -1 labels or scalars based on the depth or height of the lowest common ancestors between pairs of consecutive tokens. in addition, methods like @xcite apply the sequence-to-sequence framework to "translate" a sentence into the linearized form of its constituency tree. while being trivial and simple, parsers of this type do not guarantee structural correctness, because the syntax of the linearized form is not constrained during tree decoding. our approach differs from previous work in that it represents the constituency structure as a series of pointing representations and has a relatively simpler cross entropy based learning objective. the pointing representations can be computed in parallel, and can be efficiently converted into a full constituency tree using a top-down algorithm. our pointing mechanism shares certain similarities with the pointer network @xcite , but is distinct from it in that our method points a word to another word within the same encoded sequence. ## conclusion we have presented a novel constituency parsing method that is based on a pointing mechanism. our method utilizes an efficient top-down decoding algorithm that uses pointing functions for scoring possible spans. the pointing formulation inherently captures global structural properties and allows efficient training with cross entropy loss. with experiments we have shown that our method outperforms all existing top-down methods on the english penn treebank parsing task. our method with pre-training rivals the state-ofthe-art method, while being faster than it. on multilingual constituency parsing, it also establishes new state-of-the-art in basque and swedish.