1 Motivation

A major focus of current work in machine translation is the word order differences between source language and target language sentences. The main stream statistical machine translation (SMT) models (Brown et al. Reference Brown, Della Pietra, Della Pietra and Mercer1993; Zens, Och and Ney Reference Och and Ney2002; Koehn, Och and Marcu Reference Koehn, Och and Marcu2003; Och and Ney Reference Och and Ney2004) deal with word order differences alongside the target lexical choice (lexicon and phrase tables), albeit in two different statistical sub-models. Dynamic models integrated into the decoding process may reorder target phrases relative to their source sides, e.g., as a phrase sequence generation process with the possibility of dynamically swapping the order of neighboring phrases (Tillman Reference Tillman2004).

Similarly, hierarchical models of phrase reordering employ template phrases represented as synchronous grammars or tree transducers (e.g., Wu and Wong Reference Wu and Wong1998; Chiang Reference Chiang2005), thereby accounting for hierarchical reordering patterns in data alongside lexical choice. These models explore more varied ranges of reordering phenomena, e.g., defined by at most inverting the order of sibling subtrees under each node in binary source/target trees (akin to inversion transduction grammar (ITG); Wu and Wong Reference Wu and Wong1998).

Undoubtedly, the choice of source-target reordering patterns in machine translation is intertwined with the source-target lexical choice pairing. Statistically speaking, however, a generative story could first select a target word order, given the source sentence only, and then choose the target words, given the selected target word order and source words. One gross simplification of this statistical generative story is known as source reordering (or source permutation), where the reordered source string is fixated upon before translation starts (e.g., Xia and McCord Reference Xia and McCord2004; Collins, Koehn and Kučerová Reference Collins, Koehn and Kučerová2005; Wang, Collins and Koehn Reference Wang, Collins and Koehn2007; Tromble and Eisner Reference Tromble and Eisner2009; Khalilov and Sima'an Reference Khalilov and Sima'an2010; Visweswariah et al. Reference Visweswariah, Navratil, Sorensen, Chenthamarakshan and Kambhatla2010). In source reordering, the words of the source string s are reordered to minimize word order differences with the target string t, leading to the source permuted string . Presumably, a standard Phrase-Based Statistical Machine Translation (PBSMT) system (Zens et al. Reference Zens, Och and Ney2002; Koehn et al. Reference Koehn, Och and Marcu2003; Och and Ney Reference Och and Ney2004) trained to translate from to t should have an easier task than translating directly from s to t. The source reordering part, s-to-, can be implemented in various learning frameworks, possibly manipulating morpho-syntactic parses of s (e.g., Xia and McCord Reference Xia and McCord2004; Collins et al. Reference Collins, Koehn and Kučerová2005; Khalilov and Sima'an Reference Khalilov and Sima'an2010). Once a source reordering model exists, given s it will output a guess g that might be different from the ideal permutation . The training of the translation model on a parallel corpus g -to-t implicitly conditions the target lexical choice on the source words and the kind of chosen order in g .

Earlier work highlights the benefits of source reordering as a pre-processing step, mainly for dealing with long-range reorderings, e.g., in Dutch–English the Dutch verb in final position of a relative clause may move far forward in the English counterpart. While pre-processing the input may represent an important utility of source reordering, there remains a major side effect largely unexplored: the impact of source reordering on the back end translation model. Once the latter model is trained on parallel data {〈g ,t〉}, with g and t having far more monotone alignment between them than s and t have, the model acquires a rather different phrase table. How does the resulting phrase table differ from the original table, and what properties of this table could predict improvement in translation quality, i.e., besides the quality of the input g relative to the ideal permutation ?

In this paper we study the effects of source reordering on the back end translation model. To conduct this empirical study we first set up source reordering oracle systems (ideal source reordering) and our own version of the currently popular syntax-driven models and observe how each of these source reordering choices affects the translation model.

After presenting the baseline (Section 2), the source reordering framework (Section 3), and the related work (Section 4), Section 5 reviews the data and the experimental setting for all subsequent empirical experiments. Section 6 presents experiments measuring oracle performance improvement for three language pairs (English to Dutch/Spanish/Chinese). Beside string-driven oracle results, we report results using ITG-like transductions over a single syntactic parse tree of s. While the literature on source reordering reports mixed performance improvements for different language pairs (e.g., Xia and McCord Reference Xia and McCord2004; Collins et al. Reference Collins, Koehn and Kučerová2005; Wang et al. Reference Wang, Collins and Koehn2007; Khalilov and Sima'an Reference Khalilov and Sima'an2010), our oracle experiments show great potential for source reordering. Our results confirm other reports that reordering a single syntactic tree could be rather suboptimal (e.g., Huang et al. Reference Huang, Zhang, Gildea and Knight2009).

Subsequently, in Section 7 we present a source reordering model that manipulates the source parse tree by a cascaded sequence of (ITG-like) permutation transductions. The probability of each individual transduction in the sequence is conditioned on contextual features from the outcome of all preceding transductions. The conditioning on the outcome of preceding transductions is a departure from earlier approaches that learn statistically independent source permutation steps (e.g., Tromble and Eisner Reference Tromble and Eisner2009; Visweswariah et al. Reference Visweswariah, Navratil, Sorensen, Chenthamarakshan and Kambhatla2010), leading to individual local reorderings, being unaware of reorderings done elsewhere in the tree.

In Section 8 we report experiments both with the oracle systems and our own model. We show that the present source reordering model succeeds to obtain significant improvements over a strong baseline, yet this improvement is always only the lesser share of the potential improvement exhibited by the oracle counterparts. Following this, in Section 9, we analyze the effects of source reordering on the back end translation model by comparing the quality of its input, its phrase table, and its output to the standardly trained PBSMT baseline. We find that source reordering leads to larger phrase tables than the baseline with better coverage of phrases in held-out data, and that its potential improvement over standard PBSMT system remains largely untapped. Remarkably, tree-based source reordering (oracle as well as model) leads to larger phrase tables than the baselines that do not have better coverage, suggesting that tree-based source reordering leads to somewhat noisier phrase tables. Our main conclusion, Section 10, is that it might be worthwhile to invest in novel tree-based source reordering approaches that lead to phrase tables with better coverage of unseen phrases, because this is where source reordering may offer most of its added value over standard phrase-based systems.

