An Efficient Two-Pass Approach to Synchronous-CFG Driven Statistical MT

Proceedings of NAACL HLT 2007, pages 500–507, Rochester, NY, April 2007. c⃝2007 Association for Computational Linguistics An Efficient Two-Pass Approach to Synchronous-CFG Driven Statistical MT Ashish Venugopal and Andreas Zollmann and Stephan Vogel School of Computer Science, Carnegie Mellon University, Pittsburgh interACT Lab, University of Karlsruhe {ashishv,zollmann,vogel+}@cs.cmu.edu Abstract We present an efficient, novel two-pass approach to mitigate the computational impact resulting from online intersection of an n-gram language model (LM) and a probabilistic synchronous context-free grammar (PSCFG) for statistical machine translation. In first pass CYK-style decod- ing, we consider first-best chart item ap- proximations, generating a hypergraph of sentence spanning target language deriva- tions. In the second stage, we instantiate specific alternative derivations from this hypergraph, using the LM to drive this search process, recovering from search er- rors made in the first pass. Model search errors in our approach are comparable to those made by the state-of-the-art “Cube Pruning” approach in (Chiang, 2007) un- der comparable pruning conditions evalu- ated on both hierarchical and syntax-based grammars. 1 Introduction Syntax-driven (Galley et al., 2006) and hierarchi- cal translation models (Chiang, 2005) take advan- tage of probabilistic synchronous context free gram- mars (PSCFGs) to represent structured, lexical re- ordering constraints during the decoding process. These models extend the domain of locality (over phrase-based models) during decoding, represent- ing a significantly larger search space of possible translation derivations. While PSCFG models are often induced with the goal of producing grammati- cally correct target translations as an implicit syntax- structured language model, we acknowledge the value of n-gram language models (LM) in phrase- based approaches. Integrating n-gram LMs into PSCFGs based de- coding can be viewed as online intersection of the PSCFG grammar with the finite state machine rep- resented by the n-gram LM, dramatically increasing the effective number of nonterminals in the decoding grammar, rendering the decoding process essentially infeasible without severe, beam-based lossy prun- ing. The alternative, simply decoding without the n-gram LM and rescoring N-best alternative transla- tions, results in substantially more search errors, as shown in (Zollmann and Venugopal, 2006). Our two-pass approach involves fast, approximate synchronous parsing in a first stage, followed by a second, detailed exploration through the resulting hypergraph of sentence spanning derivations, using the n-gram LM to drive that search. This achieves search errors comparable to a strong “Cube Pruning” (Chiang, 2007), single-pass baseline. The first pass corresponds to a severe parameterization of Cube Pruning considering only the first-best (LM inte- grated) chart item in each cell while maintaining un- explored alternatives for second-pass consideration. Our second stage allows the integration of long dis- tance and flexible history n-gram LMs to drive the search process, rather than simply using such mod- els for hypothesis rescoring. We begin by discussing the PSCFG model for statistical machine translation, motivating the need 500 for effective n-gram LM integration during decod- ing. We then present our two-pass approach and discuss Cube Pruning as a state-of-the-art baseline. We present results in the form of search error analy- sis and translation …

Content truncated to 500 words