Training markov random field-based translation models using gradient ascent

Background

Various types of machine translation systems are commonly employed to translate text or speech from a source language to a target language. Examples of machine translation systems include rule-based machine translation systems, example-based machine translation systems, and statistical machine translation (SMT) systems. In contrast to approaches utilized for rule-based machine translation systems or example-based machine translation systems, SMT systems can generate translations based upon statistical translation models with parameters derived from analysis of bilingual text corpora.

A phrase translation model, also known as a phrase table, can be one of the models of a phrase-based SMT system. A phrase table is commonly constructed by implementing a two-phase approach. As part of such two-phase approach, bilingual phrase pairs can be extracted heuristically from automatically word-aligned training data. Thereafter, parameter estimation can be performed. Conventional parameter estimation techniques oftentimes include assigning each phrase pair a score estimated based on counting of words or phrases on the same word-aligned training data.

Summary

Described herein are various technologies that pertain to training and utilizing a general, statistical framework for modeling translation via Markov random fields (MRFs). An MRF-based translation model can be employed in a statistical machine translation (SMT) system. The MRF-based translation model allows for arbitrary features extracted from a phrase pair to be incorporated as evidence. For instance, one or more scores generated using the MRF-based translation model can be assigned to phrase pairs; such scores generated using the MRF-based translation model can be assigned in addition to scores estimated by other techniques (e.g., conventional counting based techniques, using disparate model(s), etc.). The parameters of the MRF-based translation model can be estimated using a large-scale discriminative training approach based on stochastic gradient ascent and an N-best list based expected Bilingual Evaluation Understudy (BLEU) as an objective function.

In accordance with various embodiments, the SMT system can receive an input string in a source language and can generate an output string in a target language based upon the input string. The SMT system can include an MRF-based phrase translation model. Further, the SMT system can evaluate scores of phrase translation pair hypotheses between the source language and the target language utilizing the MRF-based phrase translation model based upon a source phrase included in the input string in the source language. Moreover, the output string in the target language can be generated as a function of the scores of the phrase translation pair hypotheses.

Moreover, pursuant to various embodiments, the MRF-based phrase translation model can be trained for the SMT system. Respective N-best lists of translation hypotheses for source sentences in training data can be generated. Further, respective objective function scores for the translation hypotheses can be computed. Moreover, respective translation scores for the translation hypotheses can be computed using current parameters of the MRF-based phrase translation model for the SMT system. The parameters of the MRF-based phrase translation model can further be updated utilizing stochastic gradient ascent based on the objective function scores and the translation scores for the translation hypotheses.

According to various embodiments set forth herein, offline training of the MRF-based phrase translation model can be utilized. Pursuant to other embodiments, online adaptation of the MRF-based translation model can be employed.

The above summary presents a simplified summary in order to provide a basic understanding of some aspects of the systems and/or methods discussed herein. This summary is not an extensive overview of the systems and/or methods discussed herein. It is not intended to identify key/critical elements or to delineate the scope of such systems and/or methods. Its sole purpose is to present some concepts in a simplified form as a prelude to the more detailed description that is presented later.

Brief description of the drawings

FIG. 1 illustrates a functional block diagram of an exemplary system that translates an input string in a source language to an output string in a target language.

FIG. 2 illustrates an exemplary graph of a Markov random field model for phrase translation.

FIG. 3 illustrates a functional block diagram of an exemplary system that creates an MRF-based phrase translation model.

FIG. 4 illustrates a functional block diagram of an exemplary system that updates an MRF-based phrase translation model over time.

FIG. 5 is a flow diagram that illustrates an exemplary methodology of training an MRF-based phrase translation model.

FIG. 6 is a flow diagram that illustrates an exemplary methodology of training an MRF-based phrase translation model for an SMT system.

FIG. 7 is a flow diagram that illustrates an exemplary methodology of translating an input string in a source language to an output string in a target language.

FIG. 8 is a flow diagram that illustrates an exemplary methodology of translating an input string in a source language to an output string in a target language.

FIG. 9 illustrates an exemplary computing device.

Detailed description

