Positive Results for Parsing with a Bounded Stack using a Model-Based Right-Corner Transform

Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the ACL, pages 344–352, Boulder, Colorado, June 2009. c⃝2009 Association for Computational Linguistics Positive Results for Parsing with a Bounded Stack using a Model-Based Right-Corner Transform William Schuler Dept. of Computer Science and Engineering Minneapolis, MN schuler@cs.umn.edu Abstract Statistical parsing models have recently been proposed that employ a bounded stack in time- series (left-to-right) recognition, using a right- corner transform defined over training trees to minimize stack use (Schuler et al., 2008). Cor- pus results have shown that a vast majority of naturally-occurring sentences can be parsed in this way using a very small stack bound of three to four elements. This suggests that the standard cubic-time CKY chart-parsing algorithm, which implicitly assumes an un- bounded stack, may be wasting probability mass on trees whose complexity is beyond hu- man recognition or generation capacity. This paper first describes a version of the right- corner transform that is defined over entire probabilistic grammars (cast as infinite sets of generable trees), in order to ensure a fair comparison between bounded-stack and un- bounded PCFG parsing using a common un- derlying model; then it presents experimental results that show a bounded-stack right-corner parser using a transformed version of a gram- mar significantly outperforms an unbounded- stack CKY parser using the original grammar. 1 Introduction Statistical parsing models have recently been pro- posed that employ a bounded stack in time-series (left-to-right) recognition, in order to directly and tractably incorporate incremental phenomena such as (co-)reference or disfluency into parsing deci- sions (Schuler et al., 2008; Miller and Schuler, 2008). These models make use of a right-corner tree transform, based on the left-corner transform described by Johnson (1998), and are supported by corpus results suggesting that most sentences (in En- glish, at least) can be parsed using a very small stack bound of three to four elements (Schuler et al., 2008). This raises an interesting question: if most sentences can be recognized with only three or four elements of stack memory, is the standard cubic-time CKY chart-parsing algorithm, which im- plicitly assumes an unbounded stack, wasting prob- ability mass on trees whose complexity is beyond human recognition or generation capacity? This paper presents parsing accuracy results us- ing transformed and untransformed versions of a corpus-trained probabilistic context-free grammar suggesting that this is indeed the case. Experimental results show a bounded-memory time-series parser using a transformed version of a grammar signifi- cantly outperforms an unbounded-stack CKY parser using the original grammar. Unlike the tree-based transforms described previ- ously, the model-based transform described in this paper does not introduce additional context from corpus data beyond that contained in the origi- nal probabilistic grammar, making it possible to present a fair comparison between bounded- and unbounded-stack versions of the same model. Since this transform takes a probabilistic grammar as in- put, it can also easily accommodate horizontal and vertical Markovisation (annotating grammar sym- bols with parent and sibling categories) as described by Collins (1997) and subsequently. …

Content truncated to 500 words