Efficient, Feature-based, Conditional Random Field Parsing

Proceedings of ACL-08: HLT, pages 959–967, Columbus, Ohio, USA, June 2008. c⃝2008 Association for Computational Linguistics Efficient, Feature-based, Conditional Random Field Parsing Jenny Rose Finkel, Alex Kleeman, Christopher D. Manning Department of Computer Science Stanford University Stanford, CA 94305 jrfinkel@cs.stanford.edu, akleeman@stanford.edu, manning@cs.stanford.edu Abstract Discriminative feature-based methods are widely used in natural language processing, but sentence parsing is still dominated by gen- erative methods. While prior feature-based dynamic programming parsers have restricted training and evaluation to artificially short sen- tences, we present the first general, feature- rich discriminative parser, based on a condi- tional random field model, which has been successfully scaled to the full WSJ parsing data. Our efficiency is primarily due to the use of stochastic optimization techniques, as well as parallelization and chart prefiltering. On WSJ15, we attain a state-of-the-art F-score of 90.9%, a 14% relative reduction in error over previous models, while being two orders of magnitude faster. On sentences of length 40, our system achieves an F-score of 89.0%, a 36% relative reduction in error over a gener- ative baseline. 1 Introduction Over the past decade, feature-based discriminative models have become the tool of choice for many natural language processing tasks. Although they take much longer to train than generative models, they typically produce higher performing systems, in large part due to the ability to incorporate ar- bitrary, potentially overlapping features. However, constituency parsing remains an area dominated by generative methods, due to the computational com- plexity of the problem. Previous work on discrim- inative parsing falls under one of three approaches. One approach does discriminative reranking of the n-best list of a generative parser, still usually de- pending highly on the generative parser score as a feature (Collins, 2000; Charniak and Johnson, 2005). A second group of papers does parsing by a sequence of independent, discriminative decisions, either greedily or with use of a small beam (Ratna- parkhi, 1997; Henderson, 2004). This paper extends the third thread of work, where joint inference via dynamic programming algorithms is used to train models and to attempt to find the globally best parse. Work in this context has mainly been limited to use of artificially short sentences due to exorbitant train- ing and inference times. One exception is the re- cent work of Petrov et al. (2007), who discrimina- tively train a grammar with latent variables and do not restrict themselves to short sentences. However their model, like the discriminative parser of John- son (2001), makes no use of features, and effectively ignores the largest advantage of discriminative train- ing. It has been shown on other NLP tasks that mod- eling improvements, such as the switch from gen- erative training to discriminative training, usually provide much smaller performance gains than the gains possible from good feature engineering. For example, in (Lafferty et al., 2001), when switching from a generatively trained hidden Markov model (HMM) to a discriminatively trained, linear chain, conditional random field (CRF) for part-of-speech tagging, their error drops from 5.7% to 5.6%. When they add in …

Content truncated to 500 words