Patent Document ID: 8452585
Application ID: 12061313

Base Claim:
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 plurality of target word orders after forming the target dependency tree, where each target word order contains the words in the target dependency tree, wherein identifying a plurality of target word orders after forming the target dependency tree comprises restricting the word orders in the plurality of word orders to word orders that are projective with respect to the target dependency tree such that each word and the word's descendants in the target dependency tree form a contiguous subsequence in the word order; identifying N-best target word orders from the plurality of target word orders by determining a score for each target word order by combining 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; using a discriminatively trained word order model to identify a most likely target word order from the N-best target word orders, wherein for each target word order in the N-best 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.

---

Claim 5:
5. The method of claim 1 wherein the discriminatively trained word order 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.