隐马尔可夫模型（HMM）及Viterbi算法

article/2025/9/12 9:20:05

HMM简介

  对于算法爱好者来说，隐马尔可夫模型的大名那是如雷贯耳。那么，这个模型到底长什么样？具体的原理又是什么呢？有什么具体的应用场景呢？本文将会解答这些疑惑。
  本文将通过具体形象的例子来引入该模型，并深入探究隐马尔可夫模型及Viterbi算法，希望能对大家有所启发。
  隐马尔可夫模型（HMM，hidden Markov model）是可用于标注问题的统计学模型，描述由隐藏的马尔可夫链随机生成观测序列的过程，属于生成模型。HMM模型在实际的生活和生产中有着广泛的应用，包括语音识别，自然语言处理，生物信息，模式识别等领域。

引入

  某天，你的女神告诉你说，她放假三天，将要去上海游玩，准备去欢乐谷、迪士尼和外滩（不一定三个都会去）。
  她呢，会选择在这三个地方中的某几个逗留并决定是否购物，而且每天只待在一个地方。根据你对她的了解，知道她去哪个地方，仅取决于她去的上一个地方，且是否购物的概率仅取决于她去的地方。已知她去的三个地方的转移概率表如下：

 欢乐谷迪士尼外滩
欢乐谷0.80.050.15
迪士尼0.20.60.3
外滩0.20.30.5

稍微对这个表格做些说明，比如第一行，前一天去了欢乐谷后，第二天还待在欢乐谷的概率为0.8，去迪士尼的概率为0.05，去外滩的概率为0.15。
  她在每个地方的购物概率为：

地点购物概率
欢乐谷0.1
迪士尼0.8
外滩0.3

  在出发的时候，她跟你说去每个地方的可能性相同。后来，放假回来后，你看了她的朋友圈，发现她的购物情况如下：第一天不购物，第二三天都购物了。于是，你很好奇，她这三天都去了哪些地方。
  怎么样，聪明的你能求解出来吗？

HMM的模型参数

  接下来，我们将会介绍隐马尔可夫模型（HMM）。
  隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。隐藏的马尔可夫链随机生成的状态的序列，称为状态序列；每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列。序列的每一个位置又可以看作是一个时刻。
  隐马尔可夫模型由初始概率分布、状态转移概率分布以及观测概率分布确定。隐马尔可夫模型的形式定义如下：
  设Q是所有可能的状态的集合，V是所有可能的观测的集合，也就是说，Q是不可见的，而V是可见的，是我们观测到的可能结果。

 

q={q1,q2,...,qN},V={v1,v2,...,vM}q={q1,q2,...,qN},V={v1,v2,...,vM}

其中，N是可能的状态数，M是可能的观测数。
  在刚才的例子中，QQ是不可见的状态集合，应为Q={欢乐谷，迪士尼，外滩}Q={欢乐谷，迪士尼，外滩}，而VV是可以观测的集合，应为V={购物，不购物}V={购物，不购物}。
  I是长度为T的状态序列，O是对应的观测序列。

 

I=(i1,i2,...,iT),O=(o1,o2,...,oT)I=(i1,i2,...,iT),O=(o1,o2,...,oT)

在刚才的例子中，II这个序列是我们需要求解的，即女生去了哪些地方，而OO是你知道的序列，O={不购物，购物，购物}O={不购物，购物，购物}。
  A是状态转移概率矩阵：

 

A=[aij]N×NA=[aij]N×N


其中，aij=P(it+1=qj|it=qi),i=1,2,...,N;j=1,2,..,Naij=P(it+1=qj|it=qi),i=1,2,...,N;j=1,2,..,N是在时刻t处于状态qiqi的条件下在时刻t+1转移到状态qjqj的概率。在刚才的例子中，转移概率矩阵为：

 

A=⎡⎣⎢0.80.60.20.050.60.30.150.20.5⎤⎦⎥A=[0.80.050.150.60.60.20.20.30.5]

  B是观测概率矩阵：

 

