Method and system for natural language translation

• US 5,768,603 A
• Filed: 06/02/1995
• Issued: 06/16/1998
• 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: Mercer, Robert Leroy, Della Pietra, Stephen Andrew, Jelinek, Frederick, Cocke, John, Della Pietra, Vincent Joseph, Brown, Peter Fitzhugh, Lai, Jennifer Ceil
• Primary Examiner(s): Hayes, Gail O.
• Assistant Examiner(s): Thomas, Joseph
• Application Number:
  US08/459,698
• Time in Patent Office: 1,110 Days
• Field of Search: 395/759, 395/2.65, 395/2.86, 395/751, 395/752, 395/757, 395/2.41, 395/2.48
• 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 program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to provide method steps for translating source text from a first language to target text in a second language different from the first language, said method steps comprising:

measuring a value of the source text in the first 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 computer program product according to claim 1, further comprising:

a computer readable program code means for causing a computer to receive 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.

3. A computer program product, comprising:

a computer usable medium having computer readable program code means embodied in said medium for causing translation of source text from a first language to target text in a second language different from the first language, said computer readable program code means comprising,

a computer readable program code means for causing a computer to receive a source text in the first language;

a computer readable program code means for causing a computer to generate at least one target hypothesis, each of said target hypotheses comprising text selected from the second language;

a computer readable program code means for causing a computer to estimate, for each target hypothesis, a first probability of occurrence of said text associated with said target hypothesis using a target language model;

a computer readable program code means for causing a computer to estimate, 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;

a computer readable program code means for causing a computer to combine, for each target hypothesis, said first and second probabilities to produce a target hypothesis match score; and

a computer readable program code means for causing a computer to perform 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 computer program product according to claim 3, further comprising:

a computer readable program code means for causing a computer to generate a list of partial target hypotheses using said target language model and said target-to-source translation model;

a computer readable program code means for causing a computer to extend said partial hypotheses to generate a set of new hypotheses;

a computer readable program code means for causing a computer to determine a match score for at least one of said new hypotheses; and

a computer readable program code means for causing a computer to perform 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 new hypotheses according to its associated match score.

5. A computer program product according to claim 4, wherein said means for determining said match score further comprises:

a computer readable program code means for causing a computer to determine a language model score for each of said partial hypotheses using said target language model;

a computer readable program code means for causing a computer to determine a translation model score for each of said partial hypotheses using said target-to-source translation model; and

a computer readable program code means for causing a computer to combine said language and said translation model scores for each of said partial hypotheses into a combined score.

6. An computer program product according to claim 5, wherein said computer readable program code means for causing a computer to determine said translation model score further comprises:

a computer readable program code means for causing a computer to determine 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;

a computer readable program code means for causing a computer to determine an 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;

a computer readable program code means for causing a computer to determine 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;

a computer readable program code means for causing a computer to determine a distortion model score for each of said partial hypotheses, said distortion model score being proportional to the probability that the source units of linguistic structure will be in a particular position given by a position of the target units of linguistic structure that generated it; and

a computer readable program code means for causing a computer to determine 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.

7. A computer program product according to claim 5, wherein said computer readable program code means for causing a computer to determine said translation model score further comprises:

a computer readable program code means for causing a computer to determine 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;

a computer readable program code means for causing a computer to determine 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;

a computer readable program code means for causing a computer to determine 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;

a computer readable program code means for causing a computer to determine 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 a particular position given the position of the target units of linguistic structure that generated it; and

a computer readable program code means for causing a computer to determine 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 computer program product 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 computer program product, comprising:

a computer usable medium having computer readable program code means embodied in said medium for causing translation of source text from a first language to target text in a second language different from the first language, said computer readable program code means comprising,

a computer readable program code means for causing a computer to receive the source text in the first language and storing the source text in a first memory buffer;

a computer readable program code means for causing a computer to receive one of zero or more user defined criteria pertaining to the source and target texts to thereby bound the target text;

a computer readable program code means for causing a computer to access the source text from said first buffer;

a computer readable program code means for causing a computer to transduce the source text into at least one intermediate source structure of text constrained by any of said user defined criteria;

a computer readable program code means for causing a computer to generate 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;

a computer readable program code means for causing a computer to estimate 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;

a computer readable program code means for causing a computer to estimate 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;

a computer readable program code means for causing a computer to combine, for each target hypothesis, said first and second scores to produce a target hypothesis match score;

a computer readable program code means for causing a computer to transduce 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

a computer readable program code means for causing a computer to at least one of store said at least one transformed target hypothesis in a second memory buffer, and present 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.

10. A computer program product according to claim 9, wherein said first and second computer readable program code means for causing a computer to transduce further comprise:

a computer readable program code means for causing a computer to arrange 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.

11. A computer program product according to claim 10, further comprising:

a computer readable program code means for causing a computer to annotate said words with parts of speech by probablistically assigning a parts of speech to said words according to a statistical model.

12. A computer program product according to claim 11, further comprising:

