A Unified Model for Soft Linguistic Reordering Constraints
in Statistical Machine Translation

Reordering models in statistical machine translation (SMT) model the word order difference when translating from one language to another. The popular distortion or lexicalized reordering models in phrase-based SMT make good local predictions by focusing on reordering on word level, while the synchronous context free grammars in hierarchical phrase-based (HPB) translation models are capable of handling non-local reordering on the translation phrase level. However, reordering, especially without any help of external knowledge, remains a great challenge because an accurate reordering is usually beyond these word level or translation phrase level reordering models’ ability. In addition, often these translation models fail to respect linguistically-motivated syntax and semantics. As a result, they tend to produce translations containing both syntactic and semantic reordering confusions. In this paper our goal is to take advantage of syntactic and semantic parsing to improve translation quality. Rather than introducing reordering models on either the word level or the translation phrase level, we propose a unified approach to modeling reordering on the linguistic unit level, e.g., syntactic constituents and semantic roles. The reordering unit falls into multiple granularities, from single words to more complex constituents and semantic roles, and often crosses translation phrases. To show the effectiveness of our reordering models, we integrate both syntactic constituent reordering models and semantic role reordering models into a state-of-the-art HPB system [4, 7]. We further contrast it with a stronger baseline, already including fine-grained soft syntactic constraint features [24, 3]. The general ideas, however, are applicable to other translation models, e.g., phrase-based model, as well.

Our syntactic constituent reordering model considers context free grammar (CFG) rules in the source language and predicts the reordering of their elements on the target side, using word alignment information. Due to the fact that a constituent, especially a long one, usually maps into multiple discontinuous blocks in the target language, there is more than one way to describe the monotonicity or swapping patterns; we therefore design two reordering models: one is based on the leftmost aligned target word and the other based on the rightmost target word.

While recently there has also been some encouraging work on incorporating semantic structure (or, more specifically, predicate-argument structure: PAS) reordering in SMT, it is still an open question whether semantic structure reordering strongly overlaps with syntactic structure reordering, since the semantic structure is closely tied to syntax. To this end, we employ the same reordering framework as syntactic constituent reordering and focus on semantic roles in a PAS. We then analyze the differences between the syntactic and semantic features.

The contributions of this paper include the following:

• •

  We introduce novel soft reordering constraints, using syntactic constituents or semantic roles, composed over word alignment information in translation rules used during decoding time;

• •

  We introduce a unified framework to incorporate syntactic and semantic reordering constraints;

• •

  We provide a detailed analysis providing insight into why the semantic reordering model is significantly less effective when syntactic reordering features are also present.

The rest of the paper is organized as follows. Section 2 provides an overview of HPB translation model. Section 3 describes the details of our unified reordering models. Section 4 gives our experimental results and Section 5 discusses the behavior difference between syntactic constituent reordering and semantic role reordering. Section 6 reviews related work and, finally Section 7 concludes the paper.

In HPB models [4], synchronous rules take the form $X\to ⟨\gamma ,\alpha ,\sim ⟩$, where $X$ is the non-terminal symbol, $\gamma$ and $\alpha$ are strings of lexical items and non-terminals in the source and target side, respectively, and $\sim$ indicates the one-to-one correspondence between non-terminals in $\gamma$ and $\alpha$. Each such rule is associated with a set of translation model features $\left\{{\varphi }_i\right\}$, such as phrase translation probability $p(\alpha \mid \gamma )$ and its inverse $p(\gamma \mid \alpha )$, the lexical translation probability $p_{lex}(\alpha \mid \gamma )$ and its inverse $p_{lex}(\gamma \mid \alpha )$, and a rule penalty that affects preference for longer or shorter derivations. Two other widely used features are a target language model feature and a target word penalty.

Given a derivation $d$, its translation log-probability is estimated as:

where ${\lambda }_i$ is the corresponding weight of feature ${\varphi }_i$. See [4] for more details.

As mentioned earlier, the linguistic reordering unit is the syntactic constituent for syntactic reordering, and the semantic role for semantic reordering. The syntactic reordering model takes a CFG rule (e.g., $\text{VP}\to \text{VP}\text{PP}\text{PP}$) and models the reordering of the constituents on the left hand side by examining their translation or visit order according to the target language. For the semantic reordering model, it takes a PAS and models its reordering on the target side. Figure 1 shows an example of a PAS where the predicate (Pre) has two core arguments (A0 and A1) and one adjunct (TMP). Note that we refer all core arguments, adjuncts, and predicates as semantic roles; thus we say the PAS in Figure 1 has 4 roles. According to the annotation principles in (Chinese) PropBank [28, 42], all the roles in a PAS map to a corresponding constituent in the parse tree, and these constituents (e.g., NPs and VBD in Figure 1) do not overlap with each other.

