US5477451A — Method and system for natural language translation

Claim 1

Independent Claim 162 words

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.

Claim 2

Independent Claim 162 words

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.

Claim 3

Dependent Claim 76 words

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.

Claim 4

Independent Claim 168 words

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.

Claim 5

Independent Claim 168 words

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.

Claim 6

Dependent Claim 84 words

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.

Claim 7

Dependent Claim 67 words

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.

Claim 8

Dependent Claim 241 words

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.

Claim 9

Dependent Claim 255 words

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.

Claim 10

Dependent Claim 45 words

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.

Claim 11

Dependent Claim 75 words

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.

Claim 12

Independent Claim 303 words

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.

Claim 13

Independent Claim 303 words

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.

Claim 14

Dependent Claim 44 words

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.

Claim 15

Dependent Claim 25 words

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.

Claim 16

Dependent Claim 40 words

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.

Claim 17

Dependent Claim 43 words

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.

Claim 18

Dependent Claim 40 words

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.

Claim 19

Dependent Claim 41 words

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.

Claim 20

Dependent Claim 32 words

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.

Claim 21

Dependent Claim 40 words

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.

Claim 22

Dependent Claim 65 words

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.

Claim 23

Dependent Claim 133 words

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.

Claim 24

Dependent Claim 62 words

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.

Claim 25

Dependent Claim 37 words

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.

Claim 26

Dependent Claim 174 words

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.

Claim 27

Dependent Claim 174 words

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.

Claim 28

Dependent Claim 96 words

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.

Claim 29

Dependent Claim 73 words

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.

Claim 30

Dependent Claim 260 words

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.

Claim 31

Dependent Claim 247 words

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.

Claim 32

Dependent Claim 45 words

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.

Claim 33

Dependent Claim 75 words

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.

Claim 34

Dependent Claim 321 words

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.

Claim 35

Dependent Claim 321 words

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.

Claim 36

Dependent Claim 68 words

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.

Claim 37

Dependent Claim 24 words

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.

Claim 38

Dependent Claim 32 words

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.

Claim 39

Dependent Claim 33 words

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.

Claim 40

Dependent Claim 32 words

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.

Claim 41

Dependent Claim 33 words

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.

Claim 42

Dependent Claim 31 words

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.

Claim 43

Dependent Claim 43 words

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.

Claim 44

Dependent Claim 49 words

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.

Claim 45

Dependent Claim 147 words

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.

Claim 46

Dependent Claim 59 words

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.

Claim 47

Dependent Claim 34 words

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.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1998-12-18	1999-06-19	1999-12-19	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2002-12-18	2003-06-19	2003-12-19	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2006-12-18	2007-06-19	2007-12-19	$7700.00	Window Closed / Lapsed

Method and system for natural language translation

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag