Example based machine translation system

• US 20040002848A1
• Filed: 06/28/2002
• Published: 01/01/2004
• Est. Priority Date: 06/28/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Huang, Chang Ning, Wang, Wei, Zhou, Ming, Huang, Jin-Xia
• Granted Patent: US 7,353,165 B2
• Time in Patent Office: Days
• US Class Current: 704/2
• CPC Class Codes: G06F 40/45 Example-based machine translation; Alignment

Abstract

The present invention performs machine translation by matching fragments of a source language sentence to be translated to source language portions of an example in example base. When all relevant examples have been identified in the example base, the examples are subjected to phrase alignment in which fragments of the target language sentence in each example are aligned against the matched fragments of the source language sentence in the same example. A translation component then substitutes the aligned target language phrases from the matched examples for the matched fragments in the source language sentence.

Claims

1. A method of performing machine translation of a source language (SL) input to a translation output in a target language (TL), comprising:

matching fragments of the SL input to SL fragments of examples in an example base;

identifying all matched blocks in the SL input as blocks of terms in the SL input that are matched by one or more SL fragments in an example;

selecting block combinations of the matched blocks to cover one or more fragments of the SL input;

for each block in the selected block combinations, identifying an example associated with the block;

aligning TL portions of the identified example with SL portions of the identified example that match the one or more fragments of the SL input; and

providing the translation output based on the aligned portions.

2. The method of claim 1 wherein providing the translation output comprises:

outputting a plurality of possible translation outputs.

3. The method of claim 2 and further comprising:

calculating a confidence measure for each translation output.

4. The method of claim 3 wherein calculating comprises:

calculating the confidence measure as a translation confidence level as follows;

$\begin{array}{cc}\begin{array}{c}\mathrm{ConL}=c_1\times <br><br>\log <br><br>\left(\mathrm{AlignCon}\times <br><br>10\right)+c_2\times <br><br>\log <br><br>\left(\mathrm{TransPercent}\times <br><br>10\right)+\\ c_3\times <br><br>\log <br><br>\left(10/\mathrm{Example\_num}\right)+c_4\times <br><br>\log <br><br>\left(10/\mathrm{Valid\_block}<br><br>\mathrm{\_num}\right)\end{array}& \left(7\right)\\ \begin{array}{c}\mathrm{AlignCon}=\underset{\begin{array}{c}{w}_i\in <br><br>\mathrm{PhrSL},w_j\in <br><br>\mathrm{PhrTL}\\ \mathrm{i\dots <br><br>j};<br><br>\mathrm{are}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{connected}\end{array}}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Conf}<br><br>\left(C_{\mathrm{ij}}\right)/<br><br>\mathrm{PhrTL}<br><br>\\ \left(0\le <br><br>\mathrm{AlignCon}\le <br><br>1,0\le <br><br>\mathrm{TransPercent}\le <br><br>1,\underset{i=1}{\overset{4}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>c_i=1\right)\end{array}& \left(8\right)\end{array}$

where,

ConL;

is the translation confidence level;

C_1,C2, . . . , C₄;

are constants,

AlignCon;

is an alignment confidence level;

TransPercent;

is a weighted translation percentage;

Example₁₃ num;

is an employed example number identifying the identified example;

Valid_block_num;

is a fragment number in a possible TL

Translation under consideration;

PhrSL;

is a SL phrase that relates to a given input string;

PhrTL;

is a TL correspondence in the possible translation of the SL input;

|PhrTL|;

is a word number of PhrTL;

C_{i j};

is a connection between SL word i and TL word j; and

Conf (C_{i . . . j});

is the translation confidence level of word Alignment.

5. The method of claim 3 and further comprising:

identifying portions of the translation output that require a user'"'"'s attention.

6. The method of claim 1 wherein matching fragments of the SL input to fragments of examples comprises:

identifying bi-terms in the SL input; and

accessing a bi-term index of the example base that includes example identifiers identifying examples that contain indexed bi-terms.

7. The method of claim 6 wherein accessing a bi-term index comprises:

accessing a bi-term index of the example base that includes word position information indicative of a word position in the example where the bi-term resides.

8. The method of claim 7 wherein accessing a bi-term index comprises:

accessing a bi-term index of the example base that includes a score indicative of a term frequency/inverse document frequency (TF/IDF) score for the bi-term in the example.

9. The method of claim 8 wherein accessing a bi-term index comprises:

accessing a bi-term index of the example base that includes a corpus score indicative of a representative TF/IDF score for the bi-term across the example base.

10. The method of claim 1 wherein identifying an example associated with a block comprises:

calculating a block score corresponding to each example containing the block; and

identifying the example associated with the block based on the block score.

11. The method of claim 10 wherein calculating a block score comprises:

calculating the block score as follows;

$\begin{array}{cc}{\mathrm{similarity}}_j=\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{TFIDF}}_{\mathrm{kj}}& \left(5\right)\end{array}$

Where,

K=a total number of common terms included both in example j and the SL input;

TFIDF_kj=Term k'"'"'s TF/IDF weight in example j; and