Various technologies pertaining to training and utilizing Markov random field (MRF)-based translation models for statistic machine translation (SMT) systems are now described with reference to the drawings, wherein like reference numerals are used to refer to like elements throughout. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of one or more aspects. It may be evident, however, that such aspect(s) may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to facilitate describing one or more aspects. Further, it is to be understood that functionality that is described as being carried out by certain system components may be performed by multiple components. Similarly, for instance, a component may be configured to perform functionality that is described as being carried out by multiple components.

Moreover, the term “or” is intended to mean an inclusive “or” rather than an exclusive “or.” That is, unless specified otherwise, or clear from the context, the phrase “X employs A or B” is intended to mean any of the natural inclusive permutations. That is, the phrase “X employs A or B” is satisfied by any of the following instances: X employs A; X employs B; or X employs both A and B. In addition, the articles “a” and “an” as used in this application and the appended claims should generally be construed to mean “one or more” unless specified otherwise or clear from the context to be directed to a singular form.

A general, statistical framework for modeling translation via Markov random fields (MRFs) is set forth herein. An MRF-based translation model can be utilized in a statistical machine translation (SMT) system. According to various embodiments, the MRF-based translation model can be for modeling phrase translation pairs (e.g., an MRF-based phrase translation model). While many of the examples set forth herein pertain to the MRF-based translation model being for modeling phrase translation pairs, it is contemplated that such examples can be extended to MRF-based translation models for other types of translation systems in addition to or instead of phrase translation systems (e.g., hierarchical phrase based translation systems, syntax-based translation systems, etc.).

The MRF-based phrase translation model allows for arbitrary features extracted from a phrase pair to be incorporated as evidence. The parameters of the model are estimated using a large-scale discriminative training approach based on stochastic gradient ascent and an N-best list based expected Bilingual Evaluation Understudy (BLEU) as an objective function. The model can be incorporated into a standard phrase-based SMT system with minimal or no change to code of a runtime engine of such SMT system. For instance, one or more scores generated using the MRF-based phrase translation model can be assigned to phrase pairs; such scores generated using the MRF-based phrase translation model can be assigned in addition to scores estimated by other techniques (e.g., conventional counting based techniques, using disparate model(s), etc.). Incorporation of the MRF-based phrase translation model into an SMT system can enhance performance of the SMT system (e.g., a gain of 0.8-1.3 BLEU points can be obtained as compared to conventional phrase based SMT systems).

Referring now to the drawings, FIG. 1 illustrates a system 100 that translates an input string 102 in a source language to an output string 104 in a target language. The system 100 includes a statistical machine translation (SMT) system 106 that receives the input string 102 in the source language and generates the output string 104 in the target language. It is contemplated that the source language and the target language differ from each other, but can be substantially any languages (e.g., the source language can be French and the target language can be English, etc.). Further, the input string 102 in the source language can be text, speech, and so forth. Similarly, the output string 104 in the target language can be text, speech, etc.

The SMT system 106 includes a Markov random field (MRF)-based phrase translation model 108 . The MRF-based phrase translation model 108 can be used to score phrase translation pairs between the source language and the target language. For instance, the MRF-based phrase translation model 108 can be a phrase table. The MRF-based phrase translation model 108 can be employed to measure semantic similarity between phrases in the source language and the target language, for example. Further, it is to be appreciated that other types of MRF-based translation model(s) (e.g., other than the MRF-based phrase translation model 108 ) can additionally or alternatively fall within the scope of the hereto appended claims.

Moreover, the SMT system 106 can include substantially any number of disparate model(s) 110 . Examples of the disparate model(s) 110 include one or more of a phrase translation model, a word translation model, a lexicalized reordering model, a word count model, a phrase count model, an n-gram language model, or the like. However, it is contemplated that the SMT system 106 need not include the disparate model(s) 110 .

According to various embodiments, it is contemplated that the SMT system 106 can be a phrase-based SMT system. In accordance with such embodiments, the SMT system 106 can translate sequences of words (referred to as phrases), where the lengths of the phrases can differ. The phrases analyzed by the SMT system 106 can be phrasemes found using statistical methods from corpora as opposed to linguistic phrases. Many of the following examples pertain to the SMT system 106 being a phrase-based SMT system. Yet, in accordance with other embodiments, the SMT system 106 can be a disparate type of translation system such as, for instance, a hierarchical phrase based translation system, a syntax-based translation systems, or the like; accordingly, it is to be appreciated that the examples set forth herein can be extended to the SMT system 106 being a disparate type of translation system other than a phrase-based SMT system.

