六、维特比算法（Viterbi Algorithm）
维特比算法程序示例
仍然需要说明的是，本节不是这个系列的翻译，而是作为维特比算法这一章的补充，将UMDHMM这个C语言版本的HMM工具包中的维特比算法程序展示给大家，并运行包中所附带的例子。关于UMDHMM这个工具包的介绍，大家可以参考前向算法4中的介绍。
维特比算法程序示例如下（在viterbi.c中):
void Viterbi(HMM *phmm, int T, int *O, double **delta, int **psi,int *q, double pprob)
{
int i, j; / state indices /
int t; / time index */
int maxvalind;
double maxval, val;
/* 1. Initialization */
for (i = 1; i <= phmm->N; i++)
{
delta[1][i] = phmm->pi[i] * (phmm->B[i][O[1]]);
psi[1][i] = 0;
}
/* 2. Recursion /
for (t = 2; t <= T; t++) { for (j = 1; j <= phmm->N; j++)
{
maxval = 0.0;
maxvalind = 1;
for (i = 1; i <= phmm->N; i++)
{
val = delta[t-1][i](phmm->A[i][j]);
if (val > maxval)
{
maxval = val;
maxvalind = i;
}
}
delta[t][j] = maxval*(phmm->B[j][O[t]]);
psi[t][j] = maxvalind;
}
}
/* 3. Termination */
*pprob = 0.0;
q[T] = 1;
for (i = 1; i <= phmm->N; i++)
{
if (delta[T][i] > pprob)
{
pprob = delta[T][i];
q[T] = i;
}
}
/* 4. Path (state sequence) backtracking */
for (t = T - 1; t >= 1; t--)
q[t] = psi[t+1][q[t+1]];
}
在UMDHMM包中所生成的4个可执行程序中，testvit是用来测试维特比算法的， 对于给定的观察符号序列及HMM，利用Viterbi 算法生成最可能的隐藏状态序列。这里我们利用UMDHMM包中test.hmm和test.seq来测试维特比算法，关于这两个文件，具体如下：
test.hmm：
M= 2
N= 3
A:
0.333 0.333 0.333
0.333 0.333 0.333
0.333 0.333 0.333
B:
0.5 0.5
0.75 0.25
0.25 0.75
pi:
0.333 0.333 0.333
test.seq：
T= 10
1 1 1 1 2 1 2 2 2 2
对于维特比算法的测试程序testvit来说，运行：
testvit test.hmm test.seq
结果如下：
------------------------------------
Viterbi using direct probabilities
Viterbi MLE log prob = -1.387295E+01
Optimal state sequence:
T= 10
2 2 2 2 3 2 3 3 3 3
------------------------------------
Viterbi using log probabilities
Viterbi MLE log prob = -1.387295E+01
Optimal state sequence:
T= 10
2 2 2 2 3 2 3 3 3 3
------------------------------------
The two log probabilites and optimal state sequences
should identical (within numerical precision).
序列“2 2 2 2 3 2 3 3 3 3”就是最终所找到的隐藏状态序列。好了，维特比算法这一章就到此为止了。
网友评论