Language translation apparatus and method using context-based translation models

• US 5,510,981 A
• Filed: 10/28/1993
• Issued: 04/23/1996
• Est. Priority Date: 10/28/1993
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Berger, Adam L., Brown, Peter F., Mercer, Robert L., Della Pietra, Stephen A., Della Pietra, Vincent J., Kehler, Andrew S.
• Primary Examiner(s): Huntley, David M.
• Assistant Examiner(s): Poinvil, Frantzy
• Application Number:
  US08/144,913
• Time in Patent Office: 908 Days
• Field of Search: 364/419.02, 364/419.08, 364/419.16, 364/200 MS File, 381/43, 381/51
• US Class Current: 704/2
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models
• CPC Class Codes: G06F 40/45 Example-based machine translation; Alignment

Abstract

An apparatus for translating a series of source words in a first language to a series of target words in a second language. For an input series of source words, at least two target hypotheses, each including a series of target words, are generated. Each target word has a context comprising at least one other word in the target hypothesis. For each target hypothesis, a language model match score including an estimate of the probability of occurrence of the series of words in the target hypothesis. At least one alignment connecting each source word with at least one target word in the target hypothesis is identified. For each source word and each target hypothesis, a word match score including an estimate of the conditional probability of occurrence of the source word, given the target word in the target hypothesis which is connected to the source word and given the context in the target hypothesis of the target word which is connected to the source word. For each target hypothesis, a translation match score including a combination of the word match scores for the target hypothesis and the source words in the input series of source words. A target hypothesis match score including a combination of the language model match score for the target hypothesis and the translation match score for the target hypothesis. The target hypothesis having the best target hypothesis match score is output.

Claims

1. An apparatus for translating a series of source words in a first language to a series of target words in a second language different from the first language, said apparatus comprising:

means for inputting said series of source words;

means for generating at least two target hypotheses, each target hypothesis comprising said series of target words selected from a vocabulary of words in the second language, each target word having a context comprising at least one other word in the target hypothesis;

means for generating, for each target hypothesis, a language model match score comprising an estimate of the probability of occurrence of the series of words in the target hypothesis;

means for identifying at least one alignment between the input series of source words and each target hypothesis, the alignment connecting each source word with at least one target word in the target hypothesis;

means for generating, for each source word and each target hypothesis, a word match score comprising an estimate of the conditional probability of occurrence of the source word, given the target word in the target hypothesis which is connected to the source word and given the context of the target word in the target hypothesis which is connected to the source word;

means for generating, for each target hypothesis, a translation match score comprising a combination of the word match scores for the target hypothesis and the source words in the input series of source words;

means for generating a target hypothesis match score for each target hypothesis, each target hypothesis match score comprising a combination of the language model match score for the target hypothesis and the translation match score for the target hypothesis; and

means for outputting the target hypothesis having the best target hypothesis match score.

2. An apparatus as claimed in claim 1, characterized in that each target hypothesis comprises a series of target words selected from a vocabulary comprising words in the second language and a null word representing the absence of a word.

3. An apparatus as claimed in claim 2, characterized in that:

the means for identifying at least one alignment comprises means for identifying two or more alignments between the input series of source words and each target hypothesis, each alignment connecting each source word with at least one target word in the target hypothesis;

the word match score generator comprises means for generating, for each source word and each alignment and each target hypothesis, a word match score comprising an estimate of the conditional probability of occurrence of the source word, given the target word in the target hypothesis which is connected to the source word and given the context of the target word in the target hypothesis which is connected to the source word;

the translation match score generator comprises means for generating, for each target hypothesis, a translation match score comprising a combination of the word match scores for the target hypothesis and the alignments and the source words in the input series of source words.

4. An apparatus as claimed in claim 2, characterized in that:

the input means comprises means for transforming the input series of source words into a series of transformed source words;

the alignment means comprises means for identifying at least one alignment between the series of transformed source words and each target hypothesis, the alignment connecting each transformed source word with at least one target word in the target hypothesis;

the word match score generator comprises means for generating, for each transformed source word and each target hypothesis, a word match score comprising an estimate of the conditional probability of occurrence of the transformed source word, given the target word in the target hypothesis which is connected to the transformed source word and given the context of the target word in the target hypothesis which is connected to the transformed source word;

the translation match score generator comprises means for generating for each target hypothesis, a translation match score comprising a combination of the word match scores for the target hypothesis and the transformed source words; and

the output means comprises means for synthesizing a series of output words from the target hypothesis having the best target hypothesis match score, and means for outputting the synthesized output words.

5. An apparatus as claimed in claim 2, characterized in that:

the translation match score for a target hypothesis comprises the product of the word match scores for the target hypothesis and the source words in the input series of source words; and

the target hypothesis match score for a target hypothesis comprises the product of the language model match score for the target hypothesis multiplied by the translation match score for the target hypothesis.

6. An apparatus as claimed in claim 2, characterized in that:

the context of the target word in the target hypothesis which is connected to a source word is contained in at least one of two or more context classes; and

the estimated conditional probability of occurrence of the source word, given the target word in the target hypothesis which is connected to the source word and given the context of the target word which is connected to the source word, comprises at least one function having a value dependent on the class containing the context of the target word which is connected to the source word.

7. An apparatus as claimed in claim 2, characterized in that:

the context of the target word in the target hypothesis which is connected to a source word comprises at least one word having a part of speech in the target hypothesis; and