The SMT system 106 further includes a decoder component 112 . The decoder component 112 can evaluate scores of phrase translation pair hypotheses between the source language and the target language utilizing the MRF-based phrase translation model 108 based upon a source phrase included in the input string 102 in the source language. Thus, the decoder component 112 can generate the output string 104 in the target language as a function of the scores of the phrase translation pair hypotheses. For example, the decoder component 112 can generate the output string 104 in the target language as a sum of scores of phrase translation pair hypotheses of source phrases that form the input string 102 in the source language. Following this example, a source-target string pair (e.g., input string 102 —output string 104 pair) can include a list of source-target phrase pairs (e.g., a list of phrase translation pair hypotheses). The decoder component 112 can compute a translation score of a source-target string pair as a sum of the scores of the list of source-target phrase pairs that form the input string 102 . Further, the decoder component 112 can use the MRF-based phrase translation model 108 to score the source-target phrase pairs.

According to an example where the SMT system 106 includes at least one disparate model 110 , the decoder component 112 can generate the output string 104 in the target language utilizing the at least one disparate model (in addition to using the MRF-based phrase translation model 108 ). Pursuant to this example, the decoder component 112 can use a weighted log-linear combination of the MRF-based phrase translation model 108 and the at least one disparate model 110 .

Moreover, the SMT system 106 can include a feature extraction component 114 that can extract features of the phrase translation pair hypotheses for the source phrase included in the input string 102 in the source language. The phrase translation pair hypotheses for the source phrase can include the source phrase included in the input string 102 in the source language and candidate target phrases in the target language. Accordingly, the decoder component 112 can evaluate the scores of the phrase translation pair hypotheses between the source language and the target language utilizing the MRF-based phrase translation model 108 based upon the features of the phrase translation pair hypotheses for the source phrase included in the input string 102 in the source language. According to various embodiments, the features of the phrase translation pair hypotheses for the source phrase can include phrase-pair features. According to other embodiments, the features of the phrase translation pair hypotheses for the source phrase can include word-pair features. Pursuant to other embodiments, the features of the phrase translation pair hypotheses for the source phrase can include phrase-pair features and word-pair features. In accordance with yet other embodiments, the features of the phrase translation pair hypotheses for the source phrase can include phrase-pair features, word-pair features, and triplet features. Such features are described below in greater detail.

The MRF-based phrase translation model 108 can provide a general, statistical framework for modeling phrase translations, where different features can be incorporated in a unified manner. Moreover, as presented in greater detail herein, parameters of the MRF-based phrase translation model 108 can be learned effectively using a large-scale discriminative training approach which is based on stochastic gradient ascent and an N-best list based expected BLEU as the objective function. While various exemplary features modeled by the MRF-based phrase translation model 108 are described herein, it is to be appreciated that disparate features that capture other translation dependencies are intended to fall within the scope of the hereto appended claims.

The translation from the input string 102 in the source language to the output string 104 in the target language performed by the SMT system 106 can be represented as a noisy-channel model. The noisy-channel model can be formulated as:

E * = argmax E ⁢ P ⁡ ( E | F ) = argmax E ⁢ P ⁡ ( E ) ⁢ P ⁡ ( F | E ) ( 1 ) In the foregoing, F is a source sentence and E is a target translation. The noisy-channel model can be formulated as identifying a particular translation E* from among possible translations E, given the source sentence F. The Bayes rule can enable inverting the conditioning of translation probability from the source sentence F to the target translation E.

The SMT system 106 (e.g., the decoder component 112 ) can use a weighted log-linear combination of several models h(F,E,A), namely, the MRF-based phrase translation model 108 and the disparate model(s) 110 ). Thus, the SMT system 106 can use the logarithm of the phrase probability (and the lexical weight) in source-to-target and target-to-source directions. The weighted log-linear combination of the MRF-based phrase translation model 108 and the disparate model(s) 110 is represented as:

