Integer programming decoder for machine translation

• US 7,177,792 B2
• Filed: 05/31/2002
• Issued: 02/13/2007
• 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
• Primary Examiner(s): MCFADDEN, SUSAN IRIS
• Application Number:
  US10/160,284
• Publication Number:
  US 20020188438A1
• Time in Patent Office: 1,719 Days
• Field of Search: 704/2, 704/8, 704/9
• 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 text in response to solving the integer programming problem, wherein said transforming comprises generating a graph comprising a plurality of regions, each region including one or more nodes, wherein said generating a translation text comprises generating a text segment in a target language corresponding to a translation of a text segment in a source language.

2. The method of claim 1, 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.

3. The method of claim 2, further comprising:

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

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

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

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

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

8. 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, and 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 a plurality of words in a source language, wherein the transformation module comprises a graph generator operative to generate a graph including a plurality 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.

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

10. The apparatus of claim 8, 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.

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

12. 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 text in response to solving the integer programming problem, wherein the instructions operative to cause the machine to generate a translation text 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, 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.

13. The article of claim 12, 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.

14. The article of claim 12, 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.

15. The article of claim 12, 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.

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

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

18. The article of claim 12, 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.