Minimum Imputed-Risk: Unsupervised Discriminative Training for Machine Translation

Discriminative training for machine translation has been well studied in the recent past. A limitation of the work to date is that it relies on the availability of high-quality in-domain bilingual text for supervised training. We present an unsupervised discriminative training framework to incorporate the usually plentiful target-language monolingual data by using a rough "reverse" translation system. Intuitively, our method strives to ensure that probabilistic "round-trip" translation from a target-language sentence to the source-language and back will have low expected loss. Theoretically, this may be justified as (discriminatively) minimizing an imputed empirical risk. Empirically, we demonstrate that augmenting supervised training with unsupervised data improves translation performance over the supervised case for both IWSLT and NIST tasks.


Introduction
Missing data is a common problem in statistics when fitting the parameters θ of a model. A common strategy is to attempt to impute, or "fill in," the missing data (Little and Rubin, 1987), as typified by the EM algorithm. In this paper we develop imputation techniques when θ is to be trained discriminatively.
We focus on machine translation (MT) as our example application. A Chinese-to-English machine translation system is given a Chinese sentence x and * Zhifei Li is currently working at Google Research, and this work was done while he was a PHD student at Johns Hopkins University. asked to predict its English translation y. This system employs statistical models p θ (y | x) whose parameters θ are discriminatively trained using bilingual sentence pairs (x, y). But bilingual data for such supervised training may be relatively scarce for a particular language pair (e.g., Urdu-English), especially for some topics (e.g., technical manuals) or genres (e.g., blogs). So systems seek to exploit additional monolingual data, i.e., a corpus of English sentences y with no corresponding source-language sentences x, to improve estimation of θ. This is our missing data scenario. 1 Discriminative training of the parameters θ of p θ (y | x) using monolingual English data is a curious idea, since there is no Chinese input x to translate. We propose an unsupervised training approach, called minimum imputed risk training, which is conceptually straightforward: First guess x (probabilistically) from the observed y using a reverse Englishto-Chinese translation model p φ (x | y). Then train the discriminative Chinese-to-English model p θ (y | x) to do a good job at translating this imputed x back to y, as measured by a given performance metric. Intuitively, our method strives to ensure that probabilistic "round-trip" translation from a targetlanguage sentence to the source-language and back again will have low expected loss.
Our approach can be applied in an application scenario where we have (1) enough out-of-domain bilingual data to build two baseline translation systems, with parameters θ for the forward direction, and φ for the reverse direction; (2) a small amount of in-domain bilingual development data to discriminatively tune a small number of parameters in φ; and (3) a large amount of in-domain English monolingual data.
The novelty here is to exploit (3) to discriminatively tune the parameters θ of all translation model components, 2 p θ (y|x) and p θ (y), not merely train a generative language model p θ (y), as is the norm.
Following the theoretical development below, the empirical effectiveness of our approach is demonstrated by replacing a key supervised discriminative training step in the development of large MT systems -learning the log-linear combination of several component model scores (viewed as features) to optimize a performance metric (e.g. BLEU) on a set of (x, y) pairs -with our unsupervised discriminative training using only y. One may hence contrast our approach with the traditional supervised methods applied to the MT task such as minimum error rate training (Och, 2003;, the averaged Perceptron (Liang et al., 2006), maximum conditional likelihood (Blunsom et al., 2008), minimum risk (Smith and Eisner, 2006;Li and Eisner, 2009), and MIRA (Watanabe et al., 2007;Chiang et al., 2009).
We perform experiments using the open-source MT toolkit Joshua (Li et al., 2009a), and show that adding unsupervised data to the traditional supervised training setup improves performance.

Supervised Discriminative Training via Minimization of Empirical Risk
Let us first review discriminative training in the supervised setting-as used in MERT (Och, 2003) and subsequent work. One wishes to tune the parameters θ of some complex translation system δ θ (x). The function δ θ , which translates Chinese x to English y = δ θ (x) need not be probabilistic. For example, θ may be the parameters of a scoring function used by δ, along with pruning and decoding heuristics, for extracting a high-scoring translation of x.
The goal of discriminative training is to minimize the expected loss of δ θ (·), under a given taskspecific loss function L(y , y) that measures how bad it would be to output y when the correct output is y. For an MT system that is judged by the BLEU metric (Papineni et al., 2001), for instance, L(y , y) may be the negated BLEU score of y w.r.t. y. To be precise, the goal 3 is to find θ with low Bayes risk, where p(x, y) is the joint distribution of the inputoutput pairs. 4 The true p(x, y) is, of course, not known and, in practice, one typically minimizes empirical risk by replacing p(x, y) above with the empirical distributionp(x, y) given by a supervised training set The search for θ * typically requires the use of numerical methods and some regularization. 5 3 Unsupervised Discriminative Training with Missing Inputs

Minimization of Imputed Risk
We now turn to the unsupervised case, where we have training examples {y i } but not their corresponding inputs {x i }. We cannot compute the summand L(δ θ (x i ), y i ) for such i in (2), since δ θ (x i ) requires to know x i . So we propose to replace 3 This goal is different from the minimum risk training of Li and Eisner (2009) in a subtle but important way. In both cases, θ * minimizes risk or expected loss, but the expectation is w.r.t. different distributions: the expectation in Li and Eisner (2009) is under the conditional distribution p(y | x), while the expectation in (1) is under the joint distribution p(x, y). 4 In the terminology of statistical decision theory, p(x, y) is a distribution over states of nature. We seek a decision rule δ θ (x) that will incur low expected loss on observations x that are generated from unseen states of nature. 5 To compensate for the shortcut of using the unsmoothed empirical distribution rather than a posterior estimate of p(x, y) (Minka, 2000), it is common to add a regularization term ||θ|| 2 2 in the objective of (2). The regularization term can prevent overfitting to a training set that is not large enough to learn all parameters.
where p φ (· | ·) is a "reverse prediction model" that attempts to impute the missing x i data. We call the resulting variant of (2) the minimization of imputed empirical risk, and say that is the estimate with the minimum imputed risk 6 . The minimum imputed risk objective of (4) could be evaluated by brute force as follows.
1. For each unsupervised example y i , use the reverse prediction model p φ (· | y i ) to impute possible reverse translations X i = {x i1 , x i2 , . . .}, and add each (x ij , y i ) pair, weighted by p φ (x ij | y i ) ≤ 1, to an imputed training set .
2. Perform the supervised training of (2) on the imputed and weighted training data.
The second step means that we must use δ θ to forward-translate each imputed x ij , evaluate the loss of the translations y ij against the corresponding true translation y i , and choose the θ that minimizes the weighted sum of these losses (i.e., the empirical risk when the empirical distributionp(x, y) is derived from the imputed training set). Specific to our MT task, this tries to ensure that probabilistic "roundtrip" translation, from the target-language sentence y i to the source-language and back again, will have a low expected loss. 7 The trouble with this method is that the reverse model p φ generates a weighted lattice or hypergraph X i encoding exponentially many translations of y i , and it is computationally infeasible to forwardtranslate each x ij ∈ X i . We therefore investigate several approximations to (4) in Section 3.4. 6 One may exploit both supervised data {(xi, yi)} and unsupervised data {yj} to perform semi-supervised training via an interpolation of (2) and (4). We will do so in our experiments. 7 Our approach may be applied to other tasks as well. For example, in a speech recognition task, δ θ is a speech recognizer that produces text, whereas p φ is a speech synthesizer that must produce a distribution over audio (or at least over acoustic features or phone sequences) (Huang et al., 2010). (4) is the reverse prediction model p φ (·|·) that attempts to impute the missing x i . We will train this model in advance, doing the best job we can from available data, including any outof-domain bilingual data as well as any in-domain monolingual data 8 x.

The Reverse Prediction Model
In the MT setting, δ θ and p φ may have similar parameterization. One translates Chinese to English; the other translates English to Chinese.
Yet the setup is not quite symmetric. Whereas δ θ is a translation system that aims to produce a single, low-loss translation, the reverse version p φ is rather a probabilistic model. It is supposed to give an accurate probability distribution over possible values x ij of the missing input sentence x i . All of these values are taken into account in (4), regardless of the loss that they would incur if they were evaluated for translation quality relative to the missing x i .
Thus, φ does not need to be trained to minimize the risk itself (so there is no circularity). Ideally, it should be trained to match the underlying conditional distribution of x given y, by achieving a low conditional cross-entropy 2σ 2 φ 2 2 on some bilingual data, with the regularization coefficient σ 2 tuned on held out data.
It may be tolerable for p φ to impute mediocre translations x ij . All that is necessary is that the (forward) translations generated from the imputed x ij "simulate" the competing hypotheses that we would see when translating the correct Chinese input x i .

The Forward Translation System δ θ and
The Loss Function L(δ θ (x i ), y i ) The minimum empirical risk objective of (2) is quite general and various popular supervised training methods (Lafferty et al., 2001;Collins, 2002;Och, 2003;Crammer et al., 2006;Smith and Eisner, 2006) can be formalized in this framework by choosing different functions for δ θ and L(δ θ (x i ), y i ). The generality of (2) extends to our minimum imputed risk objective of (4). Below, we specify the δ θ and L(δ θ (x i ), y i ) we considered in our investigation.

Deterministic Decoding
A simple translation rule would define If this δ θ (x) is used together with a loss function L(δ θ (x i ), y i ) that is the negated BLEU score 9 , our minimum imputed risk objective of (4) is equivalent to MERT (Och, 2003) on the imputed training data. However, this would not yield a differentiable objective function. Infinitesimal changes to θ could result in discrete changes to the winning output string δ θ (x) in (6), and hence to the loss L(δ θ (x), y i ). Och (2003) developed a specialized line search to perform the optimization, which is not scalable when the number of model parameters θ is large.

Randomized Decoding
Instead of using the argmax of (6), we assume during training that δ θ (x) is itself random, i.e. the MT system randomly outputs a translation y with probability p θ (y | x). As a result, we will modify our objective function of (4) to take yet another expectation over the unknown y. Specifically, we will replace L(δ θ (x), y i ) in (4) with y p θ (y | x) L(y, y i ).
Now, the minimum imputed empirical risk objective of (4) becomes If the loss function L(y, y i ) is a negated BLEU, this is equivalent to performing minimum-risk training described by (Smith and Eisner, 2006;Li and Eisner, 2009) on the imputed data. 10 9 One can manipulate the loss function to support other methods that use deterministic decoding, such as Perceptron (Collins, 2002) and MIRA (Crammer et al., 2006). 10 Again, one may manipulate the loss function to support other probabilistic methods that use randomized decoding, such as CRFs (Lafferty et al., 2001). (8) is now differentiable, since each coefficient p θ (y | x) is a differentiable function of θ, and thus amenable to optimization by gradient-based methods; we use the L-BFGS algorithm (Liu et al., 1989) in our experiments. We perform experiments with the syntax-based MT system Joshua (Li et al., 2009a), which implements dynamic programming algorithms for second-order expectation semirings (Li and Eisner, 2009) to efficiently compute the gradients needed for optimizing (8).

Approximating
As mentioned at the end of Section 3.1, it is computationally infeasible to forward-translate each of the imputed reverse translations x ij . We propose four approximations that are computationally feasible. Each may be regarded as a different approximation of p φ (x | y i ) in equations (4) or (8).
k-best. For each y i , add to the imputed training set only the k most probable translations {x i1 , . . . x ik } according to p φ (x | y i ). (These can be extracted from X i using standard algorithms (Huang and Chiang, 2005).) Rescale their probabilities to sum to 1.
Sampling. For each y i , add to the training set k independent samples {x i1 , . . . x ik } from the distribution p φ (x | y i ), each with weight 1/k. (These can be sampled from X i using standard algorithms (Johnson et al., 2007).) This method is known in the literature as multiple imputation (Rubin, 1987).
Lattice. 11 Under certain special cases it is be possible to compute the expected loss in (3) exactly via dynamic programming. Although X i does contain exponentially many translations, it may use a "packed" representation in which these translations share structure. This representation may furthermore enable sharing work in forward-translation, so as to efficiently translate the entire set X i and obtain a distribution over translations y. Finally, the expected loss under that distribution, as required by equation (3), may also be efficiently computable.
All this turns out to be possible if (a) the posterior distribution p φ (x | y i ) is represented by an un-ambiguous weighted finite-state automaton X i , (b) the forward translation system δ θ is structured in a certain way as a weighted synchronous context-free grammar, and (c) the loss function decomposes in a certain way. We omit the details of the construction as beyond the scope of this paper.
In our experimental setting described below, (b) is true (using Joshua), and (c) is true (since we use a loss function presented by Tromble et al. (2008) that is an approximation to BLEU and is decomposable). While (a) is not true in our setting because X i is a hypergraph (which is ambiguous), Li et al. (2009b) show how to approximate a hypergraph representation of p φ (x | y i ) by an unambiguous WFSA. One could then apply the construction to this WFSA 12 , obtaining an approximation to (3). Rule-level Composition. Intuitively, the reason why the structure-sharing in the hypergraph X i (generated by the reverse system) cannot be exploited during forward translating is that when the forward Hiero system translates a string x i ∈ X i , it must parse it into recursive phrases.
But the structure-sharing within the hypergraph of X i has already parsed x i into recursive phrases, in a way determined by the reverse Hiero system; each translation phrase (or rule) corresponding to a hyperedge. To exploit structure-sharing, we can use a forward translation system that decomposes according to that existing parse of x i . We can do that by considering only forward translations that respect the hypergraph structure of X i . The simplest way to do this is to require complete isomorphism of the SCFG trees used for the reverse and forward translations. In other words, this does round-trip imputation (i.e., from y to x, and then to y ) at the rule level. This is essentially the approach taken by .

The Log-Linear Model p θ
We have not yet specified the form of p θ . Following much work in MT, we begin with a linear model where f (x, y) is a feature vector indexed by k. Our deterministic test-time translation system δ θ simply 12 Note that the forward translation of a WFSA is tractable by using a lattice-based decoder such as that by Dyer et al. (2008). outputs the highest-scoring y for fixed x. At training time, our randomized decoder (Section 3.3.2) uses the Boltzmann distribution (here a log-linear model) p θ (y | x) = e γ·score(x,y) Z(x) = e γ·score(x,y) y e γ·score(x,y ) (10) The scaling factor γ controls the sharpness of the training-time distribution, i.e., the degree to which the randomized decoder favors the highest-scoring y. For large γ, our training objective approaches the imputed risk of the deterministic test-time system while remaining differentiable.
In a task like MT, in addition to the input x and output y, we often need to introduce a latent variable d to represent the hidden derivation that relates x to y. A derivation d represents a particular phrase segmentation in a phrase-based MT system (Koehn et al., 2003) and a derivation tree in a typical syntaxbased system (Galley et al., 2006;Chiang, 2007). We change our model to assign scores not to an (x, y) pair but to the detailed derivation d; in particular, now the function f that extracts a feature vector can look at all of d. We replace y by d in (9)-(10), and finally define p θ (y|x) by marginalizing out d, where D(x, y) represents the set of derivations that yield x and y.

Minimum Imputed Risk vs. EM
The notion of imputing missing data is familiar from other settings (Little and Rubin, 1987), particularly the expectation maximization (EM) algorithm, a widely used generative approach. So it is instructive to compare EM with minimum imputed risk. One can estimate θ by maximizing the loglikelihood of the data {(x i , y i ), i = 1, . . . , N } as If the x i 's are missing, EM tries to iteratively maximize the marginal probability: 924 The E-step of each iteration comprises computing x p θt (x | y i ) log p θ (x, y i ), the expected loglikelihood of the complete data, where p θt (x | y i ) is the conditional part of p θt (x, y i ) under the current iterate θ t , and the M-step comprises maximizing it: (14) Notice that if we replace p θt (x|y i ) with p φ (x | y i ) in the equation above, and admit negated loglikelihood as a loss function, then the EM update (14) becomes identical to (4). In other words, the minimum imputed risk approach of Section 3.1 differs from EM in (i) using an externally-provided and static p φ , instead of refining it at each iteration based on the current p θt , and (ii) using a specific loss function, namely negated log-likelihood.
So why not simply use the maximum-likelihood (EM) training procedure for MT? One reason is that it is not discriminative: the loss function (e.g. negated BLEU) is ignored during training.
A second reason is that training good joint models p θ (x, y) is computationally expensive. Contemporary MT makes heavy use of log-linear probability models, which allow the system designer to inject phrase tables, linguistic intuitions, or prior knowledge through a careful choice of features. Computing the objective function of (14) in closed form is difficult if p θ is an arbitrary log-linear model, because the joint probability p θ (x i , y i ) is then defined as a ratio whose denominator Z θ involves a sum over all possible sentence pairs (x, y) of any length.
By contrast, our discriminative framework will only require us to work with conditional models. While conditional probabilities such as p φ (x | y) and p θ (y | x) are also ratios, computing their denominators only requires us to sum over a packed forest of possible translations of a given y or x. 13 In summary, EM would impute missing data using p θ (x | y) and predict outputs using p θ (y | x), both being conditional forms of the same joint model p θ (x, y). Our minimum imputed risk training method is similar, but it instead uses a pair of

Experimental Results
We report results on Chinese-to-English translation tasks using Joshua (Li et al., 2009a), an open-source implementation of Hiero (Chiang, 2007).

IWSLT Task
We train both reverse and forward baseline systems. The translation models are built using the corpus for the IWSLT 2005 Chinese to English translation task (Eck and Hori, 2005), which comprises 40,000 pairs of transcribed utterances in the travel domain. We use a 5-gram language model with modified Kneser-Ney smoothing (Chen and Goodman, 1998), trained on the English (resp. Chinese) side of the bitext. We use a standard training pipeline and pruning settings recommended by (Chiang, 2007).

NIST Task
For the NIST task, the TM is trained on about 1M parallel sentence pairs (about 28M words in each language), which are sub-sampled from corpora distributed by LDC for the NIST MT evaluation using a sampling method implemented in Joshua. We also used a 5-gram language model, trained on a data set consisting of a 130M words in English Gigaword (LDC2007T07) and the bitext's English side.

Feature Functions
We use two classes of features f k for discriminative training of p θ as defined in (9).

Regular Hiero Features
We include ten features that are standard in Hiero (Chiang, 2007). In particular, these include one baseline language model feature, three baseline translation models, one word penalty feature, three features to count how many rules with an arity of zero/one/two are used in a derivation, and two features to count how many times the unary and binary glue rules in Hiero are used in a derivation.

Target-rule Bigram Features
In this paper, we do not attempt to discriminatively tune a separate parameter for each bilingual rule in the Hiero grammar. Instead, we train several hundred features that generalize across these rules.
For each bilingual rule, we extract bigram features over the target-side symbols (including nonterminals and terminals). For example, if a bilingual rule's target-side is "on the X 1 issue of X 2 " where X 1 and X 2 are non-terminals (with a position index), we extract the bigram features on the, the X, X issue, issue of, and of X. (Note that the position index of a non-terminal is ignored in the feature.) Moreover, for the terminal symbols, we will use their dominant POS tags (instead of the symbol itself). For example, the feature the X becomes DT X. We use 541 such bigram features for IWSLT task (and 1023 such features for NIST task) that fire frequently.

IWSLT Task
In addition to the 40,000 sentence pairs used to train the baseline generative models (which are used to compute the features f k ), we use three bilingual data sets listed in Table 1, also from IWSLT, for discriminative training: one to train the reverse model p φ (which uses only the 10 standard Hiero features as described in Section 5.2.1), 14 one to train the forward model δ θ (which uses both classes of features described in Section 5.2, i.e., 551 features in total), and one for test.
Note that the reverse model φ is always trained using the supervised data of Dev φ, while the forward model θ may be trained in a supervised or semisupervised manner, as we will show below.
In all three data sets, each Chinese sentence x i has 16 English reference translations, so each y i is actually a set of 16 translations. When we impute data from y i (in the semi-supervised scenario), we 14 Ideally, we should train φ to minimize the conditional cross-entropy (5) as suggested in section 3.2. In the present results, we trained φ discriminatively to minimize risk, purely for ease of implementation using well versed steps.

Data set Purpose
# of sentences Chinese English Dev φ training φ 503 503×16 Dev θ training θ 503 * 503×16 Eval θ testing 506 506×16 Table 1: IWSLT Data sets used for discriminative training/test. Dev φ is used for discriminatively training of the reverse model φ, Dev θ is for the forward model, and Eval θ is for testing. The star * for Dev θ emphasizes that some of its Chinese side will not be used in the training (see Table 2 for details).
actually impute 16 different values of x i , by using p φ to separately reverse translate each sentence in y i . This effectively adds 16 pairs of the form (x i , y i ) to the training set (see section 3.4), where each x i is a different input sentence (imputed) in each case, but y i is always the original set of 16 references.

NIST Task
For the NIST task, we use MT03 set (having 919 sentences) to tune the component parameters in both the forward and reverse baseline systems. Additionally, we use the English side of MT04 (having 1788 sentences) to perform semi-supervised tuning of the forward model. The test sets are MT05 and MT06 (having 1082 and 1099 sentences, respectively). In all the data sets, each source sentence has four reference translations.

Main Results
We compare two training scenarios: supervised and semi-supervised. The supervised system ("Sup") carries out discriminative training on a bilingual data set. The semi-supervised system ("+Unsup") additionally uses some monolingual English text for discriminative training (where we impute one Chinese translation per English sentence).
Tables 2 and 3 report the results for the two tasks under two training scenarios. Clearly, adding unsupervised data improves over the supervised case, by at least 1.3 BLEU points in IWSLT and 0.5 BLEU in NIST.

Results for Analysis Purposes
Below, we will present more results on the IWSLT data set to help us understand the behavior of the 926   Table 3: BLEU scores for semi-supervised training for NIST task. The "Sup" system is trained on MT03, while the "+Unsup" system is trained with additional 1788 English sentences from MT04. (Note that while MT04 has 1788×4 English sentences as it has four sets of references, we only use one such set, for computational efficiency of discriminative training.) A star * indicates a result that is signicantly better than the "Sup" baseline (paired permutation test, p < 0.05). methods proposed in this paper.

Imputation with Different Reverse Models
A critical component of our unsupervised method is the reverse translation model p φ (x | y). We wonder how the performance of our unsupervised method changes when the quality of the reverse system varies. To study this question, we used two different reverse translation systems, one with a language model trained on the Chinese side of the bitext ("WLM"), and the other one without using such a Chinese LM ("NLM").  Table 4: BLEU scores for unsupervised training with/without using a language model in the reverse system. A data size of 101 means that we use only the English sentences from a subset of Dev θ containing 101 Chinese sentences and 101×16 English translations; for each English sentence we impute the 1-best Chinese translation. "WLM" means a Chinese language model is used in the reverse system, while "NLM" means no Chinese language model is used. In addition to reporting the BLEU score on Eval θ, we also report "Imputed-CN BLEU", the BLEU score of the imputed Chinese sentences against their corresponding Chinese reference sentences.
BLEU point in the forward translations. Still, even with the worse imputation (in the case of "NLM"), our forward translations improve as we add more monolingual data.

Imputation with Different k-best Sizes
In all the experiments so far, we used the reverse translation system to impute only a single Chinese translation for each English monolingual sentence. This is the 1-best approximation of section 3.4. Table 5 shows (in the fully unsupervised case) that the performance does not change much as k increases. 16 This may be because that the 5-best sentences are likely to be quite similar to one another (May and Knight, 2006). Imputing a longer k-best list, a sample, or a lattice for x i (see section 3.4) might achieve more diversity in the training inputs, which might make the system more robust.  Table 5: BLEU scores for unsupervised training with different k-best sizes. We use 101×16 monolingual English sentences, and for each English sentence we impute the k-best Chinese translations using the reverse system. the expected loss of the forward translations with respect to the observed output) is minimized. This matches the intuition that the probabilistic "roundtrip" translation from the target-language sentence to the source-language and back should have low expected loss. We applied our method to two Chinese to English machine translation tasks (i.e. IWSLT and NIST). We showed that augmenting supervised data with unsupervised data improved performance over the supervised case (for both tasks).
Our discriminative model used only a small amount of training data and relatively few features. In future work, we plan to test our method in settings where there are large amounts of monolingual training data (enabling many discriminative features). Also, our experiments here were performed on a language pair (i.e., Chinese to English) that has quite rich bilingual resources in the domain of the test data. In future work, we plan to consider lowresource test domains and language pairs like Urdu-English, where bilingual data for novel domains is sparse.