Machine translation using language order templates

• US 8,150,677 B2
• Filed: 06/26/2008
• Issued: 04/03/2012
• Est. Priority Date: 06/26/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Menezes, Arul A., Quirk, Christopher B.
• Primary Examiner(s): Vo, Huyen X.
• Application Number:
  US12/146,531
• Publication Number:
  US 20090326911A1
• Time in Patent Office: 1,377 Days
• Field of Search: 704 1- 10, 704/257, 704/277, 704/270, 704/270.1, 704251-255
• US Class Current: 704/2
• CPC Class Codes: G06F 40/45 Example-based machine translation; Alignment
• CPC Class Codes: G06F 40/55 Rule-based translation

Abstract

Many machine translation scenarios involve the generation of a language translation rule set based on parallel training corpuses (e.g., sentences in a first language and word-for-word translations into a second language.) However, the translation of a source corpus in a source language to a target corpus in a target language involves at least two aspects: selecting elements of the target language to match the elements of the source corpus, and ordering the target elements according to the semantic organization of the source corpus and the grammatic rules of the target language. The breadth of generalization of the translation rules derived from the training may be improved, while retaining contextual information, by formulating language order templates that specify orderings of small sets of target elements according to target element types. These language order templates may be represented with varying degrees of association with the alignment rules derived from the training in order to improve the scope of target elements to which the ordering rules and alignment rules may be applied.

Claims

1. A method of generating a language translation rule set comprising at least one language order template using at least one source training corpus in a source language aligned with a parallel target training corpus in a target language on a computer having a processor, the method comprising:

executing on the processor instructions configured to;

for respective parallel training corpora;

parse the source corpus to identify element types for respective source training corpus elements,

generate a parse tree mapping source training corpus elements to parallel target training corpus elements,

generate at least one candidate treelet translation pair based on the parse tree, and

generate at least one candidate order template based on the parse tree and the element types;

add at least one treelet translation pair from the candidate treelet translation pairs to the language translation rule set; and

add at least one order template from the candidate order templates to the language translation rule set.

2. The method of claim 1, the instructions configured to:

upon identifying an ordering of element types comprising at least one element type specified by a first language order template and at least one unspecified element type;

generate a second language order template comprising the first language order template and including in the ordering the unspecified element types, and

add the second language order template to the language translation rule set.

3. The method of claim 1, the instructions configured to:

generate an alignment model of the source language and the target language according to the source training corpus and the parallel target training corpus, and

add the alignment model to the language translation rule set.

4. The method of claim 3, the alignment model comprising at least one dependency treelet aligning source elements with target elements.

5. The method of claim 1, the instructions configured to:

identify element types for respective source elements of the source language;

generate at least one source language order template specifying an ordering of at least two element types according to the source training corpus; and

add the source language order template to the language translation rule set.

6. The method of claim 5, the instructions configured to:

upon failing to identify element types of respective target elements of the target language;

generate at least one language order template comprising the ordering of target elements aligned with source elements specified in at least one source language order template, and

add the at least one language order template to the language translation rule set.

7. A method of translating a source corpus in a source language into a target language using a language translation rule set comprising at least one treelet translation pair and at least one language order template on a computer having a processor, the method comprising:

executing on the processor instructions configured to;

parse the source corpus to identify element types for respective source corpus elements;

generate a parse tree mapping the source corpus elements;

select at least one treelet translation pair mapping at least one source corpus element to at least one target corpus element;

select language order templates corresponding to unordered source corpus elements; and

generate a target corpus according to the parse tree, selected treelet translation pairs, and selected language order templates.

8. The method of claim 7:

the language translation rule set comprising an alignment model of the source language and the target language, and

the selecting comprising;

selecting target elements aligned with source elements of the source corpus according to the alignment model.

9. The method of claim 8:

the alignment model comprising at least one dependency treelet aligning source elements with target elements, and

the selecting comprising;

identifying at least one dependency treelet matching the source elements, and

selecting the target elements of the dependency treelet.

10. The method of claim 9, the choosing comprising:

choosing at least one language order template specifying an ordering in the target language of at least two element types of the target elements and specifying at least one element type for respective target elements of the dependency treelet.

11. The method of claim 8:

the alignment model specifying an alignment probability between at least one source element and at least one target element; and

the selecting comprising;

selecting target elements aligned with source elements that together present acceptable alignment probabilities according to the alignment model.

12. The method of claim 7, the language translation rule set comprising at least one source language order template.

13. The method of claim 12, the selecting comprising:

identifying element types of the source elements;

verifying identified element types against at least one source language order template matching the element types of the source elements of the source corpus; and

selecting target elements of element types matching the element types of the source elements.

14. The method of claim 12, the choosing comprising:

upon failing to choose a language order template specifying an ordering in the target language of at least two element types of the target elements;

identify source elements aligned with the target elements;

choose at least one source language order template specifying an ordering in the source language of at least two element types of the source elements; and

choose at least one language order template comprising the ordering of target elements aligned with the source elements specified in the least one chosen source language order template.

15. The method of claim 7, the instructions configured to:

upon identifying an ordering of target element types not specified by a language order template;

generate a new language order template specifying an ordering of the target element types in the target language, and

add the new language order template to the language translation rule set.

16. The method of claim 7, the choosing comprising:

choosing a first language order template specifying an ordering in the target language of at least two element types of the target elements, and

recursively choosing a language order template specifying an ordering in the target language of;

at least one element type of at least one unordered target element, and

at least one element type of at least one ordered target element.

17. The method of claim 16, the recursively choosing performed according to a beam search.

18. The method of claim 17, the beam search constrained, for respective chosen language order templates, by a maximum of recursively evaluated language order templates.

19. The method of claim 17:

respective language order templates comprising an ordering probability, and

the beam search constrained by at least one of;

a minimum ordering probability for recursively evaluated language order templates, and

a maximum of recursively evaluated language order templates before ordering the target elements according to the ordering specified by the at least one chosen language order template together having an acceptable ordering probability.

20. A nonvolatile memory comprising processor-executable instructions that, when executed by a processor of a device, cause the device to translate a source corpus in a source language into a target language using a language translation rule set comprising at least one treelet translation pair and at least one language order template by:

parsing the source corpus to identify element types for respective source corpus elements;

generating a parse tree mapping the source corpus elements;

selecting at least one treelet translation pair mapping at least one source corpus element to at least one target corpus element;

selecting language order templates corresponding to unordered source corpus elements; and

generating a target corpus according to the parse tree, selected treelet translation pairs, and selected language order templates.