Extraction Programs: A Unified Approach to Translation Rule Extraction

Proceedings of the 6th Workshop on Statistical Machine Translation, pages 523–532, Edinburgh, Scotland, UK, July 30–31, 2011. c⃝2011 Association for Computational Linguistics Extraction Programs: A Unified Approach to Translation Rule Extraction Mark Hopkins and Greg Langmead and Tai Vo SDL Language Technologies Division 6060 Center Drive, Suite 150 Los Angeles, CA 90045 {mhopkins,glangmead,tvo}@sdl.com Abstract We provide a general algorithmic schema for translation rule extraction and show that several popular extraction methods (includ- ing phrase pair extraction, hierarchical phrase pair extraction, and GHKM extraction) can be viewed as specific instances of this schema. This work is primarily intended as a survey of the dominant extraction paradigms, in which we make explicit the close relationship be- tween these approaches, and establish a lan- guage for future hybridizations. This facili- tates a generic and extensible implementation of alignment-based extraction methods. 1 Introduction The tradition of extracting translation rules from aligned sentence pairs dates back more than a decade. A prominent early example is phrase-based extraction (Och et al., 1999). Around the middle of the last decade, two ex- traction paradigms were proposed for syntax-based machine translation: the Hiero paradigm of (Chi- ang, 2005) and the GHKM paradigm of (Galley et al., 2004). From these papers followed two largely independent lines of research, respectively dubbed formally syntax-based machine translation (Chiang, 2007; Zollmann and Venugopal, 2006; Venugopal et al., 2007; Lopez, 2007; Marton and Resnik, 2008; Li et al., 2009; de Gispert et al., 2010) and linguis- tically syntax-based machine translation (Galley et al., 2006; Marcu et al., 2006; Liu et al., 2006; Huang et al., 2006; Liu et al., 2007; Mi and Huang, 2008; Zhang et al., 2008; Liu et al., 2009). In this paper, we unify these strands of research by showing how to express Hiero extraction, GHKM extraction, and phrase-based extraction as instances of a single master extraction method. Specifically, we express each technique as a simple “program” given to a generic “evaluator”. Table 1 summarizes how to express several popular extraction methods as “extraction programs.” Besides providing a unifying survey of popular alignment-based extraction methods, this work has the practical benefit of facilitating the implementa- tion of these methods. By specifying the appropri- ate input program, the generic evaluator (coded, say, as a Python module) can be used to execute any of the extraction techniques in Table 1. New extraction techniques and hybridizations of existing techniques can be supported with minimal additional program- ming. 2 Building Blocks The family of extraction algorithms under consider- ation share a common setup: they extract translation rules from a sentence pair and an alignment. In this section, we define these concepts. 2.1 Patterns and Sentences Assume we have a global vocabulary of atomic sym- bols, containing the reserved substitution symbol ∇. Define a pattern as a sequence of symbols. Define the rank of a pattern as the count of its ∇ symbols. Let ∇k ≜ ⟨ k � �� � ∇, ∇, ..., ∇⟩. We will typically use space-delimited quotations to represent example patterns, e.g. …

Content truncated to 500 words