MACHINE TRANSLATION USING OVERLAPPING BIPHRASE ALIGNMENTS AND SAMPLING

• US 20120101804A1
• Filed: 10/25/2010
• Published: 04/26/2012
• Est. Priority Date: 10/25/2010
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Dymetman, Marc, Cancedda, Nicola, Roth, Benjamin, McCallum, Andrew R.
• Granted Patent: US 8,775,155 B2
• Time in Patent Office: Days
• US Class Current: 704/2
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models
• CPC Class Codes: G06F 40/45 Example-based machine translation; Alignment
• CPC Class Codes: G06F 40/51 Translation evaluation

Abstract

A system and method for machine translation are disclosed. Source sentences are received. For each source sentence, a target sentence comprising target words is generated. A plurality of translation neighbors of the target sentence is generated. Phrase alignments are computed between the source sentence and the translation neighbor. Translation neighbors are scored with a translation scoring model, based on the phrase alignment. Translation neighbors are ranked, based on the scores. In training the model, parameters of the model are updated based on an external ranking of the ranked translation neighbors. The generating of translation neighbors, scoring, ranking, and, in the case of training, updating the parameters, are iterated with one of the translation neighbors as the target sentence. In the case of decoding, one of the translation neighbors is output as a translation. The system and method may be at least partially implemented with a computer processor.

Claims

1. A method for training a translation scoring model for a statistical machine translation system, comprising:

receiving a set of source sentences, each of the source sentences comprising source words in a source language;

for each source sentence, generating a target sentence comprising target words in a target language which are translations of the source words;

generating a plurality of translation neighbors based on the target sentence, each translation neighbor comprising at least some of the target words of the target sentence;

for each of the plurality of translation neighbors, computing a phrase alignment between the source sentence and the translation neighbor;

scoring each translation neighbor with a translation scoring model, based on the computed phrase alignment between the source sentence and the translation neighbor;

ranking a plurality of the translation neighbors based on the translation model scores;

updating parameters of the model based on a comparison of the ranking based on the translation model scores with an external ranking of the plurality of translation neighbors; and

iterating, at least once more, the generating of translation neighbors, scoring, ranking, and updating parameters, wherein in the generating of the plurality of translation neighbors of the target sentence, the target sentence is a translation neighbor from a prior iteration.

2. The method of claim 1, wherein at least one of the generating of translation neighbors, scoring, ranking, and updating parameters is performed with a computer processor.

3. The method of claim 1, wherein the generating of translation neighbors comprises applying a set of operators to the target sentence, each of the operators generating at least one translation neighbor.

4. The method of claim 3, wherein the set of operators includes at least one of:

a remove operator which removes at least one target word from the target sentence;

an insert operator which inserts a word in the target sentence when a sequence of n words in the target sentence is not found in a language model;

a replace operator which replaces at least one of the target words in the target sentence with target words of a biphrase which matches at least one of the source words in the source sentence; and

a shift operator which shifts a position of a target word to at least one different position in the target sentence.

5. The method of claim 1, wherein the computing of the phrase alignment between the source sentence and the translation neighbor comprises identifying a set of biphrases which cover, at best, all source words of the source sentence and all target words of the translation neighbor, each biphrase in the set including a sequence of the source words and a sequence of the target words.

6. The method of claim 5, wherein in the phrase alignment, each source word and each target word is covered by no more than one of the biphrases except in the case of consistent overlapping biphrases which cover both a same target word and a same source word.

7. The method of claim 1, wherein the parameters are feature weights and wherein translation scoring model outputs a score for a translation neighbor which is a function of the expression exp(Σ

_kΘ

_kφ

_k(s,t)), where each φ

_k(s,t) represents a feature function and Θ

represents a vector of the feature weights indexed by k.

8. The method of claim 7, wherein at least one of the feature functions is based on the computed alignment.

9. The method of claim 1, wherein the external ranking of the plurality of translation neighbors comprises computing an objective function for each of the plurality of translation neighbors using a training corpus of sentence pairs, each sentence pair comprising a first sentence in the source language and a second sentence in the target language.

10. The method of claim 1, wherein the external ranking comprises computing the Bleu score for each of the plurality of translation neighbors.

11. The method of claim 1, wherein in the iteration, the target sentence is selected probabilistically from a set of the translation neighbors from the prior iteration where each of the translation neighbors in the set has a probability of being selected which is a function of its score assigned by the translation model.

12. A system for performing the method of claim 1 comprising memory which stores instructions for performing the method and a processor in communication with the memory which executes the instructions.

13. A computer program product comprising non-transitory media encoding instructions which when executed by a computer, perform the method of claim 1.

14. A method for machine translation comprising:

with a translation scoring model trained by the method of claim 1, translating text comprising at least one source sentence in the source language.

15. The method of claim 14, wherein the translation of the text comprises:

for each of the at least one source sentence, generating a target sentence comprising target words in a target language which are translations of the source words;

