Machine translation techniques

• US 7,533,013 B2
• Filed: 05/11/2001
• Issued: 05/12/2009
• Est. Priority Date: 05/11/2000
• Status: Expired due to Term

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Marcu, Daniel
• Primary Examiner(s): Edouard; Patrick N
• Assistant Examiner(s): Spooner; Lamont M
• Application Number:
  US09/854,327
• Publication Number:
  US 20020040292A1
• Time in Patent Office: 2,923 Days
• Field of Search: 704 2- 8, 715/264
• US Class Current: 704/2
• CPC Class Codes: G06F 16/345 Summarisation for human users
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06F 40/35 Discourse or dialogue representation
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models

Abstract

Machine translation decoding is accomplished by receiving as input a text segment in a source language to be translated into a target language, generating an initial translation as a current target language translation, applying one or more modification operators to the current target language translation to generate one or more modified target language translations, determining whether one or more of the modified target language translations represents an improved translation in comparison with the current target language translation, setting a modified target language translation as the current target language translation, and repeating these steps until occurrence of a termination condition. Automatically generating a tree (e.g., either a syntactic tree or a discourse tree) can be accomplished by receiving as input a tree corresponding to a source language text segment, and applying one or more decision rules to the received input to generate a tree corresponding to a target language text segment.

Claims

1. A machine translation decoding method comprising:

receiving as input a text segment in a source language to be translated into a target language;

generating an initial translation as an initial current target language translation;

estimating a probability of correctness of the initial translation, the probability based on alignment links between words and phrases in the source language and words and phrases in the target language;

applying one or more modification operators to the initial current target language translation by a computer to generate one or more modified target language translations;

estimating a probability of correctness of the one or more modified target language translations, the probability based on alignment links between words and phrases in the source language and words and phrases in the target language;

determining by the computer whether one or more of the modified target language translations represents an improved translation in comparison with the initial current target language translation by comparing the estimated probability of correctness of the initial translation with the estimated probability of correctness of the one or more modified target language translations;

setting by the computer a modified target language translation with a higher probability based on the comparison as the modified current target language translation; and

repeating said applying, said determining and said setting for the modified current target language translation until occurrence of a termination condition and

outputting the modified current target language translation by the computer in response to the occurrence of the termination condition.

2. The method of claim 1 wherein the text segment comprises a clause, a sentence, a paragraph or a treatise.

3. The method of claim 1 wherein generating an initial translation comprises generating a gloss.

4. The method of claim 3 wherein the gloss is a word-for-word gloss or a phrase-for-phrase gloss.

5. The method of claim 1 wherein applying one or more modification operators comprises changing in the initial current target language translation the translation of one or two words.

6. The method of claim 1 wherein applying one or more modification operators comprises (i) changing in the initial current target language translation a translation of a word and concurrently (ii) inserting another word at a position that yields an alignment of highest probability between the source language text segment and the initial current target language translation, the inserted other word having a substantial probability of having a zero-value fertility.

7. The method of claim 1 wherein applying one or more modification operators comprises deleting from the initial current target language translation a word having a zero-value fertility.

8. The method of claim 1 wherein applying one or more modification operators comprises modifying an alignment between the source language text segment and the initial current target language translation by swapping non-overlapping target language word segments in the initial current target language translation.

9. The method of claim 1 wherein applying one or more modification operators comprises modifying an alignment between the source language text segment and the initial current target language translation by (i) eliminating a target language word from the initial current target language translation and (ii) linking words in the source language text segment.

10. The method of claim 1 wherein applying one or more modification operators comprises applying two or more of the following:

(i)

changing in the initial current target language translation the translation of one or two words;

(ii) changing in the initial current target language translation a translation of a word and concurrently inserting another word at a position that yields an alignment of highest probability between the source language text segment and the initial current target language translation, the inserted other word having a high probability of having a zero-value fertility;

(iii) deleting from the initial current target language translation a word having a zero-value fertility;

(iv) modifying an alignment between the source language text segment and the initial current target language translation by swapping non-overlapping target language word segments in the initial current target language translation; and

(v) modifying an alignment between the source language text segment and the initial current target language translation by eliminating a target language word from the initial current target language translation and linking words in the source language text segment.

11. The method of claim 1 wherein estimating a probability of correctness of the one or more modified target language translations comprises calculating a probability of correctness for each of the one or more modified target language translations.

12. The method of claim 1 wherein the termination condition comprises a determination that a probability of correctness of a modified target language translation is no greater than a probability of correctness of the initial current target language translation.

13. The method of claim 1 wherein the termination condition comprises a completion of a predetermined number of iterations.

14. The method of claim 1 wherein the termination condition comprises a lapse of a predetermined amount of time.

15. A computer-implemented machine translation decoding method comprising:

receiving as input a text segment in a source language to be translated into a target language;

