Source: http://patents.com/us-8082143.html
Timestamp: 2019-10-17 17:55:42
Document Index: 247477937

Matched Legal Cases: ['Application No. 05108799', 'Application No. 05108799', 'application No. 200510108982', 'Application No. 05108799', 'Application No. 200510108982', 'Application No. 05', 'Application No. 200510108982']

US Patent # 8,082,143. Extracting treelet translation pairs - Patents.com
United States Patent 8,082,143
Menezes , et al. December 20, 2011
Appl. No.: 12/499,379
11014492 Dec., 2004 7577562
11014503 Dec., 2004 7698124
Current U.S. Class: 704/7 ; 704/2; 704/277
Field of Search: 704/1-10,277,257,251,270
5477450 December 1995 Takeda et al.
2003083708 Oct., 2003 WO
Extended Search Report, European Patent Application No. 05108799.7-1527, dated Sep. 22, 2008. cited by other .
Partial Search Report, European Patent Application No. 05108799.7-1527, dated Jun. 25, 2008. cited by other .
Sato, S. et al., "Toward Memory-Based Translation," Proc. of Coling. Aug. 20, 1990, pp. 247-252. cited by other .
Watanabe, H. et al., "Finding Structural Correspondences from Bilingual Parsed Corpus for Corpus-based Translation " Proc. of MT Summit VIII-2001, pp. 906-912. cited by other .
Decision on Rejection of Chinese patent application No. 200510108982.7, dated Feb. 6, 2009. cited by other .
EP Search Report, Application No. 05108799.7-1527, dated May 22, 2008. 15 pages. cited by other .
Chinese Application No. 200510108982.7 Decision on Rejection dated Feb. 6, 2009. 10 pages. cited by other .
European Patent Application No. 05 108 799.7 Examination Report dated Jun. 3, 2009. 5 pages. cited by other .
Uchimoto K. et al. Word Order Acquisition from Corpora, Coling 2000: 871-877. 7 pages. cited by other .
Hudson R., Word Grammar, basil Blackwell, Oxford, 1984. 8 pages. cited by other .
Chinese Patent Application No. 200510108982.7, Second Office Action mailed Apr. 28, 2011. 19 pages. cited by other.
1. A method of identifying treelet translation pairs for use in a machine translation system that translates a source language input into a target language output, the method comprising: accessing a corpus of pairs of aligned, parallel syntactic dependency structures, each pair including a source language dependency structure having nodes that represent lexical items, the nodes being aligned with nodes representing lexical items in a target language dependency structure corresponding to the source language dependency structure in the corpus; for one or more of the source language dependency structures in the corpus, enumerating, using a processor of a computer, individual source nodes and combinations of source nodes connected in the source language dependency structure as possible source treelets identifying lexical items, and corresponding dependencies, in the target language dependency structure corresponding to the source language dependency structure, that are aligned with the enumerated nodes and combinations of connected nodes, as possible target treelets corresponding to the possible source treelets, wherein a plurality of possible source treelets are enumerated for the source language dependency structure; extracting well formed treelet translation pairs from the plurality of possible source treelets and possible target treelets; and storing the treelet translation pairs in a data store.
3. The method of claim 1 wherein the source language dependency structures each represent a source language text fragment, and wherein enumerating comprises: enumerating connected portions of the source language dependency structure regardless of whether the connected portions represent discontiguous sets of words in the source language text fragment.
4. The method of claim 1 wherein the source language dependency structure comprises a source language dependency tree, and wherein enumerating comprises: enumerating connected sets of nodes that represent a non-linear branch in the source language dependency tree.
5. A system for identifying treelet translation pairs, from training data, for use in a machine translation system that translates a source language input into a target language output, the system comprising: a processor; a treelet pair extractor configured to access a corpus of pairs of aligned, parallel syntactic dependency structures, each pair including a source language dependency structure having nodes that represent lexical items, the nodes being aligned with nodes representing lexical items in a target language dependency structure; and the treelet pair extractor being further configured to enumerate sets of source nodes that are connected portions of the source language dependency structure as possible source treelets using the processor, the treelet pair extractor being configured to enumerate a plurality of possible source treelets of different sizes from the source language dependency structure, the size of each possible source treelet being indicated by a number of nodes contained in the possible source treelet.
7. The system of claim 5 and further comprising: a data store storing the extracted treelet translation pairs.
11. A hardware computer readable storage medium storing computer readable instructions which, when executed by a computer cause the computer to perform a method of identifying treelet translation pairs for use in a machine translation system that translates a source language input into a target language output, the method comprising: accessing a corpus of pairs of aligned, parallel syntactic dependency structures, each pair including a source language dependency structure having nodes that represent lexical items, the nodes being aligned with nodes representing lexical items in a target language dependency structure; enumerating connected sets of source nodes in the source language dependency structure as possible source treelets; and extracting well formed treelet translation pairs from the possible source treelets and aligned portions of a corresponding target language dependency structure.
13. The hardware computer readable medium of claim 11 wherein extracting comprises: identifying lexical items, and corresponding dependencies, in the target language dependency structure, that are aligned with the enumerated connected sets of nodes, as possible target treelets corresponding to the possible source treelets; extracting the well formed treelet translation pairs based on the possible source treelets and the possible target treelets.
14. The hardware computer readable medium of claim 13 wherein the source language dependency structures each represent a source language text fragment, and wherein enumerating comprises: enumerating connected sets of source nodes in the source language dependency structure that may represent discontiguous words in the source language text fragment.
16. The hardware computer readable medium of claim 11 wherein the method further comprises: storing the treelet translation pairs in a data store.
17. The hardware computer readable medium of claim 11 wherein the source language dependency structure comprises a source language dependency tree, and wherein enumerating comprises: enumerating connected sets of nodes that represent a non-linear branch in the source language dependency tree.
18. The hardware computer readable medium of claim 11 wherein extracting well formed treelet translation pairs comprises: extracting as a well formed treelet translation pair the possible source treelet and corresponding possible target treelet only if the lexical items in the possible source treelet are only aligned with lexical items in the possible target treelet and the lexical items in the possible target treelet are only aligned with lexical items in the possible source treelet.
(1) One-to-Many alignments: For all distinct sets of target words T.sub.i and T.sub.k where (a) All words in T.sub.i and T.sub.j are aligned to source words s.sub.k and s.sub.l, and (b) No other target words are aligned to s.sub.k and s.sub.l, and (c) t.sub.j is the representative element of T.sub.i, and (d) t.sub.j is the representative element of T.sub.j, create a dependency from t.sub.i to t.sub.j if and only if there is a dependency relation from s.sub.k to s.sub.l and for each t.sub.k in T.sub.i where t.sub.k !=t.sub.i, create a dependency from t.sub.k to t.sub.i, and for each t.sub.m in T.sub.j where t.sub.m !=t.sub.j, create a dependency from t.sub.m to t.sub.j
(2) One-to-One and Many-to-One alignments: Similarly, for all target words t.sub.i and t.sub.j that are uniquely aligned to distinct sets of source words S.sub.k and S.sub.l, we create a dependency from t.sub.i to t.sub.j if and only if there is a dependency relation from s.sub.k to s.sub.l for some s.sub.k in S.sub.k and for some s.sub.k in S.sub.l.
Thus, the output of dependency tree projection component 220 yields a corpus of word aligned parallel dependency tree structures (or dependency structures) such as those shown in FIG. 8D or 8E. For the present discussion, the term "dependency tree" will be used to refer to either the type of structure which shows dependencies by arcs along a word string (such as that shown in FIG. 7E) or the actual depending tree structure such as that shown in FIG. 7F. A "dependency tree" will thus refer to both of those structures interchangeably. Therefore, the term "word aligned parallel dependency trees" can be used to refer to both types of structures shown in FIGS. 8D and 8E interchangeably Other embodiments of the dependency projection tree component may use a different set of rules, heuristics or statistics than those described above.
Order model 206 provides a probability for each of the words at that level, falling in the annotated positions. Such a probability can be one such as that shown in Equation 1. P(pos=+1) given that Equation. 1
TABLE-US-00001 TABLE 1 ALGORITHM 1 Exhaustive decoding algorithm Function GetNBestTranslation(i:input node) L.rarw.0; a sorted list of translations for all treelet pairs p rooted at i do R.rarw.roots of input subtrees not covered by p for all r .epsilon. R do let x[r].rarw. GetNBestTranslations(r) end for for all sets of translations Q, one from x[r] for each r .epsilon. R do for all order attachments Q' of Q into the target side of p do T .rarw. target subtree interleaving Q' into the target side of p score T according to models add T to L in order end for end for end for return the n-best list L end function
In one illustrative embodiment, decoder 608 enumerates all possible ways to connect the two sub-trees and scores each possible way with the complete set of models (or all those that apply) to determine the most likely way of connecting the two. This is indicated by block 714 in FIG. 14D. The two possibilities are shown in FIG. 14C. Equation 4 indicates one illustrative way of combining the scores of each of the models to obtain an overall score for each hypothesis. Score=.lamda..sub.1 log(channel model probability)+ .lamda..sub.2 log(order model probability)+ .lamda..sub.3 log(agreement model probability)+ .lamda..sub.4 log(target LM probability) Eq. 4
The channel model probability will be the probability of "installe sur" being translated as "installed on", multiplied by the probability of "votre ordinateur" being translated as "your computer." The order model probability of the first possible order in FIG. 14C will be the probability that "sur" is a post-modifier of "installe" in position +1 multiplied by the probability that "ordinateur" is a pre-modifier of "sur" in position -1. The order model probability of the second possible order in FIG. 14C will be the probability that "sur" is a post-modifier of "installe" in position +1 multiplied by the probability that "ordinateur" is a post-modifier of "sur" in position +1. The agreement model probability will be the probability of "sur" being a child of "installe" multiplied by the probability of "ordinateur" being a child of "sur" and the probability of "votre" being a child of "ordinateur." Finally, the target language model probability will simply be the string-based probability of the target language surface string read off of each of the leaves of the hypothesis target language dependency trees, which is "installe votre ordinateur sur" for the first possibility and "installe sur votre ordinateur" for the second possibility.
TABLE-US-00002 TABLE 2 Algorithm 2 Greedy ordering algorithm Order{best} : empty ordering with 0 probability. for each possible count of pre- and post-modifiers for each premodifer position from right to left for each unordered node Evaluate this unordered node in this position end for Place the highest scoring unordered node in this position Remove that node from the unordered pool end for for each postmodifier position from left to right for each unordered node Evaluate this unordered node in this position end for Place the highest scoring unordered node in this position Remove that node from the unordered pool end for if this ordering has higher score than O_{best} Order{best} := this ordering end if end for return Order {best}
Previous Patent US 8,082,142 | Next Patent US 8,082,144