技术栈

主页 > 其他 >

隐马尔科夫模型前向后向算法

    本文是自己学习隐马尔科夫模型的一个总结,为了自己以后方便查阅,也算作是李航老师的《统计学习方法》的一个总结,若有疑问,欢迎讨论。

推荐阅读知乎上Yang Eninala写的《如何用简单易懂的例子解释隐马尔可夫模型?》,写的非常好。我会联系两者,来作为自己的一篇学习笔记。

    隐马尔可夫模型: 隐马尔可夫模型是关于时序的概率模型,描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列,再由各个状态生成一个观测而产生观测随机序列的过程。隐藏的马尔可夫链随机生成的状态的序列,称为状态序列(state sequence),每个状态生成一个观测,而由此产生的观测的随机序列,称为观测序列(observation sequenoe )。序列的每一个位置又可以看作是一个时刻。















隐马尔科夫模型的3个基本问题:

     (1)概率计算问题。给定模型和观测序列,计算在模型下的观测序列出现的概率

    (2)学习问题。已知观测序列,估计模型参数,使得在该模型下观测序列概率最大。

    (3)预测问题,也称为解码(decoding)问题。已知模型参数和观测序列,求对给定观测序列前提下,条件概率最大的状态序列。即给定观测序列,求最有可能的对应的状态序列

概率计算问题:
1、 直接计算方法
    这种方法说白了就是暴力搜索,枚举每一种状态序列,然后在根据状态序列求出观测序列的概率。
    思想很简单,可以这么想:假如我们现在已知状态序列为,那么根据状态序列S,求观测序列的概率,不就是相应的输出概率的连乘么!满足假设的状态序列总共有,然后对所有假设的状态得出的概率相加,即为。细化如下:

    状态序列的概率是


    对已经假设的状态序列,观测序列,的概率是


    观测序列O和状态序列S同时出现的概率是:


    最后,对所有的状态序列S求和,即可得到观测序列O的概率

    对于实现上式,很简单,个for循环即可枚举所有的状态,然后计算每种状态对应的观测概率,时间复杂度是O(T),因此要直接计算的话,总的时间复杂度为,当数据量稍微大一点,具体实施就不太可能,因此要实现HMM的第一个问题,就要换一种方法。

2、前向算法:

    给定隐马尔可夫模型,定义到时刻t部分观测序列且状态为的概率为前向概率,记作

    可以递推地求得前向概率及观测序列概率

    这个可以这么理解,已知选每种骰子的概率,每种骰子的输出概率,那么前t次掷骰子,掷出的点数为,并且第t用的骰子是,的概率是就是

(1)初值:

【第一次掷的是骰子是,掷出的点数为的概率,其中表示开始的时候选用骰子的概率】

(2)递推:


【第t+1次用骰子,掷出的概率】

    上式方括号中,表示第t次使用骰子掷出点数的的概率,,表示前t次掷出点数为的概率×第t+1次使用骰子的概率。

    由于第t次骰子的种类有N种,因此,第t+1次使用,而前一次,也就是第t次,使用的骰子有N种可能,即如下图:


(3)终止:


    根据(2)的递推式子可以求出表示第T次使用可以产生序列,i仍有N中可能所以相加即为最终的结果。

    例子1(前向算法):考虑盒子和球模型,状态集合,观测集合,并且有:


,试用前向算法计算

根据上面我们描述的算法,一步一步地计算,

(1)计算初值:




(2)递推:

     当时:







    当时:








3、后向算法

    给定隐马尔可夫模型,定义在时刻t部状态为的条件下,从的部分观测序列为的概率为后向概率,记作:


可以递推地求得后向概率及观测序列概率

可以这么理解,已知第t次掷骰子所用的骰子是,那么它表示的就是从次到第次的看到的点数为:的概率

(1)初值


【解释:已知最后一次所用的骰子为,那么第次之后,为任意值的概率,故而为1】

(2)递推


(3)终止



    后向算法依旧是解决概率计算问题,只不过是两种计算方式,计算结果应该是和前向算法相同,可以用例1验证一下,如下:

    例2(后向算法),考虑盒子和球模型,状态集合,观测集合,并且有:


,试用后向算法计算。
    我们仍然根据上面的算法描述,一步一步地计算,

(1)计算初值

    当


(2)递推

    当时:







    当







(3)终止




可以根绝前向算法和后向算法的定义,将两种计算方式结合起来,如下:




责任编辑:admin  二维码分享:
本文标签: HMM
点击我更换图片

评论列表