Method and system for natural language translation

• US 5,477,451 A
• Filed: 07/25/1991
• Issued: 12/19/1995
• Est. Priority Date: 07/25/1991
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Lai, Jennifer C., Cocke, John, Jelinek, Frederick, Brown, Peter F., Mercer, Robert L., Della Pietra, Stephen A., Della Pietra, Vincent J.
• Primary Examiner(s): Huntley, David M.
• Assistant Examiner(s): Kyle, Charles R.
• Application Number:
  US07/736,278
• Time in Patent Office: 1,608 Days
• Field of Search: 364/419, 364/419.02, 364/419.08, 364/419.16, 381/43, 381/51
• US Class Current: 704/9
• CPC Class Codes: G06F 40/268 Morphological analysis
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models
• CPC Class Codes: G06F 40/49 using very large corpora, e.g. the web
• CPC Class Codes: G06F 40/55 Rule-based translation

Abstract

The present invention is a system for translating text from a first source language into a second target language. The system assigns probabilities or scores to various target-language translations and then displays or makes otherwise available the highest scoring translations. The source text is first transduced into one or more intermediate structural representations. From these intermediate source structures a set of intermediate target-structure hypotheses is generated. These hypotheses are scored by two different models: a language model which assigns a probability or score to an intermediate target structure, and a translation model which assigns a probability or score to the event that an intermediate target structure is translated into an intermediate source structure. Scores from the translation model and language model are combined into a combined score for each intermediate target-structure hypothesis. Finally, a set of target-text hypotheses is produced by transducing the highest scoring target-structure hypotheses into portions of text in the target language. The system can either run in batch mode, in which case it translates source-language text into a target language without human assistance, or it can function as an aid to a human translator. When functioning as an aid to a human translator, the human may simply select from the various translation hypotheses provided by the system, or he may optionally provide hints or constraints on how to perform one or more of the stages of source transduction, hypothesis generation and target transduction.

Claims

1. A method operating on a computer for translating source text from a first language to target text in a second language different from the first language, said method comprising the steps of:

measuring a value of the source text in the firs language and storing the source text in a first memory buffer;

generating the target text in the second language based on a combination of a probability of occurrence of an intermediate structure of text associated with a target hypothesis selected from the second language using a target language model, and a probability of occurrence of the source text given the occurrence of said intermediate structure of text associated with said target hypothesis using a target-to-source translation model; and

performing at least one of a storing operation to save said target text in a second memory buffer and a presenting operation to make said target text available for at least one of a viewing and listening operation using an I/O device.

2. A method according to claim 1, further comprising the step of:

receiving at least one user defined criteria pertaining to the source text to thereby bound the target text, said criteria belonging to the group comprising specification of a noun phrase, specification of subject, specification of verb, a semantic sense of a word or group of words, inclusion of a predetermined word or group of words, and exclusion of a predetermined word or group of words.

3. A method operating on a computer for translating source text from a first language to target in a second language different from the first language, said method comprising the steps of:

receiving the source text in the first language;

generating at least one target hypothesis, each of said target hypotheses comprising text selected from the second language;

estimating, for each target hypothesis, a first probability of occurrence of said text associated with said target hypothesis using a target language model;

estimating, for each target hypothesis, a second probability of occurrence of the source text given the occurrence of said text associated with said target hypothesis using a target-to-source translation model;

combining, for each target hypothesis, said first and second probabilities to produce a target hypothesis match score; and

performing at least one of a storing operation to save and a presenting operation to make available for at least one of a viewing and listening operation, at least one of said target hypotheses according to its associated match score.

4. A method according to claim 3, further comprising the steps of:

generating a list of partial target hypotheses using said target language model and said target-to-source translation model;

extending said partial hypotheses to generate a set of new hypotheses;

determining a match score for at least one of said new hypotheses; and

performing at least one of a storing operation to save and a presenting operation to make available for viewing, at least one of said new hypotheses according to its associated match score.

5. A method according to claim 4, wherein said match score determining step further comprises the steps of:

determining a language model score for each of said partial hypotheses using said target language model;

determining a translation model score for each of said partial hypotheses using said target-to-source translation model; and

determining a combined score of said language and translation model scores for each of said partial hypotheses.

6. A method according to claim 5, wherein said translation model score determining step further comprises at least one of the following steps:

determining a fertility model score for each of said partial hypotheses, said partial hypotheses comprising at least one notion and said fertility model score being proportional to a probability that a notion in the target text will generate a specific number of units of linguistic structure in the source text;

determining a alignment score for each of said partial hypotheses, said alignment score being proportional to a probability that a unit of linguistic structure in the target text will align with one of zero or more units of linguistic structure in the source text;