the estimated conditional probability of occurrence of the source word, given the target word in the target hypothesis which is connected to the source word and given the context of the target word which is connected to the source word, comprises at least one function having a value dependent on the part of speech in the target hypothesis of at least one word in the context of the target word which is connected to the source word.

8. An apparatus as claimed in claim 2, characterized in that:

the context of the target word in the target hypothesis which is connected to a source word comprises at least one word having an identity; and

the estimated conditional probability of occurrence of the source word, given the target word in the target hypothesis which is connected to the source word and given the context of the target word which is connected to the source word, comprises at least one function having a value dependent on the identity of at least one word in the context of the target word which is connected to the source word.

9. An apparatus as claimed in claim 2, characterized in that the means for outputting the target hypothesis having the best match score comprises a display.

10. An apparatus as claimed in claim 2, characterized in that the input means comprises a keyboard.

11. An apparatus as claimed in claim 2, characterized in that the input means comprises a computer disk drive.

12. An apparatus as claimed in claim 2, characterized in that the input means comprises a computer tape drive.

13. A computer-implemented method of translating a series of source words in a first language to a series of target words in a second language different from the first language, said method comprising:

inputting a series of source words;

generating at least two target hypotheses, each target hypothesis comprising said series of target words selected from a vocabulary of words in the second language, each target word having a context comprising at least one other word in the target hypothesis;

generating, for each target hypothesis, a language model match score comprising an estimate of the probability of occurrence of the series of words in the target hypothesis;

identifying at least one alignment between the input series of source words and each target hypothesis, the alignment connecting each source word with at least one target word in the target hypothesis;

generating, for each source word and each target hypothesis, a word match score comprising an estimate of the conditional probability of occurrence of the source word, given the target word in the target hypothesis which is connected to the source word and given the context of the target word in the target hypothesis which is connected to the source word;

generating, for each target hypothesis, a translation match score comprising a combination of the word match scores for the target hypothesis and the source words in the input series of source words;

generating a target hypothesis match score for each target hypothesis, each target hypothesis match score comprising a combination of the language model match score for the target hypothesis and the translation match score for the target hypothesis; and

outputting the target hypothesis having the best target hypothesis match score.

14. A method as claimed in claim 13, characterized in that each target hypothesis comprises a series of target words selected from a vocabulary comprising words in the second language and a null word representing the absence of a word.

15. A method as claimed in claim 14, characterized in that:

the step of identifying at least one alignment comprises identifying two or more alignments between the input series of source words and each target hypothesis, each alignment connecting each source word with at least one target word in the target hypothesis;

the step of generating a word match score comprises generating, for each source word and each alignment and each target hypothesis, a word match score comprising an estimate of the conditional probability of occurrence of the source word, given the target word in the target hypothesis which is connected to the source word and given the context of the target word in the target hypothesis which is connected to the source word;

the step of generating a translation match score comprises generating, for each target hypothesis, a translation match score comprising a combination of the word match scores for the target hypothesis and the alignments and the source words in the input series of source words.

16. A method as claimed in claim 14, characterized in that:

the step of inputting comprises the step of transforming the input series of source words into a series of transformed source words;

the step of aligning comprises identifying at least one alignment between the series of transformed source words and each target hypothesis, the alignment connecting each transformed source word with at least one target word in the target hypothesis;

the step of generating a word match score comprises generating, for each transformed source word and each target hypothesis, a word match score comprising an estimate of the conditional probability of occurrence of the transformed source word, given the target word in the target hypothesis which is connected to the transformed source word and given the context of the target word in the target hypothesis which is connected to the transformed source word;

the step of generating a translation match score comprises generating, for each target hypothesis, a translation match score comprising a combination of the word match scores for the target hypothesis and the transformed source words; and

the step of outputting comprises the step of synthesizing a series of output words from the target hypothesis having the best target hypothesis match score.

17. A method as claimed in claim 14, characterized in that:

the translation match score for a target hypothesis comprises the product of the word match scores for the target hypothesis and the source words in the input series of source words; and

the target hypothesis match score for a target hypothesis comprises the product of the language model match score for the target hypothesis multiplied by the translation match score for the target hypothesis.

18. A method as claimed in claim 14, characterized in that:

the context of the target word in the target hypothesis which is connected to a source word is contained in at least one of two or more context classes; and

the estimated conditional probability of occurrence of the source word, given the target word in the target hypothesis which is connected to the source word and given the context of the target word which is connected to the source word, comprises at least one function having a value dependent on the class containing the context of the target word which is connected to the source word.

19. A method as claimed in claim 14, characterized in that:

the context of the target word in the target hypothesis which is connected to a source word comprises at least one word having a part of speech in the target hypothesis; and

the estimated conditional probability of occurrence of the source word, given the target word in the target hypothesis which is connected to the source word and given the context of the target word which is connected to the source word, comprises at least one function having a value dependent on the part of speech in the target hypothesis of at least one word in the context of the target word which is connected to the source word.

20. A method as claimed in claim 14, characterized in that:

the context of the target word in the target hypothesis which is connected to a source word comprises at least one word having an identity; and

the estimated conditional probability of occurrence of the source word, given the target word in the target hypothesis which is connected to the source word and given the context of the target word which is connected to the source word, comprises at least one function having a value dependent on the identity of at least one word in the context of the target word which is connected to the source word.

21. A method as claimed in claim 14, characterized in that the step of outputting the target hypothesis having the best match score comprises displaying the target hypothesis having the best match score.