2 Translation model baseline: phrase-based SMT

The baseline is a standard phrase-based SMT system based on Och and Ney (Reference Och and Ney2002) and Koehn et al. (Reference Koehn, Och and Marcu2003). The phrase-based model works with a table of statistics over phrase pairs acquired from word-aligned parallel data under a simple definition of translational equivalence (Zens et al. Reference Zens, Och and Ney2002). A bilingual phrase is any aligned pair of m source words and n target words that satisfies two basic constraints: (1) words are consecutive along both sides of the bilingual phrase, and (2) no word on either side of the phrase is aligned to a word outside the phrase (Och and Ney Reference Och and Ney2004). The conditional probabilities of one phrase given its counterpart are interpolated linearly together with a set of other model estimates:

(1)

where a feature function h _m refers to a system model, and the corresponding λ_m refers to the relative weight given to this model. A phrase-based system employs feature functions for a phrase pair translation model, a language model, a reordering model, and a model to score translation hypothesis according to length. The weights λ_m are usually optimized for system performance (Och Reference Och2003) as measured by bilingual evaluation understudy (BLEU) (Papineni et al. Reference Papineni, Roukos, Ward and Zhu2002).

Two phrase reordering methods are widely used in phrase-based systems. A distance-based reordering model provides the decoder with cost linear to the distance between words that are being reordered. This model constitutes the default for the Moses system (Koehn et al. Reference Koehn, Hoang, Birch, Callison-Burch, Federico, Bertoldi, Cowan, Shen, Moran, Zens, Dyer, Bojar, Constantin and Herbst2007). And, a lexicalized block-oriented data-driven reordering model (Tillman Reference Tillman2004) considers three orientations: monotone (M), swap (S), and discontinuous (D) (MSD), while the reordering probabilities are conditioned on the lexical context of each phrase pair.

3 Source reordering: framework

We start out from a word-aligned parallel corpus, consisting of triples 〈s,a,t〉, a source s, target t, and word alignment a. Source reordering assumes that a permutation of s, called , is first generated with a model P_r( | s) followed by a phrase translation model P_t(t | ). The desired permutation is one that has minimum word order divergence from t, i.e., the alignment of with t would contain the least number of crossing alignments. Figure 1 exhibits a reordering at string level that resolves the crossing alignments.

Fig. 1.

Example of Oracle string unfolding. (a) Original bilingual phrase; (b) reordered bilingual phrase.

Practically, the original parallel corpus {〈s,a,t〉} is split to two parallel corpora: (1) a source-to-permutation parallel corpus (consisting of 〈s, a, 〉), and (2) a permutation-to-target parallel corpus (consisting of 〈g , à, t〉), where g is the output of a source reordering model P_r( | s), and à results from automatically word aligning 〈g , t〉. The latter parallel corpus is used for training a phrase-based translation system P_t(t | g ), while the former corpus is used for training a source reordering model P_r( | s).

The problem of finding the optimal permutation of the source string is computationally intractable (see Tromble and Eisner Reference Tromble and Eisner2009). However, various constraints can be made on unfolding the crossing alignments in a. A common approach is to assume a binary parse tree for the source string, and define a set of eligible permutations by binary ITG transductions. This defines permutations resulting from at most inverting pairs of children under nodes of the source tree. Figure 2 exhibits a long-range reordering of verb in English-to-Dutch translation: Inverting the order of the children of the VP node would unfold the crossing alignment. However, crossing alignments represented as non-constituents cannot be resolved. This difficulty can be circumvented by employing multiple alternative parse trees, by applying heuristic transforms (e.g., binarization) to the tree to fit the alignments (Wang et al. Reference Wang, May, Knight and Marcu2010), or by defining new local transductions on top of child permutation (ITG).

Fig. 2.

Example of crossing alignments and long-distance reordering using a source parse tree.

4 Existing work on source reordering

As mentioned earlier, source reordering is but one of the existing approaches to deal with word order differences during translation. Alternatives include phrase reordering methods employed in phrase-based models (Zens and Ney Reference Zens and Ney2003; Tillman Reference Tillman2004; Koehn et al. Reference Koehn, Hoang, Birch, Callison-Burch, Federico, Bertoldi, Cowan, Shen, Moran, Zens, Dyer, Bojar, Constantin and Herbst2007), as well as hierarchical, syntax-augmented phrase-based systems often working with synchronous grammars (e.g., Wu Reference Wu1997; Galley et al. Reference Galley, Hopkins, Knight and Marcu2004; Zollmann and Venugopal Reference Zollmann and Venugopal2006; Chiang Reference Chiang2007; DeNeefe et al. Reference DeNeefe, Knight, Wang and Marcu2007; Mylonakis and Sima'an Reference Mylonakis and Sima'an2011).

Source reordering has been reported to be useful for PBSMT for a variety of language pairs with high mutual word order disparity (Xia and McCord Reference Xia and McCord2004; Collins et al. Reference Collins, Koehn and Kučerová2005; Costa-jussà and Fonollosa Reference Costa-jussà and Fonollosa2006; Popovic' and Ney Reference Popovic' and Ney2006; Li et al. Reference Li, Minghui, Zhang, Li, Zhou and Guan2007; Zwarts and Dras Reference Zwarts and Dras2007; Dyer and Resnik Reference Dyer and Resnik2010; Genzel Reference Genzel2010; Visweswariah et al. Reference Visweswariah, Navratil, Sorensen, Chenthamarakshan and Kambhatla2010).

