-
Today we're gonna talk about spelling
correction. Lots of applications make use
-
of spelling correction. For example, word
processing, almost any modern word
-
processor will take a misspelled word like
component with an A and give you
-
suggestions like component with an E and
automatically replace it for you. Modern
-
search engines will not only flag an
error. So, language spelled without a u,
-
here. But, give you, the results, as if
you had spelled the word correctly. And,
-
modern phones additionally will
automatically find misspelled words. Here,
-
I typed l-a-y-r, and it replaced it
automatically, or suggests a replacement,
-
with late. We can distinguish a number of
separate tasks and spelling correction.
-
One is the detection of the error itself.
And then the correction of the error once
-
you've found it. And we can think about
different kinds of correction. We might
-
automatically correct an error if we're
positive that the error that we know the
-
right answer for the error. So H-T-E is a
very common misspelling for the, and so
-
many word processors automatically correct
H-T-E. We might suggest a single
-
correction if we're, there's only one very
likely correction, or we might suggest a
-
whole list of corrections and let the user
pick from among them. We distinguish two
-
different classes of spelling errors. Non
word errors are errors in which the, what
-
the user types is not a word of English.
So g-r-a-f-f-e a misspelling let's say for
-
giraffe is not a word of English. By
contrast, real word errors. Are errors in
-
which then the resulting. [sound]
Misspelling is actually a word of English
-
and that makes them somewhat harder to
detect. And we can break up real word
-
errors into ones produced by really
typographical processes. These were meant
-
to type three. And typed [inaudible] let's
say. Or cognitive errors, where the user,
-
meant to type a word like [inaudible] and
instead typed a homophone of a, of the
-
word, or \u201ct-o-o\u201d instead of
[inaudible] And in both cases what, what's
-
produced is a real word of English, but by
modeling the differences between these
-
kind of errors, we might come up with
better ways of fixing them both. How
-
common are spelling errors? Depends a lot
on the task. So in web queries, spelling
-
errors are extremely common. So
practically one in four words in a web
-
query are likely to be misspelled. But in
web processing tasks on phones it's much
-
harder to get an accurate number. So
there's been a number of studies and most
-
of these studies are done by retyping. You
give the user a passage to type and then
-
you measure how well they, they type it.
And, of course, that's not quite the same
-
user's naturally writing messages or
typing. Nonetheless If you ask users to
-
retype and you don't let them use the
backspace key, they make about thirteen
-
percent of the words, thirteen percent of
the words are in error. So indicating that
-
if, that a lot of words. They correct
themselves with the backspace. If you let
-
them correct, now we're trying to
experiment on a, on a p d a style phone
-
site, organizer, they'll correct about
seven percent of the words themselves.
-
They'll still leave about two percent of
the words uncorrected, on the organizer.
-
And, similar numbers on people doing
retyping on a regular keyboard. So, the
-
numbers are about two percent where people
typing. And probably a much higher number
-
for web queries and probably a much higher
number for people texting. Are the kind of
-
spelling, spelling error [inaudible] that
we see. How do we detect non word spelling
-
errors. The traditional way is just to use
a large dictionary. Any word not in the
-
dictionary is an error. And, the larger
the dictionary, it turns out the better
-
this works. For correcting these non-word
spelling errors, we generate a set of
-
candidates that's real words that are
similar to the error. And then we pick
-
whichever one is best. And we'll talk
about the noisy-channel probability model
-
of how to do that. And it's also related
to another method called the shortest
-
weighted [inaudible] distance myth. So we
find the words that are not in the
-
dictionary. For each one, we generate a
set of candidates. Those are going to be
-
real words that are similar, we'll talk
about what similar means, to that error
-
and then we'll pick the best one. For real
word spelling errors, the algorithm is
-
quite similar. Again, for each word we
generate a candidate set. But now we do
-
this for every word in a sentence, not
just the words that are not in some
-
dictionary. So real word spelling error
correction, we don't use a dictionary
-
because of course the errors are in a
dictionary. So that wouldn't help. So, for
-
every word, we generate a candidate set.
So we might find candidate words with
-
similar pronunciations, we might find
candidate words with similar spellings,
-
and depending on the algorithm, exactly.
And it's very important that we're gonna
-
include the word itself, in the candidate
set, because the every word might be a
-
misspelling of some other real word, or it
might be the correct word. In fact, most
-
words are probably correct. So, for each
candidate set of each possible error,
-
we're gonna include the word itself. And
most of the time, in fact, we're gonna
-
pick that. And again, how we pick the
words we might use the noisy channel
-
model. We might use a classifier, we'll
talk about that so we'll discuss the
-
different methods of detecting these
errors and correcting them in the next
