2 Motivation of the statistical approach

Increasing computational power was one of the reasons to raise the current interest in MT. The scientific community is quite involved in MT. There is an active participation in major events, such as evaluations (NISTFootnote ¹,WMTFootnote ², IWSLTFootnote ³), and outstanding research groups dedicate great efforts to contribute to MT advances. The major approaches to MT are generally distinguished according to their core technology. Under this classification, there are the rule-based and the corpus-based approaches.

• • In the rule-based approach, human experts specify a set of rules to describe the translation process. This approach requires an enormous amount of input from human experts (Dorr, Reference Dorr1994; Arnold and Balkan, Reference Arnold and Balkan1995).

• • Under the corpus-based approach, the knowledge is automatically extracted by analyzing translation examples from a parallel corpus (built by human experts). The advantage is that, once the required techniques have been developed for a given language pair, (in theory) MT systems can be very quickly developed for new language pairs using provided training data. Within the corpus-based approaches, they can be further distinguished between example-based and statistical MT (EBMT and SMT, respectively). The former makes use of previously seen examples in parallel corpora (bilingual aligned text at the level of sentence consisting in human translations) as its main knowledge base. It is essentially a translation by analogy. The latter applies statistical learning techniques to build a translation model given the training parallel corpora. Thus, it relies on statistical parameters and a set of translation and language models, among other data-driven features. This approach initially worked on a word-by-word basis. However, current systems attempt to introduce a certain degree of linguistic analysis into the SMT approach. SMT approaches are mainly distinguished depending on the translation model (Lopez (Reference Lopez2007) reports a formal review of most SMT approaches):

  • – The phrase-based system identifies any contiguous sequence of words (called phrase) as unit of translation. Each source phrase is non-empty and translates to exactly one non-empty target phrase. The phrase-based translation model is trained using relative frequencies.

  • – The Ngram-based approach is a variation of the phrase-based approach. Differently to the phrase-based translation model, the Ngram-based translation model is trained on bilingual n-grams (Mariño et al., Reference Mariño, Banchs, Crego, de Gispert, Lambert, Fonollosa and Costa-jussà2006).

  • – Formally syntax-based SMT learns a synchronous context-free grammar from a bitext without any syntactic information (Wu, Reference Wu1996; Chiang, Reference Chiang2007).

  • – Linguistically and formally syntax-based SMT models are tied to some linguistic representations of syntax. These SMT systems parse a source sentence as a target sentence when translating (Yamada and Knight, Reference Yamada and Knight2002).

  • – Dependency treelet translations (Menezes et al., Reference Menezes, Toutanova and Quirk2006) align the parallel corpus, then project the source dependency parse onto the target sentence and extract dependency treelet translation pairs. Then, they train a tree-based ordering model. One of the main advantages here is that reordering is based on syntax.

Comparing with the different MT approaches, the main advantages of SMT are cited as follows:

• • SMT systems are not tailored to any specific pair of languages. To the translation system, any language is treated the same, and there is no manually created rule-set of grammar, metaphors and similar language considerations.

• • There is a better use of resources. There is a great deal of natural language in machine-readable format. SMT relies on a large corpus of texts which are available in multiple languages.

• • Generally, given that it is a corpus-based approach, SMT system is learning from existing human translations. Therefore, more natural translations have been achieved in international evaluations compared with other MT approaches.

However, notice that SMT requires resources such as parallel corpora and high computationally resources. Moreover, the main challenges in SMT are: syntactic such as word reordering, which may be quite difficult in cases of language pairs with different structures; morphological, specially when translating from a less inflected language into a more inflected language; and lexical such as out-of-vocabulary words and domain adaptation.

3 Statistical machine translation formal description

The main goal of SMT is the translation of a text given in some source language into a target language. A source string $ s_{1}^{J} \, = \,{{s}_1} \ldots {{s}_j} \ldots {{s}_J} $ has to be translated into a target string $ t_{1}^{I} \, = \,{{t}_1} \ldots {{t}_i} \ldots {{t}_I} $. Among all possible target strings, the string with the highest probability will be chosen:

$$\tilde{t}_{1}^{I} \, = \,\mathop {argmax}\limits_{t_{1}^{I} } \,P(t_{1}^{I} |s_{1}^{J} )$$

The first SMT systems were reformulated using Bayes's rule. This approach, called the noisy channel, models the probability of a target language sentence $ t_{1}^{I} \, = \,{{t}_1} \ldots {{t}_I} $ given a source language sentence $ s_{1}^{J} \, = \,{{s}_1} \ldots {{s}_J} $ as follows:

$$\tilde{t}_{1}^{I} \, = \,\mathop {argmax}\limits_{t_{1}^{I} } \,\frac{{p(s_{1}^{J} |t_{1}^{I} )\,p(t_{1}^{I} )}}{{p(s_{1}^{J} )}}$$

The denominator $ p(s_{1}^{J} ) $ inside the argmax function can be ignored since the best $ t_{1}^{I} $ sentence for a fixed sentence $ s_{1}^{J} $ is the objective function, and hence $ p(s_{1}^{J} ) $ is a constant:

$$\tilde{t}_{1}^{I} \, = \,\mathop {argmax}\limits_{t_{1}^{I} } \,p(s_{1}^{J} |t_{1}^{I} )\,p(t_{1}^{I} )$$

