Random "words" game I was thinking about a problem and I did not know how to search for relevant theory behind it so hopefully someone can help me. 
Suppose you are playing a game, where someone thinks of an object and he types its name and sends it to you so you can find out which object he is thinking of. However, even though the intention is for you to be able to guess the object correctly, the string that arrives to you has random errors. (eg He was thinking of "mathematics" and he sent "math'atics" or even "maths")
Suppose now you have been playing this game with someone for a while and you have collected a large pool of messages and classified them accordingly (with labels the name of the object they are trying to describe). 
Now a new string with random errors arrives.
Can I somehow calculate the probability that I would observe this string given it is trying to describe a particular class? 
So thinking of the string that arrives at you as a random variable that depends on the object it is trying to describe, can I approximate somehow its distribution? 
For example, suppose the true word is "Mathematics". I collect and classify these strings: ["math", "mthmatcs","Mathemat;cs","matematsat"] = "Mathematics"
then "aPMthmtcs!" or "W?MAthemtics@" arrives. It doesn't belong in the set of previous observed words however it contains sequences of letters that seem to be very "probable" when you are in "Mathematics". Can this be made somehow rigorous?
I hope this is clear enough. Sorry for long post.
 A: A simple-minded but possibly good-enough solution to this problem is to compare each new string to every string in your training data with Levenshtein distance, and return the class of the closest string. This can be thought of as a 1-nearest-neighbor classifier, and extended to $k$-nearest neighbors if you wish; a $k$ such as 3 or 5 might be more accurate than 1.
A: I would consider approaching it from an information theoretic point of view. The twist wrt information theoretic approaches is that they are momentless and rooted in metrics such as Kullback-Lieber, mutual information criterion, minimum distance length, distance correlations, and more (take your pick). 
There are several routines out there that would enable the compilation of a matrix of distance or similarity functions for non-numeric objects such as text strings. Then, based on that matrix use PCA or some related dimension reduction algorithm to create a set of component combinations. Once that's done, the final step would be to develop a "regression" model producing coefficients or weights that could be used to score new text objects and, based on their similarity to the original objects, make a probabilistic assignment(s).
The routines are out there. The one I'm most familiar with is Andreas Brandmaier's PDC (permutation distance clustering). In addition, Brandmaier has developed an R module for implementation. In his several papers, he goes into much greater theoretical depth than I am able to in this short note. This approach is worth a look and he has many ungated papers out there about it on his website at the Max Planck Institute in Germany. 