a computer readable program code means for causing a computer to analyze, syntactically, said annotated words and outputting a sequence of words and a sequence of said part-of-speech corresponding to said sequence of words.

13. A computer program product according to claim 12, further comprising:

a computer readable program code means for causing a computer to analyze, morphologically, said syntactically analyzed words by performing a morphological analysis of said words in accordance with said assigned parts of speech.

14. A computer program product according to claim 13, further comprising:

a computer readable program code means for causing a computer to assign a sense to at least one of said morphological units to elucidate the translation of that morphological unit in the target language.

15. A computer program product according to claim 10, further comprising:

a computer readable program code means for causing a computer to perform question inversion;

a computer readable program code means for causing a computer to perform do-not coalescence; and

a computer readable program code means for causing a computer to perform adverb movement.

16. A computer program product according to claim 10, further comprising:

a computer readable program code means for causing a computer to perform question inversion;

a computer readable program code means for causing a computer to perform negative coalescence; and

a computer readable program code means for causing a computer to perform at least one of adverb, pronoun and adjective movement.

17. A computer program product according to claim 9, wherein said first computer readable program code means for causing a computer to transduce further comprises:

a computer readable program code means for causing a computer to tokenize the source text by identifying individual words and word separators and arranging said words and said word separators in a sequence.

18. A computer program product according to claim 17, further comprising:

a computer readable program code means for causing a computer to assign 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.

19. A computer program product according to claim 18, further comprising:

(a) a computer readable program code means for causing a computer to determine whether said token is part of a name;

(b) a computer readable program code means for causing a computer to set a true case pattern according to a table of true cases for names if said token is part of a name;

(c) a computer readable program code means for causing a computer to determine 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;

(d) if the true case has not been determined by means (a) and (b), then proceed to implement means (e) and (f);

(e) a computer readable program code means for causing a computer to set the true case pattern equal to a most probable true case for that token if said token is part of a name;

and

(f) a computer readable program code means for causing a computer to set the true case pattern equal to the only one case for that token if said token is not part of a name.

20. A computer program product according to claim 9, further comprising:

a computer readable program code means for causing a computer to express 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.

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

22. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to provide method steps for text-to-text language translation, said method steps comprising:

building a parametric translation model to generate a modeled translation probability, comprising the steps of,

storing a translation model source training text,

storing a translation model target training text, and

choosing a first specification of parameters for the translation model so that the modeled translation probability of the source and target training texts is a first unique local maximum value;

building a parametric language model to generate a modeled probability, comprising the steps of,

storing a language model training text, and

choosing a second specification of parameters for the language model so that the modeled probability of the given training text is a second unique local maximum value; and

performing text-to-text language translation using said parametric translation model and said parametric language model.

23. A program storage device according to claim 22, said method steps further comprising:

grouping said translation model source training text into a first plurality of tokens having sentence-like structures;

grouping said translation model target training text into a second plurality of tokens having sentence-like structures; and

performing sentence alignment by aligning said first and second pluralities of tokens according to their length.

24. A program storage device according to claim 23, said method steps further comprising:

determining a probability associated with each of said sentence alignments.

25. A program storage device according to claim 23, said method steps further comprising:

generating bigram statistics for said tokens; and

generating classes of similar elements based on said bigram statistics.

26. A program storage device according to claim 22, said method steps further comprising:

performing alignment of units of linguistic structure of said source training text with units of linguistic structure of said target training text.

27. A program storage device according to claim 26, said method steps further comprising:

determining a probability associated with each of said unit alignments.

28. A program storage device according to claim 26, said method steps further comprising:

determining a sum of probabilities for all alignments of units of linguistic structure for a given pair of source and target sentences.

29. A program storage device according to claim 26, said method steps further comprising:

determining, for a given pair of source and target sentences, the most probable alignment of units of linguistic structure between the sentences.

30. A program storage device according to claim 29, said method steps further comprising:

adjusting said most probable completion of said partial alignment by changing said alignment; and

determining the most probable completion of said new alignment.

31. A program storage device according to claim 30, said method steps further comprising:

changing said alignment by performing at least one of a swapping and single move operation, said swapping comprising the interchanging of target units of linguistic structure assigned to any two source units of linguistic structure, and said single move comprising the changing of a target unit assigned to any one source unit.

32. A program storage device according to claim 26, said method steps further comprising:

determining, for a given pair of source and target sentences and a given partial alignment of units of linguistic structure between the sentences, the most probable completion of said partial alignment.

33. A program storage device according to claim 26, said method steps further comprising:

determining, for a given pair of source and target sentences and a completely specified alignment of units of linguistic structure between the sentences, the probability of said alignment.

34. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to provide method steps for translating a first text in a first language into a second text in a second language using a lexical model, said method steps comprising:

inputting the first text into the lexical model, wherein the lexical model comprises a parametric translation model for generating a first probability and a parametric language model for generating a second probability; and

determining, using the lexical model, the second text in the second language that yields a unique local maximum value of a product of the first probability of the parametric translation model and the second probability of the parametric language model.