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

1、简介

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

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

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

2、算法详解

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

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

　　　　由于i有n种可能性，我们要一 一计算，找出最小值。即：d(S,X)  =d(S,X) + ｛d(X,X)｝这样对于第二个状态的每个节点，需要n次乘法计算。假定这个状态有n个节点，把S这些节点的距离都算一遍，就有O(n·n)次计算。

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

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

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｝。