N-ary Constituent Tree Parsing with Recursive Semi- M arkov Model (2021)

Abstract: In this paper, we study the task of graph-based constituent parsing in the setting that binarization is not conducted as a pre-processing step, where a constituent tree may consist of nodes with more than two children. Previous graph-based methods on this setting typically generate hidden nodes with the dummy label inside the n-ary nodes, in order to transform the tree into a binary tree for prediction. The limitation is that the hidden nodes break the sibling relations of the n-ary node’s children. Consequently, the dependencies of such sibling constituents might not be accurately modeled and is being ignored. To solve this limitation, we propose a novel graph-based framework, which is called “recursive semi-Markov model”. The main idea is to utilize 1-order semi-Markov model to predict the immediate children sequence of a constituent candidate, which then recursively serves as a child candidate of its parent. In this manner, the dependencies of sibling constituents can be described by 1-order transition features, which solves the above limitation. Through experiments, the proposed framework obtains the F1 of 95.92% and 92.50% on the datasets of PTB and CTB 5.1 respectively. Specially, the recursive semi-Markov model shows advantages in modeling nodes with more than two children, whose average F1 can be improved by 0.3-1.1 points in PTB and 2.3-6.8 points in CTB 5.1.

## introduction there are two settings for constituent parsing models, including binary tree parsing and n-ary tree parsing. in the former, the original constituent tree with n-ary nodes is converted into a binary tree by language-specific rules. the model first predicts the binary tree, and then converts it back. in the latter, the model directly predicts the n-ary tree without the intermediate step of binarization. specifically, we target at improving graph-based models for n-ary tree parsing, which obtain better performances in recent work @xcite @xcite ) from the two streams of well-developed parsing methods, graphbased and transition-based. for n-ary tree parsing, the main idea of previous graph-based models is to generate hidden nodes with the dummy label φ inside the n-ary node, in order to expand the n-ary tree into a binary tree. in this way, n-ary tree parsing can be converted into binary tree parsing with hidden nodes, which are unobservable in the training process. consider the n-ary node "@xmath0, figure 2 : comparisons of previous and our models. (i, j) denotes the span from i to j -1. ρ(i, j) denotes the feature score of span (i, j); ψ(i, j, k) denotes the feature score of the sibling span pair (i, j) and (j, k). np, qp" in fig. 1 (a) as an example. the hidden nodes can be in two manners, as shown in fig. 1 (b , c ). either of them can be seen as being correct in training. for convenience, the potential scores of such hidden nodes are manually set to zero, to ensure that the two manners are equivalent when calculating the likelihood @xcite . the limitation of previous methods is that the generated hidden nodes break the sibling relations of the n-ary node's children. consequently, such sibling dependency feature might not be accurately modeled and is being ignored. consider the node "@xmath1, np, qp" in the above example. if we model the 1-order dependency from the sibling node pair, dependency feature scores should be calculated from both pairs of (vv, np) and (np, qp). without loss of generality, suppose the hidden node is as shown in fig. 1 (b) , and the case in fig. 1 (c ) is similar. as the hidden node φ is forced to be the sibling node of "qp", the dependency feature of (np, qp) cannot be directly calculated. in implementation, only potential scores of each node are modeled, and the dependency potential scores of sibling node pairs are being ignored. to solve this limitation, we propose a novel framework for n-ary tree parsing. our main idea is to utilize 1-order semi-markov model to directly predict the immediate children sequence of an n-ary node, without generating the hidden nodes for binarization, as shown in fig. 2 . different from previous models that only have potential scores on nodes when evaluating a tree's likelihood, the potential scores of sibling node pairs are also calculated as 1-order transition features. thus dependencies from sibling nodes can be naturally modeled, which solves the above limitation. when generating an n-ary tree, the semi-markov model is recursively conducted on the node spans in a bottom-up manner, thus we call the proposed model "recursive semi-markov model". the main challenge of designing the recursive semi-markov model is how to make the computational complexity being acceptable. in nowadays gpu era, to make full use of parallel computation is an important issue to enhance the processing speed. for example, in the previous cyk @xcite algorithm for binary trees, the absolute time complexity is o(n 3 ), where n is the sentence length. but o(n 2 ) out of it can be computed in parallel, by batchifying the spans with the same length and the divisions within a span. this means the hard time complexity of cyk, which cannot be computed in parallel, is o(n). in the case of the proposed recursive semi-markov model, the time complexity of the straight-forward dynamic programming algorithm is o(n 5 ). but by careful design, we propose an algorithm, whose complexity is o(n 4 ), with o(n 3 ) out of it can be batchified. it means the increased o(n) complexity compared with cyk can be calculated in parallel. in practice, the proposed framework can process 26 and 11 sentences per second in ptb and ctb 5.1 test sets respectively, by a single nvidia rtx gpu. our main contributions can be summarized as follows. (1) we propose a novel graph-based framework, recursive semi-markov model, for n-ary constituent tree parsing, which can model the dependencies of sibling nodes. (2) we design a dynamic programming algorithm for the proposed framework, whose complexity is o(n 4 ), with o(n 3 ) inside can be batchified. (3) experimental verifications demonstrate that the proposed framework outperforms previous methods. the f1 of the proposed framework is 95.92% and 92.50% in ptb and ctb 5.1 respectively. in the joint task with segmentation and pos tagging in ctb 5.1, the f1 is 91.84%. in addition, the proposed framework can effectively predict nodes with more than two children, improving the f1 by 0.3-1.1 points in ptb and 2.3-6.8 points in ctb 5.1. our code is released at https://github.com/npnet-research/recursive-semi-markov-model, which is developed on the base of the open-source berkekey parser @xcite . ## conclusion in this paper, a recursive semi-markov model is proposed for n-ary constituent tree parsing, with the advantage of modeling the sibling relations within n-ary node. experimental verifications on ptb and ctb 5.1 demonstrate that the proposed framework outperforms previous work in the single parsing task of both datasets and the joint task in ctb 5.1. for constituent nodes with more than 2 children, the f1 can be improved by 0.3 -1.1 points in ptb and 2.3 -6.8 points in ctb 5.1.