Viterbi algorithm

时间:2022-06-14 03:32:56

HMM(隐马尔可夫模型)是用来描述隐含未知参数的统计模型,是一个关于时序的概率模型,它描述了一个由隐藏的马尔可夫链生成状态序列,再由状态序列生成观测序列的过程。其中,状态之间的转换以及观测序列和状态序列之间都存在一定的概率关系。

任何一个HMM都可以通过下列五元组来描述:

:param obs:观测序列

:param states:隐状态

:param start_p:初始概率(隐状态)

:param trans_p:转移概率(隐状态)

:param emit_p: 发射概率 (隐状态表现为显状态的概率)

而Viterbi算法是解决隐马第三问题(求观察序列的最可能标注序列)。 
算法通过已知的可以观察到的序列,和一些已知的状态转换之间的概率情况,通过综合状态之间的转移概率和前一个状态的情况计算出概率最大的状态转换路径,从而推断出隐含状态的序列的情况。

*动态图表示Viterbi算法过程


一个简单问题

问题描述

隐含的身体状态 = { 健康 , 发烧 }

可观察的感觉状态 = { 正常 , 冷 , 头晕 }

月儿预判的阿驴身体状态的概率分布 = { 健康:0.6 , 发烧: 0.4 }

月儿认为的阿驴身体健康状态的转换概率分布 = {健康->健康: 0.7 ,健康->发烧: 0.3 ,发烧->健康:0.4 ,发烧->发烧: 0.6}

月儿认为的在相应健康状况条件下,阿驴的感觉的概率分布 = {健康,正常:0.5 ,冷 :0.4 ,头晕: 0.1 ;发烧,正常:0.1 ,冷 :0.3 ,头晕: 0.6 }

阿驴连续三天的身体感觉依次是: 正常、冷、头晕 。

利用五元组来描述问题

 states = ('Health', 'Fever')
observations = ('normal', 'cold', 'dizzy')
start_probability = {'Health': 0.6, 'Fever': 0.4}
transition_probability = {
'Health' : {'Health': 0.7, 'Fever': 0.3},
'Fever' : {'Health': 0.4, 'Fever': 0.6},
}
emission_probability = {
'Health' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6},
}

代码实现Viterbi 算法

 import numpy
def Viterbi () :
#已知条件
states = ('Health', 'Fever')
observations = ('normal', 'cold', 'dizzy')
start_probability = {'Health': 0.6, 'Fever': 0.4}
transition_probability = {
'Health' : {'Health': 0.7, 'Fever': 0.3},
'Fever' : {'Health': 0.4, 'Fever': 0.6},
}
emission_probability = {
'Health' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6},
}
day = 3
s = len(states)
V = [] Wether = []
Temp = []
#求解初始状态可能
for j in list(range(s)):
Temp.append(start_probability.get(states[j]) * emission_probability.get(states[j])[observations[0]])
V.append(Temp)
#根据初始状态求解
Wether.append(states[V[0].index(max(V[0]))]); #求解第2 - day 状态转换概率
prob = []
for d in [i + 1 for i in list(range( day - 1))]:
prob = []
pp = -1
for j in list(range(s)):
Temp = []
for k in list(range(s)):
np = V[d-1][j] * transition_probability.get(states[j])[states[k]] * emission_probability.get(states[k])[observations[d]]
Temp.append(np)
#记录路径
if np > pp:
m1 = j
m2 = k
pp = np
prob.append(Temp) print('Compute_Probability:')
print(prob)
Wether.append(states[m2])
V.append(prob[m1])
print('Large_One:')
print(prob[m1]) print(V)
print(Wether) if __name__ == '__main__':
Viterbi()

结果截图

Viterbi algorithm