A rather popular class of source-reordering algorithms involves syntactic information and aims at minimizing the need for reordering during translation by permuting the source sentence (Collins et al. Reference Collins, Koehn and Kučerová2005; Li et al. Reference Li, Minghui, Zhang, Li, Zhou and Guan2007; Wang et al. Reference Wang, Collins and Koehn2007; Zwarts and Dras Reference Zwarts and Dras2007; Genzel Reference Genzel2010; Khalilov and Sima'an Reference Khalilov and Sima'an2010). Some systems perform source permutation using a set of hand-crafted rules (Collins et al. Reference Collins, Koehn and Kučerová2005; Wang et al. Reference Wang, Collins and Koehn2007; Ramanathan et al. Reference Ramanathan, Bhattacharyya, Hegde, Shah and Sasikumar2008; Isozaki et al. Reference Isozaki, Sudoh, Tsukada and Duh2010), others make use of automatically learned reordering patterns extracted from the plain training data, the corresponding parse or dependency trees, and the alignment matrix (Li et al. Reference Li, Minghui, Zhang, Li, Zhou and Guan2007; Dyer and Resnik Reference Dyer and Resnik2010; Genzel Reference Genzel2010; PVS Reference PVS2010; Visweswariah et al. Reference Visweswariah, Navratil, Sorensen, Chenthamarakshan and Kambhatla2010; Khalilov and Sima'an Reference Khalilov and Sima'an2011; Mylonakis and Sima'an Reference Mylonakis and Sima'an2011). While the majority of systems operate on the source side of parallel corpus, there has been some algorithms that require access to source and target tree banks (Xia and McCord Reference Xia and McCord2004; Khalilov Reference Khalilov2009). Only a few models (Visweswariah et al. Reference Visweswariah, Rajkumar, Gandhe, Ramanathan and Navratil2011) work non-hierarchically at the word alignment level.

Following Li et al. (Reference Li, Minghui, Zhang, Li, Zhou and Guan2007), Tromble and Eisner (Reference Tromble and Eisner2009), Genzel (Reference Genzel2010), and Khalilov and Sima'an (Reference Khalilov and Sima'an2010), in this work source reordering is viewed as a word permutation learning problem. The space of permutations is approached efficiently using a binary ITG-like synchronous context-free grammar put on the parallel data. Similarly, a local ITG-based tree transducer with contextual conditioning is used in Li et al. (Reference Li, Minghui, Zhang, Li, Zhou and Guan2007) and Khalilov and Sima'an (Reference Khalilov and Sima'an2010), and preliminary experiments on a single language pair show improved performance. The latter two are limited to ITG-like permutations, employ limited context conditioning, and are explored either on small training data or on a single language pair. Particularly, the model in Li et al. (Reference Li, Minghui, Zhang, Li, Zhou and Guan2007) is explicitly aimed at long-distance reorderings (English–Chinese), prunes the alignment matrix gradually to fit the source syntactic parse, and employs Maximum-Entropy modeling to choose the optimal local ITG-like permutation step of sister subtrees but interleaves that step with a translation step. The latter property implies that Li et al. (Reference Li, Minghui, Zhang, Li, Zhou and Guan2007) has a unique status because it lies somewhere between pure source reordering and models that conduct reordering dynamically during decoding. Apart from this major difference, the model presented in Section 7 differs substantially from Li et al. (Reference Li, Minghui, Zhang, Li, Zhou and Guan2007) and other earlier work because it (1) incorporates other kinds of tree transduction operations than those promoted by ITG, and (2) works with the unmodified alignment matrix but learns reorderings only from those alignments that are consistent with the tree, thereby avoiding the effects of heuristics for pruning alignments to fit the tree structure (e.g., Li et al. (Reference Li, Minghui, Zhang, Li, Zhou and Guan2007)). These properties allow us to study and analyze source reordering with/without syntax using a reasonably clean but well-equipped transduction model.

Source reordering is learned over binary synchronous trees in DeNero and Uszkoreit (Reference DeNero and Uszkoreit2011) and pipe-lined with a phrase-based SMT system. The reordering model learns a binary choice over all binary trees that fit with word alignment independently from one another. Learning binary synchronous trees for reordering as independent local binary decisions contrasts with our choice for syntactic trees for learning a cascade of local context-dependent source reorderings.

An elegant approach is described in Dyer and Resnik (Reference Dyer and Resnik2010), where the source reordering derivations (s → ) constitute a latent component modeled by local child-order permutation under the nodes of a source syntactic tree. The reordering parameters are defined over individual context-free grammar (CFG) productions in these derivations without context and cast together with the standard translation model parameters in a log-linear interpolation, estimated by maximizing the posterior probability. The fact that the child-order permutations are cast as a CFG, contrasts sharply with our use of reordering patterns collected from the training data and applied as individual transducers. While the translation model in Dyer and Resnik (Reference Dyer and Resnik2010) is used during training the latent source reordering model parameters, the parameters of the two models are formulated independently of each other.

A large majority of existing works report encouraging performance improvements by source reordering but none tries to quantify the range of potential improvements with/without syntax-based reordering, and none provides an analysis of why it sometimes fails to return the expected performance improvements. The present paper constitutes a harmonized, significantly extended write-up of the work described in Khalilov and Sima'an (Reference Khalilov and Sima'an2011). The latter publication briefly and informally presents oracle results and the source reordering model (Section 7). In the present paper we concentrate on a novel empirical study and analysis of statistical translation after source reordering with fresh insights into the potential weaknesses of syntax-driven source reordering before translation.

5 Data and experimental setting

5.2 Experimental setting

Data. In our experiments we used English–Dutch and English–Spanish European Parliament data and an extraction from the English–Chinese Hong Kong Parallel Corpus. All the sets were provided with one reference translation. Basic statistics of the training, development, and test data can be found in Table 1.

