Fast Full Parsing by Linear-Chain Conditional Random Fields

Proceedings of the 12th Conference of the European Chapter of the ACL, pages 790–798, Athens, Greece, 30 March – 3 April 2009. c⃝2009 Association for Computational Linguistics Fast Full Parsing by Linear-Chain Conditional Random Fields Yoshimasa Tsuruoka†‡ Jun’ichi Tsujii†‡∗ Sophia Ananiadou†‡ † School of Computer Science, University of Manchester, UK ‡ National Centre for Text Mining (NaCTeM), UK ∗ Department of Computer Science, University of Tokyo, Japan {yoshimasa.tsuruoka,j.tsujii,sophia.ananiadou}@manchester.ac.uk Abstract This paper presents a chunking-based dis- criminative approach to full parsing. We convert the task of full parsing into a series of chunking tasks and apply a conditional random field (CRF) model to each level of chunking. The probability of an en- tire parse tree is computed as the product of the probabilities of individual chunk- ing results. The parsing is performed in a bottom-up manner and the best derivation is efficiently obtained by using a depth- first search algorithm. Experimental re- sults demonstrate that this simple parsing framework produces a fast and reasonably accurate parser. 1 Introduction Full parsing analyzes the phrase structure of a sen- tence and provides useful input for many kinds of high-level natural language processing such as summarization (Knight and Marcu, 2000), pro- noun resolution (Yang et al., 2006), and infor- mation extraction (Miyao et al., 2008). One of the major obstacles that discourage the use of full parsing in large-scale natural language process- ing applications is its computational cost. For ex- ample, the MEDLINE corpus, a collection of ab- stracts of biomedical papers, consists of 70 million sentences and would require more than two years of processing time if the parser needs one second to process a sentence. Generative models based on lexicalized PCFGs enjoyed great success as the machine learning framework for full parsing (Collins, 1999; Char- niak, 2000), but recently discriminative models attract more attention due to their superior accu- racy (Charniak and Johnson, 2005; Huang, 2008) and adaptability to new grammars and languages (Buchholz and Marsi, 2006). A traditional approach to discriminative full parsing is to convert a full parsing task into a series of classification problems. Ratnaparkhi (1997) performs full parsing in a bottom-up and left-to- right manner and uses a maximum entropy clas- sifier to make decisions to construct individual phrases. Sagae and Lavie (2006) use the shift- reduce parsing framework and a maximum en- tropy model for local classification to decide pars- ing actions. These approaches are often called history-based approaches. A more recent approach to discriminative full parsing is to treat the task as a single structured prediction problem. Finkel et al. (2008) incor- porated rich local features into a tree CRF model and built a competitive parser. Huang (2008) pro- posed to use a parse forest to incorporate non-local features. They used a perceptron algorithm to op- timize the weights of the features and achieved state-of-the-art accuracy. Petrov and Klein (2008) introduced latent variables in tree CRFs and pro- posed a caching mechanism to speed up the com- putation. In general, the latter whole-sentence ap- proaches give …

Content truncated to 500 words