E * = ⁢ argmax E ⁢ .Math. m = 1 M ⁢ λ m ⁢ h m ⁡ ( F , E , A ) = ⁢ argmax E ⁢ Score λ ⁡ ( F , E ) ( 2 ) As provided in Equation 2, A in h(F,E,A) is a hidden structure that best derives E from F, called the Viterbi derivation herein. In phrase-based SMT, A includes

the segmentation of the source sentence into phrases,

the segmentation of the target sentence into phrases, and

an alignment between the source and target phrases. Moreover, M is the number of models (e.g., the MRF-based phrase translation model 108 and the disparate model(s) 110 ) used by the SMT system 106 , m is an index for the models, and λ.sub.m is a respective weight for each of the models. For instance, the weights can correspond to reliability of the models. Accordingly, the MRF-based phrase translation model 108 described herein can be integrated into the weighted log-linear combination of models used by the SMT system 106 .

MRFs, also known as undirected graphical models, are often used in modeling joint distributions of spatial or contextual dependencies of physical phenomena. As provided herein, MRFs can be used to model a joint distribution P.sub.w(f,e) over a source-target translation phrase pair (f,e), parameterized by w. The MRF-based phrase translation model 108 is different from directional translation models that are based on conditional probabilities. The MRF model P.sub.w(f,e) can be utilized in the log-linear framework noted above since agreement or compatibility of a phrase pair can enhance score translation quality more than a directional translation probability which is modeled based on an imaged generative story.

A Markov random field is constructed from a graph G. Nodes of the graph represent random variables, and edges define independence semantics between the random variables. An MRF satisfies the Markov property, which states that a node is independent of all of its non-neighbors, defined by clique configurations of G. In modeling a phrase translation pair, two types of nodes can be defined:

phrase nodes and

word nodes. More particularly, the graph G can include two phrase nodes and a set of word nodes, each for a word in the two phrases.

FIG. 2 depicts an exemplary graph 200 (e.g., a graph G). A phrase node 202 represents a target phrase (e.g., in the target language) and a phrase node 204 represents a source phrase (e.g., in the source language). In the example depicted in FIG. 2 , the target phrase includes two words and the source phrase includes three words. Accordingly, the graph 200 includes a word node 206 and a word node 208 that respectively represent the two words of the target phrase. Moreover, the graph 200 includes a word node 210 , a word node 212 , and a word node 214 that respectively represent the three words of the source phrase.

Moreover, the joint distribution over the random variables in G can be defined as:

P w ⁡ ( f , e ) = 1 Z ⁢ .Math. c ∈ C ⁡ ( G ) ⁢ φ ⁡ ( c ; w ) ( 3 ) where e=e.sub.1, . . . , e.sub.|e|, f=f.sub.1, . . . , f.sub.|f|, and C(G) is a set of cliques in G. Further, each φ(c; w) is a non-negative potential function defined over a clique configuration c that measures a compatibility of the configuration, and w is a set of parameters that are used within the potential function. Z in Equation (3), which can be referred to as a partition function, is a normalization constant and is given by:

Z = ⁢ .Math. f ⁢ .Math. e ⁢ .Math. c ∈ C ⁡ ( G ) ⁢ φ ⁡ ( c ; w ) = ⁢ .Math. f ⁢ .Math. e ⁢ Score ⁡ ( f , e ) ( 4 ) Z can normalize the distribution P.sub.w(f,e) given by Equation (3). However, it may not be feasible to compute Z due to the exponential number of terms in the summation. Yet, Z is a global constant which is independent of e and f. Therefore, when ranking phrase translation pair hypotheses, as performed by the decoder component 112 in the SMT system 106 of FIG. 1 , Z can be dropped; thus, each phrase translation pair hypothesis can be ranked by its unnormalized joint probability (e.g., by the decoder component 112 ). Accordingly, an unnormalized probability (e.g., Score(f,e) as defined in Equation (4)) can be stored in a phrase table for each translation pair (f,e).

It is common to define MRF potential functions of the exponential form as φ(c; w)=exp(w.sub.cϕ(c)), where ϕ(c) is a real-valued feature function over clique c and w.sub.c is the weight of the feature function. In phrase-based SMT systems, the sentence-level translation probability from F to E is decomposed as the product of a set of phrase translation probabilities. Dropping the phrase segmentation and distortion model components leads to the following, where A is the Viterbi derivation:

