System for text correction adaptive to the text being corrected

A system is provided for correcting users' mistakes including context-sensitive spelling errors and the like in which an adaptive correction algorithm is utilized which is trained on not only a conventional training corpus, but also on the text which is being corrected, thus to permit the correction of words based on the particular usages of the words in the text being corrected, taking advantage of the fact that the text to be corrected is by and large already mostly correct.

FIELD OF THE INVENTION 
This invention relates to the correction of text, and more particularly to 
an adaptive system for text correction in which a training set is utilized 
that includes text which is assumed to be mostly correct. 
BACKGROUND OF THE INVENTION 
In the past, especially with respect to text editing, user mistakes such as 
spelling errors were corrected utilizing conventional spell-checking 
systems utilizing lookup tables. Subsequently, more sophisticated 
spell-checking systems were developed in which the context in which the 
word occurred was taken into account. These systems traditionally involved 
the utilization of so-called training corpora which contain examples of 
the correct use of the words in the context of the sentences in which they 
occurred. 
One of the major problems with such context-sensitive spelling-correction 
systems is the inability of these systems to take into account situations 
in which the corpus on which they were trained is dissimilar to the target 
text to which they are applied. This is an important problem for text 
correction because words can be used in a wide variety of contexts; thus 
there is no guarantee that the particular contextual uses of the words 
seen in the target text will also have been seen in the training corpus. 
Consider, for example, an algorithm whose job is to correct 
context-sensitive spelling errors; these are spelling errors that happen 
to result in a valid word of English, but not the word that was 
intended--for example, typing "to" for "too", "casual" for "causal", 
"desert" for "dessert", and so on. It is very difficult to write an 
algorithm to do this by hand. For instance, suppose we want to write an 
algorithm to correct confusions between "desert" and "dessert". We could 
write rules such as: "If the user types `desert` or `dessert`, and the 
previous word is `for`, then the user probably meant `dessert`". This rule 
would allow the algorithm to fix the error in: "I would like the chocolate 
cake for desert". The rule would not work, however, for many other cases 
in which "desert" and "dessert" were confused, for instance: "He wandered 
aimlessly through the dessert", where "desert" was probably intended. To 
fix this particular sentence, a different rule is needed, such as: "If the 
user types `desert` or `dessert`, and the previous two words are a 
preposition followed by the word `the`, then the user probably meant 
`desert`". In general, it is extremely difficult to write a set of rules 
by hand that will cover all cases. 
This difficulty of writing a set of rules by hand is the motivation for 
moving to adaptive algorithms--algorithms that learn to correct mistakes 
by being trained on examples. Instead of writing rules by hand, it is much 
easier to provide a set of examples of sentences that use "desert" and 
"dessert" correctly, and let the algorithm automatically infer the rules 
behind the examples. 
A wide variety of techniques have been presented in the Machine Learning 
literature for training algorithms from examples. However, what they all 
have in common is that they make the assumption of representativeness; 
that is, they assume that the set of examples that the algorithm is 
trained on is representative of the set of examples that the algorithm is 
asked to correct later. Put another way, they assume that the examples in 
the training and test sets are drawn, in an unbiased way, from the same 
population. It follows that whatever rules the algorithm learns from the 
training set will apply correctly to the test set. For example, if the 
training set contains examples illustrating that the word "for" occurs 
commonly before "dessert", but rarely before "desert", then, by the 
assumption of representativeness, the same distributional property of 
"for" should hold in the test set. If this assumption is violated, the 
algorithm's performance on the test set will degrade, because the rules it 
learned from the training set will not necessarily carry over to the test 
set. Existing machine learning techniques are therefore effective only to 
the extent that the training set is representative of the test set. This 
is a serious limitation, since, in general, there is no way to guarantee 
representativeness. 
SUMMARY OF INVENTION 
In order to provide for a more flexible method of correcting words in a 
text, in the subject system not only is a conventional training corpus 
used, but also the target text is analyzed to ascertain how the words to 
be corrected are used elsewhere in the text. Assuming that, on the whole, 
the words are used properly throughout the text, then when checking a 
particular occurrence of one of the words, the suggestion is made that the 
word take on the form of its usage in similar contexts that appear 
throughout the text. 
The subject system therefore provides a training procedure called sup/unsup 
which utilizes both a conventional training corpus and the target text to 
overcome this limitation of existing techniques, thereby enabling adaptive 
correction algorithms to work well even when the training set is only 
partially representative of the test set. 
The sup/unsup procedure works simply by training the algorithm, whichever 
adaptive correction algorithm is of interest, on both the traditional 
training set and the test set. It may seem, at first glance, to be 
counterproductive to train on the test set, as this set will presumably 
contain errors. However, the sup/unsup procedure is based on the 
assumption that although the test set contains errors, they will tend to 
be distributed sporadically through the test set; thus the learning 
procedure should still be able to extract correct rules, despite the 
presence of this noise. An example will clarify this concept. 
Returning to the problem of correcting context-sensitive spelling errors 
for the case of "desert" and "dessert", suppose the test set is a news 
article containing 24 occurrences of the phrase "Operation Desert Storm" 
and 1 occurrence of the incorrect phrase "Operation Dessert Storm". 
Following the sup/unsup procedure, the algorithm is trained on its usual 
training set plus this test set. The objective of training is to extract 
rules about when to use "desert" versus "dessert". The test set suggests 
the rule: "If the user types `Desert` or `Dessert`, and the previous word 
is `Operation`, and the following word is `Storm`, then the user probably 
meant `Desert`". This rule will work for 24 out of the 25 examples to 
which it applies. Although it is not perfect, it is reliable enough that 
the system can safely learn this rule. It can then apply the rule to the 
very same test set from which it was learned to detect the 1 occurrence of 
"Operation Dessert Storm" that violates the rule. 
The strength of this procedure is that it can detect sporadic errors, such 
as the single incorrect spelling "Operation Dessert Storm" in a test 
document, even if there are no relevant occurrences in the training 
set--that is, even if the training set is unrepresentative of the test 
set. One way to look at this procedure is that it is checking for 
inconsistencies in the test set, rather than "errors" with respect to some 
training set that is deemed error-free. The procedure is, of course, still 
able to detect errors that are illustrated by the original training set. 
The weakness of the procedure is that it cannot detect systematic errors 
in the test set. For example, if the user types "Operation Dessert Storm" 
every time, the system will be unable to find the error. 
It should be borne in mind that the effectiveness of the sup/unsup 
procedure depends on two factors. The first is the size of the test set; 
the larger the test set, the easier it will be to detect inconsistencies. 
For instance, in the example above, there were 24 correct occurrences of 
"Operation Desert Storm"; if instead the test set were much smaller and 
had only 2 occurrences, the algorithm might not have enough information to 
learn the rule about "Operation" and "Storm" implying "Desert". The second 
factor affecting the effectiveness of sup/unsup is the percentage of 
mistakes in the test set. In the example above, the user made 1 mistake in 
25 occurrences of "Operation Desert Storm"; if instead the level were 10 
or 15 out of 25, it would become difficult for the algorithm to learn the 
appropriate rule. 
It will be appreciated that the sup/unsup training procedure applies to any 
adaptive correction algorithm, regardless of the means used for 
adaptation, and regardless of the correction task under consideration. 
The term "adaptive correction algorithm" as used herein refers to 
algorithms that correct users' mistakes, e.g., context-sensitive spelling 
errors, and that learn to do their job of correcting mistakes by being 
trained on examples that illustrate correct answers and/or mistakes. 
More particularly, in one embodiment, the specific algorithm utilized for 
target text analysis involves scanning the full collection of training 
texts, which in this embodiment includes both a conventional training 
corpus, and the target text to which the system is being applied, so as to 
ascertain the features that characterize the context in which each word 
that is being corrected may appear. By features is meant two types of text 
patterns. The first type is called context words, and refers to the 
presence of a particular keyword within some fixed distance of the target 
word that is being corrected. For instance, if the words being corrected 
are "desert" and "dessert", then useful context words might include "hot", 
"dry", and "sand" on the one haled, and "chocolate", "cake", and "sweet" 
on the other hand. The presence of words in the former group within, for 
instance, 10 words on either side of the target word tends to indicate 
that "desert" was intended as the target word; whereas the presence of 
words in the latter group tends to imply that "dessert" was intended. 
The second type of feature is called collocations, and refers to the 
pattern of part-of-speech tags and specific words in the immediate context 
of the target word. For instance, if the words being corrected are again 
"desert" and "dessert", then one useful collocation might be "`PREPOSITION 
the` occurs immediately to the left of the target word". This collocation 
matches any sentence in which the target word, which is either "desert" or 
"dessert", is directly preceded by the word "the", which in turn is 
directly preceded by a word that has been tagged as "PREPOSITION". For 
instance, the collocation would match the sentence "He went to the 
desert", in which the target word, "desert", is immediately preceded by 
the word "the", which is immediately preceded by the word "to", which is 
tagged as a preposition. This collocation, when matching a sentence, tends 
to imply that "desert" was intended as the target word, and not "dessert". 
In one embodiment, the part-of-speech tags needed for this analysis are 
derived by a lookup procedure that utilizes a dictionary which lists, for 
any given word, its set of possible part-of-speech tags. A collocation is 
considered to match a sentence if each specific word in the collocation 
matches the corresponding word in the sentence, and if each part-of-speech 
tag in the collocation is a member of the set of possible part-of-speech 
tags of the corresponding word in the sentence. 
The subject system derives a set of features of the two types described 
above by scanning through the training texts for all occurrences of the 
words being corrected. For each such occurrence, it proposes as candidate 
features all context words and collocations that match that occurrence. 
After working through the whole set of training texts, it collects and 
returns the set of features proposed. In one embodiment, pruning criteria 
are applied to this set of features to eliminate features that are based 
on insufficient data, or that are ineffective at discriminating among the 
words being corrected. 
Having derived a set of features that characterize the contexts in which 
each of the words being corrected tends to occur, then by a conventional 
Bayesian method, these features are used as evidence to ascertain the 
probability that each of the words being corrected is in fact the word 
that the user intended to type. Having derived these probabilities, the 
word selected as correct is that word having the highest probability. For 
instance, if the word "desert" is used 100 times in a particular context, 
and if the word "dessert" is used either not at all or a limited number of 
times in the same context, then the subject system will select "desert" as 
the correct word in future occurrences of this context, even if the user 
typed "dessert". Bayesian analysis for context-sensitive spelling 
correction is described in the paper, "A Bayesian hybrid method for 
context-sensitive spelling correction", by Andrew R. Golding, in the 
Proceedings of the Third Workshop on Very Large Corpora, at the June 1995 
conference of the Association for Computational Linguistics, pages 39-53. 
Thus both a conventional training corpus and a special training corpus 
involving the target text are utilized to ascertain the correct spelling 
of a target word in the text. The conventional training corpus is merged 
with the target-text corpus so that context-sensitive spelling correction 
is based on both corpora. The result is that improved spelling correction 
is achieved through the analysis of the use of the word throughout the 
target text, as well as in the conventional training corpus. 
In summary, a system is provided for correcting users' mistakes including 
context-sensitive spelling errors and the like in which an adaptive 
correction algorithm is utilized which is trained on not only a 
conventional training corpus, but also on the text which is being 
corrected, thus to permit the correction of words based on the particular 
usages of the words in the text being corrected, taking advantage of the 
fact that the text to be corrected is by and large already mostly correct.

DETAILED DESCRIPTION 
Referring now to FIG. 1, a system 10 for correcting text includes a 
training phase 12, followed by a run-time processing phase 14. In the 
training phase, target text 16 is combined with a conventional training 
corpus 18 to provide a combined corpus 20 in which the corpus utilized 
includes the target text and therefore is exceedingly useful in tailoring 
the text-correction system to the text in question. 
The combined corpus is utilized in a feature-extraction step 22 in which 
selected features are culled from the combined corpus as illustrated at 
24. These features include context words and collocations, so that it is 
these features which provide evidence that allows the computation of the 
probability of each word that could have been intended for the target word 
in the target text. 
During run-time processing, a probability-based spelling-correction system 
30 is provided with the target text and determines first a target word and 
secondly the probability of the correctness of this word based on the 
combined corpus and the selected features. For instance, the list of 
selected features is matched against each occurrence of the target word in 
the target text, so as to collect evidence about the likely intended 
identity of the target word. The evidence is combined into a single 
probability for each word that could have been intended for the target 
word using Bayes' rule, in one embodiment. Other spelling-correction 
systems for use in determining the identity of the correct word include a 
system based on the Winnow algorithm which employs a multiplicative 
weight-updating scheme as well as a variant of weighted-majority voting. 
This technique is described in a paper entitled, "Applying Window to 
Context-Sensitive Spelling Correction" by Andrew R. Golding and Dan Roth, 
in Machine Learning: The Proceedings of the 13th International Conference, 
Lorenza Saitta, ed., Morgan Kaufmann, San Francisco, Calif., 1996. 
It can be seen that the spelling correction in step 30 is provided, in one 
embodiment, by a conventional Bayesian method which, rather than using a 
conventional training corpus alone, utilizes a corpus which includes the 
target text. The advantage of so doing is that the system for finding the 
probability of the correct word is enhanced by inspecting the target text 
for similar occurrences of the word so that a more powerful technique for 
obtaining the correct word is achieved. 
The result of the probability-based spelling correction is the suggestion 
of a word to be inserted in the text in place of the target word if the 
target word needs changing yielding a corrected text 32 as illustrated. 
Referring now to FIG. 2, feature extraction 22 is detailed such that in one 
embodiment, the output of the combined corpus 20 is coupled to a module 34 
which lists all possible context words and collocations as candidate 
features, utilizing a dictionary 36 of sets of part-of-speech tags. For 
instance, for the word "walks", the dictionary would give the set of 
part-of-speech tags consisting of "PLURAL NOUN" and "THIRD PERSON SINGULAR 
VERB". The process of listing all possible context words and collocations 
is illustrated by the sentence, "John lives in the desert", in which the 
target word is "desert", for which the user could intend either "desert" 
or "dessert". In this sentence, the set of possible part-of-speech tags 
for "in" consists of the single tag "PREPOSITION", while that for the word 
"the" consists of the single tag "DETERMINER". In this case, four context 
words and four collocations are proposed as candidate features. The 
context words are the words "John", "lives", "in", and "the", each of 
which is a word that occurs nearby the target word. The collocations are: 
"`in the` occurs immediately to the left of the target word"; 
"`PREPOSITION the` occurs immediately to the left of the target word"; 
"`in DETERMINER` occurs immediately to the left of the target word"; and 
"`PREPOSITION DETERMINER` occurs immediately to the left of the target 
word". These four collocations represent all ways of expressing the nearby 
context of the target word in terms of specific words and part-of-speech 
tags. 
Having provided a list of all possible context words and collocations as 
candidate features, as seen at 36, a module counts the occurrences of all 
candidate features in the combined corpus 20, followed by a pruning step 
at 38 to prune features that have insufficient data or are uninformative 
discriminators. By insufficient data is meant the number of occurrences of 
the feature in the training corpus is below a prespecified threshold, 
which, in one embodiment, is set to 10. By uninformative discriminator is 
meant that the presence of the feature fails to be significantly 
correlated with the identity of the target word, as determined by a 
chi-square statistical test, which, in one embodiment, is set to the 5% 
level of significance. The result is a list of features 40 to be utilized 
in the run-time processing for probability-based spelling correction. 
Referring now to FIG. 3, the system 30 for performing probability-based 
spelling correction from target text 16 and features 40 includes, as a 
first step, finding the next occurrence of a given target word as 
illustrated at 42. Upon a determination at 44 of the occurrence of the 
target word in the target text, module 46 initializes the probability of 
each word, w.sub.i, that could have been intended for the target word. In 
one embodiment, the probability of each word, w.sub.i, is set to the ratio 
of the probability that the word occurred in the combined corpus to the 
total probability that any of the words w.sub.i occurred in the corpus. 
Having initialized the probability of each word, w.sub.i, module 48 finds 
the next feature that matches the occurrence of the target word. The 
inputs to this module are features 40 and the dictionary of sets of 
part-of-speech tags 36. What is happening is that having found the 
occurrences of the target word, the system now finds which features in its 
list of possible features match each occurrence of the target word. The 
utilization of features enhances the robustness of the system in that not 
only must the probability be based on the target word occurrence, it must 
also be based on the presence of features that match that target word 
occurrence. 
Assuming that the next feature that matches the occurrence is found, then 
module 58 updates the probability of each word, w.sub.i, that could have 
been intended for the target word, using Bayes' rule. The probability 
update is performed to adjust the probability for each word, w.sub.i, so 
as to take into account the evidence about the likely identity of the 
target word that is provided by the feature that matched the target word 
occurrence. As a result, when all features that match the target 
occurrence have been processed, a probability will have been calculated, 
based on the context of the target word, that measures the probability 
that each word w.sub.i is the word that was intended for the target word 
given the context in which it occurred. This is done by gathering the 
evidence from the features that matched the occurrence of the target word. 
In the illustrated embodiment, Bayes' rule is utilized to update the 
probability of each word, w.sub.i, based on a feature match with the 
target text. Bayes' rule is given by the following formula: 
##EQU1## 
where F is the set of features that matched the occurrence of the target 
word; P(w.sub.i .vertline.) is the probability that word w.sub.i was 
intended, given that the set F of features has been found to match the 
target occurrence; P(w.sub.i) is the so-called prior probability of word 
w.sub.i, which is the value to which the probability for word w.sub.i was 
initialized in 46; P() is a scaling factor that need not be used as it 
does not affect the final outcome of the computation; and each term 
P(.function..vertline.w.sub.i) is a so-called likelihood term that is used 
to update, at 58, the probabilities of the words w.sub.i given that 
feature .function. has been found to match the target occurrence, and is 
calculated from the number of occurrences of feature .function. in the 
combined corpus. 
If the result of the test at 50 is that no feature that matches the target 
occurrence was found, then, as illustrated at 52, the correct word 
selected is that word, w.sub.i, with the highest probability. It will be 
appreciated that when a word is selected as being correct by module 52, 
this word is entered into a text buffer 56 into which has previously been 
loaded the original target text. Following the selection by module 52 of 
the word, w.sub.i, with the highest probability, the system iteratively 
cycles back to find the next occurrence of a target word in the target 
text, with the iteration continuing until all such occurrences have been 
processed. At this time, when no more occurrences are found, the text 
buffer 56 will contain the original target text, as modified by all 
spelling corrections made during the spelling-correction procedure. 
Corrected text 54 is therefore generated through the readout of the text 
buffer 56 as illustrated at 60 at the end of the sequence. 
In summary, a combined corpus is formed in the training phase in which the 
target text is an integral part of the combined corpus and specially 
tailors the corpus to the text under consideration. Having formed the 
combined corpus, selected features are extracted to enable a more robust 
calculation of the probability that a given word is the correct word in 
the context of the target occurrence. By considering those words that 
could have been intended for the target word, as well as features, one can 
provide more accurate probabilities in a run-time sequence for text 
correction. Utilization of context words and collocations as features is 
by virtue of example only, as other features are within the scope of this 
invention. 
Moreover, the method for selecting probabilities, while being described in 
terms of a Bayes' rule iterative process, is but one of a number of 
techniques for determining the probability of a word as being correct in a 
particular context. 
The C code for the subject system follows, in two parts: feature 
extraction, and spelling correction. Code for feature extraction: 
##SPC1## 
Having above indicated several embodiments of the Subject Invention, it 
will occur to those skilled in the art that modifications and alternatives 
can be practiced within the spirit of the invention. It is accordingly 
intended to define the scope of the invention only as indicated in the 
following claims: