Order model for dependency structure

• US 20060111891A1
• Filed: 12/16/2004
• Published: 05/25/2006
• 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.
• Granted Patent: US 7,505,894 B2
• Time in Patent Office: Days
• 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 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; and

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

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 5 wherein the source language dependency structure has nodes aligned with the nodes in the target language dependency tree, and wherein assigning a score for each node comprises:

computing a probability that a selected node in the target language dependency tree has switched to become a pre or post modifier of its parent node in the target language dependency structure given that a node in the source language dependency structure aligned to the selected node in the target language dependency node was a pre or post modifier of its parent node in the source language dependency structure.

8. The method of claim 7 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.

9. The method of claim 7 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.

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

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

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

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

14. The method of claim 12 and further comprising:

deploying the model in a machine translation system.

15. A model 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 model comprising:

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.

16. The model of claim 15 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.

17. The model of claim 16 wherein the nodes in the target language dependency tree each 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.

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

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

20. The model of claim 19 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.

21. The model of claim 19 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.

22. The model of claim 15 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.

23. The method of claim 15 wherein the order model is deployed in a machine translation system.

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

25. The model of claim 24 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.

26. A method of training a model, comprising:

accessing a corpus of parallel, aligned source language dependency structures and target language dependency structures; and

training the model to assign scores to an ordering of nodes in a target language dependency structure with a machine learning system based on a set of features in the corpus.

27. The method of claim 26 wherein accessing comprises:

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

28. The method of claim 27 wherein training comprises:

training the model to assign the scores given source language dependency structures and alignments between the source and target language dependency structures.

29. The method of claim 28 wherein training the model comprises:

training the model using decision trees.