Inferring semantic relations

• US 6,138,085 A
• Filed: 07/31/1997
• Issued: 10/24/2000
• Est. Priority Date: 07/31/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Vanderwende, Lucy, Richardson, Stephen D.
• Primary Examiner(s): Chang, Vivian
• Assistant Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US08/904,226
• Time in Patent Office: 1,181 Days
• Field of Search: 704/1, 704/8, 704/9, 704/10, 707/530, 707/531, 707/532, 707/5, 707/2
• US Class Current: 704/1
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

The present invention provides a facility for determining, for a semantic relation that does not occur in a lexical knowledge base, whether this semantic relation should be inferred despite its absence from the lexical knowledge base. This semantic relation to be inferred is preferably made up of a first word, a second word, and a relation type relating the meanings of the first and second words. In a preferred embodiment, the facility identifies a salient semantic relation having the relation type of the semantic relation to be inferred and relating the first word to an intermediate word other than the second word. The facility then generates a quantitative measure of the similarity in meaning between the intermediate word and the second word. The facility further generates a confidence weight for the semantic relation to be inferred based upon the generated measure of similarity in meaning between the intermediate word and the second word. The facility may also generate a confidence weight for the semantic relation to be inferred based upon the weights of one or more paths connecting the first and second words.

Claims

1. A method in a computer system for determining whether a queried semantic relation is valid, the queried semantic relation comprising two query words and a query relation type relating the meanings of the query words, comprising:

identifying a first group of salient semantic relation paths relating the meanings of the two query words, the identified semantic relation paths each comprising an ordered chain of semantic relations, each semantic relation comprising two words and a relation type relating the meanings of the two words, such that each identified semantic relation path relates the meanings of the two query words via one or more intermediate words;

among the first group of semantic relation paths, identifying a second group of one or more semantic relation paths in which the first or last semantic relation is of the query relation type; and

for each of the second group of semantic relation paths;

determining whether the intermediate word in the semantic relation of the semantic relation path having the query relation type and the query word not in the semantic relation of the semantic relation path having the query relation type have similar meanings, and

if the intermediate word in the semantic relation of the semantic relation path having the query relation type and the query word not in the semantic relation of the semantic relation path having the query relation type have similar meanings, determining that the queried semantic relation is valid.

2. A computer-readable medium whose contents cause a computer system to determine whether a queried semantic relation is valid, the queried semantic relation comprising two query words and a query relation type relating the meanings of the query words, by:

identifying a first group of salient semantic relation paths relating the meanings of the two query words, the identified semantic relation paths each comprising an ordered chain of semantic relations, each semantic relation comprising two words and a relation type relating the meanings of the two words, such that each identified semantic relation path relates the meanings of the two query words via one or more intermediate words;

among the first group of semantic relation paths, identifying a second group of one or more semantic relation paths in which the first or last semantic relation is of the query relation type; and

for each of the second group of semantic relation paths;

determining whether the intermediate word in the semantic relation of the semantic relation path having the query relation type and the query word not in the semantic relation of the semantic relation path having the query relation type have similar meanings, and

if the intermediate word in the semantic relation of the semantic relation path having the query relation type and the query word not in the semantic relation of the semantic relation path having the query relation type have similar meanings, determining that the queried semantic relation is valid.

3. A method in a computer system for determining whether a queried semantic relation is valid, the queried semantic relation comprising two query words and a relation type relating the meanings of the query words, comprising:

identifying a first group of salient semantic relation paths relating the meanings of the two query words, the identified semantic relation paths each comprising an ordered chain of semantic relations, each semantic relation comprising two words and a relation type relating the meanings of the two words, such that each identified semantic relation path relates the meanings of the two query words via one or more intermediate words;

among the first group of semantic relation paths, identifying a second group of one or more semantic relation paths in which the first or last semantic relation is of the query relation type;

in each of the semantic relation paths of the second group, selecting the semantic relation of the query type;

among the second group of semantic relation paths, identifying a third group of one or more semantic relation paths in which the intermediate word in the selected semantic relation and the query word not in the selected semantic relation have similar meanings; and

determining a quantitative assessment of whether the queried semantic relation is valid based upon the weights of the semantic relation paths of the third group.

4. The method of claim 3 wherein the determining determines the quantitative assessment of whether the queried semantic relation is valid based upon an average of the weights of the semantic relation paths of the third group.

5. The method of claim 3 wherein the determining determines the quantitative assessment of whether the queried semantic relation is valid based upon an maximum of the weights of the semantic relation paths of the third group.

6. The method of claim 3, further comprising determining that the queried semantic relation is valid where the quantitative assessment exceeds a validity threshold.

