The Lighter Aspects Of Decision Theory

We’ve pretty well exhausted all I want to say on the differences between conjectures, hypotheses, and theories for the time being. Readers are still weighing in with their comments. So I might distill them down in another posting. Also, I’ve got some comments of the difference between faith and knowing. We can explore that later, also. You will find that I respect both and can show my reasons for saying these two concepts are indeed different and we need both.

However, let’s go back to some of the lighter aspects of decision theory and its consequences along with a healthy dose of puzzles that are recreational with the possibility of insight.

Have you ever wondered how a spellchecker works? If you type a word and it is not recognized as being in the dictionary, how does the checker decide which valid words to suggest? There’s obviously an element of decision theory here because the checker must make decisions according to some algorithm as to which words are closest to what was meant.

In the worksheet for a programming class, the instructions for writing a spellchecker were to compare the word with a dictionary and if it didn’t match, then

Replace any one letter with another.
Insert a new letter somewhere in the word.
Delete a letter somewhere in the word.
Transpose two adjacent letters.

At each step, compare the doctored word with the dictionary to see if there is a match, and if so, list it as an alternative. The instructor who listed this operation likely did so in terms of the “edit-distance,” which I will not define accurately here, but for our purposes, it is the number of keystrokes that must be off to produce the error. Obviously typing the wrong letter is more likely than mistyping two letters, etc. And mistyping a single letter is probably more likely than inserting an extra letter.

But the listing of these types of errors and arranging them in expected order of occurrence hides the assumptions we made to get them in the first place. For instance, the probability of transposing two letters is known from psychological studies to be a common type of error. Having the type of a priori knowledge about how humans err is a valuable tool in setting up the checking algorithm. That is, by listing the types of errors likely to be made and arranging them in order of expected probability, we have made many assumptions based on our own experiences.

There are some other assumptions in the assignment. For instance, it assumes that spelling errors can result in two types of misspellings: non-word producing errors, and real-word producing errors. So a mistyped error that is in the dictionary cannot be corrected unless the spellchecker is integrated with a syntax checker.

For non-word producing errors, the best a checker can do is to find the closest neighbors to the non-words that are also in the dictionary. To do this, one must first define a way of organizing arrays of letters such that a distance metric can be defined to select the nearest neighbors. Once that is done, the rest is simple.

While there are many ways to do this, a common way is to treat the non-word as a vector a vector in some hyperspace. For instance, each letter gives the projection of that vector onto an axis. WLG, the axes can be labeled in sequence with the position of the letter in the word. For example, “HTE” would be a three-dimensional vector with length “H” along axis 1; length “T” along the second axis, and length “E” along the third. The alternate vector “THE” has the same total length, but is oriented as a different angle. (Typing “HTE” for “THE” is called a typographic error as opposed to a cognitive error such as using the wrong word entirely. Typing “two” for “too” is probably a cognitive error since “w” is way across the keyboard from “o.”)

When this is done correctly, a distance metric can be defined which incorporates the known types of errors biased in a heuristic way to account for known human foibles. Then for a given non-word, the nearest neighbors that are real words can be displayed for you to select which you wanted. Think of the nearest neighbors as those that lie on the surface of a hyper-sphere centered on the incorrectly typed word. Start by considering spheres of radius one in this letter space. Color non-word nearest neighbors black and real-word nearest neighbors red. Then spellchecking is simply finding the red nearest neighbors that lie on the surface.

But what happens if none of the selections are what you meant? Most checkers have a “More” option. When you activate that, the checker simply repeats the process with radius 2 to give you more choices. As you might guess, expanding the radius increases the surface area of the hyper-sphere, so there are many more likely intersections with real words. For that reason, the “More” function usually has a lot of choices.

Obviously this only scratches the surface of spellchecking. Commercial checkers incorporate more complex decision making.

For those who wish to delve further into decision theory without wading through a lot of equations, I have posted a tutorial on elementary decision theory. It shows examples of faulty physicians’ diagnoses (important for those considering surgery) and how to evaluate anti-terrorist activities (important for everyone). That tutorial can be found here.