Projecting dependencies to generate target language dependency structure

• US 7,200,550 B2
• Filed: 12/16/2004
• Issued: 04/03/2007
• 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.
• Primary Examiner(s): Dorvil; Richemond
• Assistant Examiner(s): Vo; Huyen X.
• Application Number:
  US11/014,108
• Publication Number:
  US 20060111896A1
• Time in Patent Office: 838 Days
• Field of Search: 704/1, 704/2, 704/4, 704/5, 704/7, 704/8, 704/9, 704/10, 704/251, 704/257, 704/270, 704/277, 364/419.02
• US Class Current: 704/10
• 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 for generating a target language dependency structure, the method comprising:

accessing a training data corpus having a plurality of pairs of parallel text fragments, each pair of parallel text fragments comprising a source language text fragment and a corresponding target language text fragment;

obtaining an aligned structure in which lexical items in a source language dependency structure, generated based on a source language text fragment, are aligned with lexical items in a corresponding target language text fragment; and

projecting dependencies from lexical items in the source language dependency structure to lexical items in the target language text fragment to obtain the target language dependency structure, wherein the target language dependency structure comprises a target language dependency tree and wherein the dependency projection component is configured to re-adjust the target language dependency structure by identifying a node in the target language dependency tree that is out of order, and re-attaching the identified node at a lowest level in the target language dependency tree that yields a target language string with lexical items in the same order that they appear in the target language text fragment.

2. The method of claim 1 wherein projecting dependencies comprises:

determining whether the target language dependency structure is properly indicative of the target language text fragment; and

if not, adjusting the target language dependency structure so it is properly indicative of the target language text fragment.

3. The method of claim 2 wherein determining comprises:

reading the target language dependency structure to generate a target language text string; and

determining whether the lexical items in the target language text string are in a different order than they appear in the target language text fragment.

4. The method of claim 3 wherein adjusting the target language dependency structure comprises:

re-arranging the target language dependency structure until lexical items in the target language text string read from the target language dependency structure are the same order that they appear in the target language text fragment.

5. The method of claim 1 wherein obtaining an aligned structure comprises:

parsing the source language text fragment to obtain a source language dependency structure;

segmenting the corresponding target language text fragment into lexical items; and

aligning lexical items in the source language dependency structure with lexical items in the target language text fragment.

6. The method of claim 5 wherein projecting comprises:

when a lexical item in the source language dependency structure is not aligned with a lexical item in the target language text fragment, then projecting no dependency from the unaligned lexical item in the source language dependency structure to the target language text fragment.

7. The method of claim 1 wherein a dependency in the source language dependency structure is between first and second source lexical items in the source language dependency structure and the first and second source lexical items are aligned with first and second target lexical items in the target language text fragment, respectively, and wherein projecting comprises:

assigning the dependency between the first and second source lexical items to the first and second target lexical items.

8. The method of claim 1 wherein a lexical item in the source language dependency structure is aligned with a plurality of lexical items in the target language text fragment, and wherein projecting comprises:

identifying a parent node for the plurality of lexical items in the target language dependency structure;

identifying a right-most one of the plurality of lexical items in the target language text fragment;

assigning the right-most lexical item as dependent from the parent node; and

assigning a remainder of the plurality of lexical items in the target language text fragment as dependent from the right-most lexical item.

9. The method of claim 1 wherein an unaligned lexical item in the target language text fragment is unaligned to a lexical item in the source language dependency structure, and wherein projecting comprises:

identifying a lexical item located proximate the unaligned lexical item in the target language text fragment; and

assigning the unaligned lexical item as dependent from the identified lexical item.

10. The method of claim 9 wherein identifying comprises:

identifying one lexical item, of a set of target language lexical items adjacent the unaligned lexical item in the target language text fragment, that is lowest on the target language dependency structure; and

assigning the unaligned lexical item as dependent from the identified lexical item.

11. The method of claim 1 and further comprising:

using at least a portion of the target language dependency structure in a machine translation system to translate a source language input into a target language output.

12. The method of claim 1, wherein, when a plurality of lexical items in the source language dependency structure are aligied with one lexical item in the target language text fragment, then projecting comprises:

identifying one of the plurality of lexical items in the source language dependency structure that is highest in the source language dependency structure; and

assigning a dependency associated with the identified one of the plurality of items in the source language dependency structure to the one lexical item in the target language text fragment.

13. A system for generating a target language dependency structure, the system comprising:

a corpus processing system configured to obtain an aligned structure in which lexical items in a source language dependency structure, indicative of a source language training data text fragment, are aligned with lexical items in a corresponding training data target language text fragment that is a translation of the source language text fragment; and

a dependency projection component configured to project dependencies from lexical items in the source language dependency structure to the lexical items in the target language text fragment to obtain the target language dependency structure, wherein the target language dependency structure comprises a target language dependency tree and wherein the dependency projection component is configured to re-adjust the target language dependency structure by identifying a node in the target language dependency tree that is out of order, and re-attaching the identified node at a lowest level in the target language dependency tree that yields a target language string with lexical items in the same order that they appear in the target language text fragment.

