Can someone please explain these word probability formulas to me?

Question

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) = log₂ 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) = MAX_{phrase.startsWith(prefix')} editDistance.distance(prefix,prefix') + log₂ 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.

Answer 1

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.

Answer 2

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.