7. A computer-readable medium whose contents cause a computer system to determine whether a queried semantic relation is valid, the queried semantic relation comprising two query words and a relation type relating the meanings of the query words, by:

identifying a first group of salient semantic relation paths relating the meanings of the two query words, the identified semantic relation paths each comprising an ordered chain of semantic relations, each semantic relation comprising two words and a relation type relating the meanings of the two words, such that each identified semantic relation path relates the meanings of the two query words via one or more intermediate words;

among the first group of semantic relation paths, identifying a second group of one or more semantic relation paths in which the first or last semantic relation is of the query relation type;

in each of the semantic relation paths of the second group, selecting the semantic relation of the query type;

among the second group of semantic relation paths, identifying a third group of one or more semantic relation paths in which the intermediate word in the selected semantic relation and the query word not in the selected semantic relation have similar meanings; and

determining a quantitative assessment of whether the queried semantic relation is valid based upon the weights of the semantic relation paths of the third group.

8. The computer-readable medium of claim 7 wherein the contents of the computer-readable medium further cause the computer system to determine that the queried semantic relation is valid where the quantitative assessment exceeds a validity threshold.

9. A method in a computer system for determining whether a queried semantic relation is valid, the queried semantic relation comprising two query words and a relation type relating the meanings of the query words, comprising:

identifying a first group of salient semantic relation paths relating the meanings of the two query words, the identified semantic relation paths each comprising an ordered chain of semantic relations, each semantic relation comprising two words and a relation type relating the meanings of the two words, such that each identified semantic relation path relates the meanings of the two query words via one or more intermediate words;

among the first group of semantic relation paths, identifying a second group of one or more semantic relation paths in which the first or last semantic relation is of the query relation type; and

determining a quantitative assessment of whether the queried semantic relation is valid based upon the weights of the semantic relation paths of the second group.

10. The method of claim 9, further comprising determining that the queried semantic relation is valid where the quantitative assessment exceeds a validity threshold.

11. A computer-readable medium whose contents cause a computer system to determine whether a queried semantic relation is valid, the queried semantic relation comprising two query words and a relation type relating the meanings of the query words, by:

identifying a first group of salient semantic relation paths relating the meanings of the two query words, the identified semantic relation paths each comprising an ordered chain of semantic relations, each semantic relation comprising two words and a relation type relating the meanings of the two words, such that each identified semantic relation path relates the meanings of the two query words via one or more intermediate words;

among the first group of semantic relation paths, identifying a second group of one or more semantic relation paths in which the first or last semantic relation is of the query relation type; and

determining a quantitative assessment of whether the queried semantic relation is valid based upon the weights of the semantic relation paths of the second group.

12. The computer-readable medium of claim 11 wherein the contents of the computer-readable medium further cause the computer system to determine that the queried semantic relation is valid where the quantitative assessment exceeds a validity threshold.

13. A method in a computer system for determining whether a queried semantic relation is valid, the queried semantic relation comprising two query words and a relation type relating the meanings of the query words, comprising:

identifying a first group of salient semantic relation paths relating the meanings of the two query words, the identified semantic relation paths each comprising an ordered chain of semantic relations, each semantic relation comprising two words and a relation type relating the meanings of the two words, such that each identified semantic relation path relates the meanings of the two query words via one or more intermediate words;

among the first group of semantic relation paths, identifying a second group of one or more semantic relation paths in which the first or last semantic relation is of the query relation type;

in each of the semantic relation paths of the second group, selecting the semantic relation of the query type; and

determining a quantitative assessment of whether the queried semantic relation is valid based upon the level of similarity between the meanings of the intermediate word in the selected semantic relation and the query word not in the selected semantic relation in the semantic relation paths of the second group.

14. The method of claim 13 wherein the determining determines the quantitative assessment of whether the queried semantic relation is valid based upon an average of the weights of the semantic relation paths of the third group.

15. The method of claim 13 wherein the determining determines the quantitative assessment of whether the queried semantic relation is valid based upon an maximum of the weights of the semantic relation paths of the third group.

16. The method of claim 13, further comprising determining that the queried semantic relation is valid where the quantitative assessment exceeds a validity threshold.

17. A computer-readable medium whose contents cause a computer system to determine whether a queried semantic relation is valid, the queried semantic relation comprising two query words and a relation type relating the meanings of the query words, by:

identifying a first group of salient semantic relation paths relating the meanings of the two query words, the identified semantic relation paths each comprising an ordered chain of semantic relations, each semantic relation comprising two words and a relation type relating the meanings of the two words, such that each identified semantic relation path relates the meanings of the two query words via one or more intermediate words;

among the first group of semantic relation paths, identifying a second group of one or more semantic relation paths in which the first or last semantic relation is of the query relation type;

