Viterbi experiments

I implemented the Viterbi algorithm and my results are not good yet but I am optimistic. Here is the setup:

I have 7 test images, here is the roster:

lyndon johnson
george bush
gerald ford
richard nixon
william clinton
ronald reagan
james carter

The names are all lower case because I'm not taking case into account yet.

I have calculated the transition probabilities - so I have a 26x26 matrix containing the probability of transitioning from 1 character to another. Here is how I calculated that:

P(o|e) = Count(oe) / Count(e)

This means that the probability that I see the sequence "oe" is the number of times I saw the sequence "oe" divided by the number of times I just saw the letter "e".

Emission probabilities, in my case, are supposed to mean "the probability of seeing this character image given that I know what the character is". For example, the probability of seeing this character image given that I know it is an 'a'. That probability is hard to calculate, I would have to use Gaussians and other crazy math. So, instead of doing that, for now I am doing a very simple nearest neighbor probability calculation. Given a character image, I run nearest neighbor against all of my training data and take the top 40 votes. I say that the probability that this character is an 'a' is the amount of votes for 'a' + 1 divided by 40 + 26. Ideally I would just say that the probability that this character is an 'a' is the amount of votes for 'a' / 40. However, my nearest neighbor framework is working pretty poorly so just because I have no votes for 'a' I don't want to completely eliminate this possibility. Therefore, no letter has zero probability.

I thought that even though my nearest neighbor framework is working pretty badly, that the transition probabilities would help out a lot because the roster is so small. Not really the case though!

Here is an example of an input name:




Here is what my algorithm came up with for the name:
licallinilicl

Yeah, pretty bad. At first I was like "are those even valid transitions?!" but it's true, each of those transitions are valid. For example "li", "William" is in the roster. So, I need to figure out a way to take more into account than just the bigrams. Maybe I should have an "isPrefix" function such that as I'm going through the HMM, only give something a probability if it is a valid prefix of a name. Ok that is what I will do next.