Modification of annotated bilingual segment pairs in syntax-based machine translation

• US 8,825,466 B1
• Filed: 06/08/2007
• Issued: 09/02/2014
• Est. Priority Date: 06/08/2007
• Status: Active Grant

• Current Assignee: Language Weaver, Inc. (RWS Holdings Plc), University of Southern California
• Original Assignee: Language Weaver, Inc. (RWS Holdings Plc), University of Southern California
• Inventors: May, Jonathan, Knight, Kevin, Wang, Wei
• Primary Examiner(s): Dorvil, Richemond
• Assistant Examiner(s): ADESANYA, OLUJIMI A
• Application Number:
  US11/811,228
• Time in Patent Office: 2,643 Days
• Field of Search: 704/2, 704 4- 5, 704/9, 704/240, 704/251
• US Class Current: 704/2
• CPC Class Codes: G06F 40/45 Example-based machine translation; Alignment

Abstract

Systems and methods for automatically modifying an annotated bilingual segment pair are provided. An annotated bilingual segment pair (“Pair”) may be modified to generate improved translation rules used in machine translation of documents from a source language to a target language. Because a single Pair may be used to translate a phrase, many Pairs are used in a machine translation system and manual correction of each model is impractical. Each Pair may be modified by re-labeling syntactic categories within the Pair, re-structuring a tree within the Pair, and/or re-aligning source words to target words within the Pair. In exemplary embodiments, many alternate Pairs (or portions thereof) are generated automatically, rule sequences corresponding to each are derived, and one or more rule sequences are selected. Using the selected rule sequence, a modified Pair is distilled.

Claims

1. A method for generating a tree to string annotated bilingual segment pair, the method comprising:

receiving a first annotated bilingual segment pair comprising two or more words in a source language, two or more words in a target language, and an alignment between the two or more words in the source language and the two or more words in the target language;

processing, by a computer, the first annotated bilingual segment pair to generate a target forest including a plurality of trees, each tree representing an alternative annotated bilingual segment pair including an alignment rule sequence that can be used to express a relationship between the words in the bilingual segment pair, the processing of the first annotated bilingual segment pair by the computer including re-labeling, re-structuring, and re-aligning the first annotated bilingual segment pair;

building a derivation forest from the target forest, the derivation forest including a plurality of trees;

deriving, by the computer, a plurality of rule sequences for the plurality of trees in the derivation forest, each tree in the derivation forest including a set of rule sequences derived from a tree in the target forest;

selecting one of the derived rule sequences based on a probability that the selected rule sequence is more likely than the other derived rule sequences, using an expectation-maximization algorithm;

generating, by the computer, a second annotated bilingual segment pair based on the selected rule sequence, wherein the second annotated bilingual segment pair has an alignment; and

extracting translation rules from the second annotated bilingual segment pair based on the alignment of the second annotated bilingual segment pair.

2. The method recited in claim 1, wherein processing the first annotated bilingual segment pair comprises re-structuring a first tree in the first annotated bilingual segment pair or re-aligning the first annotated bilingual segment pair.

3. The method recited in claim 1, wherein re-labeling syntactic structures comprises combining two or more of the syntactic structures.

4. The method recited in claim 1, wherein processing the first annotated bilingual segment pair further comprises:

re-structuring a first tree in the first annotated bilingual segment pair to generate the plurality of the trees.

5. The method recited in claim 4, wherein re-structuring the first tree comprises adding a new parent node to include a subset of existing nodes.

6. The method recited in claim 1, wherein processing the first annotated bilingual segment pair further comprises:

extracting translation rules from the first annotated bilingual segment pair based on the alignment, wherein the plurality of the trees includes the translation rules.

7. The method recited in claim 1, further comprising:

training a translation engine using the second annotated bilingual segment pair.

8. The method recited in claim 1, wherein selecting one of the rule sequences comprises summing weights associated with at least a portion of the plurality of the trees.

9. The method recited in claim 1, wherein the first annotated bilingual segment pair and the second annotated bilingual segment pair both comprise a tree-to-string annotated bilingual segment pair.

10. The method recited in claim 1, wherein the first annotated bilingual segment pair and the second annotated bilingual segment pair both comprise a tree-to-tree annotated bilingual segment pair.

11. The method recited in claim 1, wherein the first annotated bilingual segment pair and the second annotated bilingual segment pair both comprise a string-to-tree annotated bilingual segment pair.

12. A system for generating a tree to string annotated bilingual segment pair, the system comprising:

a processor configured to;

receive a first annotated bilingual segment pair to generate a plurality of trees, the first annotated bilingual segment pair comprising two or more words in a source language, two or more words in a target language, and an initial alignment between the two or more words in the source language and the two or more words in the target language, and