Table 1.

Statistics of the training, development and test corpora

Experimental setup. The word alignment was obtained by running GIZA++Footnote ¹ (Och Reference Och2003), supported by mkclsFootnote ² (Och Reference Och1999) tool. All phrase translation systems in this paper (including the back-end systems for oracle and source reordering) are trained on word alignments obtained by the grow-diag-final-and heuristic for symmetrizing alignments produced from both translation directions (cf. Och and Ney Reference Och and Ney2003). The source reordering models (before translation) are trained on simplified word alignments as explained in relevant sections.

The PBSMT system that we consider in this study employs Moses toolkit (Koehn et al. Reference Koehn, Hoang, Birch, Callison-Burch, Federico, Bertoldi, Cowan, Shen, Moran, Zens, Dyer, Bojar, Constantin and Herbst2007). We followed the guidelines provided on the Moses web pageFootnote ³ to train and use the system.

All language models were trained with SRI LM toolkit (Stolcke Reference Stolcke2002). Target-side language models (for Dutch, Spanish, and Chinese) use 5-grams, while the idealized English () is modeled using 3-grams.

We use Stanford parserFootnote ⁴ (Klein and Manning Reference Klein and Manning2003) as a source-side parsing engine. The parser was trained on the WSJ Penn treebank (Marcus, Santorini and Marcinkiewicz Reference Marcus, Santorini and Marcinkiewicz1993) provided with fourteen syntactic categories and forty-eight part-of-speech (POS) tags. The evaluation conditions were case-sensitive and included punctuation marks. For Maximum-Entropy modeling we used the maxent toolkitFootnote ⁵.

6 Idealized source reordering: oracles

Work on source reordering for PBSMT reports that permuting the source words to minimize the order differences with the target sentence could improve translation performance. The reported improvements often vary considerably, both due to language pair and choice of source reordering approach. In this section we attempt gaging the performance improvement of various idealized (oracle) source reordering systems. The oracle task is simply to perform unfolding operations on the crossing links in alignment a (estimated between corpora s and t) that leads to as monotone alignment à as possible. We introduce a set of tree-based constraints that control the unfolding of alignment crossings. We measure the impact of (un)folded alignment crossings on the final performance of the PBSMT system (see Table 2). In Section 9 we analyze the impact of these oracles on the subsequent translation system.

Table 2.

Summary of oracle results

6.1 Oracle models

The oracle models discussed here are greedy in nature in that they execute a sequence of local reordering operations unfolding crossing alignments in a given word alignment. It is possible to generalize this greedy approach into a dynamic search-based approach by defining a figure-of-merit for every possible sequence of local reorderings based on independent, local figures-of-merit (cf. Tromble and Eisner Reference Tromble and Eisner2009). The definition of an adequate, decomposable figure-of-merit, particularly for tree-based systems, is difficult and will necessarily involve other kinds of simplifying assumptions.

Crucially, the word alignments used for preparing the source-permuted strings for oracles are obtained using Giza++ with intersection heuristic. In contrast, the translation systems, including all back-end models for source reordering, are trained on word alignments obtained by Giza++ with the grow-diag-final-and heuristic.

Oracle string. The objective that this algorithm optimizes is to obtain the source permutation that unfolds all crossing alignments in a, the alignment between source and target strings. This algorithm (Oracle string) traverses the alignment a from left-to-right and for each crossing link it comes across, it moves the source word involved in the crossing to the nearest source position that unfolds that crossing. Figure 3 shows the pseudo-code for this algorithm. The pseudo-code produces the permutation of s that contains no crossing alignments. Figure 1 shows an example of word reordering done at the string level.

Fig. 3.

Pseudo code Oracle string. The algorithm creates the permutation by resolving crossing alignments in a. A triple 〈i ₀, j, i_n〉 in à consists of the original source position i ₀ for word w _{i 0}, the aligned target position j, and the current source position i_n for word w _{i 0}. The wild-card * in a triple stands for ‘any existing value’ and is used when the value is irrelevant at that point.

Oracle parse tree with permute siblings. The oracle tree system employs a source syntactic tree τ to constrain Oracle string. Let the current crossing alignment pair with source side positions be given by i and k (underlined in Figure 3). Let the current parse tree at the mth step of this algorithm be τ^m, obtained after m preceding steps and initialized at the beginning with τ₀ = τ. Having a crossing alignment in hand, we search bottom-up in τ_m for the largest subtreeFootnote ⁶ with root address μ that fulfills the following three requirements:

1. (R1) Node μ covers both positions i and k,

2. (R2) The crossing alignment given by source-sides i and k can be resolved by permuting the positions of the child nodes of μ, and

3. (R3) Swapping the positions of these child nodes does not introduce new crossing alignments.

If and when a suitable node μ is found, this oracle unfolds this crossing alignment pair by conducting swapping in τ_m leading to a new parse tree τ_m+1, else the alignment crossing is skipped to the next one and τ_m+1 is equivalent to τ_m. In practice this adds a constraint on unfolding steps (1)–(3) in Oracle string (Figure 3). NULL-aligned words do not prevent unfolding crossings because we include them with the adjacent words that are involved in the crossings. We call this configuration Oracle tree.

Figure 2 shows an example. According to the Oracle tree constraint, the word ‘went’ can be placed in the end of the sentence, since the replacement can be done as a swapping of ‘VBP’ and ‘PP’ categories. The same happens for the word ‘reflect’ swapping with ‘S’ constituent in Figure 2, but not for the chunks ‘the positions’ and ‘not properly’: This crossing cannot be resolved under the tree constraint, since they are not dominated by sibling syntactic categories.

