1
$\begingroup$

I'm working on a word-prediction/spelling-correction software project and I need to calculate the probability that a dictionary word is what the user meant to type, referred to as a "score". I found an article that explains how to score matches using statistical techniques, but I don't understand it 100% (I'm not stats-savvy). I hope it is easy for you to understand!

First, some definitions:

prefix: What the user typed. It is called a prefix because it is usually incomplete since we score words as the user types in order to provide predictions.

word: A word from the dictionary.

probability: The frequency of a word in the language, expressed as the number of times it appears in a codex. The probability distribution is quasi-logarithmic, as you may expect.

edit distance: A measure of the number of errors (i.e. typos) between prefix and word. It is an integer <=0 where 0 = no typos.

score: The article refers to two types of score. score(prefix,word) (which I will refer to as prediction score) is the probability that word is what the user is typing. It is a function of word probability and edit distance. I think score(word) (which I will refer to as word score) is just word probability, normalized somehow.

What I don't understand:

The formulas below, especially p'(word) and score(prefix,word). Can someone please dumb down both the formulas below? I'm sure I can understand them with a little help. If you need more detail I'll do my best to provide it.

Thanks in advance...

The article

Scores for words are defined by the log (base 2) of their probability estimates:

score(word) = log2 p'(word)

where probabilities are estimated using maximum likelihood:

p'(word) = count(word) / Σword' count(word')

Additive smoothing may be easily carried out on the inputs, so it is not carried out here.

The score for a prefix matching a word is given by:

score(prefix,word) = MAXphrase.startsWith(prefix') editDistance.distance(prefix,prefix') + log2 p'(word)

In words, the score for a prefix matching a word is the sum of log probability of the word plus the edit distance between the prefix and the best matching prefix of the word. The edit distances should thus be scaled as log probabilities in order to combine with the phrase probabilities properly.

$\endgroup$

2 Answers 2

2
$\begingroup$

Okay they say p-word is is the probability that come about from what is called the likelihood equation. The data is the given prefix. The likelihood is given the prefix the probability that to prefix corresponds to a given word. So for example suppose someone typed yuo. A very likely word would be you since o and u are close on the keyboard and in typing the key for o may have accidently been hit first. Another possibility is your. That could occur if the same mistake was made with the o and the u but the person forgot to type the r or hit it too softly. Based on this description you would have a higher likelihood than your. But to quantify this statistically what is done is that you collect lots of typing samples that covers many words and many typos for the words. You find out what the intended word was. So your likeihood for each word is the number of times the actual word is you when yuo is typed divided by the total numner of times yuo occurs. Perhaps that would be 0.80 in this case and 0.15 for your when yuo occurs. Now this could be refined based on sentence structure and context but hat become much more complicated and is not what they are doing here. In this case we say that the probability that the word is you given that yuo is typed is 0.80 and for your it is 0.15. Since you has the highest probaility we call it the maximum likelihood estimate for the correct word given the data yuo. So what they cll p-word would in this case be 0.80 for the word you. Now for some reason not completely clear to me they choose to score the word log base 2 of 0.80. That means the score is the value x so that 2 raised to the power x is 0.80. Using Excel you can determine that x=0.32200 approximately. Since the log is a monotonic function meaning as p increases x always increases the highest likelihood will correspond to the highest score. I hope this give you a good feel for what is going on with the statistics.

$\endgroup$
3
  • $\begingroup$ Thank you. :) I understand the typing concepts in your explanation (e.g. transposed characters) but it's the formulas I don't understand. I get them fundamentally, but not enough to program them in computer code. Specifically, what does "MAXphrase.startsWith(prefix') editDistance.distance(prefix,prefix')" mean? P.S. I think the reason they use log base 2 is because word probability has a logarithmic distribution but edit distance doesn't, so they use log2() on the former before summing. $\endgroup$ May 23, 2012 at 22:55
  • 1
    $\begingroup$ I am a statistician. I can tell you about the probabilities and statistical concepts underlying the likelihood equations and such. I don't know the specifics of how they program it or anything like that. Your initial question was what does p'(word) mean and I explained that. Also I can see what score(word) means. That other term in score(prefix,word) doesn't suggest anything to me. $\endgroup$ May 23, 2012 at 23:09
  • $\begingroup$ I can only guess that in addition to the score for the word something about the closeness of the prefix in question ot other prefixes that near is factored into the score additively. But I don't understand why that isn't redundant. $\endgroup$ May 23, 2012 at 23:09
1
$\begingroup$

After thinking this over I realize the score formula is something like what I guessed and the distance term is not redundant. Let us concern the example of the yuo prefix again. Suppose p(you|yuo)=0.80 and P(your|yuo)=0.15 and P(yours|yuo)=0.05. now conisder another scenario where our data suggest that p(you|yuo)=0.80 and p(your|yuo)=0.05 and p(yours|yuo)=0.05 and all other words have probabilities <0.05. Then even though you has the same p in each case the score for you should be higher in thesecond case because all the competing word are more distant in their probabilities. So it makes sense to add a dsitance score that would add more in the second scenario compared to the first.

$\endgroup$
3
  • $\begingroup$ Hi Michael, thanks for the update. The distance term is definitely not redundant because p'(word) is only probability of a CORRECTLY-SPELLED word within a language/codex. The edit distance used in p'(prefix|word) factors typos into the probability. Thus the score is a function of how probable a dictionary word is, minus its distance from the prefix. A great example is the prefix "yo". The user may have meant to type "to", which has a very high-probability, with an edit distance of 1 from the prefix. (cont...) $\endgroup$ May 25, 2012 at 16:39
  • $\begingroup$ ... Or he may be in the middle of typing "you", which is slightly less probable, also with an edit distance of 1 (if you consider "u" to be a missing letter). Finally, he may be typing the slang word "yo" which has an edit distance of zero, but also a very low probability. p'() (as I programmed it) scores "to" the highest, with "you" in close second place. $\endgroup$ May 25, 2012 at 16:39
  • $\begingroup$ @BarryFruitman Thanks for the updated information. After rethinking it I was very sure the distance part was not redundant. But the score works a little differently than I first thought but it is very sensible. $\endgroup$ May 25, 2012 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.