B=[bj(k)]N×MB=[bj(k)]N×M

其中，bj(k)=P(ot=vk|it=qj),k=1,2,...,M;j=1,2,...,Nbj(k)=P(ot=vk|it=qj),k=1,2,...,M;j=1,2,...,N是在时刻t处于状态qjqj的条件下生成观测vkvk的概率。在刚才的例子中：

 

B=⎡⎣⎢0.10.80.30.90.20.7⎤⎦⎥B=[0.10.90.80.20.30.7]

  ππ是初始状态概率向量π=(πi)π=(πi),其中πi=P(i1=qi),i=1,2,...,Nπi=P(i1=qi),i=1,2,...,N是时刻t=1处于状态qjqj的概率。在刚才的例子中， π=(13,13,13).π=(13,13,13).
  综上，我们已经讲完HMM中的基本概念。同时，我们可以知道，隐马尔可夫模型由初始状态概率向量ππ，状态转移概率矩阵AA和观测概率矩阵BB决定。ππ和AA决定状态序列，BB决定观测序列。因此，隐马尔可夫模型λλ可用三元符号表示，即

 

λ=(A,B,π)λ=(A,B,π)

A,B,πA,B,π称为HMM的三要素。
  当然，隐马尔可夫模型之所以被称为马尔可夫模型，是因为它使用了两个基本的假设，其中之一为马尔可夫假设。它们分别是：

  1. 齐次马尔科夫假设，即假设隐藏的马尔可夫链在任意时刻t的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关，也与时刻t无关。

 

P(ii|it−1,ot−1,...,i1,o1)=P(it|it−1),t=1,2,...,TP(ii|it−1,ot−1,...,i1,o1)=P(it|it−1),t=1,2,...,T

  1. 观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关。

 

P(oi|iT,oT,...,it+1,ot+1,it,tt−1,ot−1,...,i1,o1)=P(ot|it),t=1,2,...,TP(oi|iT,oT,...,it+1,ot+1,it,tt−1,ot−1,...,i1,o1)=P(ot|it),t=1,2,...,T

  在刚才的假设中，我们对应的两个假设分别为：她去哪个地方，仅取决于她去的上一个地方；是否购物的概率仅取决于她去的地方。前一个条件为齐次马尔科夫假设，后一个条件为观测独立性假设。
  以上，我们就介绍了HMM的基本概念及假设。而HMM的三个基本问题如下：

  1. 概率计算问题。给定模型λ=(A,B,π)λ=(A,B,π)和观测序列O=(o1,o2,...,oT)O=(o1,o2,...,oT),计算在模型λλ下观测序列OO出现的概率P(O|λ).P(O|λ).
  2. 学习问题。已知观测序列O=(o1,o2,...,oT)O=(o1,o2,...,oT)，估计模型λ=(A,B,π)λ=(A,B,π)参数，使得在该模型下观测序列概率P(O|λ)P(O|λ)最大。
  3. 预测问题。已知模型λ=(A,B,π)λ=(A,B,π)和观测序列O=(o1,o2,...,oT)O=(o1,o2,...,oT)，求对给定观测序列条件概率P(I|O)P(I|O)最大的状态序列I=(i1,i2,...,iT).I=(i1,i2,...,iT).即给定观测序列，求最有可能的对应的状态序列。

  上面的例子即为HMM的第三个基本问题，也就是，给定观测序列{不购物，购物，购物}，结果最有可能的状态序列，即游玩的地方。