P ⁡ ( E | F ) ≈ max A ⁢ P ⁡ ( E | A , F ) ⁢ ⁢ P ⁡ ( E | A , F ) = .Math. ( f , e ) ∈ A ⁢ P ⁡ ( e | f ) ( 5 )

Similarly, the joint probability P(F|E) can be decomposed as:

P ⁡ ( F , E ) ≈ max A ⁢ P ⁡ ( F , A , E ) ( 6 ) P ⁡ ( F , A , E ) = ⁢ .Math. ( f , e ) ∈ A ⁢ P w ⁡ ( f , e ) ∝ ⁢ .Math. ( f , e ) ∈ A ⁢ log ⁢ ⁢ P w ⁡ ( f , e ) = ⁢ .Math. ( f , e ) ∈ A ⁢ ⁢ .Math. c ∈ G f , e ⁡ ( c ) ⁢ w c ⁢ ϕ ⁡ ( c ) = ⁢ .Math. ( f , e ) ∈ A ⁢ w .Math. ϕ ⁡ ( f , e ) which can essentially be proportional to a weighted linear combination of a set of features.

To instantiate an MRF model, a graph structure representing the translation dependencies between source and target phrases, and a set of potential functions over the cliques of this graph can be defined.

As noted above, the exemplary graph 200 (e.g., the graph G) of FIG. 2 includes two types of nodes: phrase nodes 202 - 204 and word nodes 206 - 214 . The MRF-based phrase translation model 108 described herein can be constructed from the graph 200 . The graph 200 includes two phrase nodes 202 - 204 for the source and target phrases respectively and word nodes 206 - 214 , each for a word in these phrases. Cliques and their corresponding potential functions (or features) attempt to abstract the idea behind translation models that can be effective for machine translation. In particular, three types of cliques can be formed from the graph G (e.g., the graph 200 ).

A first type of clique includes two phrase nodes. Thus, from the graph 200 , a clique that includes the phrase node 202 and the phrase node 204 can be formed. A potential function over such a clique captures phrase-to-phrase translation dependencies similar to the use the bi-directional translation models in phrase-based SMT systems. The potential is defined as φ.sub.p(f,e)=w.sub.pϕ.sub.p(f,e), where the feature ϕ.sub.p(f,e), called the phrase-pair feature, is an indicator function whose value is 1 if e is target phrase and f is source phrase, and 0 otherwise. While the conditional probabilities in a directional translation model is estimated using relative frequencies of phrase pairs extracted from word-aligned parallel sentences, the parameter of the phrase-pair function w.sub.p can be learned discriminatively as described in greater detail below.

A second type of clique includes two word nodes, one in the source phrase and the other in the target phrase. An example of such a clique formed from the graph 200 includes the word node 206 and the word node 210 . A potential over such a clique captures word-to-word translation dependencies similar to the use the IBM Model 1 for lexical weighting in phrase-based SMT systems. The potential function is defined as φ.sub.t(f,e)=w.sub.tϕ.sub.t(f,e), where the feature ϕ.sub.t(f,e), called the word-pair feature, is an indicator function whose value is 1 if e is a word in target phrase e and f is a word in source phrase f, and 0 otherwise.

A third type of cliques includes three word nodes, with two of the word nodes being in one language and the third word node being in the other language. An example of such a clique formed from the graph 200 includes the word node 206 , the word node 210 , and the word node 212 . A potential over such a clique is intended to capture inter-word dependencies for selecting word translations. The potential function can be based on the triplet lexicon model which is based on lexicalized triplets (e,f,f′). It can be understood as two source (or target) words triggering one target (or source) word. The potential function is defined as φ.sub.tp(f,f′,e)=w.sub.tpϕ.sub.tp(f,f′,e), where the feature ϕ.sub.tp(f,f′,e), called the triplet feature, is an indicator function whose value is 1 if e is a word in target phrase e and f and f′ are two different words in source phrase f, and 0 otherwise.

Moreover, for any clique c that includes nodes in only one language, it can be assumed that φ(c)=1 for such clique, which typically has no impact on scoring a phrase pair. According to an example, a potential over cliques including a phrase node and word nodes in target language can be defined, which can act as a form of a target language model. By way of another example, edges can be added in the graph so as to define potentials that capture more sophisticated translation dependencies. The optimal potential set can vary among different language pairs and depend upon an amount and quality of training data.

