HMM学习最佳范例六:维特比算法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

此条目发表在隐马尔科夫模型分类目录,贴了, , , , , , , , 标签。将固定链接加入收藏夹。

HMM学习最佳范例六:维特比算法5》有 13 条评论

  1. Pingback引用通告: 我爱自然语言处理(ZZ) | Shirley's Blog

  2. 张知临说:

    博主,再麻烦你请教几个问题:
    1、关于这个程序:为什么 psi 要定义为 int 型的矩阵呢?他存储的不是反向指针的结果吗?这个不应该也是double值吗?
    2、/* 3. Termination */ 和/* 4. Path (state sequence) backtracking */ 没有太看懂什么意思?如果把delta矩阵全部计算出来之后,那么我只要选取每列中最大的值就可以得到最佳状态序列了,为什么还要步骤3和4 呢?

    [回复]

    陈伟 回复:

    博主很忙.所以回答很简略 : )
    两个问题其实可以合起来回答
    最后一列是选的最大值,但是倒数第二列不一定是最大值,要看最后一列的. 如果最后一列的最大值计算,使用的是倒数第二列次大值.那么倒二的最大值就要靠边站了. 为啥次大值能这么嚣张? 程序里的这行代码: val = delta[t-1][i]*(phmm->A[i][j])告诉我们一切. : ) 也就是说,除了看值,还要看转移概率phmm->A[i][j].而psi数组保存的就是位置信息.比如次大值在第三个状态,那么psi[t][q[t]] = 3.

    程序的第三步是获取最终的最大值.而第四步是从psi中不断回溯获取上一层节点的状态位置.

    [回复]

    52nlp 回复:

    o(∩_∩)o 哈哈

    [回复]

  3. 52nlp说:

    “psi[t][j] = maxvalind”, psi记录的是最大值的位置信息,是int值;
    第3\4步目的是找全局最优的状态,可以再看看前面viterbi算法的描述。

    [回复]

  4. nlp说:

    您好,看过很多隐马尔可夫模型的资料,没有具体去做工程实践,现在理解起来还是有些盲点,期待与版主交流,可以加你为qq好友吗?

    [回复]

    52nlp 回复:

    抱歉,工作很忙,不加qq。如果有问题,可以贴在这里。

    [回复]

  5. mcnlp说:

    您好,请问,这个源程序的代码哪里有下载?

    [回复]

    52nlp 回复:

    可以看这个链接:
    http://www.52nlp.cn/several-different-programming-language-version-of-hmm

    [回复]

    mcnlp 回复:

    谢谢

    [回复]

  6. anlp说:

    六、维特比算法(Viterbi Algorithm)

    维特比算法程序示例

    void Viterbi(HMM *phmm, int T, int *O, double **delta, int **psi,int *q, double *pprob)
    {
    ……
    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;

    貌似维特比算法程序示例中计算delta的方法和公式中的不一样,
    上述示例代码中给出好像是另一个公式:
    delta[t+1][j]=MAX(delta[t][i]*a[i][j])*b[j][O[t]]
    这两个哪一个对?

    [回复]

    pengi 回复:

    是因为之前有这么一段

    /* 0. Preprocessing */

    for (i = 1; i N; i++)
    phmm->pi[i] = log(phmm->pi[i]);
    for (i = 1; i N; i++)
    for (j = 1; j N; j++) {
    phmm->A[i][j] = log(phmm->A[i][j]);
    }

    biot = dmatrix(1, phmm->N, 1, T);
    for (i = 1; i N; i++)
    for (t = 1; t B[i][O[t]]);
    }

    可以看到delta, a, biot这些都被取对数处理过了,所以相乘变成了相加。

    [回复]

    pengi 回复:

    我认为:
    val = delta[t-1][i]*(phmm->A[i][j]);
    计算从t-1时刻到t时刻,状态从i到j的概率,通过冒泡排序得到最大的概率。
    delta[t][j] = maxval*(phmm->B[j][O[t]]);
    然后这一步用最大概率与发射概率相乘

    B[j][O[t]]与求最大的i没有关系,可以把它放到for循环之外。

    其实就是这样的
    delta[t+1][j]=MAX(delta[t][i]*a[i][j])*b[j][O[t+1]]

    [回复]

发表评论

电子邮件地址不会被公开。 必填项已用*标注