Algorithms for Weighted Pushdown Automata

Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 9669 - 9680 December 7-11, 2022 ©2022 Association for Computational Linguistics Algorithms for Weighted Pushdown Automata Alexandra Butoi1 Brian DuSell2 Tim Vieira3 Ryan Cotterell1 David Chiang2 1ETH Zürich 2University of Notre Dame 3Johns Hopkins University alexandra.butoi@inf.ethz.ch {bdusell1, dchiang}@nd.edu {tim.f.vieira, ryan.cotterell}@gmail.com Abstract Weighted pushdown automata (WPDAs) are at the core of many natural language process- ing tasks, like syntax-based statistical machine translation and transition-based dependency parsing. As most existing dynamic program- ming algorithms are designed for context-free grammars (CFGs), algorithms for PDAs often resort to a PDA-to-CFG conversion. In this paper, we develop novel algorithms that oper- ate directly on WPDAs. Our algorithms are inspired by Lang’s algorithm, but use a more general definition of pushdown automaton and either reduce the space requirements by a factor of |Γ| (the size of the stack alphabet) or reduce the runtime by a factor of more than |𝐴���| (the number of states). When run on the same class of PDAs as Lang’s algorithm, our algorithm is both more space-efficient by a factor of |Γ| and more time-efficient by a factor of |𝐴���| · |Γ|. https://github.com/rycolab/wpda 1 Introduction Weighted pushdown automata (WPDAs) are widespread in natural language processing (NLP), primarily in syntactic analysis. For instance, WPDAs have found use in syntax-based statisti- cal machine translation (Allauzen et al., 2014), and many transition-based dependency parsers (Nivre, 2004; Chen and Manning, 2014; Weiss et al., 2015; Dyer et al., 2015; Andor et al., 2016; Shi et al., 2017; Ma et al., 2018; Fernández-González and Gómez-Rodríguez, 2019) are special cases of WPDAs. In addition, PDAs have been used in com- putational psycholinguistics as models of human sentence processing (Resnik, 1992). Despite their ubiquity, there has been relatively little research on the theory of WPDAs themselves. In some ways, WPDAs are treated as second-class citizens com- pared to their equivalent cousins, weighted context- free grammars (WCFGs), for which a variety of dy- Extended PDA Top-down PDA Bottom-up PDA Top-down NF PDA Simple PDA Bottom-up NF PDA Stringsum CFG Chomsky NF Prop. 2 Aho-Ullman Prop. 1 Prop. 4 Prop. 3 Fig. 5 Lang Fig. 3 CKY ⊂ ⊂ Figure 1: Roadmap of the paper. Solid lines are new results in this paper; dashed lines are old results. We are aware of two existing methods for PDA stringsums, via CFG and via Lang’s algorithm; our algorithms are faster and/or more general than both. namic programming algorithms exists (Bar-Hillel et al., 1961; Earley, 1970; Stolcke, 1995). To help fill this gap, this paper offers several new and im- proved algorithms for computing with WPDAs. Figure 1 gives an overview of most of our re- sults. We start by defining a weighted version of the extended PDAs of Aho and Ullman (1972, p. 173) and two special cases: the standard defi- nition (Hopcroft et al., 2006), which we call top- down, and its mirror image, which we call bottom- up. Both top-down and bottom-up WPDAs have been used in NLP. …

Content truncated to 500 words