Determining similarity between words

• US 6,098,033 A
• Filed: 07/31/1997
• Issued: 08/01/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: Dolan, William B., Richardson, Stephen D.
• Primary Examiner(s): Isen, Forester W.
• Assistant Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US08/904,223
• Time in Patent Office: 1,097 Days
• Field of Search: 704/1, 704/9, 704/10, 707/530, 707/531, 707/532, 707/533
• US Class Current: 704/1
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

The present invention provides a facility for determining similarity between two input words utilizing the frequencies with which path patterns occurring between the words occur between words known to be synonyms. A preferred embodiment of the facility utilizes a training phase and a similarity determination phase. In the training phase, the facility first identifies, for a number of pairs of synonyms, the most salient semantic relation paths between each pair of synonyms. The facility then extracts from these semantic relation paths their path patterns, which each comprise a series of directional relation types. The number of times that each path pattern occurs between pairs of synonyms, called the frequency of the path pattern, is counted. In the training phase, the facility identifies the most salient semantic relation paths between the input words, and extracts their path patterns. The facility then averages the frequencies counted in the training phase for the path patterns extracted for the input words in order to obtain a quantitative measure of the similarity between the input words.

Claims

1. A method in a computer system for determining the similarity of a pair of input words, the method comprising:

(a) selecting a multiplicity of pairs of words known to be synonyms;

(b) for a each selected pair of synonyms;

(1) identifying the most salient semantic relation paths connecting the words of the pair of synonyms, each identified semantic relation path comprising an ordered series of semantic relations, each semantic relation having a relation type; and

(2) for each identified path;

(A) extracting from the path a path pattern comprising the relation types of the relations of the path; and

(B) augmenting a path pattern frequency indicating the likelihood that an arbitrary pair of words that are connected by a path having the extracted path pattern have similar meanings;

(c) identifying the most salient semantic relation paths connecting the input words; and

(d) obtaining from the path pattern frequencies for the path patterns of the identified paths a quantitative measure of the similarity of the input words.

2. The method of claim 1 wherein the pair of input words comprises two different words.

3. The method of claim 1 wherein the pair of input words comprises two different senses of the same word.

4. A method in a computer system for determining the similarity of a pair of input words using a list of path pattern weights, each path pattern weight indicating quantitatively the likelihood that an arbitrary pair of words connected by a path having the path pattern have similar meanings, the method comprising:

identifying a plurality of semantic relation paths connecting the input words, the identified paths comprising an ordered series of semantic relations each having a relation type;

combining the path pattern weights for the path patterns of the identified paths to obtain a quantitative measure of the similarity of the input words; and

if the obtained quantitative measure of the similarity of the input words exceeds a minimum similarity measure, indicating that the input words are similar.

5. A computer-readable medium whose contents cause a computer system to determine the similarity of a pair of input words using a list of path patterns weights, each path pattern weight indicating quantitatively the likelihood that an arbitrary pair of words connected by a path having the path pattern have similar meanings, by:

identifying a plurality of semantic relation paths, the identified paths connecting the input words and comprising an ordered series of semantic relations, each semantic relation having a relation type;

averaging the path pattern weights for the path patterns of the identified paths to obtain a quantitative measure of the similarity of the input words; and

if the obtained quantitative measure of the similarity of the input words exceeds a minimum similarity measure, indicating that the input words are similar.

6. A method in a computer system for identifying path patterns indicating similarity between word pairs connected by these path patterns, the method comprising:

(a) for a each of a multiplicity of pairs of words known to be synonyms;

(1) identifying the most salient semantic relation paths connecting the words of the pair, each identified semantic relation comprising an ordered series of semantic relations, each semantic relation having a relation type; and

(2) for each identified path;

(A) extracting from the path a relation type path pattern comprising the relation types of the relations of the path; and

(B) augmenting an indication of the likelihood that an arbitrary pair of words connected by a path having the extracted relation type path pattern have similar meanings,

such that, after the performance of the method, the likelihood indications reflect the likelihood that an arbitrary pair of words connected by a path having the relation type path pattern have similar meanings.

7. The method of claim 6, further comprising:

