Method and system of machine translation

• US 20070239423A1
• Filed: 04/06/2007
• Published: 10/11/2007
• Est. Priority Date: 04/07/2006
• Status: Active Grant

• Current Assignee: Basis Technology Corporation
• Original Assignee: Basis Technology Corporation
• Inventors: Miller, Scott
• Granted Patent: US 7,827,028 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 system and method is provided for generating a translingual parsing model and for using the model to machine translate a source language to a destination language. The system and method includes receiving a sentence in the source language, and with the translingual parsing model, searching among and statistically ranking candidate parses each having elements labeled with destination language words, syntactic labels, and role labels indicating relationships between the elements. A statistically high ranked parse is selected and rearranged using the syntactic and role labels, in accordance with word order conventions of the destination language to generate a translingual parse of the source language sentence.

Claims

1. A method for machine translation from a source language to a destination language, said method comprising:

(a) receiving, at a translation module, at least one sentence in the source language;

(b) searching among and statistically ranking, with a translingual parsing model, a plurality of candidate parses each having;

elements labeled with destination language words corresponding to words of the source language sentence;

syntactic labels indicating a syntactic category of the elements; and

role labels indicating relationships between the elements;

(c) selecting a statistically high ranked parse for the at least one sentence; and

(d) rearranging the parse using the syntactic and role labels, in accordance with word order conventions of the destination language to generate a translingual parse of the source language sentence.

2. The method of claim 1, wherein said rearranging (d) comprises using a rule set associated with the word order conventions.

3. The method of claim 1, wherein the translingual parse comprises a plurality of nodes disposed in downstream branching relation from a single top node to a plurality of terminal nodes.

4. The method of claim 3, wherein said plurality of nodes comprises:

a plurality of labeled nodes including the syntactic labels and the role labels;

a plurality of pre-terminal nodes coupled downstream of the labeled nodes, the pre-terminal nodes respectively including the destination language words; and

the plurality of terminal nodes coupled to the pre-terminal nodes, the terminal nodes respectively including the words of the source language sentence.

5. The method of claim 3, wherein the syntactic labels are selected from the group consisting of:

CC, CD, UH, DT, EX, FW, IN, JJ, JJR, JJS, LS, MD, NN, NNS, NNP, NNPS, PDT, POS, PRP, PP$, RB, RBR, RBS, RP, SYM, TO, UH, VB, VBD, VBG, VBN, VBP, VBZ, WDT, WP, WP$, WRB, #, $, ., ,, ;

, (, ), ″

, ‘

, “

, ’

, ”

, ADJP, ADVP, NP, PP, S, SBAR, SBARQ, SINV, SQ, VP, WHADVP, WHNP, WHPP, X, and combinations thereof.

6. The method of claim 3, wherein the role labels define candidate roles of each labeled node, within the translingual parse, relative to its adjacent upstream node.

7. The method of claim 6, wherein the role labels are selected from the group consisting of:

HEAD, SBJ, OBJ, SYNHEAD, PPMOD, SMOD, PREMOD, POSTMOD, MIDMOD, and combinations thereof.

8. The method of claim 4, wherein said rearranging (d) comprises placing the pre-terminal nodes into a word order associated with the destination language.

9. The method of claim 8, comprising removing the plurality of terminal nodes from the translingual parse to generate a destination language parse.

10. The method of claim 8, comprising extracting the pre-terminal nodes to generate a destination language translation.

11. The method of claim 1, wherein said assigning (b) comprises (d) generating the translingual parsing model.

12. The method of claim 11, wherein said generating (d) comprises:

(e) receiving, at a parser training module, a destination language treebank having parse trees of a plurality of destination language sentences, the parse trees of said destination language sentences having nodes labeled with the syntactic labels;

(f) generating, using the destination language treebank, a destination language parsing model, including parameters for ranking candidate parse trees for a destination language sentence;

(g) receiving, at the parsing module, a second plurality of destination language sentences from a parallel corpus, the parallel corpus including the second plurality of destination language sentences and their respective source language equivalents;

(h) applying the destination language parsing model to the second plurality of destination language sentences to generate a ranked list of candidate parse trees for each sentence of the second plurality of destination language sentences;

(i) transforming the candidate parse trees by applying, with a tree transformer, a rule set associated with linguistic characteristics of the source and destination languages;

(j) assigning, with a role labeler, a linguistic role label to nodes of the candidate parse trees, the role label corresponding to the linguistic role of a node within its respective parse tree;

(k) extracting grammar constraints from portions of each candidate parse tree;

(l) estimating the translingual parsing model using the extracted grammar constraints, and source language sentences of the parallel corpus, the translingual parsing model including parameters sufficient to rank candidate parses, wherein the parameters relate elements of the candidate parses including source language words, destination language words, syntactic labels, and role labels.

