维特比算法(Viterbi)-实例讲解(暴力破解+代码实现)

2018/03/11 00:20
阅读数 220

1、简介

  维特比算法是一个通用的求序列最短路径的动态规划算法,也可以用于很多其他问题,比如:文本挖掘、分词原理。既然是动态规划算法,那么就需要找到合适的局部状态,以及局部状态的递推公式。在HMM中,维特比算法定义了两个局部状态用于递推。

  第一个局部状态是在时刻i隐藏状态为i所有可能的状态转移路径i1,i2.......it中的最大概率

  第二个局部状态由第一个局部状态递推得到。

2、算法详解

  (1)从点S出发,对于第一个状态X1的各个节点,不妨假定有n1个,计算出S到它们的距离d(S,X1i),其中X1i代表任意状态1的节点。因为只有一步,所以这些距离都是S到它们各自的最短距离。

  (2)对于第二个状态X2的所有节点,要计算出从S到它们的最短距离。对于特点的节点X2i,从S到它的路径可以经过状态1的n1中任何一个节点X1i,对应的路径长度就是d(S,X2i) = d(S,X1i) + d(X1i,X2i)。

    由于i有n1种可能性,我们要一 一计算,找出最小值。即:d(S,X2i) min =d(S,X1i) + {d(X1i,X2i)}1→n1这样对于第二个状态的每个节点,需要n1次乘法计算。假定这个状态有n2个节点,把S这些节点的距离都算一遍,就有O(n1·n2)次计算。

  (3)接下来,类似地按照上述方法从第二个状态走到第三个状态,一直走到最后一个状态,就得到了整个网格从头到尾的最短路径。

  (4)假设这个隐含马尔可夫链中节点最多的状态有D个节点,也就是说整个网格的宽度为D,那么任何一步的复杂度不超过O(D2),由于网格长度是N,所以整个维特比算法的复杂度是O(N·D2)。

3、实例展示

  (1)天气只有三类(Sunny,Cloudy,Rainy),海藻湿度有四类{Dry,Dryish, Damp,Soggy },而且海藻湿度和天气有一定的关系。

  (2)隐藏的状态:Sunny, Cloudy, Rainy;

  (3)观察状态序列:{Dry, Damp, Soggy}

  (4)初始状态序列:

  

 (5)状态转移矩阵:

  

 (6)发射矩阵:

  

  假设连续观察3天的海藻湿度为(Dry,Damp,Soggy),求这三天最可能的天气情况。

  1、暴力破解:

  前提:第二天的情况只和第一天的天气有关,第三天的天气只和第二天的天气有关。

  所以第一天湿度为Dry的情况为:

    P(Dry|day1-Sunny)=0.63*0.6

    P(Dry|day1-Cloudy)=0.17*0.25

    P(Dry|day1-Rainy)=0.2*0.05

    P(Dry|day1-Suny)的概率最大,所以第一天最大概率为:Sunny

  第二天湿度为Damp的情况为:

    P(Damp|day2-Sunny)=max{P(Dry|day1-Sunny)*0.5,P(Dry|day1-Cloudy)*0.25,P(Dry|day1-Rainy)*0.25}*0.15

    P(Damp|day2-Cloudy)=max{P(Dry|day1-Sunny)*0.375,P(Dry|day1-Cloudy)*0.125,P(Dry|day1-Rainy)*0.625}*0.25

    P(Damp|day2-Rainy)=max{P(Dry|day1-Sunny)*0.125,P(Dry|day1-Cloudy)*0.625,P(Dry|day1-Rainy)*0.35}*0.35

    P(Damp|day2-Cloud)概率最大,所以第二天最大概率为:Cloud

  第三天湿度为Soggy的情况为:

    P(Soggy|day3-Sunny)=max{P(Damp|day2-Sunny)*0.5,P(Damp|day2-Cloudy)*0.25,P(Damp|day2-Rainy)*0.25}*0.05

    P(Soggy|day3-Cloudy)=max{P(Damp|day2-Sunny)*0.375,P(Damp|day2-Cloudy)*0.125,P(Damp|day2-Rainy)*0.625}*0.25

    P(Soggy|day3-Rainy)=max{P(Damp|day2-Sunny)*0.125,P(Damp|day2-Cloudy)*0.625,P(Damp|day2-Rainy)*0.375}*0.5

    P(Soggy|day3-Rainy)概率最大,所以第三天最大概率为:Rainy

  所以3天的天气最大概率为{Sunny,Cloud,Rainy}

  分析:

      第一天:对应每种天气下湿度为Dry放入最大概率则为可能的天气;

      第二天:对应第一天的各种天气分别转换Sunny,且转换的概率最大的情况下,取天气湿度为Damp的概率,Cloudy和Rainy同理,然后取这三种天气下概率最大的天气

      第三天:对应第二天的各种天气分别转换Sunny(注意这里第二天对应第一天,已经得到最大概率)且转换的概率最大的情况下,取天气湿度为Damp的概率,Cloudy和Rainy同理,然后取这三种天气下概率最大的天气

 

   2、python代码实现:

#-*- coding:utf-8 -*-
import numpy as np
def viterbi(trainsition_probability,emission_probability,pi,obs_seq):

    #转换为矩阵进行计算
    trainsition_probability=np.array(trainsition_probability)
    emission_probability=np.array(emission_probability)
    pi=np.array(pi)

    #定义要返回的矩阵
    F = np.zeros((Row, Col))

    #初始状态
    F[:,0]=pi*np.transpose(emission_probability[:,obs_seq[0]])


    for t in range(1,Col):
        list_max=[]
        for n in range(Row):
            list_x=list(np.array(F[:,t-1])*np.transpose(trainsition_probability[:,n]))

            #获取最大概率
            list_p=[]
            for i in list_x:
                list_p.append(i*10000)
            list_max.append(max(list_p)/10000)

        F[:, t] = np.array(list_max) * np.transpose(emission_probability[:,obs_seq[t]])

    return F


if __name__ == '__main__':
    #隐藏状态
    invisible=['Sunny','Cloud','Rainy']
    #初始状态
    pi=[0.63,0.17,0.20]
    #转移矩阵
    trainsition_probability=[[0.5,0.375,0.125],
                             [0.25,0.125,0.625],
                             [0.25,0.375,0.375]]
    #发射矩阵
    emission_probability=[[0.6,0.2,0.15,0.05],
                          [0.25,0.25,0.25,0.25],
                          [0.05,0.10,0.35,0.5]]
    #最后显示状态
    obs_seq=[0,2,3]

    #最后返回一个Row*Col的矩阵结果
    Row = np.array(trainsition_probability).shape[0]
    Col = len(obs_seq)

    F=viterbi(trainsition_probability, emission_probability, pi, obs_seq)

    print F

 

结果:

[[ 0.378     0.02835        0.00070875]
[ 0.0425    0.0354375    0.00265781]
[ 0.01        0.0165375    0.01107422]]

每列代表Dry,Damp,Soggy的概率,每行代表Sunny,Cloud,Rainy,所以可以看出最大概率的天气为{Sunny,Cloud,Rainy}。

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部