Viterbi算法

  求解HMM的第三个基本问题，会用到大名鼎鼎的维特比算法（Viterbi Algorithm）。
  维特比算法以安德鲁·维特比（Andrew Viterbi）命名，是现代数字通信中最常用的算法，同时也是很多自然语言处理采用的解码算法。可以毫不夸张地讲，维特比是对我们的生活影音力最大的科学家之一，因为基于CDMA的3G移动通信标准主要就是他和厄文·雅各布（Irwin Mark Jacobs）创办的高通公司（Qualcomm）指定的。
  维特比算法是一个特殊但应用最广的动态规划（dynamic programming）算法，利用动态规划，可以解决任何一个图中的最短路径问题，同时，它也是求解HMM描述的第三个基本问题的算法。
  在维特比算法中，需要引入两个变量δδ和ψ.ψ.定义在时刻t状态i的所有单个路径(i1,i2,...,it)(i1,i2,...,it)中概率最大值为

 

δt+1(i)=max1≤j≤N[δt(j)aji]bi(ot+1),i=1,2,...,N;t=1,2,...,T.δt+1(i)=max1≤j≤N[δt(j)aji]bi(ot+1),i=1,2,...,N;t=1,2,...,T.

定义在时刻t状态为i的所有单个路径(i1,i2,...,it−1,i)(i1,i2,...,it−1,i)中概率最大的路径的第i-1个节点为

 

ψt(i)=argmax1≤j≤N[δt−1(j)aji],i=1,2,...,N;t=1,2,...,T.ψt(i)=argmax1≤j≤N[δt−1(j)aji],i=1,2,...,N;t=1,2,...,T.

  下面是维特比算法在HMM的第三个基本问题的算法：

Python代码实现

  下面，对于刚才给出的例子，我们将使用Python，来写代码实现Viterbi算法，同时求解刚才的问题。

# -*- coding: utf-8 -*-
# HMM.py
# Using Vertibi algorithmimport numpy as npdef Viterbi(A, B, PI, V, Q, obs):N = len(Q)T = len(obs)delta = np.array([[0] * N] * T, dtype=np.float64)phi = np.array([[0] * N] * T, dtype=np.int64)# 初始化for i in range(N):delta[0, i] = PI[i]*B[i][V.index(obs[0])]phi[0, i] = 0# 递归计算for i in range(1, T):for j in range(N):tmp = [delta[i-1, k]*A[k][j] for k in range(N)]delta[i,j] = max(tmp) * B[j][V.index(obs[i])]phi[i,j] = tmp.index(max(tmp))# 最终的概率及节点P = max(delta[T-1, :])I = int(np.argmax(delta[T-1, :]))# 最优路径pathpath = [I]for i in reversed(range(1, T)):end = path[-1]path.append(phi[i, end])hidden_states = [Q[i] for i in reversed(path)]return P, hidden_statesdef main():# 状态集合Q = ('欢乐谷', '迪士尼', '外滩')# 观测集合V = ['购物', '不购物']# 转移概率: Q -> QA = [[0.8, 0.05, 0.15],[0.2, 0.6, 0.2],[0.2, 0.3, 0.5]]# 发射概率, Q -> VB = [[0.1, 0.9],[0.8, 0.2],[0.3, 0.7]]# 初始概率PI = [1/3, 1/3, 1/3]# 观测序列obs = ['不购物', '购物', '购物']P, hidden_states = Viterbi(A,B,PI,V,Q,obs)print('最大的概率为: %.5f.'%P)print('隐藏序列为：%s.'%hidden_states)main()

输出结果如下：

最大的概率为: 0.02688.
隐藏序列为：['外滩', '迪士尼', '迪士尼'].

  现在，你有很大的把握可以确定，你的女神去了外滩和迪士尼。

   注意：本人现已开通微信公众号： Python爬虫与算法（微信号为：easy_web_scrape）， 欢迎大家关注哦~~

参考文献

  1. 一文搞懂HMM（隐马尔可夫模型）：https://www.cnblogs.com/skyme/p/4651331.html
  2. 李航《统计学习方法》 清华大学出版社
  3. HMM与分词、词性标注、命名实体识别：http://www.hankcs.com/nlp/hmm-and-segmentation-tagging-named-entity-recognition.html
  4. Hidden Markov Models 1: http://docplayer.net/21306742-Hidden-markov-models-1.html
  5. 吴军 《数学之美》 人民邮电出版社