(b) for a each of a multiplicity of pairs of words known to not be synonyms;

(1) identifying the most salient semantic relation paths connecting the words of the pair, each identified semantic relation comprising an ordered series of semantic relations, each semantic relation having a relation type; and

(2) for each identified path;

(A) extracting from the path a relation type path pattern comprising the relation types of the relations of the path; and

(B) reducing the indication of the likelihood that an arbitrary pair of words connected by a path having the relation type path pattern have similar meanings.

8. The method of claim 7 wherein the method utilizes a dictionary containing a list of words and a thesaurus identifying pairs of synonymous words, further comprising:

(c) identifying a pair of words known to not be synonyms by;

(1) randomly selecting two words from the dictionary; and

(2) determining that the randomly selected words are not identified as synonymous by the thesaurus.

9. A computer-readable medium whose contents cause a computer system to identify path patterns indicating similarity between word pairs connected by these path patterns by:

(a) for a each of a multiplicity of pairs of words known to be synonyms;

(1) identifying the most salient semantic relation paths connecting the words of the pair, each identified semantic relation comprising an ordered series of semantic relations, each semantic relation having a relation type; and

(2) for each identified path;

(A) extracting from the path a relation type path pattern comprising the relation types of the relations of the path; and

(B) incrementing a relation type path pattern frequency for the extracted relation type path pattern indicating the likelihood that an arbitrary pair of words connected by a path having the extracted relation type path pattern have similar meanings,

such that, after the performance of the steps, the relation type path pattern frequencies of the relation type path patterns reflect the likelihood that an arbitrary pair of words connected by a path having the relation type path pattern have similar meanings.

10. The computer-readable medium of claim 9 wherein the contents of the computer-readable medium further cause the computer system to:

(b) for a each of a multiplicity of pairs of words known to not be synonyms;

(1) identify the most salient semantic relation paths connecting the words of the pair, each identified semantic relation comprising an ordered series of semantic relations, each semantic relation having a relation type; and

(2) for each identified path;

(A) extract from the path a relation type path pattern comprising the relation types of the relations of the path; and

(B) decrement the relation type path pattern frequency for the extracted relation type path pattern, thus reducing the reflected likelihood that an arbitrary pair of words connected by a path having the relation type path pattern have similar meanings.

11. A method in a computer system for determining the level of similarity of a pair of input words, the method comprising:

for each of a plurality of semantic relation type path patterns comprising an ordered series of semantic relation types;

determining a weight for the semantic relation type path pattern characterizing the extent to which semantic relation paths having that semantic relation type path pattern and occurring between arbitrary pairs of words indicate that the arbitrary pairs of words have similar meanings; and

for paths between the input words including the most salient paths between the input words, combining the weights determined for the semantic relation type path patterns corresponding to the paths between the input words in order to obtain an indication of the level of similarity of the pair of input words.

12. The method of claim 11 wherein the pair of input words comprises two different words.

13. The method of claim 11 wherein the pair of input words comprises two different senses of the same word.

14. The method of claim 11 wherein the combining comprises determining the mean of the weights determined for the semantic relation type path patterns corresponding to the paths between the input words.

15. A computer system for determining the level of similarity of a pair of input words, the method comprising:

a semantic relation type path pattern weighting subsystem that, for each of a plurality of semantic relation type path patterns comprising an ordered series of semantic relation types, determines a weight for the semantic relation type path pattern characterizing the extent to which semantic relation paths having the semantic relation type path pattern and occurring between arbitrary pairs of words indicate that the arbitrary pairs of words have similar meanings; and

a weight combination subsystem that, for paths between the input words including the most salient paths between the input words, combines the weights determined for the semantic relation type path patterns corresponding to the paths between the input words in order to obtain an indication of the level of similarity of the pair of input words.

16. The computer system of claim 15 wherein the weight combination subsystem is an averager that determines the mean of the weights determined for the semantic relation type path patterns corresponding to the paths between the input words.

17. A method in a computer system for determining the level of similarity of a pair of input words, the method comprising:

identifying a plurality of semantic relation type path patterns, each comprising an ordered series of semantic relation types, whose occurrence between arbitrary pairs of words indicate that the arbitrary pairs of words have similar meanings; and

