我爱自然语言处理(ZZ)

http://www.52nlp.cn/hmm-learn-best-practices-six-viterbi-algorithm-5

六、维特比算法(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”就是最终所找到的隐藏状态序列。好了,维特比算法这一章就到此为止了。

下一讲:前向-后向算法

本文翻译自:http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html

转载请注明出处“我爱自然语言处理”:www.52nlp.cn

本文链接地址:http://www.52nlp.cn/hmm-learn-best-practices-six-viterbi-algorithm-5

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s