Source: https://patents.google.com/patent/US8082143B2/en
Timestamp: 2018-05-25 13:08:47
Document Index: 785422486

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

US8082143B2 - Extracting treelet translation pairs - Google Patents
Extracting treelet translation pairs Download PDF
US8082143B2
US8082143B2 US12499379 US49937909A US8082143B2 US 8082143 B2 US8082143 B2 US 8082143B2 US 12499379 US12499379 US 12499379 US 49937909 A US49937909 A US 49937909A US 8082143 B2 US8082143 B2 US 8082143B2
US12499379
US20090271177A1 (en )
The present application is a continuation of and claims priority of U.S. patent application Ser. No. 11/014,492, filed Dec. 16, 2004, which is a divisional of and claims priority of U.S. patent application Ser. No. 11/014,503, filed Dec. 16, 2004, which is based on and claims the benefit of U.S. provisional patent application Ser. No. 60/625,489, filed Nov. 4, 2004, the content of which is hereby incorporated by reference in its entirety.
Inversion transduction grammars (ITGs) are used in another prior art attempt to incorporate a notion of constituency into statistical machine translation. The basic idea is to consider alignment and translation as simultaneous parses of the source and target language. Two types of binary branching rules are allowed. Either the source and target constituents are produced in the same order, or the source and target constituents are produced in reverse order. Some such systems are described in Wu, STOCHASTIC INVERSION INDUCTION GRAMMARS AND BILINGUAL PARSING OF PARALLEL CORPORA, Computational Linguistics, 23(3):377-403 (1997); Wu and Wong, MACHINE TRANSLATION WITH A STOCHASTIC GRAMMATICAL CHANNEL, Proceedings of the ACL (1998); Zens and Ney, A COMPARATIVE STUDY ON REORDERING CONSTRAINTS AND STATISTICAL MACHINE TRANSLATION, Proceedings of the ACL (2003); and Zens et al., REORDERING CONSTRAINTS FOR PHRASE-BASED STATISTICAL MACHINE TRANSLATION, Proceedings of COLING (2004). These grammars are theoretically interesting. However, in order to make these types of processes computationally efficient, a number of severely limiting simplifying assumptions must be made. This significantly reduces the modeling power of such systems. In addition, this type of translation model acts only at the level of a single lexical item at a time (i.e., at the word level) and phrasal combinations are not modeled directly. This is a rather severe limitation. The demonstrated translation quality of these systems has not been on par with the best SMT systems.
Another prior art approach related to Inversion Transduction Grammars uses head transducers to produce a translation by simultaneously parsing the source sentence and transuding a target dependency tree using a collection of transducers that apply independently to each level of a source dependency tree. These transducers are limited in scope. They rely only on very local context, such that the end result is a fundamentally word-based (as opposed to phrase-based) decoder. The transducer induction process is also likely complicated by data sparsity problems. Instead of factoring the translation modeling into several different components (such as lexical selection, ordering, etc.), only a single transducer is trained. One such system is set out in Alashawi, et al., LEARNING DEPENDENCY TRANSLATION MODELS AS COLLECTIONS OF FINITE-STATE HEAD TRANSDUCERS, Computational Linguistics, 26(1):45-60 (2000).
FIGS. 4A-4D illustrate generation of a dependency structure and word alignment of a pair of sentences.
FIGS. 6A-6E illustrate structures that show projection of dependencies from the source language dependency tree to the target language dependency tree.
FIGS. 7A-7F illustrate projection of dependencies from a source language dependency tree to a target language dependency tree where a word in the target sentence is unaligned.
FIGS. 8A-8I illustrate projection of dependencies from a source language tree to a target language tree and the extraction of treelet translation pairs where multiple words in the source language input are aligned to a single word in the target language input.
FIGS. 9A-9C illustrate extraction of treelet translation pairs from a pair of sentences in which multiple words in the target language sentence are aligned to a single word in the source language sentence.
FIGS. 10A-10D illustrate how an order model is trained in accordance with one embodiment of the present invention.
FIGS. 11A-11C illustrate the operation of a second embodiment of an order model.
FIGS. 14A-14C illustrate the operation of a dynamic programming decoder in accordance with one embodiment of the present invention.
(c) tj is the representative element of Ti, and
(d) tj is the representative element of Tj, create a dependency from ti to tj if and only if there is a dependency relation from sk to sl and for each tk in Ti where tk !=ti, create a dependency from tk to ti, and for each tm in Tj where tm !=tj, create a dependency from tm to tj
(2) One-to-One and Many-to-One alignments: Similarly, for all target words ti and tj that are uniquely aligned to distinct sets of source words Sk and Sl, we create a dependency from ti to tj if and only if there is a dependency relation from sk to sl for some sk in Sk and for some sk in Sl.
A treelet translation pair is defined as connected subgraph of the source language dependency tree and the corresponding connected subgraph of the target language dependency tree. However, in accordance with one embodiment of the present invention, the definition of “connected subgraph” treats siblings from any node in the tree as being connected through a dummy parent node. Extraction of treelet translation pairs is performed by treelet pair extractor 224 shown in FIG. 2. Example structures indicating how this is done are shown in FIGS. 8E-8I and a flow diagram illustrating how this is done is shown in FIG. 8J.
Treelet pair extractor 224 then extracts from the enumerated treelets and corresponding alignments, well-formed treelet translation pairs. This is indicated by block 410 in FIG. 8J. The treelets “empty-vider” and “the-le” are both well-formed and are thus extracted and placed in the treelet translation table. However, the entire treelet translation pair for the terms “bin” and “recycle” is shown in FIG. 8G. Because both the single node treelet “recycle” and the single node treelet “bin” are aligned to the same target language word “corbeille”, extracting either of them independently of the other would not generate a well-formed treelet translation pair. It would result in an alignment extending outside the treelet translation pair. Therefore, those two enumerated treelets of size 1 are discarded.
P(pos=+1) given that Equation. 1
part-of-speech (POS) of the word aligned to this word=
POS of the word aligned to parent of this word=Verb
P(challenge(fatigué)=win)|same features as in Eq. 1. Eq. 3
L←0; a sorted list of translations
R←roots of input subtrees not covered by p
let x[r]← GetNBestTranslations(r)
T ← target subtree interleaving Q′
Score=λ1 log(channel model probability)+
λ2 log(order model probability)+
λ3 log(agreement model probability)+
λ4 log(target LM probability) Eq. 4
return Order {best}
In accordance with another embodiment of the present invention, decoder 608 is not implemented as a dynamic programming decoder, but is instead implemented using the A * search. The A * search technique is well known and one exemplary discussion of it is set out in Och et al., AN EFFICIENT A * SEARCH ALGORITHM FOR STATISTICAL MACHINE TRANSLATION, in ACL 2001: Data-Driven Machine Translation Workshop, Toulouse France, pp. 55-62 (July 2001).
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.
2. The method of claim 1, wherein each child node of a parent node is considered to be connected with other child nodes of the parent node.
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 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.
6. The system of claim 5 wherein each child node of a parent node is considered to be connected with other child nodes of the parent node, and extract well formed treelet translation pairs from the possible source treelets and corresponding aligned portions of the target language dependency structure.
7. The system of claim 5 and further comprising:
a data store storing the extracted treelet translation pairs.
8. The system of claim 5 wherein the source language dependency structures each represent a source language text fragment.
9. The system of claim 8 wherein the treelet translation pair extractor is configured to enumerate connected sets of source nodes in the source language dependency structure regardless of whether they represent discontiguous words in the source language text fragment.
10. The system of claim 5 wherein the source language dependency structure comprises a source language dependency tree, and wherein the treelet pair extractor is configured to enumerate connected sets of nodes that represent a non-linear branch in the source language dependency tree.
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.
12. The hardware computer readable medium of claim 11 wherein each child node of a parent node is considered to be connected to other child nodes of the parent node.
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.
15. The hardware computer readable medium of claim 13, wherein enumerating comprises enumerating connected sets of source nodes in the source language dependency structure as possible source treelets such that a plurality of possible source treelets are enumerated for the source language dependency structure, and wherein extracting comprises extracting well formed treelet translation pairs from the possible source treelets and aligned portions of a corresponding target language dependency structure, the well formed treelet translation pairs comprising individual ones of the possible source treelets that are selected based on whether a lexical item represented by a node in the selected source treelet has an alignment in another one of the plurality of possible source treelets.
16. The hardware computer readable medium of claim 11 wherein the method further comprises:
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:
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.
US12499379 2004-11-04 2009-07-08 Extracting treelet translation pairs Active 2025-06-30 US8082143B2 (en)
US11014492 US7577562B2 (en) 2004-11-04 2004-12-16 Extracting treelet translation pairs
US12499379 US8082143B2 (en) 2004-11-04 2009-07-08 Extracting treelet translation pairs
US11014492 Continuation US7577562B2 (en) 2004-11-04 2004-12-16 Extracting treelet translation pairs
US20090271177A1 true US20090271177A1 (en) 2009-10-29
US8082143B2 true US8082143B2 (en) 2011-12-20
US8180624B2 (en) * 2007-09-05 2012-05-15 Microsoft Corporation Fast beam-search decoding for phrasal statistical machine translation
US5477450A (en) 1993-02-23 1995-12-19 International Business Machines Corporation Machine translation method and apparatus
WO2003083708A2 (en) 2002-03-28 2003-10-09 British Telecommunications Public Limited Company Machine translation
US20050171757A1 (en) * 2002-03-28 2005-08-04 Appleby Stephen C. Machine translation
Arul Menezes et al., A best-first alignment algorithm for automatic extraction of transfer mappings from bilingual corpora. Proceedings of the Workshop on Data-driven Machine Translation, 39, 2001.
Chinese Application No. 200510108982.7 Decision on Rejection dated Feb. 6, 2009. 10 pages.
Chinese First Office Action. Application No. 200510108982.7, dated May 9, 2008.
Chinese Patent Application No. 200510108982.7, Second Office Action mailed Apr. 28, 2011. 19 pages.
Decision on Rejection of Chinese patent application No. 200510108982.7, dated Feb. 6, 2009.
EP Search Report, Application No. 05108799.7-1527, dated May 22, 2008. 15 pages.
European Patent Application No. 05 108 799.7 Examination Report dated Jun. 3, 2009. 5 pages.
Extended Search Report, European Patent Application No. 05108799.7-1527, dated Sep. 22, 2008.
Hudson R., Word Grammar, basil Blackwell, Oxford, 1984. 8 pages.
Partial Search Report, European Patent Application No. 05108799.7-1527, dated Jun. 25, 2008.
Rada Mihalcea et al., An evaluation exercise for word alignment. In Rada Mihalcea and Ted Pederson, editors, HLT-NAACL 2003 Workshop: Building and Using Parallel Texts: Data Driven Machine Translation and Beyond, pp. 1-10, Edmondton, Alberta, Canada, May 31, 2003. Association for Computational Linguistics.
Sato, S. et al., "Toward Memory-Based Translation," Proc. of Coling. Aug. 20, 1990, pp. 247-252.
Uchimoto K. et al. Word Order Acquisition from Corpora, Coling 2000: 871-877. 7 pages.
Watanabe, H. et al., "Finding Structural Correspondences from Bilingual Parsed Corpus for Corpus-based Translation " Proc. of MT Summit VIII-2001, pp. 906-912.
US7200550B2 (en) 2007-04-03 grant