Efficient Constituency Parsing by Pointing

Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 3284–3294 July 5 - 10, 2020. c⃝2020 Association for Computational Linguistics 3284 Efficient Constituency Parsing by Pointing Thanh-Tung Nguyen†¶, Xuan-Phi Nguyen†¶, Shafiq Joty¶§, Xiaoli Li† ¶Nanyang Technological University §Salesforce Research Asia †Institute for Infocomm Research, A-STAR Singapore {ng0155ng@e.;nguyenxu002@e.;srjoty@}ntu.edu.sg xlli@i2r.a-star.edu.sg Abstract We propose a novel constituency parsing model that casts the parsing problem into a se- ries of pointing tasks. Specifically, our model estimates the likelihood of a span being a le- gitimate 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 with- out 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 es- tablishes new state-of-the-art in Basque and Swedish in the SPMRL shared tasks on mul- tilingual constituency parsing. 1 Introduction Constituency or phrase structure parsing is a core task in natural language processing (NLP) with myriad downstream applications. Therefore, de- vising effective and efficient algorithms for pars- ing 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 effec- tively encode the input tokens into dense vector representations while modeling the structural de- pendencies between tokens in a sentence. These include recurrent networks (Dyer et al., 2016; Stern et al., 2017b) and more recently self- attentive networks (Kitaev and Klein, 2018). The parsing methods can be broadly distin- guished based on whether they employ a greedy transition-based algorithm or a globally optimized S She 1 ∅ VP enjoys 2 S-VP playing 3 tennis 4 . 5 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 ex- ample 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. chart parsing algorithm. The transition-based parsers (Dyer et al., 2016; Cross and Huang, 2016; Liu and Zhang, 2017) generate trees au- toregressively as a form of shift-reduce decisions. Though computationally attractive, the local deci- sions made at each step may propagate errors to subsequent steps which would suffer from expo- sure bias. Chart parsing methods, on the other hand, learn scoring functions for subtrees and perform global search over all possible trees to find the most prob- able tree for a sentence (Durrett and Klein, 2015; Gaddy et al., 2018; Kitaev and Klein, …

Content truncated to 500 words