http://chatgpt.dhexx.cn/article/gIGJBYj0.shtml

相关文章

viterbi算法实例及python实现

viterbi算法实例及python实现

Python中hmmlearn给出了三种HMM模型：MultiomialHMM,GaussianHMM,GMMHMM。本文以MultiomialHMM为例，使用《从机器学习到深度学习》中第六章的活动/天气模型进行推算。 假设有这样一个问题，远在另一个城市上大学的儿子每天通过邮件向你汇报他今…
阅读更多...
在HMM中实际应用Viterbi算法的例子

在HMM中实际应用Viterbi算法的例子

在HMM中实际应用Viterbi算法的例子 Viterbi概念动态规划使用HMM的Viterbi算法参考Viterbi概念 本质：动态规划算法 维特比算法是多步骤每步多选择模型的最优选择问题。 其在每一步的所有选择都保存了前续所有步骤到当前步骤当前选择的最小总代价（或者最大价值）以及当前代价…
阅读更多...
HMM和viterbi算法初步实践-----中文分词

HMM和viterbi算法初步实践-----中文分词

马尔科夫性质:当一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态。换句话说，在给定现在状态时，它与过去状态（即该过程的历史路径）是条件独立的（也就是没有任何的…
阅读更多...
HMM和Viterbi算法

HMM和Viterbi算法

一、隐马尔可夫模型（Hidden Markov Model） 1、简介 隐含马尔可夫模型并不是俄罗斯数学家马尔可夫发明的，而是美国数学家鲍姆提出的，隐含马尔可夫模型的训练方法（鲍姆-韦尔奇算法）也是以他名字命名的。隐含马…
阅读更多...
基于Hmm模型和Viterbi算法的中文分词和词性标注

基于Hmm模型和Viterbi算法的中文分词和词性标注

使用 python 实现基于Hmm模型和Viterbi算法的中文分词及词性标注；使用 最大概率算法 进行优化。最终效果：人民日报语料：分词(F1:96.189%)；词性标注(F1:97.934%) 完整代码和数据，参见本实验的 github地址：h…
阅读更多...
【生信算法】利用HMM纠正测序错误（Viterbi算法的python实现）

【生信算法】利用HMM纠正测序错误（Viterbi算法的python实现）

利用HMM纠正测序错误（Viterbi算法的python实现） 问题背景 对两个纯系个体M和Z的二倍体后代进行约~0.05x的低覆盖度测序，以期获得后代个体的基因型，即后代中哪些片段分别来源于M和Z。已知： 后代中基因型为MM、MZ&…
阅读更多...
Viterbi算法实现中文分词和词性标注

Viterbi算法实现中文分词和词性标注

Viterbi算法 目标过程词典分词统计分词词性标注 附录附录二附录三 源码地址 目标 实现基于词典的分词方法和统计分词方法对分词结果进行词性标注对分词及词性标注结果进行评价，包括4个指标：正确率、召回率、F1值和效率 过程 词典分词 基于词典的分词…
阅读更多...
viterbi 算法与python实现

viterbi 算法与python实现

Viterbi算法 （部分内容转自知乎：《如何通俗地讲解 viterbi 算法？》） 1、问题描述 如下如所示，如何快速找到从 S 到 E 的最短路径？ 一：遍历穷举法，可行，但速度太慢&am…
阅读更多...
维特比算法(viterbi)原理以及简单实现

维特比算法(viterbi)原理以及简单实现

维特比算法 看一下维基百科的解释，维特比算法（Viterbi algorithm）是一种动态规划算法。它用于寻找最有可能产生观测事件序列的维特比路径——隐含状态序列，特别是在马尔可夫信息源上下文和隐马尔可夫模型中。 通俗易懂的解释知乎…
阅读更多...
flask中jsonify遇到的坑

flask中jsonify遇到的坑