Oracle tree with delete descendants, permute siblings. This oracle implements an additional mechanism of tree modification to increase the number of reordering permutations in comparison with Oracle tree algorithm. Here we allow for a tree transduction operation that deletes a maximum number d of intervening node layers in the source tree before applying sibling permutation as in Oracle tree. This oracle can be seen as an attempt to bridge the difference between unconstrained string-level and tree-constrained unfolding of crossing alignments. Tree layers that intervene between a crossing alignment pair are removed to relax tree constraints.

This algorithm consists of a single refinement when the three requirements (R1, R2, and R3) of Oracle tree above are not fulfilled. If these requirements are not fulfilled by any node μ in τ_m, then this algorithm enters a loop for deleting the smallest number of layers (at most d) before attempting to unfold the alignment crossing by standard permute siblings as in Oracle tree. At every round in this loop it conducts two steps:

1. (1) Seek the smallest subtree covering both source sides of the alignment crossing pair (with source side i and k in Figure 3). Let the root of this subtree have address μ_p, and suppose the address of the child node that covers source side positions i and k are μ_p^l and μ_p^r, respectively.

2. (2) For each μ_p^x ∈ {μ_p^l, μ_p^r} if the alignments covered by the subtree under μ_p^x do not consist of a contiguous span (i.e., block) on the target side, then node μ_p^x is deleted from τ_m and the child subtrees of μ_p^x are pulled up to become the direct children of μ_p, leading to tree . When this deletion has been attempted/done for both child nodes, the number of deleted layers is incremented by one.

If the Oracle tree still cannot be applied to resolve the current alignment crossing by permuting the children of μ_p after the deletion, then the loop is re-entered to attempt deleting another layer from . If the crossing alignment at hand is resolved, the algorithm continues to the next one with the modified tree (after all deletions and permute-siblings) renamed as the current tree τ_m+1, otherwise it proceeds to treat the next crossing alignment with the trees obtained after deletions as the current tree τ_m+1.

This oracle is illustrated in Figure 4. The word ‘must’ cannot be moved to the beginning of the sentence in Figure 4(a) by Oracle tree. Instead, this is done in two steps. Firstly, the VP dominating the words ‘must’ and ‘apply’ (a node dominating a source side with a non-contiguous target side) is deleted under the current node S (the root of the smallest subtree dominating the crossing alignments), the transformed tree is shown in Figure 4(b). Subsequently, the siblings under S in the resulting tree are permuted, ‘must’ is reordered across the whole clause and placed to the first position (see Figure 4(c)). We call this system Oracle mod. Figure 5 shows an example in which crossing alignment links cannot be unfolded without deleting four intervening layers.

Fig. 4.

Example of text monotonization with tree transformation. (a) Original parse tree; (b) parse tree with deleted VP category; (c) reordered parse tree.

Fig. 5.

Example of unfoldable alignment crossings.

7 A Statistical model of syntactic tree transduction

We now present a model that learns from the source permuted parallel corpus (containing tuples 〈s, a, 〉) a probabilistic optimization (arg max_π(s)P_r(π(s) | s, τs)), where τs is the source parse and π(s) is some eligible permutation of s. We view the permutations leading from s to as a sequence of local tree transductions τ₀ → . . . → τ_n, where ₀ = s and _n = , and each transduction τ_i−1 → τ_i is defined using any of the two kinds of local tree transduction operations (explained next, but see also Section 6) or alternatively no operation (NOP).

Theoretically speaking, we can define the probability of the sequence of local tree transductions τ₀ → . . . → τ_n as

(2)

The latter Markov approximation seems reasonable because the preceding tree τ_i−1 is the result of all preceding transductions, thereby summarizing the changes but forgetting exact transductions leading to these changes. This definition deviates from the majority of earlier works, e.g., Tromble and Eisner (Reference Tromble and Eisner2009) and Visweswariah et al. (Reference Visweswariah, Navratil, Sorensen, Chenthamarakshan and Kambhatla2010), which defines 0th-order Markov models where every transduction step is independent from preceding transductions. The work in Li et al. (Reference Li, Minghui, Zhang, Li, Zhou and Guan2007) presents a model that conditions ITG-like transductions on local context, but that model conducts a recursive process over the parse tree that involves a single reordering and single translation step. Our model conducts full source reordering before actual translation starts.

The Markov conditioning makes the optimization , over an interesting space like that defined by ITG, intractable. Observe that the sequence of transductions can be represented compactly as a sequence of parse-forests, one parse-forest for each i=1. . . x. However, the conditioning P(τ_i | τ_i−1) implies that every tree in forest i is conditioned on a tree in forest i−1. If the number of trees in every forest is guaranteed to be linear in input length n, the optimization will cost n^x. Reasonably (avoiding transduction cycles), the number of transductions x could be linear in n, leading to time-complexity O(nⁿ). Earlier work (e.g., Tromble and Eisner Reference Tromble and Eisner2009; Visweswariah et al. Reference Visweswariah, Navratil, Sorensen, Chenthamarakshan and Kambhatla2010) avoids the conditioning context altogether, effectively assuming that each intermediate permutation is independent from the preceding ones. Next we make a different approximation that retains the conditioning context of each local transduction but gives up on the global optimization over whole transduction derivations.

Algorithm. Initially all nodes in the source tree τ₀ are marked as unvisited. Our algorithm (see Figure 6) takes the next unvisited node with address μ in a top-down, left-to-right (pre-order) tree traversal of the current tree τ_i−1, marks this node as visited and then statistically selects the most likely of three transduction operations (defined next), and applies the selected operation to the current node. Note that our operations reord child nodes and could delete certain nodes, and hence the nodes marked visited remain as such (or are deleted) during the transduction sequence to avoid revisiting them.

Fig. 6.

General pseudo-code for the described model (MERrd[+xlt]). The function FRINGE returns the ordered sequences of terminals (words) at the leaf nodes (the fringe) of the input tree. Function APPLY.OPERATION applies the statistical MaxEnt-trained conditional probability selector to select the most likely operation (Perm, Del-Perm, NOP) for input node μ in tree τ_i.