Similaritty_j=matching weight between the example j and the SL input.

12. The method of claim 1 wherein aligning TL portions of the example with the SL portions comprises:

performing word alignment to identify anchor alignment points between the SL portion and the TL portion of the example;

finding all continuous alignments between the TL portion and the SL portion based on the anchor alignment points; and

finding all non-continuous alignments between the TL portion and the SL portion based on the anchor alignment points.

13. The method of claim 1 wherein selecting block combinations comprises:

calculating a block combination score for different combinations of the identified blocks; and

identifying N best block combinations based on the block combination scores.

14. The method of claim 13 wherein calculating a block combination score comprises:

15. A method of performing machine translation of a source language (SL) input to a translation output in a target language (TL), comprising:

selecting examples, from an example base, that correspond to fragments of the SL input;

aligning TL portions of the selected examples with SL portions that correspond to the fragments of the SL input by, for each example;

performing word alignment to identify anchor alignment points between the SL portion and the TL portion;

finding continuous alignments between the TL portion and the SL portion based on the anchor alignment points;

finding non-continuous alignments between the TL portion and the SL portion; and

translating the SL input to the translation output from the continuous and non-continuous alignments.

16. The method of claim 15 comprises:

generating a plurality of translation outputs based on the continuous and non-continuous alignments;

calculating a score for each translation out put; and

selecting at least one translation output.

17. The method of claim 16 and further comprising:

calculating a confidence measure for the selected translation output; and

identifying one or more portions of the translation output that have a confidence measure below a threshold level.

18. The method of claim 15 wherein finding continuous alignments comprises:

obtaining SL boundary information indicative of positions of words in the SL input that define a boundary for a fragment of the SL portion to be aligned.

19. The method of claim 18 wherein finding continuous alignments further comprises:

obtaining TL boundary information identifying boundary positions of words in the TL portion of the example that are aligned with the SL portion, based on the anchor alignment points, to obtain a minimum possible alignment (MinPA).

20. The method of claim 19 wherein finding continuous alignments further comprises:

identifying a maximum possible alignment (MaxPA) by extending boundaries identified by the TL boundary information until an inconsistent alignment anchor point is reached.

21. The method of claim 20 wherein finding continuous alignments further comprises:

generating all alignments between MinPA and MaxPA, all of which include MinPA.

22. The method of claim 18 wherein finding all non-continuous alignments comprises:

identifying a word set in the TL portion of the example that corresponds to the SL portion to be aligned, based on the anchor alignment points.

23. The method of claim 22 wherein finding all non-continuous alignments further comprises:

identifying a word set in the SL portion of the example that aligns to a portion of the word set in the TL portion but is outside the SL boundary information.

24. The method of claim 23 wherein finding all non-continuous alignments further comprises:

if the word set in the SL portion is continuous, finding all possible continuous alignments for the word set in the SL portion and the TL portion of the example.

25. The method of claim 23 wherein finding all non-continuous alignments further comprises:

removing from the word set in the TL portion the words that align with the words in the SL portion that are outside the SL boundary information to obtain a minimum possible alignment (MinPA).

26. The method of claim 25 wherein finding all non-continuous alignments further comprises:

extending boundaries of MinPA, until an inconsistent alignment anchor point is reached, to obtain a maximum possible alignment (MaxPA).

27. The method of claim 26 wherein finding all non-continuous alignments further comprises:

generating continuous substrings from the TL portion between MinPA and MaxPA, all of which include MinPA.

28. The method of claim 15 wherein performing word alignment comprises:

accessing a bilingual dictionary to obtain dictionary information indicative of word translations between the SL portion and the TL portion of the example.

29. The method of claim 28 wherein word alignment further comprises:

if the TL portion of the example is in a non-segmented language, performing word segmentation on the example.

30. The method of claim 28 wherein word alignment further comprises:

applying a distortion model aligner to align words in the SL portion with words in the TL portion based on word position.

31. The method of claim 30 wherein word alignment further comprises:

accessing a monolingual dictionary to merge characters in the TL portion into words and merge words in the TL portion into phrases.

32. The method of claim 31 wherein word alignment further comprises:

performing statistical alignment between as yet unaligned words in the SL portion and the TL portion.

33. A word alignment system in an example based machine translation system that translates a source language (SL) input to a translation output in a target language (TL) based on examples in an example base, comprising:

a bilingual dictionary aligner accessing a bilingual dictionary to obtain dictionary information indicative of word translations between a SL portion and a TL portion of a selected example;

a distortion model aligner coupled to the bilingual dictionary and configured to align words in the SL portion with words in the TL portion of the selected example based on word position;

a monolingual dictionary aligner coupled to the distortion model aligner and configured to merge characters in the TL portion into words and merge words in the TL portion into phrases; and

a statistical aligner coupled to the monolingual dictionary aligner and configured to perform statistical alignment between as yet unaligned words in the SL portion and the TL portion of the example.

34. The word alignment system of claim 33 and further comprising:

a word segmenter coupled to the bilingual dictionary aligner and configured to perform word segmentation on the example.