Method for constructing a knowledge base, knowledge base system, machine translation method and system therefor

• US 5,267,156 A
• Filed: 12/05/1991
• Issued: 11/30/1993
• Est. Priority Date: 12/05/1991
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Nomiyama, Hiroshi
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): Tran, Khai
• Application Number:
  US07/803,276
• Time in Patent Office: 726 Days
• Field of Search: 364/419
• US Class Current: 704/10
• CPC Class Codes: G06F 40/45 Example-based machine translation; Alignment

Abstract

A method and apparatus for machine translation of language is disclosed. For each translation pattern, qualified words and corresponding translations are extracted. The invention generalizes words by converting them into concepts which are more general and can be applied to many inputs. A partial thesaurus is generated that describes hierarchies of words and concepts that are hypernyms of these words. Based on frequency information obtained for the words, an importance value is computed for each concept. Importances are used to determine the possibility of generalizing concepts in the translation.

Claims

1. A method for constructing a knowledge base for responding to an input source-language word pattern that meets a translation pattern description and outputting a translation in a target language, from translation cases stored in a case base, by using a thesaurus describing hierarchies of words and concepts in the source language, comprising the steps of:

(a) searching the case base to find one or more translation cases using a selected translation pattern description, the selected translation pattern description having a source language pattern with source values, an associated target language pattern with target values, and links that relate respective source and target values, the translation pattern description being selected when the input-source language word pattern matches the source language pattern;

(b) extracting one or more matching translation cases having words in the source language that meet one or more translation pattern description conditions and extracting a respective corresponding translation for the extracted translation cases, the extracted matching translation cases and corresponding translations being a set of translation pattern cases, the extracted matching translation cases having the words in the source language as source values and the corresponding translations having a target value determined by a translation of their respective source values;

(c) generating a partial thesaurus for one or more translation pattern cases in the set of translation pattern cases, the partial thesaurus created by extracting parts of a thesaurus that contain the source values and hypernyms of the source values and obtaining for each of said source values and hypernyms a corresponding translation, the source value and corresponding translation comprising a pair, the pair and a corresponding frequency of occurrence of the pair comprising a word node in a hierarchy of word nodes in the partial thesaurus;

(d) computing an importance value of a translation for each word node contained in said partial thesaurus on the basis of said frequency of the word node; and

(e) determining whether to convert a word contained in a translation pattern case into a hypernym in said partial thesaurus by using the importance value of a corresponding translation computed for the hypernym, and, if possible, converting the word into the hypernym in order to generalize said translation pattern case.

2. The method according to claim 1 wherein the importance of a generalized case is computed on the basis of the importance of the corresponding translation of the pair which is computed for word nodes contained in said generalized case.

3. The method according to claim 1 wherein said step (e) is repeated, and duplicated generalized cases are deleted during the repetition.

4. The method according to claim 1 wherein said conditions are described by using variables that hold words in the source language as their values.

5. The method according to claim 4 wherein said step (c) generates a partial thesaurus for each source language value;

and

said step (c) also uses the importance value of the translations computed for concepts contained in a partial thesaurus corresponding to another variable to determine whether to convert a word into a hypernym thereof.

6. The method according to claim 1 wherein said step (d) computes the importance value of a translation for a direct hypernym of a word contained in a partial thesaurus by using frequency information obtained for words that are hyponyms of said hypernym.

7. The method according to claim 6 wherein the importance value of a translation for a higher-level word node is computed recursively by using the importance of the translation for a lower-level word node.

8. The method according to claim 6 wherein, in response to a translation corresponding to a direct hypernym of a word whose importance is second or lower for the hypernym but larger than a predetermined threshold, some of the words that are hyponyms of said hypernym are subcategorized into a new concept.

9. The method according to claim 1 wherein, if translation rules are provided, said translation rules being described independently of translation cases in said case base their importances are computed on the basis of corresponding translations for concepts contained in said rules, and said translation rules are stored in said knowledge base with their computed importances.

10. A translation knowledge base system comprising means for accumulating generalized cases for outputting translations into a target language in response to the input of a source-language word pattern comprising:

(a) a translation pattern description means for searching a case base to find one or more translation cases that match the translation pattern description means, the translation pattern description means having a source language pattern with source values, and associated target language pattern with target values, and links that relate respective source and target values;

(b) a set of translation pattern cases extracted by matching translation cases having words in the source language that meet one or more translation pattern description conditions and having a corresponding translation for the extracted translation cases;

(c) a partial thesaurus for each translation pattern case in the set of translation pattern cases, the partial thesaurus representing the hierarchies of words contained in the translation pattern cases and concepts that are hypernyms of said words in said thesaurus, the partial thesaurus also having information for each of the words being a corresponding translation, the word and corresponding translation comprising a pair, the pair and a corresponding frequency of occurrence of the pair comprising a words node in a hierarchy of word nodes in the partial thesaurus;

(d) an importance value of a translation for each concept contained in said partial thesaurus computed from the frequency of the word node; and

(e) a means for determining whether to convert a word contained in a pattern case into a hypernym in said partial thesaurus by using the importance value of a corresponding translation computed for the hypernym, and, if possible, converting the word into the hypernym in order to generalize the pattern case.

11. A method for machine translation from an input expressed in a source language into an output expressed in a target language by using a knowledge base for responding to an input source language word pattern comprising the steps of:

(a) searching the knowledge base to find one or more translation cases using a selected translation pattern description, the selected translation pattern description having a source language pattern with source values, an associated target language pattern with target values, and links that relate respective source and target values, the translation pattern description being selected when the input source language word pattern matches the source language pattern;

(b) extracting one or more matching translation cases having words in the source language that meet one or more translation pattern description conditions and extracting a respective corresponding translation for the extracted translation cases, the extracted matching translation cases and corresponding translations being a set of translation pattern cases, the extracted matching translation cases having the words in the source language as source values and the corresponding translations having a target value determined by a translation of their respective source values;

(c) generating a partial thesaurus for one or more translation pattern cases in the set of translation pattern cases, the partial thesaurus created by extracting parts of a thesaurus that contain the source values and hypernyms of the source values and obtaining for each of said source values and hypernyms a corresponding translation, the source value and corresponding translation comprising a pair, the pair and a corresponding frequency of occurrence of the pair comprising a word node in a hierarchy of word nodes in the partial thesaurus;

(d) computing an importance value of a translation for each word node contained in said partial thesaurus on the basis of said frequency of the word node and using the importance value to determine whether to generalize the translation pattern case by converting a word to a hypernym;

(e) obtaining a target value translation by using the importance values of the word nodes; and

(f) using the obtained target value in a target language pattern as the translation of the source language input.

12. The method according to claim 11 wherein said generalized cases are provided with importances reflecting the frequencies of cases assigned to them, and wherein, if multiple generalized cases are obtained in said step (d), their importances are compared to determine which generalized case to use.

13. The method according to claim 11 wherein said step (d) determines whether a concept that is not contained in said thesaurus is applicable to translation under said conditions, and wherein, if any, said concept is used together with said thesaurus in step (c).