隐马尔可夫模型的Viterbi解码算法

前言

前面在做自然语言处理时涉及到一些词性标注的工作，一般会使用隐马尔科夫模型（HMM）来实现词性标注，而HMM模型的解码实现算法一般就会使用Viterbi算法。

关于穷举法

HMM模型有多种应用，这里说的是其中一个常见应用，即根据观察序列找到最可能的隐含状态序列。最朴素的想法就是直接穷举所有可能的隐含状态序列，并计算出每个组合成的状态序列的概率，概率最大的那个组合序列即是最可能的隐含状态序列。举个水藻和天气的例子，穷举出所有可能的隐含状态序列的概率，如下，
P(dry,damp,soggy | sunny,sunny,sunny), P(dry,damp,soggy | sunny,sunny,cloudy), P(dry,damp,soggy | sunny,sunny,rainy), … . P(dry,damp,soggy | rainy,rainy,rainy)，最大值对应的序列即为最可能的隐含状态序列。穷举的路径一共有$3^t$条，可以看到随着序列还有状态数的增加，计算量是非常大的。

Viterbi算法

上面的穷举法需要的计算量很大，为减少复杂度引入Viterbi算法，Viterbi算法要解决的解码问题就是多步且每步多重选择的最优选择的问题。根据下图就能很清晰看到Viterbi的核心思想，随着时刻增加，每个节点都保存了前一时刻所有节点到该节点的最优值的子路径，如图中红色箭头，当前时刻的某一节点可能的路径为上一时刻所有节点到该节点的路径，但我们只保留其中一条最优路径。依次计算完所有步后，最后通过回溯的方法得到整个过程的最优路径。

下面用一个例子说明整个过程，假设有3中状态，序列为t个时刻，p(a1)表示a1节点的值，p(b1)表示b1节点的值，同理其他的节点也一样。对于不同时刻，状态之间的转换概率是不变的，所以p(aa)表示从a状态转移到a状态的概率，不管是从1时刻到2时刻，还是从2时刻到3时刻，都是相同的。同理还有p(ab)、p(ac)、p(ba)…。

t+1时刻节点值的计算公式为$p_{t+1}(y) = p_t(x) p(xy)$其中x,y都属于a,b,c一种状态。

我们计算t=2时刻的p(a)的值，它可能从a1到a2、b1到a2或c1到a2，假如a1到a2这条路径计算出来的p(a)最大，那么就保留该路径。同理分别计算p(b)和p(c)的最大值，保留b1到b2的路径，b1到c2的路径。接着计算t=3时刻的p(a)、p(b)和p(c)，最后到达t时刻，计算该时刻最大的p(a)、p(b)和p(c)，选择出它们最大的值的节点，再根据保留的上一时刻的路径依次往前回溯，就得到最优的序列。比如ct是最大的节点，那就是$c_t > c_{t-1} > ... > b_3 > c_2 > b_1$即最可能的序列为bcb…cc。

========广告时间========

鄙人的新书《Tomcat内核设计剖析》已经在京东销售了，有需要的朋友可以到 https://item.jd.com/12185360.html 进行预定。感谢各位朋友。

为什么写《Tomcat内核设计剖析》

=========================

欢迎关注：