generating an initial translation by the computer as an initial current target language translation;

estimating a probability of correctness of the initial translation by the computer, the probability based on alignment links between words and phrases in the source language and words and phrases in the target language;

applying one or more modification operators by the computer to the initial current target language translation to generate one or more modified target language translations;

estimating a probability of correctness of the one or more modified target language translations, the probability based on alignment links between words and phrases in the source language and words and phrases in the target language;

determining by the computer whether one or more of the modified target language translations represents an improved translation in comparison with the initial current target language translation by comparing the estimated probability of correctness of the initial translation with the estimated probability of correctness of the one or more modified target language translations;

iteratively modifying the current target language translation of the source language text segment based on the determination; and

repeating said applying, said determining and said iteratively modifying until occurrence of a termination condition.

16. The method of claim 15 wherein the termination condition comprises a determination that a probability of correctness of a modified translation is no greater than a probability of correctness of a previous translation.

17. The method of claim 15 wherein the termination condition comprises a completion of a predetermined number of iterations.

18. The method of claim 15 wherein the source language text segment comprises a clause, a sentence, a paragraph, or a treatise.

19. The method of claim 15 wherein the method starts with an approximate target language translation and iteratively improves the translation with each successive iteration.

20. The method of claim 19 wherein the approximate target language translation comprises a gloss.

21. The method of claim 20 wherein the gloss comprises a word-for-word gloss or a phrase-for-phrase gloss.

22. The method of claim 19 wherein the approximate target language translation comprises a predetermined translation selected from among a plurality of predetermined translations.

23. The method of claim 15 wherein the method implements a greedy algorithm.

24. The method of claim 15 wherein iteratively modifying the translation comprises incrementally improving the translation with each iteration.

25. The method of claim 15 wherein iteratively modifying the translation comprises performing at each iteration one or more modification operations on the translation.

26. The method of claim 25 wherein the one or more modification operations comprises one or more of the following operations:

(i) changing one or two words in the translation;

(ii) changing a translation of a word and concurrently inserting another word at a position that yields an alignment of highest probability between the source language text segment and the translation, the inserted other word having a high probability of having a zero-value fertility;

(iii) deleting from the translation a word having a zero-value fertility;

(iv) modifying an alignment between the source language text segment and the translation by swapping non-overlapping target language word segments in the translation; and

(v) modifying an alignment between the source language text segment and the translation by eliminating a target language word from the translation and linking words in the source language text segment.

27. A machine translation decoder comprising:

a memory, the memory containing program instructions configured to be executed by a processor;

a processor able to access and execute the program instructed stored in the memory;

a decoding engine, configured to receive as input a text segment in a source language to be translated into a target language and to generate an initial translation as a current target language translation, comprising one or more modification operators to be applied to a current target language translation to generate one or more modified target language translations;

a probability module in communication with the decoding engine configured to estimate a probability of correctness of the initial translation, the probability based on alignment links between words and phrases in the source language and words and phrases in the target language, to estimate a probability of correctness of the one or more modified target language translations, the probability based on alignment links between words and phrases in the source language and words and phrases in the target language, and to determine whether one or more of the modified target language translations represents an improved translation in comparison with the initial current target language translation by comparing the estimated probability of correctness of the initial translation with the estimated probability of correctness of the one or more modified target language translations; and

a process loop configured to iteratively modify the current target language translation of a source language text based on the probability module estimate of the probability of correctness of the one or more modified target language translations and the probability module determination regarding whether one or more of the modified target language translations represent an improved translation, the process loop terminating upon occurrence of a termination condition.

28. The decoder of claim 27 wherein the process loop controls the decoding engine to incrementally improve the current target language translation with each iteration.

29. The decoder of claim 27 further comprising a module for determining a probability of correctness for a translation.

30. The decoder of claim 29 wherein the probability module for determining a probability of correctness comprises a language model and a translation module.

31. The decoder of claim 29 wherein the process loop terminates upon a determination that a probability of correctness of a modified translation is no greater than a probability of correctness of a previous translation.

32. The method of claim 27 wherein the process loop terminates upon completion of a predetermined number of iterations.

33. The decoder of claim 27 wherein the one or more modification operators comprise one or more of the following:

(i) an operator to change in the current target language translation the translation of one or two words;

(ii) an operator to change in the current target language translation a translation of a word and to concurrently insert another word at a position that yields an alignment of highest probability between the source language text segment and the current target language translation, the inserted other word having a high probability of having a zero-value fertility;

(iii) an operator to delete from the current target language translation a word having a zero-value fertility;

(iv) an operator to modify an alignment between the source language text segment and the current target language translation by swapping non-overlapping target language word segments in the current target language translation; and

(v) an operator to modify an alignment between the source language text segment and the current target language translation by eliminating a target language word from the current target language translation and linking words in the source language text segment.