Probabilistic Parsing Strategies

Probabilistic Parsing Strategies Mark-Jan Nederhof Faculty of Arts University of Groningen P.O. Box 716 NL-9700 AS Groningen The Netherlands markjan@let.rug.nl Giorgio Satta Dept. of Information Engineering University of Padua via Gradenigo, 6/A I-35131 Padova Italy satta@dei.unipd.it Abstract We present new results on the relation between context-free parsing strategies and their probabilis- tic counter-parts. We provide a necessary condition and a sufficient condition for the probabilistic exten- sion of parsing strategies. These results generalize existing results in the literature that were obtained by considering parsing strategies in isolation. 1 Introduction Context-free grammars (CFGs) are standardly used in computational linguistics as formal models of the syntax of natural language, associating sentences with all their possible derivations. Other computa- tional models with the same generative capacity as CFGs are also adopted, as for instance push-down automata (PDAs). One of the advantages of the use of PDAs is that these devices provide an operational specification that determines which steps must be performed when parsing an input string, something that is not offered by CFGs. In other words, PDAs can be associated to parsing strategies for context- free languages. More precisely, parsing strategies are traditionally specified as constructions that map CFGs to language-equivalent PDAs. Popular ex- amples of parsing strategies are the standard con- structions of top-down PDAs (Harrison, 1978), left- corner PDAs (Rosenkrantz and Lewis II, 1970), shift-reduce PDAs (Aho and Ullman, 1972) and LR PDAs (Sippu and Soisalon-Soininen, 1990). CFGs and PDAs have probabilistic counterparts, called probabilistic CFGs (PCFGs) and probabilis- tic PDAs (PPDAs). These models are very popular in natural language processing applications, where they are used to define a probability distribution function on the domain of all derivations for sen- tences in the language of interest. In PCFGs and PPDAs, probabilities are assigned to rules or tran- sitions, respectively. However, these probabilities cannot be chosen entirely arbitrarily. For example, for a given nonterminal A in a PCFG, the sum of the probabilities of all rules rewriting A must be 1. This means that, out of a total of say m rules rewriting A, only m − 1 rules represent “free” parameters. Depending on the choice of the parsing strategy, the constructed PDA may allow different probabil- ity distributions than the underlying CFG, since the set of free parameters may differ between the CFG and the PDA, both quantitatively and qualitatively. For example, (Sornlertlamvanich et al., 1999) and (Roark and Johnson, 1999) have shown that a prob- ability distribution that can be obtained by training the probabilities of a CFG on the basis of a corpus can be less accurate than the probability distribution obtained by training the probabilities of a PDA con- structed by a particular parsing strategy, on the basis of the same corpus. Also the results from (Chitrao and Grishman, 1990), (Charniak and Carroll, 1994) and (Manning and Carpenter, 2000) could be seen in this light. The question arises of whether parsing strate- gies can be extended probabilistically, i.e., whether a given construction of PDAs from CFGs can be …

Content truncated to 500 words