Relating Probabilistic Grammars and Automata

Relating Probabilistic Grammars and Automata Steven Abney David McAllester Fernando Pereira AT&T Labs-Research 180 Park Ave Florham Park NJ 07932 {abney, dmac, pereira}@research.att.com Abstract Both probabilistic context-free grammars (PCFGs) and shift-reduce probabilistic push- down automata (PPDAs) have been used for language modeling and maximum likelihood parsing. We investigate the precise relationship between these two formalisms, showing that, while they define the same classes of probabilis- tic languages, they appear to impose different inductive biases. 1 Introduction Current work in stochastic language models and maximum likelihood parsers falls into two main approaches. The first approach (Collins, 1998; Charniak, 1997) uses directly the defini- tion of stochastic grammar, defining the prob- ability of a parse tree as the probability that a certain top-down stochastic generative pro- cess produces that tree. The second approach (Briscoe and Carroll, 1993; Black et al., 1992; Magerman, 1994; Ratnaparkhi, 1997; Chelba and Jelinek, 1998) defines the probability of a parse tree as the probability that a certain shift- reduce stochastic parsing automaton outputs that tree. These two approaches correspond to the classical notions of context-free grammars and nondeterministic pushdown automata re- spectively. It is well known that these two clas- sical formalisms define the same language class. In this paper, we show that probabilistic context- free grammars (PCFGs) and probabilistic push- down automata (PPDAs) define the same class of distributions on strings, thus extending the classical result to the stochastic case. We also touch on the perhaps more interesting ques- tion of whether PCFGs and shift-reduce pars- ing models have the same inductive bias with respect to the automatic learning of model pa- rameters from data. Though we cannot provide a definitive answer, the constructions we use to answer the equivalence question involve blow- ups in the number of parameters in both direc- tions, suggesting that the two models impose different inductive biases. We are concerned here with probabilistic shift-reduce parsing models that define prob- ability distributions over word sequences, and in particular the model of Chelba and Je- linek (1998). Most other probabilistic shift- reduce parsing models (Briscoe and Carroll, 1993; Black et al., 1992; Magerman, 1994; Rat- naparkhi, 1997) give only the conditional prob- ability of a parse tree given a word sequence. Collins (1998) has argued that those models fail to capture the appropriate dependency relations of natural language. Furthermore, they are not directly comparable to PCFGs, which define probability distributions over word sequences. To make the discussion somewhat more con- crete, we now present a simplified version of the Chelba-Jelinek model. Consider the following sentence: The small woman gave the fat man her sandwich. The model under discussion is based on shift- reduce PPDAs. In such a model, shift transi- tions generate the next word w and its associ- ated syntactic category X and push the pair (X, w) on the stack. Each shift transition is followed by zero or more reduce transitions that combine topmost stack entries. For exam- ple the stack elements (Det, the), (hdj, small), (N, woman) can be combined …

Content truncated to 500 words