Bottom-Up Constituency Parsing and Nested Named Entity Recognition with Pointer Networks (2022)

Abstract: Constituency parsing and nested named entity recognition (NER) are similar tasks since they both aim to predict a collection of nested and non-crossing spans. In this work, we cast nested NER to constituency parsing and propose a novel pointing mechanism for bottom-up parsing to tackle both tasks. The key idea is based on the observation that if we traverse a constituency tree in post-order, i.e., visiting a parent after its children, then two consecutively visited spans would share a boundary. Our model tracks the shared boundaries and predicts the next boundary at each step by leveraging a pointer network. As a result, it needs only linear steps to parse and thus is efficient. It also maintains a parsing configuration for structural consistency, i.e., always outputting valid trees. Experimentally, our model achieves the state-of-the-art performance on PTB among all BERT-based models (96.01 F1 score) and competitive performance on CTB7 in constituency parsing; and it also achieves strong performance on three benchmark datasets of nested NER: ACE2004, ACE2005, and GENIA. Our code will be available at https://github.com/xxxxx .

## introduction constituency parsing is an important task in natural language processing, having many applications in downstream tasks, such as semantic role labeling @xcite , opinion mining @xcite , among others. named entity recognition (ner) is a fundamental task in information extraction and nested ner has been receiving increasing attention due to its broader applications @xcite . constituency parsing and nested ner are similar tasks since they both aim to predict a collection of nested and non-crossing spans (i.e., if two spans overlap, one must be a subspan of the other). fig. 1 mary acquired those three businesses in may 1988 . we show the span and pointing representations. in this work, we focus on constituency parsing, but our proposed method tackles nested ner as well. the two main paradigms in constituency pars-ing are span-based and transition-based methods. span-based methods @xcite @xcite decompose the score of a constituency tree into the scores of constituent spans and use chart-based algorithms for inference. built upon powerful neural encoders, they have obtained stateof-the-art results. however, they suffer from the high inference time complexity of exact algorithms or error propagation of top-down approximate algorithms. in contrast, transition-based methods @xcite @xcite , inter alia) conduct a series of local actions (e.g., shift and reduce) to build the final parse in linear steps, so they enjoy lower parsing time complexities. however, they suffer from the error propagation and exposure bias problems. recently, @xcite propose a sequence-to-sequence (seq2seq) model with pointer networks @xcite . they cast constituency parsing to a top-down splitting problem. first, they use neural encoders to obtain span representations, similar to span-based methods. then they feed input parent span representations into the neural decoder recursively following the order shown in fig. 2 (a) 2 -which amounts to pre-order traversal-to output a series of splitting points (i.e., boundaries) via pointer networks, so that each parent span is split into two child spans. notably, @xcite propose a similar top-down pointing mechanism, but they design a chart-based parsing algorithm instead of adopting seq2seq modeling, and has been shown underperforming @xcite . thanks to seq2seq modeling, @xcite 's model achieves a competitive parsing performance with a lower parsing complexity compared with span-based methods. however, their model has two main limitations. first, when generating each constituent, its subtree features cannot be exploited since its subspans have not been realized yet @xcite . thus it is difficult for the model to predict the splitting point of a long span due to a lack of its subtree information, which exacerbates the error propagation problem and undermines the parsing performance. second, since each parent span can only be split into two, their parsing algorithm can only ouput binary trees, thus needing binarization. we conduct experiments on the benchmarking ptb and ctb for constituency parsing. on ptb, we achieve the state-of-the-art performance (96.01 f1 score) among all bert-based models. on ctb, we achieve competitive performance. we also apply our method to nested ner and conduct experiments on three benchmark datasets: ace2004, ace2005, and genia. our method achieves comparable performance to many tailored methods of nested ner, beating previous parsing-based methods. our contributions can be summarized as the following: ## main result on both ptb and ctb, we find incorporating e y t-1 in eq. 1 leads to a slightly inferior performance (-0.02 f1 score on ptb and -0.05 f1 score on ctb), so we report results without this input feature. to verify this, we plot fig. 4 to show the changes of f1 scores with different constituent span lengths on the ptb test set. we can see that our method consistently outperforms the method of @xcite ) on all span lengths, but our advantage is most prominent for spans of @xmath0, which verifies our conjecture. in fig. 5 , we can see that when a constituent has multiple children (>3), our method performs much better than that of @xcite , which validates the benefit of n-ary tree parsing. an intuitive explanation of this benefit is that our method predicts n-ary branching structures in a single step, whereas theirs needs multiple steps, which is more error-prone. effect of beam search. we also tried beam search but observed very slight improvement or even worse performance (e.g., +0.05 f1 score on ptb and -0.03 f1 score on ctb when we use a beam size 20). hence we report all results using greedy decoding for simplicity. this suggests that greedy decoding can yield near-optimal solutions, indicating that our model is less prone to the error propagation problem. effect of training loss. as discussed in sec. 2.3, we find that explicitly considering the structural consistency constraints when normalizing is harmful (-0.12 f1 score on ptb, -0.10 f1 score on ctb). we speculate that not enforcing the constraints during training can help the model to learn the constraints implicitly, which is helpful for the model to generalize better on the unseen test set. notably, @xcite also adopt this strategy, i.e., normalizing over all boundaries. speed. similar to @xcite , the training process (i.e., teacher forcing) can be fully parallelized without resorting to structured inference, which could be compute-intensive or hard to parallelize. on ptb, it takes only 4.5 hours to train the model using bert as the encoder with a single titan v gpu. as for parsing, our method has the same parsing complexity as @xcite , i.e., worst-case o(n 2 ). ## related work constituency parsing. there are many methods to tackle constituency parsing, such as transitionbased methods @xcite @xcite , span-based methods @xcite @xcite @xcite @xcite , sequence-to-sequence (seq2seq)based methods @xcite , sequencelabeling-based methods @xcite @xcite , among others. our work belongs to the category of seq2seqbased methods. previous seq2seq models linearize constituency trees into bracket sequences @xcite or shift-reduce action sequences @xcite . however, they may produce invalid outputs and their performance lags behind span-based methods. recently, seq2seq models lin-earize constituency trees into sequences of spans in pre-order @xcite or in in-order @xcite . our method generates sequences of spans in post-order instead, which has the advantage of utilizing rich subtree features and performing direct n-ary tree parsing. binarization is de facto in constituency parsing, but there is a recent trend toward n-ary parsing. previous span-based methods adopt either explicit binarization @xcite or implicit binarization @xcite . although the implicit binarization strategy eliminates the need for binarization in training, it can only output binary trees during decoding. @xcite propose an n-ary-aware span-based method by defining semi-markov processes on each parent span so that the transition scores of adjacent sibling child-spans are explicitly considered in parsing. @xcite ; @xcite propose novel transition systems to model n-ary trees. our method outputs n-ary trees without the need for binarization via a novel pointing mechanism. parsing with pointer networks. pointer networks @xcite are introduced to the parsing literature by @xcite and quickly become popular in various parsing subtasks because they are flexible to predict various trees/graphs and can achieve very competitive performance. @xcite linearize a dependency tree in a top-down depth-first and inside-out manner and use a pointer network to predict the linearized dependency tree, which is then extended by @xcite to discourse parsing. @xcite add shortcuts between the decoder states of the previously generated parents/siblings to the current decoder states in both dependency and discourse parsing. @xcite propose a left-to-right dependency parser that predicts the heads of each word autoregressively, and later, they propose right-toleft and outside-in variants @xcite . they also adapt the left-to-right dependency parser to semantic dependency parsing (which predicts acyclic graphs instead of trees) @xcite , discontinuous constituency parsing (by treating discontinuous constituency trees as augmented dependency trees) @xcite , and joint dependency and constituency parsing @xcite . they use a pointer network to reorder the sentence to reduce discontinuous constituency parsing to continuous constituency parsing @xcite . @xcite cast (discourse) constituency/rst parsing as conditional splitting and use pointer networks to select the splitting points. @xcite propose an action-pointer network for amr parsing. nested ner. there are also many methods to tackle nested ner, such as hypergraph-based methods @xcite @xcite , sequence-labeling-based methods @xcite , parsing-based methods @xcite @xcite , layered methods @xcite @xcite , span-based methods @xcite , objectdetection-based methods @xcite etc. our work belongs to the category of parsingbased methods. @xcite insert named entities into a constituency tree and use a discriminative parser @xcite for learning and prediction. @xcite adapt a shift-reduce transition-based parser to output a constituency forest instead of a constituency tree for nested ner. @xcite adapt a span-based neural treecrf parser, treat nested named entities as the observed parts of a partially-observed constituency tree and develop a masked inside algorithm to marginalize all unobserved parts for maximizing the probability of the observed named entities. our method has a better performance as well as a lower time complexity than @xcite . recently, @xcite extend the work of @xcite , casting nested ner to lexicalized constituency parsing for leveraging headword information. they achieve a higher performance at the cost of a higher parsing complexity, i.e., o(n 4 ). ## discussion and future work in the deep learning era, global optimization on trees becomes less important in both training and decoding. teng and @xcite show that a span-based model trained with a local span classification loss performs well in conjunction with cyk decoding. @xcite ; @xcite show that top-down greedy decoding per-forms comparably. in this work we have shown that greedy decoding works well. thus it would also be a fruitful direction to design more powerful neural decoders which can leverage more subtree information and can maintain structural consistency. also, it is a fruitful direction to devise more powerful span representations. ## conclusion in this work we have presented a novel pointing mechanism and model for bottom-up constituency parsing, which allows n-ary tree parsing in linear steps. experiments on multiple datasets show the effectiveness of our methods in both constituency parsing and nested ner.