Discriminative Syntactic Word Order Model for Machine Translation

• US 20080319736A1
• Filed: 04/02/2008
• Published: 12/25/2008
• Est. Priority Date: 06/21/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Toutanova, Kristina Nikolova, Chang, Pi-Chuan
• Granted Patent: US 8,452,585 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models

Abstract

A discriminatively trained word order model is used to identify a most likely word order from a set of word orders for target words translated from a source sentence. For each set of word orders, the discriminatively trained word order model uses features based on information in a source dependency tree and a target dependency tree and features based on the order of words in the word order. The discriminatively trained statistical model is trained by determining a translation metric for each of a set of N-best word orders for a set of target words. Each of the N-best word orders are projective with respect to a target dependency tree and the N-best word orders are selected using a combination of an n-gram language model and a local tree order model.

Claims

1. A method comprising:

forming a source dependency tree for a source sentence in a source language, the source dependency tree indicating the syntactic hierarchy of source words in the source sentence;

forming a target dependency tree indicating the syntactic hierarchy of target words in a target language that are translations of source words in the source sentence;

identifying a set of target word orders, where each target word order that is identified is projective with respect to the target dependency tree;

using a discriminatively trained word order model to identify a most likely target word order from the set of target word orders, wherein for each set of target word orders, the discriminatively trained word order model uses features based on information in the source dependency tree and the target dependency tree and features based on the order of words in the target word order.

2. The method of claim 1 wherein identifying a set of target word orders comprises scoring each of a plurality of word orders based on a language model probability that provides a probability of the target words appearing in a surface form in that order and a local tree order model probability that provides a probability for positions of words assigned to child nodes relative to positions of words assigned to head nodes in the target dependency tree.

3. The method of claim 2 wherein the features based on information in the source dependency tree and the target dependency tree use part of speech tags for words in the source dependency tree and part of speech tags for words in the target dependency tree.

4. The method of claim 3 wherein the discriminatively trained statistical model uses as features the language model probability of the target words appearing in a surface form in the target word order and a local tree order model probability that provides a probability for positions of words assigned to child nodes relative to positions of words assigned to head nodes in the target dependency tree.

5. The method of claim 2 wherein the features based on the order of words in the target word order comprise features that indicate how words in the source sentence are positioned relative to each other where the words are translations of two contiguous target words in the target word order.

6. The method of claim 1 wherein the discriminatively trained statistical model is trained based on N-best target word orders identified by scoring each of a plurality of word orders based on a language model probability that provides a probability of the target words appearing in a surface form in that order and a local tree order model probability that provides a probability for positions of words assigned to child nodes relative to positions of words assigned to head nodes in a target dependency tree.

7. A method comprising:

receiving a target dependency tree comprising target words translated from source words of a source dependency tree, the target dependency tree and the source dependency tree providing hierarchical relationships between words;

scoring a plurality of word orders for the target words that are projective with respect to the target dependency tree to form word order scores, wherein scoring a word order comprises;

determining an n-gram language model probability for the word order; and

determining a local tree order model probability that is based on information from the source dependency tree, the target dependency tree and the word order;

using the word order scores to select a smaller set of word orders for the target words from the plurality of word orders for the target words;

using the smaller set of word orders of the target words to discriminatively train a model for selecting orders of target words; and

storing the parameters for the model on a computer-readable storage medium for use in ordering words in translations.

8. The method of claim 7 wherein using the smaller set of word orders to discriminatively train parameters for a model comprises:

determining a translation metric score for each word order in the smaller set of word orders;

selecting an order based on the translation metric score; and

discriminatively training the parameters of the model to optimize an objective function computed for the selected order.

9. The method of claim 8 wherein discriminatively training the parameters of the model to optimize an objective function comprises minimizing a negative log-likelihood of the selected order, wherein the log-likelihood comprises the log of a score for the selected word order over a sum of scores for each word order in the smaller set of word orders.

10. The method of claim 7 wherein the target words are translated from the source words using machine translation.

11. The method of claim 10 wherein some target words may be incorrect translations of source words.

12. A computer-readable storage medium having computer-executable instructions for performing steps comprising:

receiving a target dependency tree for a target sentence having words ordered in a first word order, wherein the target dependency tree is formed based on a machine translation from a source language to a target language,

reordering words in the target sentence to identify a second word order through steps comprising;

while limiting consideration of word orders to those word orders that are projective with respect to the target dependency tree, using feature values derived from the target dependency tree to determine likelihoods for a plurality of possible orders for the target words; and

selecting one of the orders for the target words based on the likelihoods.

13. The computer-readable storage medium of claim 12 further comprising identifying a source dependency tree for the source sentence.

14. The computer-readable storage medium of claim 13 further comprising identifying the plurality of possible orders for the target words by scoring a larger set of possible word orders for the target words using a combination of an n-gram language model and a local tree order model and selecting the plurality of possible orders with the best scores.

15. The computer-readable storage medium of claim 14 wherein the local tree order model provides a score based on the source dependency tree, the target dependency tree and the word order of target words.

16. The computer-readable storage medium of claim 15 wherein determining likelihoods for a plurality of possible orders for the target words comprises using feature weights that have been discriminatively trained based on word orders scored using a translation metric.

17. The computer-readable storage medium of claim 16 wherein the feature values use values for part of speech features for target words.

18. The computer-readable storage medium of claim 17 wherein the feature values use values for part of speech features for source words.

19. The computer-readable storage medium of claim 18 wherein the feature values comprise the score from the combination of the n-gram language model and the local tree order model.

20. The computer-readable storage medium of claim 19 wherein two contiguous target words in a word order of target words are respective translations of two source words in the source sentence and wherein the feature values comprise values for features that describe the position of the two source words relative to each other in the source sentence.