Inducing Sentence Structure from Parallel Corpora for Reordering

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 193–203, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Inducing Sentence Structure from Parallel Corpora for Reordering John DeNero Google Research denero@google.com Jakob Uszkoreit Google Research uszkoreit@google.com Abstract When translating among languages that differ substantially in word order, machine transla- tion (MT) systems benefit from syntactic pre- ordering—an approach that uses features from a syntactic parse to permute source words into a target-language-like order. This paper presents a method for inducing parse trees au- tomatically from a parallel corpus, instead of using a supervised parser trained on a tree- bank. These induced parses are used to pre- order source sentences. We demonstrate that our induced parser is effective: it not only improves a state-of-the-art phrase-based sys- tem with integrated reordering, but also ap- proaches the performance of a recent pre- ordering method based on a supervised parser. These results show that the syntactic structure which is relevant to MT pre-ordering can be learned automatically from parallel text, thus establishing a new application for unsuper- vised grammar induction. 1 Introduction Recent work in statistical machine translation (MT) has demonstrated the effectiveness of syntactic pre- ordering: an approach that permutes source sen- tences into a target-like order as a pre-processing step, using features of a source-side syntactic parse (Collins et al., 2005; Xu et al., 2009). Syntac- tic pre-ordering is particularly effective at apply- ing structural transformations, such as the order- ing change from a subject-verb-object (SVO) lan- guage like English to a subject-object-verb (SOV) language like Japanese. However, state-of-the-art pre-ordering methods require a supervised syntac- tic parser to provide structural information about each sentence. We propose a method that learns both a parsing model and a reordering model di- rectly from a word-aligned parallel corpus. Our ap- proach, which we call Structure Induction for Re- ordering (STIR), requires no syntactic annotations to train, but approaches the performance of a re- cent syntactic pre-ordering method in a large-scale English-Japanese MT system. STIR predicts a pre-ordering via two pipelined models: (1) parsing and (2) tree reordering. The first model induces a binary parse, which defines the space of possible reorderings. In particular, only trees that properly separate verbs from their object noun phrases will license an SVO to SOV trans- formation. The second model locally permutes this tree. Our approach resembles work with binary syn- chronous grammars (Wu, 1997), but is distinct in its emphasis on monolingual parsing as a first phase, and in selecting reorderings without the aid of a target-side language model. The parsing model is trained to maximize the conditional likelihood of trees that license the re- orderings implied by observed word alignments in a parallel corpus. This objective differs from those of previous grammar induction models, which typ- ically focus on succinctly explaining the observed source language corpus via latent hierarchical struc- ture (Pereira and Schabes, 1992; Klein and Man- ning, 2002). Our convex objective allows us to train a feature-rich log-linear parsing …

Content truncated to 500 words