in each of the semantic relation paths of the second group, selecting the semantic relation of the query type; and

determining a quantitative assessment of whether the queried semantic relation is valid based upon the level of similarity between the meanings of the intermediate word in the selected semantic relation and the query word not in the selected semantic relation in the semantic relation paths of the second group.

18. The computer-readable medium of claim 17 wherein the contents of the computer-readable medium further cause the computer system to determine that the queried semantic relation is valid where the quantitative assessment exceeds a validity threshold.

19. A method in a computer system for assessing the strength of an input semantic relation comprising two input words and an input relation type relating the input words, comprising:

identifying a salient semantic relation having the input relation type and relating one of the input words to an intermediate word other than the other input word;

generating a quantitative measure of the similarity of the intermediate word and the other input word; and

generating a confidence weight for the input semantic relation that quantitatively reflects the level of confidence with which the input semantic relation should be inferred based upon the generated measure of similarity of the intermediate word and the other input word.

20. A computer-readable medium whose contents cause a computer system to assess the strength of an input semantic relation comprising first and second input words and an input relation type relating the first and second input words by:

identifying a salient semantic relation having the input relation type and relating the first input word to an intermediate word other than the second input word;

generating a quantitative measure of the similarity of the intermediate word and the second input word; and

generating a confidence weight for the input semantic relation that quantitatively reflects the level of confidence with which the input semantic relation should be inferred based upon the generated measure of similarity of the intermediate word and the second input word.

21. A method in a computer system for assessing the strength of an input semantic relation comprising two input words and an input relation type relating the input words, comprising:

identifying a salient semantic relation having the input relation type and relating one of the input words to an intermediate word other than the other input word;

determining the weight of the identified semantic relation;

generating a quantitative measure of the similarity of the intermediate word and the other input word; and

generating a confidence weight for the input semantic relation based upon both the generated quantitative measure of the similarity of the intermediate word and the other input word and the determined weight of the identified semantic relation determined.

22. The method of claim 21, further comprising determining that the input semantic relation should be inferred where the confidence weight exceeds a predetermined threshold.

23. The method of claim 21, further comprising determining the path weight of an artificial path comprising the identified semantic relation and a special semantic relation characterizing the level of similarity of the intermediate word and the other input word, and wherein the generating step generates a confidence weight based on the determined path weights.

24. A computer-readable medium whose contents cause a computer system to assess the strength of an input semantic relation comprising first and second input words and an input relation type relating the first and second input words by:

identifying a salient semantic relation having the input relation type and relating one of the input words to an intermediate word other than the other input word;

determining the weight of the identified semantic relation;

generating a quantitative measure of the similarity of the intermediate word and the other input word; and

generating a confidence weight for the input semantic relation based upon both the generated quantitative measure of the similarity of the intermediate word and the other input word and the determined weight of the identified semantic relation determined.

25. The computer-readable medium of claim 24 wherein the contents of the computer-readable medium further cause the computer system to determine that the input semantic relation should be inferred where the confidence weight exceeds a predetermined threshold.

26. The computer-readable medium of claim 24 wherein the contents of the computer-readable medium further cause the computer system to determine the path weight of an artificial path comprising the identified semantic relation and a special semantic relation characterizing the level of similarity of the intermediate word and the other input word, and wherein the generating generates a confidence weight based on the determined path weights.

27. A computer memory containing a composite lexical knowledge base relating the meanings of words, the composite lexical knowledge base identifying a multiplicity of semantic relations each relating the meanings of an identified pair of words, the multiplicity of semantic relations comprising both:

semantic relations of a first type, each obtained by parsing a segment of natural language occurring in a corpus of natural language segments; and

semantic relations of a second type, each obtained by inference from a plurality of semantic relations of the first type, such that the composite lexical knowledge base may be used to determine the validity of a selected semantic relation in the context of the corpus irrespective of whether the selected semantic relation can be obtained by parsing the corpus.

28. A computer-based system for assessing the strength of an input semantic relation comprising two input words and an input relation type relating the input words, comprising:

a relation identification subsystem that identifies a salient semantic relation having the input relation type and relating one of the input words to an intermediate word other than the other input word;

a similarity measurement subsystem that generates a quantitative measure of the similarity of the intermediate word and the other input word; and

a weighting subsystem that generates a confidence weight for the input semantic relation that quantitatively reflects the level of confidence with which the input semantic relation should be inferred based upon the generated measure of similarity of the intermediate word and the other input word.

29. The computer-based system of claim 28, further comprising a semantic relation validation subsystem that determines whether the input semantic relation is valid based on the confidence weight generated by the weighting subsystem.