Advances in Discriminative Parsing

Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pages 873–880, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Advances in Discriminative Parsing Joseph Turian and I. Dan Melamed {lastname}@cs.nyu.edu Computer Science Department New York University New York, New York 10003 Abstract The present work advances the accu- racy and training speed of discrimina- tive parsing. Our discriminative parsing method has no generative component, yet surpasses a generative baseline on con- stituent parsing, and does so with mini- mal linguistic cleverness. Our model can incorporate arbitrary features of the in- put and parse state, and performs fea- ture selection incrementally over an ex- ponential feature space during training. We demonstrate the flexibility of our ap- proach by testing it with several pars- ing strategies and various feature sets. Our implementation is freely available at: http://nlp.cs.nyu.edu/parser/. 1 Introduction Discriminative machine learning methods have improved accuracy on many NLP tasks, including POS-tagging, shallow parsing, relation extraction, and machine translation. Some advances have also been made on full syntactic constituent parsing. Successful discriminative parsers have relied on generative models to reduce training time and raise accuracy above generative baselines (Collins & Roark, 2004; Henderson, 2004; Taskar et al., 2004). However, relying on information from a generative model might prevent these approaches from realizing the accuracy gains achieved by dis- criminative methods on other NLP tasks. Another problem is training speed: Discriminative parsers are notoriously slow to train. In the present work, we make progress towards overcoming these obstacles. We propose a flexi- ble, end-to-end discriminative method for training parsers, demonstrating techniques that might also be useful for other structured prediction problems. The proposed method does model selection with- out ad-hoc smoothing or frequency-based feature cutoffs. It requires no heuristics or human effort to optimize the single important hyper-parameter. The training regime can use all available informa- tion from the entire parse history. The learning al- gorithm projects the hand-provided features into a compound feature space and performs incremen- tal feature selection over this large feature space. The resulting parser achieves higher accuracy than a generative baseline, despite not using a genera- tive model as a feature. Section 2 describes the parsing algorithm. Sec- tion 3 presents the learning method. Section 4 presents experiments with discriminative parsers built using these methods. Section 5 compares our approach to related work. 2 Parsing Algorithm The following terms will help to explain our work. A span is a range over contiguous words in the in- put. Spans cross if they overlap but neither con- tains the other. An item is a (span, label) pair. A state is a partial parse, i.e. a set of items, none of whose spans may cross. A parse inference is a (state, item) pair, i.e. a state and an item to be added to it. The frontier of a state consists of the items with no parents yet. The children of a candi- date inference are the frontier items below the item to be inferred, …

Content truncated to 500 words