Integer programming decoder for machine translation

• US 20020188438A1
• Filed: 05/31/2002
• Published: 12/12/2002
• Est. Priority Date: 05/31/2001
• Status: Active Grant

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Yamada, Kenji, Knight, Kevin
• Granted Patent: US 7,177,792 B2
• Time in Patent Office: Days
• US Class Current: 704/2
• CPC Class Codes: G06F 40/42 Data-driven translation
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models

Abstract

A machine translation (MT) decoder may transform a translation problem into an integer programming problem, such as a Traveling Salesman Problem (TSP). The decoder may invoke an integer program (IP) solver to solve the integer programming problem and output a likely decoding based on the solution.

Claims

1. A method comprising:

transforming a translation problem into an integer programming problem; and

generating a translation in response to solving the integer programming problem.

2. The method of claim 1, wherein said generating a translation comprises generating a text segment in a target language corresponding to a translation of a text segment in a source language.

3. The method of claim 1, wherein said transforming comprises generating a graph comprising a plurality of regions, each region including one or more nodes.

4. The method of claim 3, further comprising:

inputting a text segment including words in a source language,

wherein each of said plurality of regions represents a corresponding one of the words in the source language, and

wherein the one or more nodes in each of said plurality of regions represent possible translations of the word corresponding to said region.

5. The method of claim 4, further comprising:

assigning a distance between each of said nodes, said distance comprising one or more linguistic constraints.

6. The method of claim 5, wherein said generating a translation comprises finding a shortest tour including one node in each of said plurality of regions.

7. The method of claim 6, wherein said graph further comprises a region corresponding to a sentence boundary.

8. The method of claim 7, wherein said tour begins and ends in the region corresponding to the sentence boundary.

9. The method of claim 1, wherein said transforming comprises transforming the translation problem into a traveling salesman problem.

10. Apparatus comprising:

a transformation module operative to transform an input text segment in a source language into an integer programming problem ; and

an integer program solver operative to solve said integer programming problem.

11. The apparatus of claim 10, further comprising:

a database including a plurality of linguistic constraints for a target language and a plurality of words in the target language corresponding to possible translations for a plurality of words in a source language.

12. The apparatus of claim 11, wherein the transformation module comprises a graph generator operative to generate a graph including a plurality of regions and a plurality of nodes, each region corresponding to a word in an input source language text segment and each node corresponding to a possible translation of a word in the input source language, and to assign a distance between nodes based on said plurality of linguistic constraints.

13. The apparatus of claim 12, wherein the integer program solver is operative to find a shortest tour including one node in each of said plurality of regions.

14. The apparatus of claim 13, wherein the integer problem solver is further operative to output a text segment in the target language, said text segment including a plurality of words corresponding to the nodes in the shortest tour.

15. The apparatus of claim 14, wherein the plurality of words are aligned in an order corresponding to an order of nodes visited in the tour.

17. The article of claim 16, wherein the instructions operative to cause the machine to generate a translation include instructions operative to cause the machine to generate a text segment in a target language corresponding to a translation of a text segment in a source language.

18. The article of claim 16, wherein the instructions operative to cause the machine to transform include instructions operative to cause the machine to generate a graph comprising a plurality of regions, each region including one or more nodes.

19. The article of claim 18, further comprising instructions operative to cause the machine to:

input a text segment including words in a source language,

wherein each of said plurality of regions represents a corresponding one of the words in the source language, and

wherein the one or more nodes in each of said plurality of regions represent possible translations of the word corresponding to said region.

20. The article of claim 19, further comprising instructions operative to cause the machine to:

assign a distance between each of said nodes, said distance comprising one or more linguistic constraints.

21. The article of claim 20, wherein the instructions operative to cause the machine to generate a translation includes instructions operative to cause the machine to find a shortest tour including one node in each of said plurality of regions.

22. The article of claim 21, wherein said graph further comprises a region corresponding to a sentence boundary.

23. The article of claim 22, wherein said tour begins and ends in the region corresponding to the sentence boundary.

24. The article of claim 16, wherein the instructions operative to cause the machine to transform instructions operative to cause the machine to transform the translation problem into a traveling salesman problem.

16. An article comprising a machine-readable medium including machine-executable instructions, the instruction operative to cause the machine to:

transform a translation problem into an integer programming problem; and

generate a translation in response to solving the integer programming problem.