Order model for dependency structure

• US 7,505,894 B2
• Filed: 12/16/2004
• Issued: 03/17/2009
• Est. Priority Date: 11/04/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Menezes, Arul A., Quirk, Christopher B., Cherry, Colin A.
• Primary Examiner(s): Vo; Huyen X.
• Application Number:
  US11/014,152
• Publication Number:
  US 20060111891A1
• Time in Patent Office: 1,552 Days
• Field of Search: 704/1, 704/2, 704/4, 704/5, 704/277, 704/3, 704/7, 704/8, 704/9
• US Class Current: 704/3
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models

Abstract

In one embodiment of the present invention, a decoder receives a dependency tree as a source language input and accesses a set of statistical models that produce outputs combined in a log linear framework. The decoder also accesses a table of treelet translation pairs and returns a target dependency tree based on the source dependency tree, based on access to the table of treelet translation pairs, and based on the application of the statistical models.

Claims

1. A computer-implemented method of assigning a score to an ordering of a target language dependency structure given a source language dependency structure and an alignment between nodes in the source language dependency structure and nodes in the target language dependency structure, the method comprising:

receiving a source language dependency structure indicative of a source language text fragment and a target language dependency structure;

assigning a score to the order of dependent nodes, depending directly from a parent node, in the target language dependency structure; and

wherein the target language dependency structure comprises a target language dependency tree and the source language dependency structure has nodes aligned with nodes in the target language dependency tree, and wherein assigning a score comprises;

computing a metric indicative of a probability that a selected node in the target language dependency tree has changed from one of a pre or post modifier of its parent node to become another of the pre or post modifier of its parent node in the target language dependency tree given that a node in the source language dependency structure aligned to the selected node in the target language dependency tree was a pre or post modifier of its parent node in the source language dependency structure; and

providing an output to a component of a machine translation system based on the assigned score.

2. The method of claim 1 wherein the target language dependency structure includes a plurality of parent nodes and wherein assigning a score to the order of dependent nodes comprises:

assigning a score to the order of dependent nodes depending directly from each of the plurality of parent nodes in the target language dependency structure.

3. The method of claim 1 wherein the target language dependency structure comprises a multi-level target language dependency tree and wherein assigning a score comprises:

assigning a score to the order of dependent nodes on each level of the multi-level target language dependency tree, independently of an order of nodes on other levels of the multi-level target language dependency tree; and

combining the scores of each level together to assign a score for the ordering of the whole target language dependency structure.

4. The method of claim 3 wherein the nodes in the target language dependency tree each represent a word in a target language text fragment.

5. The method of claim 4 wherein assigning a score to the order of dependent nodes on each level comprises:

assigning a score for each node, in turn, at each level of the target language dependency tree; and

combining the scores assigned to each node to assign a score to each level.

6. The method of claim 5 wherein assigning a score for each node comprises:

computing a probability of each node having a position offset relative to the parent node.

7. The method of claim 6 wherein assigning a score to each node comprises:

computing a probability for the selected node having a given proximity to its parent node relative to other nodes at a same level of the target language dependency tree.

8. The method of claim 6 wherein assigning a score for each node comprises:

assigning a score indicative of whether a selected node in the target language dependency tree should switch order position relative to each other node on the same level of the target language dependency tree and having a same modifier relationship to the parent node as the selected node.

9. The method of claim 1 wherein the scores assigned to the order of the target language dependency structure are based on a plurality of features comprising at least some of a set of features including:

target words corresponding to the dependent nodes and the parent node, source words aligned to the target words, positions of the source words in the source language dependency structure, and part-of-speech of each of the source and target words.

10. The method of claim 1 and further comprising:

learning to assign scores to orders of dependent nodes based on a corpus of parallel, aligned dependency structures.

11. The method of claim 10 wherein learning to assign scores comprises:

collecting sets of features from ordered target language dependency structures in the corpus; and

using a machine learning technique on the set of features to produce a model for assigning scores to orderings of target language dependency structures given source language dependency structures and alignments between the source and target dependency structures.

12. The method of claim 11 wherein using a machine learning technique comprises using decision trees.

13. The method of claim 11 and further comprising:

deploying the model in a machine translation system.

14. A computer-implemented system for assigning a score to the ordering of a target language dependency structure given a source language dependency structure and an alignment between nodes in the source language dependency structure and the target language dependency structure, the system comprising:

a subsystem including an order model configured to assign a score to an order of child nodes depending on a parent node in the target language dependency structure, given a plurality of source nodes in the source language dependency structure and an alignment between the nodes in the source language dependency structure and the target language dependency nodes, wherein the target language dependency structure comprises a target language dependency tree and wherein the source language dependency structure has nodes aligned with the nodes in the target language dependency tree, and wherein the order model is configured to compute a score indicative of whether a selected node in the target language dependency tree will switch from being a pre or post modifier of a parent node in the source language dependency structure to being a post or pre modifier of the parent node in the target language dependency tree, wherein the subsystem is configured to be deployed in a machine translation system.

15. The system of claim 14 wherein the target language dependency structure comprises a multi-level target language dependency tree wherein the order model is configured to assign a score to the order of dependent nodes on each level of the multi-level target language dependency tree, independently of an order of nodes on other levels of the multi-level target language dependency tree, and the score assigned to the whole dependency structure is based on a combination of the scores at each level.

16. The system of claim 15 wherein each of the nodes in the target language dependency tree represent a word in a target language text fragment, and wherein the order model is configured to assign a score to an order for each node, in turn, at each level of the target language dependency tree.

17. The system of claim 16 wherein the order model is configured to compute a probability of each node having a position offset relative to the parent node.

18. The system of claim 16 wherein the source language dependency structure has nodes aligned with the nodes in the target language dependency tree, and wherein the order model is configured to compute a score indicative of whether a selected node in the target language dependency tree will switch from being a pre or post modifier of a parent node in the source language text fragment to being a post or pre modifier of the parent node in the target language text fragment.

19. The system of claim 16 wherein the order model is configured to compute a probability of a position of each node having a position relative to other nodes at a same level of the target language dependency tree.

20. The system of claim 16 wherein the order model is configured to compute a probability indicative of whether a selected node in the target language dependency tree should switch order position relative to each other node on the same level of the target language dependency tree and having a same modifier relationship to the parent node as the selected node.

21. The system of claim 14 wherein the order model computes a probability for the order based on a plurality of features comprising at least some of a set of features including:

target words corresponding to the dependent nodes and the parent node, source words aligned to the target words, positions of the source words in the source language dependency structure, and part-of-speech of each of the source and target words.

22. The system of claim 14 wherein the model is generated by learning to assign scores to orders of child nodes based on a corpus of parallel, aligned dependency structures.

23. The system of claim 22 wherein learning is performed by:

collecting sets of features from ordered target language dependency structures in the corpus; and

using a machine learning technique on the set of features to produce a model for assigning scores to orderings of target language dependency structures given source language dependency structures and alignments between the source and target language dependency structures.