if path patterns occurring between the input words include semantic relation type path patterns among the identified plurality, indicating that the input words are similar in meaning.

18. The method of claim 17 wherein the pair of input words comprises two different words.

19. The method of claim 17 wherein the pair of input words comprises two different senses of the same word.

20. A computer-readable medium whose contents cause a computer system to determine the level of similarity of a pair of input words by:

identifying a plurality the semantic relation type path patterns, each comprising an ordered series of semantic relation types, whose occurrence between arbitrary pairs of words indicate that the arbitrary pairs of words have similar meanings; and

if path patterns occurring between the input words include semantic relation type path patterns among the identified plurality, indicating that the input words are similar in meaning.

21. A method in a computer system for determining the strength of a selected relationship between a pair of input words, the method comprising:

(a) selecting a multiplicity of pairs of words between which the selected relationship is known to be strong;

(b) for a each selected pair of words;

(1) identifying the most salient semantic relation paths connecting the words of the selected pair, each identified semantic relation path comprising an ordered series of semantic relations, each semantic relation having a relation type; and

(2) for each identified path;

(A) extracting from the path a path pattern comprising the relation types of the relations of the path; and

(B) augmenting a path pattern frequency indicating the likelihood that the selected relationship is strong between an arbitrary pair of words that are connected by a path having the extracted path pattern;

(c) identifying the most salient semantic relation paths connecting the input words; and

(d) averaging the path pattern frequencies for the path patterns of the identified paths to obtain a quantitative measure of the strength of the selected relationship between the input words.

22. The method of claim 21, further including selecting similarity as the selected relationship.

23. The method of claim 21, further comprising:

(e) selecting a multiplicity of word pairs of a second type between which the selected relationship is known to not be strong; and

(f) for each selected word pair of the second type;

(1) identifying the most salient semantic relation paths connecting the words of the selected pair, each identified semantic relation path comprising an ordered series of semantic relations, each semantic relation having a relation type; and

(2) for each identified path;

(A) extracting from the path a path pattern comprising the relation types of the relations of the path; and

(B) reducing a path pattern frequency indicating the likelihood that the selected relationship is strong between an arbitrary pair of words that are connected by a path having the extracted path pattern.

24. A computer-readable medium whose contents cause a computer system to determine the strength of a selected relationship between a pair of input words by:

(a) selecting a multiplicity of pairs of words between which the selected relationship is known to be strong;

(b) for a each selected pair of words;

(1) identifying the most salient semantic relation paths connecting the words of the selected pair, each identified semantic relation path comprising an ordered series of semantic relations, each semantic relation having a relation type; and

(2) for each identified path;

(A) extracting from the path a path pattern comprising the relation types of the relations of the path; and

(B) augmenting a path pattern frequency indicating the likelihood that the selected relationship is strong between an arbitrary pair of words that are connected by a path having the extracted path pattern;

(c) identifying the most salient semantic relation paths connecting the input words; and

(d) obtaining from the path pattern frequencies for the path patterns of the identified paths a quantitative measure of the strength of the selected relationship between the input words.

25. A computer memory containing a word similarity data structure for determining the similarity of a pair of input words, the word similarity data structure comprising entries, each entry identifying:

a semantic relation type path pattern comprising an ordered series of semantic relation types; and

a weight for the semantic relation type path pattern characterizing the extent to which a semantic relation paths of the semantic relation type path pattern occurring between an arbitrary pair of words indicates that the words of the arbitrary pair have similar meanings, the word similarity data structure being usable to determine the similarity of the input words by combining the weights for semantic relation type path patterns that occur between the input words.

26. The computer memory of claim 25 wherein the weight indicated by each entry of the word similarity data structure comprises the frequency with which the semantic relation type path pattern of the entry occurs between words known to be synonyms.

27. The computer memory of claim 25 wherein the weight indicated by each entry of the word similarity data structure comprises the frequency with which the semantic relation type path pattern of the entry occurs between words known to be synonyms, reduced by the frequency with which the semantic relation type path pattern of the entry occurs between words known not to be synonyms.