3.1 Model

The log-linear model of the baseline BTG-based SMT system is identical to the one defined in Xiong et al. (Reference Xiong, Liu and Lin2006), which is formulated as follows.

(1) \begin{equation} M(\mathcal {D}) = M_T(r^l_{1..n_l}) \cdot M_R(r^m_{1..n_m})^{\lambda _R} \cdot P_{f}(e(\mathcal {D}))^{\lambda _{f}} \cdot \mbox{exp}(|e(\mathcal {D})|)^{\lambda _w} \end{equation}

where

• • $\mathcal {D}$ denotes a BTG derivation that is defined as a sequence of BTG rules.

  \begin{equation} \mathcal {D} = <r^l_{1..n_l}, r^m_{1..n_m}> \end{equation}

• • r^l _1..nl are BTG lexical rules which translate source phrases f into target phrases e as follows.

  \begin{equation} r^l: X \rightarrow e/f \end{equation}

• • r^m _1..nm are BTG merging rules that combine two neighboring blocks X ₁ and X ₂ into a larger block X in a straight ([]) or inverted (⟨⟩)order.

  \begin{equation} r^m: X\rightarrow [X_1, X_2] \mbox{or} \langle X_1, X_2 \rangle \end{equation}

• • The translation model M_T(r^l _1..nl) consists of phrase and lexical translation probabilities that are widely used in phrase-based SMT (Koehn et al. Reference Koehn, Och and Marcu2003) for the BTG lexical rules r^l _1..nl.

• • The reordering model M_R(r^m _1..nm) predicts the merging order (straight or inverted) with discriminative contextual features (Xiong et al. Reference Xiong, Liu and Lin2006) for the BTG merging rules r^m _1..nm.

• • P_f is the standard forward n-gram language model.

• • $\mbox{exp}(|e(\mathcal {D})|)$ represents the word penalty model on the target yield $e(\mathcal {D})$.

