Reordering Grammar Induction

Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 44–54, Lisbon, Portugal, 17-21 September 2015. c⃝2015 Association for Computational Linguistics. Reordering Grammar Induction Miloˇs Stanojevi´c ILLC University of Amsterdam m.stanojevic@uva.nl Khalil Sima’an ILLC University of Amsterdam k.simaan@uva.nl Abstract We present a novel approach for unsu- pervised induction of a Reordering Gram- mar using a modified form of permuta- tion trees (Zhang and Gildea, 2007), which we apply to preordering in phrase-based machine translation. Unlike previous ap- proaches, we induce in one step both the hierarchical structure and the transduction function over it from word-aligned parallel corpora. Furthermore, our model (1) han- dles non-ITG reordering patterns (up to 5-ary branching), (2) is learned from all derivations by treating not only labeling but also bracketing as latent variable, (3) is entirely unlexicalized at the level of re- ordering rules, and (4) requires no linguis- tic annotation. Our model is evaluated both for accuracy in predicting target order, and for its im- pact on translation quality. We report sig- nificant performance gains over phrase re- ordering, and over two known preordering baselines for English-Japanese. 1 Introduction Preordering (Collins et al., 2005) aims at permut- ing the words of a source sentence s into a new order ´s, hopefully close to a plausible target word order. Preordering is often used to bridge long dis- tance reorderings (e.g., in Japanese- or German- English), before applying phrase-based models (Koehn et al., 2007). Preordering is often bro- ken down into two steps: finding a suitable tree structure, and then finding a transduction function over it. A common approach is to use monolin- gual syntactic trees and focus on finding a trans- duction function of the sibling subtrees under the nodes (Lerner and Petrov, 2013; Xia and Mccord, 2004). The (direct correspondence) assumption underlying this approach is that permuting the sib- lings of nodes in a source syntactic tree can pro- duce a plausible target order. An alternative ap- proach creates reordering rules manually and then learns the right structure for applying these rules (Katz-Brown et al., 2011). Others attempt learn- ing the transduction structure and the transduction function in two separate, consecutive steps (DeN- ero and Uszkoreit, 2011). Here we address the challenge of learning both the trees and the trans- duction functions jointly, in one fell swoop, from word-aligned parallel corpora. Learning both trees and transductions jointly raises two questions. How to obtain suitable trees for the source sentence and how to learn a distri- bution over random variables specifically aimed at reordering in a hierarchical model? In this work we solve both challenges by using the fac- torizations of permutations into Permutation Trees (PETs) (Zhang and Gildea, 2007). As we ex- plain next, PETs can be crucial for exposing the hierarchical reordering patterns found in word- alignments. We obtain permutations in the training data by segmenting every word-aligned source-target pair into minimal phrase pairs; the resulting alignment between minimal phrases is written as a permuta- tion (1:1 and onto) on the …

Content truncated to 500 words