Source-side Preordering for Translation using Logistic Regression and Depth-first Branch-and-Bound Search

Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics, pages 239–248, Gothenburg, Sweden, April 26-30 2014. c⃝2014 Association for Computational Linguistics Source-side Preordering for Translation using Logistic Regression and Depth-first Branch-and-Bound Search∗ Laura Jehl⋆ Adri`a de Gispert‡ Mark Hopkins‡ William Byrne‡ ⋆Dept. of Computational Linguistics, Heidelberg University. 69120 Heidelberg, Germany jehl@cl.uni-heidelberg.de ‡ SDL Research. East Road, Cambridge CB1 1BH, U.K. {agispert,mhopkins,bbyrne}@sdl.com Abstract We present a simple preordering approach for machine translation based on a feature- rich logistic regression model to predict whether two children of the same node in the source-side parse tree should be swapped or not. Given the pair-wise chil- dren regression scores we conduct an effi- cient depth-first branch-and-bound search through the space of possible children per- mutations, avoiding using a cascade of classifiers or limiting the list of possi- ble ordering outcomes. We report exper- iments in translating English to Japanese and Korean, demonstrating superior per- formance as (a) the number of crossing links drops by more than 10% absolute with respect to other state-of-the-art pre- ordering approaches, (b) BLEU scores im- prove on 2.2 points over the baseline with lexicalised reordering model, and (c) de- coding can be carried out 80 times faster. 1 Introduction Source-side preordering for translation is the task of rearranging the order of a given source sen- tence so that it best resembles the order of the tar- get sentence. It is a divide-and-conquer strategy aiming to decouple long-range word movement from the core translation task. The main advan- tage is that translation becomes computationally cheaper as less word movement needs to be con- sidered, which results in faster and better transla- tions, if preordering is done well and efficiently. Preordering also can facilitate better estimation of alignment and translation models as the paral- lel data becomes more monotonically-aligned, and ∗This work was done during an internship of the first au- thor at SDL Research, Cambridge. translation gains can be obtained for various sys- tem architectures, e.g. phrase-based, hierarchical phrase-based, etc. For these reasons, preordering has a clear re- search and commercial interest, as reflected by the extensive previous work on the subject (see Sec- tion 2). From these approaches, we are particu- larly interested in those that (i) involve little or no human intervention, (ii) require limited computa- tional resources at runtime, and (iii) make use of available linguistic analysis tools. In this paper we propose a novel preordering approach based on a logistic regression model trained to predict whether to swap nodes in the source-side dependency tree. For each pair of sibling nodes in the tree, the model uses a feature-rich representation that includes lexical cues to make relative reordering predictions be- tween them. Given these predictions, we conduct a depth-first branch-and-bound search through the space of possible permutations of all sibling nodes, using the regression scores to guide the search. This approach has multiple advantages. First, the search for permutations is efficient and does not require specific heuristics or hard limits for …

Content truncated to 500 words