determining a lexical model score, for each of said partial hypotheses, said lexical model score being proportional to the probability that said units of linguistic structure in the target text of a given partial hypothesis will translate into said units of linguistic structure of said source text;

determining a distortion model score for each of said partial hypotheses, said distortion model score being proportional to the probability that a source unit of linguistic structure will be in a particular position given a position of the target units of linguistic structure that generated it; and

determining a combined score, said combined score being proportional to a product of at leas tone of said fertility, alignment, lexical and distortion model scores for each of said partial hypotheses.

7. A method according to claim 5, wherein said translation model score determining step further comprises at least one of the following steps:

determining a fertility model score for each of said partial hypotheses, said partial hypotheses comprising at least one notion and said fertility model score being proportional to a probability that a notion in the target text will generate a specific number of notion units of linguistic structure in an intermediate structure source text;

determining an alignment score for each of said partial hypotheses, said alignment score being proportional to the probability that a unit of linguistic structure in said intermediate structure of target text will align with one of zero or more units of linguistic structure in said intermediate structure of source text;

determining a lexical model score, for each of said partial hypotheses, said lexical model score being proportional to a probability that said units of linguistic structure in said intermediate structure of target text of a given partial hypothesis will translate into said units of linguistic structure of said intermediate structure source text;

determining a distortion model score for each of said partial hypotheses, said distortion model score being proportional to a probability that a source unit of linguistic structure will be in a particular position given the position of the target units of linguistic structure that generated it; and

determining a combined score, said combined score being proportional to a product of at least one of said fertility, alignment, lexical and distortion model scores for each of said partial hypotheses.

8. A method according to claim 6, wherein each of said notions comprises at least one unit of linguistic structure, and each of said units of linguistic structure in the target text produces one of zero or more units of linguistic structure in the source text.

9. A method according to claim 3, further comprising the step of:

receiving at least one user defined criteria pertaining to the source text to thereby bound the target text, criteria belonging to the group comprising specification of a noun phrase, specification of subject, specification of verb, a semantic sense of a word or group of words, inclusion of a predetermined word or group of words, and exclusion of a predetermined word or group of words.

10. A method operating on a computer for translating source text from a first language to target text in a second language different from the first language, said method comprising the steps of:

receiving the source text in the first language and storing the source text in a first memory buffer;

receiving one of zero or more user defined criteria pertaining to the source and target texts to thereby bound the target text;

accessing the source text from said first buffer and transducing the source text into at least one intermediate source structure of text constrained by any of said user defined criteria;

generating at least one target hypothesis, each of said target hypotheses comprising an intermediate target structure of text selected from the second language constrained by any of said user defined criteria;

estimating a first score, said first score being proportional to a probability of occurrence of each intermediate target structure of text associated with said target hypotheses using a target structure language model;

estimating a second score, said second score being proportional to a probability that said intermediate target structure of text associated with said target hypotheses will translate into said intermediate source structure of text using a target structure-to-source structure translation model;

combining, for each target hypothesis, said first and second scores to produce a target hypothesis match score;

transducing each of said intermediate target structures of text into at least one transformed target hypothesis of text in the second language constrained by any of said user defined criteria; and

performing at least one of a storing operation to save said at least one transformed target hypothesis in a second memory buffer and a presenting operation to make available for at least one of a viewing and listening operation according to its associated match score and said user defined criteria.

11. A method according to claim 10, wherein said intermediate source and target structures are transduced by:

arranging and rearranging, respectively, elements of the source and target text according to at least one of lexical substitutions, part-of-speech assignment, a morphological analysis, and a syntactic analysis.

12. A method according to claim 11, wherein said syntactic analysis further comprises the steps of:

performing question inversion;

performing do-not coalescence; and

performing adverb movement.

13. A method according to claim 11, wherein said intermediate source structure transducing step further comprises the step of:

annotating said words with parts of speech by probablistically assigning a parts of speech to said words according to a statistical model.

14. A method according to claim 13, wherein said intermediate source structure transducing step further comprises the step of:

analyzing, syntactically, said annotated words and outputting a sequence of words and a sequence of said parts of speech corresponding to said sequence of words.

15. A method according to claim 14, wherein said intermediate source structure transducing step further comprises the step of:

analyzing, morphologically, said syntactically analyzed words by performing a morphological analysis of said words in accordance with said assigned parts of speech.

16. A method according to claim 15, wherein said intermediate source structure transducing step further comprises the step of:

assigning a sense to at least one of said morphological units to elucidate the translation of that morphological unit in the target language.

17. A method according to claim 11, wherein said syntactic analysis further comprises the steps of:

performing question inversion;

performing negative coalescence; and

performing at least one of adverb, pronoun and adjective movement.