Next, we use a CFG rule to describe our syntactic reordering model. Treating the two forms of reorderings in a unified way, the semantic reordering model is obtainable by regarding a PAS as a CFG rule and considering a semantic role as a constituent.

Because the translation of a source constituent might result in multiple discontinuous blocks, there can be several ways to describe or group the reordering patterns. Therefore, we design two general constituent reordering sub-models. One is based on the leftmost aligned word (leftmost reordering model) and the other is based on the rightmost aligned word (rightmost reordering model), as follows. Figure 2 shows the modeling steps for the leftmost reordering model. Figure 2(a) is an example of a CFG rule in the source parse tree and its word alignment links to the target language. Note that constituent ${\text{𝑋𝑃}}_4$, which covers word $f_8$, has no alignment. Then for each ${\text{𝑋𝑃}}_i$, we find the leftmost target word which is aligned to a source word covered by ${\text{𝑋𝑃}}_i$. Figure 2(b) shows that the leftmost target words for ${\text{𝑋𝑃}}_1$, ${\text{𝑋𝑃}}_2$, and ${\text{𝑋𝑃}}_3$ are $e_2$, $e_5$, and $e_3$, respectively, while ${\text{𝑋𝑃}}_4$ has no aligned target word. Then we get visit order $V=\left\{v_i\right\}$ for $\left\{{\text{𝑋𝑃}}_i\right\}$ in the transformation from Figure 2(b) to Figure 2(c), with the following strategies for special cases:

• •

  if the first constituent ${\text{𝑋𝑃}}_1$ is unaligned, we add a NULL word at the beginning of the target side and link ${\text{𝑋𝑃}}_1$ to the NULL word;

• •

  if a constituent ${\text{𝑋𝑃}}_i$ ($i>1$) is unaligned, we add a link to the target word which is aligned to ${\text{𝑋𝑃}}_{i-1}$, e.g., ${\text{𝑋𝑃}}_4$ will be linked to $e_3$; and

• •

  if $k$ constituents ${\text{𝑋𝑃}}_{m_1}\mathrm{\dots }{\text{𝑋𝑃}}_{m_k}$ () are linked to the same target word, then $v_{m_i}=v_{m_{i+1}}-1$, e.g., since ${\text{𝑋𝑃}}_3$ and ${\text{𝑋𝑃}}_4$ are both linked to $e_3$, then $v_3=v_4-1$.

Finally Figure 2(d) converts the visit order $V=\left\{v_1,\mathrm{\dots }{v}_n\right\}$ into a sequence of leftmost reordering types $LRT=\left\{lr{t}_1,\mathrm{\dots },lr{t}_{n-1}\right\}$. For every two adjacent constituents ${\text{𝑋𝑃}}_i$ and ${\text{𝑋𝑃}}_{i+1}$ with corresponding visit order $v_i$ and $v_{i+1}$, their reordering could be one of the following:

• •

  Monotone (M) if $v_{i+1}=v_i+1$;

• •

  Discontinuous Monotone (DM) if $v_{i+1}>v_i+1$;

• •

  Swap (S) if $v_{i+1}=v_i-1$;

• •

  Discontinuous Swap (DS) if .

Up to this point, we have generated a sequence of leftmost reordering types $\text{𝐿𝑅𝑇}=\left\{lr{t}_1,\mathrm{\dots },lr{t}_{n-1}\right\}$ for a given CFG rule cfg: $\text{𝑋𝑃}\to {\text{𝑋𝑃}}_1\mathrm{\dots }{\text{𝑋𝑃}}_n$. The leftmost reordering model takes the following form:

where $\psi \left(\text{𝑐𝑓𝑔}\right)$ indicates the surrounding context of the CFG. By assuming that any two reordering types in $\text{𝐿𝑅𝑇}=\left\{lr{t}_1,\mathrm{\dots },lr{t}_{n-1}\right\}$ are independent of each other, we reformulate Eq. 2 into:

