Patent US5659771A successfully refreshed from Google Patents.
US5659771A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System for spelling correction in which the context of a target word in a sentence is utilized to determine which of several possible words was intended
Assignee: Mitsubishi Electric Research Laboratories Inc
•
Filing: 1995-05-19
•
Granted: 1997-08-19
•
Expires: 2015-05-19
Abstract
Abstract A system is provided for spelling correction in which the context of a wordn a sentence is utilized to determine which of several alternative or possible words was intended. The probability that a particular alternative was the word that was intended is determined through Bayesian analysis utilizing multiple kinds of features of the context of the target word, such as the presence of certain characteristic words within some distance of the target word, or the presence of certain characteristic patterns of words and part-of-speech tags around the target word. The system successfully combines multiple types of features via Bayesian analysis through means for resolving egregious interdependencies among features. The system first recognizes the interdependencies, and then resolves them by deleting all but the strongest feature involved in each interdependency, thereby allowing it to make its decisions based on the strongest non-conflicting set of features. In addition, the robustness of the system's decisions is enhanced by the pruning or deletion from consideration of certain features, in one case by deleting features for which there is insufficient evidence in the training corpus to support reliable decision-making, and secondly by deleting features which are uninformative at discriminating among the alternative spellings of the target word under consideration.
Inventors
- 👤 Andrew R. Golding
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 19:23
CPC Classifications
G; G06; G06F; G06F40/00; G06F40/20; G06F40/232
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
222 words
A system for spelling correction in which the context of a target word in a sentence is utilized to determine which of several possible words was intended, comprising: a training corpus containing a set of sentences; a dictionary of part-of-speech tags of words in said training corpus; a confusion set including a list of possible words that could have been intended for said target word; an ordered list of features usable to discriminate among words in said confusion set to correct instances in which one word in said confusion set has been incorrectly substituted for another; and, means responsive to said training corpus, said dictionary, said confusion set, said ordered list of features, and said target word for determining the intended spelling of said target word from context, said means for determining the intended selling of said target word including means for assigning a probability to each word in said confusion set, means for obtaining a feature from said ordered list of features, means for ascertaining if said obtained feature matches the context of said target word in said sentence, thereby to provide a list of matched features, and means for determining if a feature from said ordered list conflicts with a previously obtained feature, said conflict-determining means including means for establishing if there is an egregious interdependency between said obtained features.
Claim 2
Independent Claim
222 words
A system for spelling correction in which the context of a target word in a sentence is utilized to determine which of several possible words was intended, comprising: a training corpus containing a set of sentences; a dictionary of part-of-speech tags of words in said training corpus; a confusion set including a list of possible words that could have been intended for said target word; an ordered list of features usable to discriminate among words in said confusion set to correct instances in which one word in said confusion set has been incorrectly substituted for another; and, means responsive to said training corpus, said dictionary, said confusion set, said ordered list of features, and said target word for determining the intended spelling of said target word from context, said means for determining the intended selling of said target word including means for assigning a probability to each word in said confusion set, means for obtaining a feature from said ordered list of features, means for ascertaining if said obtained feature matches the context of said target word in said sentence, thereby to provide a list of matched features, and means for determining if a feature from said ordered list conflicts with a previously obtained feature, said conflict-determining means including means for establishing if there is an egregious interdependency between said obtained features.
Claim 3
Dependent Claim
79 words
The system of claim 1, wherein said means for establishing an egregious interdependency includes means for establishing if both of said features are not context-word features, if both features are collocation features and only if there is an overlap between the portion of the context that they test, and if one of said features is a collocation feature and the other is a context-word feature and if said collocation feature explicitly tests for the presence of said context word.
Claim 4
Dependent Claim
40 words
The system of claim 1, and further including means for updating the running probability for each word in said confusion set for a matched feature and for using said updated probability for selecting the intended spelling of said target word.
Claim 5
Dependent Claim
27 words
The system of claim 3, wherein said means for updating said running probability includes means utilizing Bayes' rule for estimating the joint probability of all matched features.
Claim 6
Dependent Claim
23 words
The system of claim 1, and further including means for providing said ordered list including means for providing a pruned list of features.
Claim 7
Independent Claim
222 words
A system for spelling correction in which the context of a target word in a sentence is utilized to determine which of several possible words was intended, comprising: a training corpus containing a set of sentences; a dictionary of part-of-speech tags of words in said training corpus; a confusion set including a list of possible words that could have been intended for said target word; an ordered list of features usable to discriminate among words in said confusion set to correct instances in which one word in said confusion set has been incorrectly substituted for another; means responsive to said training corpus, said dictionary, said confusion set, said ordered list of features, and said target word for determining the intended spelling of said target word from context; and, means for providing said ordered list including means for providing a pruned list of features, said means for providing a pruned list of features including means responsive to said training corpus, said confusion set, and said dictionary for proposing all possible features as candidate features; means for providing a count of the occurrences of each candidate feature in said training corpus; means responsive to said count for enumerating features having a count below a predetermined threshold; and, means for eliminating features that are not informative at discriminating among the words in said confusion set.
Claim 8
Independent Claim
222 words
A system for spelling correction in which the context of a target word in a sentence is utilized to determine which of several possible words was intended, comprising: a training corpus containing a set of sentences; a dictionary of part-of-speech tags of words in said training corpus; a confusion set including a list of possible words that could have been intended for said target word; an ordered list of features usable to discriminate among words in said confusion set to correct instances in which one word in said confusion set has been incorrectly substituted for another; means responsive to said training corpus, said dictionary, said confusion set, said ordered list of features, and said target word for determining the intended spelling of said target word from context; and, means for providing said ordered list including means for providing a pruned list of features, said means for providing a pruned list of features including means responsive to said training corpus, said confusion set, and said dictionary for proposing all possible features as candidate features; means for providing a count of the occurrences of each candidate feature in said training corpus; means responsive to said count for enumerating features having a count below a predetermined threshold; and, means for eliminating features that are not informative at discriminating among the words in said confusion set.
Claim 9
Dependent Claim
43 words
The system of claim 6, wherein said means for eliminating features that are not informative includes means for performing a chi-square test to ascertain the degree of association between the presence of a feature and the distribution of words in said confusion set.
Claim 10
Dependent Claim
20 words
The system of claim 6, and further including means for ordering the uneliminated remaining features in order of decreasing strength.
Claim 11
Dependent Claim
68 words
The system of claim 8, wherein strength is defined as strength(f)=max 1 ≦i≦n p(w i |f) where f is a feature, n is the number of words in said confusion set, w i is the ith word in said confusion set, and p(w i |f) is the probability that, given that feature f is present for some word in the confusion set, that word is w i .
References Cited (Backward Citations)
US5075896A
Cited
US5541836A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-08-18 | 2001-02-17 | 2001-08-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-08-18 | 2005-02-17 | 2005-08-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-08-18 | 2009-02-17 | 2009-08-19 | $7700.00 | Window Closed / Lapsed |