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

ACL ID N09-1039
Title Positive Results for Parsing with a Bounded Stack using a Model-Based Right-Corner Transform
Venue Human Language Technologies
Session Main Conference
Year 2009
Authors

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 ord...