Viterbi algorithm的更多相关文章

  1. 维特比算法(Viterbi Algorithm)

      寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states) 对于一个特殊的隐马尔科夫模型(HMM)及一个相应的观察序列,我们常常希望 ...

  2. HMM——维特比算法(Viterbi algorithm)

    1. 前言维特比算法针对HMM第三个问题,即解码或者预测问题,寻找最可能的隐藏状态序列: 对于一个特殊的隐马尔可夫模型(HMM)及一个相应的观察序列,找到生成此序列最可能的隐藏状态序列. 也就是说给定 ...

  3. HMM Viterbi算法 详解

    HMM:隐式马尔可夫链   HMM的典型介绍就是这个模型是一个五元组: 观测序列(observations):实际观测到的现象序列 隐含状态(states):所有的可能的隐含状态 初始概率(start ...

  4. HMM隐马尔科夫算法(Hidden Markov Algorithm)初探

    1. HMM背景 0x1:概率模型 - 用概率分布的方式抽象事物的规律 机器学习最重要的任务,是根据一些已观察到的证据(例如训练样本)来对感兴趣的未知变量(例如类别标记)进行估计和推测. 概率模型(p ...

  5. 隐马尔可夫模型(HMM)及Viterbi算法

    HMM简介   对于算法爱好者来说,隐马尔可夫模型的大名那是如雷贯耳.那么,这个模型到底长什么样?具体的原理又是什么呢?有什么具体的应用场景呢?本文将会解答这些疑惑.   本文将通过具体形象的例子来引 ...

  6. Viterbi算法和隐马尔可夫模型(HMM)算法

    隐马尔可夫模型(HMM)及Viterbi算法 https://www.cnblogs.com/jclian91/p/9954878.html HMM简介   对于算法爱好者来说,隐马尔可夫模型的大名那 ...

  7. 维特比算法(Viterbi)

    维特比算法(Viterbi) 维特比算法 编辑 维特比算法是一种动态规划算法用于寻找最有可能产生观测事件序列的-维特比路径-隐含状态序列,特别是在马尔可夫信息源上下文和隐马尔可夫模型中.术语“维特比路 ...

  8. Viterbi(维特比)算法在CRF(条件随机场)中是如何起作用的?

    之前我们介绍过BERT+CRF来进行命名实体识别,并对其中的BERT和CRF的概念和作用做了相关的介绍,然对于CRF中的最优的标签序列的计算原理,我们只提到了维特比算法,并没有做进一步的解释,本文将对 ...

  9. 隐马尔可夫模型(HMM)及Viterbi算法

    HMM简介 对于算法爱好者来说,隐马尔可夫模型的大名那是如雷贯耳.那么,这个模型到底长什么样?具体的原理又是什么呢?有什么具体的应用场景呢?本文将会解答这些疑惑. 本文将通过具体形象的例子来引入该模型 ...

随机推荐

  1. python征程1.4(初识python)

    1.列表解析. (1)这是一个,让人听起来十分欣喜的术语,代表着你可以通过一个循环将所有值放到一个列表中.python列表解析属于python的迭代中的一种,相比python for循环速度会快很多. ...

  2. ZeroMQ接口函数之 :zmq_socket – 创建ZMQ套接字

    ZeroMQ API 目录 :http://www.cnblogs.com/fengbohello/p/4230135.html ZeroMQ 官方地址:http://api.zeromq.org/4 ...

  3. uboot命令

    uboot是怎么启动kernel的呢? 先熟悉一下uboot的命令吧. 首先是md, 查看内存. OpenJTAG> md 000000000: ea000014 e59ff014 e59ff0 ...

  4. CENTOS LINUX查询内存大小、频率

    more /proc/meminfo dmidecode [root@barcode-mcs ~]# dmidecode -t memory linux下查看主板内存槽与内存信息 1.查看内存槽数.那 ...

  5. Linux内存管理专题

    Linux的内存管理涉及到的内容非常庞杂,而且与内核的方方面面耦合在一起,想要理解透彻非常困难. 在开始学习之前进行了一些准备工作<如何展开Linux Memory Management学习?& ...

  6. Java中&amp&semi;0xFF是什么意思?计算机的原码、补码和反码

    https://blog.csdn.net/xmc281141947/article/details/74740061

  7. VMware上配置DPDK环境并运行实例程序

    1. 在虚拟机VMware上配置环境 VMware安装:http://www.zdfans.com/html/5928.html Ubuntu:https://www.ubuntu.com/downl ...

  8. java类加载详解

    1,类的加载过程: JVM将类加载过程分为三个步骤:装载(load),链接(link)和初始化(initialize),其中链接又分为三个步骤: 验证(varification),准备(Prepara ...

  9. Lyft Level 5 Challenge 2018 - Elimination Round翻车记

    打猝死场感觉非常作死. A:判一下起点和终点是否在其两侧即可. #include<iostream> #include<cstdio> #include<cmath&gt ...

  10. Appium PageObject

    原文地址http://blog.csdn.net/TalorSwfit20111208/article/details/77434950 由于无法联系上您,在此分享您的文章,希望谅解! Appium ...