Optimization for Statistical MachineTranslation: A Survey
Graham Neubig∗

Taro Watanabe∗∗†Graduate School of Information Science
Nara Institute of Science and Technology

Google Inc.

In statistical machine translation (SMT), the optimization of the system parameters to maximize
translation accuracy is now a fundamental part of virtually all modern systems. In this article,
we survey 12 years of research on optimization for SMT, from the seminal work on discriminativemodels (Och and Ney 2002) and minimum error rate training (Och 2003), to the most recent
advances. Starting with a brief introduction to the fundamentals of SMT systems, we follow bycovering a wide variety of optimization algorithms for use in both batch and online optimization.
Specifically, we discuss losses based on direct error minimization, maximum likelihood, maximum margin, risk minimization, ranking, and more, along with the appropriate methods forminimizing these losses. We also cover recent topics, including large-scale optimization, nonlinear models, domain-dependent optimization, and the effect of MT evaluation measures orsearch on optimization. Finally, we discuss the current state of affairs in MT optimization,and point out some unresolved problems that will likely be the target of further research in
optimization for MT.
1. Introduction
Machine translation (MT), has long been both one of the most promising applicationsof natural language processing technology, and one of the most elusive. However, overapproximately the past decade, huge gains in translation accuracy have been achieved(Graham et al. 2014), and commercial systems deployed for hundreds of language
pairs are being used by hundreds of millions of users. There are many reasons forthese advances in the accuracy and coverage of MT, but among them two particularly
stand out: statistical machine translation (SMT) techniques that make it possible to learn
statistical models from data, and massive increases in the amount of data available tolearn SMT models.
Within the SMT framework, there have been two revolutions in the way we mathematically model the translation process. The first was the pioneering work of Brown etal. (1993), who proposed the idea of SMT, and described methods for estimation of theparameters used in translation. In this work, the parameters of a word-based generativetranslation model were optimized to maximize the conditional likelihood of the training∗ 8916-5 Takayama-cho, Ikoma, Nara, Japan. E-mail: neubig@is.naist.jp∗∗ 6-10-1 Roppongi, Minato-ku, Tokyo, Japan. E-mail: tarow@google.com† This work was mostly done while the second author was affiliated with National Institute of Information
and Communications Technology, 3-5 Hikaridai, Seika-cho, Soraku-gun, Kyoto, 619-0289, Japan.
Submission received: 3rd June, 2014; revised version received: 18th March, 2015; accepted for publication:
11th October, 2015.

© 2006 Association for Computational Linguistics

Computational Linguistics

Which Loss Functions?
Error (§3.1)
Softmax (§3.2)
Risk (§3.3)
Margin, Perceptron (§3.4)
Ranking (§3.5)
Minimum Squared Error (§3.6)

Volume 1, Number 1

Which Optimization Algorithm?
Minimum Error Rate Training (§5.1)
Gradient-based Methods (§5.2, §6.5)
Margin-based Methods (§5.3)
Linear Regression (§5.4)
Perceptron (§6.2)
MIRA (§6.3)
AROW (§6.4)
Which Hypotheses to Target?
k-best vs. Lattice vs. Forest (§2.4)
Merged k-bests (§5)
Forced Decoding (§2.4), Oracles (§4)

Which Evaluation Measure?
Corpus-level, Sentence Level (§2.5)
BLEU and Approximations (§2.5.1, §2.5.2)
Other Measures (§8.3)
Other Topics:
Large Data Sets (§7), Non-linear Models (§8.1),
Domain Adaptation (§8.2), Search and Optimization (§8.4)

Table 1: A road map of the various elements that affect MT optimization.

corpus. The second major advance in SMT is the discriminative training framework
proposed by Och and Ney (2002) and Och (2003), which propose log-linear models forMT, optimized to maximize either the probability of getting the correct sentence froma k-best list of candidates, or to directly achieve the highest accuracy over the entire
corpus. By describing the scoring function for MT as a flexibly parameterizable loglinear model, and describing discriminative algorithms to optimize these parameters, it
became possible to think of MT like many other structured prediction problems, suchas POS tagging or parsing (Collins 2002).
However, within the general framework of structured prediction MT stands apart inmany ways, and as a result requires a number of unique design decisions not necessary
in other frameworks (as summarized in Table 1). The first is the search space that must
be considered. The search space in MT, is generally too large to expand exhaustively, so
it is necessary to decide which subset of all the possible hypotheses should be used in
optimization. In addition the evaluation of MT accuracy is not straightforward, with
automatic evaluation measures for MT still being researched to this day. From theoptimization perspective, even once we have chosen an automatic evaluation metric,
it is not necessarily the case that it can be decomposed for straightforward integration
with structured learning algorithms. Given this evaluation measure, it is necessary toincorporate it into a loss function to target. The loss function should be closely related
to the final evaluation objective, while allowing for the use of efficient optimization algorithms. Finally, it is necessary to choose an optimization algorithm. In many cases it ispossible to choose a standard algorithm from other fields, but there are also algorithms
that have been tailored towards the unique challenges posed by MT.
In this article, we survey the state of the art in machine translation optimization in acomprehensive and systematic fashion, covering a wide variety of topics, with a unified
set of terminology. In Section 2, we first provide definitions of the problem of machinetranslation, describe briefly how models are built, how features are defined, and howtranslations are evaluated, and finally define the optimization setting. In Section 3, we
next describe a variety of loss functions that have been targeted in machine translation2

Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

optimization. In Section 4, we explain about selection of oracle translations, a nontrivial process that directly affects the optimization results. In Section 5, we describe
batch optimization algorithms, starting with the popular minimum error rate training,and continuing with other approaches using likelihood, margin, rank loss, or risk as
objectives. In Section 6, we describe online learning algorithms, first explaining the relationship between corpus-level optimization and sentence-level optimization, and thenmoving on to algorithms based on perceptron, margin, or likelihood-based objectives.
In Section 7, we describe the recent advances in scaling training of MT systems up tolarge amounts of data through parallel computing, and in Section 8, we cover a numberof other topics in MT optimization such as non-linear models, domain adaptation, andthe relationship between MT evaluation and optimization. Finally, we conclude with
9, overviewing the methods described, making a brief note about which methods see
the most use in actual systems, and outlining some of the unsolved problems in the
optimization of MT systems.
2. Machine Translation Preliminaries and Definitions
Before delving into the details of actual optimization algorithms, we first introduce preliminaries and definitions regarding MT in general and the MT optimization problem inparticular. We focus mainly on the aspects of MT that are relevant to optimization, andreaders may refer to Koehn (2010) or Lopez (2008) for more details about MT in general.
2.1 Machine Translation
Machine translation is the problem of automatically translating from one natural language to another. Formally, we define this problem by specifying F to be the collectionof all source sentences to be translated, f ∈ F as one of the sentences, and E(f ) as thecollection of all possible target language sentences that can be obtained by translating f .
Machine translation systems perform this translation process by dividing the translationof a full sentence into the translation and recombination of smaller parts, which are
represented as hidden variables, which together form a derivation.
For example, in phrase-based translation (Koehn, Och, and Marcu 2003), the hidden
variables will be the alignment between the phrases of the source and target sentences,and in tree-based translation models (Yamada and Knight 2001; Chiang 2007), thehidden variables will represent the latent tree structure used to generate the translation.
We will define D(f ) to be the space of possible derivations that can be acquired fromsource sentence f , and d ∈ D(f ) to be one of those derivations. Any particular derivation d will correspond to exactly one e ∈ E(f ), although the opposite is not true (thederivation uniquely determines the translation, but there can be multiple derivations
corresponding to a particular translation). We also define tuple he, di consisting of atarget sentence and its corresponding derivation, and T (f ) ⊆ E(f ) × D(f ) as the set of
all of these tuples.
Because the set of all possible translations E(f ) will contain both good and badtranslations, it is necessary to have a method to identify and output the good translations. In order to do so, in machine translation it is common to define a linear
model that determines the score of each translation candidate. In this linear model
we first define an M -dimensional feature vector for each output and its derivation ash(f , e, d) : F × E × D → RM . For each feature, we also define a corresponding weight,
resulting in an M -dimensional weight vector w ∈ RM . Based on these feature andweight vectors, we proceed to define the problem of selecting the best he, di as the3Computational Linguistics

Volume 1, Number 1

following maximization problem
hê, d̂i = arg max w> h(f , e, d),(1)he,di∈T (f )where the dot product of the parameters and features is equivalent to the score assigned
to a particular translation.
The optimization problem that we will be surveying in this article is generally
concerned with finding the most effective weight vector w from the set of possible
weight vectors RM .1 Optimization is also widely called tuning in the SMT literature.
In addition, because of the exponentially large number of possible translations in E(f )that must be considered, it is necessary to take advantage of the problem structure,making MT optimization an instance of structured learning.
2.2 Model Construction
The first step of creating a machine translation system is model construction, in whichtranslation models (TMs) are extracted from a large parallel corpus. The TM is usuallycreated by first aligning the parallel text (Och and Ney 2003), using this text to extract
multi-word phrases pairs or synchronous grammar rules (Koehn, Och, and Marcu 2003;
Chiang 2007), and scoring these rules according to several features explained in moredetail in Section 2.3. The construction of the TM is generally performed first in a mannerthat does not directly consider the optimization of translation accuracy, and followed by
an optimization step that explicitly considers the accuracy achieved by the system.2 In
this survey, we will focus on the optimization step, and thus do not cover elements
of model construction that do not directly optimize an objective function related totranslation accuracy, but interested readers can reference Koehn (2010) for more details.
In the context of this article, however, the TM is particularly important in the roleit plays in defining our derivation space D(f ). For example, in the case of phrase-basedtranslation, only phrase pairs included in the TM will be expanded during the processof searching for the best translation (explained in Section 2.4).
This has major implications from the point of view of optimization, the most important of which being that we must use separate data for training the TM and optimizing
the parameters w. The reason for this lies in the fact that the TM is constructed in such a
way that allows it to “memorize” long multi-word phrases included in the training data.
Using the same data to train the model parameters will result in overfitting, learningparameters that heavily favor using these memorized multi-word phrases, which will
not be present in a separate test set.
The traditional way to solve this problem is to train the TM on a large parallel
corpus on the order of hundreds of thousands to tens of millions of sentences, thenperform optimization of parameters on a separate set of data consisting of around one
thousand sentences, often called the development set. When learning the weights forlarger feature sets, however, a smaller development set is often not sufficient, and it iscommon to perform cross-validation, holding out some larger portion of the training

1 It should be noted that while most work on MT optimization is concerned with linear models, and thus
we will spend the majority of this paper discussing optimization of these models, optimization using
non-linear models is also possible, and discussed in Section 8.1.
2 It should also be noted there have been a few recent attempts to jointly perform rule extraction andoptimization, doing away with this two-step process (Xiao and Xiong 2013).

4

Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

set for parameter optimization. It is also possible to perform leaving-one-out training,where counts of rules extracted from a particular sentence are subtracted from themodel before translating the sentence (Wuebker, Mauser, and Ney 2010).
2.3 Features for Machine Translation
Given this overall formulation of MT, the features h(f , e, d) that we choose to use torepresent each translation hypothesis are of great importance. In particular, with regards
to optimization, there are two important distinctions between types of features: local vs.
non-local, and dense vs. sparse.
With regards to the first distinction, local features, such as phrase translation probabilities, do not require additional contexts from other partial derivations, and they arecomputed independently from one another. On the other hand, when features for aparticular phrase pair or synchronous rule cannot be computed independently fromother pairs, they are called non-local features. This distinction is important, as local
features will not result in an increase in the size of the search space, while non-local
features have the potential to make search more difficult.
The second distinction is between dense features, which define a small number ofhighly informative feature functions, and sparse features, which define a large numberof less informative feature functions. Dense features are generally easier to optimize,both from a computational point of view because the smaller number of features reduces computational and memory requirements, and because the smaller number ofparameters reduces the risk of overfitting. On the other hand, sparse features allow
for more flexibility, as their parameters can be directly optimized to increase translation
accuracy, so if optimization is performed well they have the potential to greatly increasetranslation accuracy. The remainder of this section describes some of the widely usedfeatures in more detail.
2.3.1 Dense Features:. Dense features, which are generally continuously valued andpresent in nearly all translation hypotheses, are used in the majority of machine translation systems. The most fundamental set of dense features are phrase/rule translation
probabilities or relative frequencies in which the log of sentence-wise probability
distributions p(f |e) and p(e|f ), are split into the sum of phrase or rule log probabilities
hφ (f , e, d) =X

log pφ (α|β),hφ0 (f , e, d) =P

hα,βi∈d log pφ0 (β|α).

(2)hα,βi∈d

Here α and β are the source and target sides of a phrase pair or rule. These features are
estimated using counts of each phrase derived from the training corpus as follows:count(α, β),0α0 count(α , β)pφ (α|β) = P

count(α, β).
0
β 0 count(α, β )pφ0 (β|α) = P(3)In addition, it is also common to use lexical weighting, which estimates parameters
for each phrase pair or rule by further decomposing them into word-wise probabilities(Koehn, Och, and Marcu 2003). This helps more accurately estimate the reliability ofphrase pairs or rules that have low counts. It should be noted that all of these features
can be calculated directly from the rules themselves, and are thus local features.

5Computational Linguistics

Volume 1, Number 1

Another set of important features are language models (LMs) which capture thefluency of translation e, and are usually modeled by n-gramshlm (f , e, d) =|e|
Xlog plm (ei |ei−1
i−n+1 ).

(4)i=1

Note that the n-gram LM is computed over e regardless of the boundaries of phrase
pairs or rules in the derivation, and is thus a non-local feature.
The n-gram language model assigns higher penalties for longer translations, and
it is common to add a word penalty feature that measures the length of translation e
to compensate for this. Similarly, phrase penalty or rule penalty features express thetrade-off between longer or shorter derivations. There exist other features which aredependent on the underlying MT system model. Phrase-based MT heavily relies on
the distortion probabilities which are computed by the distance on the source side oftarget-adjacent phrase pairs. More refined lexicalized reordering models estimate theparameters from the training data based on the relative distance of two phrase pairs(Tillman 2004; Galley and Manning 2008).
2.3.2 Sparse features:. While dense features form the foundation of most SMT systems,in recent years the ability to define richer feature sets and directly optimize the systemusing rich features has been shown to allow for significant increases in accuracy. On theother hand, large and sparse feature sets make the MT optimization problem significantly harder, and many of the optimization methods we will cover in the rest of thissurvey are aimed at optimizing rich feature sets.
The first variety of sparse features that we can think of are phrase features orrule features, which count the occurrence of every phrase or rule. Of course, it is only
possible to learn parameters for a translation rule if it exists in the training data used in
optimization, so when using a smaller data set for optimization it is difficult to robustly
learn these features. Chiang, Knight, and Wang (2009) have noted that this problem canbe alleviated by only selecting and optimizing the more frequent of the sparse features.
Simianer, Riezler, and Dyer (2012) also propose features using the “shape” of translation
rules, transforming a ruleX → hne X 1 pas, did not X 1 i(5)

into a string simply indicating whether each word is a terminal (T) or non-terminal (N)N → hT N T, T T Ni.

(6)Count-based features can also be extended to cover other features of the translation,such as phrase or rule bigrams, indicating which phrases or rules tend to be used
together (Simianer, Riezler, and Dyer 2012).
Another alternative for the creation of features that are sparse, but less sparse thanfeatures of phrases or rules, is lexical features (Watanabe et al. 2007). Lexical features,
similar to lexical weighting, focus on the correspondence between the individual words
that are included in a phrase or rule. The simplest variety of lexical features remembers
which source words f are aligned with which target words e, and fires a feature foreach pair. It is also possible to condition lexical features on the surrounding context
in the source language (Chiang, Knight, and Wang 2009; Xiao et al. 2011), fire features6

Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

between every pair of words in the source or target sentences (Watanabe et al. 2007),or integrate bigrams on the target side (Watanabe et al. 2007). Of these, the former two
can be calculated from source and local target context, but target bigrams require target
bigram context and are thus non-local features.
One final variety of features that has proven useful is syntax-based features (Marton and Resnik 2008; Blunsom and Osborne 2008). In particular, phrase-based andhierarchical phrase-based translation do not directly consider syntax (in the linguistic
sense) in the construction of the models, so introducing this information in the form offeatures has a potential for benefit. One way to introduce this information is to parsethe input sentence before translation, and use the information in the parse tree in thecalculation of features. For example, we can count the number of times a phrase ortranslation rule matches, or partially matches (Marton and Resnik 2008), a span witha particular label, based on the assumption that rules that match a syntactic span are
more likely to be syntactically reasonable.
2.3.3 Summary features:. While sparse features are useful, training of sparse features is
an extremely difficult optimization problem, and at this point there is still no methodthat has been widely demonstrated as being able to robustly estimate the parameters of
millions of features. Due to this fact, a third approach of first training the parameters ofsparse features, then condensing the sparse features into dense features and performing
one more optimization pass (potentially with a different algorithm), has been widelyused in a large number of research papers and systems (Dyer et al. 2009; He and Deng2012; Flanigan, Dyer, and Carbonell 2013; Setiawan and Zhou 2013). A dense feature
created from a large group of sparse features and their weights is generally called asummary feature, and can be expressed as follows
hsum (f , e, d) = w>
sparse hsparse (f , e, d).

(7)

There has also been work that splits sparse features into not one, but multiple groups,
creating a dense feature for each group (Xiang and Ittycheriah 2011; Liu et al. 2013).
2.4 Decoding
Given an input sentence f , the task of decoding is defined as an inference problemof finding the best scoring derivation hê, d̂i according to Equation (1). In general theinference is intractable if we enumerate all possible derivations in T (f ) and rank each
derivation by the model. We assume that a derivation is composed of a set of steps
d = d1 , d2 , · · · , d|d|(8)where each dj is a step, e.g., a phrase pair in phrase-based MT or a synchronous rule intree-based MT, ordered in a particular way. We also assume that each feature function
can be decomposed over each step, and Equation 1 can be expressed byhê, d̂i = arg max
he,di∈T (f )

|w|
X
i

wi

|d|
X

hi (dj , ρi (dj−1
1 ))

(9)

j=1

7

Computational Linguistics

Volume 1, Number 1