Let the current tree be τ_i−1 and let the current node has address x, syntactic label N_x, and directly dominate α_x (the ordered sequence of node labels under x). We optimize the conditional probability of the transduction operation it employs over the following kinds of operations, beside NOP:

Perm Permutes the children of x in τ_i−1 with probability

(3)

where π(α_x) is a permutation of α_x (the ordered sequence of node labels under x) and C_x is a local tree context of node x in tree τ_s'i−1. Effectively, we employ a context-sensitive tree-rewrite rule: if C_x then .

Del-Perm Select a child of x to delete, pull its children up directly under x, effectively changing α_x to some α_x^d, and then permute the children of the latter,

(4)

where symbolizes the result of deleting a subtree under a child of x. This operation is also extended to subtrees of depth n ∈ {1,2,3,5} under x, i.e., a child is depth 1, a child with its children is depth 2, and so on. Effectively, we employ a sequence of two context-sensitive tree-rewrite rules (1) if C_x then followed by (2) if C_x then .

Obviously, the number of possible permutations of α_x is factorial in the length of α_x. Fortunately, the source-permuted training data exhibits only a fraction of possible permutations even for longer α_x sequences. Furthermore, by conditioning probability on local context C_x, the number of permutations is limited to a handful set. By limiting the space of permutations in this fashion, however, our tree-based models are more vulnerable to the sparsity of local permutations and their contexts in the training data.

Now that we optimize the choice for each transduction on its own in a derivation, we cannot anymore guarantee that the full derivation will lead to good source reordering. Particularly, we risk making locally optimal choices but globally suboptimal ones. We alleviate this by choosing individual transductions that lead to improved permutations both at the tree- and string-levels. We interpolate the terms in (3) and (4) with probability ratios of the idealized (desired) source-reordered language model P_lm:

where TRANS_i is any of the two transduction operations or NOP, and P_lm is a language model trained on the side of the corpus {〈s, a, 〉} (trained over strings obtained by resolving cross alignments). Optimizing this interpolation can be interpreted as optimizing the optimal permutation that can serve as input for a subsequent translation model among those that have good tree transductions. The language model ratio can be seen as one factor in the log-linear modelFootnote ⁷, incorporating lexical features from windows of lexical context left and right of the subtree under the current node in the tree before the transduction is applied as well as in the tree resulting from the transduction.

Estimates and features. We estimate the string probabilities P_lm(.) using 3-gram language models trained on the side of the source-permuted parallel corpus {〈s, a, 〉}. We estimate the conditional probability P_r(TRANS | N_x → α_x, C_x) using a Maximum-Entropy framework, where feature functions are defined to capture the permutation as a class, the node label N_x and its head POS tag, the child sequence α_x together with the corresponding sequence of head POS tags and other features corresponding to different contextual informationFootnote ⁸.

We collect the following set of fifteen features by using the corresponding tree-based Oracle traversals (Section 6) of the alignments in the training data:

• • Local tree topology. Subtree instances that include parent node and the ordered sequence of child node labels (1).

• • Dependency features. Features that determine the POS tag of the head word of the current node (2), together with the sequence of POS tags of the head words of its child nodes (3), the POS tag of the head word of the parent (4), and grandparent nodes (5).

• • Syntactic features. Apart from the whole path from the current node to the tree root node (6), we used three binary features from this class: (7) whether the parent node is a child of the node annotated with the same syntactic category, (8) whether the parent node is a descendant of the node annotated with the same syntactic category, and (9) if the current subtree is embedded into a ‘S-SBAR’ subtreeFootnote ⁹.

• • POS lexical features. Bi- and tri-grams of POS tags of the left- and right-hand sides neighboring words (10–13).

• • Counters. A number of words covered by a given constituent (14) and a number of children of the given node (15).

8 Translation and reordering experiments

We use exactly the same data and experimental setting used for the oracle experiments described in Section 6. For all systems and experiments in the sequel we employ a PBSMT back-end system that works both with lexicalized phrase reordering and the MSD reordering (see Section 2 for details).

The word alignments used for preparing the source-permuted strings for training our own models are obtained by disambiguating the alignments obtained from Giza++ followed by the grow-diag-final-and symmetrization heuristic. The disambiguation aims at resolving many-to-one or one-to-many alignments leaving only one-to-one alignments and unaligned words. The disambiguation selects among one-to-many and many-to-one alignment links for the same word only the single link with the highest score according to the lexical probability model obtained from training with Giza++.Footnote ¹⁰ As mentioned earlier, all translation systems, including the back-end models for source reordering, are trained on word alignments obtained by Giza++ with the grow-diag-final-and heuristic.

System names. MERrd configuration corresponds to the PBSMT system with the source side of the parallel corpus reordered using the present Maximum Entropy source reordering model, but the transduction operations are limited to permuting the children only. MERrd+xlt configuration refers to the set of systems which, beside child permutation, includes a deletion operation with the maximum number of tree layers that can be deleted set to x. All reordered systems include an MSD model as a supporting reordering mechanism.

Translation results. Table 3 shows the results of automatic evaluation using BLEU and NIST (Doddington Reference Doddington2002) metrics. BLEU scores measured on the test data, which are statistically significant from the best PBSMT results, are marked with bold. The statistical significance calculationsFootnote ¹¹ have been done for a 95% confidence interval and 1000 re-samples, following the guidelines in Koehn (Reference Koehn2004).

Table 3.

Experimental results

Discussion. Our results show that source-reordering is beneficial for language pairs with high mutual word order disparity. In contrast to English–Dutch and English–Chinese translation tasks, the statistical significance test reveals that all but the MERrd+5lt English–Spanish PBSMT system with rearranged input are not different from the translation quality delivered by Moses. This disappointing result for the English-to-Spanish translation task may be explained by the fact that many reordering differences are resolved by standard reordering models (distance-based and MSD).

