Integer programming decoder for machine translation

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.

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.  
   
   
       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.    
   
   
       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.