In-Order Transition-based Constituent Parsing

In-Order Transition-based Constituent Parsing Jiangming Liu and Yue Zhang Singapore University of Technology and Design, 8 Somapah Road, Singapore, 487372 jmliunlp@gmail.com, yue zhang@sutd.edu.sg Abstract Both bottom-up and top-down strategies have been used for neural transition-based con- stituent parsing. The parsing strategies dif- fer in terms of the order in which they recog- nize productions in the derivation tree, where bottom-up strategies and top-down strategies take post-order and pre-order traversal over trees, respectively. Bottom-up parsers bene- fit from rich features from readily built par- tial parses, but lack lookahead guidance in the parsing process; top-down parsers benefit from non-local guidance for local decisions, but rely on a strong encoder over the input to predict a constituent hierarchy before its con- struction. To mitigate both issues, we pro- pose a novel parsing system based on in-order traversal over syntactic trees, designing a set of transition actions to find a compromise be- tween bottom-up constituent information and top-down lookahead information. Based on stack-LSTM, our psycholinguistically moti- vated constituent parsing system achieves 91.8 F1 on the WSJ benchmark. Furthermore, the system achieves 93.6 F1 with supervised reranking and 94.2 F1 with semi-supervised reranking, which are the best results on the WSJ benchmark. 1 Introduction Transition-based constituent parsing employs se- quences of local transition actions to construct con- stituent trees over sentences. There are two pop- ular transition-based constituent parsing systems, namely bottom-up parsing (Sagae and Lavie, 2005; Zhang and Clark, 2009; Zhu et al., 2013; Watanabe and Sumita, 2015) and top-down parsing (Dyer et al., 2016; Kuncoro et al., 2017). The parsing strate- gies differ in terms of the order in which they recog- nize productions in the derivation tree. The process of bottom-up parsing can be re- garded as post-order traversal over a constituent tree. For example, given the sentence in Figure 1, a bottom-up shift-reduce parser takes the ac- tion sequence in Table 2(a)1 to build the output, where the word sequence “The little boy” is first read, and then an NP recognized for the word sequence. After the system reads the verb “likes” and its subsequent NP, a VP is recognized. The full order of recognition for the tree nodes is 3⃝→ 4⃝→ 5⃝→ 2⃝→ 7⃝→ 9⃝→ 10 ⃝→ 8⃝→ 6⃝→ 11 ⃝→ 1⃝. When making local decisions, rich information is available from readily built partial trees (Zhu et al., 2013; Watanabe and Sumita, 2015; Cross and Huang, 2016), which contributes to local disambiguation. However, there is lack of top-down guidance from lookahead information, which can be useful (Johnson, 1998; Roark and Johnson, 1999; Charniak, 2000; Liu and Zhang, 2017). In addition, binarization must be applied to trees, as shown in Figure 1(b), to ensure a constant number of actions (Sagae and Lavie, 2005), and to take advantage of lexical head information (Collins, 2003). However, such binarization requires a set of language-specific rules, which hampers adaptation of parsing to other languages. On the other hand, the process of top-down parsing can be regarded as pre-order traversal over a tree. Given the …

Content truncated to 500 words