A gap between the maximum reachable performance shown by tree transduction systems and the translation quality delivered by our model is 0.05–0.29 BLEU points for English–Dutch, 0.01–0.09 for English–Spanish, and 0.27–0.76 for English–Chinese. These numbers demonstrate that there are some potentially usable regularities not captured by our current conditional tree-transduction model.

9 Analysis of translation after source reordering

So far, our oracle and system experiments warrant two conclusions:

• • Oracle string source-reordered systems offer a large improvement potential over standard PBSMT. Oracle tree-constrained systems offer only a small part of this potential.

• • Our own tree-based source reordering PBSMT model variations do improve over standard PBSMT, albeit the improvement does not exploit the full potential improvement offered by tree-based source reordering shown by the oracles.

In this section we analyze the quality of the reordering mechanism, and concentrate on its impact on the robustness and adequacy of the translation model. We study three possible explanations for the gap between tree-based systems, Oracle string, and standard PBSMT:

1. H1 A source reordering approach may or may not lead to improved word order prior to translation. Our hypothesis here is that tree-based source reordering does improve source word order when measured against the output of Oracle string as gold standard, and that the ranking in improved source reordering is predictive of final translation quality.

2. H2 The back-end translation system employs a phrase-table extracted from the source-reordered strings to target sentences: the hypothesis is that the phrase-table quality improves due to (tree-based) source reordering. We need effective measures of quality that may explain differences of performance between various kinds of source reordering systems defined in this paper.

3. H3 Source reordering improves the lexical choice in the output of the full system.

We concentrate on the English-to-Dutch and English-to-Spanish translation tasks and the systems developed for them. All oracles as well as tree-based transduction systems work with a back-end phrase-based translation system enhanced with lexicalized and MSD reordering. Our study is structured in three parts corresponding to the input (H1), phrase table (H2), and output (H3) of the translation model applied after source reordering.

9.1 Input: assessing permutation quality before translation

To measure the quality of reordering performance in the output of the reordering module (input of the translation system), we use the LRscore metric (Birch and Osborne Reference Birch and Osborne2010), which scores the difference in word order between two datasets balanced by a lexical componentFootnote ¹². The LRscore averages over all pairs of a candidate translation t and its reference translation r in a test set of length N (number of segments):

(5)

where R(r, t) = d(r, t) * BP(r, t) is the reordering metric dependent on the Hamming distance d(r, t) and the brevity penalty BP(r, t) defined as

with |x| denoting the length of every string x in words.

As a word order gold standard we used the Oracle string output, which constitutes the source permutation that contains the smallest number of crossing alignments with the target sentence.

The results of reordering quality evaluation for two language pairs can be found in Table 4. For both language pairs, the source without pre-processing (input to PBSMT) has the lowest LRscore, whereas Oracle mod + 5lt has the highest possible LRscore (closest to Oracle string). Clearly, the potential space for gain for source reordering over PBSMT for English–Spanish (with 93.20% for PBSMT) is about one-fourth of that for English–Dutch (with 72.64% for PBSMT). The difference between Oracle mod+5lt and PBSMT is about 10 points for English–Dutch, with the Oracle mod+5lt closing approximately only one-third of the gap between the input of PBSMT and that of Oracle string. This difference is far smaller for English–Spanish, with Oracle mod+5lt closing less than 10% of the gap between the input of PBSMT and that of Oracle string.

Table 4.

LRscore as a measure of reordering success for two language pairs

Regarding hypothesis H1, we conclude that tree-based source reordering does have the potential to improve source order but cannot bridge the lion's share with the gold standard Oracle string. Hence, limited source reordering is one reason that Oracle tree systems offer limited performance gain.

9.2 Phrase table quality measures

Now we study the impact of source reordering on the phrase table (hypothesis H2). We concentrate on two indicators: phrase table size and phrase table coverage on held out sets. The first measures increase in diversity of phrase pairs, whereas the second measures whether the increase is useful in covering unseen input of the same kind.

Phrase table size and coverage. Table 5 contrasts the number of phrases extracted from the corpus with reordered and monotone source parts. Clearly, all source-reordered systems have larger phrase tables, with increase in size approximately predicting improved translation performance (see Table 3). The phrase pair extraction method underlying phrase-based translation has the property that more monotone the word alignment in the training parallel data is, more phrase pairs can be extracted. Yet, beside monotonization, phrase tables size may increase due to inconsistent alignments or reorderings (noise). Hence, next we directly measure the coverage of the phrase table on held-out data. We observe the percentage of phrases from held-out datasets that are covered by the primaryFootnote ¹³ phrase table. Our assumption was that the source reordering will create more monotone alignments in training data allowing more and longer phrases, and hence possibly better coverage of phrases in unseen data.

Table 5.

Size of phrase tables for English-to-Dutch system (millions of instances)

For all systems, phrase coverage was measured by averaging over the same ten-fold, independent random partitioning of the training corpus into a held-out and an extraction set as follows. For each i∈[1. .10] the following three steps were conducted: (1) A 1K-line held-out partition Φ_i is randomly extracted and the remaining part is called Φ^C_i; (2) a pair of multi-sets of bilingual phrases is extracted, one (called H_i) from the held-out partition Φ_i and another (E_i) from Φ^C_i; and (3) two coverage scores were calculated: the coverage of phrase-types (called Cov. uniq) is calculated as the ratio , where H^s and E^s are the sets underlying the corresponding multi-sets, and the frequency-weighted coverage of phrases (called Cov.) given by .Footnote ¹⁴Table 6 reports both coverage scores averaged over ten partitions for English–Dutch and English–Spanish.

Table 6.

Coverage of phrase types (Cov. uniq.) and tokens (weighted by frequency – Cov.) averaged over ten-fold held-out sets