Similarly, the sequence of rightmost reordering types RRT can be decided for a CFG rule $\text{𝑋𝑃}\to {\text{𝑋𝑃}}_1\mathrm{\dots }{\text{𝑋𝑃}}_n$.

Accordingly, for a PAS pas: $\text{𝑃𝐴𝑆}\to {\text{𝑅}}_1\mathrm{\dots }{\text{𝑅}}_n$, we can obtain its sequences of leftmost and rightmost reordering types by using the same way described above.

We have presented our unified approach to incorporating syntactic and semantic soft reordering constraints in an HPB system. In this section, we test its effectiveness in Chinese-English translation.

The trend of the results, summarized as performance gain over the baseline and MR08 systems averaged over all test sets, is presented in Table 6. The syntactic reordering models outperform the semantic reordering models, and the gain achieved by the semantic reordering models is limited in the presence of the MR08 syntactic features. In this section, we look at MR08 system and the systems improving it to explore the behavior differences between the two reordering models.

Coverage analysis: Our statistics show that syntactic reordering features (either leftmost or rightmost) are called 24 times per sentence on average. This is compared to only 9 times per sentence for semantic reordering features. This is not surprising since the semantic reordering features are exclusively attached to predicates, and the span set of the semantic roles is a strict subset of the span set of the syntactic constituents; only 22% of syntactic constituents are semantic roles. On average, a sentences has 4 PASs and each PAS contains 3 semantic roles. Of all the semantic role pairs, 44% are in the same CFG rules, indicating that this part of semantic reordering has overlap with syntactic reordering. Therefore, the PAS model has fewer opportunities to influence reordering.

Reordering accuracy analysis: The reordering type distribution on the reordering model training data in Table 3 suggests that semantic reordering is more difficult than syntactic reordering. To validate this conjecture on our translation test data, we compare the reordering performance among the MR08 system, the improved systems and the maximum entropy classifiers. For the test set, we have four reference translations. We run GIZA++ on the data combination of our translation training data and test data to get the alignment for the test data and each reference translation. Once we have the (semi-)gold alignment, we compute the gold reordering types between two adjacent syntactic constituents or semantic roles. Then we evaluate the automatic reordering outputs generated from both our translation systems and maximum entropy classifiers. Table 7 shows the accuracy averaged over the four gold reordering sets (the four reference translations). It shows that 1) as expected, our classifiers do worse on the harder semantic reordering prediction than syntactic reordering prediction; 2) thanks to the high accuracy obtained by the maxent classifiers, integrating either the syntactic or the semantic reordering constraints results in better reordering performance from both syntactic and semantic perspectives; 3) in terms of the mutual impact, the syntactic reordering models help improving semantic reordering more than the semantic reordering models help improving syntactic reordering; and 4) the rightmost models have a learnability advantage over the leftmost models, achieving higher accuracy across the board.

Feature weight analysis: Table 8 shows the syntactic and semantic reordering feature weights. It shows that the semantic feature weights decrease in the presence of the syntactic features, indicating that the decoder learns to trust semantic features less in the presence of the more accurate syntactic features. This is consistent with our observation that semantic reordering is harder than syntactic reordering, as seen in Tables 3 and 7.

Potential improvement analysis: Table 7 also shows that our current maximum entropy classifiers have room for improvement, especially for semantic reordering. In order to explore the error propagation from the classifiers themselves and explore the upper bound for improvement from the reordering models, we perform an “oracle” study, letting the classifiers be aware of the “gold” reordering type between two syntactic constituents or two semantic roles, and returning a higher probability for the gold reordering type and a smaller one for the others (i.e., we set 0.9 for the gold reordering type, and let the other non-gold three types share 0.1). Again, to get the gold reordering type, we run GIZA++ to get the alignment for tuning/test source sentences and each of four reference translations. We report the averaged performance by using the gold reordering type extracted from the four reference translations. Table 9 compares the performance between the non-oracle and oracle settings. We clearly see that using gold syntactic reordering types significantly improves the performance (e.g., 34.9 vs. 33.4 on average) and there is still some room for improvement by building a better maximum entropy classifiers (e.g., 34.9 vs. 34.3). To our surprise, however, the improvement achieved by gold semantic reordering types is still small (e.g., 33.9 vs. 33.4), suggesting that the potential improvement of semantic reordering models is much more limited. And we again see that the improvement achieved by semantic reordering models is limited in the presence of the syntactic reordering models.