Turning to FIG. 3 , illustrated is a system 300 that creates the MRF-based phrase translation model 108 . The system 300 includes a training component 302 that trains the MRF-based phrase translation model 108 based upon training data 304 . The training component 302 can learn parameters of the MRF-based phrase translation model 108 from the training data 304 using a large-scale discriminative training algorithm based on stochastic gradient ascent and an objective function for parameter optimization.

Similar to techniques for constructing conventional phrase tables, the training component 302 can construct the MRF-based phrase translation model 108 by heuristically extracting bilingual phrase pairs from automatically word-aligned training data (e.g., the training data 304 ). Thereafter, the training component 302 can perform parameter estimation. Yet, techniques for parameter estimation described herein differ from conventional approaches.

Moreover, instead of parameterizing a phrase translation pair using a set of scoring functions that are learned independently (e.g., phrase translation probabilities and lexical weights), the training component 302 can use a general, statistical framework in which arbitrary features extracted from a phrase pair can be incorporated to model the translation in a unified way. Utilization of the MRF-based phrase translation model 108 can provide such general, statistical framework.

Further, because the MRF-based phrase translation model 108 has to work with other component models (e.g., the disparate model(s) 110 ) in the SMT system 106 in order to produce translations, and the quality of translation is measured via BLEU score, it is desirable to optimize the parameters of the MRF-based phrase translation model 108 jointly with the other component models with respect to an objective function that is closely related to the evaluation metric under consideration (e.g., BLEU). To this end, a large-scale discriminative training approach can be implemented by the training component 302 . While techniques such as Minimum Error Rate Training (MERT) can be used for tuning a small number of features on a small training set, discriminative training methods as provided herein can support training for a greater number of features for a greater number of sentence pairs. More particularly, the training component 302 can use stochastic gradient ascent and an N-best list based expected BLEU as the objective function for large-scale discriminative training.

Moreover, training of the MRF-based phrase translation model 108 can be adopted for various SMT systems, and the learning techniques can provide results that are reproducible. The features for the MRF-based phrase translation model 108 can be developed in such a way that the resulting model is of the same or similar format as that of a traditional phrase table. Thus, the MRF-based phrase translation model 108 can be incorporated into a standard phrase-based SMT system, requiring minimal or no code change in the runtime engine. Yet, it is to be appreciated that other formats are intended to fall within the scope of the hereto appended claims.

Estimation of the parameters of the MRF-based phrase translation model 108 by the training component 302 is now described. It is to be appreciated, however, that parameters other than those described below can additionally or alternatively be estimated by the training component 302 .

Although MRFs are by nature generative models, it may be inappropriate to train the parameters using conventional likelihood based approaches for various reasons. For instance, it may be difficult to compute the partition function in Equation (4), especially depending upon scale. Further, use of conventional likelihood based approaches can be inappropriate due to the metric divergence problem. That is, the maximum likelihood estimation is unlikely to be optimal for the evaluation metric under consideration, as demonstrated on a variety of tasks including machine translation and information retrieval. Therefore, a large-scale discriminative training approach that uses stochastic gradient ascent and an N-best list based expected BLEU as the objective function can instead be utilized by the training component 302 .

Machine translation can be cast as a structured classification task. It maps an input source sentence F to an output pair (E,A) where E is the output target sentence and A the Viterbi derivation of E. A is assumed to be constructed during the translation process. In phrase-based SMT, A includes a segmentation of the source and target sentences into phrases and an alignment between source and target phrases.

It can be assumed that translations are modeled using a linear model parameterized by a vector θ. Given a vector h(F,E,A) of feature functions on (F,E,A), and assuming θ contains a component for each feature, the output pair (E,A) for a given input F are selected using the argmax decision rule:

( E * , A * ) = argmax ( E , A ) ⁢ θ T ⁢ h ⁡ ( F , E , A ) ( 7 ) In phrase-based SMT, computing the argmax exactly is intractable, so it is performed approximately by beam decoding.