1.jsonify可以将字典转换成json对象传入前端 data {"movie": movie_list,"page": page,"dic_list": dic,"total_page": total_page}>>坑1 字典的值不能为range(x,x)，上图dic就是像range(x,x)，会报错 …
阅读更多...
flask中的jsonify返回的是乱码

flask中的jsonify返回的是乱码

用flask返回json时遇到了返回字符串支持中文显示的问题，在web端显示的是utf-8的编码如图; 虽然不影响接口的读取，但是可读性太差，于是研究了一下怎么直接显示成中文。最后找到了解决方案如下，在配置中加入下面一行代码就OK了。 …
阅读更多...
request jsonify

request jsonify

python的flask框架为用户提供了直接返回包含json格式数据响应的方法，即jsonify，在开发中会经常用到。如下一段简单的flask后端代码，服务端视图函数根据请求参数返回json格式的数据到客户端。 转载于:https://www.cnblogs.com/daqingzi/p/9018…
阅读更多...
Flask使用json或jsonify返回响应的数据

Flask使用json或jsonify返回响应的数据

前言 在做网站前后端数据交互的时候，我们经常需要使用Ajax等方法向后端发送请求来获取响应的数据，而我们经常需要的就是json格式的响应数据，它实际上就是一个字符串。要知道Flask如何返回json响应数据，首先就需要知道如何将字典di…
阅读更多...
Flask 学习-8. jsonify返回中文没正常显示问题

Flask 学习-8. jsonify返回中文没正常显示问题

前言 Flask 接口返回的json 格式数据有中文的时候，默认是以ASCII码 返回的，没正常显示中文。 jsonify 返回 json 数据 函数直接返回dict 数据 或返回jsonfy() 函数处理的数据，都是以json格式返回的 from flask import Flask, jsonify fro…
阅读更多...
flask jsonify之序列化时的default函数、jsonify序列化自定义对象

flask jsonify之序列化时的default函数、jsonify序列化自定义对象

目录 1.看源码 2、重写默认的default函数，实现自己的序列化机制 3、把对象转化成字典 3.1 __dict__的方式 3.2、定义keys和__getitem__的方式 4、最终的代码实现 5、关于default函数的其他知识 1.看源码 打开site-package，flask，json…
阅读更多...
Flask | 解决jsonify返回中文乱码问题

Flask | 解决jsonify返回中文乱码问题

在采用 return jsonify(data) 返回内容中含有中文时，前端接收数据出现中文乱码问题，乱码格式如下（仅中文为ASCII码）： 故在此记录下该问题的解决方式，以作后期参考： 在定义Flask app时&#xff…
阅读更多...
jsonify返回中文编码的问题

jsonify返回中文编码的问题

app.config[JSON_AS_ASCII]Flase 在它下面加上上面的代码就欧克了 没加之前或者为True： 加了之后：
阅读更多...
flask学习二（jsonify）

flask学习二（jsonify）

示例一： 实现动态路由，代码如下 # coding:utf-8 from flask import Flask from flask import jsonify # 创建对象 app Flask(__name__)users_list {"1001":["123","张三",19],"1002":["234","…
阅读更多...
flask中jsonify和json区别

flask中jsonify和json区别

一 JSON数据结构 要把json与字典区分开来 dumps(字典转换成Json) loads(Json转换成字典) Python 的字典是一种数据结构，JSON 是一种数据格式。 json 就是一个根据某种约定格式编写的纯字符串，不具备任何数据结构的特征。而 python 的字典…
阅读更多...
关于flask入门教程-记录集转jsonify

关于flask入门教程-记录集转jsonify

Flask 框架里，可以用 jsonify 返回 json 数据，但是为什么不用 Python 自带的 json 模块返回 JSON 数据呢？ 其实两者是差不多的，jsonify指明了Content-Type 是 application/json ， 这样做是符合 HTTP 协议的规定的&…
阅读更多...
推荐文章

Copyright @ 2022~2023