generating a plurality of translation neighbors of the target sentence, each translation neighbor comprising at least some of the target words of the target sentence;

for each of the plurality of translation neighbors, computing a phrase alignment between the source sentence and the translation neighbor;

scoring each translation neighbor with a translation scoring model, based on the computed phrase alignment between the source sentence and the translation neighbor;

ranking a plurality of the translation neighbors based on the translation model scores;

iterating, at least once more, the generating of translation neighbors, scoring, and ranking, wherein in the generating of the plurality of translation neighbors of the target sentence, the target sentence is a translation neighbor from a prior iteration; and

outputting a translation neighbor as a translation of the source sentence based on the ranking.

16. The method of claim 15, wherein at each iteration the target sentence is probabilistically selected from translation neighbor from prior iterations by annealing the scores of the translation neighbors according to a formula in which the score is taken to an exponent which is increased with each iteration.

22. A computer program product comprising non-transitory media encoding instructions which when executed by a computer, perform the method of claim 1.

17. A machine translation system comprising

memory for storing a set of source sentences, each of the source sentences comprising source words in a source language;

memory storing instructions for;

for each source sentence, generating a target sentence comprising target words in a target language which are translations of the source words;

generating a plurality of translation neighbors of the target sentence, each translation neighbor comprising at least some of the target words of the target sentence;

for each of the plurality of translation neighbors, computing a phrase alignment between the source sentence and the translation neighbor;

scoring each translation neighbor with a translation scoring model, based on the computed phrase alignment between the source sentence and the translation neighbor;

ranking a plurality of the translation neighbors based on the translation model scores;

if the source sentences are being used for training the model, updating parameters of the model based on a comparison of the translation model score-based ranking with an external ranking of the plurality of translation neighbors;

iterating, at least once more, the generating of translation neighbors, scoring, ranking, and, in the case of training, updating the parameters, wherein in the generating of the plurality of translation neighbors of the target sentence, the target sentence is a translation neighbor from a prior iteration; and

if the source sentence is received for decoding, outputting a translation neighbor as a translation of the source sentence;

if the source sentence is received for training, storing the trained model generated in one of the iterations in memory; and

a processor in communication with the memory for executing the instructions.

18. The system of claim 17, further comprising a biphrase table stored in memory accessible to the processor from which biphrases are drawn for computing the phrase alignment and generating the target sentence.

19. A method for machine translation comprising:

receiving text to be translated comprising at least one source sentence each of the source sentences comprising source words in a source language;

for each of the at least one source sentence, generating a target sentence comprising target words in a target language which are translations of the source words;

generating a plurality of translation neighbors of the target sentence, each translation neighbor comprising at least some of the target words of the target sentence;

for each of the plurality of translation neighbors, computing a phrase alignment between the source sentence and the translation neighbor;

scoring each translation neighbor with a translation scoring model, based on the computed phrase alignment between the source sentence and the translation neighbor;

ranking a plurality of the translation neighbors based on the translation model scores;

iterating, at least once more, the generating of translation neighbors, scoring, and ranking, wherein in the generating of the plurality of translation neighbors of the target sentence, the target sentence is a translation neighbor from a prior iteration; and

outputting one of the translation neighbors as a translation of the source sentence based on the ranking.

20. The method of claim 19, wherein at least one of the generating of translation neighbors, scoring, ranking, and outputting is performed with a computer processor.

21. The method of claim 19, wherein the computing of the phrase alignment between the source sentence and the translation neighbor comprises identifying a set of biphrases which cover, at best, all source words of the source sentence and all target words of the translation neighbor, each biphrase in the set including a sequence of the source words and a sequence of the target words, and wherein in the phrase alignment, each source word and each target word is covered by no more than one of the biphrases except in the case of consistent overlapping biphrases which cover both a same target word and a same source word.

23. A machine translation system comprising

memory for storing a set of source sentences, each of the source sentences comprising source words in a source language;

memory storing instructions for;

for each source sentence, generating a target sentence comprising target words in a target language which are translations of the source words;

in a first iteration, generating a plurality of translation neighbors of the target sentence, each translation neighbor comprising at least some of the target words of the target sentence;

for each of the plurality of translation neighbors, computing a phrase alignment between the source sentence and the translation neighbor;

scoring each translation neighbor with a translation scoring model, based on the computed phrase alignment between the source sentence and the translation neighbor;

ranking a plurality of the translation neighbors based on the translation model scores;

if the source sentences are being used for training the model, updating parameters of the model based on a comparison of the translation model score-based ranking with an external ranking of the plurality of translation neighbors;

iterating, at least once, the generating of translation neighbors, scoring, ranking, and, in the case of training, updating the parameters, wherein in the generating of the plurality of translation neighbors of the target sentence, the target sentence is a translation neighbor from a prior iteration; and

if the source sentence is received for decoding, outputting a translation neighbor as a translation of the source sentence;

if the source sentence is received for training, storing the trained model generated in one of the iterations in memory; and

a processor in communication with the memory for executing the instructions.