HMM学习最佳范例七:前向-后向算法5

七、前向-后向算法(Forward-backward algorithm)

  上一节我们定义了两个变量及相应的期望值,本节我们利用这两个变量及其期望值来重新估计隐马尔科夫模型(HMM)的参数pi,A及B:

fb12

  如果我们定义当前的HMM模型为fb13,那么可以利用该模型计算上面三个式子的右端;我们再定义重新估计的HMM模型为fb14,那么上面三个式子的左端就是重估的HMM模型参数。Baum及他的同事在70年代证明了fb15因此如果我们迭代地的计算上面三个式子,由此不断地重新估计HMM的参数,那么在多次迭代后可以得到的HMM模型的一个最大似然估计。不过需要注意的是,前向-后向算法所得的这个结果(最大似然估计)是一个局部最优解。
  关于前向-后向算法和EM算法的具体关系的解释,大家可以参考HMM经典论文《A tutorial on Hidden Markov Models and selected applications in speech recognition》,这里就不详述了。下面我们给出UMDHMM中的前向-后向算法示例,这个算法比较复杂,这里只取主函数,其中所引用的函数大家如果感兴趣的话可以自行参考UMDHMM。

前向-后向算法程序示例如下(在baum.c中):

void BaumWelch(HMM *phmm, int T, int *O, double **alpha, double **beta, double **gamma, int *pniter, double *plogprobinit, double *plogprobfinal)
{
  int   i, j, k;
  int   t, l = 0;

  double    logprobf, logprobb,  threshold;
  double    numeratorA, denominatorA;
  double    numeratorB, denominatorB;

  double ***xi, *scale;
  double delta, deltaprev, logprobprev;

  deltaprev = 10e-70;

  xi = AllocXi(T, phmm->N);
  scale = dvector(1, T);

  ForwardWithScale(phmm, T, O, alpha, scale, &logprobf);
  *plogprobinit = logprobf; /* log P(O |intial model) */
  BackwardWithScale(phmm, T, O, beta, scale, &logprobb);
  ComputeGamma(phmm, T, alpha, beta, gamma);
  ComputeXi(phmm, T, O, alpha, beta, xi);
  logprobprev = logprobf;

  do  
  {

    /* reestimate frequency of state i in time t=1 */
    for (i = 1; i <= phmm->N; i++)
      phmm->pi[i] = .001 + .999*gamma[1][i];

    /* reestimate transition matrix  and symbol prob in
        each state */
    for (i = 1; i <= phmm->N; i++)
    {
      denominatorA = 0.0;
      for (t = 1; t <= T - 1; t++)
        denominatorA += gamma[t][i];

      for (j = 1; j <= phmm->N; j++)
      {
        numeratorA = 0.0;
        for (t = 1; t <= T - 1; t++)
          numeratorA += xi[t][i][j];
        phmm->A[i][j] = .001 +
                 .999*numeratorA/denominatorA;
      }

      denominatorB = denominatorA + gamma[T][i];
      for (k = 1; k <= phmm->M; k++)
      {
        numeratorB = 0.0;
        for (t = 1; t <= T; t++)
        {
          if (O[t] == k)
            numeratorB += gamma[t][i];
        }

        phmm->B[i][k] = .001 +
                 .999*numeratorB/denominatorB;
      }
    }

    ForwardWithScale(phmm, T, O, alpha, scale, &logprobf);
    BackwardWithScale(phmm, T, O, beta, scale, &logprobb);
    ComputeGamma(phmm, T, alpha, beta, gamma);
    ComputeXi(phmm, T, O, alpha, beta, xi);

    /* compute difference between log probability of
      two iterations */
    delta = logprobf - logprobprev;
    logprobprev = logprobf;
    l++;

  }
  while (delta > DELTA); /* if log probability does not
              change much, exit */
 
  *pniter = l;
  *plogprobfinal = logprobf; /* log P(O|estimated model) */
  FreeXi(xi, T, phmm->N);
  free_dvector(scale, 1, T);
}

  
  前向-后向算法就到此为止了。

未完待续:总结

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

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

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