18. A method according to claim 10, wherein said intermediate source structure transducing step further comprises the step of:

tokenizing the source text by identifying individual words and word separators and arranging said words and said word separators in a sequence.

19. A method according to claim 18, wherein said intermediate source structure transducing step further comprises the step of:

determining case of said words using a case transducer, said case transducer assigning each word a token and a case pattern, said case pattern specifying a case of each letter of the word, and evaluating each case pattern to determine a true case pattern of the word.

20. A method according to claim 19, wherein said determining step further comprises the steps of:

(1) determining whether said token is part of a name;

(2) if said token is not part of a name;

determining whether said token is a member of a set of tokens which have only one true case;

if said token is part of a name;

setting the true case pattern according to a table of true cases for names;

(3) if the true case has not been determined by steps 1 and 2, and if the token is a first token in a sentence, then;

setting the true case pattern equal to a most probable true case for that token; and

(4) otherwise;

setting the true case pattern equal to the only one case for that token.

21. A method according to claim 10, wherein each of said intermediate target structures is expressed as an ordered sequence of units of linguistic structure, and a first score probability is obtained by multiplying conditional probabilities of each of said units of linguistic structure within an intermediate target structure given an occurrence of previous units of linguistic structure within said intermediate target structure.

22. A method according to claim 21, wherein said conditional probability of each unit of each of linguistic structure within an intermediate target structures depends only on a fixed number of preceding units within said intermediate target structure.

23. A computer system for translating source text from a first language to target text in a second language different from the first language, said system comprising:

means for receiving the source text in the first language;

means for generating at least one target hypothesis, each of said target hypotheses comprising text selected from the second language;

means for estimating, for each target hypothesis, a first probability of occurrence of said text associated with said target hypothesis using a target language model;

means for estimating, for each target hypothesis, a second probability of occurrence of the source text given the occurrence of said text associated with said target hypothesis using a target-to-source translation model;

means for combining, for each target hypothesis, said first and second probabilities to produce a target hypothesis match score; and

means for performing at least one of a storing and presenting operation to save or otherwise make available for at least one of a viewing and listening operation, at least one of said target hypotheses according to its associated match score.

24. A system according to claim 23, further comprising:

means for generating a list of partial target hypotheses using said target language model and said target-to-source translation model;

means for extending said partial hypotheses to generate a set of new hypotheses;

means for determining a match score for at least one of said new hypotheses; and

means for performing at least one of a storing and presenting operation to save or otherwise make available for at least one of a viewing and listening operation, at least one of said new hypotheses according to its associated match score.

25. A system according to claim 24, wherein said means for determining said match score further comprises:

means for determining a language model score for each of said partial hypotheses using said target language model;

means for determining a translation model score for each of said partial hypotheses using said target-to-source translation model;

and means for combining said language and said translation model scores for each of said partial hypotheses into a combined score.

26. A system according to claim 25, wherein said means for determining said translation model score further comprises:

means for determining a fertility model score for each of said partial hypotheses, said partial hypotheses comprising at least one notion and said fertility model score being proportional to the probability that a notion in the target text will generate a specific number of notion units of linguistic structure in an intermediate structure source text;

means for determining an alignment score for each of said partial hypotheses, said alignment score being proportional to a probability that a unit of linguistic structure in said intermediate structure of target text will align with one of zero or more units of linguistic structure in said intermediate structure of source text;

means for determining a lexical model score, for each of said partial hypotheses, said lexical model score being proportional to the probability that said units of linguistic structure in said intermediate structure of target text of a given partial hypothesis will translate into said units of linguistic structure of said intermediate structure source text;

means for determining a distortion model score for each of said partial hypotheses, said distortion model score being proportional to a probability that a source unit of linguistic structure will be in a particular position given the position of the target units of linguistic structure that generated it; and

means for determining a combined score, said combined score being proportional to the product of at least one of said fertility, alignment, lexical and distortion model scores for each of said partial hypotheses.

27. A system according to claim 25, wherein said means for determining said translation model score further comprises:

means for determining a fertility model score for each of said partial hypotheses, said partial hypotheses comprising at least one notion and said fertility model score being proportional to the probability that a notion in the target text will generate a specific number of notions of units of linguistic structure in the source text;

means for determining an alignment score for each of said partial hypotheses, said alignment score being proportional to the probability that a unit of linguistic structure in the target text will align with one of zero or more units of linguistic structure in the source text;

means for determining a lexical model score, for each of said partial hypotheses, said lexical model score being proportional to the probability that said units of linguistic structure in the target text of a given partial hypothesis will translate into said units of linguistic structure of source text;

