Syntax-based statistical translation model

• US 8,214,196 B2
• Filed: 07/03/2002
• Issued: 07/03/2012
• Est. Priority Date: 07/03/2001
• Status: Active Grant

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Yamada, Kenji, Knight, Kevin
• Primary Examiner(s): YEN, ERIC L
• Application Number:
  US10/190,298
• Publication Number:
  US 20030023423A1
• Time in Patent Office: 3,653 Days
• Field of Search: 704/4, 704/7, 704/9, 704/2
• US Class Current: 704/2
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models

Abstract

A statistical translation model (TM) may receive a parse tree in a source language as an input and separately output a string in a target language. The TM may perform channel operations on the parse tree using model parameters stored in probability tables. The channel operations may include reordering child nodes, inserting extra words at each node (e.g., NULL words) translating leaf words, and reading off leaf words to generate the string in the target language. The TM may assign a translation probability to the string in the target language.

Claims

1. A method for translating natural languages using a statistical translation system, the method comprising:

parsing a first string in a first language into a parse tree using a statistical parser included in the statistical machine translation system, the parse tree including a plurality of nodes, one or more of said nodes including one or more leafs, each leaf including a first word in the first language, the nodes including child nodes having labels;

determining a plurality of possible reorderings of one or more of said child nodes including one or more of the leafs using the statistical translation system, the reordering performed in response to a probability corresponding to a sequence of the child node labels;

determining a probability between 0.0000% and 100.0000%, non-inclusive, of the possible reorderings by the statistical translation system;

determining a plurality of possible insertions of one or more words at one or more of said nodes using the statistical translation system;

determining a probability between 0.0000% and 100.0000%, non-inclusive, of the possible insertions of one or more words at one or more of said nodes by the statistical translation system;

translating the first word at each leaf into a second word corresponding to a possible translation in a second language using the statistical translation system; and

determining a total probability between 0.0000% and 100.0000%, non-inclusive, based on the reordering, the inserting, and the translating by the statistical translation system.

2. The method of claim 1, wherein said translating comprises translating the first word at each leaf into a second word in the second language in response to a probability of a correct translation.

3. The method of claim 1, wherein said inserting comprises inserting one of a plurality of NULL words at one or more of said nodes.

4. The method of claim 1, wherein said inserting comprises inserting the word at an insert position relative to a node.

5. The method of claim 4, wherein the insert position comprises one of a left position, a right position, and no position.

6. The method of claim 1, wherein the parse tree includes one or more parent nodes and a plurality of child nodes associated with the one or more parent nodes, the parent nodes having parent node labels and the child nodes having child node labels.

7. The method of claim 6, wherein said inserting comprises inserting one of the plurality of words at a child node in response to the child node label and the parent node label.

8. The method of claim 1, further comprising:

generating a second string including the second word at each leaf.

9. The method of claim 8, further comprising:

assigning a translation probability to the second string.

10. An apparatus for translating natural languages, the apparatus comprising:

a reordering module operative to determine a plurality of possible reorderings of nodes in a parse tree, said parse tree including the plurality of possible nodes, one or more of said nodes including a leaf having a first word in a first language, the parse tree including a plurality of parent nodes having labels, each parent node including one or more child nodes having a label, the reordering module including a reorder table having a reordering probability associated with reordering a first child node sequence into a second child node sequence;

an insertion module operative to determine a plurality of possible insertions of an additional word at one or more of said nodes and to determine a probability between 0.0000% and 100.0000%, non-inclusive, of the possible insertions of of the additional word;

a translation module operative to translate the first word at each leaf into a second word corresponding to a possible translation in a second language;

a probability module to determine a plurality of possible reorderings of a probability between 0.0000% and 100.0000%, non-inclusive, of said plurality of possible reorderings of one or more of said nodes and to determine a total probability between 0.0000% and 100.0000%, non-inclusive, based on the reorder, the insertion, and the translation; and

a statistical translation system operative to execute the reordering module, the insertion module, the translation module, and the probability module to effectuate functionalities attributed respectively thereto.

11. The apparatus of claim 10, wherein the translation module is further operative to generate an output string including the second word at each leaf.

12. The apparatus of claim 11, wherein the translation module is operative to assign a translation probability to the output string.

13. The apparatus of claim 11, further comprising a training module operative to receive a plurality of translation sentence pairs and train the apparatus using said translation pairs and an Expectation Maximization (EM) algorithm.

14. The apparatus of claim 10, wherein the insertion module includes an insertion table including the probability associated with inserting the additional word in a position relative to one of the child nodes.

15. The apparatus of claim 14, wherein the insertion probability is associated with a label pair including the label of said one or more child node and the label of the parent node associated with said child node.

16. The apparatus of claim 10, wherein the insertion module includes an insertion table including an insertion probability associated with inserting one of a plurality of additional words.

17. The apparatus of claim 16, wherein the additional word comprises a NULL word.

18. An article comprising a non-transitory machine readable medium including machine-executable instructions, the instructions operative to cause a machine to:

parse a first string in a first language into a parse tree, the parse tree including a plurality of nodes, one or more of said nodes including one or more leafs, each leaf including a first word in the first language, the nodes including child nodes having labels;

determine a plurality of possible reorderings of one or more of said child nodes including one or more of the leafs, the reordering performed in response to a probability corresponding to a sequence of the child node labels;

determine a probability between 0.0000% and 100.0000%, non-inclusive, of the plurality of possible reorderings;

determining a plurality of possible insertions of one or more words at one or more of said nodes;

determine a probability between 0.0000% and 100.0000%, non-inclusive, of the plurality of possible insertions at one or more of said nodes;

translate the first word at each leaf into a second word corresponding to a possible translation in a second language; and

determine a total probability between 0.0000% and 100.0000%, non-inclusive, based on the reordering, the inserting, and the translating, wherein the nodes include child nodes having labels, and wherein said reordering comprises reordering one or more of said child nodes in response to a probability corresponding to a sequence of the child node labels.