process the first annotated bilingual segment pair, the processing including;

re-labeling, restructuring, and re-aligning the first annotated bilingual segment pair, to generate

a plurality of target trees, each tree representing an alternative annotated bilingual segment pair including an alignment rule sequence that can be used to express a relationship between the words in the bilingual segment pair;

a derivation module configured to derive a plurality of derivation trees from the plurality of the target trees, each derivation tree including a rule sequence derived from a target tree;

a training module configured to select one of the derived rule sequences, based on a probability that the selected rule sequence is more likely than the other derived rule sequences, using an expectation-maximization algorithm; and

a distillation module configured to generate a second annotated bilingual segment pair based on the selected rule sequence, and produce translation rules from the second annotated bilingual segment pair.

13. The system recited in claim 12, wherein the processor is further configured to re-structure a first tree in the first annotated bilingual segment pair or re-align the first annotated bilingual segment pair.

14. The system recited in claim 12, wherein the processor is further configured to re-structure a first tree in the first annotated bilingual segment pair.

15. The system recited in claim 12, wherein the processor is further configured to extract translation rules from the first annotated bilingual segment pair based on the alignment.

16. The system recited in claim 12, wherein the first annotated bilingual segment pair and the second annotated bilingual segment pair both comprise a tree-to-string annotated bilingual segment pair.

17. A non-transitory computer readable storage medium having embodied thereon a program, the program being executable by a processor for performing a method for generating an annotated bilingual segment pair, the method comprising:

receiving a first annotated bilingual segment pair comprising a source string including two or more words in a source language, a target phrase represented as a first tree that includes two or more words in a target language, and an alignment between the source string and the first tree;

processing the first annotated bilingual segment pair, the processing of the first annotated bilingual pair including;

re-labeling one or more nodes of a tree representing the first annotated bilingual segment pair,

re-structuring the tree representing the annotated bilingual segment pair, including adding parent nodes to the tree,

re-aligning the first annotated bilingual segment pair, and

generating a target forest including a plurality of target trees based on the re-labeling, re-structuring, and re-aligning;

building a derivation forest of a plurality of derivation trees based on the target forest, each derivation tree representing a rule sequence that corresponds to target tree;

deriving a plurality of rule sequences from the plurality of the derivation trees;

calculating a probability using an expectation-maximization algorithm that the derived rule sequence is correct for each of the derived rule sequences;

selecting the rule sequences having the highest probability;

generating a second annotated bilingual segment pair based on the selected rule sequence, wherein the second annotated bilingual segment pair has an alignment; and

extracting translation rules from the second annotated bilingual segment pair based on the alignment of the second annotated bilingual segment pair.

18. The non-transitory computer readable storage medium recited in claim 17, wherein processing the first annotated bilingual segment pair comprises re-structuring the first tree in the first annotated bilingual segment pair or re-aligning the first annotated bilingual segment pair.

19. The non-transitory computer readable storage medium recited in claim 17, wherein re-labeling syntactic structures comprises combining two or more of the syntactic structures.

20. The non-transitory computer readable storage medium recited in claim 17, wherein processing the first annotated bilingual segment pair further comprises:

re-structuring the first tree in the first annotated bilingual segment pair to generate the plurality of the trees.

21. The non-transitory computer readable storage medium recited in claim 20, wherein re-structuring the first tree comprises adding a new parent node to include a subset of existing nodes.

22. The non-transitory computer readable storage medium recited in claim 17, wherein processing the first annotated bilingual segment pair further comprises:

extracting translation rules from the first annotated bilingual segment pair based on the alignment, wherein the plurality of the trees includes the translation rules.

23. The non-transitory computer readable storage medium recited in claim 17, wherein the method further comprises:

training a translation engine using the second annotated bilingual segment pair.

24. The non-transitory computer readable storage medium recited in claim 17, wherein selecting one or more of the rule sequences comprises summing weights associated with at least a portion of the plurality of the derivation trees.

25. The non-transitory computer readable storage medium recited in claim 17, wherein the first annotated bilingual segment pair and the second annotated bilingual segment pair both comprise a tree-to-string annotated bilingual segment pair.

26. The non-transitory computer readable storage medium recited in claim 17, wherein the first annotated bilingual segment pair and the second annotated bilingual segment pair both comprise a tree-to-tree annotated bilingual segment pair.

27. The non-transitory computer readable storage medium recited in claim 17, wherein the first annotated bilingual segment pair and the second annotated bilingual segment pair both comprise a string-to-tree annotated bilingual segment pair.