Transition-Based Syntactic Linearization with Lookahead Features

Proceedings of NAACL-HLT 2016, pages 488–493, San Diego, California, June 12-17, 2016. c⃝2016 Association for Computational Linguistics Transition-Based Syntactic Linearization with Lookahead Features Ratish Puduppully †∗, Yue Zhang ‡, Manish Shrivastava † †Kohli Center on Intelligent Systems (KCIS), International Institute of Information Technology, Hyderabad (IIIT Hyderabad) ‡Singapore University of Technology and Design ratish.surendran@research.iiit.ac.in yue zhang@sutd.edu.sg m.shrivastava@iiit.ac.in Abstract It has been shown that transition-based meth- ods can be used for syntactic word order- ing and tree linearization, achieving signifi- cantly faster speed compared with traditional best-first methods. State-of-the-art transition- based models give competitive results on ab- stract word ordering and unlabeled tree lin- earization, but significantly worse results on labeled tree linearization. We demonstrate that the main cause for the performance bottle- neck is the sparsity of SHIFT transition actions rather than heavy pruning. To address this is- sue, we propose a modification to the stan- dard transition-based feature structure, which reduces feature sparsity and allows lookahead features at a small cost to decoding efficiency. Our model gives the best reported accuracies on all benchmarks, yet still being over 30 times faster compared with best-first-search. 1 Introduction Word ordering is the abstract language modeling task of making a grammatical sentence by ordering a bag of words (White, 2004; Zhang and Clark, 2015; De Gispert et al., 2014; Bohnet et al., 2010; Filip- pova and Strube, 2007; He et al., 2009), which is practically relevant to text-to-text applications such as summarization (Wann et al., 2009) and machine translation (Blackwood et al., 2010). Zhang (2013) built a discriminative word ordering model, which takes a bag of words, together with optional POS and dependency arcs on a subset of input words, and ∗Part of the work was done when the author was a visiting student at Singapore University of Technology and Design. yields a sentence together with its dependency parse tree that conforms to input syntactic constraints. The system is flexible with respect to input constraints, performing abstract word ordering when no con- straints are given, but gives increasingly confined outputs when more POS and dependency relations are specified. It has been applied to syntactic lin- earization (Song et al., 2014) and machine transla- tion (Zhang et al., 2014). One limitation of Zhang (2013) is relatively low time efficiency, due to the use of time-constrained best-first-search (White and Rajkumar, 2009) for de- coding. In practice, the system can take seconds to order a bag of words in order to obtain reasonable output quality. Recently, Liu et al. (2015) proposed a transition-based model to address this issue, which uses a sequence of state transitions to build the out- put. The system of Liu et al. (2015) achieves signifi- cant speed improvements without sacrificing accura- cies when working with unlabeled dependency trees. With labeled dependency trees as input constraints, however, the system of Liu et al. (2015) gives much lower accuracies compared with Zhang (2013). While the low accuracy can be attributed to heavy pruning, we show that it can be mitigated by modi- fying the …

Content truncated to 500 words