Patent US6098033A successfully refreshed from Google Patents.
US6098033A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Determining similarity between words
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1997-07-31
•
Granted: 2000-08-01
•
Expires: 2017-07-31
Abstract
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.
Inventors
- 👤 Stephen D. Richardson
- 👤 William B. Dolan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 20:07
CPC Classifications
G; G06; G06F; G06F40/00; G06F40/20; G06F40/279; G06F40/284; G06F40/30
Claims Analysis
Total Claims: 39
Claim 1
Independent Claim
166 words
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.
Claim 2
Independent Claim
166 words
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.
Claim 3
Dependent Claim
15 words
The method of claim 1 wherein the pair of input words comprises two different words.
Claim 4
Dependent Claim
19 words
The method of claim 1 wherein the pair of input words comprises two different senses of the same word.
Claim 5
Independent Claim
127 words
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.
Claim 6
Independent Claim
127 words
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.
Claim 7
Dependent Claim
131 words
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.
Claim 8
Dependent Claim
131 words
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.
Claim 9
Independent Claim
157 words
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.
Claim 10
Independent Claim
157 words
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.
Claim 11
Dependent Claim
108 words
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.
Claim 12
Dependent Claim
62 words
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.
Claim 13
Dependent Claim
178 words
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.
Claim 14
Dependent Claim
178 words
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.
Claim 15
Dependent Claim
133 words
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.
Claim 16
Independent Claim
134 words
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.
Claim 17
Independent Claim
134 words
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.
Claim 18
Dependent Claim
15 words
The method of claim 11 wherein the pair of input words comprises two different words.
Claim 19
Dependent Claim
19 words
The method of claim 11 wherein the pair of input words comprises two different senses of the same word.
Claim 20
Dependent Claim
31 words
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.
Claim 21
Dependent Claim
145 words
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.
Claim 22
Dependent Claim
145 words
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.
Claim 23
Dependent Claim
37 words
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.
Claim 24
Independent Claim
84 words
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.
Claim 25
Independent Claim
84 words
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.
Claim 26
Dependent Claim
15 words
The method of claim 17 wherein the pair of input words comprises two different words.
Claim 27
Dependent Claim
19 words
The method of claim 17 wherein the pair of input words comprises two different senses of the same word.
Claim 28
Dependent Claim
85 words
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.
Claim 29
Dependent Claim
85 words
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.
Claim 30
Independent Claim
183 words
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.
Claim 31
Independent Claim
183 words
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.
Claim 32
Dependent Claim
13 words
The method of claim 21, further including selecting similarity as the selected relationship.
Claim 33
Dependent Claim
131 words
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.
Claim 34
Dependent Claim
183 words
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.
Claim 35
Dependent Claim
183 words
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.
Claim 36
Dependent Claim
118 words
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.
Claim 37
Dependent Claim
118 words
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.
Claim 38
Dependent Claim
40 words
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.
Claim 39
Dependent Claim
63 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-08-01 | 2004-01-31 | 2004-08-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-08-01 | 2008-01-31 | 2008-08-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-08-01 | 2012-01-31 | 2012-08-01 | $7700.00 | Window Closed / Lapsed |