Parsing with the Shortest Derivation

Parsing with the Shortest Derivation Rens Bod Informatics Research Institute, University of Leeds, Leeds LS2 9JT, & Institute for Logic, Language and Computation, University of Amsterdam rens@scs.leeds.ac.uk Abstract Common wisdom has it that the bias of stochastic grammars in favor of shorter derivations of a sentence is harmful and should be redressed. We show that the common wisdom is wrong for stochastic grammars that use elementary trees instead of context-free rules, such as Stochastic Tree-Substitution Grammars used by Data-Oriented Parsing models. For such grammars a non-probabilistic metric based on the shortest derivation outperforms a probabilistic metric on the ATIS and OVIS corpora, while it obtains competitive results on the Wall Street Journal (WSJ) corpus. This paper also contains the first published experiments with DOP on the WSJ. 1. Introduction A well-known property of stochastic grammars is their propensity to assign higher probabilities to shorter derivations of a sentence (cf. Chitrao & Grishman 1990; Magerman & Marcus 1991; Briscoe & Carroll 1993; Charniak 1996). This propensity is due to the probability of a derivation being computed as the product of the rule probabilities, and thus shorter derivations involving fewer rules tend to have higher probabilities, almost regardless of the training data. While this bias may seem interesting in the light of the principle of cognitive economy, shorter derivat- ions generate smaller parse trees (consisting of fewer nodes) which are not warranted by the correct parses of sentences. Most systems therefore redress this bias, for instance by normalizing the derivation probability (see Caraballo & Charniak 1998). However, for stochastic grammars that use elementary trees instead of context-free rules, the propensity to assign higher probabilities to shorter derivations does not necessarily lead to a bias in favor of smaller parse trees, because elementary trees may differ in size and lexicalization. For Stochastic Tree-Substitution Grammars (STSG) used by Data- Oriented Parsing (DOP) models, it has been observed that the shortest derivation of a sentence consists of the largest subtrees seen in a treebank that generate that sentence (cf. Bod 1992, 98). We may therefore wonder whether for STSG the bias in favor of shorter derivations is perhaps beneficial rather than harmful. To investigate this question we created a new STSG-DOP model which uses this bias as a feature. This non-probabilistic DOP model parses each sentence by returning its shortest derivation (consisting of the fewest subtrees seen in the corpus). Only if there is more than one shortest derivation the model backs off to a frequency ordering of the corpus- subtrees and chooses the shortest derivation with most highest ranked subtrees. We compared this non- probabilistic DOP model against the probabilistic DOP model (which estimates the most probable parse for each sentence) on three different domains: the Penn ATIS treebank (Marcus et al. 1993), the Dutch OVIS treebank (Bonnema et al. 1997) and the Penn Wall Street Journal (WSJ) treebank (Marcus et al. 1993). Surprisingly, the non-probabilistic DOP model outperforms the probabilistic DOP model on both the ATIS and OVIS treebanks, while it obtains competit- …

Content truncated to 500 words