14. The system of claim 13 and further comprising:

a training data corpus having a plurality of pairs of parallel text fragments, each pair of parallel text fragments comprising a source language text fragment and a corresponding target language text fragment.

15. The system of claim 13 wherein the dependency projection component is configured to determine whether the target language dependency structure is properly indicative of the target language text fragment, and if not, adjust the target language dependency structure so it is properly indicative of the target language text fragment.

16. The system of claim 15 wherein the dependency projection component is configured to determine whether the target language dependency structure is properly indicative of the target language text fragment by reading the target language dependency structure to generate a target language text string, and determine whether the lexical items in the target language text string are in a different order than they appear in the target language text fragment.

17. The system of claim 16 wherein the dependency projection component is configured to adjust the target language dependency structure by re-arranging the target language dependency structure until lexical items in the target language text string read from the target language dependency structure are the same order that they appear in the target language text fragment.

18. The system of claim 13 wherein the corpus processing system comprises:

a parser configured to parse the source language text fragment to obtain a source language dependency structure.

19. The system of claim 13 wherein the corpus processing system comprises:

a segmenter configured to segment target language text fragments into lexical items.

20. The system of claim 13 wherein the corpus processing system comprises:

an alignment component configured to align lexical items in the source language dependency structure with lexical items in the target language text fragment.

21. A computer readable medium storing computer readable instructions which, when executed by a computer, cause a computer to perform a method for generating a target language dependency structure, the method comprising:

accessing a training data corpus having a plurality of pairs of parallel text fragments, each pair of parallel text fragments comprising a source language text fragment and a corresponding target language text fragment;

obtaining an aligned structure in which lexical items in a source language dependency structure, generated based on a source language text fragment, are aligned with lexical items in a corresponding target language text fragment; and

projecting dependencies from lexical items in the source language dependency structure to the aligned lexical items in the target language text fragment to obtain the target language dependency structure, wherein a lexical item in the source language dependency structure is aligned with a plurality of lexical items in the target language text fragment, and wherein projecting comprises;

identifying a parent node for the plurality of lexical items in the target language dependency structure;

identifying a right-most one of the plurality of lexical items in the target language text fragment;

assigning the right-most lexical item as dependent from the parent node; and

assigning a remainder of the plurality of lexical items in the target language text fragment as dependent from the right-most lexical item;

determining whether the target language dependency structure is properly indicative of the target language text fragment; and

if not, adjusting the target language dependency structure so it is properly indicative of the target language text fragment.

22. The computer readable medium of claim 21 wherein determining comprises:

reading the target language dependency structure to generate a target language text string; and

determining whether the lexical items in the target language text string are in a different order than they appear in the target language text fragment.

23. The computer readable medium of claim 22 wherein adjusting the target language dependency structure comprises:

re-arranging the target language dependency structure until lexical items in the target language text string read from the target language dependency structure are the same order that they appear in the target language text fragment.

24. The computer readable medium of claim 23 wherein re-arranging comprises:

identifying a node in the target language dependency tree that is out of order; and

re-attaching the identified node at a lowest level in the target language dependency tree that yields a target language string with lexical items in the same order that they appear in the target language text fragment.

25. The computer readable medium of claim 21 wherein obtaining an aligned structure comprises:

parsing the source language text fragment to obtain a source language dependency structure;

segmenting the corresponding target language text fragment into lexical items; and

aligning lexical items in the source language dependency structure with lexical items in the target language text fragment.

26. The computer readable medium of claim 25 wherein projecting comprises:

when an unaligned lexical item in the source language dependency structure is not aligned with a lexical item in the target language text fragment, then projecting no dependency from the unaligned lexical item in the source language dependency structure to the target language text fragment.

27. The computer readable medium of claim 21 wherein a dependency in the source language dependency structure is between first and second source lexical items in the source language dependency structure and the first and second source lexical items are aligned with first and second target lexical items in the target language text fragment, respectively, and wherein projecting comprises:

assigning the dependency between the first and second source lexical items to the first and second target lexical items.

28. The computer readable medium of claim 21 wherein an unaligned lexical item in the target language text fragment is unaligned to a lexical item in the source language dependency structure, and wherein projecting comprises:

identifying a lexical item located proximate the unaligned lexical item in the target language text fragment; and

assigning the unaligned lexical item as dependent from the identified lexical item.

29. The computer readable medium of claim 28 wherein identifying comprises:

identifying one lexical item, of a set of target language lexical items adjacent the unaligned lexical item in the target language text fragment, that is lowest on the target language dependency structure; and

assigning the unaligned lexical item as dependent from the identified lexical item.

30. The computer readable medium of claim 21 a plurality of lexical items in the source language dependency structure are aligned with one lexical item in the target language text fragment, and wherein projecting comprises:

identifying one of the plurality of lexical items in the source language dependency structure that is highest in the source language dependency structure; and

assigning a dependency associated with the identified one of the plurality of items in the source language dependency structure to the one lexical item in the target language text fragment.