Phrase to phrase joint probability model for statistical machine translation

• US 7,454,326 B2
• Filed: 03/27/2003
• Issued: 11/18/2008
• Est. Priority Date: 03/27/2002
• Status: Active Grant

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Marcu, Daniel, Koehn, Philipp, Knight, Kevin, Wong, William
• Primary Examiner(s): Dorvil; Richemond
• Assistant Examiner(s): Siedler; Dorothy S
• Application Number:
  US10/402,350
• Publication Number:
  US 20040030551A1
• Time in Patent Office: 2,063 Days
• Field of Search: 704/10, 704/2
• 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

Abstract

A machine translation (MT) system may utilize a phrase-based joint probability model. The model may be used to generate source and target language sentences simultaneously. In an embodiment, the model may learn phrase-to-phrase alignments from word-to-word alignments generated by a word-to-word statistical MT system. The system may utilize the joint probability model for both source-to-target and target-to-source translation applications.

Claims

1. A method comprising:

receiving a phrase {right arrow over (e)}_i in a first language; and

generating a joint probability model from a parallel corpus, the generating based on at least one generated pair of phrases ({right arrow over (e)}_i, {right arrow over (f)}_i) wherein {right arrow over (e)}_i comprises a first number of words and {right arrow over (f)}_i comprises a second number of words, the first number being different from the second number.

2. The method of claim 1, further comprising:

generating a phrase-to-phrase probabilistic dictionary from the joint probability model and the parallel corpus.

3. The method of claim 1, wherein said generating the joint probability model comprises:

stochastically generating a bag of concepts C;

for each c_i ^ε

C, generating the pair of phrases ({right arrow over (e)}_i, {right arrow over (f)}_i) according to the distribution t({right arrow over (e)}_i, {right arrow over (f)}_i); and

ordering the phrases generated in each language so as to create two linear sequences of phrases.

4. The method of claims 3, further comprising training the model, the training comprising:

determining high-frequency n-grams in E and F;

initializing a t-distribution table with alignments;

performing Viterbi based EM training for a plurality of iterations; and

deriving a joint probability model and a conditional probability model.

5. The method of claim 1, wherein generating the joint probability model comprises:

(1) stochastically generating a bag of concepts C;

(2) initializing E and F to empty sentences ^ε

;

(3) randomly removing a concept c_i ^ε

C and generating the pair of phrases ({right arrow over (e)}_i {right arrow over (f)}_i) according to the distribution t({right arrow over (e)}_i, {right arrow over (f)}_i);

(4) appending the phrase {right arrow over (f)}_i to the end of F;

(5) inserting phrase {right arrow over (e)}_i, at position l in E provided that no other phrase occupies any of the positions between l and l+|{right arrow over (e)}_i|, where |{right arrow over (e)}_i| gives the length of the phrase {right arrow over (e)}_i; and

repeating steps (3) to (5) until C is empty.

6. The method of claims 5, further comprising training the model, the training comprising:

determining high-frequency n-grams in E and F;

initializing a t-distribution table with alignments;

performing Viterbi based EM training for a plurality of iterations; and

deriving a joint probability model and a conditional probability model.

7. The method of claim 1, further comprising:

determining a translation for an input sentence comprising the phrase {right arrow over (e)}_i using a greedy decoding operation.

8. The method of claim 1, further comprising:

determining a translation for an input sentence comprising the phrase {right arrow over (e)}_i using a beam search algorithm.

24. The method of claim 1, wherein the first number of words or the second number of words is one.

9. A method comprising:

generating a phrase-to-phrase probabilistic dictionary from a parallel corpus using word-for-word alignments in the parallel corpus and a phrase-based model generated from the parallel corpus, the generating based on a generated pair of phrases ({right arrow over (e)}_i, {right arrow over (f)}_i wherein {right arrow over (e)}_i comprises a first number of words and {right arrow over (f)}_i comprises a second number of words, the first number being different from the second number.

10. The method of claim 9, further comprising determining a best output sentence in a second language for an input sentence in the first language, the determining comprising:

segmenting the input sentence into a sequence of phrases;

translating each of the phrases into a phrase in the second language; and

reordering the output phrases.

11. The method of claim 10, wherein the reordering comprises using a relative distortion probability distribution.

12. The method of claim 9, wherein the generating comprises:

performing a word-to-word alignment on both sides of the parallel corpus to produce a plurality of word alignments; and

collecting a plurality of aligned phrase pairs that are consistent with word alignments in said plurality of word alignments.

13. The method of claim 12, further comprising:

estimating a phrase translation probability distribution of the collected phrase pairs based on relative frequencies.

14. The method of claim 13, further comprising:

parsing both sides of the word-aligned parallel corpus with a syntactic parser to generate syntactic parse trees; and

for each of the collected phrase pairs, checking if both phrases associated with the collected phrase pair is associated with a subtree in the syntactic parse trees.

15. The method of claim 13, further comprising:

identifying a collected aligned phrase pair of the collected phrase pairs, the collected phrase pair associated with a plurality of alignments; and

calculating a lexical weight for each of the plurality of alignments.

16. The method of claim 9, wherein the generating comprises:

performing bidirectional word-to-word alignment operations on the parallel corpus to generate two sets of word alignments.

17. The method of claim 16 further comprising:

identifying alignment points at intersections between the two sets of word alignments.

18. The method of claim 16, further comprising:

identifying alignment points at a union of the two sets of word alignments.

25. The method of claim 9, wherein the first number of words or the second number of words is one.

19. A method comprising:

(1) receiving an input string including a plurality of words in a first language;

from an initial hypothesis in a second language, (2) selecting a sequence from said plurality of words in the input string, (3) selecting a possible phrase translation in the second language for said selected sequence, (4) attaching the possible phrase translation to the current hypothesis to produce an updated hypothesis, (5) marking the words in said selected sequence as translated, (6) storing the hypothesis sequence in a stack, and (7) updating a probability cost of the updated hypothesis;

(8) repeating steps (2) to (7) based on a size of the stack to produce one or more possible translations for the input string; and

(9) selecting one of said possible translations in the stack having a highest probability.

20. The method of claim 19, wherein the initial hypothesis is empty.

21. The method of claim 19, wherein the each of the possible translations comprises a hypothesis leaving no corresponding untranslated words in the input string.

22. The method of claim 19, wherein updating the probability cost comprises calculating a current cost for the updated hypothesis and estimating a future cost for the updated hypothesis.

23. The method of claim 19, further comprising:

discarding the updated hypothesis if the updated hypothesis has a higher cost than n-best updated hypotheses in the stack, where n corresponds to a predetermined beam size.