Syntax-based statistical translation model

• US 20030023423A1
• Filed: 07/03/2002
• Published: 01/30/2003
• Est. Priority Date: 07/03/2001
• Status: Active Grant

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Knight, Kevin, Yamada, Kenji
• Granted Patent: US 8,214,196 B2
• Time in Patent Office: Days
• 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 separate 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 comprising:

parsing a first string in a first language into a parse tree including a plurality of leafs, each leaf including a first word in the first language;

reordering one or more of the leafs; and

translating the first word at each leaf into a second word corresponding to a possible translation in a second language.

2. The method of claim 1, wherein the parse tree comprises a plurality of nodes, one or more of said nodes including one or more leafs.

3. The method of claim 2, wherein said reordering comprises reordering one or more of said nodes.

4. The method of claim 1, comprising determining a probability of said reordering.

5. The method of claim 2, wherein the nodes include child nodes having labels.

6. The method of claim 5, 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.

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

8. The method of claim 1, further comprising:

inserting one of a plurality of words at one or more of said nodes.

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

10. The method of claim 8, wherein said inserting comprises inserting the word at an insert position relative to the node.

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

12. The method of claim 10, 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.

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

14. The method of claim 1, further comprising:

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

15. The method of claim 14, further comprising:

assigning a translation probability to the second string.

16. Apparatus comprising:

a reordering module operative to reorder nodes in a parse tree, said parse tree including a plurality of nodes, one or more of said nodes including a leaf having a first word in a first language;

an insertion module operative to insert an additional word at one or more of said nodes; and

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.

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

18. The apparatus of claim 17, further comprising a translation model operative to assign a translation probability to the output string.

19. The apparatus of claim 17, 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.

20. The apparatus of claim 16, wherein the parse tree comprises a plurality of parent nodes, each parent node having a label, and

wherein each parent node includes one or more child nodes, each child node having a label.

21. The apparatus of claim 20, wherein the reordering module includes a reorder table including a reordering probability associated with reordering a first child node sequence into a second child node sequence.

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

23. The apparatus of claim 22, 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.

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

25. The apparatus of claim 24, wherein the additional word comprises a NULL word.

26. An article comprising a 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 including a plurality of leafs, each leaf including a first word in the first language;

reorder one or more of the leafs; and

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

27. The article of claim 26, wherein the parse tree comprises a plurality of nodes, one or more of said nodes including one or more leafs.

28. The article of claim 27, wherein the instructions operative to cause the machine to reorder include instructions operative to cause the machine to reorder one or more of said nodes.