# Can someone please explain these word probability formulas to me?

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.

# 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.

-

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.

-
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. –  Barry Fruitman May 23 '12 at 22:55
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. –  Michael Chernick May 23 '12 at 23:09
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. –  Michael Chernick May 23 '12 at 23:09
Thanks, Michael. :) –  Barry Fruitman May 24 '12 at 0:28