In a phrase-based SMT system (e.g., the SMT system 106 ) equipped by a MRF-based phrase translation model (e.g., the MRF-based phrase translation model 108 ), the parameters to be learned by the training component 302 are θ=(λ,w), where λ is a vector of parameters (e.g., on the order of ones or tens of parameters) used in the log-linear model of Equation (2), with one weight for each component model (e.g., a respective weight for each of the MRF-based phrase translation model 108 and the disparate model(s) 110 ); and w is a vector including weights (e.g., on the order of millions of weights), each for one feature function in the MRF model of Equation (3).

The training component 302 can include a candidate identification component 306 , a label component 308 , a score evaluation component 308 , and an optimization component 312 for learning θ (e.g., employing three steps). More particularly, given a baseline phrase-based SMT system (e.g., the SMT system 106 of FIG. 1 ) and a pre-set λ, the candidate identification component 306 can generate an N-best list of translation hypotheses for each source sentence in the training data 304 . Thereafter, with λ fixed, the optimization component 312 can optimize w with respect to an objective function on the training data 304 . Then, with w fixed, the optimization component 312 can optimize λ using MERT to maximize the BLEU score on development data.

The candidate identification component 306 can generate respective N-best lists of translation hypotheses for the source sentences in the training data 304 . Given a set of source-target sentence pairs as training data (F.sub.n,E.sub.n.sup.r), n=1 . . . N, a baseline phrase-based SMT system (e.g., the SMT system 106 with the disparate model(s) 110 and/or a previously trained MRF-based phrase translation model) can be used by the candidate identification component 306 to generate a list of N-best output pairs (e.g., 100-best output pairs) for each source sentence F according to Equation (7).

Moreover, the label component 308 can compute objective function scores for the translation hypotheses. The label component 308 can label the translation hypotheses with the respective objective function scores. Thus, the label component 308 can label each output pair (E,A) by a sentence-level BLEU score, denoted by sBLEU, which is computed according to Equation (8):

s ⁢ ⁢ BLEU ⁡ ( E , E r ) = BP × 1 4 ⁢ .Math. n = 1 4 ⁢ log ⁢ ⁢ p n ( 8 ) In the foregoing, E.sup.r is the reference translation (e.g., human provided translation, translation considered to be true, etc.), and p.sub.n, n=1 . . . 4 are precisions of n-grams. While precisions of lower order n-grams (e.g., p.sub.1 and p.sub.2) are computed by the label component 308 directly without smoothing, matching counts for higher order n-grams can be sparse at the sentence level and can thus be smoothed by the label component 308 as:

p n = # ⁢ ( matched ⁢ ⁢ ngram ) + α ⁢ ⁢ p n 0 # ⁢ ( ngram ) + α , for ⁢ ⁢ n = 3 , 4 In the above, α is a smoothing parameter (e.g., set to 5), and p.sub.n.sup.0 is the prior value of p.sub.n, whose value is computed as p.sub.n.sup.0=(p.sub.n-1).sup.2/p.sub.n-2 for n=3 and 4. BP in Equation

is the sentence-level brevity penalty, computed as

0 BP = exp ⁡ ( 1 - β ⁢ ⁢ r c ) , which differs from its corpus-level counterpart in two ways. First, a non-clipped BP can be used, which can provide an enhanced approximation to the corpus-level BLEU computation because the per-sentence BP may effectively exceed unity in corpus-level BLEU computation. Second, the ratio between the length of reference sentence r and the length of translation hypothesis c is scaled by a factor β such that the total length of the references on training data equals that of the 1-best translation hypotheses produced by the baseline SMT system.

Utilization of sBLEU defined above can provide a small but consistent improvement over other variations of sentence-level BLEU. The use of the scaling factor β in computing BP can enhance BP of the baseline's 1-best output on the training data 304 , and can provide an effect of forcing the discriminative training to improve BLEU by improving n-gram precisions rather than by improving brevity penalty.

Moreover, the score evaluation component 310 can compute respective translation scores for the translation hypotheses using current parameters of the MRF-based phrase translation model 108 . Further, the optimization component 312 can update the parameters of the MRF-based phrase translation model 108 utilizing stochastic gradient ascent based on the objective function scores and the translation scores for the translation hypotheses.