Here $ p(t_{1}^{I} ) $ is the language model of the target language. A language model is usually formulated as a probability distribution over strings that attempts to reflect how likely a string occurs inside a language (Chen & Goodman, Reference Chen and Goodman1998). SMT systems make use of the same n-gram language models as do speech recognition and other applications. The language model component is monolingual, so acquiring training data is relatively easy. Then, $ p(s_{1}^{J} |t_{1}^{I} ) $ is the string translation model, which is the basis of the translation. The argmax operation denotes the search problem, that is, the generation of the output sentence in the target language.

In recent systems, such an approach has been expanded to a more general maximum entropy approach in which a log-linear combination of multiple feature functions (h_m) is implemented (Och, Reference Och2003). With respect to criterion shown in Equation (3), this approach leads to maximizing a linear combination of feature functions:

$$\tilde{t}\, = \,\mathop {argmax}\limits_t \left\{ {\mathop{\sum}\limits_{m\, = \,1}^M {{\lambda }_m}{{h}_m}(s_{1}^{J}, t_{1}^{I} )} \right\}$$

where λ_m is the weight given to the $ {{h}_m}(s_{1}^{J}, t_{1}^{I} ) $ feature function and M is the total number of feature functions.

The overall architecture of this statistical translation approach is summarized in Figure 1.

Figure 1

Architecture of the translation approach based on the log-linear framework approximation

4 Statistical word alignment

A key issue in modeling the string translation probability $ p(s_{1}^{J} |t_{1}^{I} ) $ is to define the correspondence between words of the target and source sentences. This section reports a brief description of the most popular word alignment approaches used to implement a phrase-based system.

In typical cases, it can be assumed a sort of pairwise dependence by considering all word pairs (s_j, t_i) for a given sentence pair $ (s_{1}^{J}, t_{1}^{I} ) $. A word alignment is a mapping between the source words and the target words in a set of parallel sentences. Given parallel texts, the task of automatic word alignment focuses on detecting which tokens or set of tokens from each language are connected together in a given translation context or if any token has no alignment in which case is aligned to NULL.

Figure 2 shows a visualization of an alignment between the English sentence For that is the decisive point here and the Spanish sentence Este es el punto decisivo. Additionally, this figure shows what is called the word alignment matrix.

Figure 2

Word alignment example

The alignment approach is an instance of unsupervised learning, where the system is not given examples of the kind of output desired, but it is instead trying to find values for the alignments which best explain the observed bitext.

In principle, there may be an arbitrary alignment relationships between the target and the source words. So-called statistical alignment models are decomposed into:

• • fertility model, which accounts for the probability that a target word t_i generates φ_i words in the source sentence.

• • lexicon model, which models the probability to produce a source word s_j given a target word t_i.

• • distortion model, which tries to explain the phenomenon of placing a source word in position j given that the target word is placed in position i in the target sentence (also used with inverted dependencies, and known as the alignment model).

The different combinations of these three models are commonly known in the literature as IBM models (Brown et al., Reference Brown, Della Pietra, Della Pietra and Mercer1993). Currently, word alignments based on IBM and HMM models for which a systematic performance comparison can be found in Och (Reference Och2003), are considered to be the state of the art. Typically, the implementation by Och and Ney (Reference Och and Ney2000), which is freely available in the GIZA++ package, is used (Figure 3).

Figure 3

Illustration of the generative process underlying IBM models

There are some current SMT systems that do not use IBM model parameters in their training schemes, but instead use only the most probable alignment (using a Viterbi search) given the estimated IBM models (typically by means of GIZA++). IBM models are asymmetric probabilistic models. Therefore, usually alignments are computed from source-to-target and target-to-source and, then, symmetrization strategies are applied. Several symmetrization algorithms have been proposed, the most widely known being the union, intersection and refined (Och & Ney, Reference Och and Ney2000) of source-to-target and target-to-source alignments, and the grow-diag-final (Koehn et al., Reference Koehn, Amittai, Birch, Callison-Burch, Osborne, Talbot and White2005), which employs the previous intersection and union alignments.

Lately, recent work has begun to explore supervised methods that rely on presenting the system with a (usually small) number of manually aligned sentences (Callison-Burch et al., Reference Callison-Burch, Talbot and Osborne2004). Besides the benefit of the additional information provided by supervision, these models are able to combine many features of the data, such as context, syntactic structure, part-of-speech or translation lexicon information, which are difficult to integrate into the generative statistical models traditionally used (Fraser & Marcu, Reference Fraser and Marcu2006; Lambert, Reference Lambert2008). Additionally, discriminative alignment training allows to extend the IBM models with new (sub)models that leads to additional increases in word alignment accuracy.

In order to evaluate the quality of the word alignment task, the Alignment Error Rate (AER) measure as proposed in Och and Ney (Reference Och and Ney2000) has been commonly used. Given a manual gold standard alignment with the criterion of Sure and Possible links, Recall, Precision and AER measures are defined as follows:

$$\displaylines{ Recall\, = \,\frac{{\left| {A \cap S} \right|}}{{\left| S \right|}},\; \; Precision\, = \,\frac{{\left| {A \cap P} \right|}}{{\left| A \right|}} \cr & AER\, = \,1\,{\rm{ - }}\,\frac{{\left| {A \cap S} \right|\, + \,\left| {A \cap P} \right|}}{{\left| A \right|\, + \,\left| S \right|}} \cr}$$