Clearly, Oracle string improves the coverage of the phrase table (types and frequency-weighted). The disappointing coverage (both phrase type and frequency-weighted) of Oracle tree for both language pairs is illuminating: this system acquires many more phrase types (Table 5) but has lower coverage than PBSMT. The Oracle mod systems have improved phrase-type coverage (Cov. uniq) even relative to PBSMT, but cannot bridge more than a small fraction of difference between Oracle string and PBSMT. It is interesting to note that the Cov. (frequency-weighted coverage) is lower than the PBSMT coverage almost for all tree-based systems. This suggests that phrase-type coverage is improved mainly for phrase-types expected to occur infrequently but might have decreased for phrase-types expected to occur frequently, with the likely situation that the added phrases are noise.

We conclude here that tree-based systems lead to larger phrase tables that hardly have any improved coverage which supports the hypothesis that these systems' phrase-based translation model suffers somewhat from the tree-based source reordering. For the phrase-based model, tree-based source reordering creates more noisy alignments in the training data. This is, however, counter balanced by resolving long-distance reorderings, which explains the final translation improvement over PBSMT.

9.3 Output: effect of source reordering on final lexical choice

We now focus on the output of translation systems. We would like to know how lexical choice varies as the source reordering varies. It is conceivable that changing the source order lead to different phrase pairs and hence offer the target language model other options to choose from. While the lexical choice is certainly a part of BLEU scores, here we look at other complementary measures that we can interpret by neutralizing the word order differences.

Instead of BLEU1 (bag of words BLEU), we calculate the precision, recall, and F1 of the output quality in terms of lexical choice. We consider both the output sentences of a given system as well as the corresponding reference translations as bags of word tokens and consider the intersection between these two bags of word tokens for defining

(6)

(7)

where C_ov is the total number of word tokens across the test corpus that are in the intersection of the MT system output and the human reference translations (as bags of words), C_transl is the total number of word tokens in the translation system output, and C_ref is the total number of words in the reference translations.

The results can be found in Table 7. The results of all systems are largely comparable, supporting the conclusion that source reordering only marginally impacts the system's lexical choice, i.e., its impact concentrates on improved reordering of the output.

Table 7.

Lexical precision/recall and F-measure analysis of MT output

9.4 Discussion

In the background of our analysis we had the following conclusion from Section 6: Source reordering has large potential for performance improvement if source permutation is unlimited, but when limited by the simple tree-based reordering only a fraction of the potential remains. The empirical analysis so far sheds light on why this is the case. Following is the summary:

• • Tree-based source reordering manages to arrive at a closer word order to the gold standard Oracle string (virtually target order) than the original source sentence. However, measured using the LRscore metric (Birch and Osborne Reference Birch and Osborne2010), the best tree-based reordering only covers one-third of the LRscore gap between original sentence and oracle string reordered sentence. This is one explanation for the limited potential of the tree-based oracles relative to the Oracle string.

• • Source-reordering leads to larger phrase tables. For Oracle string this increase leads to substantial increase in coverage of unseen phrase pairs in held-out input (about 25% for English–Dutch and 12% for English–Spanish). For the tree-based oracle, the phrase tables are larger but there is hardly any coverage improvement over the PBSMT table, suggesting that the size increase is mainly due to somewhat arbitrary source reordering (looking at that from the string, phrase-based level).

• • Source reordering hardly impacts lexical selection in the translation system output.

Together these findings refine the common wisdom that tree-based source reordering constrains the space of source permutations in effective and thus harmless ways. Indeed, tree-based source reordering can deal with long-range reorderings that the baseline PBSMT system cannot deal with. But because tree-based reordering follows the constituency structure and adheres to the limitations of reordering the sister branches, it could conduct selective/noisy source reordering at the string level that sometimes may cancel the benefits of source reordering. The latter does not necessarily imply that tree-based reordering is problematic per se, but that its combination with a PBSMT back-end system is fraught with certain difficulties.

The lack of improvement in lexical choice in translation output may look expected. We think that this hints at the fact that in source reordering (as a pre-processing component to a phrase-based MT model) the lexical choice is rigidly conditioned on the choice of source reordering. This is because a single permutation is input to the translation model. It might be better to input a distribution of possible source permutations to the translation model.

Along the way we also suggested that the LRscore metric (Birch and Osborne Reference Birch and Osborne2010), when combined with phrase table coverage, is a reasonably good predictor of the system's reordering capabilities and its final translation performance (in BLEU). Figures 7(a) and (b) show plots of the BLEU score against LRscore and expected phrase Coverage. A reasonable interpretation of these plots is that the relative BLEU score change (increase/decrease) can be reasonably predicted from a suitable combination of LRscore and Coverage. This combination of performance predictors could save system development time because it avoids system optimization time (Minimum Error-Rate Training) and actual translation. How to conduct such a combination most effectively is left as a topic for future research.

Fig. 7.

Plots of final BLEU scores against the corresponding LRscores and expected phrase coverage. (a) English–Spanish systems; (b) English–Dutch systems.

Finally, it is important to stress the particular limitations of this study when interpreting the empirical findings. Our experiments are based on automatically generated word alignments and parse trees, which are far from ideal. Our oracle results suggest that the quality of word alignments is sufficient to allow for performance improvement over the baseline PBSMT system. The quality of parser output and the potential mismatch between monolingual constituency boundaries and phrase pair boundaries could be a more serious limitation, however. It can be interesting to compare the results shown by translation and reordering systems based on automatically generated alignments with the ones using manual word alignments in the same spirit as it is done in DeNero and Uszkoreit (Reference DeNero and Uszkoreit2011).

The greedy tree-based (oracle) systems reflect a dominant section of current practice in studying source reordering. We suspect that the limitations of these greedy tree-based source reordering systems will also hold for more optimally trained tree-based systems, i.e., those that work with global search for reordering sequences over the source parse. Our findings should be seen to highlight the need for a more robust syntax-sensitive source reordering approach than an approach based on local transduction operations over a constituency tree output by a source language parser.