means for determining a distortion model score for each of said partial hypothesis, said distortion model score being proportional to the probability that the source units of linguistic structure will be in a particular position given the position of the target units of linguistic structure that generated it; and

means for determining a combined score, said combined score being proportional to the product of at least one of said fertility, alignment, lexical and distortion model scores for each of said partial hypotheses.

28. A system according to claim 27, wherein each of said notions comprises at least one unit of linguistic structure, and each of said units of linguistic structure in the target text produces one of zero or more units of linguistic structure in the source text.

29. A system according to claim 23, further comprising:

means for receiving at least one user defined criteria pertaining to the source text to thereby bound the target text, said criteria belonging to a group comprising specification of a noun phrase, specification of subject, specification of verb, a semantic sense of a word or group of words, inclusion of a predetermined word or group of words and exclusion of a predetermined word or group of words.

30. A computer system for translating source text from a first language to target text in a second language different from the first language, said system comprising:

means for receiving the source text in the first language and storing the source text in a first memory buffer;

means for receiving one of zero or more user defined criteria pertaining to the source and target texts to thereby bound the target text;

means for accessing the source text from said first buffer;

first transducing means for transducing the source text into at least one intermediate source structure of text constrained by any of said user defined criteria;

means for generating at least one target hypothesis, each of said target hypotheses comprising a intermediate target structure of text selected from the second language constrained by any of said user defined criteria;

means for estimating a first score, said first score being proportional to a probability of occurrence of each intermediate target structure of text associated with said target hypotheses using a target structure language model;

means for estimating a second score, said second score being proportional to a probability that said intermediate target structure of text associated with said target hypotheses will translate into said intermediate source structure of text using a target structure-to-source structure translation model;

means for combining, for each target hypothesis, said first and second scores to produce a target hypothesis match score;

second transducing means for transducing each of said intermediate target structures of text into at least one transformed target hypothesis of text in the second language constrained by any of said user defined criteria; and

means for at least one of storing said at least one transformed target hypothesis in a second memory buffer, and presenting or otherwise making said at least one transformed target hypothesis available for at least one of a viewing and listening operation according to its associated match score and said user defined criteria.

31. A system according to claim 30, wherein said first and second transducing means further comprise:

third means for arranging elements of the source text according to at least one of lexical substitutions, part-of-speech assignment, a morphological analysis, and a syntactic analysis; and

fourth means for rearranging elements of the target text according to at least one of lexical substitutions, part-of-speech assignment, a morphological analysis, and a syntactic analysis.

32. A system according to claim 31, further comprising:

means for performing question inversion;

means for performing do-not coalescence; and

means for performing adverb movement.

33. A system according to claim 31, further comprising:

means for annotating said words with parts of speech by probablistically assigning a parts of speech of said words according to a statistical model.

34. A system according to claim 33, further comprising:

means for analyzing, syntactically, said annotated words and outputting a sequence of words and a sequence of said part-of-speech corresponding to said sequence of words.

35. A system according to claim 34, further comprises:

means for analyzing, morphologically, said syntactically analyzed words by performing a morphological analysis of said words in accordance with said assigned parts of speech.

36. A system according to claim 35, further comprising:

means for assigning a sense to at least one of said morphological units to elucidate the translation of that morphological unit in the target language.

37. A system according to claim 31, further comprising:

means for performing question inversion;

means for performing negative coalescence; and

means for performing at least one of adverb, pronoun and adjective movement.

38. A system according to claim 30, wherein said first transducing means further comprises;

means for tokenizing the source text by identifying individual units of linguistic structure and unit separators and arranging said units of linguistic structure and said unit separators in a sequence.

39. A system according to claim 38, further comprising:

a case transducer means for assigning to each word a token and a case pattern, said case pattern specifying a case of each letter of the word, and evaluating each case pattern to determine a true case pattern of the word.

40. A system according to claim 39, further comprising:

(a) means for determining whether said token is part of a name;

(b) means for setting a true case according to a table of true cases for names if said token is part of a name;

(c) means for determining whether said token is a member of a set of tokens which have only one true case if said token is not part of a name;

(c) if the true case has not be determined by steps a and b, and if said token is part of a name, then;

(d) means for setting the true case equal to a most probable true case for that token if said token is part of a name; and

(f) means for setting the true case equal to the case for that token if said token is not part of a name.

41. A system according to claim 30, further comprising:

means for expressing each of said intermediate target structures as an ordered sequence of units of linguistic structure, and means for multiplying conditional probabilities of said units within an intermediate target structure given an occurrence of previous units of linguistic structure within said intermediate target structure to obtain said first score.

42. A system according to claim 41, wherein a conditional probability of each unit of each of said intermediate target structure depends only on a fixed number of preceding units within said intermediate target structure.