The optimization component 312 can use an N-best list based expected BLEU as the objective function for parameter optimization. Given the current model θ, the expected BLEU, denoted by xBLEU(θ), over one training sample (e.g., a labeled N-best list generated from a pair of source and target sentences (F,E.sup.r)), can be defined as:

x ⁢ ⁢ BLEU ⁡ ( θ ) = .Math. E ⁢ P θ ⁡ ( E | F ) ⁢ sBLEU ⁡ ( E , E r ) ( 9 ) where sBLEU is the sentence-level BLEU, defined in Equation (8). Moreover, P.sub.θ(E|F) is a normalized translation probability from F to E computed by the score evaluation component 310 using softmax as:

P θ ⁡ ( E | F ) = exp ⁡ ( Score θ ⁡ ( F , E ) ) .Math. E ′ ⁢ exp ⁡ ( Score θ ⁡ ( F , E ′ ) ) ( 10 ) where Score.sub.θ(.) is the translation score according to the current model θ:

Score θ ⁡ ( F , E ) = λ .Math. h ⁡ ( F , E , A ) + .Math. ( f , e ) ∈ A ⁢ w .Math. ϕ ⁡ ( f , e ) ( 11 ) The right hand side of Equation

includes two terms. The first term is the score produced by the baseline system, which is fixed during phrase model training. The second term is the translation score produced by the MRF model, which is updated after each training sample during training Comparing Equations

and (11), the MRF model can be viewed as yet another component model under the log linear model framework with its λ being set to 1.

Given the objective function, the parameters of the MRF model are optimized by the optimization component 312 using stochastic gradient ascent. The following algorithm, for instance, can be employed by the training component 302 to train the MRF-based phrase translation model 108 . 1) Initialize w, assuming λ is fixed during training. 2) For t=1 . . . T (T=the total number of iterations) 3) For each training sample (labeled 100-best list) 4) Compute P.sub.θ(E|F) for each translation hypothesis E based on the current model θ=(λ,w) 5) Update the model via w.sup.new=w.sup.old+η.Math.g(w.sup.old), where η is the learning rate and g is the gradient computed according to Equations 12 and 13 below.

Accordingly, as shown above, T iterations can be performed on the training set, where each time is considered an epoch. For each training sample, the model parameters can be updated as: w .sup.new =w .sup.old +η.Math.g ( w .sup.old)

where η is the learning rate. The gradient g is computed as:

g ⁡ ( w ) = ⁢ ∂ x ⁢ ⁢ BLEU ⁡ ( w ) ∂ w = ⁢ .Math. ( E , A ) ⁢ ( s ⁢ ⁢ BLEU ⁡ ( E , E r ) - x ⁢ ⁢ BLEU ⁡ ( θ ) ) ⁢ P θ ⁡ ( E | F ) ⁢ ϕ ⁡ ( F , E , A ) ( 13 )

The foregoing algorithm can be employed to simplify the training procedure without scarifying much quality of the trained model. For instance, a regularization term is not included in the objective function; rather, early stopping and cross valuation can be implemented. According to an example, it is contemplated that an MRF model can be produced after each epoch, and quality on a development set can be tested by first combining the MRF model with other baseline component models via MERT and then examining BLEU score on the development set. By way of illustration, training for T epochs (T=100) can be performed and then the model with the best BLEU score on the development set can be selected; yet, the claimed subject matter is not limited to the foregoing example. Moreover, it is contemplated that the leave-one-out method to generate the N-best lists need not be employed. Instead, the models used in the baseline SMT system can be trained on the same parallel data on which the N-best lists are generated.

Many of the examples set forth herein describe an offline training algorithm. Yet, it is contemplated that the techniques set forth herein can be applicable to other scenarios, such as online adaptation (e.g., as described in FIG. 4 ).

FIG. 4 illustrates a system 400 that updates the MRF-based phrase translation model 108 over time. The system 400 includes the SMT system 106 , which can further include the MRF-based phrase translation model 108 , the disparate model(s) 110 , the decoder component 112 , and the feature extraction component 114 . Moreover, the system 400 includes the training component 302 ; although not show, it is contemplated that the training component 302 can include the candidate identification component 306 , the label component 308 , the score evaluation component 310 , and the optimization component 312 .

The description continues in the full USPTO document.