Syntax-based reordering: Some previous work pre-ordered words in the source sentences, so that the word order of source and target sentences is similar. The reordering rules were either manually designed [6, 36, 41, 18] or automatically learned [39, 12, 35, 15, 19], using syntactic parses. Li et al. [20] focused on finding the $n$-best pre-ordered source sentences by predicting the reordering of sibling constituents, while Yang et al. [44] obtained word order by using a reranking approach to reposition nodes in syntactic parse trees. Both are close to our work; however, our model generates reordering features that are integrated into the log-linear translation model during decoding.

Another approach in previous work added soft constraints as weighted features in the SMT decoder to reward good reorderings and penalize bad ones. Marton and Resnik [24] employed soft syntactic constraints with weighted binary features and no MaxEnt model. They did not explicitly target reordering (beyond applying constraints on HPB rules). Although employing linguistically motivated labels in SCFG is capable of capturing constituent reorderings [5, 25], the rules are sparser than SCFG with nameless non-terminals (i.e., Xs) and soft constraints. Ge [11] presented a syntax-driven maximum entropy reordering model that predicted the source word translation order. Gao et al. [10] employed dependency trees to predict the translation order of a word and its head word. Huang et al. [13] predicted the translation order of two source words.⁴⁴Note that they obtained the translation order of source word pairs by predicting the reordering of adjacent constituents, which was quite close to our work. Our work, which shares this approach, differs from their work primarily in that our syntactic reordering models are based on the constituent level, rather than the word level.

Semantics-based reordering: Semantics-based reordering has also seen an increase in activity recently. In the pre-ordering approach, Wu et al. [38] automatically learned pre-ordering rules from PAS. In the soft constraint or reordering model approach, Liu and Gildea [23] modeled the reordering/deletion of source-side semantic roles in a tree-to-string translation model. Xiong et al. [40] and Li et al. [21] predicted the translation order between either two arguments or an argument and its predicate. Instead of decomposing a PAS into individual units, Zhai et al. [45] constructed a classifier for each source side PAS. Finally in the post-processing approach category, Wu and Fung [37] performed semantic role labeling on translation output and reordered arguments to maximize the cross-lingual match of the semantic frames between the source sentence and the target translation. To our knowledge, their semantic reordering models were PAS-specific. In contrast, our model is universal and can be easily adopted to model the reordering of other linguistic units (e.g., syntactic constituents). Moreover, we have studied the effectiveness of the semantic reordering model in different scenarios.

Non-syntax-based reorderings in HPB: Recently we have also seen work on lexicalized reordering models without syntactic information in HPB [31, 14, 26]. The non-syntax-based reordering approach models the reordering of translation words/phrases while the syntax-based approach models the reordering of syntactic constituents. Although there are overlaps between translation phrases and syntactic constituents, it is reasonable to think that the two reordering approaches can work together well and even complement each other, as the linguistic patterns they capture differ substantially. Setiawan et al. [32] modeled the orientation decisions between anchors and two neighboring multi-unit chunks which might cross phrase or rule boundaries. Last, we also note that recent work on non-syntax-based reorderings in (flat) phrase-based models [2, 9] can also be potentially adopted to hpb models.

In this paper, we have presented a unified reordering framework to incorporate soft linguistic constraints (of syntactic or semantic nature) into the HPB translation model. The syntactic reordering models take CFG rules and model their reordering on the target side, while the semantic reordering models work with PAS. Experiments on Chinese-English translation show that the reordering approach can significantly improve a state-of-the-art hierarchical phrase-based translation system. We have also discussed the differences between the two linguistic reordering models.

There are many directions in which this work can be continued. First, the syntactic reordering model can be extended to model reordering among constituents that cross CFG rules. Second, although we do not see obvious gain from the semantic reordering model when the syntactic model is adopted, it might be beneficial to further jointly consider the two reordering models, focusing on where each one does well. Third, to better examine the overlap or synergy between our approach and the non-syntax-based reordering approach, we will conduct direct comparisons and combinations with the latter.

This research was supported in part by the BOLT program of the Defense Advanced Research Projects Agency, Contract No. HR0012-12-C-0015. Any opinions, findings, conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the view of DARPA. The authors would like to thank three anonymous reviewers for providing helpful comments, and also acknowledge Ke Wu, Vladimir Eidelman, Hua He, Doug Oard, Yuening Hu, Jordan Boyd-Graber, and Jyothi Vinjumur for useful discussions.