HMM学习最佳范例七:前向-后向算法5》有 34 条评论

  1. 游客说:

    很是好啊,谢谢楼主的分享,

    [回复]

  2. 52nlp说:

    欢迎常来看看!

    [回复]

  3. jumay说:

    楼主,你好。用Baum-welch算法来训练HMM模型时,只用输入隐藏状态的个数,观察向量的个数,观察序列,我有个几个疑问:
    1.单单靠这些,怎么来评估这个参数模型就是最优的?因为我用这个算法测试的时候,每次迭代次说都是1.
    2.
    现在我想利用HMM来做人体行为识别,我有一个基本行为库,其中包括三个行为(也就是隐藏状态):walk,run,jump;库中包括的是人体不同行为的轮廓,每个行为对应8个观察向量,也就是说此模型总共观察向量有32个。我该怎么训练HMM呢

    [回复]

    52nlp 回复:

    不好意思,晚上回来的比较迟。
    首先用Baum-welch算法来训练HMM模型本身得到的解是局部最优,而全局最优解。另外,只给出这几个条件用这个算法进行无监督训练的HMM模型效果应该很差。
    举个例子,在实际的词性标注应用中,也会辅之以词典词性信息或者词类信息才能得到一个相对较好的HMM词性标注模型。但就是这样,也没有从一个已经做好标注的小语料库中直接得到的HMM模型的准确率高。
    所以对于你的第2个问题,最好的方法是你能建立一个与实际问题相对应的训练集,譬如:
    O1/walk O2/jump O3/run O4/run …
    ….
    其中Oi是观察向量,从这样的训练集中直接计算生成一个HMM模型的效果估计会比利用Baum-welch算法来训练HMM模型好很多。

    [回复]

    jumay 回复:

    谢谢你!O(∩_∩)O~ 我再考虑一下

    [回复]

  4. jumay说:

    你好,楼主,我有一个问题:用上述bw算法来训练HMM的时候,按理说迭代次数是不同的,但是不管我的输入观察序列是多少,迭代次数都是1.为什么会这样

    [回复]

    52nlp 回复:

    没有仔细考虑这个问题,估计输入序列可能过短,可以试着用100长以上的序列试一下。不太清楚原因,在我讲的《HMM在自然语言处理中的应用一:词性标注3》中训练序列的长度是590。
    另外,觉得在umdhmm中直接使用Baum-welch算法来训练HMM模型只适用于教学举例,真正的应用中如果没有很好的训练集也应该辅之以一些辅助信息。

    [回复]

    jumay 回复:

    你好!谢谢你的答复。这个地方还是不太理解,即便是我辅助的有观察值对应的隐藏状态,比如说0/walk 2/walk 3/walk 8/run 9/run 10/run ,该怎么利用这些参数和bw算法进行有监督的训练呢

    [回复]

    52nlp 回复:

    这个可以参考“HMM在自然语言处理中的应用一:词性标注5”,直接计算HMM的各个参数值就可了。

  5. LayersSss说:

    博主,我一直没看懂baum-welch算法,即使是看着umdhmm的代码,博主提到的《A tutorial on Hidden Markov Models and selected applications in speech recognition》,是L.R.Rabiner的那一篇吗?
    我想应用hmm识别到图像匹配中去,训练时效果很差,所以想仔细理解一下训练用的算法。

    [回复]

    52nlp 回复:

    是这一篇论文,建议好好读读英文原始文献,我这里翻译的比较粗糙。
    另外除了多花一点时间琢磨这个算法外,所需要的一些基本数学知识也要了解一下。

    [回复]

  6. Beingspider说:

    博主你好,我有几个问题想向你请教,希望你给予指点,先谢谢了。
    1.我现在在做中文语料的词性标注,首先要用EM算法来估计AB矩阵,
    所以我要用到前后向算法,但是一次前后向算法之后,得到的两个前后向矩阵
    均溢出!(前后向算法就会溢出);
    2.关于EM算法初始值的选择,我怎样才能尽可能选择好的初始值呢?

    [回复]

    Beingspider 回复:

    第一个问题已经解决,我找了资料第二个问题主要是对B(发射概率)的初始化。博主有没有好的建议?或者能给我提供些关于K均值分割算法的资料,谢谢了。

    [回复]

    52nlp 回复:

    非常抱歉,这方面我没有什么经验,也没有这方面的资料!

    [回复]

    Beingspider 回复:

    呵呵,没事。还是要谢谢你。

  7. 请问WithScale是什么意思,有什么用说:

    在前向算法与后向算法中都分别有带WithScale的函数;比如在backward.c 中有两个函数,一个是Backward()一个是BackwardWithScale(),请问后者有什么用。本人比较菜,望博主能指点一二。谢谢

    [回复]

    52nlp 回复:

    从代码中看scale一个比例因子数组,它是对前向算法和后向算法每一轮的中间结果进行按比例修正的,至于为什么这样做,我也不是很清楚,抱歉!

    [回复]

    请问WithScale是什么意思,有什么用 回复:

    Thank you anyway

    [回复]

    chen 回复:

    这个问题是这样: C语言中的double类型的阶码只有11位,当O序列过长,算出的概率值是很小的,比如当概率值为
    2^-3000,这个pprob会被当成0,log(pprob)会被当成-INF。但实际上log(pprob)是-3000才对,而-3000是个很普通,可以正常表示的数。
    故:withscal方法再算log(pprob)时,绕过了计算pprob,再log的过程,而是直接计算了,这样就不至于当O序列过长时,得到一些无意义的数了,基本原理是log(a/b)=log(a)-log(b)

    chen 回复:

    所以当O序列过长时,用带withscal的方法,否则pprob都是0,log(pprob)都是-INF。log一个数,往往是为了缩放,log函数是单调的,并不影响两个数的相对大小,即如果a<b,则一定有:log(a)<log(b), 这种缩放很常见的。
    如果不理解,不要纠结了,withscal的结果就是概率值取log的结果,没问题。

  8. splash说:

    此代码在模型参数调整中存在错误。我在改写的C#代码里修正了此错误。
    详见:http://blog.csdn.net/jhqin/archive/2011/06/09/6534916.aspx

    [回复]

    52nlp 回复:

    谢谢指正!

    [回复]

  9. xiaobai说:

    我想问一下 看到一书上提到用前向后向算法训练HMM时,HMM应用的典型场合是可以得到词典。这句话可以理解成只有语料(词汇,比如msr_training.txt分好词的文本)么?还有一个问题是HMM的初始化,应该是什么呢

    [回复]

  10. 袁军说:

    您好,请教您一个问题:在给定观察序列O的情况下,用B-W算法寻求一个λ使得P(O|λ)最大,这里的P(O|λ)与用迭代好了的λ使用前向算法计算的P(O|λ)是一致的吗?

    [回复]

    52nlp 回复:

    应该是一致的吧,看你使用的目的了。

    [回复]

    袁军 回复:

    用在不同的地方会不一致吗,还请博主举个例子比方说? 谢谢!

    [回复]

    52nlp 回复:

    我理解你的这个问题中前者是求参,后者是应用,不冲突的

  11. 不达说:

    博主您好,我想请教您一个问题,请问在baum-welch算法中对参数进行重估时,B的重估的含义是什么呢?

    [回复]

  12. Pingback引用通告: HMM模型的初步学习及其perl实现 | 博云社区

  13. 郝丽说:

    博主,你好!我遇到一道题需要利用马尔科夫模型去解,但是因为是管理专业的,第一次接触到这种方法,所以,想请教一下。。。。。

    [回复]

  14. sharp说:

    看了一上午文中所说的tutorial 看到前向后向时的一头雾水 才发现这里的blog~

    [回复]

  15. pslzym说:

    楼主能不能把这个代码粗略的讲一下,看的很晕啊。不过前面的写的很好,谢谢楼主。

    [回复]

  16. nayangya说:

    博主,你好。我想用隐马尔科夫模型来识别刀具磨损状态,我一直搞不懂观测序列到底是什么,是某一个状态下的观测Ot,用一组特征值表示,还是几个连续状态下的观测O1,O2..OT,如果是几个连续状态下的观测值,那怎么识别啊?

    [回复]

  17. yanglin说:

    想问一下博主,里面BW算法,求前项变量的时候为何要出去scale[t]呢?

    [回复]

发表评论

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