• • λs are weights of sub-models mentioned above (i.e., {M_T,M_R,P_f, exp(||)}, which are tuned by minimum error rate training (MERT) (Och Reference Och2003).

3.2 Decoder

We use a CKY-style decoder to find the best translation for each source sentence according to the model $M(\mathcal {D})$ defined in (1). In particular, given a source sentence f ₁. . .f_J, the CKY-style decoder employs BTG rules to generate derivations for each segment spanning from f_i to f_j. When the decoding procedure completes, the best derivation $\mathcal {D}^\ast$ that covers the whole input sentence will be found. The final translation e* is produced from the best derivation as follows.

(2) \begin{eqnarray} \mathcal {D}^\ast &=& \mathop {\rm argmax}_{f(\mathcal {D})=f_1\ldots f_J}M(\mathcal {D}) \nonumber \\ e^\ast &=& e(\mathcal {D}^\ast) \end{eqnarray}

where $f(\mathcal {D})$ and $e(\mathcal {D})$ are the source and target yields of $\mathcal {D,}$ respectively.

Following Chiang (Reference Chiang2007), we describe the CKY-style decoder for BTG-based SMT in a deductive system. The decoding algorithm is shown in Figure 1. $[X, i, j, \mathcal {S}(X)]:\mathcal {W}$ denotes a weighted item X spanning from f_i to f_j with a weight $\mathcal {W}$ which is calculated according to (1). $\mathcal {S}(X)$ is the n-gram language model state of the item. Normally, we define the leftmost/rightmost n − 1 words in target translations as the language model state for CKY-style decoding. In the algorithm, (3) generates an item using the lexical rule X → e/f to translate the source phrase f spanning from i to j to the target phrase e. Equation (4) merges two neighboring items into a larger item in a straight order and (5) in an inverted order. The weights of new items are calculated in a dynamic programming manner by reusing weights $\mathcal {W}_1$ and $\mathcal {W}_2$ of their sub-items. We only need to compute the incremental part Δ that includes the language model increment which will be described in Section 6 and the reordering model score for the BTG merging rules in a straight or inverted order (Xiong et al. Reference Xiong, Liu and Lin2006).

Fig. 1.

The CKY-style decoding algorithm for BTG-based SMT.

The actual CKY-style decoding procedure is given by the pseudo code in Figure 2. All items spanning from i to j are stored in a chart cell chart[X, i, j]. When we add new items to a chart cell, we recombine items with the same language model state by discarding those with lower weights in order to trim the search space.

Fig. 2.

The CKY-style decoding procedure for BTG-based SMT.

4.1 Model

Given a sequence of words w^m ₁ = (w ₁. . .w_m), a standard forward n-gram language model assigns a probability P_f(w^m ₁) to w^m ₁ as follows.

(6) \begin{equation} P_f\left(w_1^m\right) = \prod _{i=1}^{m}P\left(w_i|w_1^{i-1}\right) \approx \prod _{i=1}^{m}P\left(w_i|w_{i-n+1}^{i-1}\right) \end{equation}

where the approximation is based on the nth order Markov assumption. In other words, when we predict the current word w_i, we only consider the preceding n − 1 words w _{i − n + 1}. . .w _{i − 1} instead of the whole context history w ₁. . .w _{i − 1}.

Different from the forward n-gram language model, the backward n-gram language model assigns a probability P_b(w^m ₁) to w^m ₁ by looking at the succeeding context according to

(7) \begin{equation} P_b\left(w_1^m\right) = \prod _{i=1}^{m}P\left(w_i|w_{i+1}^{m}\right) \approx \prod _{i=1}^{m}P\left(w_i|w_{i+1}^{i+n-1}\right) \end{equation}

4.2 Training

For the convenience of training, we invert the order in each sentence in the training data, i.e., from the original order (w ₁. . .w_m) to the reverse order (w_m. . .w ₁). In this way, we can use the same toolkit that we use to train a forward n-gram language model to train a backward n-gram language model without any other changes. To be consistent with training, we also need to reverse the order of translation hypotheses when we access the trained backward language model.Footnote ² Note that the Markov context history of (7) is w _{i + n − 1}. . .w _{i + 1} instead of w _{i + 1}. . .w _{i + n − 1} after we invert the order. The words are the same but the order is completely reversed.

5.1 Model

We use pointwise mutual information (PMI) (Church and Hanks Reference Church and Hanks1990) to measure the strength of the association between x and y in a trigger pair, which is defined as follows

(8) \begin{equation} PMI(x,y) = \mbox{log}\left(\frac{P(x,y)}{P(x)P(y)}\right) \end{equation}

where P(x, y) is the joint probability of (x, y), and P(x) and P(y) are marginal probabilities that can be derived from P(x, y).

Zhou (Reference Zhou2004) proposes a new language model enhanced with MI trigger pairs. In his model, the probability of a given sentence w^m ₁ is approximated as

(9) \begin{equation} \begin{split} P\left(w_1^m\right) \approx & \left(\prod _{i=1}^{m}P\big (w_i|w_{i-n+1}^{i-1}\big)\right) \\ & \times \prod _{i=n+1}^m \prod _{k=1}^{i-n} \mbox{exp}(PMI(w_k,w_i, i-k-1)) \end{split} \end{equation}

There are two components in his model. The first component is still the standard n-gram language model. The second one is the MI trigger model which multiplies all exponential PMI values for trigger pairs where the current word is the triggered word and all preceding words outside the n-gram window of the current word are triggers. Note that his MI trigger model is distance dependent since trigger pairs (w_k, w_i) are sensitive to their distance i − k − 1 (zero distance for adjacent words). Therefore, the distance between word x and word y should be taken into account when calculating their PMI.

In this article, we adopt a distance-independent MI trigger model as follows

(10) \begin{equation} MI\left(w_1^m\right) = \prod _{i=n+1}^m \prod _{k=1}^{i-n} \mbox{exp}(PMI(w_k,w_i)) \end{equation}

We integrate the MI trigger model into the log-linear model of machine translation as an additional knowledge source which complements the standard n-gram language model in capturing long-distance dependencies. Using MERT (Och Reference Och2003), we are even able to tune the weight of the MI trigger model against the weight of the standard n-gram language model while Zhou (Reference Zhou2004) sets equal weights for both models.Footnote ³

In Section 8.3.2, we empirically compare our distance-independent MI trigger model with Zhou's distance-dependent model.

5.2 Training

We can use the maximum likelihood estimation method to calculate PMI for each trigger pair by taking counts from the training data. Let C(x, y) be the number of times that x and y co-occur in the same sentence in the training data. The joint probability of (x, y) is calculated as

(11) \begin{equation} P(x,y) = \frac{C(x,y)}{\sum _{x}\sum _{y}C(x,y)} \end{equation}

The marginal probabilities of x and y can be deduced from the joint probability as follows

(12) \begin{equation} P(x) = \sum \nolimits _{y}P(x,y) \end{equation}

(13) \begin{equation} P(y) = \sum \nolimits _{x}P(x,y) \end{equation}

Since the number of distinct trigger pairs is $\mathcal {O}(|T|^2),$ where T is the target language vocabulary, the question is how to select valuable trigger pairs. We select trigger pairs according to the following three steps.

1. (1) The distance between x and y must not be less than n − 1. Suppose, we use a 5-gram language model and y = w_i, then x ∈ {w ₁. . .w _{i − 5}}.

2. (2) C(x, y) > c. In all our experiments, we set c = 10.

3. (3) Finally, we only keep trigger pairs whose PMI value is larger than 0. Trigger pairs whose PMI value is less than 0 often contain stop words, such as ‘the’, ‘a’. These stop words have very large marginal probabilities due to their high frequencies. In Section 8.3.1, we empirically investigate whether we should use PMI-negative trigger pairs or trigger pairs with stop words.

6.1 Backward language model integration

In this section, we present an algorithm to integrate the backward n-gram language model into the CKY-style decoder of BTG-based SMT that is described in Section 3.2. Wu (Reference Wu1996) introduces a dynamic programming algorithm to integrate a forward bigram language model with inversion transduction grammar. His algorithm is then adapted and extended for integrating forward n-gram language models into synchronous context free grammars (CFGs) by Chiang (Reference Chiang2007). Our algorithm is different from theirs in two major aspects as follows.

1. (1) The string input to the algorithms is in a reverse order.Footnote ⁴

2. (2) We adopt a different way to calculate language model probabilities for partial hypotheses so that we can utilize incomplete n-grams.

Before we introduce the integration algorithm, we define three functions $\mathcal {P}$, $\mathcal {L}$, and $\mathcal {R}$ on strings (in a reverse order) over the target language terminal alphabet T. The function $\mathcal {P}$ is defined as follows.

(14) \begin{equation} \begin{split} \mathcal {P}(w_k\ldots w_1) = & \underbrace{P(w_k)\ldots P(w_{k-n+2}|w_k\ldots w_{k-n+3})}_a \\ & \times \underbrace{\prod _{1 \le i \le k-n+1} P(w_i|w_{i+n-1}\ldots w_{i+1})}_b \end{split} \end{equation}

This function consists of two parts:

• • The first part (a) calculates incomplete n-gram language model probabilities for word w_k to w _{k − n + 2}. That means, we calculate the unigram probability for w_k (P(w_k)), bigram probability for w _{k − 1} (P(w _{k − 1}|w_k)) and so on until we take n − 1-gram probability for w _{k − n + 2} (P(w _{k − n + 2}|w_k. . .w _{k − n + 3})). This resembles the way in which the forward language model probability in the future cost is computed in the standard phrase-based SMT (Koehn et al. Reference Koehn, Och and Marcu2003).

• • The second part (b) calculates complete n-gram backward language model probabilities for word w _{k − n + 1} to w ₁.

The function is different from Chiang's p function in that his function p only calculates language model probabilities for the complete n-grams. This makes two items not directly comparable. In order to address this issue, Chiang also calculates incomplete n-gram language model probabilities using a heuristic function. However, this heuristic function for incomplete n-grams is added to the score of an item only for pruning. In our integration algorithm, language model probabilities for incomplete n-grams are intrinsic to item scores.

Since we calculate backward language model probabilities in a left-to-right decoding process, the succeeding context for the current word is either yet to be generated or incomplete in terms of n-grams. The $\mathcal {P}$ function enables us to utilize incomplete succeeding contexts to approximately predict words. Once the succeeding contexts are complete, we can quickly update language model probabilities in an efficient way in our algorithms.

The other two functions $\mathcal {L}$ and $\mathcal {R}$ are defined as follows

(15) \begin{equation} \mathcal {L}(w_k\ldots w_1) = \left\lbrace \begin{array}{ll}w_k\ldots w_{k-n+2}, &\mbox{if} k \ge n \\ w_k\ldots w_1, & \mbox{otherwise} \end{array} \right. \end{equation}

(16) \begin{equation} \mathcal {R}(w_k\ldots w_1) = \left\lbrace \begin{array}{ll}w_{n-1}\ldots w_{1}, & \mbox{if} k \ge n \\ w_k\ldots w_1, & \mbox{otherwise} \end{array} \right. \end{equation}

$\mathcal {L}$

$\mathcal {R}$

The algorithm is shown in Figure 3. The item [X, i, j; l|r] indicates that a BTG node X has been constructed spanning from i to j on the source side with the leftmost|rightmost n − 1 words l|r on the target side (the language model state). As mentioned before, all target strings assessed by the defined functions ($\mathcal {P}$, $\mathcal {L}$, and $\mathcal {R}$) are in an inverted order (denoted by $\overline{e}$). In order to highlight how we integrate the backward language model into BTG-based SMT, we only display the backward language model probability for each item, ignoring all other scores such as phrase translation probabilities. Equation (19) in Figure 3 shows how we calculate the backward language model probability for an axiom which applies a BTG lexical rule to translate a source phrase f into a target phrase e. Equations (20) and (21) show how we update the backward language model probabilities for two merging rules which combine two neighboring blocks in a straight and inverted order respectively. The fundamental theories behind this update are

(17) \begin{equation} \mathcal {P}(\overline{e_1e_2}) = \mathcal {P}(\overline{e_1})\mathcal {P}(\overline{e_2})\frac{\mathcal {P}(\mathcal {R}(\overline{e_2})\mathcal {L}(\overline{e_1}))}{\mathcal {P}(\mathcal {R}(\overline{e_2}))\mathcal {P}(\mathcal {L}(\overline{e_1}))} \end{equation}

(18) \begin{equation} \mathcal {P}(\overline{e_2e_1}) = \mathcal {P}(\overline{e_1})\mathcal {P}(\overline{e_2})\frac{\mathcal {P}(\mathcal {R}(\overline{e_1})\mathcal {L}(\overline{e_2}))}{\mathcal {P}(\mathcal {R}(\overline{e_1}))\mathcal {P}(\mathcal {L}(\overline{e_2}))} \end{equation}

Fig. 3.

Integrating the backward language model into a BTG-based CKY-style decoder.

Whenever two strings e ₁ and e ₂ are concatenated in a straight or inverted order, we can reuse their $\mathcal {P}$ values ($\mathcal {P}(\overline{e_1})$ and $\mathcal {P}(\overline{e_2})$) in terms of dynamic programming. Only the probabilities of boundary words (e.g., $\mathcal {R}(\overline{e_2})\mathcal {L}(\overline{e_1})$ in (17)) need to be recalculated since they have complete n-grams after the concatenation. Table 1 shows values of $\mathcal {P}$, $\mathcal {L}$, and $\mathcal {R}$ in a 3-gram example which helpsto verify (17). These two equations guarantee that our algorithm can correctly compute the backward language model probability of a sentence stepwise in a dynamic programming framework.Footnote ⁵

Table 1.

Values of $\mathcal {P}$, $\mathcal {L}$, and $\mathcal {R}$ in a 3-gram example

Figure 4 displays a real-world example to show how we update the score of a 5-gram backward language model when two items are merged. Let us take the item X₀₁ for instance. This item is the combination of items X₀ (with target string e ₁ = ‘understand’) and X₁ (with target string e ₂ = ‘that Africa can no longer’) in a straight order. The backward language model costs (i.e., $\mbox{log}\mathcal {P}(\overline{e_1})$ and $\mbox{log}\mathcal {P}(\overline{e_2})$) of items X₀ and X₁ are − 4.52 and − 9.67, respectively. The leftmost four words of $\overline{e_1}$ (i.e., $\mathcal {L}(\overline{e_1})$) comprise only the single word ‘understand’ while the rightmost four words of $\overline{e_2}$ (i.e., $\mathcal {R}(\overline{e_2})$) are ‘no can Africa that’. According to (17), the backward language model cost of the item X₀₁ should be (− 4.52) + (− 9.67) + (− 14.71) − (− 4.52) − (− 11.25) = − 13.13. Similarly, we can easily calculate the backward language model score of item X₀₁₂ when we merge items X₀₁ and X₂. Note that we can store the calculated backward language model scores of the leftmost/rightmost words of each item in practice to save time.

Fig. 4.

A BTG tree fragment showing how the values of the forward (FLM), backward (BLM) and mutual information trigger (MI) language model are computed. The rectangles display the FLM/BLM costs (log (base-10) probabilities) of target strings as well as the PMI values of trigger pairs that are used to calculate the FLM/BLM/MI values of items X₀₁ (the combination of items X₀ and X₁) and X₀₁₂ (the combination of items X₀₁ and X₂).

The theoretical time complexity of this algorithm is $\mathcal {O}(J^3|T|^{4(n-1)})$ because in the update parts in (17) and (18) both the numerator and denominator have up to 2(n − 1) terminal symbols. J is the length of source sentence. This is the same as the time complexity of Chiang's language model integration (Chiang Reference Chiang2007).

This algorithm can also be easily adapted to integrate the forward n-gram language model by redefining the three functions $\mathcal {P}$, $\mathcal {L}$, and $\mathcal {R}$ on strings that are not reversed (i.e., in their original order). Due to the space limit, we do not introduce it here. Interesting readers can find how we calculate the forward language model in Figure 4.

6.2 MI trigger model integration

We integrate the MI trigger model into the BTG-based SMT system still in a dynamic programming fashion. In particular, we calculate MI trigger model scores for two strings e ₁ and e ₂ that are concatenated in a straight (e ₁e ₂) or inverted (e ₂e ₁) order as follows.

(22) \begin{equation} MI(e_1e_2) = MI(e_1)MI(e_2)MI(e_1 \mapsto e_2) \end{equation}

(23) \begin{equation} MI(e_2e_1) = MI(e_1)MI(e_2)MI(e_2 \mapsto e_1) \end{equation}

(24) \begin{equation} MI(e_1 \rightarrow e_2) = \prod _{w_i \in e_2} \prod _{{{\scriptstyle {\begin{array}{*10c}w_k \in e_1 \\ i -k \ge n\end{array}}}}} \mbox{exp}(PMI(w_k,w_i)) \end{equation}

Similarly, MI(e ₂↦e ₁) denotes the MI trigger model score for trigger pairs in which a word in e ₂ triggers a word in e ₁, which is calculated as follows.

(25) \begin{equation} MI(e_2 \rightarrow e_1) = \prod _{w_i \in e_1} \prod _{{{\scriptstyle {\begin{array}{*10c}w_k \in e_2 \\ i -k \ge n\end{array}}}}} \mbox{exp}(PMI(w_k,w_i)) \end{equation}

The integration algorithm is shown in Figure 5. The problem here is that the state of the MI trigger model involves all words in a string. It is different from the state of the n-gram language model as the latter only considers the preceding or succeeding n − 1 words. If we define the MI trigger model state as the whole string involved, it results in an intractable integration algorithm as we can not resort to hypotheses recombination for search space pruning. In order to make the integration algorithm tractable, we still use the outermost n − 1 words to define the MI trigger model state. Although this will lead to search errors, we can benefit from the MI trigger model for long-distance dependencies in a tractable way.

Fig. 5.

Integrating the MI trigger language model into a BTG-based CKY-style decoder.

Let us revisit Figure 4 in order to get a clear picture of how we calculate the MI trigger language model. This time we take the item X₀₁₂ (the combination of items X₀₁ and X₂) as an example. The MI trigger language model score of item X₂ (log value of (10)) is 0 as there are no two words whose distance is equal or larger than four. For item X₀₁, although the distance of the two words (understand, longer) is equal to four, they are not selected as a trigger pair as the two words co-occur rarely. Therefore, the default MI value for these two words is set 0. When we combine items X₀₁ and X₂ into item X₀₁₂, the MI trigger language model score of item X₀₁₂ will be deduced from MI(X₀₁), MI(X₂) and all trigger pairs (x, y) where x and y are in X₀₁ and X₂ respectively and their distance is not less than four. The qualified trigger pairs therefore include (understand, missed), (understand, opportunities), (that, missed), (that, opportunities) and (Africa, opportunities). Their PMI values are shown in the PMI rectangle in Figure 4. As we only use trigger pairs whose PMI value is larger than 0, the final MI trigger language model score of item X₀₁₂ is calculated as MI(X₀₁) + MI(X₂) + PMI(that, opportunities) + PMI(Africa, opportunities) = 1.10 according to (24).

8.1 Experimental setup

In this section, we describe our experimental configurations on the three language pairs. We adopted the case-insensitive BLEU-4 (Papineni et al. Reference Papineni, Roukos, Ward and Zhu2002) and METEOR (Banerjee and Lavie Reference Banerjee and Lavie2005) as the evaluation metrics. In order to alleviate the impact of MERT (Och Reference Och2003) instability, we followed the suggestion of Clark et al. (Reference Clark, Dyer, Lavie and Smith2011) to run MERT three times and report average BLEU/METEOR scores over the three runs for all our experiments.

8.1.1 Chinese-to-english (ZH–EN)

The training corpora for Chinese-to-English are from LDC, namely LDC2004E12, LDC2004T08, LDC2005T10, LDC2003E14, LDC2002E18, LDC2005T06, LDC2003E07 and LDC2004T07. Statistics of the training corpora are shown in Table 2. We used all corpora to train our translation model and smaller corpora without the United Nations corpus (LDC2004E12) to build a maximum entropy-based reordering model (Xiong et al. Reference Xiong, Liu and Lin2006).

Table 2.

Parallel data sets used for Chinese/Spanish/Vietnamese-to-English experiments

To train the forward/backward language models and MI trigger model, we used the Xinhua section of the English Gigaword corpus (306 million words). Firstly, we built a forward 5-gram language model using the SRILM toolkit (Stolcke Reference Stolcke2002) with modified Kneser– Ney smoothing. Then we trained a backward 5-gram language model on the same monolingual corpus in the way described in Section 4.2. Finally, we trained our MI trigger model still on this corpus according to the method in Section 5.2.

We used the NIST MT03 evaluation test data as the development set, and the NIST MT-04 as the test set. To optimize some configurations on the MI trigger model (Sections 8.3.1 and 8.3.2), we also used the NIST MT-05 as the test set. Each sentence in the dev/test set has four different reference translations.

8.2 Backward language model

We investigate the effectiveness of the proposed backward language model within two contexts: (1) using it alone and (2) combining it with the forward language model.

8.2.1 Backward language model alone

As we discussed in Section 6.1, we can completely replace the forward language model with the backward language model. The only difference is that the order of input to the backward language model is reversed. Table 3 shows the results of using the backward language model alone across the three language pairs. Compared with the forward language model, the backward language model achieves better performance in terms of both BLEU and METEOR. This resonates with the finding of Finch and Sumita (Reference Finch and Sumita2009), who report that among translations from sixteen different source languages to English, reverse decoding (with the backward language model) outperforms forward decoding (with the forward language model) in most cases (13 versus 3). The results in Table 3 empirically reconfirm that the backward language model may be a better choice than the forward language model when a source language is translated to English.

Table 3.

Effects of the proposed backward language model. FLM: forward language model; BLM: backward language model; MR: METEOR

The reason why the backward language model generally outperforms the forward language model in X-to-English translation may be related to the distribution of head word positions relative to current words in English. We study such distribution on the English Penn Treebank (Marcus, Santorini and Marcinkiewicz Reference Marcus, Santorini and Marcinkiewicz1993) where all parse trees are automatically transferred to dependency treesFootnote ⁷. We assume that the head of a dependency relation is more predictive of its dependent objects than vice versa. In the dependency structure assigned to a sentence, all words are dependent on some head, except for the matrix verb. Analysis of the dependency structures in the corpus shows that 86.43% of words have their head within a 5-word window to their left or to their right. Of those, 53.3% have their head within a 5-word window to their RIGHT. Hence the majority of words depend on a head that follows them, rather than on a head that precedes them. In other words, most words have backward (rather than forward) dependencies, which endows the backward language model with a stronger prediction ability than that of the forward language model in English.

In view of the difficulty in the syntactical dependency analysis, here we provide a more practical and straightforward indicator to show whether we should use a backward language model. As we can train a backward or forward language model on the same training corpus, we can also easily calculate the perplexity of them on the same test corpus. Table 4 displays the perplexity of the forward/backward language models on the reference corpora of the test sets of three language pairs. The backward language model has a lower perplexity on ZH/VI–EN. Given the higher performance of the backward language model on ZH/VI–EN shown in Table 3, the lower perplexity of the BLM is a strong indicator that we should incorporate the backward language model.

Table 4.

Perplexity of the forward/backward language models on the reference sets

8.2.2 Backward and forward language model combination

The last row of Table 3 shows that the integration of a forward language model and a backward language model achieves improvements in terms of both BLEU and METEOR over a single forward language model across all three language pairs. The absolute improvements in BLEU score are 0.60, 0.27, and 0.48 BLEU points on ZH/ES/VI–EN, respectively. The relatively lower improvements on Spanish-to-English may be related to the higher perplexity of the backward language model on the reference set of ES–EN as shown in Table 4.

Table 5 provides a Chinese-to-English example that displays how the backward language model improves translation quality. The italicized words in the hypothesis generated by using the backward and forward language model together (FLM + BLM) exactly match the reference. However, the italicized words in the baseline hypothesis fail to match the reference due to the incorrect position of the word ‘decree’ (XXXX). We calculate the forward/backward language model score (the logarithm of language model probability) for the italicized words in both the baseline and FLM + BLM hypothesis according to the trained language models. The difference in the forward language model score is only 1.582, which may be offset by differences in other features in the log-linear translation model. On the other hand, the difference in the backward language model score is 3.517. This larger difference may guarantee that the hypothesis generated by FLM + BLM is better enough to be selected as the best hypothesis by the decoder. This suggests that the backward language model is able to provide useful and discriminative information which is complementary to that given by the forward language model.

Table 5.

Translation example from the NIST MT-04 test set, comparing the baseline with the backward language model

8.3 MI trigger model

In this section, we integrate various trigger pairs into our MI trigger model and thoroughly investigate their impact on translation quality in terms of BLEU/METEOR. In particular,

1. (1) We study the distribution of trigger pairs according to their PMI values and component words. We then explore different trigger pair selection criteria based on this distribution.

2. (2) We further investigate whether we should use distance-dependent or syntactically informed triggers.

3. (3) We finally evaluate our MI trigger model on the three language pairs.

Note that all experiments of (1) and (2) are conducted on the Chinese-to-English translation task with the NIST MT-05 being the test set.

8.3.1 Trigger pair selection

Trigger pairs (x, y) can be divided into three categories according to their PMI value PMI(x, y).

1. (1) PMI(x, y) > 0, if there is a genuine association between x and y (Church and Hanks Reference Church and Hanks1990).

2. (2) PMI(x, y) = 0, if x and y occur independently.

3. (3) PMI(x, y) < 0, if x and y are in complementary distributionFootnote ⁸ (Church and Hanks Reference Church and Hanks1990) or (x, y) include words which occur with a very high frequency, such as stop words.

We investigate the distribution of such categories on the Chinese-to-English translation task. We collect 5.03M trigger pairs in total from the training data after we remove trigger pairs that violate the selection criteria (1) and (2) described in Section 5.2. Table 6 gives the distribution on these collected trigger pairs.

Table 6.

Distribution of trigger pairs on the Chinese-to-English translation task

From the table, we can observe that the majority of trigger pairs (accounting for 57.36%) are with a positive PMI value. Among these PMI-positive trigger pairs, most of them (70%) do not contain any stop words. However, among PMI-negative trigger pairs, most of them (accounting for 57.79%) include stop words. Based on this distribution, we conducted several experiments on the NIST MT-05: (1) using all trigger pairs (All); (2) only using PMI-positive trigger pairs (Pos); (3) only using PMI-positive trigger pairs without stop words (Pos-sw); and finally (4) only using PMI-negative trigger pairs (Neg). The results are shown in Table 7.

Table 7.

Results of using various trigger pair selection criteria

We can see from the table that we achieve the best performance in terms of BLEU when we only integrate PMI-positive trigger pairs into the MI trigger model (Pos). When we exploit both PMI-positive and PMI-negative trigger pairs (All), the BLEU score is significantly dropped (34.73 versus 34.02) compared with the BLEU score of Pos. Furthermore, only using PMI-negative trigger pairs (Neg) leads to a more seriously degraded performance which is worse than that of the baseline. This indicates that PMI-negative trigger pairs may not help even if they provide complementary cues.

Yet another interesting finding is about trigger pairs with stop words. If we remove PMI-positive trigger pairs that contain stop words (Pos-sw), the result shows that the absence of trigger pairs with stop words degrades the performance in terms of BLEU and METEOR. This suggests that stop words are important in constructing trigger pairs. Section 8.3.3 gives an example of a trigger pair that contains a stop word ‘is’ and shows how this trigger pair helps the decoder find a better hypothesis.

In all experiments hereafter, we therefore only use PMI-positive trigger pairs (including PMI-positive trigger pairs with stop words) in our MI trigger model.

8.3.2 Distance-dependent triggers and syntactically informed triggers

In this section, we explore two informative triggers: distance-dependent triggers and syntactically informed triggers. Our goal is to find whether the associated distance and syntax information are able to improve our MI trigger model. In the distance-dependent MI trigger model, we maintain the distance between two words w_k and w_i as the third element in each trigger, following Zhou's model (Zhou Reference Zhou2004). The PMI of a distance-dependent trigger is therefore calculated as follows

(26) \begin{equation} PMI(w_k,w_i, i-k-1) = \mbox{log}\left(\frac{P(w_k,w_i, i-k-1)}{P(w_k)P(w_i)}\right) \end{equation}

Table 8 shows the result of the distance-dependent MI trigger model on the NIST MT-05. Compared with the distance-independent MI trigger model, the distance-dependent model obtains a degraded performance in terms of both BLEU and METEOR, especially the latter which is even worse than that of the baseline. Therefore, we do not adopt the distance-dependent model given its larger model size with a worse performance compared with the distance-independent model.

Table 8.

Results of using distance-dependent/syntactically informed MI triggers. MI-di: distance-independent MI model; MI-dd: distance-dependent MI model; MI-syn: syntactically informed MI model

In order to employ syntactical information, we annotated each word in the training data with part-of-speech (POS) tags via a conditional random field (CRF) based POS tagger.Footnote ⁹ The extracted trigger pairs (w_k/t_k, w_i/t_i) are therefore associated with POS information (t_k and t_i). Words in extracted bilingual phrases are also associated with POS tags so that we can obtain POS tags for target words during decoding. With the remaining (training procedure and trigger selection) kept the same as the distance-independent model, the syntactically informed MI trigger model is not able to achieve further improvements either in terms of BLEU and METEOR as shown in Table 8.

8.3.3 Effects of MI trigger model across language pairs

We evaluated our distance-independent MI trigger model on the three language pairs. Only PMI-positive trigger pairs are used as described in Section 8.3.1. The results are given in Table 9. From the table, we can see that the MI trigger model is able to improve translation quality on all three language pairs in terms of both BLEU and METEOR. We obtain absolute improvements of 0.39, 0.46, and 0.44 BLEU points on ZH–EN, ES–EN and VI–EN, respectively. This indicates that language models in SMT can significantly benefit from triggers which carry long-distance dependency information.

Table 9.

Results of combining the MI trigger model with the forward and backward language model. For the convenience of comparison, here we repeat the results of FLM + BLM from Table 3. MR: METEOR

In Table 10, we present a Chinese-to-English example to show how the MI trigger model improves translation quality. The major difference in hypotheses of this example is the word choice between ‘is’ and ‘was’. The new system enhanced with the MI trigger model (FLM + MI) selects the former while the baseline selects the latter. The forward language model score for the baseline hypothesis is − 26.4141, which is higher than the forward language model score of the FLM + MI hypothesis − 26.6698. This could be the reason why the baseline selects the word ‘was’ instead of ‘is’. As can be seen, there is another ‘is’ in the preceding context of the word ‘was’ in the baseline hypothesis. Unfortunately, this word ‘is’ is located just outside the scope of the preceding 5-gram context of ‘was’. The forward 5-gram language model is hence not able to take it into account when calculating the probability of ‘was’. However, this is not a problem for the MI trigger model. Since ‘is’ and ‘was’ rarely co-occur in the same sentence, the PMI value of the trigger pair (is, was)Footnote ¹⁰ is − 1.03114 while the PMI value of the trigger pair (is, is) is as high as 0.315516. Therefore, our MI trigger model selects ‘is’ rather than ‘was’.Footnote ¹¹ This example illustrates that the MI trigger model is capable of selecting correct words by using long-distance trigger pairs.

Table 10.

Translation example from the NIST MT-04 test set, comparing the baseline with the MI trigger model. Both system outputs are not detokenized so that we can see how language model scores are calculated. The underlined words highlight the difference between the enhanced models and the baseline

8.4 Combination of the backward language model and MI trigger model

The last question is whether a combination of the backward language model and the MI trigger model is able to gain further improvements. According to the results shown in Table 9, the answer to this question is mixed. In Chinese/Vietnamese-to-English, the combination of the backward language model and the MI trigger model (FLM + BLM + MI) is able to obtain improvements of 0.97 and 0.64 BLEU points, respectively, over the single forward language model. These improvements are larger than that achieved by integrating only one model with the forward language model (FLM + BLM or FLM + MI). In Spanish-to-English, we successfully achieve further improvements over FLM + BLM but fail to obtain further improvements over FLM + MI. It seems that the MI trigger model is more helpful than the backward language model in Spanish-to-English translation.

This is also suggested by the relative weights assigned by MERT to the backward and MI trigger language models against the weight of the forward language model, which are shown in Table 11. In Chinese/Vietnamese-to-English, the backward language model has a much larger weight than that of the forward language model. This indicates that the tuning algorithm prefers the backward language model to the forward language model in these two tasks. However, in the Spanish-to-English translation task, the backward language model obtains a very low weight. Such relative weights of the forward/backward language models are exactly consistent with the perplexities of these two language models shown in Table 4. Similarly, the relative weights of the MI trigger model are also in line with its contributions in the translation tasks of the three language pairs.

Table 11.

Relative weights of the backward language model (BLM) and the mutual information trigger model (MI) against the weight of the forward language model assigned by MERT. We set the weights of the forward language model as the reference (values are set to 1)

8.5 Language model size and decoding speed

In this section, we discuss the size of three language models as well as decoding speed with these models. Table 12 shows the information of model size and decoding speed in the Chinese–English translation task. In order to have a clear comparison, we set the model size and decoding speed of the baseline system (with the forward language model) as the reference (values are set to 1). Then we show the ratios of model size and decoding speed of other systems against those of the baseline. From the table, we can observe that

• • The size of the backward language model is marginally smaller than that of the forward language model (maybe due to smoothing).

• • The size of the MI trigger model is quite small, about 10% of that of the forward language model.

• • The decoder with the backward language model is faster than that with the forward language model (maybe due to the smaller model size). The combination of two language models (BLM + FLM) does not slow the decoding quite much (only 6% slower than the baseline). This displays the advantage of our integration algorithm as we do not need to run the decoding process twice, each of which is with a different language model (forward or backward).

• • The decoding speed for systems with the MI trigger model is much slower than the baseline. The reason for this is that we do not use an efficient data structure to access the huge trigger pair table. We store trigger pairs in an ordinary standard map. We believe that the decoding speed will be much faster if we do some optimizations with a more efficient data structure, such as trie.

Table 12.

Language model size and decoding speed