隐马尔科夫模型HMM(四)维特比算法解码隐藏状态序列
在本篇我们会讨论HMM模型最后一个问题的求解,即即给定模型和观测序列,求给定观测序列条件下,最可能出现的对应的隐藏状态序列。在阅读本篇前,建议先阅读这个系列的第一篇以熟悉HMM模型。
HMM模型的解码问题最常用的算法是维特比算法,当然也有其他的算法可以求解这个问题。同时维特比算法是一个通用的求序列最短路径的动态规划算法,也可以用于很多其他问题,比如之前讲到的文本挖掘的分词原理中我们讲到了单独用维特比算法来做分词。
本文关注于用维特比算法来解码HMM的的最可能隐藏状态序列。
如果大家看过之前写的文本挖掘的分词原理中的维特比算法,就会发现这两篇之中的维特比算法稍有不同。主要原因是在中文分词时,我们没有观察状态和隐藏状态的区别,只有一种状态。但是维特比算法的核心是定义动态规划的局部状态与局部递推公式,这一点在中文分词维特比算法和HMM的维特比算法是相同的,也是维特比算法的精华所在。
维特比算法也是寻找序列最短路径的一个通用方法,和dijkstra算法有些类似,但是dijkstra算法并没有使用动态规划,而是贪心算法。同时维特比算法仅仅局限于求序列最短路径,而dijkstra算法是通用的求最短路径的方法。
(欢迎转载,转载请注明出处。欢迎沟通交流: liujianping-ok@163.com)