Phrase-based statistical machine translation as a generalized traveling salesman problem
Systems and methods are described that facilitate phrase-based statistical machine translation (SMT) incorporating bigram (or higher n-gram) language models by modeling bi-phrases as nodes in a graph. Additionally, construction of a translation is modeled as a “tour” amongst the nodes of the graph, such that a translation solution is generated by treating the graph as a generalized traveling salesman problem (GTSP) and solving for an optimal tour. The overall cost of a tour is computed by adding the costs associated with the edges traversed during the tour. Thus, the described systems and methods map the SMT problem directly into a GTSP problem, which itself can be directly converted into a TSP problem.
1. A method of translating two languages using statistical machine translation (SMT) and a generalized asymmetric traveling salesman problem (GTSP) graph, comprising:
defining a SMT problem as a GTSP;
translating blocks of an input sentence using bi-phrases corresponding to nodes in a GTSP graph that represents the GTSP;
solving the GTSP; and
outputting the translated blocks in an order defined by the GTSP solution; and further comprising:
generating an optimal tour of the GSTP graph;
computing a true cost C t of the optimal tour;
computing an apparent cost C a of the optimal tour;
determining a difference D between a true cost C t and an apparent cost C a of the optimal tour;
determining whether the difference D is less than a predetermined threshold ε;
outputting the optimal tour as a solution to the GSTP if D is less than the predetermined threshold ε; and
translating the input sentence from a first language to a second language using the output GSTP solution;
wherein the true cost C t of the optimal tour is computed using n-gram costs, where n is an integer greater than or equal to 3.
2. The method of claim 1 , wherein solving the GTSP further comprises:
transforming the GTSP to an asymmetric traveling salesman problem (ATSP);
transforming the ATSP to a standard traveling salesman problem (TSP); and
solving the TSP to translate the blocks of the input sentence.
3. The method of claim 2 , further comprising solving the TSP using at least one of a Concorde solver and a Lin-Kernighan-heuristic.
4. The method of claim 1 , further comprising:
refining at least one node in the graph if D is greater than or equal to the predetermined threshold c, and generating a refined graph comprising the refined node; and
iteratively computing the true cost C t and apparent cost C a for one or more refined graphs, determining the difference D there between, and comparing the difference D to the predetermined threshold ε until D is less than c.
5. The method of claim 1 , wherein the optimal tour visits each node exactly once, wherein edges between nodes in the optimal tour are each associated with a respective bigram weight, and wherein the apparent cost C a of the optimal tour is computed by summing the bigram weights of all edges in the tour.
6. The method of claim 1 , further comprising generating the optimal tour of the graph using at least one of an approximate solver algorithm and an exact solver algorithm.
7. The method of claim 1 , wherein the SMT is a phrase-based SMT (PBSMT).
8. A non-transitory computer readable recording medium comprising instructions, which when executed on a computer cause the computer to perform the method of claim 1 .
9. A system that facilitates phrase-based statistical machine translation (PBSMT), comprising:
a processor that:
defines a PBSMT as a generalized traveling salesman problem (GTSP);
translates blocks of an input sentence using bi-phrases corresponding to nodes in a GTSP graph that represents the GTSP;
solves the GTSP; and
outputs the translated blocks in an order defined by the GTSP solution;
wherein the processor is further configured to:
generate an optimal tour of the GSTP graph;
output the optimal tour as a solution to the GSTP upon determining that a difference D between a true cost C t and an apparent cost C a of the optimal tour is less than a predetermined threshold ε; and
translate the input sentence from a first language to a second language using the output GSTP solution;
wherein the true cost C t of the optimal tour is computed using n-gram costs, where n is an integer greater than or equal to 3.
10. The system of claim 9 , wherein to solve the GTS, the processor:
transforms the GTSP to an asymmetric traveling salesman problem (ATSP);
transforms the ATSP to a standard traveling salesman problem (TSP); and
solves the TSP to translate the blocks of the input sentence.
11. The system of claim 10 , wherein the processor solves the TSP using at least one of a Concorde solver and a Lin-Kernighan-heuristic.
12. A method of phrase-based statistical machine translation (PBSMT), comprising:
defining a PBSMT task as a generalized traveling salesman problem (GTSP);
generating a graph of the GTSP comprising a plurality of nodes;
generating an optimal tour of the graph;
computing a true cost C t of the optimal tour;
computing an apparent cost C a of the optimal tour;
determining a difference D between the true cost C t and an apparent cost C a ;
determining whether the difference D is less than a predetermined threshold ε;
outputting the optimal tour as a solution to the GSTP if D is less than the predetermined threshold ε; and
translating an input sentence from a first language to a second language using the output GSTP solution;
wherein the true cost C t of the optimal tour is computed using n-gram costs, where n is an integer greater than or equal to 3.
13. The method of claim 12 , further comprising refining at least one node in the graph if D is greater than or equal to the predetermined threshold ε, and generating a refined graph comprising the refined node.
14. The method of claim 13 , further comprising iteratively computing the true cost C t and apparent cost C a for one or more refined graphs, determining the difference D there between, and comparing the difference D to the predetermined threshold ε until D is less than ε.
15. The method of claim 12 , wherein the optimal tour visits each node exactly once, wherein edges between nodes in the optimal tour are each associated with a respective bigram weight.
16. The method of claim 15 , wherein the apparent cost C a of the optimal tour is computed by summing the bigram weights of all edges in the tour.
17. The method of claim 12 , further comprising:
associating with the input sentence a plurality of blocks, each block corresponding to a bi-phrase that includes a phrase pair having a first-language phrase and a corresponding second-language phrase;
identifying an optimal selection and ordering of blocks using the output GTSP solution;
and outputting a corresponding ordering of the second-language phrases of the selected blocks.
18. The method of claim 12 , further comprising generating the optimal tour of the graph using at least one of an approximate solver algorithm and an exact solver algorithm.