where A is the hypothesis alignment and S is the set of Sure links in the gold standard reference, and P includes the set of Possible and Sure links in the gold standard reference.

In Fraser and Marcu (Reference Fraser and Marcu2006), the authors confirm experimentally that the AER does not correlate well with MT performance. On the other hand, they obtain strong correlations with the F-Measure:

$${\rm{F {\hbox -} Measure}}\;{\rm{with}}\;{\rm{Sure}}\;{\rm{and}}\;{\rm{Possible}}\,(A,P,S,\alpha )\, = \,\frac{1}{\displaystyle{\frac{\alpha }{{Precision(A,P)}}\, + \,\frac{{(1{\rm{ - }}\alpha )}}{{Recall(A,S)}}}}$$

The basic property of F-measure is that unbalanced Precision and Recall should be penalized.

Nowadays, the quality of the word alignment algorithms is highly dependent on the quality and quantity of parallel corpus. Additionally, the more monotonic are the language pairs, the better the word alignment.

5 Phrase-based statistical machine translation model

The job of the translation model, given a target sentence and a foreign sentence, is to assign a probability that $ t_{1}^{I} $ generates $ s_{1}^{J} $. While these probabilities can be estimated by thinking about how each individual word is translated, modern SMT is based on the intuition that a better way to compute these probabilities is to consider the behavior of phrases (sequences of words). The intuition of phrase-based SMT is to use phrases as well as single words as the fundamental units of translation. Phrases are estimated from multiple segmentations of the word-aligned parallel corpora by using relative frequencies. The main difference between the phrase- and word-based models is that the former manages bilingual units of several words (i.e. discurso extenso # long speech) instead of only individual words themselves.

The basic idea of phrase-based translation is to segment the given source sentence into units (i.e. phrases), then translate each phrase and finally compose the target sentence from these phrase translations.

Basically, a bilingual phrase is a pair of m source words and n target words. For extraction from a bilingual word-aligned training corpus, two additional constraints are considered:

1. 1. the words are consecutive and

2. 2. they are consistent with the word alignment matrix, meaning that words inside the phrase are only aligned to words inside the phrase.

The phrase-based approach was first presented in Och (Reference Och1999) and named Alignment Templates, consisting of pairs of generalized phrases which allow for word classes and include internal word alignments.

A simplification of this model is the so-called phrase-based SMT presented in Zens et al. (Reference Zens, Och and Ney2002). This approach does not use word classes but instead uses bilingual phrases without internal alignment. The following criterion defines the set of bilingual phrases BP of the sentence pair ($ s_{1}^{J} ;t_{1}^{I} $) that is consistent with the word alignment matrix A:

$$BP(s_{1}^{J}, t_{1}^{I}, A)\, = \,\{ (s_{j}^{{j\, + \,m}}, t_{i}^{{i\, + \,n}} )\,:\,\forall (i^{\prime},j^{\prime})\,{\epsilon}\,A:j\,{\leqslant}\,j^{\prime}\,{\leqslant}\,j\, + \,m\, \leftrightarrow \,i\,{\leqslant}\,i^{\prime}\,{\leqslant}\,i\, + \,n\} $$

Figure 4 shows the phrases (maximum length of three words) extracted from the word alignment shown in Figure 2.

Figure 4

Phrase extraction example. Source and target are separated by $ ||| $

The extraction of bilingual phrases from a word alignment corpus can be done in a straightforward manner and pseudo-code is reported in Zens et al. (Reference Zens, Och and Ney2002). To use the bilingual phrases in the translation model, the hidden variable B is introduced. This is a segmentation of the sentence pair ($ s_{1}^{J} ;t_{1}^{I} $) into K phrases ($ s_{K}^{J} ;t_{1}^{K} $). It is used a one-to-one phrase alignment, that is, one source phrase is translated by exactly one target phrase.

$$Pr(s_{1}^{J} |t_{1}^{I} )\, = \,\alpha (t_{1}^{I} )\,\times \,\mathop{\sum}\limits_B Pr({{\tilde{s}}_k}|{{\tilde{t}}_k})$$

where the hidden variable B is the segmentation of the sentence pair in K bilingual phrases $ (\tilde{s}_{1}^{K}, \tilde{t}_{1}^{K} ) $, and $ \alpha (t_{1}^{I} ) $ assumes equal probability for all segmentations.

Given the collected phrase pairs, the phrase translation probability distribution is commonly estimated by relative frequency in both directions:

$$P(s|t)\, = \,\frac{{N(s,t)}}{{N(t)}}$$

$$P(t|s)\, = \,\frac{{N(s,t)}}{{N(s)}}$$

where N(s, t) means the number of times the phrase s is translated by t. N(s) and N(t) are the number of times the source and the target phrase appear, respectively.

Recently, the phrase-based translation model has been further improved by using the factored Language Models (FLMs) technique. FLMs are a newer language modeling technique: more sophisticated than n-grams, but more widely applicable than the syntax-based models. FLMs do not reduce the complexity of an n-gram model, but they use a richer set of conditioning possibilities to improve performance. These models are capable of incorporating some amount of linguistic information, such as semantic classes or parts of speech. The appeal of FLMs for MT is this option to layer linguistic information in the corpus, when available, on top of the power of statistical n-gram language models (Axelrod, Reference Axelrod2006).

6 Log-linear framework and decoding

Currently, most SMT systems consider a log-linear framework of probabilistic information (Och, Reference Och2002; Bertoldi et al., Reference Bertoldi, Cattoni, Cettolo, Chen and Federico2006; Mariño et al., Reference Mariño, Banchs, Crego, de Gispert, Lambert, Fonollosa and Costa-jussà2006; Matusov et al., Reference Matusov, Zens, Vilar, Mauser, Popovic, Hasan and Ney2006). This section describes the log-linear framework and names the main decoding used in a phrase-based system.

Following Figure 1, the simplest phrase-based approach (the noisy channel) would be the following combination of two feature functions (h):

$${{h}_{tm}}(t_{1}^{I}, s_{1}^{J} )\, = \,log\,p(s_{1}^{J} |t_{1}^{I} );\,\,\,{{h}_{lm}}(t_{1}^{I}, s_{1}^{J} )\, = \,log\,p(t_{1}^{I} )$$

Here, $ p(t_{1}^{I} ) $ denotes the trained language model and $ p(s_{1}^{J} |t_{1}^{I} ) $ denotes the trained translation model. Then, there can be obtained two maximum entropy model parameters λ_lm and λ_tm that can be trained using an optimization algorithm.

Additional feature functions widely used are cited as follows:

• • A word bonus for each produced target word.

$${{h}_{wb}}(t_{1}^{I}, s_{1}^{J} )\, = \,I$$

• • Additional language models introducing linguistic knowledge as Part of Speech (POS) target language model (Costa-jussà et al., Reference Costa-jussà, Crego, de Gispert, Lambert, Khalilov, Mariño, Fonollosa and Banchs2006; Crego et al., Reference Crego, de Gispert, Lambert, Costa-jussà, Khalilov, Banchs, Mariño and Fonollosa2006).

• • A distortion model. Distortion in SMT refers to a word having a different (‘distorted’) position in the target sentence than the corresponding word had in the source sentence. The feature functions related to distortion or reordering are reviewed and proposed in the next chapter.

• • Lexical models (such as IBM model 1 from source-to-target and from target-to-source).

$${{h}_{ib{{m}_1}}}(t_{1}^{I}, s_{1}^{J} )\, = \,log\frac{1}{{{{{(I\, + \,1)}}^J} }}\prod\limits_{j\, = \,1}^J \mathop{\sum}\limits_{i\, = \,0}^I p(t_{j}^{n} |s_{i}^{n} )$$

Figure 5 draws how to train three of the above mentioned feature functions.

Figure 5

Training steps of the most common feature functions

All feature functions are combined in the decoder, which is in charge of solving the maximization problem of translation shown in Equation (3). Given that the decoding is an NP-hard problem, the phrase-based system uses a simplified search based on a beam search and its general framework is described in Koehn et al. (Reference Koehn, Hoang, Birch, Callison-Burch, Federico, Bertoldi, Cowan, Shen, Moran, Zens, Dyer, Bojar, Constantin and Herbst2007). The most relevant simplifications are the pruning away of low-scoring hypotheses and the reordering constraints in order to reduce the search space. With a well-tuned beam size, it is possible to gain large speedups with very little loss of accuracy (Tillmann & Ney, Reference Tillmann and Ney2003; Lopez, Reference Lopez2007). Moses Footnote ⁴ is a freely available phrase-based decoder and it is widely used. When the feature functions do not have a feasible integration in the beam search procedure, feature functions are incorporated in rescoring (see Section 9).

7 Reordering approaches

This section describes several state-of-the-art reordering techniques employed in SMT systems. Reordering is understood as the word order redistribution of the translated words.

In initial SMT systems, this different order is only modeled within the limits of translation units. Relying only in the reordering provided by translation units may not be good enough in most language pairs, which might require longer reorderings. Therefore, additional techniques may be deployed to face the reordering challenge. Costa-jussà and Fonollosa (Reference Costa-jussà and Fonollosa2009b) propose a classification of reordering techniques that tries to cover most recent reordering works. This classification can be summarized as follows:

• • Straight heuristic reordering search constraints: These techniques are founded on the application of distance-based restrictions to the search space. The use of these constraints generates simple reordering models, which imply a necessary balance between translation accuracy and efficiency. One simple model is a ‘weak’ distance-based distortion model that was initially used to penalize the longest reorderings. Other reordering constraints are: distortion (Koehn et al., Reference Koehn, Och and Marcu2003; Och & Ney, Reference Och and Ney2004); IBM (Berger et al., Reference Berger, Della Pietra and Della Pietra1996; Tillmann & Ney, Reference Tillmann and Ney2003); ITG (Wu, Reference Wu1996); local (Kanthak et al., Reference Kanthak, Vilar, Matusov, Zens and Ney2005) or maxjumps (Crego, Reference Crego2008). In view of content independence of the distortion and flat reordering models, several researchers (Tillmann, Reference Tillmann2004; Koehn et al., Reference Koehn, Amittai, Birch, Callison-Burch, Osborne, Talbot and White2005) proposed a more powerful model called lexicalized reordering model that is phrase dependent. Lexicalized reordering model learns local orientations (monotone or non-monotone) with probabilities for each bilingual phrase from training data. This lexicalized reordering approach is implemented in the open source Moses toolkitFootnote ⁵.

• • Source reordering approaches: Here the reordering rules are defined in the source language. The idea is to reorder the source language in a way that better matches the target language by using some of the following strategies:

  • – Deterministic Reordering Rules (Popovic & Ney, Reference Popovic and Ney2006; Costa-jussà et al., Reference Costa-jussà, Fonollosa and Monte2011). The source corpus is reordered following a set of rules. These rules have been automatically learned using lexical and/or morphological information, that is, POS. The decoder search is monotonic.

  • – Clause Restructuring (Xia & McCord, Reference Xia and McCord2004; Collins et al., Reference Collins, Koehn and Kucerová2005; Wang et al., Reference Wang, Collins and Koehn2007). These methods, which are applied both in training and decoding steps, use syntactic information to reorder source words in SMT as a preprocessing step. This source reordering is complemented with a local reordering in search.

  • – Input Reordering Graph (Kanthak et al., Reference Kanthak, Vilar, Matusov, Zens and Ney2005; Mauser et al., Reference Mauser, Matusov and Ney2006). The word alignment is then used as a function of source words to reorder the source corpus. Inspired by Knight and Al-Onaizan (Reference Knight and Al-Onaizan1998), they permute the source sentence to provide a source input graph which extends the search graph. The reordering hypotheses of the source input graph are limited by several constraints, such as IBM or ITG. Similarly, in Crego and Mariño (Reference Crego and Mariño2007) and Zhang et al. (Reference Zhang, Zens and Ney2007), the reordering search problem is addressed through a source input graph. In this case, the reordering hypotheses are defined from a set of linguistically motivated rules (either using POS or chunks). In Costa-jussà and Fonollosa (Reference Costa-jussà and Fonollosa2009a), the reordering hypotheses are automatically extracted by using an Ngram-based reordering approach, and in Khalilov et al. (Reference Khalilov, Fonollosa and Dras2009), reordering hypotheses are derived through a syntactically augmented alignment of source and target texts.

• • Reordering in rescoring: Typically the rescoring methods have generally provided small accuracy gains given the restriction of being applied to an n-best list. In these approaches, a baseline system is used to generate n-best translation hypotheses. Statistical or syntactic features are then used in a second model that re-ranks the n-best lists, in an attempt to improve over the baseline approach. Koehn and Knight (Reference Koehn and Knight2003) apply a re-ranking approach to the sub-task of noun–phrase translation. Hassan et al. (Reference Hassan, Hearne, Way and Sima'an2006) introduces super-tag information.

• • Reordering based on syntax structures: This type of reordering is not carried out using standard phrases. In fact, it solves translation following some of the other SMT approaches, which were named in Section 2. Therefore, as this is out of this paper's scope, only some standard works are referenced. In Quirk et al. (Reference Quirk, Menezes and Cherry2005) and Langlais and Gotti (Reference Langlais and Gotti2006), a dependency tree-based reordering model is inferred from aligned string-tree pairs. Parsing is performed on the source language and a corresponding dependency grammar is inferred on the aligned target side. Others use constituent trees (Chiang, Reference Chiang2007), in which context-free rules are inferred from string-to-string pairs (notice: no parsing is required). In this approach, phrases are reorganized into hierarchical by reducing subphrases to variables. This template-based scheme not only captures the reorderings of phrases, but also integrates some phrasal generalizations into the global model. This type of system has became more popular in recent International Evaluations, for example, see Vilar et al. (Reference Vilar, Stein, Zhang, Matusov, Mauser, Bender, Mansour and Ney2008).

8 Minimum error training

This section reports several optimization strategies that are used to train the model parameters $ \lambda _{1}^{M} $ of Equation (4).

An adequate algorithm for such a task is the downhill simplex algorithm (Nelder & Mead, Reference Nelder and Mead1965) or the SPSA (Lambert & Banchs, Reference Lambert and Banchs2006). The method uses a geometrical figure called a simplex consisting in N dimensions of N + 1 points and all their interconnecting line segments, polygonal faces, etc. The starting point is a set of N + 1 points in parameter space, defining an initial simplex. At each step, the simplex performs geometrical operations (reflexions, contractions and expansions) until a local minimum is reached. Generally it adjusts the log-linear weights so as to maximize an objective function. Note that in this problem, only a local optimum is usually found. Tuning is performed according to MT quality measures and evaluated over development data.

Nowadays, the most widely used optimization scheme is an n-best list, which is produced by the decoder (see Figure 6). The optimization algorithm is used to minimize the translation error while rescoring this n-best list. With the optimal coefficients, a new decoding is performed so as to produce an updated n-best list (Bertoldi, Reference Bertoldi2006). This process converges after only 5–10 decodings. For each internal optimization, about 50 iterations are still required, but each iteration is much shorter since they only require to rescoring an n-best list. Most recent approaches propose to substitute the n-best lists to lattices (Macherey et al., Reference Macherey, Och, Thayer and Uszkoreit2008).

Figure 6

Double-loop optimization block diagram

9 Rescoring and system combination

This section reports an overview of the works, which have been developed in rescoring and system combination. Rescoring aims at integrating feature functions in the log-linear SMT framework, which cannot be easily incorporated into a dynamic programming search.

One straightforward solution to this problem is to use a SMT decoder that computes a list of n-best translations and then rescore the list with the feature functions that were not incorporated in decoding.

In Och et al. (Reference Och, Gildea, Khudanpur, Sarkar, Yamada, Fraser, Kumar, Shen, Smith, Eng, Jain, Jin and Radev2004), more than 450 different feature functions were used in order to improve the syntactic form of the MT output.

A widely known work is by Kumar and Byrne (Reference Kumar and Byrne2004), which presents the Minimum Bayes-Risk (MBR) approach in rescoring. It aims to minimize expected loss of translation errors under loss functions that measure translation performance. This algorithm was originally developed to work with n-best lists of translations, and recently has been extended to lattices and hypergraphs, which have the capacity of encoding many more hypotheses than typical n-best lists (Kumar et al., Reference Kumar, Macherey, Dyer and Och2009). DeNero et al. (Reference DeNero, Chiang and Knight2009) proposed a variant of the MBR procedure that applies efficiently to translation forests. These approaches can be interpreted as consensus decoding procedures because they choose a translation similar to other high posterior translations.

Later, some language modeling techniques have been used to rescore the n-best outputs. For example, clustered language models were implemented in Hasan and Ney (Reference Hasan and Ney2005). They reported a language model based on clusters obtained by applying regular expressions to the training data and thus discriminating several different sentence types, for example, interrogatives, imperatives or enumerations. The main motivation rested on the observation that different sentence types also have different syntactic structures, and thus yield a varying distribution of n-grams reflecting their word order. Also, techniques of neural language modeling (Schwenk et al., Reference Schwenk, Costa-jussà and Fonollosa2006) have been used for the purpose of rescoring. The basic idea of continuous space language models, also called neural network language models, is to project the word indices onto a continuous space and to use a probability estimator operating on this space. Since the resulting probability functions are smooth functions of the word representation, better generalization to unknown n-grams can be expected.

System combination in SMT has its inspiration from the fact that combining outputs from different systems was shown to be quite successful in automatic speech recognition (ASR). Voting schemes like the ROVER approach of Fiscus (Reference Fiscus1997) use edit distance alignment and time information to create confusion networks from the output of several ASR systems.

In MT, some approaches combine lattices or n-best lists from several different MT systems (Frederking & Nirenburg, Reference Frederking and Nirenburg1994). To be successful, such approaches require compatible lattices and comparable scores of the (word) hypotheses in the lattices.

The most straightforward approach simply selects, for each sentence, one of the provided hypotheses. The selection is made based on the scores of translation, language and other models (Nomoto, Reference Nomoto2004; Doi et al., Reference Doi, Hwang, Imamura, Okuma and Sumita2005).

Bangalore et al. (Reference Bangalore, Bordel and Riccardi2001) uses the edit distance alignment extended to multiple sequences to construct a confusion network from several translation hypotheses. This algorithm produces monotone alignments only, that is, allows insertion, deletion and substitution of words. Jayaraman and Lavie (Reference Jayaraman and Lavie2005) try to deal with translation hypotheses with significantly different word order. They introduce a method that allows non-monotone alignments of words in different translation hypotheses for the same sentence.

Confusion networks have been generated by choosing one hypothesis as the skeleton and other hypotheses are aligned against it. The skeleton defines the word order of the combination output. Previously mentioned MBR was used to choose the skeleton in Sim et al. (Reference Sim, Byrne, Gales, Sahbi and Woodland2007). The average translation edit rate (TER) score (Snover et al., Reference Snover, Dorr, Schwartz, Micciulla and Makhoul2006) was computed between each system's 1-best hypotheses in terms of TER. This work was extended by Rosti et al. (Reference Rosti, Ayan, Xiang, Schwartz Matsoukas and Dorr2007) by introducing system weights for word confidences.

More recently, experiments combining several kinds of MT systems have been presented in Matusov et al. (Reference Matusov, Leusch, Banchs, Bertoldi, Dechelotte, Federico, Kolss, Lee, Marino, Paulik, Roukos, Schwenk and Ney2008). They propose to use a consensus translation using an alignment procedure that explicitly models reordering of words in the hypotheses. In contrast to existing approaches, the context of the whole document, rather than a single sentence, is considered in this iterative, unsupervised procedure, yielding a more reliable alignment.

10 Domain adaptation

One of the main limitations of the phrase-based system is the out-domain generalization. This section reviews several techniques, which focus on solving this generalization challenge.

Training data for SMT is generally collected from wherever it is available. The application domain for a MT system has been investigated with and without in-domain available data. Initial adaptation efforts focused on adapting the target language model to the specific domain, such as it was done for speech recognition.

The main inconveniences of performing out-domain translations are the out-of-vocabulary words, the unknown expressions and the syntactic constructions. These challenges have mainly been addressed either by trying to incorporate source context information or, by trying to exploit different kinds of in-domain material to improve SMT. In-domain material can be mainly: parallel and/or monolingual. Additionally, works that focus on solving unknown vocabulary (Langlais & Patry, Reference Langlais and Patry2007) and adding morphological information (Nießen & Ney, Reference Nießen and Ney2001; Axelrod, Reference Axelrod2006; de Gispert & Marino, Reference de Gispert and Marino2008) are also dealing with out-domain challenges.

The exploitation of in-domain monolingual corpora have been mainly limited to the target language model (Eck et al., Reference Eck, Vogel and Waibel2004). Bulyko et al. (Reference Bulyko, Matsourkas, Schwartz, Nguyen and Makhoul2007) explored discriminative estimation of language model weights by directly optimizing MT performances. Wu et al. (Reference Wu, Wang and Zong2008) investigated linear and log-linear interpolation of in-domain and out-domain language models. In Schwenk and Estève (Reference Schwenk and Estève2008), the authors present a promising technique of target language models linear interpolation.

More recently, Bertoldi and Federico (Reference Bertoldi and Federico2009) have used the in-domain monolingual corpora to synthesize a bilingual corpus by translation of the monolingual adaptation data into the counterpart language. Translation, reordering and language models were estimated after translating in-domain texts with the baseline system.

To sum up, all the above works focus on introducing statistical techniques that can help to correctly translate in-domain expressions and vocabulary.

11 Source context information

The phrase-based translation model allows to introduce both source and target context information in comparison with the word-based translation model. However, the idea of introducing context information is simplified in the phrase-based systems given that all training sentences contribute equally to the final translation.

More complex works which introduce source context information can be found in the SMT literature. For example, Stroppa et al. (Reference Stroppa, van de Bosch and Way2007) and Haque et al. (Reference Haque, Kumar Naskar, Ma and Way2009) incorporate source language context using neighboring words, part-of-speech tags and/or supertags. They use a memory-based classification approach to obtain the probability for the given additional contexts with the source phrase. Works such as Carpuat and Wu (Reference Carpuat and Wu2007) are context-rich approaches from Word Sense Disambiguation methods. Other related works focus on extending the translation and target language model using neural networks (Schwenk et al., Reference Schwenk, Costa-jussa and Fonollosa2007), which aim at smoothing both the translation and target language model in order to use the n-grams more adequate in the translated sentence.

To sum up, all these works focus on introducing semantic context in a standard phrase-based system.

Exploding in-domain parallel corpora have been recently addressed in the scientific community by the annual WMT international evaluations (Callison-Burch et al., Reference Callison-Burch, Fordyce, Koehn, Monz and Schroeder2007, Reference Callison-Burch, Koehn, Monz and Schroeder2008, Reference Callison-Burch, Koehn, Monz and Schroeder2009).

The straightforward way to use in-domain parallel corpora is to simply concatenate the training corpora available and use the combined data for both translation model and language model training. However, in case the in-domain data is a much smaller set than the out-domain corpus, the gain expected through a simply concatenation is not much. The result can be even worse than using only the in-domain data when the in-domain data have a very particular style (Khalilov et al., Reference Khalilov, Costa-jussà, Henríquez, Fonollosa, Hernández, Mariño, Banchs, Chen, Zhang, Aw and Li2008).

Another proposal is to implement a TM interpolation strategy. Authors in Koehn and Schroeder (Reference Koehn and Schroeder2007) show that the linear interpolation of translation models achieve gains in translation quality. Alternatively, a log-linear interpolation also improves translation (Khalilov et al., Reference Khalilov, Costa-jussà, Henríquez, Fonollosa, Hernández, Mariño, Banchs, Chen, Zhang, Aw and Li2008).

The technique of mixture models is exploited in works such as Foster and Kuhn (Reference Foster and Kuhn2007), Civera and Juan (Reference Civera and Juan2007) and Finch and Sumita (Reference Finch and Sumita2008). Mixture modeling is a standard technique for density estimation that is capable of learning specific probability distributions that better fit subsets of the training data set.

In Rogati (Reference Rogati2009), the author adds in-domain corpora by automatically weighting and combining multiple translation resources, according to several criteria, in order to better match a target corpus or a specific domain sample. The criteria include lexical-level domain match, translation quality estimates, size and taxonomy representation.

12 Evaluation measures

Automatic and human evaluation has been widely investigated by the scientific community. This section reports an overview of the most widely used SMT evaluation measures.

Having an automatic evaluation is a must in order to optimize a MT system. Interesting and widely used automatic measures are referenced as follows:

• • Bilingual Evaluation Understudy (BLEU; Papineni et al., Reference Papineni, Roukos, Ward and Zhu2002) has dominated most MT work. Essentially, it consists of an n-gram corpus-level measure and it is always referred to as a given n-gram order (BLEU_n, n usually being 4).

• • NIST (Doddington, Reference Doddington2002) is an accuracy measure that calculates how informative a particular n-gram is, and the rarer a correct n-gram is, the more weight it will be given. Small variations in translation length do not impact much in the overall score.

• • Word Error Rate (WER; McCowan et al., Reference McCowan, Moore, Dines, Gatica-Perez, Flynn, Wellner and Bourlard2004) is a standard speech recognition evaluation metric. One general difficulty of measuring performance lies in the fact that the translated word sequence can have a different length from the reference word sequence (supposedly the correct one). The WER is derived from the Levenshtein distance, working at the word level. Additionally for translation, its multiple-reference version (mWER) is computed on a sentence-by-sentence basis, so that the final measure for a given corpus is based on the cumulative WER for each sentence. Similar to WER, there is the Position-Independent Error Rate (mPER), which is again computed on a sentence-by-sentence basis. The main difference with WER is that it does not penalize the wrong order in the translation.

• • Metric for Evaluation of Translation with Explicit ORdering (METEOR) evaluates a translation by computing a score based on explicit word-to-word matches between the translation and a reference translation. If more than one reference translation is available, the given translation is scored against each reference independently, and the best score is reported. It has been found (Lavie & Agarwal, Reference Lavie and Agarwal2007) that it correlates well with human adequacy.

• • From a more intuitive point of view, in Snover et al. (Reference Snover, Dorr, Schwartz, Makhoul, Micciula and Weischedel2005), Translation Error Rate or TER is presented. This measures the amount of editing that a human would have to perform to change a system output so it exactly matches a reference translation. Its application in real-life situation is reported in Przybocki et al. (Reference Przybocki, Sanders and Le2006).

Actually, there are many interesting automatic measures, for example, the ones which have been presented and evaluated in the Annual Workshop of Machine Translation (WMT)Footnote ⁶. Some measures include linguistic knowledge and do correlate with human criteria (Giménez & Màrquez, Reference Giménez and Màrquez2007; Popovic & Ney, Reference Popovic and Ney2009).

On the other hand, there are many schemas for human evaluation measures in MT. The most popular method is to obtain ratings from monolingual judges for segments of a document. Judges are presented with a segment, and are asked to rate it for two variables: adequacy and fluency. Adequacy is a rating of how much information is transferred between the original and the translation, and fluency is a rating of how good the English is. This technique is found to cover the relevant parts of the quality evaluation, while at the same time being easier to deploy, as it does not require expert judgment. Measuring systems based on adequacy and fluency, along with informativeness is now the standard methodology for the ARPA evaluation program.

Among the different challenges in human evaluation there are, in the first place, the consistency between the evaluator himself and the other evaluators. An evaluator normally evaluates from 1 to 5 in fluency and adequacy each. It is difficult to maintain consistency in the own evaluations and at the same time, it is even more difficult to keep pace with other evaluators. Generally, this challenge is overcome by calculating an average among the evaluators. And, in the second place, another challenge is to learn from evaluation. Evaluating different types of errors would allow to distinguish system which perform more or less the same.

Another trend is to manually post-edit the references with information from the test hypothesis translations, so that differences between translation and reference account only for errors and the final score is not influenced by the effects of synonymy. Actually, in the DARPA's Global Autonomous Language Exploitation (GALE) program (Olive, Reference Olive2005), one effective way to evaluate was asking evaluators to edit the translation by means of HTER (Human targeted Translation Edit Rate). In that sense, the less number of edits, the better the translation. Authors in Callison-Burch et al. (Reference Callison-Burch, Koehn, Monz and Schroeder2009) proposed to edit the translation output as fluent as possible, which reflects the annotators’ understanding of the sentence.

Other proposals regarding evaluation classification schemas can be found in the literature. Vilar et al. (Reference Vilar, Xu, Fernando-D'Haro and Ney2006), for instance, proposed a 5-category schema that does not use linguistic criteria. The classification presented in the current paper offers more linguistic information about the type of error; for example, Vilar et al. (Reference Vilar, Xu, Fernando-D'Haro and Ney2006) use the concept of incorrect words that can be related to multiple linguistic levels: lexical, semantic and morphological. On the other hand, Flanagan classification (Flanagan, Reference Flanagan1994) lists a series of errors that are pair language dependent. In the current paper, a similar list of subcategories for Catalan–Spanish is presented; however, these subcategories are included in a 5-category schema, which is language independent. Finally, Popovic (Reference Popovic2009) presented a framework for automatic error analysis and categorization. The basic idea is to actually identify erroneous words using algorithms for the calculation of WER and PER. The extracted error details can be used in combination with different types of natural language knowledge (such as base forms, POS tags and others). The work focuses on the five error categories from Vilar et al. (Reference Vilar, Xu, Fernando-D'Haro and Ney2006), and the new measures correlate well with the results of human analysis when using the same categorization. Finally, in Farrús et al. (Reference Farrús, Costa-jussà, Mariño and Fonollosa2010), they propose an evaluation method based on the assumption that all the errors can be classified into one of the following linguistic levels: orthographic, morphological, lexical, semantic and syntactic. Human evaluators use specific guidelines to classify and compute the number and type of errors encountered in the translations in order to analyze their linguistic quality.

13 Research directions

This paper overviewed the main phrase-based SMT research works: from the original approach (the Alignment Templates), to the nowadays SMT current research directions, which are mainly depicted in Sections 7–12. Actually, the principle SMT research objectives are to solve the following linguistic challenges:

• • Syntactic, which includes word ordering: SVO or VSO languages; location modifiers and nouns.

• • Morphological, which includes word correspondences: keeping number agreement among others.

• • Lexical, which includes out-of-vocabulary words. The main reasons for out of vocabulary words are the limitation of training data, domain changes and morphology.

The new strategy that tries to face the above challenges altogether is to combine the basic ideas of different SMT approaches: for example, hierarchical and phrase-based or Ngram-based SMT systems. Works such as Lopez (Reference Lopez2008) allow for introducing discontinuous phrases in a standard phrase-based system. Crego and Yvon (Reference Crego and Yvon2009) allows for a translation of discontiguous tuples that is the translation unit of an Ngram-based SMT system.

Research in SMT may develop SMT systems of better quality for professional translators. Research fields such as domain adaptation should be really helpful in the recent initiative of Interactive Machine Translation (IMT), where an SMT system aids the translator by interactively making suggestions for completing the translation. The IMT idea have been developed in the TransType and TransType2 European projects (Barrachina et al., Reference Barrachina, Bender, Casacuberta, Civera, Cubel, Khadivi, Lagarda, Ney, Toms and Vidal2009). Out of these projects, a recent online IMT (i.e. Caitra) system is now availableFootnote ⁷.