13. The method of claim 12, wherein said linguistic characteristics include morphological structure of the source and destination languages.

14. The method of claim 12, wherein said linguistic characteristics include phrase structure of the source and destination languages.

15. The method of claim 12, wherein said estimating (l) is effected using an inside-outside algorithm.

16. The method of claim 12, wherein said estimating (l) is effected using a CKY algorithm.

17. The method of claim 12, wherein said receiving (g) further comprises receiving a destination language corpus.

18. The method of claim 17, wherein said extracting (k) comprises extracting statistics relating to dependencies between elements from the parse trees of the destination language corpus.

19. The method of claim 18, wherein the dependencies comprise lexicalized dependencies.

20. A method for generating a translingual parsing model for machine translating a source language to a destination language, said method comprising:

(a) receiving, at a parser training module, a destination language treebank having parse trees of a plurality of destination language sentences, the parse trees of said destination language sentences having nodes labeled with their syntactic categories in the destination language;

(b) generating, using the destination language treebank, a destination language parsing model, including parameters for ranking candidate parse trees for a destination language sentence;

(c) receiving, at the parsing module, a second plurality of destination language sentences from a parallel corpus, the parallel corpus including the second plurality of destination language sentences and their respective source language equivalents;

(d) applying the destination language parsing model to the second plurality of destination language sentences to generate a ranked list of candidate parse trees for each sentence of the second plurality of destination language sentences;

(e) transforming the candidate parse trees by applying, with a tree transformer, a rule set associated with linguistic characteristics of the source and destination languages;

(f) assigning, with a role labeler, a linguistic role label to nodes of the candidate parse trees, the role label corresponding to the linguistic role of a node within its respective parse tree;

(g) extracting grammar constraints from portions of each candidate parse tree;

(h) estimating the translingual parsing model using the extracted grammar constraints and source language sentences of the parallel corpus, the translingual parsing model including parameters sufficient to rank candidate parses, wherein the parameters relate elements of the candidate parses including source language words, destination language words, syntactic labels, and role labels.

21. The method of claim 20, wherein said linguistic characteristics include morphological structure of the source and destination languages.

22. The method of claim 20, wherein said linguistic characteristics include phrase structure of the source and destination languages.

23. The method of claim 20, wherein said estimating (h) is effected with a translingual grammar estimation module including a parser and a grammar.

24. The method of claim 20, wherein said receiving (c) comprises receiving a destination language corpus.

25. The method of claim 24, wherein said extracting (g) comprises extracting statistics relating to dependencies between elements from the parse trees of the destination language corpus.

26. The method of claim 25, wherein the dependencies comprise lexicalized dependencies.

27. A system for machine translation from a source language to a destination language, the system comprising:

a translation module configured for receiving at least one sentence in the source language;

a translingual parsing model configured for searching among and statistically ranking a plurality of candidate parses each having;

elements labeled with destination language words corresponding to words of the source language sentence;

syntactic labels indicating a syntactic category of the elements; and

role labels indicating relationships between the elements;

a parser configured for selecting the highest statistically ranked parse for the at least one sentence; and

a reordering module configured for rearranging at least one of the statistically ranked parses, using the syntactic and role labels, in accordance with word order conventions of the destination language to generate a translingual parse of the source language sentence.

28. A system for generating a translingual parsing model for machine translating a source language to a destination language, said system comprising:

a parser training module configured for receiving a destination language treebank having parse trees of a plurality of destination language sentences, the parse trees having nodes labeled with their syntactic categories;

the parser training module configured for generating, using the destination language treebank, a destination language parsing model, including parameters for ranking candidate parse trees for a destination language sentence;

the parser training module configured for receiving a second plurality of destination language sentences from a parallel corpus, the parallel corpus including the second plurality of destination language sentences and their respective source language equivalents;

a destination language parser configured for applying the destination language parsing model to the second plurality of destination language sentences to generate a ranked list of candidate parse trees for each sentence of the second plurality of destination language sentences;

a tree transformer configured for transforming the candidate parse trees by applying a rule set associated with linguistic characteristics of the source and destination languages;

a role labeler configured to assign a linguistic role label to nodes of the candidate parse trees, the role label corresponding to the linguistic role of a node within its respective parse tree;

an extraction module configured for extracting grammar constraints from portions of each candidate parse tree;

a translingual grammar estimator configured for estimating the translingual parsing model using the extracted grammar constraints and source language sentences of the parallel corpus;

the translingual parsing model including parameters sufficient to rank candidate parses, wherein the parameters relate elements of the candidate parses including source language words, destination language words, syntactic labels, and role labels.

