Data-Driven Parsing with Probabilistic Linear Context-Free Rewriting Systems

Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 537–545, Beijing, August 2010 Data-Driven Parsing with Probabilistic Linear Context-Free Rewriting Systems Laura Kallmeyer and Wolfgang Maier SFB 833, University of T¨ubingen {lk,wmaier}@sfs.uni-tuebingen.de Abstract This paper presents a first efficient imple- mentation of a weighted deductive CYK parser for Probabilistic Linear Context- Free Rewriting Systems (PLCFRS), to- gether with context-summary estimates for parse items used to speed up pars- ing. LCFRS, an extension of CFG, can de- scribe discontinuities both in constituency and dependency structures in a straight- forward way and is therefore a natural candidate to be used for data-driven pars- ing. We evaluate our parser with a gram- mar extracted from the German NeGra treebank. Our experiments show that data- driven LCFRS parsing is feasible with a reasonable speed and yields output of competitive quality. 1 Introduction Data-driven parsing has largely been dominated by Probabilistic Context-Free Grammar (PCFG). The use of PCFG is tied to the annotation princi- ples of popular treebanks, such as the Penn Tree- bank (PTB) (Marcus et al., 1994), which are used as a data source for grammar extraction. Their an- notation generally relies on the use of trees with- out crossing branches, augmented with a mech- anism that accounts for non-local dependencies. In the PTB, e.g., labeling conventions and trace nodes are used which establish additional implicit edges in the tree beyond the overt phrase struc- ture. In contrast, some other treebanks, such as the German NeGra and TIGER treebanks allow anno- tation with crossing branches (Skut et al., 1997). Non-local dependencies can then be expressed di- rectly by grouping all dependent elements under a single node. However, given the expressivity restrictions of PCFG, work on data-driven parsing has mostly excluded non-local dependencies. When us- ing treebanks with PTB-like annotation, label- ing conventions and trace nodes are often dis- carded, while in NeGra, resp. TIGER, tree trans- formations are applied which resolve the crossing branches (K¨ubler, 2005; Boyd, 2007, e.g.). Espe- cially for these treebanks, such a transformation is questionable, since it is non-reversible and implies information loss. Some research has gone into incorporating non- local information into data-driven parsing. Levy and Manning (2004) distinguish three approaches: 1. Non-local information can be incorporated di- rectly into the PCFG model (Collins, 1999), or can be reconstructed in a post-processing step af- ter PCFG parsing (Johnson, 2002; Levy and Man- ning, 2004). 2. Non-local information can be incorporated into complex labels (Hockenmaier, 2003). 3. A formalism can be used which accom- modates the direct encoding of non-local informa- tion (Plaehn, 2004). This paper pursues the third approach. Our work is motivated by the following re- cent developments: Linear Context-Free Rewrit- ing Systems (LCFRS) (Vijay-Shanker et al., 1987) have been established as a candidate for mod- eling both discontinuous constituents and non- projective dependency trees as they occur in tree- banks (Kuhlmann and Satta, 2009; Maier and Lichte, 2009). LCFRS extend CFG such that non-terminals can span tuples of possibly non- 537 CFG: A …

Content truncated to 500 words