where hi (dj , ρi (dj−11 )) is a feature function for the jth step decomposed from the globalfeature function of hi (f , e, d). As mentioned in the previous section, non-local features
require information that can not be calculated directly from the rule itself, and ρi (d1j−1 )is a variable that defines the residual information to score this ith feature function using
the partial derivation dj−1
(Gesmundo and Henderson 2011; Green, Cer, and Manning12014). For example, in phrase-based translation, for an n-gram language model feature,ρi (dj−1
1 ) will be the n − 1 word suffix of the partial translation (Koehn, Och, and Marcu
2003). The local feature functions, such as phrase translation probabilities in Section
2.3.1, require no context from partial derivations, and thus ρi (d1j−1 ) = ∅.
The problem of decoding is treated as a search problem in which partial derivationsḋ together with ρi (ḋ) in Equation (9) are enumerated to form hypotheses or states. In
phrase-based MT, search is carried out by enumerating partial derivations in left-toright order on the target side while remembering the translated source word positions.
Similarly, the search in MT with synchronous grammars is performed by using theCYK+ algorithm (Chappelier and Rajman 1998) on the source side and generating
partial derivations for progressively longer source spans. Due to the enormous search
space brought about by maintaining ρi (ḋ) in each partial derivation, beam search isused to heuristically prune the search space. As a result, search is inexact due to thesearch error caused by heuristic pruning, in which the best scoring hypothesis is notnecessarily optimal in terms of given model parameters.
The search is efficiently carried out by merging equivalent states encoded as ρ
(Koehn, Och, and Marcu 2003; Huang and Chiang 2007), and the space is succinctly
represented by compact data structures, such as graphs (Ueffing, Och, and Ney 2002)(or lattices) in phrase-based MT (Koehn, Och, and Marcu 2003) and hypergraphs (Klein
and Manning 2004) (or packed forests) in tree-based MT (Huang and Chiang 2007).
These data structures may be directly employed as compact representations of allderivations for optimization.
However, using these data structures directly can be unwieldly, and thus it is morecommon to obtain a k-best list as an approximation of the derivation space. Figure 1(a)shows an example of k-best English translations for a French input sentence, “la délégation chinoise appuiera pleinement la présidence .” The k-best list may be obtained
either from a lattice in Figure 1(b) or from a forest in Figure 1(c). It should be noted thatdifferent derivations in a k-best list may share the same translation due to the variationof phrases or rules in constructing a translation, e.g., the choice of “support the chair”
or “support” and “the chair” in Figure 1(b). A diverse k-best list can be obtained byextracting a unique k-best list which maintains only the best scored derivation sharing
the same translation (Hasan, Zens, and Ney 2007; Huang, Knight, and Joshi 2006),
by incorporating a penalty term when scoring derivations (Gimpel et al. 2013), or by
performing Monte-Carlo sampling to acquire a more diverse set of candidates (Blunsom
and Osborne 2008).
Another class of decoding problem is forced decoding in which the output from a
decoder is forced to match with a reference translation of the input sentence. In phrasebased MT, this is implemented by adding additional features to reward hypotheses thatmatch with the given target sentence (Liang, Zhang, and Zhao 2012; Yu et al. 2013). In
MT using synchronous grammars, it is carried out by biparsing over two languages,
for instance, by a variant of the CYK algorithm (Wu 1997) or by a more efficient twostep algorithm (Dyer 2010b; Peitz et al. 2012). Even if we perform forced decoding,
we are still not guaranteed that the decoder will be able to produce the referencetranslation (due to unknown words, reordering limits, or other factors). This problem

8

Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

the delegation of china will support the chair in full .
the chinese delegation will fully support the chair .
the chinese delegation will fully support the presidency .
the delegation of china will in full support the presidency .
the china delegation will in full support the chair .
(a) k-best

X
X X.
of
delegationchinesethechinachinesesupport the chairchina
in fullwill

X will X .
X support X

supportfully

the chair.

the X X

will support X X
the X of X

will X support X

fully
fully
the presidencychinesesupportdelegation china
in full the presidency
in fulldelegation(b) lattice(c) forest

the chair

Figure 1: k-best list, lattice and forest

can be resolved by preserving the prefix of partial derivations (Yu et al. 2013), or byallowing approximate matching of the target side (Liang, Zhang, and Zhao 2012). It
is also possible to create a neighborhood of a forced decoding derivation by adding
additional hyperedges to the true derivation, which allows for efficient generation ofnegative examples for discriminative learning algorithms (Xiao et al. 2011).
2.5 Evaluation
Once we have a machine translation system that can produce translations, we next must
perform evaluation to judge how good the generated translations actually are. As the
final consumer of machine translation output is usually a human, the most natural formof evaluation is manual evaluation by human annotators. However, due to the fact thathuman evaluation is expensive and time consuming, in recent years there has been ashift to automatic calculation of the quality of MT output.
In general, automatic evaluation measures use a set of data consisting of N inputnoNNsentences F = f (i), each of which having a reference translation E = e(i) i=1
i=1

that was created by a human translator. The input F is automatically translated usingnoN
a machine translation system to acquire MT results Ê = ê(i), which are theni=1

compared to the corresponding references. The closer the MT output is to the reference,
the better it is deemed to be according to automatic evaluation. In addition, as there
are often many ways to translate a particular sentence, it is also possible to perform
evaluation with multiple references created by different translators. There has also beensome work on encoding a huge number of references in a lattice, created either by hand(Dreyer and Marcu 2012) or by automatic paraphrasing (Zhou, Lin, and Hovy 2006).
One major distinction between optimization measures is whether they are calculated on the corpus level or the sentence level. Corpus-level measures are calculated
by taking statistics over the whole corpus, while sentence-level measures are calculated
by measuring a sentence-level accuracy, and defining the corpus-level accuracy as theaverage of the sentence-level accuracies. All optimization algorithms that are applicable9Computational Linguistics

Volume 1, Number 1

to corpus-level measures are applicable to sentence-level measures, but the opposite is
not true, making this distinction important from the optimization point of view.
The most commonly used MT evaluation measure BLEU (Papineni et al. 2002) isdefined on the corpus level, and we will cover it in detail as it plays an important rolein some of the methods that follow. Of course, there have been many other evaluation
measures proposed since BLEU, with TER (Snover et al. 2006) and METEOR (Banerjee
and Lavie 2005) being among the most widely used. The great majority of metrics otherthan BLEU are defined on the sentence level, and thus are conducive to optimization
algorithms that require sentence-level evaluation measures. We discuss the role ofevaluation in MT optimization more completely in Section 8.3.
2.5.1 BLEU. BLEU is defined as the geometric mean of n-gram precisions (usually forn from 1 to 4), and a brevity penalty to prevent short sentences from receiving unfairly
high evaluation scores. For a single reference sentence e and a corresponding system
output ê, we can define cn (ê) as the number of n-grams in ê, and mn (e, ê) as the numberof n-grams in ê that match e
cn (ê) = |{gn ∈ ê}|mn (e, ê) = |{gn ∈ ê} ∩ {g 0 n ∈ e}| .
Here, {gn ∈ ê} and {g 0 n ∈ e} are multisets that can contain identical n-grams more thanonce, and ∩ is an operator for multisets that allows for consideration of multiple instances of the same n-gram.3 Note that the total count for a candidate n-gram is clipped
to be no more than the count in the reference translation. If we have a corpus of reference(i)(i)
sets R = {e(1) , . . . , e(N ) }, where each sentence has M references e(i) = {e1 , . . . , eM },(1)(N )the BLEU score of the corresponding system outputs E = {ê , . . . , ê } can be defined as

BLEU(E, Ê) =

4
Y
n=1

(i)

PN

(i)

(i)
i=1 mn ({e1 , . . . , eM }, ê )PN(i)
i=1 cn (ê )! 14· BP(E, Ê),

(10)

where the first term corresponds to geometric mean of the n-gram precisions, and thesecond term BP(E, Ê) is the brevity penalty. The brevity penalty is necessary here
because evaluation of precision favors systems that output only the words and phrases
that have high accuracy, and avoids outputting more difficult-to-translate content thatmight not match the reference. The brevity penalty prevents this by discounting outputs
that are shorter than the reference(BP(E, Ê) = min 1, exp

PN(i)i=1 |ẽ |1 − PN(i)i=1 |ê |

!)
(11)

,

where ẽ(i) is defined as the longest reference with a length shorter than or equal to ê(i) .

3 We let #A (a) denote the number of times a appeared in a multiset A, and define: |A| =#A∪B (a) = max{#A (a), #B (a)} and #A∩B (a) = min{#A (a), #B (a)}.

10P

a #A (a),Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

2.5.2 BLEU+1. One thing to notice here is that BLEU is calculated by taking statistics
over the entire corpus, and thus it is a corpus-level measure. There is nothing inherently
preventing us from calculating BLEU on a single sentence, but in the single-sentencecase it is common for the number of matches of higher order n-grams to become zero,
resulting in a BLEU score of zero for the entire sentence. One common solution to thisproblem is the use of a smoothed version of BLEU commonly referred to as BLEU+1(Lin and Och 2004). In BLEU+1, we add one to the numerators and denominators ofeach n-gram of order greater than one
c0n (ê) = |{gn ∈ ê}| + δ(n > 1)
m0n (e, ê) = |{gn ∈ ê} ∩ {g 0 n ∈ e}| + δ(n > 1),
where δ(·) is a function that takes a value of 1 when the corresponding statement is true.
We can then re-define a sentence-level BLEU using these smoothed counts
1

BLEU’(e, ê) =


4  0
Y
m ({e1 , . . . , eM }, ê) 4nn=1

c0n (ê)· BP(e, ê),(12)

and the corpus-level evaluation can be re-defined as the average of sentence levelevaluations
N

BLEU’(E, Ê) =1 X
BLEU’(e(i) , ê(i) ).
N i=1

(13)

It has also been noted, however, that the average of sentence-level BLEU+1 is not avery accurate approximation of corpus-level BLEU, but by adjusting the smoothingheuristics it is possible to achieve a more accurate approximation (Nakov, Guzman, andVogel 2012).
2.6 The Optimization Setting
During the optimization process, we will assume that we have some data consisting ofoNnNsources F = f (i)with corresponding references E = e(i) i=1 as defined in thei=1

