I want to use HMM with Viterbi Algorithm to correct typographical errors, I calculated the required probability but when I apply Viterbi algorithm I got very bad results, I checked the code line by line and I couldn't find the error
public ForwardViterbi(string[] states, string[] observations, double[] startProbability, double[,] transitionProbability, double[,] emissionProbability, double scaleFactor)
{
this.states = states;
this.observations = observations;
this.startProbability = startProbability;
this.transitionProbability = transitionProbability;
this.emissionProbability = emissionProbability;
this.scaleFactor = scaleFactor;
}
//----------------------------------------------------------------------
//The Methods
public void Process(int[] problem)
{
double[,] T = new double[states.Length, 3]; //We will store the probability sequence for the Viterbi Path
vPath = new int[problem.Length];
vProbs = new double[problem.Length];
//initialize T
//------------------------------------------------------------------
for (int state = 0; state < states.Length; state++)
{
T[state, 0] = startProbability[state];
T[state, 1] = state;
T[state, 2] = startProbability[state];
}
for (int output = 0; output < problem.Length; output++)
{
double[,] U = new double[states.Length, 3]; //We will use this array to calculate the future probabilities
Console.WriteLine("\nTesting hypothesis {0} ({1})", output, observations[problem[output]]);
double highest = 0;
for (int nextState = 0; nextState < states.Length; nextState++)
{
double total = 0;
double argMax = 0;
double valMax = 0;
Console.WriteLine(" Estimating probability for future state {0} ({1})", nextState, states[nextState]);
for (int state = 0; state < states.Length; state++)
{
Console.WriteLine(" The testing state is {0} ({1})", states[state], state);
double prob = T[state, 0];
double v_path = T[state, 1];
double v_prob = T[state, 2];
double p = emissionProbability[state, problem[output]] * transitionProbability[state, nextState] * scaleFactor;
prob *= p;
v_prob *= p;
total += prob;
if (v_prob > valMax)
{
valMax = v_prob;
argMax = nextState;
}
Console.WriteLine(" VProbability of {0} is {1} with scale {2}^{3}", states[nextState], v_prob, scaleFactor, output + 1);
if (v_prob > highest)
{
highest = v_prob;
vPath[output] = nextState;
vProbs[output] = v_prob;
}
}
U[nextState, 0] = total;
U[nextState, 1] = argMax;
U[nextState, 2] = valMax;
}
T = U;
Console.WriteLine("The highest probability was {0} in state {1} (scale factor of {2}^{3})", highest, states[vPath[output]], scaleFactor, output + 1);
}
//Apply SumMax
double Total = 0;
double ValMax = 0;
for (int state = 0; state < states.Length; state++)
{
double prob = T[state, 0];
double v_path = T[state, 1];
double v_prob = T[state, 2];
Total += prob;
if (v_prob > ValMax)
{
ValMax = v_prob;
}
}
Console.WriteLine("\nAnalysis: Total probability (sum of all paths) for the given state is :: {0}\nThe Viterbi Path Probability is :: {1}", Total, ValMax);
Console.WriteLine("The above results are presented with a scale factor of {0}^{1}", scaleFactor, problem.Length);
}
I've just checked this implementation and the one published on wikipedia. This one doesn't seem to work. The one on wikipedia does work. If you want - you can compare them, but I'm lazy to do this.
(I've implemented solution for exactly your problem as described here)