29. The method of claim 28, wherein said linguistic characteristics include morphological structure of the source and destination languages.

30. The method of claim 28, wherein said linguistic characteristics include phrase structure of the source and destination languages.

31. An article of manufacture for machine translating a source language into a destination language, said article of manufacture comprising:

a computer usable medium having a computer readable program code embodied therein, said computer usable medium having;

computer readable program code for;

receiving, at a translation module, at least one sentence in the source language;

searching among and statistically ranking, with a translingual parsing model, a plurality of candidate parses each having;

elements labeled with destination language words corresponding to words of the source language sentence;

syntactic labels indicating a syntactic category of the elements; and

role labels indicating relationships between the elements;

selecting the highest statistically ranked parse for the at least one sentence; and

rearranging the parse using the syntactic and role labels, in accordance with word order conventions of the destination language to generate a translingual parse of the source language sentence.

32. The article of manufacture of claim 31, comprising computer readable program code for generating the translingual parsing model.

33. The article of manufacture of claim 32, wherein said computer readable program code for generating the translingual parsing model comprises computer readable program code for:

receiving, at a parser training module, a destination language treebank having parse trees of a plurality of destination language sentences, the parse trees of said destination language sentences having nodes labeled with the syntactic labels;

generating, using the destination language treebank, a destination language parsing model, including parameters for ranking candidate parse trees for a destination language sentence;

receiving, at the parsing module, a second plurality of destination language sentences from a parallel corpus, the parallel corpus including the second plurality of destination language sentences and their respective source language equivalents;

applying the destination language parsing model to the second plurality of destination language sentences to generate a ranked list of candidate parse trees for each sentence of the second plurality of destination language sentences;

transforming the candidate parse trees by applying, with a tree transformer, a rule set associated with linguistic characteristics of the source and destination languages;

assigning, with a role labeler, a linguistic role label to nodes of the candidate parse trees, the role label corresponding to the linguistic role of a node within its respective parse tree;

extracting grammar constraints from portions of each candidate parse tree; and

estimating the translingual parsing model using the extracted grammar constraints and source language sentences of the parallel corpus;

the translingual parsing model including parameters sufficient to rank candidate parses, wherein the parameters relate elements of the candidate parses including source language words, destination language words, syntactic labels, and role labels.

34. The method of claim 33, wherein said linguistic characteristics include morphological structure of the source and destination languages.

35. The method of claim 33, wherein said linguistic characteristics include phrase structure of the source and destination languages.

36. An automated translation machine for translating a source language into a destination language, said translation machine comprising:

means for receiving, at a translation module, at least one sentence in the source language;

means for searching among and statistically ranking, with a translingual parsing model, a plurality of candidate parses each having;

elements labeled with destination language words corresponding to words of the source language sentence;

syntactic labels indicating a syntactic category of the elements; and

role labels indicating relationships between the elements;

means for selecting the highest statistically ranked parse for the at least one sentence; and

means for rearranging the parse using the syntactic and role labels, in accordance with word order conventions of the destination language to generate a translingual parse of the source language sentence.

37. The automated translation machine of claim 36, comprising means for generating the translingual parsing model.

38. The automated translation machine of claim 37, wherein said means for generating the translingual parsing model comprises:

means for receiving, at a parser training module, a destination language treebank having parse trees of a plurality of destination language sentences, the parse trees of said destination language sentences having nodes labeled with the syntactic labels;

means for generating, using the destination language treebank, a destination language parsing model, including parameters for ranking candidate parse trees for a destination language sentence;

means for receiving, at the parsing module, a second plurality of destination language sentences from a parallel corpus, the parallel corpus including the second plurality of destination language sentences and their respective source language equivalents;

means for applying the destination language parsing model to the second plurality of destination language sentences to generate a ranked list of candidate parse trees for each sentence of the second plurality of destination language sentences;

means for transforming the candidate parse trees by applying, with a tree transformer, a rule set associated with linguistic characteristics of the source and destination languages;

means for assigning, with a role labeler, a linguistic role label to nodes of the candidate parse trees, the role label corresponding to the linguistic role of a node within its respective parse tree;

means for extracting grammar constraints from portions of each candidate parse tree; and

means for estimating the translingual parsing model using the extracted grammar constraints and source language sentences of the parallel corpus, the translingual parsing model including parameters sufficient to rank candidate parses, wherein the parameters relate elements of the candidate parses including source language words, destination language words, syntactic labels, and role labels.

39. The method of claim 38, wherein said linguistic characteristics include morphological structure of the source and destination languages.

40. The method of claim 38, wherein said linguistic characteristics include phrase structure of the source and destination languages.