Cube Summing, Approximate Inference with Non-Local Features, and Dynamic Programming without Semirings

Proceedings of the 12th Conference of the European Chapter of the ACL, pages 318–326, Athens, Greece, 30 March – 3 April 2009. c⃝2009 Association for Computational Linguistics Cube Summing, Approximate Inference with Non-Local Features, and Dynamic Programming without Semirings Kevin Gimpel and Noah A. Smith Language Technologies Institute Carnegie Mellon University Pittsburgh, PA 15213, USA {kgimpel,nasmith}@cs.cmu.edu Abstract We introduce cube summing, a technique that permits dynamic programming algo- rithms for summing over structures (like the forward and inside algorithms) to be extended with non-local features that vio- late the classical structural independence assumptions. It is inspired by cube prun- ing (Chiang, 2007; Huang and Chiang, 2007) in its computation of non-local features dynamically using scored k-best lists, but also maintains additional resid- ual quantities used in calculating approx- imate marginals. When restricted to lo- cal features, cube summing reduces to a novel semiring (k-best+residual) that gen- eralizes many of the semirings of Good- man (1999). When non-local features are included, cube summing does not reduce to any semiring, but is compatible with generic techniques for solving dynamic programming equations. 1 Introduction Probabilistic NLP researchers frequently make in- dependence assumptions to keep inference algo- rithms tractable. Doing so limits the features that are available to our models, requiring features to be structurally local. Yet many problems in NLP—machine translation, parsing, named-entity recognition, and others—have benefited from the addition of non-local features that break classical independence assumptions. Doing so has required algorithms for approximate inference. Recently cube pruning (Chiang, 2007; Huang and Chiang, 2007) was proposed as a way to lever- age existing dynamic programming algorithms that find optimal-scoring derivations or structures when only local features are involved. Cube prun- ing permits approximate decoding with non-local features, but leaves open the question of how the feature weights or probabilities are learned. Mean- while, some learning algorithms, like maximum likelihood for conditional log-linear models (Laf- ferty et al., 2001), unsupervised models (Pereira and Schabes, 1992), and models with hidden vari- ables (Koo and Collins, 2005; Wang et al., 2007; Blunsom et al., 2008), require summing over the scores of many structures to calculate marginals. We first review the semiring-weighted logic programming view of dynamic programming al- gorithms (Shieber et al., 1995) and identify an in- tuitive property of a program called proof locality that follows from feature locality in the underlying probability model (§2). We then provide an analy- sis of cube pruning as an approximation to the in- tractable problem of exact optimization over struc- tures with non-local features and show how the use of non-local features with k-best lists breaks certain semiring properties (§3). The primary contribution of this paper is a novel technique— cube summing—for approximate summing over discrete structures with non-local features, which we relate to cube pruning (§4). We discuss imple- mentation (§5) and show that cube summing be- comes exact and expressible as a semiring when restricted to local features; this semiring general- izes many commonly-used semirings in dynamic programming (§6). 2 Background In this section, we …

Content truncated to 500 words