Efficient Structured Inference for Transition-Based Parsing with Neural Networks and Error States

Efficient Structured Inference for Transition-Based Parsing with Neural Networks and Error States Ashish Vaswani∗ USC Information Sciences Institute vaswani@usc.edu Kenji Sagae∗ USC Institute for Creative Technologies sagae@usc.edu Abstract Transition-based approaches based on local classification are attractive for dependency parsing due to their simplicity and speed, despite producing results slightly below the state-of-the-art. In this paper, we propose a new approach for approximate structured in- ference for transition-based parsing that pro- duces scores suitable for global scoring us- ing local models. This is accomplished with the introduction of error states in local train- ing, which add information about incorrect derivation paths typically left out completely in locally-trained models. Using neural net- works for our local classifiers, our approach achieves 93.61% accuracy for transition-based dependency parsing in English. 1 Introduction Transition-based parsing approaches based on local classification of parser actions (Nivre, 2008) remain attractive due to their simplicity, despite producing results slightly below the state-of-the-art. Although the application of online structured prediction and beam search has made transition-based parsing com- petitive in accuracy (Zhang and Clark, 2008; Huang et al., 2012) while retaining linear time complex- ity, greedy inference with locally-trained classifiers is still widely used, and techniques for improving the performance of greedy parsing have been pro- posed recently (Choi and Palmer, 2011; Goldberg and Nivre, 2012; Goldberg and Nivre, 2013; Hon- nibal et al., 2013). Recent work on the applica- tion of neural network classification to drive greedy transition-based dependency parsing has achieved high accuracy (Chen and Manning, 2014), showing ∗Both authors contributed equally to this paper. how effective locally-trained neural network mod- els are at predicting parser actions, while providing a straightforward way to improve parsing accuracy using word embeddings pre-trained using a large set of unlabeled data. We propose a novel approach for approximate structured inference for transition-based parsing that uses locally-trained neural networks that, unlike pre- vious local classification approaches, produce scores suitable for global scoring. This is accomplished with the introduction of error states in local training, which add information about incorrect derivation paths typically left out completely in locally-trained models. Our approach produces high accuracy for transition-based dependency parsing in English, sur- passing parsers based on the structured perceptron (Huang and Sagae, 2010; Zhang and Nivre, 2011) by allowing seamless integration of pre-trained word embeddings, while requiring nearly none of the fea- ture engineering typically associated with parsing with linear models. Trained without external re- sources or pre-trained embeddings, our neural net- work (NN) dependency parser outperforms the NN transition-based dependency parser from Chen and Manning (2014), which uses pre-trained word em- beddings trained on external data and more features, thanks to improved search. Our experiments show that naive search produces very limited improve- ments in accuracy compared to greedy inference, while search in conjunction with error states that mark incorrect derivations produces substantial ac- curacy improvements. 2 Background: Transition-Based Parsing Transition-based approaches are attractive in depen- dency parsing for their algorithmic simplicity and straightforward data-driven application. Using shift- 183 Transactions of the Association for …

Content truncated to 500 words