Machine translation techniques

• US 20020040292A1
• Filed: 05/11/2001
• Published: 04/04/2002
• Est. Priority Date: 05/11/2000
• Status: Active Grant

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Marcu, Daniel
• Granted Patent: US 7,533,013 B2
• Time in Patent Office: Days
• US Class Current: 704/4
• 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 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 said applying, said determining and said setting until occurrence of a 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 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 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 current target language translation, the inserted other word having a high probability of having a zero-value fertility.

7. The method of claim 1 wherein applying one or more modification operators comprises deleting from the 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 current target language translation by swapping non-overlapping target language word segments in the 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 current target language translation by (i) eliminating a target language word from the 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 current target language translation the translation of one or two words;

(ii) changing in the 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 current target language translation, the inserted other word having a high probability of having a zero-value fertility;

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

(iv) modifying 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) modifying 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.

11. The method of claim 1 wherein determining whether one or more of the modified target language translations represents an improved translation in comparison with the current target language translation comprises calculating a probability of correctness for each of the 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 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.

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.

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 module for determining a probability of correctness for a translation 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.

35. The method of claim 34 wherein the one or more decision rules comprise a sequence of decision rules.

36. The method of claim 34 wherein the one or more decision rules collectively represent a transfer function.

37. The method of claim 34 further comprising automatically determining the one or more decision rules based on a training set.

38. The method of claim 37 wherein the training set comprises a plurality of input-output tree pairs and a mapping between each of the input-output tree pairs.

39. The method of claim 38 wherein the mapping between each of the input-output tree pairs comprises a mapping between leaves of the input tree and leaves of the paired output tree.

40. The method of claim 39 wherein mappings between leaves of input-output tree pairs can be one-to-one, one-to-many, many-to-one, or many-to-many.

41. The method of claim 38 wherein automatically determining the one or more decision rules comprises determining a sequence of operations that generates an output tree when applied to the paired input tree.

42. The method of claim 41 wherein determining a sequence of operations comprises using a plurality of predefined operations that collectively are sufficient to render any input tree into the input tree'"'"'s paired output tree.

43. The method of claim 42 wherein the plurality of predefined operations comprise one or more of the following:

a shift operation that transfers an elementary discourse tree (edt) from an input list into a stack;

a reduce operation that pops two edts from a top of the stack, combines the two popped edts into a new tree, and pushes the new tree on the top of the stack;

a break operation that breaks an edt into a predetermined number of units;

a create-next operation that creates a target language discourse constituent that has no correspondent in the source language tree;

a fuse operation that fuses an edt at the top of the stack into the preceding edt;

a swap operation that swaps positions of edts in the input list; and

an assignType operation that assigns one or more of the following types to edts;

Unit, MultiUnit, Sentence, Paragraph, MultiParagraph, and Text.

44. The method of claim 43 wherein the plurality of predefined operations comprises a closed set including the shift operation, the reduce operation, the break operation, the create-next operation, the fuse operation, the swap operation and the assignType operation.

45. The method of claim 41 wherein determining a sequence of operations results in a plurality of learning cases, one learning case for each input-output tree pair.

46. The method of claim 45 further comprising associating one or more features with each of the plurality of learning cases based on context.

47. The method of claim 46 wherein the associated features comprise one or more of the following:

operational and discourse features, correspondence-based features, and lexical features.

48. The method of claim 45 further comprising applying a learning program to the plurality of learning cases to generate the one or more decision rules.

49. The method of claim 48 wherein the learning program comprises C4.5.

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

51. The method of claim 34 wherein the target language text segment comprises a clause, a sentence, a paragraph, or a treatise.

52. The method of claim 34 wherein the source language text segment and the target language text segment are different types of text segments.

53. The method of claim 34 wherein each of the source language tree and the target language tree comprises a syntactic tree.

54. The method of claim 34 wherein each of the source language tree and the target language tree comprises a discourse tree.

15. A computer-implemented machine translation decoding method comprising iteratively modifying a target language translation of a source language text segment until an occurrence of a termination condition.

27. A machine translation decoder comprising:

a decoding engine comprising one or more modification operators to be applied to a current target language translation to generate one or more modified target language translations; and

a process loop to iteratively modify the current target language translation using the one or more modification operators, the process loop terminating upon occurrence of a termination condition.

34. A computer-implemented tree generation method comprising:

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.

55. A computer-implemented tree generation module comprising a predetermined set of decision rules that when applied to a tree corresponding to a source language text segment generate a tree corresponding to a target language text segment.

56. The module of claim 55 wherein the source language text segment comprises a clause, a sentence, a paragraph, or a treatise.

57. The module of claim 55 wherein the target language text segment comprises a clause, a sentence, a paragraph, or a treatise.

58. The module of claim 55 wherein the source language text segment and the target language text segment are different types of text segments.

59. The module of claim 55 wherein each of the source language tree and the target language tree comprises a syntactic tree.

60. The module of claim 55 wherein each of the source language tree and the target language tree comprises a discourse tree.

61. The module of claim 55 wherein the predetermined set of decision rules defines a transfer function between source language trees and target language trees.

62. A method of determining a transfer function between trees of different types, the method comprising:

generating a training set comprising a plurality of tree pairs and a mapping between each tree pair, each tree pair comprises a source tree and a corresponding target tree;

generating a plurality of learning cases by determining, for each tree pair, a sequence of operations that result in the target tree when applied to the source tree; and

generating a plurality of decision rules by applying a learning algorithm to the plurality of learning cases.

63. The method of claim 62 further comprising, prior to generating the plurality of decision rules, associating one or more features with each of the learning cases based on context.

64. A computer-implemented discourse-based machine translation system comprising:

a discourse parser that parses the discourse structure of a source language text segment and generates a source language discourse tree for the text segment;

a discourse-structure transfer module that accepts the source language discourse tree as input and generates as output a target language discourse tree; and

a mapping module that maps the target language discourse tree into a target text segment.

65. The system of claim 64 wherein the discourse-structure transfer module comprises a plurality of decision rules generated from a training set of source language-target language tree pairs.