First- and Second-Order Expectation Semirings with Applications to Minimum-Risk Training on Translation Forests

Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 40–51, Singapore, 6-7 August 2009. c⃝2009 ACL and AFNLP First- and Second-Order Expectation Semirings with Applications to Minimum-Risk Training on Translation Forests∗ Zhifei Li and Jason Eisner Department of Computer Science and Center for Language and Speech Processing Johns Hopkins University, Baltimore, MD 21218, USA zhifei.work@gmail.com, jason@cs.jhu.edu Abstract Many statistical translation models can be regarded as weighted logical deduction. Under this paradigm, we use weights from the expectation semiring (Eisner, 2002), to compute first-order statistics (e.g., the ex- pected hypothesis length or feature counts) over packed forests of translations (lat- tices or hypergraphs). We then introduce a novel second-order expectation semir- ing, which computes second-order statis- tics (e.g., the variance of the hypothe- sis length or the gradient of entropy). This second-order semiring is essential for many interesting training paradigms such as minimum risk, deterministic anneal- ing, active learning, and semi-supervised learning, where gradient descent optimiza- tion requires computing the gradient of en- tropy or risk. We use these semirings in an open-source machine translation toolkit, Joshua, enabling minimum-risk training for a benefit of up to 1.0 BLEU point. 1 Introduction A hypergraph or “packed forest” (Gallo et al., 1993; Klein and Manning, 2004; Huang and Chi- ang, 2005) is a compact data structure that uses structure-sharing to represent exponentially many trees in polynomial space. A weighted hypergraph also defines a probability or other weight for each tree, and can be used to represent the hypothesis space considered (for a given input) by a mono- lingual parser or a tree-based translation system, e.g., tree to string (Quirk et al., 2005; Liu et al., 2006), string to tree (Galley et al., 2006), tree to tree (Eisner, 2003), or string to string with latent tree structures (Chiang, 2007). ∗This research was partially supported by the Defense Advanced Research Projects Agency’s GALE program via Contract No HR0011-06-2-0001. We are grateful to Sanjeev Khudanpur for early guidance and regular discussions. Given a hypergraph, we are often interested in computing some quantities over it using dynamic programming algorithms. For example, we may want to run the Viterbi algorithm to find the most probable derivation tree in the hypergraph, or the k most probable trees. Semiring-weighted logic pro- gramming is a general framework to specify these algorithms (Pereira and Warren, 1983; Shieber et al., 1994; Goodman, 1999; Eisner et al., 2005; Lopez, 2009). Goodman (1999) describes many useful semirings (e.g., Viterbi, inside, and Viterbi- n-best). While most of these semirings are used in “testing” (i.e., decoding), we are mainly interested in the semirings that are useful for “training” (i.e., parameter estimation). The expectation semiring (Eisner, 2002), originally proposed for finite-state machines, is one such “training” semiring, and can be used to compute feature expectations for the E- step of the EM algorithm, or gradients of the like- lihood function for gradient descent. In this paper, we apply the expectation semir- ing (Eisner, 2002) to a hypergraph (or packed for- est) rather than just …

Content truncated to 500 words