Approximate PCFG Parsing Using Tensor Decomposition

Proceedings of NAACL-HLT 2013, pages 487–496, Atlanta, Georgia, 9–14 June 2013. c⃝2013 Association for Computational Linguistics Approximate PCFG Parsing Using Tensor Decomposition Shay B. Cohen Department of Computer Science Columbia University, USA scohen@cs.columbia.edu Giorgio Satta Department of Information Engineering University of Padua, Italy satta@dei.unipd.it Michael Collins Department of Computer Science Columbia University, USA mcollins@cs.columbia.edu Abstract We provide an approximation algorithm for PCFG parsing, which asymptotically im- proves time complexity with respect to the in- put grammar size, and prove upper bounds on the approximation quality. We test our algo- rithm on two treebanks, and get significant im- provements in parsing speed. 1 Introduction The problem of speeding-up parsing algorithms based on probabilistic context-free grammars (PCFGs) has received considerable attention in recent years. Several strategies have been proposed, including beam-search, best-first and A∗. In this paper we focus on the standard approach of approx- imating the source PCFG in such a way that parsing accuracy is traded for efficiency. Nederhof (2000) gives a thorough presentation of old and novel ideas for approximating non- probabilistic CFGs by means of finite automata, on the basis of specialized preprocessing of self- embedding structures. In the probabilistic domain, approximation by means of regular grammars is also exploited by Eisner and Smith (2005), who filter long-distance dependencies on-the-fly. Beyond finite automata approximation, Charniak et al. (2006) propose a coarse-to-fine approach in which an approximated (not necessarily regular) PCFG is used to construct a parse forest for the in- put sentence. Some statistical parameters are then computed on such a structure, and exploited to filter parsing with the non-approximated grammar. The approach can also be iterated at several levels. In the non-probabilistic setting, a similar filtering ap- proach was also proposed by Boullier (2003), called “guided parsing.” In this paper we rely on an algebraic formulation of the inside-outside algorithm for PCFGs, based on a tensor formulation developed for latent-variable PCFGs in Cohen et al. (2012). We combine the method with known techniques for tensor decompo- sition to approximate the source PCFG, and develop a novel algorithm for approximate PCFG parsing. We obtain improved time upper bounds with respect to the input grammar size for PCFG parsing, and provide error upper bounds on the PCFG approxi- mation, in contrast with existing heuristic methods. 2 Preliminaries This section introduces the special representation for probabilistic context-free grammars that we adopt in this paper, along with the decoding algorithm that we investigate. For an integer i ≥ 1, we let [i] = {1, 2, . . . , i}. 2.1 Probabilistic Context-Free Grammars We consider context-free grammars (CFGs) in Chomsky normal form, and denote them as (N, L, R) where: • N is the finite set of nonterminal symbols, with m = |N|, and L is the finite set of words (lexi- cal tokens), with L ∩ N = ∅ and with n = |L|. • R is a set of rules having the form a → b c, a, b, c ∈ N, or the form a → x, …

Content truncated to 500 words