Systems and methods for fast and memory efficient machine translation using statistical integrated phase lattice

Abstract

A phrase-based translation system and method includes a statistically integrated phrase lattice (SIPL) (H) which represents an entire translational model. An input (I) is translated by determining a best path through an entire lattice (S) by performing an efficient composition operation between the input and the SIPL. The efficient composition operation is performed by a multiple level search where each operand in the efficient composition operation represents a different search level.

1 . A phrase-based translation method, comprising: 
 providing a statistically integrated phrase lattice (SIPL) (H) which represents an entire translational model; and    translating an input (I) by determining a best path through an entire lattice (S) by performing an efficient composition operation between the input and the SIPL, wherein the efficient composition operation is performed by a multiple level search where each operand in the efficient composition operation represents a different search level.    
   
   
       2 . The method as recited in  claim 1 , wherein the SIPL comprises multiple finite state transducers computed separately and prior to the translating step.  
   
   
       3 . The method as recited in  claim 2 , wherein the finite state transducers include at least one language model (L) and at least one translation model (M).  
   
   
       4 . The method as recited in  claim 3 , further comprising computing the at least one translation model (M) offline, wherein the at least one translation model includes a word-to-phrase sequencer (P), a phrase translation transducer (T), a target language phrase-to-word transducer (W).  
   
   
       5 . The method as recited in  claim 1 , wherein providing a statistically integrated phrase lattice (SIPL) includes providing the SIPL as a chain of conditional probabilities wherein portions of the chain include finite state machines.  
   
   
       6 . The method as recited in  claim 5 , wherein the finite state machines include determinizable transducers.  
   
   
       7 . The method as recited in  claim 1 , wherein translating includes performing a state traversal search across the entire lattice (S) wherein each of multiple levels of the multiple level search is searched simultaneously.  
   
   
       8 . The method as recited in  claim 1 , wherein multiple levels for the multiple level search include a level for the input (I), and at least one level for the SIPL.  
   
   
       9 . The method as recited in  claim 1 , wherein multiple levels include a level for the input (I), a level for a translation model and a level for language model.  
   
   
       10 . The method as recited in  claim 1 , wherein the best path is determined based on negative log probability cost.  
   
   
       11 . The method as recited in  claim 1 , wherein translating further comprises merging active search states of two or more of the input (I), the language model (L) and the translation model (M) when the states are identical.  
   
   
       12 . The method as recited in  claim 1 , wherein translating further comprises pruning states to balance between speed and accuracy.  
   
   
       13 . The method as recited in  claim 1 , wherein the method is run on a portable device.  
   
   
       14 . The method as recited in  claim 13 , wherein the portable device includes less than 20 MB of operating memory.  
   
   
       15 . A computer program product comprising a computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to perform a phrase-based translation method, comprising: 
 providing a statistically integrated phrase lattice (SIPL) (H) which represents an entire translational model; and    translating an input (I) by determining a best path through an entire lattice (S) by performing an efficient composition operation between the input and the SIPL, wherein the efficient composition operation is performed by a multiple level search where each operand of the efficient composition operation represents a different search level.    
   
   
       16 . The computer program product as recited in  claim 15 , wherein the SIPL comprises multiple finite state transducers computed separately and prior to the translating step.  
   
   
       17 . The computer program product as recited in  claim 16 , wherein the finite state transducers include at least one language model (L) and at least one translation model (M).  
   
   
       18 . The computer program product as recited in  claim 17 , further comprising computing the at least one translation model (M) offline, wherein the at least one translation model includes a word-to-phrase sequencer (P), a phrase translation transducer (T), a target language phrase-to-word transducer (W).  
   
   
       19 . The computer program product as recited in  claim 15 , wherein providing a statistically integrated phrase lattice (SIPL) includes providing the SIPL as a chain of conditional probabilities wherein portions of the chain include finite state machines.  
   
   
       20 . The computer program product as recited in  claim 19 , wherein the finite state machines include determinizable transducers.  
   
   
       21 . The computer program product as recited in  claim 15 , wherein translating includes performing a state traversal search across the entire lattice (S) wherein each of multiple levels is searched simultaneously.  
   
   
       22 . The computer program product as recited in  claim 15 , wherein the multiple level search includes multiple levels with a level for the input (I), and at least one level for the SIPL.  
   
   
       23 . The computer program product as recited in  claim 15 , wherein multiple levels of the multiple level search includes a level for the input (I), a level for a translation model and a level for language model.  
   
   
       24 . The computer program product as recited in  claim 15 , wherein the best path is determined based on negative log probability cost.  
   
   
       25 . The computer program product as recited in  claim 15 , wherein translating further comprises merging active search states of two or more of the input (I), the language model (L) and the translation model (M) when the states are identical.  
   
   
       26 . The computer program product as recited in  claim 15 , wherein translating further comprises pruning states to balance between speed and accuracy.  
   
   
       27 . The computer program product as recited in  claim 16 , wherein the product is run on a portable device.  
   
   
       28 . The computer program product as recited in  claim 27 , wherein the portable device includes less than 20 MB of operating memory.  
   
   
       29 . A method for training a phrase-based translation model, comprising: 
 extracting bilingual phrase pairs from utterances and estimating translation probabilities of the bilingual pairs to create an inventory of bilingual phrase pairs; and    creating a statistically integrated phrase lattice (SIPL) (H) using the inventory of bilingual phrase pairs to represent an entire translational model which includes a plurality of weighted finite state transducers (WFSTs) including at least a language model (L) and a translation model (M) against which an input may be compared to translate phrases.    
   
   
       30 . The method as recited in  claim 29 , wherein the translation model (M) includes a word-to-phrase sequencer (P), a phrase translation transducer (T), and a target language phrase-to-word transducer (W).  
   
   
       31 . The method as recited in  claim 29 , wherein the entire translational model is computed offline and stored in a portable device.  
   
   
       32 . A computer program product comprising a computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to train a phrase-based translation model, comprising: 
 extracting bilingual phrase pairs from utterances and estimating translation probabilities of the bilingual pairs to create an inventory of bilingual phrase pairs; and    creating a statistically integrated phrase lattice (SIPL) (H) using the inventory of bilingual phrase pairs to represent an entire translational model which includes a plurality of weighted finite state transducers (WFSTs) including at least a language model (L) and a translation model (M) against which an input may be compared to translate phrases.    
   
   
       33 . A phrase-based translation system, comprising: 
 a statistically integrated phrase lattice (SIPL) (H) stored in memory which represents an entire translational model; and    a translation module configured to translate an input (I) by determining a best path through an entire lattice (S), the translation model being configured to perform an efficient composition operation between the input and the SIPL, wherein the efficient composition operation is performed by a multiple level search where each operand in the efficient composition operation represents a different search level.    
   
   
       34 . The system as recited in  claim 33 , wherein the system is run on a portable device.  
   
   
       35 . The system as recited in  claim 34 , wherein the portable device includes less than 20 MB of operating memory for performing the translation and the entire translational model is stored in less than 100 MB.