Relating Probabilistic Grammars and Automata

By Steven P. Abney, David A. McAllester, Fernando C Pereira. 1999

Both probabilistic context-free grammars (PCFGs) and shift-reduce probabilistic pushdown 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 probabilistic languages, they appear to impose different inductive biases.

Subfields: Computational Linguistics & Semantics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Linguistics & Semantics

Citations in the corpus

Recurrent Neural Network Grammars (2016, methodology): “For a tree y and a sequence of symbols x , we write a ( x , y ) to indicate the corresponding sequence of generation transitions, and b ( x , y ) to indicate the parser transitions.”
Globally Normalized Transition-Based Neural Networks (2016, neutral): “…(or non-equivalence) results for joint models of the form p ( d 1: n , x 1: n ) are quite different: for example results from Chi (1999) and Abney et al. (1999) Then it is easily veriﬁed that In proving P G P L we will use a simple problem where every example seen in training or test data…”
Structured Generative Models of Natural Source Code (2014, background): “Aside from the question of the order of the traversals, Tree Traversal models are essentially special cases of Probabilistic Pushdown Automata (PPDA) (for deﬁnition and weak equivalence to PCFGs, see Abney et al. (1999)).”
Inside-Outside and Forward-Backward Algorithms Are Just Backprop (tutorial paper) (2016, background): “The construction below Nederhof and Satta (2003) takes the weighted version of such a grammar and “renormalizes” it into a PCFG (Thompson, 1974; Abney et al., 1999; Chi, 1999).”
Structured language modeling (2000, background): “A thorough comparison between the two related classes of probabilistic languages (PCFGs and shift-reduce probabilistic push-down automata) has been presented in Abney et al. (1999). Related work in statistical parsing of natural language includes the early work in Jelinek, Lafferty, Magerman, Mercer”
Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations (2005, background): “WCFG’s and their relationship to pPDSs and SCFGs were considered in Abney et al. [1999], but they did not consider algorithms for analyzing them.”
Joint and Conditional Estimation of Tagging and Parsing Models (2001, background): “The distribution over trees generated by the joint model is a probabilistic context-free language (Abney et al., 1999).”