Feature-Rich Translation by Quasi-Synchronous Lattice Parsing

Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 219–228, Singapore, 6-7 August 2009. c⃝2009 ACL and AFNLP Feature-Rich Translation by Quasi-Synchronous Lattice Parsing Kevin Gimpel and Noah A. Smith Language Technologies Institute School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213, USA {kgimpel,nasmith}@cs.cmu.edu Abstract We present a machine translation frame- work that can incorporate arbitrary fea- tures of both input and output sentences. The core of the approach is a novel de- coder based on lattice parsing with quasi- synchronous grammar (Smith and Eis- ner, 2006), a syntactic formalism that does not require source and target trees to be isomorphic. Using generic approx- imate dynamic programming techniques, this decoder can handle “non-local” fea- tures. Similar approximate inference tech- niques support efficient parameter esti- mation with hidden variables. We use the decoder to conduct controlled exper- iments on a German-to-English transla- tion task, to compare lexical phrase, syn- tax, and combined models, and to mea- sure effects of various restrictions on non- isomorphism. 1 Introduction We have seen rapid recent progress in machine translation through the use of rich features and the development of improved decoding algorithms, often based on grammatical formalisms.1 If we view MT as a machine learning problem, features and formalisms imply structural independence as- sumptions, which are in turn exploited by efficient inference algorithms, including decoders (Koehn et al., 2003; Yamada and Knight, 2001). Hence a tension is visible in the many recent research ef- forts aiming to decode with “non-local” features (Chiang, 2007; Huang and Chiang, 2007). Lopez (2009) recently argued for a separation between features/formalisms (and the indepen- 1Informally, features are “parts” of a parallel sentence pair and/or their mutual derivation structure (trees, alignments, etc.). Features are often implied by a choice of formalism. dence assumptions they imply) from inference al- gorithms in MT; this separation is widely appreci- ated in machine learning. Here we take first steps toward such a “universal” decoder, making the fol- lowing contributions: Arbitrary feature model (§2): We define a sin- gle, direct log-linear translation model (Papineni et al., 1997; Och and Ney, 2002) that encodes most popular MT features and can be used to encode any features on source and target sentences, de- pendency trees, and alignments. The trees are op- tional and can be easily removed, allowing sim- ulation of “string-to-tree,” “tree-to-string,” “tree- to-tree,” and “phrase-based” models, among many others. We follow the widespread use of log-linear modeling for direct translation modeling; the nov- elty is in the use of richer feature sets than have been previously used in a single model. Decoding as QG parsing (§3–4): We present a novel decoder based on lattice parsing with quasi- synchronous grammar (QG; Smith and Eisner, 2006).2 Further, we exploit generic approximate inference techniques to incorporate arbitrary “non- local” features in the dynamic programming algo- rithm (Chiang, 2007; Gimpel and Smith, 2009). Parameter estimation (§5): We exploit simi- lar approximate inference methods in regularized pseudolikelihood estimation (Besag, 1975) with hidden variables to discriminatively and …

Content truncated to 500 words