previous section, and that we would like to use these to opimize the parameters of themodel. As mentioned in Section 2.5, it is also possible to use more than one referencetranslation in evaluation, but in this survey we will assume for simplicity of exposition
that only one reference is used.
When we select a certain weight vector w, this will affect the scores calculated
according to the model, and thus the result acquired during decoding, as describedin Section 2.4. To express whether this effect is a positive or negative one, we define aloss function `(F, E; w) : F N × E N × RM → R that provides a numerical indicator of
how “bad” the translations generated when we use a particular w are. As the goal of
optimization is to achieve better translations, we would like to choose parameters that
reduce this loss. More formally, we can cast the problem as minimizing the expectationof `(·), or risk minimizationŵ = arg min EP r(F,E) [`(F, E; w)].

(14)

w∈RM

11

Computational Linguistics

Volume 1, Number 1Here, P r(F, E) is the true joint distribution over all sets of input and output sentencesthat we are likely to be required to translate. However, in reality we will not know thetrue distribution over all sets of sentences a user may ask us to translate. Instead, we
have a single set of data (henceforth, training data), and attempt to find the w thatminimizes the loss on this dataŵ = arg min `(F, E; w).

(15)

w∈RM

Because we are now optimizing on a single empirically derived set of training data, thisframework is called empirical risk minimization.
In machine learning problems, it is common to introduce regularization to preventthe learning of parameters that over-fit the training data. This gives us the framework of
regularized empirical risk minimization, which will encompass most of the methods
described in this survey, and is formalized asŵ = arg min `(F, E; w) + λΩ(w),

(16)

w∈RM

where λ is a parameter adjusting the strength of regularization, and Ω(w) is a regularization term, common choices for which include the L2 regularizer Ω2 (w) = 21 kwk22 =PM1 >m=1 |wm | (Chen and Rosenfeld 1999;
2 w w or the L1 regularizer Ω1 (w) = kwk1 =Tibshirani 1996). Intuitively, if λ is set to a small value, optimization will attempt tolearn a w that effectively minimizes loss on the training data, but there is a risk of overfitting reducing generalization capability. On the other hand, if λ is set to a larger value,
optimization will be less aggressive in minimizing loss on the training data, reducing
over-fitting, but also possibly failing to capture useful information that could be used to
improve accuracy.
3. Defining a Loss Function
The first step in performing optimization is defining the loss function that we areinterested in optimizing. The choice of a proper loss function is critical in that it effects
the final performance of the optimized MT system, and also the possible choices for optimization algorithms. This section describes several common choices for loss functions,and describes their various features.
3.1 Error
The first, and most straightforward, loss that we can attempt to optimize is error(Och 2003). We assume that by comparing the decoder’s translation result Ê withthe reference E, we are able to calculate a function error(E, Ê) : E N × E N → R≥0 that
describes the extent of error included in the translations. For example, if we use the
BLEU described in Section 2.5 as an evaluation measure for our system, it is natural
to use 1 - BLEU as an error function, so that as our evaluation improves, the error
decreases. Converting this to a loss function that is dependent on the model parameters,
we obtain the following loss expressing the error over the 1-best results obtained by

12Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

decoding in Equation (1)



)N 

(

`error (F, E, C; w) = error E, arg max w> h(f (i) , e, d)he,di∈c(i)

.

(17)

i=1

Error has the advantage of being simple, easy to explain, and directly related totranslation performance, and these features make it perhaps the most commonly used
loss in current machine translation systems. On the other hand, it also has a large
disadvantage in that the loss function expressed in Equation (17) is not convex, andmost MT evaluation measures used in the calculation of the error function error(·)
are not continuously differentiable. This makes direct minimization of error a difficult
optimization problem (particularly for larger feature sets), and thus a number of other,easier-to-optimize losses are used as well.
A special instance of error, which is worth mentioning due to its relation to themethods we will introduce in the following sections, is zero–one loss. Zero–one loss
focuses on whether an oracle translation is chosen as the system output. Oracle translations can be vaguely defined as “good” translations, such as the reference translatione(i) , or perhaps the best translation in the k-best list (described in detail in Section 4). If
we define the set of oracle translations for sentence i as o(i) , zero–one loss is defined byplugging the following zero–one error function into Equation (17):

N

1 X
error(E, Ê) =1 − δ(ê(i) ∈ o(i) ) ,
N i=1

(18)

where ê(i) is the one-best translation candidate, and δ(ê(i) ∈ o(i) ) is one if ê(i) is amember of o(i) and zero otherwise.

3.2 Softmax Loss
One thing to note about error is that there is no concept of “probability” of eachtranslation candidate incorporated in its calculation. Being able to define a well-scaled
probability of candidates can be useful, however, for estimation of confidence measuresor incorporation with downstream applications. Softmax loss is a loss that is similar to
the zero–one loss, but directly defines a probabilistic model and attempts to maximize
the probability of the oracle translations (Berger, Pietra, and Pietra 1996; Och and Ney
2002; Blunsom, Cohn, and Osborne 2008).
In particular, if we assume that MT is modeled according to the log-linear model

exp(w> h(f , e, d))0 ,>0he0 ,d0 i∈c exp(w h(f , e , d ))pw (e, d|f , c) = P

(19)

13

Computational Linguistics

Volume 1, Number 1

we can define softmax loss `softmax (·) as follows:N`softmax (F, E, C; w) = −

1 Y
N i=1

X

pw (e, d|f (i) , c(i) )(20)

he,di∈o(i)

P
(i)
N
>
1 Y he,di∈o(i) exp(w h(f , e, d)).
=−P
N i=1 he,di∈c(i) exp(w> h(f (i) , e, d))(21)

From Equation (21), we can see that only the oracle translations contribute to thenumerator, while all candidates in c(i) contributes to the denominator. Thus, intuitively,
the softmax objective prefers parameter settings that assign high scores to the oracletranslations, and lower scores to any other members of c(i) that are not oracles.
It should be noted that this loss can be calculated from a k-best list by iterating overthe entire list and calculating the numerators and denominators in Equation (19). It isalso possible, but more involved, to calculate over lattices or forests by using dynamic
programming algorithms such as the forward–backward or inside–outside algorithms(Blunsom, Cohn, and Osborne 2008; Gimpel and Smith 2009).
3.3 Risk-based Loss
In contrast to softmax loss, which can be viewed as a probabilistic version of zero–one
loss, risk defines a probabilistic version of the translation error (Smith and Eisner 2006;
Zens, Hasan, and Ney 2007; Li and Eisner 2009; He and Deng 2012). Specifically, risk
is based on the expected error incurred by a probabilistic model parameterized by w.
This combines the advantages of the probabilistic model in softmax loss with the direct
consideration of translation accuracy afforded by using error directly. In comparison toerror, it also has the advantage of being differentiable, allowing for easier optimization.
To define this error, we define a scaling parameter γ ≥ 0 and use it in the calculationof each hypothesis’s probabilityexp(γw> h(f , e, d))0 .
>0he0 ,d0 i∈c exp(γw h(f , e , d ))pγ,w (e, d|f , c) = P(22)

Given this probability, we then calculate the expected loss as follows
N`risk (F, E, C; γ, w) =

1 X
(i)
E
, e)]
(i) (i) [err(eN i=1 pγ,w (e,d|f ,c )

(23)

N

1 X
=
N i=1

X

err(e(i) , e)pγ,w (e, d|f (i) , c(i) ).

(24)

he,di∈c(i)In Equation (22), when γ = 0 regardless of parameters w every hypothesis he, di will
be assigned a uniform probability, and when γ = 1 the probabilities are equivalent tothose in the log-linear model of Equation (19). When γ → ∞, the probability of thehighest-scored hypothesis will approach 1, and thus our objective will approach theerror defined in Equation (17). This γ can be adjusted in a way that allows for more
effective search of the parameter space, as described in more detail in Section 5.5.

14

Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

3.4 Margin-based Loss
The zero–one loss in Section 3.1 was based on whether the oracle received a higherscore than other hypotheses. The idea of margin, which is behind the classification
paradigm of support vector machines (SVMs) (Joachims 1998), takes this a step further,finding parameters that explicitly maximize the distance, or margin, between correctand incorrect candidates. The main advantage of margin-based methods is that they areable to consider the error function, and often achieve high accuracy. These advantages
make margin-based methods perhaps the second most popular loss used in current MT
systems after direct minimization of error.
This margin-based objective can be defined as the loss below:N`margin (F, E, C; w) =1 X
N (C) i=1

X

X

he∗ ,d∗ i∈o(i) he,di∈c(i) \o(i)nomax 0, ∆ err(e(i) , e∗ , e) − w> ∆h(f (i) , e∗ , d∗ , e, d) , (25)where we define∆ err(e, e∗ , e0 ) = err(e, e0 ) − err(e, e∗ )
∗

∗

0

0

∗

∗

0

(26)
0

∆h(f , e , d , e , d ) = h(f , e , d ) − h(f , e , d ).

(27)

In Equation (25), we first specify that for each pair of oracle candidates o(i) , and nonoracle candidates c(i) \ o(i) , the margin w> ∆h(·) between oracle e∗ and non-oracle eshould be greater than the difference in the error ∆ err(·).4 We then define the loss as thetotal amount that this margin is violated. In this loss calculation, the number of pairsP(i)is N (C) = N\ o(i) | · |o(i) |. Note that here err(·) is not calculated on the corpus
i=1 |clevel, but on the sentence level, and may not directly correspond to our corpus-level
error error(·).
It is also common to consider the case where we calculate this loss with regards toonly a single translation candidate and oracle, and this is often called hinge loss. If we(i)define hê(i) , d̂ i ∈ c(i) \ o(i) as the 1-best translation candidate(i)hê(i) , d̂ i =arg maxw> h(f (i) , e, d),(28)he,di∈c(i) \o(i)and he∗(i) , d∗(i) i ∈ o(i) as the oracle translation
he∗(i) , d∗(i) i = arg min err(e(i) , e),(29)he,di∈o(i)4 Eq. (25) can be regarded as an instance of ranking loss described in Section 3.5 in which bettertranslations are selected only from a set of oracle translations.

15Computational Linguistics

Volume 1, Number 1

the hinge loss can be defined as follows

N

1 X
N i=1
n
o
(i)
max 0, ∆ err(e∗(i) , e∗ , e) − w> ∆h(f (i) , e∗(i) , d∗(i) , ê(i) , d̂ ) . (30)`hinge (F, E, C; w) =A special instance of this hinge loss that is widely used in machine translation, and machine learning in general, is perceptron loss (Liang et al. 2006), which further removes
the term considering the error, and simply incurs a penalty if the one-best candidate
receives a higher score than the oracle`perceptron (F, E, C; w) =

N
n
o
(i)
1 X
max 0, −w> ∆h(f (i) , e∗(i) , d∗(i) , ê(i) , d̂ ) .
N i=1

(31)

In addition to maximizing the margin itself, there has also been work on maximizing the relative margin (Eidelman, Marton, and Resnik 2013). To explain the relative
margin, we first define the worst hypothesis as(i)hĕ(i) , d̆ i = arg max err(e(i) , e)(32)he,di∈c(i)and then calculate the spread ∆ err(e(i) , ė(i) , ĕ(i) ), which is the difference of errors
(i)

(i)

between the oracle hypothesis hė(i) , ḋ i and worst hypothesis hĕ(i) , d̆ i. An additionalterm can then be added to the objective function to penalize parameter settings withlarge spreads. The intuition behind the relative margin criterion is that in addition toincreasing the margin, considering the spread reduces the variance between the nonoracle hypotheses. Given an identical margin, having a smaller variance indicates thatan unseen hypothesis will be less likely to pass over the margin and be misclassified.
3.5 Ranking Loss
Perceptron and margin losses attempted to distinguish between oracle and non-oracle
hypotheses. This can be considered a specific instance of the more general ranking
framework (Herbrich, Graepel, and Obermayer 1999; Freund et al. 2003; Burges et al.
2005; Cao et al. 2007), where for an arbitrary pair of translation candidates, a binaryclassifier is trained to distinguish which of the two candidates has the lower error. If aparticular pair of candidates in the training data hek , dk i and hek0 , dk0 i is ranked in thecorrect order, the following condition is satisfied:err(e(i) , ek ) < err(e(i) , ek0 )⇐⇒ w> h(f (i) , ek , dk ) > w> h(f (i) , ek0 , dk0 ).

16

Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

This can be expressed aserr(e(i) , ek ) < err(e(i) , ek0 )⇐⇒ w> h(f (i) , ek , dk ) > w> h(f (i) , ek0 , dk0 )⇐⇒ w> h(f (i) , ek , dk ) − w> h(f (i) , ek0 , dk0 ) > 0⇐⇒ w> h(f (i) , ek , dk ) − h(f (i) , ek0 , dk0 ) > 0⇐⇒ w> ∆h(f (i) , ek , dk , ek0 , dk0 ) > 0,
where ∆h(f (i) , ek , dk , ek0 , dk0 ) can be treated as training data to be classified using any
variety of binary classifier. Each binary decision made by this classifier becomes anindividual choice, and thus the ranking loss is the sum of these individual losses. As thebinary classifier, it is possible to use perceptron, hinge, or softmax losses between thecorrect and incorrect answers.
It should be noted that standard ranking techniques make a hard decision between
candidates with higher and lower error, which can cause problems when the ranking
by error does not correlate well with the ranking measured by the model. The crossentropy ranking loss solves this problem by softly fitting the model distribution to the
distribution of ranking measured by errors (Green et al. 2014).
3.6 Mean Squared Error Loss
Finally mean squared error loss is another method that does not make a hard zero–one decision between the better and worse candidates, but instead attempts to directly
estimate the difference in scores (Bazrafshan, Chung, and Gildea 2012). This is done by
first finding the difference in errors between the two candidates ∆ err(e(i) , e∗ , e) anddefining the loss as the mean squared error of the difference between the inverse of thedifference in the errors and the difference in the model scores5
N`mse (F, E, C; w) =1 X
N (C) i=1

X

X

he∗ ,d∗ i∈o(i) he,di∈c(i)−∆ err(e(i) , e∗ , e) − w> ∆h(f (i) , e∗ , d∗ , e, d)2. (33)

4. Choosing Oracles
In the previous section, many loss functions used oracle translations, which are defined
as a set of translations for any sentence that are “good.” Choosing oracle translations is
not a trivial task, and in this section we describe the details involved.
4.1 Bold vs. Local Updates
In other structured learning tasks such as part of speech tagging or parsing, it is common
to simply use the correct answer as an oracle. In translation, this is equivalent to
5 We take the inverse because we would like model scores and errors to be inversely correlated.

17

Computational Linguistics

Volume 1, Number 1

optimizing towards an actual human reference, which is called bold update (Liang etal. 2006). It should be noted that even if we know the reference e, we still need to obtaina derivation d, and thus it is necessary to perform forced decoding (described in Section2.4) to obtain this derivation.
However, bold update has a number of practical difficulties. For example, we are
not guaranteed that the decoder is able to actually produce the reference (for example,
in the case of unknown words), in which case forced decoding will fail. In addition, even
if the hypothesis exists in the search space, it might require a large change in parameters
w to ensure that the reference gets a higher score than all other hypotheses. This is truein the case of non-literal translations, for example, which may be producible by the
decoder, but only through using a derivation that would normally receive an extremely
low probability.
Local update is an alternative method that selects an oracle from a set of hypotheses
produced during the normal decoding process. The space of hypotheses used to selectoracles is usually based on k-best lists, but can also include lattices or forests output
by the decoder as described in Section 2.4. Due to the previously mentioned difficulties
with bold update, it has been empirically observed that local update tends to outperform bold update in online optimization (Liang et al. 2006). However, it also makes it
necessary to select oracle translations from a set of imperfect decoder outputs, and wewill describe this process in more detail in the following section.
4.2 Selecting Oracles and Approximating Corpus-level Error
First, we define o(i) ⊆ c(i) as the set of oracle translations, derivation-translation pairsin c(i) that minimize the error function
O=

 n
oN 
arg min error E, o(i) ⊆ c(i).
i=1N{o(i) ⊆c(i) }i=1

(34)

One thing to note here is that error(·) is a corpus-level error function. As mentioned in
Section 2.5, evaluation measures for MT can be classified into those that are decomposable on the sentence level, and those that are not. If this error function can be composedas the sum of sentence-level errors, such as BLEU+1, choosing the oracle is simple;
we simply need to find the set of candidates that have the lowest error independently
sentence by sentence.6
However, when using a corpus-level error function we need a slightly more sophisticated method, such as the greedy method of Venugopal and Vogel (2005). In thismethod (Figure 2), the oracle is first initialized either as an empty set or by randomly
picking from the candidates. Next, we iterate randomly through the translation candidates in c(i) , try replacing the current oracle o(i) with the candidate, and check thechange in the error function (Line 9), and if the error decreases, replace the oracle withthe tested candidate. This process is repeated until there is no change in O.

6 More accurately, finding the oracle in the k-best list by enumeration of the hypotheses is easy, but finding
the oracle in a compressed data structure such as a lattice is computationally difficult, and approximation
algorithms are necessary (Leusch, Matusov, and Ney 2008; Li and Khudanpur 2009; Sokolov, Wisniewski,
and Yvon 2012a).

18

Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

1: procedure O RACLE(hF, E, Ci)
2:
3:
4:
5:
6:
7:
8:
9:


N
O = o(i) i=1
o(i) ← {he, di ∼ c(i) } or o(i) ← ∅repeatfor i ∈ P ERMUTE({1, . . . , N }) do . Random ordero(i) ← ∅s←∞for k ∈ {1, . . . , K} do(1)(i−1)

s0 ← error E, {o1 , . . . , o1

(i)

(i+1)

, ck , o1(N ), . . . , o1 }

if s0 < s then. Update the oracle
(i)
(i)
11:
o ← {ck }12:s ← s013:
else if s0 = s then. Same error value(i)14:o(i) ← o(i) ∪ {ck }15:
end if16:
end for17:
end for18:
until convergence . If O doesn’t change, converged
19:
return O
20: end procedure
10:

Figure 2: Greedy search for an oracle

4.3 Selecting Oracles for Margin-based Methods
Considering the hinge loss of Equation (30), the 1-best and oracle candidates are acquired according to Equation (28) and Equation (29) respectively, and the loss is calculated according to Equation (31). In order to minimize this loss, we would like to selectthe pair with the largest loss, and update so that the loss gets smaller. However, it is not(i)necessarily the case that the candidates with the maximum model score hê(i) , d̂ i andminimum loss he∗(i) , d∗(i) i form the pair with the minimal margin. Thus, when using
margin-based objectives, it is common to modify the criterion for selecting candidates
to use in the update as follows (Chiang, Marton, and Resnik 2008; Chiang, Knight, andWang 2009):(i)hē(i) , d̄ i = arg max w> h(f (i) , e, d) + err(e(i) , e)(35)he,di∈c(i)(i)

hė(i) , ḋ i = arg max w> h(f (i) , e, d) − err(e(i) , e).

(36)he,di∈c(i)

(i)

(i)

(i)

Thus we can replace hê(i) , d̂ i and he∗(i) , d∗(i) i with hē(i) , d̄ i and hė(i) , ḋ i, resulting
in a margin of
(i)

(i)

∆ err(e(i) , ė(i) , ē(i) ) − w> ∆h(f (i) , ė(i) , ḋ , ē(i) , d̄ ),

(37)

19

Computational Linguistics

Volume 1, Number 1

1: procedure B ATCH L EARN (hF, Ei =noN
hf (i) , e(i) i)i=1w(1) ← ∅N
C = c(i) ≡ ∅ i=1. k-best Listfor t ∈ {1 . . . T } dofor i ∈ {1 . . . N } dokbest(i) ← GEN(f (i) , w(t) ) . Decode with w(t)7:c(i) ← c(i) ∪ kbest(i). k-best Merging
8:
end for9:w(t+1) ← arg minw∈RM `(F, E, C; w) + λΩ(w). Optimization
10:
end for11:
return w(T +1)
12: end procedure
2:
3:
4:
5:
6:

Figure 3: Batch optimization

which is the largest margin in the k-best list. Explaining more intuitively, this criterion
provides a bias towards selecting hypotheses with high error, making the learningalgorithm work harder to correctly classify very bad hypotheses than it does for hypotheses that are only slightly worse than the oracle. Inference methods that consider
the loss as in Equations (35) and (36) are called loss-augmented inference (Taskar et al.
2005) methods, and can minimize losses with respect to the candidate with the largest
violation. Gimpel and Smith (2012) take this a step further, defining a structured ramp
loss that additionally considers Equations (28) and (29) within this framework.
5. Batch Methods
Now that we have explained the details of calculating loss functions used in machinetranslation, we turn to the actual algorithms used in optimizing using these loss functions. In this section, we cover batch learning approaches to MT optimization. Batch
learning works by considering the entire training data on every update of the parameters, in contrast to online learning (covered in the following section), which considers
only part of the data at any one time. In standard approaches to batch learning, forevery training example hf (i) , e(i) i we enumerate every translation and derivation in
the respective sets E(f (i) ) and D(f (i) ), and attempt to adjust the parameters so we canachieve the translations with the lowest error for the entire data.
However, as mentioned previously, the entire space of derivations is too large tohandle in practice. To resolve this problem, most batch learning algorithms for MT
follow the general procedure shown in Figure 3, performing iterations that alternate
between decoding and optimization (Och and Ney 2002). In Line 6, GEN(f (i) , w(t) ) =
n
oK
(i)
(i)
hek , dk i
indicates that we use the current parameters w(t) to perform decoding
k=1

of sentence f (i) , and obtain a sub-set of all derivations. For convenience, we will assume
that this subset is expressed using a k-best list kbest(i) , but it is also possible to use
lattices or forests as explained in Section 2.4.
A k-best list with scores for each hypothesis can be used as an approximation
for the distribution over potential translations of f (i) according to the parameters w.

20

Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

However, because the size of the k-best list is limited, and the presence of searcherrors in decoding means that we are not even guaranteed to find the highest-scoring
hypotheses, this approximation is far from perfect. The effect of this approximation isparticularly obvious if the lack of coverage of the k-best list is systematic. For example, if
the hypotheses in the k-best list are all much too short, optimization may attempt to fix
this by adjusting the parameters to heavily favor very long hypotheses, far overshooting
the actual optimal parameters.7
As a way to alleviate the problems caused by this approximation, in Line 7 wemerge the k-best lists from multiple decoding iterations, finding a larger and moreaccurate set C of derivations. Given C and the training data hF, Ei, we perform
minimization of the Ω(w) regularized loss function `(·) and obtain new parametersw(t+1) (Line 9). Generation of k-best lists and optimization is performed until a hard
limit of T iterations is reached, or until training has converged. In this setting, usuallyconvergence is defined as any iteration in which the merged k-best list does not change,or when the parameters w do not change (Och 2003).
Within this batch optimization framework, the most critical challenge is to findan effective way to solve the optimization problem in Line 9 of Figure 3. Section 5.1
describes methods for directly optimizing the error function. There are also methods
for optimizing other losses such as those based on probabilistic models (Section 5.2),
error margins (Section 5.3), ranking (Section 5.4), and risk (Section 5.5).
5.1 Error Minimization
5.1.1 Minimum Error Rate Training Overview. Minimum error rate training (MERT)(Och 2003) is one of the first, and is currently the most widely used method for MT
optimization, and focuses mainly on direct minimization of the error described in
Section 3.1. Because error is not continuously differentiable, MERT uses optimization
methods that do not require the calculation of a gradient, such as iterative line searchinspired by Powell’s method (Press et al. 2007; Och 2003), or the Downhill-Simplex
method (Nelder-Mead method) (Press et al. 2007; Zens, Hasan, and Ney 2007; Zhao
and Chen 2009).
The algorithm for MERT using line search is shown in Figure 4. Here, we assume
that w and h(·) are M -dimensional, and bm is an M -dimensional vector where the mth element is 1 and the rest of the elements are zero. For the T iterations, we decide
the dimension m of the feature vector (Line 6), and for each possible weight vector
w(j) + γbm choose the γ ∈ R that minimizes `error (·) using line search (Line 7). Then,among the γ for each of the M search dimensions, perform update using γ̂ that affords
the largest reduction in error (Line 9 and 10). This algorithm can be deemed a variety ofsteepest descent, which is a standard implementation most implementations of MERT
(Koehn et al. 2007). Another alternative is a variant of coordinate descent, e.g., Powell’smethod, in which search and update is performed in each dimension.
One feature of MERT is that it is known to easily fall into local optima of the error
function. Because of this, it is standard to choose R starting points (Line 4), perform
optimization starting at each of these starting points, and finally choose the ŵ thatminimizes the loss from the weights acquired from each of the R random restarts. The
R starting points are generally chosen so that one of the points is the best w from the

7 Liu et al. (2012) propose a method to avoid over-aggressive moves in parameter space by considering thebalance between increase in the evaluation score and the similarity to the parameters on the previous
iteration.

21

Computational Linguistics

Volume 1, Number 1

1: procedure MERT(F, E, C)
2:ŵ ← ∅
3:for r ∈ {1 . . . R} dow(1) ∼ RM. Initialize randomly
for t ∈ {1 . . . T } do
. Until convergencefor m ∈ {1 . . . M } do
. For each dimensionγ̂ m ← arg minγ `error (F, E, C; w(t) + γbm ) . Search
end forγ̂ ← arg minγ̂ m `error (F, E, C; w(t) + γ̂ m bm ) . Descent10:w(t+1) ← w(t) + γ̂bm
. Update11:
end for12:
if `error (F, E, C; w(T +1) ) < `error (F, E, C; ŵ) then13:ŵ ← w(T +1)
14:
end if15:
end for16:
return ŵ
17: end procedure
4:
5:
6:
7:
8:
9:

Figure 4: Minimum error rate training (MERT)

previous iteration, and the remaining R − 1 have each element of w chosen randomly
and uniformly from some interval, although it has also been shown that more intelligent
choice of initial points can result in better final scores (Moore and Quirk 2008).
5.1.2 Line Search for MERT. While the majority of this process is relatively straightforward, the line search in Line 7 of Figure 4 requires a bit more explanation. In thisstep, we would like to choose the γ that results in the ordering of hypotheses in c(i) that
achieves the lowest error. In order to do so, MERT uses an algorithm that allows forexact enumeration of which of the K candidates in c(i) will be chosen for each value of
γ. Concretely, we defineno>arg max w(j) + γbm h(f (i) , e, d)(38)

he,di∈c(i)>= arg max w(j) h(f (i) , e, d) +γ · hm (f (i) , e, d)
{z
}
|
{z
}
he,di∈c(i) |(39)= arg max a(f (i) , e, d) + γ · b(f (i) , e, d),(40)intercept

slope

he,di∈c(i)where each hypothesis he, di in c(i) of Equation (40) is expressed as a line with intercept>a(f (i) , e, d)(= w(j) h(f (i) , e, d)) and slope b(f (i) , e, d)(= hm (f (i) , e, d)) with γ as aparameter. Equation (40) is a function that returns the translation candidate with thehighest score. We can define a function g(γ; f (i) ) that corresponds to the score of thishighest-scoring candidate as follows:g(γ; f (i) ) =max a(f (i) , e, d) + γ · b(f (i) , e, d).
he,di∈c(i)

22

(41)

Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation(i)g(γ; f (i) )

c1

(i)

(i)
c2

c3

(i)

c4
γ

Figure 5: An example of hypotheses as lines

We can see that Equation (41) is a piecewise linear function (Papineni 1999; Och 2003),
as at any given γ ∈ R the translation candidate with the highest score a(·) + γ · b(·)
will be selected, and this score corresponds to the line that is in the highest position atthat particular γ. In Figure 5, we show an example with the following four translation
candidates:
(i)

(i)

c1 : 2.5 + γ · (−0.8), c2 : 1 + γ · (−0.2)
.
(i)
(i)
c3 : 2 + γ · (−0.5), c4 : −0.5 + γ · 0.2(42)

If we set γ to a very small value such as −∞, the candidate with the smallest slope, in(i)this example c1 , will be chosen. Furthermore, if we make γ gradually larger, we will(i)
see that c1 continues to be the highest scoring candidate until we reach the intersection(i)(i)
of c1 and c3 at
2.5 − 2
≈ 1.667,(−0.5) − (−0.8)

(43)

(i)

after which c3 will be the highest scoring candidate. If we continue increasing γ, we(i)(i)
will continue by selecting c2 and c4 starting at their corresponding intersections.
A function like Equation (41) that chooses the highest-scoring line for each spanover γ is called an envelope, and can be used to compactly express the results wewill obtain by rescoring c(i) according to a particular γ (Figure 6(a)). After finding theenvelope, for each line that participates in the envelope, we can calculate the sufficient
statistics necessary for calculating the loss `error (·) and error error(·). For example, given
the envelope in Figure 6(a), Figure 6(b) is an example of the sentence-wise loss withrespect to γ.
The envelope in shown in Equation (41) can also be viewed as the problem offinding a convex hull in computational geometry. A standard and efficient algorithm
for finding a convex hull of multiple lines is the sweep line algorithm (Bentley andOttmann 1979; Macherey et al. 2008) (see Figure 7). Here, we assume L is a set of thelines corresponding to the K translation candidates in c(i) , each line l ∈ L is expressed
as ha(l), b(l), γ(l)i with intercept a(l) = a(f (i) , e, d), and slope b(l) = b(f (i) , e, d). Furthermore, we define γ(l) as an intersection initialized to −∞. S ORT L INES(L) in Figure
3 sorts the lines in the order of their slope b(l), and if two lines lk1 have the same slope
lk2 chooses the one with the larger intercept a(lk1 ) > a(lk2 ) and deletes the other. We
next process the sorted set of lines L0 (|L0 | ≤ K) in order of ascending slope (Lines 4–18). If we assume H is the envelope expressed as the set of lines it contains, we find the23Volume 1, Number 1g(γ; f (i) )Computational Linguisticsγ`error (·)(a) Envelopeγ(b) Loss

Figure 6: An example of line search in MERT

1: procedure S WEEP L INE (L = {ha(l(k) ), b(l(k) ), γ(l(k) )i}K
k=1 )2:
H ← ∅,j ← 1
3:
L0 ← S ORT L INES(L)for l ∈ L0 do
if j > 1 thenwhile j > 1 doa(l)−a(Hj−1 )7:γ(l) ← b(Hj−1 )−b(l)8:if γ(Hj−1 ) < γ(l) then
9:
break
10:
end if11:
j ←j−1
12:
end while
13:
end if14:
if j = 1 then15:γ(l) ← −∞16:
end if17:
Hj ← l,j ← j + 1
18:
end for19:
return H1j−1
20: end procedure
4:
5:
6:

. Intersection of Hj−1 and l. l is in the envelope. The leftmost line

Figure 7: The “sweep line” algorithm

line that intersects with line under consideration at the highest point, (Lines 6–12), andupdate the envelope H. As L contains at most K lines, H’s size is also at most K.
Given a particular input sentence f (i) , its set of translation candidates c(i) , and theresulting envelope H (i) , we can also define the set of intersections between lines in the
(i)
(i)
(i)
(i)
envelope as γ1 < · · · < γj < · · · < γ|H (i) | . We also define ∆`j to be the change in the24Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

(i)

(i)

(i)

(i)

loss function that occurs when we move from one span [γj−1 , γj ) to the next [γj , γj+1 ).
If we first calculate the loss incurred when setting γ = −∞, then process the spans in(i)increasing order, keeping track of the difference ∆`j incurred at each span boundary,
it is possible to efficiently calculate the loss curve over all spans of γ.
In addition, while all explanation of line search to this point has focused on theprocedure for a single sentence, by calculating the envelopes for each sentence in thedata 1 ≤ i ≤ N , and combining these envelopes into a single plane, it is relatively simple
to perform this processing on the corpus level as well. It should be noted that for corpusbased evaluation measures such as BLEU, when performing corpus-level processing,
we do not keep track of the change in the loss, but the change in the sufficient statistics
required to calculate the loss for each sentence. In the case of BLEU, the sufficient
statistics amount to n-gram counts cn , n-gram matches mn , and reference lengths r.
We then calculate the loss curve `error (·) for the entire corpus based on these sufficient
statistics, and find a γ that minimizes Equation (17) based on this curve. By repeating
this line search for each parameter until we can no longer obtain a decrease, it is possible
to find a local minimum in the loss function, even for non-convex or non-differentialfunctions.
5.1.3 MERT’s Weaknesses and Extensions. While MERT is widely used as the standard
optimization procedure for MT, it also has a number of weaknesses, and a number ofextensions to the MERT framework have been proposed to resolve these problems.
The first weakness of MERT is the randomness in the optimization process. Because
each iteration of the training algorithm generally involves a number of random restarts,
the results will generally change over multiple training runs, with the changes often
being quite significant. Some research has shown that this randomness can be stabilized
somewhat by improving the ability of the line-search algorithm to find a globally
good solution by choosing random seeds more intelligently (Moore and Quirk 2008;
Foster and Kuhn 2009) or by searching in directions that consider multiple features atonce, instead of using the simple coordinate ascent as described in Algorithm 4 (Cer,Jurafsky, and Manning 2008). Orthogonally to actual improvement of the results, Clark
et al. (2011) suggest that because randomness is a fundamental feature of MERT andother optimization algorithms for MT, it is better experimental practice to perform
optimization multiple times, and report the resulting means and standard deviations
over various optimization runs.
It is also possible to optimize the MERT objective using other optimization algorithms. For example, Suzuki, Duh, and Nagata (2011) present a method for using
particle swarm optimization, a distributed algorithm where many “particles” are eachassociated with a parameter vector, and the particle updates its vector in a way such thatit moves towards the current local and global optima. Another alternative optimization
algorithm is Galley and Quirk (2011)’s method for using linear programming to perform search for optimal parameters over more than one dimension, or all dimensions
at a single time. However, as MERT remains a fundamentally computationally hard
problem, this method takes large amounts of time for larger training sets or feature
spaces.
It should be noted that instability in MERT is not entirely due to the fact that search
is random, but also due to the fact that k-best lists are poor approximations of the whole
space of possible translations. One way to improve this approximation is by performing
MERT over an exponentially large number of hypotheses encoded in a translation lattice(Macherey et al. 2008) or hypergraph (Kumar et al. 2009). It is possible to perform MERT

25

Computational Linguistics

Volume 1, Number 1

over these sorts of packed data structures by observing the fact that the envelopes
used in MERT can be expressed as a semiring (Dyer 2010a; Sokolov and Yvon 2011),
allowing for exact calculation of the full envelope for all hypotheses in a lattice or
hypergraph using polynomial-time dynamic programming (the forward algorithm orinside algorithm respectively). There has also been work to improve the accuracy of the
k-best approximation by either sampling k-best candidates from the translation lattice(Chatterjee and Cancedda 2010), or performing forced decoding to find derivations that
achieve the reference translation, and adding them to the k-best list (Liang, Zhang, andZhao 2012).
The second weakness of MERT is that it has no concept of regularization, causing
it to overfit the training data if there are too many features, and there have been several
attempts to incorporate regularization to ameliorate this problem. Cer, Jurafsky, andManning (2008) propose a method to incorporate regularization by not choosing theplateau in the loss curve that minimizes the loss itself, but chooses the point considering
the loss values for a few surrounding plateaus, helping to avoid points that have a low
loss, but are surrounded by plateaus with higher loss. It is also possible to incorporate
regularization into MERT-style line search using an SVM-inspired margin-based objective (Hayashi et al. 2009) or by using scale-invariant regularization methods such as L0or a scaled version of L2 (Galley et al. 2013).
The final weakness of MERT is that it has computational problems when scaling tolarge numbers of features. When using only a standard set of 20 or so features, MERT
is able to perform training in reasonable time, but the number of line searches, and thustime, required in Algorithm 4 scales linearly with the number of features. Thus trainingof hundreds of features is time consuming, and there are no published results training
standard MERT on thousands or millions of features. It should be noted however, that
Galley et al. (2013) report results for thousands of features by choosing intelligent search
directions by calculating the gradient of expected BLEU, as explained in Section 5.5.2.
5.2 Gradient-based Batch Optimization
In the previous section, MERT optimized a loss function that was exactly equivalent
to the error function, which is not continuously differentiable and thus precludes theuse of standard convex optimization algorithms used in other optimization problems.
In contrast, other losses such as the softmax loss described in Section 3.2 and risk-based
losses described in Section 3.3 are differentiable, allowing for the use of these algorithms
for MT optimization (Smith and Eisner 2006; Blunsom and Osborne 2008).
Convex optimization is well covered in the standard machine learning literature, so
we do not cover it in depth, but methods such as conjugate gradient (CG, using firstorder statistics) (Nocedal and Wright 2006), the limited-memory Broyden-FletcherGoldfarb-Shanno method (L-BFGS, using second-order statistics) (Liu and Nocedal1989) are standard options for optimizing these losses. These methods are equallyapplicable when the loss is combined with a differentiable regularizer Ω(w), such as
L2 regularization. Using a non-differentiable regularizer such as L1 makes optimization
more difficult, but can be handled by other algorithms such as orthant-wise limitedmemory Quasi-Newton (OWL-QN) (Andrew and Gao 2007).
In addition to the function being differentiable, if it is also convex we can be
guaranteed that these algorithms will not get stuck in local optima and reach a globally
optimal solution. In general, the softmax objective is convex if there is only one elementin the oracle set o(i) , and not necessarily convex if there are multiple oracles. In the caseof MT, as there are usually multiple translations e that minimize error(·), and multiple

26

Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

derivations d that result in the same translation e, o(i) will generally contain multiple
members. Thus, we can not be entirely certain that we will reach a global optimum.

5.3 Margin-Based Optimization
Minimizing the margin-based loss described in Section 3.4, possibly with the additionof a regularizer, is also a relatively standard problem in the machine learning literature.
Methods to solve Equation (25) include sequential minimization optimization (SMO)(Platt 1999), dual coordinate descent (Hsieh et al. 2008), as well as the quadratic
program solvers used in standard SVMs (Joachims 1998).
It should also be noted that there have also been several attempts to apply marginbased online learning algorithms explained in Section 6.3, but in a batch setting where
the whole training corpus is decoded before each iteration of optimization (Cherry andFoster 2012; Gimpel and Smith 2012). While we will explain these methods in moredetail later, it should be noted that the advantage of using these methods in a batch
setting mainly lies in simplicity; for online learning it is often necessary to directly
implement the optimization procedure within the decoder, while in a batch setting
the implementation of the decoding and optimization algorithm can be performed
separately.

5.4 Ranking and Linear Regression Optimization
The rank-based loss described in Section 3.5 is essentially the combination of multiple
losses over binary decisions. These binary decisions can be solved using gradientbased or margin-based methods, and thus optimization itself can be solved with thealgorithms described in the previous two sections. However, one important concern
in this setting is training time. At the worst, the number of pairwise comparisons forany particular k-best list is k(k − 1)/2, leading to unmanageably large amounts of timerequired for training.
One way to alleviate this problem is by randomly sampling a small number ofthese k(k − 1)/2 hypotheses for use in optimization, which has been shown empiricallyto allow for increases in training speed without decreases in accuracy. For example,
Hopkins and May (2011) describe a method dubbed pairwise ranking optimization(PRO) that selects 5,000 pairs randomly for each sentence, and among these random
pairs using the 50 with the largest difference in error for training the classifier. Other selection heuristics, for example avoiding training on candidate pairs with overly different
scores (Nakov, Guzmán, and Vogel 2013), or performing Monte-Carlo sampling (Rothet al. 2010; Haddow, Arun, and Koehn 2011), are also possible and potentially increase
accuracy. Recently, there has also been a method proposed that uses an efficient ranking
SVM formulation that alleviates the need for this sampling and explicitly performs
ranking over all pairs (Dreyer and Dong 2015).
The mean squared error loss described in Section 3.6, which is similar to ranking
loss in that it will prefer a proper ordering of the k-best list, is much easier to optimize.
This loss can be minimized using standard techniques for solving least-squared-error
linear regression (Press et al. 2007).

27

Computational Linguistics

Volume 1, Number 1

5.5 Risk Minimization
The risk-based loss in Section 3.3 is also differentiable and thus can be optimized bygradient-based methods. One thing to note here is that risk objective is highly nonconvex, and thus some care needs to be taken to ensure that optimization does not
fall into a local optimum. The motivation behind introducing the scaling parameter γ in
Equation (22) is that it allows us to control the “peakiness” of the distribution, which canbe useful for optimization. Putting this formally, we first define the entropy of pγ,w (·) asN

H(pγ,w ) = −

1 X
N i=1

X

pγ,w (e, d|f (i) , c(i) ) log pγ,w (e, d|f (i) , c(i) ).

(44)

he,di∈c(i)When γ takes a small value this entropy will be high, indicating that the loss function
is relatively smooth and less sensitive to local optima. Conversely, when γ → ∞, theentropy becomes lower, and the loss function becomes more peaky with more local
optima. It has been noted that this fact can be used for effective optimization throughthe process of deterministic annealing (Sindhwani, Keerthi, and Chapelle 2006). In
deterministic annealing, the parameter γ is not set as a hyperparameter, and instead theentropy H(pγ,w ) is directly used as a regularization function during the optimization
process (Smith and Eisner 2006; Li and Eisner 2009)arg min `risk (F, E, C; γ, w) − T · H(pγ,w ) + λΩ(w).

(45)γ∈R≥0 ,w∈RM

In Equation (45), T is the temperature, which can either be set as a hyperparameter,or gradually decreased from ∞ to −∞ (or 0) through a process of cooling (Smith andEisner 2006). The motivation for cooling is that if we start with a large T , the earlier
steps using a smoother function will allow us approach the global optimum, while thelater steps will allow us to approach the actual error function.
It should be noted that in Equation (24), and the discussion up to this point, wehave been using not the corpus-based error, but the sentence-based error err(e(i) , e).
There have also been attempts to make the risk minimization framework applicable tocorpus-level error error(·), specifically BLEU. We will discuss two such methods.

5.5.1 Linear BLEU. Linear BLEU (Tromble et al. 2008) provides an approximation for
corpus-level BLEU that can be divided among sentences. Linear BLEU uses a Taylor
expansion to approximate the effect that the sufficient statistics of any particular sentence will have on corpus-level BLEU. We define r as the total length of the referencetranslations, c as the total length of the candidates, and cn and mn (1 ≤ n ≤ 4) as thetranslation candidate’s number of n-grams, and number of n-grams that match thereference respectively. Taking the equation for corpus-level BLEU (Papineni et al. 2002)
and assuming that the n-gram counts are approximately equal for 1 ≤ n ≤ 4, we get the28Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

following approximation:4nro 1 Xmnlog BLEU = min 0, 1 −
+
log
c
4 n=1
cn

(46)

4
n
mn
ro 1 X+log.
≈ min 0, 1 −
c
4 n=1
c

(47)

If we assume that when we add the sufficient statistics of a particular sentence e, thecorpus-level statistics change to r0 , c0 , c0n , and m0n , and we can express the change in
BLEU in the logarithm domain as follows∆ log BLEU = log BLEU0 − log BLEU
≈

4
4
m0
1X
mn
1X
log 0n −
log
.
4 n=1
c
4 n=1
c

(48)
(49)

If we make the assumption that there is no change in the brevity penalty, ∆ log BLEU
relies solely on mn and c. ∆ log BLEU can then be approximated using a first-order
Taylor expansion as follows:∆ log BLEU ≈ (c0 − c)=−4X
∂ log BLEU0∂ log BLEU0
0
(m
−
m
)
+
(50)
n
n
∂c0
∂m0n
c0 =c
m0n =mnn=1

4c0 − c 1 X m0n − mn
+
.
c
4 n=1
mn

(51)

As c0 − c is the length of e, and m0n − mn is the number of n-grams (gn ) in e that match(i)the n-grams (gn ) in e(i) , the sentence-level error function errlBLEU (·) for linear BLEU is
errlBLEU (e(i) , e) =4(i)
|e| 1 X |{gn ∈ e} ∩ {gn ∈ e(i) }|
−
.
c
4 n=1
mn

(52)

c and mn are set to a fixed value (Tromble et al. 2008). For example, in the batch optimization algorithm of Figure 3 they can be calculated based on the k-best list generated
prior to optimization.
5.5.2 Expectations of Sufficient Statistics. DeNero, Chiang, and Knight (2009) present
an alternative method that calculates not the expectation of the error itself, but the
expectation of the sufficient statistics used in calculating the error. In contrast tosentence-level approximations or formulations such as linear BLEU, the expectation of
the sufficient statistics can be calculated directly on the corpus level. Due to this fact, by
maximizing the evaluation derived by these expected statistics, it is possible to directly
optimize for a corpus-level error, in a manner similar to MERT (Pauls, Denero, and Klein2009).
When this is applied to BLEU in particular, this measure is often called xBLEU(Rosti et al. 2010, 2011) and the required sufficient statistics include n-gram counts and29Computational Linguistics

Volume 1, Number 1

matched n-gram counts. We define the kth translation candidate in c(i) as hek , dk i, itsscore as si,k = γw> h(f (i) , ek , dk ), and the probability in Equation (22) as
exp(si,k )pi,k = PK.
k0 =1 exp(si,k0 )(53)

Next, we define the expectation of the n-gram (gn ∈ ek ) frequency as cn,i,k , the expectation of the number of n-gram matches as mn,i,k , and the expectation of the reference
length as ri,k . These values can calculated as below:
cn,i,k = |{gn ∈ ek }| · pi,kmn,i,k = |{gn ∈ ek } ∩ {gn(i) ∈ e(i) }| · pi,kri,k = |e(i) | · pi,k .
It should be noted that while these equations apply to k-best lists, it is also possible tocalculate statistics over lattices or forests using dynamic programming algorithms andtools such as the expectation semiring (Eisner 2002; Li and Eisner 2009).
xBLEU is calculated from these expected sufficient statistics

xBLEU =

4
Y
n=1

PN PK

k=1 mn,i,k
Pi=1
N PK
i=1
k=1 cn,i,k

! 14

PN PK

·φ

ri,k
1 − PNi=1PKk=1
i=1
k=1 c1,i,k

!
,

(54)

where φ(x) is the brevity penalty. Compared to the risk minimization in Equation (24),
we define our optimization problem as the maximization of xBLEU:`xBLEU (F, E, C; γ, w) = − xBLEU .

(55)

It is possible to calculate a gradient for xBLEU, allowing for optimization using
gradient-based optimization methods, and we explain the full (somewhat involved)
derivation in Appendix A.
6. Online Methods
In the batch learning methods of Section 5, the steps of decoding and optimization
are performed sequentially over the entire training data. In contrast, online learning
performs updates not after the whole corpus has been processed, but over smaller
subsets of the training data deemed mini batches. One of the major advantages of
online methods is that updates are performed on a much more fine-grained basis, it
is often the case that online methods converge faster than batch methods, particularly
on larger data sets. On the other hand, online methods also have the disadvantage ofbeing harder to implement (they often must be implemented inside the decoder, whilebatch methods can be separate), and also generally being less stable (with sensitivity tothe order in which the training data is processed or other factors).
In the online learning algorithm in Figure 8, from the training data hF, Ei =noN(i) (i)hf , e i
we first randomly choose a mini batch consisting of K sentences of pari=130

Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

1: procedure O NLINE L EARN (hF, Ei =
2:
3:
4:
5:
6:

w(1) ← ∅for t ∈ {1, . . . , T } dohF̃ (t) , Ẽ (t) i ⊆ hF, Ei
C̃ (t) ← {c̃(j) = ∅}K
j=1
for hf̃(j)noN
hf (i) , e(i) i)
i=1. Sample (|hF̃ (t) , Ẽ (t) i| = K)
. k-best translation candidates, ẽ(j) i ∈ hF̃ (t) , Ẽ (t) i do(j)c̃(j) ← GEN(f̃ , w(t) ). Decode with w(t)end forw(t+1) ← arg minw∈RM `(F̃ (t) , Ẽ (t) , C̃ (t) ; w) + λΩ(w).
Optimization
10:
end for11:
return w(T +1)
12: end procedure
7:
8:
9:

Figure 8: Online Learning

n (j)
oK
allel data hF̃ (t) , Ẽ (t) i = hf̃ , ẽ(j) i

j=1(Line 4). We then decode each source sentence(j)f̃ of the mini batch and generate a k-best list (Line 7), which is used in optimization(Line 9). In contrast to the batch learning algorithm in Figure 3, we do not merge the
k-bests from previous iterations. In addition, optimization is performed not over theentire data, but only the data hF̃ (t) , Ẽ (t) i and its corresponding k-best, C̃ (t) . Like batchlearning, within the online learning framework, there are a number of optimization
algorithms and objective functions that can be used.
The first thing we must consider during online learning is that because we only
optimize over the data in the mini-batch, it is not possible to directly optimize a corpuslevel evaluation measure such as BLEU, and it is necessary to define an error functionthat is compatible with the learning framework (see Section 6.1). Once the error has beenset, we can perform parameter updates according to a number of different algorithms
including the perceptron (Section 6.2), MIRA (Section 6.3), AROW (Section 6.4), andstochastic gradient descent (SGD) (Section 6.5).
6.1 Approximating the Error
In online learning, parameters are updated not with respect to the entire training corpus,
but with respect to a subset of data sampled from the corpus. This has consequences
for the calculation of translation quality when using a corpus-level evaluation measuresuch as BLEU. For example, when choosing an oracle for oracle-based optimization
methods, the oracles chosen when considering the entire corpus will be different fromthe oracles chosen when considering a mini-batch. In general, the amount of difference
between the corpus-level and mini-batch level oracles will vary depending on the sizeof a mini-batch, with larger mini-batches providing a better approximation (Watanabe
2012; Tan et al. 2013). Thus, when using smaller batches, especially single sentences, itis necessary to use methods to approximate the corpus-level error function as coveredin the next two sections.

31Computational Linguistics

Volume 1, Number 1

6.1.1 Approximation with a Pseudo-corpus. The first method to approximate thecorpus-level evaluation measure relies on creating a pseudo-corpus, and using it toaugment the statistics used in the mini-batch error calculation (Watanabe et al. 2007).
noN
Specifically, given the training data hF, Ei = hf (i) , e(i) i, we define its correspondi=1
 (i) Ning pseudo-corpus Ē = ē. Ē could be, for example, either the 1-best translation
i=1
candidate or the oracle calculated during the decoding step in Line 7 of Figure 8. In thepseudo-corpus approximation, the sentence-level error for the translation candidate e0
acquired by decoding the ith source sentence in the training data can be defined as the
corpus-level error acquired when in Ē, the ith sentence ē(i) is replaced with e0
errpseudo (e(i) , e0 ) = error E, {ē(1) , . . . , ē(i−1) , e0 , ē(i+1) , . . . , ē(N ) } .

(56)

6.1.2 Approximation with Decay. When approximating the error function using a
pseudo-corpus, it is necessary to remember translation candidates for every sentencein the corpus. In addition, the size of differences in the sentence-level error becomes
dependent on the number of other sentences in the corpus, making it necessary to perform scaling of the error, particularly for max-margin methods (Watanabe et al. 2007).
As an alternative method that alleviates these problems, there has also been a method
proposed that remembers a single set of sufficient statistics for the whole corpus, andupon every update forces these statistics to decay according to some criterion (Chiang,
Marton, and Resnik 2008; Chiang, Knight, and Wang 2009; Chiang 2012).
We define define s̄ as the sufficient statistics necessary to calculate a particularevaluation measure. For example, in the case of BLEU, this would be a particulartranslation candidate’s counts of the number of n-grams, the number of matched ngrams, and the reference length. When evaluating the error for a candidate e0 of the ith
sentence in the training data, we first decay the sufficient statisticss̄ ← ν × s̄,(57)

where ν < 1 is the amount of decay, taking a value such as 0.9 or 0.99. Next, based onthese sufficient statistics, we calculate the error of each candidate for the sentence bysumming the sufficient statistics of the sentence with the decayed sufficient statistics s̄.
For example, if we want to calculate BLEU using statBLEU (e(i) , e0 ) and the ith training
sentence hf (i) , e(i) i, if BLEU(·) is a function calculating BLEU from a particular set of
sufficient statistics, we can use the following equation:
errbleu0 (e(i) , e0 ) = 1 − BLEU(s̄ + statBLEU (e(i) , e0 )).

(58)

After performing update for a particular sentence s̄ is then updated with the statistics
from the 1-best hypothesis found during decoding. When the training data is large, thisfunction will place more emphasis on the recently generated examples, forgetting theolder ones.
6.2 The Perceptron
The most simple algorithm for online learning is the perceptron algorithm shown in
Figure 9, which as its name suggests, optimizes the perceptron loss of Section 3.4. The
most central feature of the algorithm is that when the 1-best and oracle translations

32

Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

1: procedure P ERCEPTRON (hF, Ei =noN
hf (i) , e(i) i)i=1w(1) ← 0
for t ∈ {1 . . . T } do
hf , ei ∼ hF, Ei. Assume K = 1c̃ ← GEN(f , w(t) ). Decode with w(t)6:hê, d̂i ∈ c̃
. 1-best candidate7:he∗ , d∗ i ∈ õ ⊆ c̃
. Oracle candidate8:
if he∗ , d∗ i =6 hê, d̂i then9:w(t+1) ← w(t) + h(f , e∗ , d∗ ) − h(f , ê, d̂) . Update10:
end if
11:
end forP +1 (t)w
12:return w(T +1) or T1 Tt=2
13: end procedure
2:
3:
4:
5:

Figure 9: The perceptron algorithm

differ, we update the parameters at Line 9. Because the gradient of the perceptron loss
in Equation (31) with respect to w is
K

(i)
1 X
(i)
−∆h(f̃ , e∗(i) , d∗(i) , ê(i) , d̂ )
K i=1
K

=


(i)
1 X 
(i)
(i)
− h(f̃ , e∗(i) , d∗(i) ) − h(f̃ , ê(i) , d̂ ) , (59)K i=1

this algorithm can also be viewed as updating the parameters based on this gradient,making the parameters for oracle he∗(i) , d∗(i) i stronger, and the parameters for the(i)mistaken translation hê(i) , d̂ i weaker.
In Line 12, we return the final parameters to be used in translation. The moststraightforward approach here is to simply return the parameters resulting from thefinal iteration of the perceptron training, but in a popular variant called the averaged
perceptron, we instead use the average of the parameters over all iterations in training(Collins 2002). This averaging helps reduce overfitting of sentences that were viewed
near the end of the training process, and is known to improve robustness to unknown
data, resulting in higher translation accuracy (Liang et al. 2006).
6.3 MIRA
In Line 9 of the perceptron algorithm in Figure 9, the parameters are updated using thegradient with respect to w(t) (see Equation (59)). This update has the advantage of being
simple and being guaranteed to converge when the data is linearly separable, but it isis common for MT to handle feature sets that do not allow for linear separation of the
1-best and oracle hypotheses, resulting in instability in learning. The margin infused
relaxed algorithm (MIRA) (Crammer and Singer 2003; Crammer et al. 2006) is another
online learning algorithm designed to help reduce these problems of instability. The
update in MIRA follows the same Equation (59), but also adds an additional term that33

Computational Linguistics

Volume 1, Number 1

prevents the parameters w(t) from varying largely from their previous values8`MIRA (F̃ , Ẽ, C̃; w, w(t) ) =K
1λMIRA Xkw − w(t) k22 +
2
K i=1

n
o
(i)
(i)
max 0, ∆ err(ẽ(i) , e∗(i) , ê(i) ) − w> ∆h(f̃ , e∗(i) , d∗(i) , ê(i) , d̂ ) . (60)It should be noted that while this is defined as a loss, it is dependent on the parametersat the previous time step, in contrast to the losses in Section 3.
In Line 9 of Figure 8, (or when K = 1, Line 9 of Figure 9), the next parameters w(t+1)
are chosen to minimize Equation (60) (Watanabe et al. 2007; Chiang, Marton, and Resnik
2008; Chiang, Knight, and Wang 2009). λMIRA is a hyperparameter that controls theamount of fitting to the data, with larger values indicating a stronger fit. Intuitively, theMIRA objective contains an error-minimizing term similar to that of the perceptron, butalso contains a regularization term with respect to the change in parameters comparedto w(t) , preferring smaller changes in parameters. When K > 1, this equation can beformulated using Lagrange multipliers and solved using a quadratic programming
solver similar to that used in SVMs. When K = 1, we can simply use the following
update formulaw(t+1) = w(t) + α(t) ∆h(f̃ , e∗ , d∗ , ê, d̂)
)
(
∗
∗
>
∗
∆
err(ẽ,
e
,
ê)
−
w
∆h(
f̃
,
e
,
d
,
ê,
d̂)
.
α(t) = min λMIRA ,k∆h(f̃ , e∗ , d∗ , ê, d̂)k2

(61)
(62)

The amount of update is proportional to the difference in loss between hypotheses, butwhen the difference in the features between the oracle and incorrect hypotheses is small,the features that are different will be subject to an extremely large update. The functionof the parameter λMIRA is to control these over-aggressive updates. It should also be
noted that when we set α(t) = 1, MIRA reduces to the perceptron algorithm.
6.4 AROWOne of the problems often pointed out with MIRA is that it is over-agressive, mainly
because it attempts to classify the current training example correctly according toEquation (60), even when the training example is an outlier or includes noise. One way
to reduce the effect of noise is through the use of adaptive regularization of weights(AROW) (Crammer, Kulesza, and Dredze 2009; Chiang 2012). AROW is based on asimilar concept to MIRA, but instead of working directly on the weight vector w, it
defines a Gaussian distribution N (w, Σ) over the weights. The covariance matrix Σ
is usually assumed to be diagonal, and each variance term in Σ functions as a sortof learning rate for its corresponding weight, with weights of higher variance being
updated more widely, and weights with lower variance being updated less.

8 The algorithm presented here is actually the PA-I algorithm (Crammer et al. 2006) applied to structured
learning, and for historical reasons most research in parsing, MT, and other areas refer to this algorithm
not as PA-I, but MIRA (McDonald, Crammer, and Pereira 2005; Watanabe et al. 2007).

34

Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

For notational simplicity, we first define x(i) = ∆h(f̃
which we can express the AROW loss as follows:

(i)

(i)

, e∗(i) , d∗(i) , ê(i) , d̂ ), after`AROW (F̃ , Ẽ, C̃; w, Σ, w(t) , Σ(t) ) = KL(N (w, Σ)||N (w(t) , Σ(t) ))+

K 
n
o λ
1 X
var >(i)λMIRA max 0, ∆ err(ẽ(i) , e∗(i) , ê(i) ) − w> x(i) +
x
Σx(i)
(63)
K i=1
2
where KL(·) is the Kullback-Leibler divergence. The KL divergence term here plays asimilar role to the parameter norm in MIRA, preventing large changes in the weight
distributions from update to update, and the first term within the summation is thesame loss term as MIRA. The main difference lies in the second term within the summation, which penalizes variance matrices that have large values for features seen in the
hypotheses to be updated. This has the effect of decreasing the variance, and thus thelearning rate, for frequently updated features, preventing large and aggressive movesof weights for features that already have been seen often and thus can be consideredrelatively reliable. In the case of K = 1 and where λMIRA = λvar , the AROW update thatminimizes this loss consists of the following updates of w and Σ (Crammer, Kulesza,
and Dredze 2009):
w(t+1) = w(t) + α(t+1) Σ(t) x(i)(64)Σ(t+1) = Σ(t) − β (t+1) Σ(t) x(i) x>(i) Σ(t)α(t+1) = max 0, 1 − w>(t) x(i) β (t+1)(65)

β (t+1) =1.
x>(i) Σt−1 x(i) + 1/2λvar

(66)
(67)

6.5 Stochastic Gradient Descent
Stochastic gradient descent (SGD) is a gradient-based online algorithm for optimizing
differentiable losses, possibly with the addition of L2 regularization Ω2 (w), or L1 regularization Ω1 (w). As SGD relies on gradients, it can be thought of as an alternative tothe gradient-based batch algorithms in Section 5.2. Compared to batch algorithms, SGD
requires less memory and tends to converge faster, but requires more care (particularly
with regards to the selection of a learning rate) to ensure that it converges to a goodanswer.
In SGD, like with the perceptron algorithm and MIRA, in Line 9 of Figure 8 theparameters are updated according to the gradient ∆`(·) + λ∆Ω(·) with respect to w(t)(Bottou 1998):η (t+1) ← update(η (t) )

(68)

n
o
w(t+1) ← w(t) − η (t+1) ∆`(F̃ (t) , Ẽ (t) , C̃ (t) ; w(t) ) + λ∆Ω(w(t) ) ,(69)

where η (t) > 0 is the learning rate, which is generally initialized to a value η (1) andgradually reduced according to a function update(·) as learning progresses. One stan-35

Computational Linguistics

Volume 1, Number 1

dard method for updating η (t) according to the following formulaη (t+1) ←η (1)
1 + t/T(70)

allows for a guarantee of convergence (Collins et al. 2008). In Equation (69), the parameters are updated and we obtain w(t+1) . Within this framework, in the perceptron
algorithm η (t) is set to a fixed value, and in MIRA the amount of update changes for every mini-batch. SGD-style online gradient-based methods have been used in translationfor optimizing risk-based (Gao and He 2013), ranking-based (Watanabe 2012; Green etal. 2013), and other (Tillmann and Zhang 2006) objectives. When the regularization termΩ(w) is not differentiable, such as L1 regularization, it is a common practice to employ
forward-backward splitting (FOBOS) (Duchi and Singer 2009; Green et al. 2013) inwhich the optimization is performed in two steps:
1w(t+ 2 ) ← w(t) − η (t+1) ∆`(F̃ (t) , Ẽ (t) , C̃ (t) ; w(t) )

(71)

1
1
w(t+1) ← arg min kw − w(t+ 2 ) k22 + η (t+1) λΩ(w).
2
w

(72)

First, we perform updates without considering the regularization term in Equation (71).
Second, the regularization term is applied in Equation (72), which balances regulariza1
tion and proximity to w(t+ 2 ) . As an alternative to FOBOS, it is possible to use dual
averaging, which keeps track of the average of previous gradients and optimizes forthese along with the full regularization term (Xiao 2010).
An alternative to stochastic gradient descent is adaptive gradient (AdaGrad)(Duchi, Hazan, and Singer 2011; Green et al. 2013) updates. The motivation behind AdaGrad is similar to that of AROW (Section 6.4), using second-order covariance statistics Σto adjust the learning rate of individual parameters based on their update frequency. If
we define the SGD gradient as x = ∆`(F̃ (t) , Ẽ (t) , C̃ (t) ; w(t) ) + λ∆Ω(w(t) ) for notational
simplicity, the update rule for AdaGrad can be expressed as follows
Σ−1(t+1) ← Σ−1(t) + xx>
w(t+1) ← w(t) − ηΣ1/2(t) x.

(73)
(74)

Like AROW, it is common to use a diagonal covariance matrix, and each time an update
is performed the variance for the updated features decreases, reducing the overall
learning rate for more commonly updated features. It should be noted that as the updateof each feature is automatically controlled by the covariance matrix, there is no need todecay η as is necessary in SGD.
7. Large-scale Optimization
Up until this point, we have generally given a mathematical or algorithmic explanationof the various optimization methods, and placed a smaller emphasis on factors suchas training efficiency. In traditional optimization settings for MT where we optimize
only a small number of weights for dense features on a training set of around 1,000
sentences, efficiency is often less of a concern. However, when trying to move to larger
sets of sparse features, 1,000 sentences of training data is simply not enough to robustly

36

Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

1: procedure PARALLEL L EARN (hF, Ei)
2:
Split hF, Ei into S shards {hF1 , E1 i, . . . , hFS , ES i}for s ∈ {1, . . . , S} parallel do. Run shards in parallelws ← O NLINE L EARN(hFs , Es i)or B ATCH L EARN(hFs , Es i). Local learning5:
end for6:w ← mix ({w1 , . . . , wS }). Parameter mixing
7:
return w
8: end procedure
3:
4:

Figure 10: Parallel learning

estimate the parameters, and larger training sets become essential. When moving tolarger training sets, parallelization of both the decoding process and the optimization
process becomes essential. In this section, we outline the methods that can be used toperform parallelization, greatly increasing the efficiency of training. As parallelizationin MT has seen wider use with respect to online learning methods, we will start with adescription of online methods and touch briefly upon batch methods afterwards.
7.1 Large-scale Online Optimization
Within the online learning framework, it is possible to improve the efficiency of learning
through parallelization (McDonald, Hall, and Mann 2010). An example of this is shownnoN
in Figure 10, where the training data hF, Ei = hf (i) , e(i) i
is split into S shards
i=1(Line 2), learning is performed locally over each shard hFs , Es i, and the S sets ofparameters ws acquired through local learning are combined according to a function
mix(·), a process called parameter mixing (Line 6). This can be considered an instanceof the MapReduce (Dean and Ghemawat 2008) programming model, where each Map
assigns shards to S CPUs and performs training, and Reduce combines the resulting
parameters ws .
In the training algorithm of Figure 10, because parameters are learned locally oneach shard, it is not necessarily guaranteed that the parameters are optimized for thedata as a whole. In addition, it is also known that some divisions of the data can lead tocontradictions between the parameters (McDonald, Hall, and Mann 2010). Because ofthis, when performing distributed online learning, it is common to perform parameter
mixing several times throughout the training process, which allows the separate shards
to share information and prevents contradiction between the learned parameters. Basedon the timing of the update, these varieties of mixing are called synchronous update
and asynchronous update.
7.1.1 Synchronous Update. In the online learning algorithm with synchronous updateshown in Figure 11, learning is performed independently over each shard hFs , Es i(1 ≤s ≤ S). The difference between this and Figure 10 lies in the fact that learning is
performed T 0 times, with each iteration initialized with the parameters w(t) from theprevious iteration (Line 7).
After the local learning finishes, the parameters are mixed in Line 8 (McDonald,Hall, and Mann 2010; Watanabe et al. 2007; Watanabe 2012). In the mixing function it is37Computational Linguistics

Volume 1, Number 1

1: procedure S YNCHRONOUS O NLINE L EARN (hF, Ei)
2:
Split hF, Ei into S fragments {hF1 , E1 i, . . . , hFS , ES i}
3:
4:
5:
6:
7:

w(1) ← 0. Initialize parameters
for s ∈ {1, . . . , S} parallel do. Run shards in parallel
for t ∈ {1, . . . , T } do(t)w̄s ← w(t). Copy parameters to each shard
(t+1)
(t)
w̄s
← O NLINE L EARN(hFs , Es i, w̄s , T 0 ). Local learning on each shard

(t+1)

(t+1)

w(t+1) ← mix {w̄1
, . . . , w̄S
9:
end for10:
end forP +1 (t)11:return w(T +1) or T1 Tt=2w
12: end procedure8:}. Mix parameters

Figure 11: Online learning with synchronous update

most common to use the average of the parameters

w

(t+1)

←

S
X

µs w̄(t+1)
,
s

(75)

s=1

P
where Ss=1 µs = 1. As µs , it is possible to use a uniform distribution, or a weight
proportional to the number of online updates performed at each shard (McDonald,Hall, and Mann 2010; Simianer, Riezler, and Dyer 2012). It should be noted that thisalgorithm can be considered a variety of the MapReduce framework, allowing for
relatively straightforward implementation using parallel processing infrastructure suchas Hadoop (Eidelman 2012).
Simianer, Riezler, and Dyer (2012) propose another method for mixing parameters
that, instead of averaging at each iteration, chooses to preserve only the parametersthat have been learned over all shards, and sets all the remaining parameters to zero,
allowing for a simple sort of feature selection. In particular, we define a S × M matrix
h
i>
(t+1)
(t+1)
(t+1)
(t+1)
at each shard as W̄
= w̄1| . . . |w̄S,
that combines the parameters w̄stakes the L2 norm of each matrix column, and average the columns with high norm
values while setting the rest to zero.
7.1.2 Asynchronous Update. While parallel learning with synchronous update is guaranteed to converge (McDonald, Hall, and Mann 2010), parameter mixing only occurs
after all the data has been processed, leading to inefficiency over large data sets. To fix
this problem, asynchronous update sends information about parameter updates to eachshard asynchronously, allowing the parameters to be updated more frequently, resulting
in faster learning (Chiang, Marton, and Resnik 2008; Chiang, Knight, and Wang 2009).
The algorithm for learning with asynchronous update is shown in Figure 12. With
the datahFs , Es i (1 ≤ s ≤ S) split into S pieces, each shard performs T iterations of
training by sampling a mini-batch (Line 7), translating each sentence (Line 10), andperforming optimization on the mini-batch level (Line 12).

38

Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

1: procedure A SYNCHRONOUS O NLINE L EARN (hF, Ei)
2:
Split hF, Ei into S fragments {hF1 , E1 i, . . . , hFS , ES i}
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

w(1) ← 0
for s ∈ {1, . . . , S} parallel dofor t ∈ {1, . . . , T } do(t)w̄s ← copyasync w(t). Initialize parameters. Run s shards in parallel. Copy parameters to each shard(t)(t)
hF̃s , Ẽs i ⊆ hFs , Es i(t)
KC̃s ← {c̃(j)s = ∅}j=1
(j)
(t)
(t)
for hf̃ s , ẽ(j)s i ∈ hF̃s , Ẽs i do
(j)
(t)
c̃(j)
s ← GEN(f̃ s , w̄ s )

(t)

(t)

. Decode with w̄s

end for
(t+1)
(t)
(t)
(t)
w̄s
← arg minw̄s ∈RM `(F̃s , Ẽs , C̃s ; w̄s ) + λΩ(w̄s )
(t+1)

(t+1)
(t+1)
{w̄1
, . . . , w̄S }w← mixasync
14:
end for15:
end forP +1 (t)16:
return w(T +1) or T1 Tt=2w
17: end procedure
13:

(t)

. Sample (|hF̃s , Ẽs i| = K)
. k-best candidates. Optimize. Mix parameters

Figure 12: Online learning with asynchronous update

Compared to the synchronous algorithm in Figure 11, the parameter mixing operator mixasync (·) in Line 13 sends the result of the mini-batch level update∆w̄(t+1)= w̄(t+1)− w̄(t)
s
s
s

(76)

to each shard s0 (s0 6= s,1 ≤ s0 ≤ S). It should be noted that because the number of dimensions M in the parameter vector is extremely large, and each mini-batch will only
update a small fraction of these parameters, by only sending the parameters that haveactually changed in each mini-batch update we can greatly increase the efficiency of the
training. In operator copyasync (·) of Line 6, the learner receives the update from all theother shards and mixes them together to acquire the full update vector

w̄(t)
s ←

S
X

(t)

∆w̄s0 .

(77)

s0 =1

It should be noted that at mixing time, there is no need to wait for the update vectors
from all of the other shards; update can be performed with only the update vectors thathave been received at the time. Because of this, each shard will not necessarily be usingparameters that reflect all the most recent updates performed on other shards. However,as updates are performed much more frequently than in synchronous update, it is easier
to avoid local optima, and learning tends to converge faster. It can also be shown that
(under some conditions) the amount of accuracy lost by this delay in update is bounded(Zinkevich, Langford, and Smola 2009; Recht et al. 2011).

39

Computational Linguistics

Volume 1, Number 1

7.2 Large-scale Batch Optimization
Compared to online learning, within the batch optimization framework, parallelization
is usually straightforward. Often, decoding takes the majority of time required for the
optimization process, and because the parameters will be identical for each sentence inthe decoding run (Algorithm 3 Line 6), decoding can be parallelized trivially. The process of parallelizing optimization itself depends slightly on the optimization algorithm,
but is generally possible to achieve in a number of ways.
The first, and simplest method for parallelization is the parallelization of optimization runs. The most obvious example of this is MERT, where random restarts are
required. Each of the random restarts is completely independent, so it is possible to run
these on different nodes, and finally check which run achieved the best accuracy anduse that result.
Another more fine-grained method for parallelization, again most useful for MERT,
is the parallelization of search directions. In the loop starting at Algorithm 4 Line 6,
MERT performs line search in several different directions, each one being independentof the others. Each of these line searches can be performed in parallel, and the direction
allowing for the greatest gain in accuracy is chosen when all threads have completed.
A method that is applicable to a much broader array of optimization methods isthe parallelization of calculation of sufficient statistics. In this approach, like in Section
7.1.1, we first split the data into shards hFs , Es i(1 ≤ s ≤ S). Then, over these shards wecalculate the sufficient statistics necessary to perform a parameter update. For example,
in MERT these sufficient statistics would consist of the envelope for each of the potential
search directions. In gradient based methods, the sufficient statistics would consist of
the gradient calculated with respect to only the data on the shard. Finally, when all
threads have finished calculating these statistics, a master thread combines the statistics
from each shard, either by merging the envelopes, or by adding the gradients.
8. Other Topics in MT Optimization
In this section we cover several additional topics in optimization for MT, including nonlinear models (Section 8.1), optimization for a particular domain or test set (Section 8.2),
and the interaction between evaluation measures (Section 8.3) or search (Section 8.4)
and optimization.
8.1 Non-linear Models
It should be noted that up until this point, all models that we have considered calculate
the scores for translation hypotheses according to a linear model, where the score is
calculated according to the dot product of the features and weights shown in Equation(1). However, linear models are obviously limited in their expressive power, and anumber of works have attempted to move beyond linear combinations of features tononlinear combinations.
In general, most non-linear models for machine learning can be applied to MT as
well, with one major caveat. Specifically, the efficiency of the decoding process largely
relies on the feature locality assumption mentioned in Section 2.3. Unfortunately the locality assumption breaks down when moving beyond a simple linear scoring function,and overcoming this problem is the main obstacle to applying non-linear models to MT(or structured learning in general). A number of countermeasures to this problem exist:

40Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

Reranking: The most simple and commonly used method for incorporating nonlinearity, or other highly non-local features that cannot be easily incorporated insearch, is through the use of reranking (Shen, Sarkar, and Och 2004). In this case,a system optimized using a standard linear model is used to create a k-best list of
outputs, and this k-best list is then reranked using the non-linear model (Nguyen,
Mahajan, and He 2007; Duh and Kirchhoff 2008). Because we are now only dealing
with fully expanded hypotheses, scoring becomes trivial, but reranking also has
the major downsides of potentially missing useful hypotheses not included in the
k-best list,9 and requiring time directly proportional to the size of the k-best list.
Local Non-linearity: Another possibility is to first use a non-linear function to calculate
local features, which are then used as part of the standard linear model (Liu etal. 2013). Alternatively, it is possible to treat feature-value pairs as new binaryfeatures (Clark, Dyer, and Lavie 2014). In this case, all effects of non-linearity are
resolved before the search actually begins, allowing for the use of standard andefficient search algorithms. On the other hand, it is not possible to incorporate
non-local features into the non-linear model.
Improved Search Techniques: While there is no general-purpose solution to incorporating non-linear models into search, for some particular models it is possible toperform search in a way that allows for incorporation of non-linearities. For example, ensemble decoding has been used with stacking-based models (Razmara
and Sarkar 2013), and it has been shown that the search space can be simplified tothe extent that kernel functions can be calculated efficiently (Wang, Shawe-Taylor,and Szedmak 2007).
Once the problems of search have been solved, a number of actual learning techniques can be used to model non-linear scoring functions. One of the most popular
examples of non-linear functions are those utilizing kernels, and methods applied to MT
include kernel-like functions over the feature space such as the Parzen window, binning,and Gaussian kernels (Nguyen, Mahajan, and He 2007), or the n-spectrum string kernel
for finding associations between the source and target strings (Wang, Shawe-Taylor,and Szedmak 2007). Neural networks are another popular method for modeling nonlinearities, and it has been shown that neural networks can effectively be used to calculate new local features for MT (Liu et al. 2013). Methods such as boosting or stacking,which combine together multiple parameterizations of the translation model have been
incorporated through reranking (Duh and Kirchhoff 2008; Lagarda and Casacuberta
2008; Duan et al. 2009; Sokolov, Wisniewski, and Yvon 2012b), or ensemble decoding(Razmara and Sarkar 2013). Regression decision trees have also been introduced as amethod for inducing non-linear functions, incorporated through history-based searchalgorithms (Turian, Wellington, and Melamed 2006), or by using the trees to inducefeatures local to the search state (Toutanova and Ahn 2013).
8.2 Domain-Dependent Optimization
One widely acknowledged feature of machine learning problems in general is that theparameters are sensitive to the domain of the data, and by optimizing the parameterswith data from the target domain it is possible to achieve gains in accuracy. In machinetranslation, this is also very true, although much of the work on domain adaptation has
9 This problem can be ameliorated somewhat by ensuring that there is sufficient diversity in the n-best list
(Gimpel et al. 2013).

41

Computational Linguistics

Volume 1, Number 1

focused on adapting the model learning process prior to explicit optimization towards
an evaluation measure (Koehn and Schroeder 2007). However, there are a few works on
optimization-based domain adaptation in MT, as we will summarize below.
One relatively simple way of performing domain adaptation is by selecting a subsetof the training data that is similar to the data that we want to translate (Li et al.
2010). This can be done by selecting sentences that are similar to our test corpus, oreven selecting adaptation data for each individual test sentence (Liu et al. 2012). If noparallel data exists in the target domain, it has also been shown that first automaticallytranslating data from the source to the target language or vice-versa, then using this datafor optimization and model training is also helpful (Ueffing, Haffari, and Sarkar 2007; Liet al. 2011; Zhao et al. 2011) In addition, in a computer-assisted translation scenario, it ispossible to reflect post-edited translations back into the optimization process as new indomain training data (Mathur, Mauro, and Federico 2013; Denkowski, Dyer, and Lavie2014).
Once adaptation data has been chosen, it is necessary to decide how to use the data.
The most straightforward way is to simply use this in-domain data in optimization, but
if the data is small it is preferable to combine both in- and out-of-domain data to achieve
more robust parameter estimates. This is essentially equivalent to the standard domainadaptation problem in machine learning, and in the context of MT there have been
methods proposed to perform Bayesian adaptation of probabilistic models (SanchisTrilles and Casacuberta 2010), and online update using ultra-conservative algorithms(Liu et al. 2012). This can be extended to cover multiple target domains using multi-task
learning (Cui et al. 2013).
Finally, it has been noted that when optimizing a few dense parameters, it is useful
to make the distinction between in-domain translation (when the model training data
matches the test domain) and cross-domain translation (when the model training data
mismatches the test domain). In cross-domain translation, fewer long rules will be
used, and translation probabilities will be less reliable, and the parameters must change
accordingly to account for this (Pecina, Toral, and van Genabith 2012). It has also beenshown that building TMs for several domains and tuning the parameters to maximize
translation accuracy can improve MT accuracy on the target domain (Haddow 2013).
Another option for making the distinction between in-domain and out-of-domain data
is by firing different features for in-domain and out-of-domain training data, allowing
for the learning of different weights for different domains (Clark, Lavie, and Dyer 2012).
8.3 Evaluation Measures and Optimization
In the entirety of this article, we have assumed that optimization for MT aims to
reduce MT error defined using an evaluation measure, generally BLEU. However, as
mentioned in Section 2.5, evaluation of MT is an active research field, and there aremany alternatives in addition to BLEU. Thus, it is of interest whether changing themeasure used in optimization can affect the overall quality of the translations achieved,
as measured by human evaluators.
There have been a few comprehensive studies on the effect of the metric used in
optimization on human assessments of the generated translations (Cer, Manning, andJurafsky 2010; Callison-Burch et al. 2011). These studies showed the rather surprising
result that despite the fact that other evaluation measures had proven superior to BLEU
with regards to post-facto correlation with human evaluation, a BLEU-optimized systems proved superior to systems tuned using other metrics. Since this result, however,there have been other reports stating that systems optimized using other metrics such

42

Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

as TESLA (Liu, Dahlmeier, and Ng 2011) and MEANT (Lo et al. 2013) achieve superior
results to BLEU-optimized systems.
There have also been attempts to directly optimize not automatic, but humanevaluation measures of translation quality (Zaidan and Callison-Burch 2009). However,the cost of performing this sort of human-in-the-loop optimization is prohibitive, so
Zaidan and Callison-Burch (2009) propose a method that re-uses partial hypotheses in
evaluation. Saluja, Lane, and Zhang (2012) also propose a method for incorporating
binary good/bad input into optimization, with the motivation that this sort of feedback
is easier for human annotators to provide than generating new reference sentences.
Finally, there is also some work on optimizing multiple evaluation metrics at one
time. The easiest way to do so is to simply use the linear interpolation of two or more
metrics as the error function (Dyer et al. 2009; He and Way 2009; Servan and Schwenk
2011):

error(E, Ê) =LX

ρi errori (E, Ê),

(78)

i=1

where L is the number of error functions, and ρi is a manually set interpolation coefficient for its respective error function. There are also more sophisticated methods basedon the idea of optimizing towards Pareto-optimal hypotheses (Duh et al. 2012), which
achieve error lower than all other hypotheses on at least one evaluation measure,pareto(E, E) = {Ê ∈ E : ∀E 0 ∈E ∃i errori (E, Ê) < errori (E, E 0 )}.

(79)

To incorporate this concept of Pareto optimality into optimization, the Pareto-optimal
set is defined on the sentence level, and ranking loss (Section 3.5) is used to ensurethat the Pareto-optimal hypotheses achieve a higher score than those that are not Pareto
optimal. This method has also been extended to take advantage of ensemble decoding,where multiple parameter settings are used simultaneously in decoding (Sankaran,
Sarkar, and Duh 2013).
8.4 Search and Optimization
As mentioned in Section 2.4, because MT decoders perform approximate search, they
may make search errors and not find the hypothesis that achieves the highest modelscore. There have been a few attempts to consider this fact in the optimization process.
For example, in the perceptron algorithm of Section 6.2 it is known that the convergence guarantees of the structured perceptron no longer hold when using approximate
search. The first method that can be used to resolve this problem is the early updating
strategy (Collins and Roark 2004; Cowan, Kuc̆erová, and Collins 2006). The early updating strategy is a variety of bold update, where the decoder output e∗(i) must be exactly
equal to the reference e(i) . Decoding proceeds as normal, but the moment the correct
hypothesis e(i) can no longer be produced by any hypothesis in the search space (i.e.,a search error has occurred), search is stopped and update is performed using only
the partial derivation. The second method is the max-violation perceptron (Huang,
Fayong, and Guo 2012; Yu et al. 2013). In the max-violation perceptron, forced decoding
is performed to acquire a derivation he∗(i) , d∗(i) i that can exactly reproduce the correct
output e(i) , and update is performed at the point when the score of a partial hypothesis

43Computational Linguistics

MERT
MIRA
Ranking
Softmax
Risk
None

WMT 2011
All
Best
80
100
0
0
0
0
3
0
3
0
17
0

Volume 1, Number 1

WMT 2012
All
Best
79
100
0
0
4
0
0
0
0
0
17
0

WMT 2013
All
Best
68
25
20
75
8
0
0
0
0
0
4
0

WMT 2014
All
Best
63
50
27
50
5
0
0
0
5
0
0
0

Table 2: Percent of WMT systems using each optimization method, including all systems, or systems that achieved the best results on at least on language pair.

ˆheˆ(i) , d(i) i exceeds that of the partial hypothesis he∗(i) , d∗(i) i by the greatest margin (thepoint of “maximum violation”).
Search-aware tuning (Liu and Huang 2014) is a method that is able to consider
search errors using an arbitrary optimization method. It does so by defining an evaluation measure for not only full sentences, but also partial derivations that occur during
the search process, and optimizes parameters for k-best lists of partial derivations.
Finally, there has also been some work on optimizing features not of the model itself,
but parameters of the search process, using the downhill simplex algorithm (Chungand Galley 2012). Using this method, it is possible to adjust the beam width, distortion
penalty, or other parameters that actually affect the size and shape of the derivation
space, as opposed to simply rescoring hypotheses within it.
9. Conclusion
In this survey article, we have provided a review of the current state-of-the-art inmachine translation optimization, covering batch optimization, online optimization,
expansions to large scale data, and a number of other topics. While these optimization
algorithms have already led to large improvements in machine translation accuracy, thetask of MT optimization is, as stated in the introduction, an extremely hard one that is
far from solved.
The utility of an optimization algorithm can be viewed from a number of perspectives. The final accuracy achieved is, of course, one of the most important factors, but
speed, scalability, ease of implementation, final resulting model size, and many otherfactors play an important role. We can assume that the algorithms being used outsideof the context of research on optimization itself are those that satisfy these criteria insome way. While it is difficult to exactly discern exactly which algorithms are seeing thelargest amount of use (industrial SMT systems rarely disclose this sort of information
publicly), one proxy for this is to look at systems that performed well on shared tasks
such as the Workshop on Machine Translation (WMT) (Bojar et al. 2014). In Table 2
we show the percentage of WMT systems using each optimization algorithm for the
past four years, both including all systems, and systems that achieved the highest levelof human evaluation in the resource-constrained setting for at least one language pair.
From these statistics we can see that even after over ten years, MERT is still the dominant
optimization algorithm. However, starting in WMT 2013, we can see a move to systems

44

Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

based on MIRA, and to a lesser extent ranking, particularly in the most competitive
systems.
In these systems, the preferred choice of an optimization algorithm seems to be
MERT when using up to 20 features, and MIRA when using a large number of features(up to several hundred). There are fewer examples of systems using large numbersof features (tens of thousands, or millions) in actual competitive systems, with a few
exceptions (Dyer et al. 2009; Neidert et al. 2014; Wuebker et al. 2014). In the case whena large number of sparse features are used, it is most common to use a softmax or
risk-based objective and gradient-based optimization algorithms, often combining thefeatures into summary features and performing a final tuning pass with MERT.
The fact that algorithms other than MERT are seeing adoption in competitive systems for shared tasks is a welcome sign for the future of MT optimization research.
However, there are still many open questions in the field, a few of which can be outlined
below:
Stable Training with Millions of Features: At the moment, there is still no stable training recipe that has been widely proven to effectively optimize millions of features.
Finding an algorithm that gives consistent improvements in this setting is perhaps
the largest open problem in MT optimization.
Evaluation Measures for Optimization: While many evaluation measures show consistent improvements in correlation with human evaluation scores over BLEU
when used to evaluate the output of existing MT systems, there are few results thatshow that systems optimized with evaluation measures other than BLEU achieve
consistent improvements in human evaluation scores.
Better Training/Utilization of Non-linear Scoring Functions: Non-linear
functionsusing neural networks have recently achieved large improvements in a numberof areas of natural language processing and machine learning. Better methods
to incorporate these sort of non-linear scoring functions into MT is a highly
promising direction, but will require improvements of both learning the scoring
functions and correctly incorporating these functions into MT decoding.
Resolving these, and many other, open questions will likely be among the top prioritiesof MT optimization research in the years to come.
References
Andrew, Galen and Jianfeng Gao. 2007.
Scalable training of L1-regularized
log-linear models. In Proceedings of ICML,
pages 33–40, Corvalis, Oregon.
Banerjee, Satanjeev and Alon Lavie. 2005.
METEOR: An automatic metric for MT
evaluation with improved correlation withhuman judgments. In Proceedings of the
ACL Workshop on Intrinsic and Extrinsic
Evaluation Measures for Machine Translation
and/or Summarization, pages 65–72, Ann
Arbor, Michigan.
Bazrafshan, Marzieh, Tagyoung Chung, andDaniel Gildea. 2012. Tuning as linear
regression. In Proceedings of HLT/NAACL,
pages 543–547, Montréal, Canada.
Bentley, J. L. and T. A. Ottmann. 1979.
Algorithms for reporting and counting

geometric intersections. IEEE Transactions
on Computers, 28(9):643–647.
Berger, Adam L., Vincent J. Della Pietra, andStephen A. Della Pietra. 1996. A maximum
entropy approach to natural language
processing. Computational Linguistics,
22:39–71.
Blunsom, Phil, Trevor Cohn, and Miles
Osborne. 2008. A discriminative latentvariable model for statistical machinetranslation. In Proceedings of ACL/HLT,
pages 200–208, Columbus, Ohio.
Blunsom, Phil and Miles Osborne. 2008.
Probabilistic inference for machinetranslation. In Proceedings of EMNLP, pages
215–223, Honolulu, Hawaii.
Bojar, Ondrej, Christian Buck, ChristianFedermann, Barry Haddow, Philipp
Koehn, Johannes Leveling, Christof Monz,
Pavel Pecina, Matt Post, Herve

45

Computational Linguistics

Saint-Amand, Radu Soricut, Lucia Specia,
and Aleš Tamchyna. 2014. Findings of the2014 workshop on statistical machinetranslation. In Proceedings of WMT, pages
12–58, Baltimore, Maryland.
Bottou, Léon. 1998. Online algorithms andstochastic approximations. In David Saad,
editor, Online Learning and Neural Networks.
Cambridge University Press, Cambridge,
UK.
Brown, Peter F., Vincent J. Della Pietra,
Stephen A. Della Pietra, and Robert L.
Mercer. 1993. The mathematics ofstatistical machine translation: Parameter
estimation. Computational Linguistics,
19(2):263–311.
Burges, Chris, Tal Shaked, Erin Renshaw, Ari
Lazier, Matt Deeds, Nicole Hamilton, andGreg Hullender. 2005. Learning to rank
using gradient descent. In Proceedings of
ICML, pages 89–96, Bonn, Germany.
Callison-Burch, Chris, Philipp Koehn,
Christof Monz, and Omar Zaidan. 2011.
Findings of the 2011 workshop on
statistical machine translation. In
Proceedings of WMT, pages 22–64,
Edinburgh, Scotland, UK.
Cao, Zhe, Tao Qin, Tie-Yan Liu, Ming-Feng
Tsai, and Hang Li. 2007. Learning to rank:
From pairwise approach to listwise
approach. In Proceedings of ICML, pages
129–136, Corvalis, Oregon.
Cer, Daniel, Dan Jurafsky, andChristopher D. Manning. 2008.
Regularization and search for minimum
error rate training. In Proceedings of WMT,
pages 26–34, Columbus, Ohio.
Cer, Daniel, Christopher D. Manning, andDaniel Jurafsky. 2010. The best lexical
metric for phrase-based statistical MT
system optimization. In Proceedings of
HLT/NAACL, pages 555–563, Los Angeles,
California.
Chappelier, Jean-Cédric and Martin Rajman.
1998. A generalized CYK algorithm forparsing stochastic CFG. In Proceedings ofthe 1st Workshop on Tabulation in Parsing and
Deduction, pages 133–137, Paris, France.
Chatterjee, Samidh and Nicola Cancedda.
2010. Minimum error rate training by
sampling the translation lattice. In
Proceedings of EMNLP, pages 606–615,
Cambridge, MA.
Chen, Stanley F and Ronald Rosenfeld. 1999.
A Gaussian prior for smoothing maximum
entropy models. Technical report, DTIC
Document.
Cherry, Colin and George Foster. 2012. Batch
tuning strategies for statistical machine46

Volume 1, Number 1

translation. In Proceedings of HLT/NAACL,
pages 427–436, Montréal, Canada.
Chiang, David. 2007. Hierarchicalphrase-based translation. Computational
Linguistics, 33(2):201–228.
Chiang, David. 2012. Hope and fear fordiscriminative training of statisticaltranslation models. Journal of Machine
Learning Research, 13:1159–1187.
Chiang, David, Kevin Knight, and Wei
Wang. 2009. 11,001 new features forstatistical machine translation. In
Proceedings of HLT/NAACL, pages 218–226,
Boulder, Colorado.
Chiang, David, Yuval Marton, and Philip
Resnik. 2008. Online large-margin trainingof syntactic and structural translation
features. In Proceedings of EMNLP, pages
224–233, Honolulu, Hawaii.
Chung, Tagyoung and Michel Galley. 2012.
Direct error rate minimization for
statistical machine translation. In
Proceedings of WMT, pages 468–479,
Montréal, Canada.
Clark, Jonathan H., Chris Dyer, and Alon
Lavie. 2014. Locally non-linear learning forstatistical machine translation via
discretization and structured
regularization. Transactions of the
Association for Computational Linguistics,
2(1):393–404.
Clark, Jonathan H., Chris Dyer, Alon Lavie,
and Noah A. Smith. 2011. Betterhypothesis testing for statistical machinetranslation: Controlling for optimizer
instability. In Proceedings of ACL/HLT,
pages 176–181, Portland, Oregon.
Clark, Jonathan H, Alon Lavie, and Chris
Dyer. 2012. One system, many domains:
Open-domain statistical machinetranslation via feature augmentation. In
Proceedings of AMTA, San Diego,
California.
Collins, Michael. 2002. Discriminative
training methods for hidden Markov
models: Theory and experiments withperceptron algorithms. In Proceedings of
EMNLP, pages 1–8, Philadelphia,
Pennsylvania.
Collins, Michael, Amir Globerson, Terry Koo,
Xavier Carreras, and Peter L. Bartlett. 2008.
Exponentiated gradient algorithms forconditional random fields andmax-margin Markov networks. Journal of
Machine Learning Research, 9:1775–1822.
Collins, Michael and Brian Roark. 2004.
Incremental parsing with the perceptron
algorithm. In Proceedings of ACL, pages
111–118, Barcelona, Spain.

Graham Neubig and Taro Watanabe

Cowan, Brooke, Ivona Kuc̆erová, andMichael Collins. 2006. A discriminativemodel for tree-to-tree translation. In
Proceedings of EMNLP, pages 232–241,
Sydney, Australia.
Crammer, Koby, Ofer Dekel, Joseph Keshet,
Shai Shalev-Shwartz, and Yoram Singer.
2006. Online passive-aggressivealgorithms. Journal of Machine Learning
Research, 7:551–585.
Crammer, Koby, Alex Kulesza, and Mark
Dredze. 2009. Adaptive regularization ofweight vectors. In Proceedings of NIPS,
pages 414–422, Vancouver, Canada.
Crammer, Koby and Yoram Singer. 2003.
Ultraconservative online algorithms for
multiclass problems. Journal of Machine
Learning Research, 3:951–991.
Cui, Lei, Xilun Chen, Dongdong Zhang,
Shujie Liu, Mu Li, and Ming Zhou. 2013.
Multi-domain adaptation for SMT using
multi-task learning. In Proceedings of
EMNLP, pages 1055–1065, Seattle,
Washington.
Dean, Jeffrey and Sanjay Ghemawat. 2008.
Mapreduce: Simplified data processing onlarge clusters. Communications of the ACM,
51(1):107–113.
DeNero, John, David Chiang, and Kevin
Knight. 2009. Fast consensus decoding
over translation forests. In Proceedings of
ACL/IJCNLP, pages 567–575, Singapore.
Denkowski, Michael, Chris Dyer, and Alon
Lavie. 2014. Learning from post-editing:
Online model adaptation for statisticalmachine translation. In Proceedings of
EACL, pages 395–404, Gothenburg,
Sweden.
Dreyer, Markus and Yuanzhe Dong. 2015.
Apro: All-pairs ranking optimization for
mt tuning. In Proceedings of NAACL, pages
1018–1023, Denver, Colorado.
Dreyer, Markus and Daniel Marcu. 2012.
Hyter: Meaning-equivalent semantics fortranslation evaluation. In Proceedings of
HLT/NAACL, pages 162–171, Montréal,
Canada.
Duan, Nan, Mu Li, Tong Xiao, and Ming
Zhou. 2009. The Feature Subspace method
for SMT system combination. In
Proceedings of EMNLP, pages 1096–1104,
Singapore.
Duchi, John, Elad Hazan, and Yoram Singer.
2011. Adaptive subgradient methods foronline learning and stochastic
optimization. Journal of Machine Learning
Research, 12:2121–2159.
Duchi, John and Yoram Singer. 2009. Efficientonline and batch learning using forward

Optimization for Statistical Machine Translation

backward splitting. Journal of Machine
Learning Research, 10:2899–2934.
Duh, Kevin and Katrin Kirchhoff. 2008.
Beyond log-linear models: Boosted
minimum error rate training for n-best
re-ranking. In Proceedings of ACL/HLT:
Short Papers, pages 37–40, Columbus, Ohio.
Duh, Kevin, Katsuhito Sudoh, Xianchao Wu,
Hajime Tsukada, and Masaaki Nagata.
2012. Learning to translate with multiple
objectives. In Proceedings of ACL, pages
1–10, Jeju Island, Korea.
Dyer, Chris. 2010a. A Formal Model of
Ambiguity and its Applications in MachineTranslation. Ph.D. thesis, University of
Maryland.
Dyer, Chris. 2010b. Two monolingual parses
are better than one (synchronous parse). In
Proceedings of HLT/NAACL, pages 263–266,
Los Angeles, California.
Dyer, Chris, Hendra Setiawan, Yuval Marton,and Philip Resnik. 2009. The University of
Maryland statistical machine translation
system for the Fourth Workshop on
Machine Translation. In Proceedings of
WMT, pages 145–149, Athens, Greece.
Eidelman, Vladimir. 2012. Optimization
strategies for online large-margin learningin machine translation. In Proceedings of theSeventh Workshop on Statistical MachineTranslation, pages 477–486, Montreal,
Canada.
Eidelman, Vladimir, Yuval Marton, andPhilip Resnik. 2013. Online relative margin
maximization for statistical machinetranslation. In Proceedings of ACL, pages
1116–1126, Sofia, Bulgaria.
Eisner, Jason. 2002. Parameter estimation forprobabilistic finite-state transducers. In
Proceedings of ACL, pages 1–8,
Philadelphia, Pennsylvania.
Flanigan, Jeffrey, Chris Dyer, and Jaime
Carbonell. 2013. Large-scale discriminative
training for statistical machine translation
using held-out line search. In Proceedings of
HLT/NAACL, pages 248–258, Atlanta,
Georgia.
Foster, George and Roland Kuhn. 2009.
Stabilizing minimum error rate training. In
Proceedings of WMT, pages 242–249,
Athens, Greece.
Freund, Yoav, Raj Iyer, Robert E. Schapire,
and Yoram Singer. 2003. An efficient
boosting algorithm for combining
preferences. Journal of Machine Learning
Research, 4:933–969.
Galley, Michel and Christopher D. Manning.
2008. A simple and effective hierarchicalphrase reordering model. In Proceedings of47

Computational Linguistics

EMNLP, pages 848–856, Honolulu,
Hawaii.
Galley, Michel and Chris Quirk. 2011.
Optimal search for minimum error rate
training. In Proceedings of EMNLP, pages
38–49, Edinburgh, Scotland, UK.
Galley, Michel, Chris Quirk, Colin Cherry,and Kristina Toutanova. 2013. Regularized
minimum error rate training. In
Proceedings of EMNLP, pages 1948–1959,
Seattle, Washington.
Gao, Jianfeng and Xiaodong He. 2013.
Training mrf-based phrase translation
models using gradient ascent. In
Proceedings of HLT/NAACL, pages 450–459,
Atlanta, Georgia.
Gesmundo, Andrea and James Henderson.
2011. Heuristic search for non-bottom-up
tree structure prediction. In Proceedings of
EMNLP, pages 899–908, Edinburgh,
Scotland, UK.
Gimpel, Kevin, Dhruv Batra, Chris Dyer, andGregory Shakhnarovich. 2013. A
systematic exploration of diversity inmachine translation. In Proceedings of
EMNLP, pages 1100–1111, Seattle,
Washington.
Gimpel, Kevin and Noah A. Smith. 2009.
Feature-rich translation byquasi-synchronous lattice parsing. In
Proceedings of EMNLP, pages 219–228,
Singapore.
Gimpel, Kevin and Noah A. Smith. 2012.
Structured ramp loss minimization formachine translation. In Proceedings of
HLT/NAACL, pages 221–231, Montréal,
Canada.
Graham, Yvette, Timothy Baldwin, Alistair
Moffat, and Justin Zobel. 2014. Is machinetranslation getting better over time? In
Proceedings of EACL, pages 443–451,
Gothenburg, Sweden.
Green, Spence, Daniel Cer, and Christopher
Manning. 2014. An empirical comparisonof features and tuning for phrase-based
machine translation. In Proceedings of
WMT, pages 466–476, Baltimore,
Maryland.
Green, Spence, Sida Wang, Daniel Cer, andChristopher D. Manning. 2013. Fast andadaptive online training of feature-richtranslation models. In Proceedings of ACL,
pages 311–321, Sofia, Bulgaria.
Green, Spence, Sida I. Wang, Jason Chuang,
Jeffrey Heer, Sebastian Schuster, andChristopher D. Manning. 2014. Humaneffort and machine learnability incomputer aided translation. In Proceedingsof EMNLP, pages 1225–1236, Doha, Qatar.

48

Volume 1, Number 1

Haddow, Barry. 2013. Applying pairwise
ranked optimisation to improve theinterpolation of translation models. In
Proceedings of HLT/NAACL, pages 342–347,
Atlanta, Georgia.
Haddow, Barry, Abhishek Arun, and Philipp
Koehn. 2011. SampleRank training forphrase-based machine translation. In
Proceedings of WMT, pages 261–271,
Edinburgh, Scotland.
Hasan, Saša, Richard Zens, and Hermann
Ney. 2007. Are very large N-best lists
useful for SMT? In Proceedings of
HLT/NAACL, pages 57–60, Rochester, NewYork.
Hayashi, Katsuhiko, Taro Watanabe, Hajime
Tsukada, and Hideki Isozaki. 2009.
Structural support vector machines for
log-linear approach in statistical machinetranslation. In Proceedings of IWSLT, pages
144–151, Tokyo, Japan.
He, Xiaodong and Li Deng. 2012. Maximum
expected BLEU training of phrase andlexicon translation models. In Proceedingsof ACL, pages 292–301, Jeju Island, Korea.
He, Yifan and Andy Way. 2009. Improving
the objective function in minimum error
rate training. In Proceedings of MT Summit,
pages 238–245, Ottawa, Canada.
Herbrich, Ralf, Thore Graepel, and Klaus
Obermayer. 1999. Support vector learningfor ordinal regression. In Proceedings of
ICANN, pages 97–102, Edinburgh,
Scotland, UK.
Hopkins, Mark and Jonathan May. 2011.
Tuning as ranking. In Proceedings of
EMNLP, pages 1352–1362, Edinburgh,
Scotland, UK.
Hsieh, Cho-Jui, Kai-Wei Chang, Chih-Jen Lin,S. Sathiya Keerthi, and S. Sundararajan.
2008. A dual coordinate descent method
for large-scale linear SVM. In Proceedings of
ICML, pages 408–415, Helsinki, Finland.
Huang, Liang and David Chiang. 2007.
Forest rescoring: Faster decoding withintegrated language models. In Proceedingsof ACL, pages 144–151, Prague, Czech
Republic.
Huang, Liang, Suphan Fayong, and Yang
Guo. 2012. Structured perceptron with
inexact search. In Proceedings of
HLT/NAACL, pages 142–151, Montréal,
Canada.
Huang, Liang, Kevin Knight, and Aravind
Joshi. 2006. Statistical syntax-directedtranslation with extended domain of
locality. In Proceedings of AMTA, pages
66–73, Cambridge, Massachusetts.

Graham Neubig and Taro Watanabe

Joachims, Thorsten. 1998. Text categorization
with support vector machines: Learning withmany relevant features. Springer, New York.
Klein, Dan and Christopher D. Manning.
2004. Parsing and hypergraphs. In Harry
Bunt, John Carroll, and Giorgio Satta,
editors, New developments in parsing
technology. Kluwer Academic Publishers,
Norwell, MA, pages 351–372.
Koehn, Philipp. 2010. Statistical MachineTranslation. Cambridge University Press,
New York, NY, 1st edition.
Koehn, Philipp, Hieu Hoang, Alexandra
Birch, Chris Callison-Burch, MarcelloFederico, Nicola Bertoldi, Brooke Cowan,
Wade Shen, Christine Moran, Richard
Zens, Chris Dyer, Ondrej Bojar, Alexandra
Constantin, and Evan Herbst. 2007. Moses:
Open source toolkit for statistical machinetranslation. In Proceedings of ACL: Demoand Poster Sessions, pages 177–180, Prague,
Czech Republic.
Koehn, Philipp, Franz Josef Och, and Daniel
Marcu. 2003. Statistical phrase-basedtranslation. In Proceedings of HLT/NAACL,
pages 48–54, Edmonton, Canada.
Koehn, Philipp and Josh Schroeder. 2007.
Experiments in domain adaptation for
statistical machine translation. In
Proceedings of WMT, pages 224–227,
Prague, Czech Republic.
Kumar, Shankar, Wolfgang Macherey, Chris
Dyer, and Franz Och. 2009. Efficient
minimum error rate training andminimum Bayes-risk decoding fortranslation hypergraphs and lattices. In
Proceedings of ACL/IJCNLP, pages 163–171,
Singapore.
Lagarda, Antonio and Francisco
Casacuberta. 2008. Applying boosting tostatistical machine translation. In
Proceedings of EAMT, pages 88–96,
Hamburg, Germany.
Leusch, Gregor, Evgeny Matusov, andHermann Ney. 2008. Complexity offinding the BLEU-optimal hypothesis in a
confusion network. In Proceedings of
EMNLP, pages 839–847, Honolulu,
Hawaii.
Li, Mu, Yinggong Zhao, Dongdong Zhang,and Ming Zhou. 2010. Adaptive
development data selection for log-linear
model in statistical machine translation. In
Proceedings of COLING, pages 662–670,
Beijing, China.
Li, Zhifei and Jason Eisner. 2009. First- andsecond-order expectation semirings withapplications to minimum-risk training ontranslation forests. In Proceedings of

Optimization for Statistical Machine Translation

EMNLP, pages 40–51, Singapore.
Li, Zhifei and Sanjeev Khudanpur. 2009.
Forest reranking for machine translation
with the perceptron algorithm. GALE bookchapter on MT From Text.
Li, Zhifei, Ziyuan Wang, Jason Eisner,
Sanjeev Khudanpur, and Brian Roark.
2011. Minimum imputed-risk:
Unsupervised discriminative training formachine translation. In Proceedings of
EMNLP, pages 920–929, Edinburgh,
Scotland, UK.
Liang, Huashen, Min Zhang, and Tiejun
Zhao. 2012. Forced decoding for minimum
error rate training in statistical machinetranslation. Journal of Computational
Information Systems, 8(2):861–868.
Liang, Percy, Alexandre Bouchard-Côté, Dan
Klein, and Ben Taskar. 2006. An end-to-end
discriminative approach to machinetranslation. In Proceedings of COLING/ACL,
pages 761–768, Sydney, Australia.
Lin, Chin-Yew and Franz Josef Och. 2004.
Orange: a method for evaluating
automatic evaluation metrics for machinetranslation. In Proceedings of COLING,
pages 501–507, Geneva, Switzerland.
Liu, Chang, Daniel Dahlmeier, andHwee Tou Ng. 2011. Better evaluation
metrics lead to better machine translation.
In Proceedings of EMNLP, pages 375–384,
Edinburgh, Scotland, UK.
Liu, Dong C. and Jorge Nocedal. 1989. On
the limited memory BFGS method forlarge scale optimization. Mathematical
Programming, 45(3):503–528.
Liu, Lemao, Hailong Cao, Taro Watanabe,
Tiejun Zhao, Mo Yu, and Conghui Zhu.
2012. Locally training the log-linear model
for smt. In Proceedings of EMNLP/CoNLL,
pages 402–411, Jeju Island, Korea.
Liu, Lemao and Liang Huang. 2014.
Search-aware tuning for machinetranslation. In Proceedings of EMNLP, pages
1942–1952, Doha, Qatar.
Liu, Lemao, Taro Watanabe, Eiichiro Sumita,
and Tiejun Zhao. 2013. Additive neuralnetworks for statistical machinetranslation. In Proceedings of ACL, pages
791–801, Sofia, Bulgaria.
Liu, Lemao, Tiejun Zhao, Taro Watanabe,
Hailong Cao, and Conghui Zhu. 2012.
Expected error minimization withultraconservative update for SMT. In
Proceedings of COLING: Posters, pages
723–732, Mumbai, India.
Liu, Lemao, Tiejun Zhao, Taro Watanabe, andEiichiro Sumita. 2013. Tuning SMT with alarge number of features via online feature

49

Computational Linguistics

grouping. In Proceedings of IJCNLP, pages
279–285, Nagoya, Japan.
Lo, Chi-kiu, Karteek Addanki, Markus Saers,and Dekai Wu. 2013. Improving machinetranslation by training against an
automatic semantic frame based
evaluation metric. In Proceedings of ACL:
Short Papers, pages 375–381, Sofia,
Bulgaria.
Lopez, Adam. 2008. Statistical machinetranslation. ACM Computing Surveys,
40(3):1 – 49.
Macherey, Wolfgang, Franz Och, Ignacio
Thayer, and Jakob Uszkoreit. 2008.
Lattice-based minimum error rate training
for statistical machine translation. In
Proceedings of EMNLP, pages 725–734,
Honolulu, Hawaii.
Marton, Yuval and Philip Resnik. 2008. Softsyntactic constraints for hierarchicalphrased-based translation. In Proceedings of
ACL/HLT, pages 1003–1011, Columbus,
Ohio.
Mathur, Prashant, Cettolo Mauro, andMarcello Federico. 2013. Online learning
approaches in computer assistedtranslation. In Proceedings of WMT, pages
301–308, Sofia, Bulgaria.
McDonald, Ryan, Koby Crammer, andFernando Pereira. 2005. Online
large-margin training of dependency
parsers. In Proceedings of ACL, pages 91–98,
Ann Arbor, Michigan.
McDonald, Ryan, Keith Hall, and Gideon
Mann. 2010. Distributed training strategies
for the structured perceptron. In
Proceedings of HLT/NAACL, pages 456–464,
Los Angeles, California.
Moore, Robert C. and Chris Quirk. 2008.
Random restarts in minimum error rate
training for statistical machine translation.
In Proceedings of COLING, pages 585–592,
Manchester, UK.
Nakov, Preslav, Francisco Guzman, andStephan Vogel. 2012. Optimizing forsentence-level BLEU+1 yields shorttranslations. In Proceedings of COLING,
pages 1979–1994, Mumbai, India.
Nakov, Preslav, Francisco Guzmán, andStephan Vogel. 2013. A tale about pro andmonsters. In Proceedings of ACL: Short
Papers, pages 12–17, Sofia, Bulgaria.
Neidert, Julia, Sebastian Schuster, Spence
Green, Kenneth Heafield, and Christopher
Manning. 2014. Stanford universityâĂŹs
submissions to the wmt 2014 translation
task. In Proceedings of WMT, pages
150–156, Baltimore, Maryland.

50

Volume 1, Number 1

Nguyen, Patrick, Milind Mahajan, andXiaodong He. 2007. Training
non-parametric features for statisticalmachine translation. In Proceedings of
WMT, pages 72–79, Prague, Czech
Republic.
Nocedal, Jorge and Stephen J Wright. 2006.
Conjugate gradient methods. Springer, NewYork.
Och, Franz Josef. 2003. Minimum error rate
training in statistical machine translation.
In Proceedings of ACL, pages 160–167,
Sapporo, Japan.
Och, Franz Josef and Hermann Ney. 2002.
Discriminative training and maximum
entropy models for statistical machinetranslation. In Proceedings of ACL, pages
295–302, Philadelphia, Pennsylvania.
Och, Franz Josef and Hermann Ney. 2003. A
systematic comparison of various
statistical alignment models. Computational
Linguistics, 29(1):19–51.
Papineni, K. A. 1999. Discriminative training
via linear programming. In Proceedings of
ICASSP, pages 561–564, Phoenix, Arizona.
Papineni, Kishore, Salim Roukos, Todd
Ward, and Wei-Jing Zhu. 2002. BLEU: amethod for automatic evaluation ofmachine translation. In Proceedings of ACL,
pages 311–318, Philadelphia,
Pennsylvania.
Pauls, Adam, John Denero, and Dan Klein.
2009. Consensus training for consensus
decoding in machine translation. In
Proceedings of EMNLP, pages 1418–1427,
Singapore.
Pecina, Pavel, Antonio Toral, and Josef van
Genabith. 2012. Simple and effective
parameter tuning for domain adaptationof statistical machine translation. In
Proceedings of COLING, pages 2209–2224,
Mumbai, India.
Peitz, Stephan, Arne Mauser, Joern Wuebker,
and Hermann Ney. 2012. Forced
derivations for hierarchical machinetranslation. In Proceedings of COLING:
Posters, pages 933–942, Mumbai, India.
Platt, John C. 1999. Fast training of support
vector machines using sequential minimal
optimization. In Bernhard Schölkopf,
Christopher J. C. Burges, and Alexander J.
Smola, editors, Advances in Kernel Methods.
MIT Press, Cambridge, MA, pages
185–208.
Press, William H., Saul A. Teukolsky,
William T. Vetterling, and Brian P.
Flannery. 2007. Numerical Recipes 3rd
Edition: The Art of Scientific Computing.
Cambridge University Press, New York,Graham Neubig and Taro Watanabe

NY, 3rd edition.
Razmara, Majid and Anoop Sarkar. 2013.
Stacking for statistical machine translation.
In Proceedings of ACL: Short Papers, pages
334–339, Sofia, Bulgaria.
Recht, Benjamin, Christopher Re, Stephen
Wright, and Feng Niu. 2011. Hogwild: A
lock-free approach to parallelizing
stochastic gradient descent. In Proceedingsof NIPS, pages 693–701, Vancouver,
Canada.
Rosti, Antti-Veikko, Bing Zhang, Spyros
Matsoukas, and Richard Schwartz. 2010.
BBN system description for WMT10
system combination task. In Proceedings of
WMT, pages 321–326, Uppsala, Sweden.
Rosti, Antti-Veikko, Bing Zhang, Spyros
Matsoukas, and Richard Schwartz. 2011.
Expected BLEU training for graphs: BBN
system description for WMT11 system
combination task. In Proceedings of WMT,
pages 159–165, Edinburgh, Scotland, UK.
Roth, Benjamin, Andrew McCallum, Marc
Dymetman, and Nicola Cancedda. 2010.
Machine translation using overlappingalignments and SampleRank. In
Proceedings of AMTA, Denver, Colorado.
Saluja, Avneesh, Ian Lane, and Ying Zhang.
2012. Machine translation with binary
feedback: a large-margin approach. In
Proceedings of AMTA, San Diego,
California.
Sanchis-Trilles, Germán and Francisco
Casacuberta. 2010. Log-linear weight
optimisation via Bayesian adaptation in
statistical machine translation. In
Proceedings of COLING: Posters, pages
1077–1085, Beijing, China.
Sankaran, Baskaran, Anoop Sarkar, andKevin Duh. 2013. Multi-metric
optimization using ensemble tuning. In
Proceedings of HLT/NAACL, pages 947–957,
Atlanta, Georgia.
Servan, Christophe and Holger Schwenk.
2011. Optimising multiple metrics with
MERT. Prague Bulletin of Mathematical
Linguistics, 96(1):109–117.
Setiawan, Hendra and Bowen Zhou. 2013.
Discriminative training of 150 million
translation parameters and its application
to pruning. In Proceedings of HLT/NAACL,
pages 335–341, Atlanta, Georgia.
Shen, Libin, Anoop Sarkar, and Franz Josef
Och. 2004. Discriminative reranking formachine translation. In Daniel Marcu
Susan Dumais and Salim Roukos, editors,
Proceedings of HLT/NAACL, pages 177–184,
Boston, Massachusetts.

Optimization for Statistical Machine Translation

Simianer, Patrick, Stefan Riezler, and Chris
Dyer. 2012. Joint feature selection in
distributed stochastic learning forlarge-scale discriminative training in smt.
In Proceedings of ACL, pages 11–21, Jeju
Island, Korea.
Sindhwani, Vikas, S. Sathiya Keerthi, andOlivier Chapelle. 2006. Deterministic
annealing for semi-supervised kernel
machines. In Proceedings of ICML, pages
841–848, Pittsburgh, Pennsylvania.
Smith, David A. and Jason Eisner. 2006.
Minimum risk annealing for training
log-linear models. In Proceedings of
COLING/ACL: Poster Sessions, pages
787–794, Sydney, Australia.
Snover, Matthew, Bonnie Dorr, Richard
Schwartz, Linnea Micciulla, and John
Makhoul. 2006. A study of translation edit
rate with targeted human annotation. In
Proceedings of AMTA, pages 223–231,
Cambridge, Massachusetts.
Sokolov, Artem, Guillaume Wisniewski, andFrancois Yvon. 2012a. Computing lattice
BLEU oracle scores for machinetranslation. In Proceedings of EACL, pages
120–129, Avignon, France.
Sokolov, Artem, Guillaume Wisniewski, andFrançois Yvon. 2012b. Non-linear n-best
list reranking with few features. In
Proceedings of AMTA, San Diego,
California.
Sokolov, Artem and François Yvon. 2011.
Minimum error rate training semiring. In
Proceedings of EAMT, pages 241–248,
Leuven, Belgium.
Suzuki, Jun, Kevin Duh, and Masaaki
Nagata. 2011. Distributed minimum error
rate training of SMT using particle swarm
optimization. In Proceedings of IJCNLP,
pages 649–657, Chiang Mai, Thailand.
Tan, Ming, Tian Xia, Shaojun Wang, andBowen Zhou. 2013. A corpus level MIRA
tuning strategy for machine translation. In
Proceedings of EMNLP, pages 851–856,
Seattle, Washington.
Taskar, Ben, Vassil Chatalbashev, Daphne
Koller, and Carlos Guestrin. 2005.
Learning structured prediction models: A
large margin approach. In Proceedings of
ICML, pages 896–903, Bonn, Germany.
Tibshirani, Robert. 1996. Regression
shrinkage and selection via the lasso.
Journal of the Royal Statistical Society. Series
B (Methodological), 58(1):267–288.
Tillman, Christoph. 2004. A unigram
orientation model for statistical machinetranslation. In Proceedings of HLT/NAACL,
pages 101–104, Boston, Massachusetts.

51

Computational Linguistics

Tillmann, Christoph and Tong Zhang. 2006.
A discriminative global training algorithm
for statistical MT. In Proceedings of
COLING/ACL, pages 721–728, Sydney,
Australia.
Toutanova, Kristina and Byung-Gyu Ahn.
2013. Learning non-linear features formachine translation using gradientboosting machines. In Proceedings of ACL:
Short Papers, pages 406–411, Sofia,
Bulgaria.
Tromble, Roy, Shankar Kumar, Franz Och,and Wolfgang Macherey. 2008. Latticeminimum Bayes-risk decoding forstatistical machine translation. In
Proceedings of EMNLP, pages 620–629,
Honolulu, Hawaii.
Turian, Joseph, Benjamin Wellington, and
I Dan Melamed. 2006. Scalable
discriminative learning for natural
language parsing and translation. In
Proceedings of NIPS, pages 1409–1416,
Vancouver, Canada.
Ueffing, Nicola, Gholamreza Haffari, andAnoop Sarkar. 2007. Transductive learningfor statistical machine translation. In
Proceedings of ACL, pages 25–32, Prague,
Czech Republic.
Ueffing, Nicola, Franz Josef Och, andHermann Ney. 2002. Generation of word
graphs in statistical machine translation. In
Proceedings of EMNLP, pages 156–163,
Philadelphia, Pennsylvania.
Venugopal, Ashish and Stephan Vogel. 2005.
Considerations in maximum mutual
information and minimum classification
error training for statistical machinetranslation. In Proceedings of EAMT, pages
271–279, Budapest, Hungary.
Wang, Zhuoran, John Shawe-Taylor, andSandor Szedmak. 2007. Kernel regression
based machine translation. In Proceedingsof HLT/NAACL: Short Papers, pages
185–188, Rochester, New York.
Watanabe, Taro. 2012. Optimized online rank
learning for machine translation. In
Proceedings of HLT/NAACL, pages 253–262,
Montréal, Canada.
Watanabe, Taro, Jun Suzuki, Hajime
Tsukada, and Hideki Isozaki. 2007. Online
large-margin training for statisticalmachine translation. In Proceedings of
EMNLP/CoNLL, pages 764–773, Prague,
Czech Republic.
Wu, Dekai. 1997. Stochastic inversion
transduction grammars and bilingualparsing of parallel corpora. Computational
Linguistics, 23(3):377–403.

52

Volume 1, Number 1

Wuebker, Joern, Arne Mauser, and Hermann
Ney. 2010. Training phrase translation
models with leaving-one-out. In
Proceedings of ACL, pages 475–484,
Uppsala, Sweden.
Wuebker, Joern, Stephan Peitz, Andreas
Guta, and Hermann Ney. 2014. The rwth
aachen machine translation systems for
iwslt 2014. In Proceedings of IWSLT, pages
150–154, Lake Tahoe, Nevada.
Xiang, Bing and Abraham Ittycheriah. 2011.
Discriminative feature-tied mixture
modeling for statistical machinetranslation. In Proceedings of ACL/HLT,
pages 424–428, Portland, Oregon.
Xiao, Lin. 2010. Dual averaging methods forregularized stochastic learning and online
optimization. Journal of Machine Learning
Research, 11:2543–2596.
Xiao, Xinyan, Yang Liu, Qun Liu, andShouxun Lin. 2011. Fast generation oftranslation forest for large-scale SMT
discriminative training. In Proceedings of
EMNLP, pages 880–888, Edinburgh,
Scotland, UK.
Xiao, Xinyan and Deyi Xiong. 2013.
Max-margin synchronous grammar
induction for machine translation. In
Proceedings of EMNLP, pages 255–264,
Seattle, Washington.
Yamada, Kenji and Kevin Knight. 2001. A
syntax-based statistical translation model.
In Proceedings of ACL, pages 523–530,
Toulouse, France.
Yu, Heng, Liang Huang, Haitao Mi, and Kai
Zhao. 2013. Max-violation perceptron andforced decoding for scalable MT training.
In Proceedings of EMNLP, pages 1112–1123,
Seattle, Washington.
Zaidan, Omar F. and Chris Callison-Burch.
2009. Feasibility of human-in-the-loop
minimum error rate training. In Proceedingsof EMNLP, pages 52–61, Singapore.
Zens, Richard, Sasa Hasan, and Hermann
Ney. 2007. A systematic comparison oftraining criteria for statistical machinetranslation. In Proceedings of
EMNLP/CoNLL, pages 524–532, Prague,
Czech Republic.
Zhao, Bing and Shengyuan Chen. 2009. A
simplex Armijo downhill algorithm for
optimizing statistical machine translation
decoding parameters. In Proceedings of
HLT/NAACL: Short Papers, pages 21–24,
Boulder, Colorado.
Zhao, Yinggong, Shujie Liu, Yangsheng Ji,
Jiajun Chen, and Guodong Zhou. 2011.
Transductive minimum error rate training
for statistical machine translation. In

Graham Neubig and Taro Watanabe

Optimization for Statistical Machine Translation

Proceedings of IJCNLP, pages 641–648,
Chiang Mai, Thailand.
Zhou, Liang, Chin-Yew Lin, and Eduard
Hovy. 2006. Re-evaluating machinetranslation results with paraphrase
support. In Proceedings of EMNLP, pages
77–84, Sydney, Australia.
Zinkevich, Martin, John Langford, andAlex J. Smola. 2009. Slow learners are fast.
In Proceedings of NIPS, pages 2331–2339,
Vancouver, Canada.

Appendix A: Derivation for xBLEU Gradients
In this appendix, we explain in detail how to derive a gradient for the xBLEU objective
in Equation (54), which has not been described completely in previous works.
First, we consider the brevity penalty
φ(x) = min {1, exp(x)} .

(A.1)

We can see that it is not differentiable, which precludes the use of gradient-basedalgorithms. To remedy this problem Rosti et al. (2010) propose the use of the following
differentiable approximation for the brevity penalty (Rosti et al. 2010).

ϕ(x) =

exp(x) − 1+ 1.
1 + exp(10000x)(A.2)

Using Equation (54) and the approximated brevity penalty in Equation (A.2), we can
express xBLEU = exp(P ) · B, leading to the following equation
4
N X
K
N X
K
X
X
1X
P =
log
mn,i,k − log
cn,i,k
4 n=1
i=1
i=1
k=1

!
(A.3)

k=1

B = ϕ (1 − R)
PN PK
ri,k
.
R = PNi=1PKk=1
i=1
k=1 c1,i,k

(A.4)
(A.5)

Taking the derivative of xBLEU with respect to w, we get
N K∂ xBLEU X X ∂ xBLEU ∂ log pi,k=∂w
∂ log pi,k
∂w
i=1

(A.6)

k=1

=

N X
K X
K
X
∂ xBLEU ∂ log pi,k ∂si,k0
i=1 k=1 k0 =1∂ log pi,k∂si,k0

∂w

.

(A.7)

53

Computational Linguistics

Volume 1, Number 1

Thus,∂si,k0= γ · h(f (i) , ek0 , dk0 )∂w∂ log pi,k= δ(k, k 0 ) − pi,k0 ,∂si,k0

(A.8)
(A.9)

and
∂ xBLEU∂B∂P= exp(P ) ·+ exp(P ) ·· B.
∂ log pi,k∂ log pi,k∂ log pi,k

(A.10)

Additionally, the following equation holds∂B∂B ∂1 − R=∂ log pi,k
∂1 − R ∂ log pi,k
= ϕ0 (1 − R) · (−R) ·(A.11)

PN

i0 =1

ri,k
PK

k0 =1 ri0 ,k0

− PN

i0 =1

c1,i,kPK

4mn,i,k∂P
1X
cn,i,k=− PN PK.
PN PK∂ log pi,k4 n=1 i0 =1 k0 =1 mn,i0 ,k0
i0 =1
k0 =1 cn,i0 ,k0

k0 =1 c1,i0 ,k0!
(A.12)(A.13)

After calculating this gradient, it is possible to optimize this according to standard
gradient-based methods. However, like MR using sentence-level evaluation mentioned
in Section 5.5, the evaluation measure is not convex, and the same precautions need tobe taken to avoid falling into local optima.

54

55