机器学习:隐马尔可夫模型(HMM)

news/2024/10/31 3:21:06/

后续会回来补充代码

1 隐马尔可夫模型

  隐马尔可夫模型(Hidden Markov Model,HMM)是可用于标注问题的统计学模型,描述由隐藏的马尔可夫链随机生成观测序列的过程。

1.1 数学定义

  隐马尔可夫模型是关于时序的概率模型,描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列,再由各个状态生成同一个观测从而产生观测随机序列的过程。隐藏的马尔可夫链随机生成状态序列,而每一个状态又生成一个观测。序列的每一个位置称作一个时刻。
  隐马尔可夫模型可以由初始状态概率向量 π \pi π,状态转移矩阵 A A A和观测矩阵 B B B决定。 π \pi π A A A决定状态序列, B B B决定观测序列。隐马尔可夫模型可以记作: λ = ( π , A , B ) \lambda=(\pi,A,B) λ=(π,A,B)。其各个部分的介绍如下:
  记 Q = { q 1 , q 2 , … , q N } Q=\{q_{1},q_{2},\dots,q_{N}\} Q={q1,q2,,qN}为所有可能的状态集合, V = { v 1 , v 2 , … , v M } V=\{v_{1}, v_{2},\dots,v_{M}\} V={v1,v2,,vM}为所有可能的观测集合。假设目前得到的 T T T个时刻观测序列 O = ( o 1 , o 2 , … , o T ) O=(o_{1},o_{2},\dots,o_{T}) O=(o1,o2,oT),其对应的状态序列记为 I = ( i 1 , i 2 , … , i T ) I=(i_{1},i_{2},\dots,i_{T}) I=(i1,i2,,iT)状态序列是不可知的
  状态转移矩阵 A = [ a i j ] N × N A=[a_{ij}]_{N\times N} A=[aij]N×N, 其中 a i j = P ( i t + 1 = q j ∣ i t = q i ) , i , j = 1 , 2 , … , N a_{ij}=P(i_{t+1}=q_{j}|i_{t}=q_{i}),i,j=1,2,\dots,N aij=P(it+1=qjit=qi),i,j=1,2,,N,即为在时刻 t t t处于状态 q i q_{i} qi的条件下在时刻 t + 1 t+1 t+1转移到状态 q j q_{j} qj的概率。观测矩阵 B = [ b j ( k ) ] N × M B=[b_{j}(k)]_{N\times M} B=[bj(k)]N×M,其中 b j ( k ) = P ( o t = v k ∣ i t = q j ) , k = 1 , 2 , … , M , j = 1 , 2 , … , N b_{j}(k)=P(o_{t}=v_{k}|i_{t}=q_{j}),k=1,2,\dots,M,j=1,2,\dots,N bj(k)=P(ot=vkit=qj),k=1,2,,M,j=1,2,,N为时刻 t t t处于状态 q j q_{j} qj的条件下生成观测 v k v_{k} vk的概率。
  初始状态变量 π = ( π i ) \pi=(\pi_{i}) π=(πi),其中 π i = P ( i 1 = q i ) , i = 1 , 2 , … , N \pi_{i}=P(i_{1}=q_{i}),i=1,2,\dots,N πi=P(i1=qi),i=1,2,,N为初始时刻 t = 1 t=1 t=1处于状态 q i q_{i} qi的概率。

1.2 基本假设

  • 齐次马尔可夫假设:隐藏的马尔科夫链在任意时刻 t t t的状态只依赖于其前一个时刻状态,与其他时刻的状态和观测无关,也与时刻 t t t无关: P ( i t ∣ i t − 1 , o t − 1 , … , i 1 , o 1 ) = P ( i t ∣ i t − 1 ) , t = 1 , 2 , … , T P(i_{t}|i_{t-1},o_{t-1},\dots,i_{1},o_{1})=P(i_{t}|i_{t-1}),t=1,2,\dots,T P(itit1,ot1,,i1,o1)=P(itit1),t=1,2,,T
  • 观测独立性假设:任意时刻的观测只依赖于该时刻的马尔可夫链的状态,与其他观测及状态无关。

1.3 基本问题

  • 概率计算问题:给定模型 λ = ( π , A , B ) \lambda=(\pi,A,B) λ=(π,A,B)和观测序列 O O O,计算该观测序列出现的概率 P ( O ∣ λ ) P(O|\lambda) P(Oλ)。求解该问题可以使用前向算法和后向算法,这里不详细介绍。
  • 学习问题:已知观测序列 O O O,估计模型 λ = ( π , A , B ) \lambda=(\pi,A,B) λ=(π,A,B)参数,使得在该模型下观测序列概率 P ( O ∣ λ ) P(O|\lambda) P(Oλ)最大。求解该问题主要使用Baum-Welch算法(这个算法是EM算法的一种特例,EM算法在三硬币模型上的推导过程参考:https://blog.csdn.net/yeshang_lady/article/details/132151771)。这里不再赘述。
  • 预测问题:又被称为解码问题。已知模型 λ = ( π , A , B ) \lambda=(\pi,A,B) λ=(π,A,B)和观测序列 O O O,求对给定观测序列条件概率 P ( I ∣ O ) P(I|O) P(IO)最大的状态序列。这里主要介绍维特比算法。

2 预测问题

2.1 维特比算法

  维特比算法是一个动态规划算法,其规划过程与前向算法类似。两个算法的区别在于:评估问题的前向算法会保留每一条路径的概率,最终结果是各概率之和;维特比算法是计算给定观测序列下最可能的隐藏状态序列,因此每一步都只保留概率最大的路径,最终结果是一条概率最大的路径。其算法流程如下:

输入: 模型 λ = ( A , B , π ) \lambda=(A,B,\pi) λ=(A,B,π)和观测序列 O = ( o 1 , o 2 , … , o T ) O=(o_{1},o_{2},\dots,o_{T}) O=(o1,o2,,oT)
输出:最优路径 I ∗ = ( i 1 ∗ , i 2 ∗ , … , i T ∗ ) I^{*}=(i_{1}^{*},i_{2}^{*},\dots,i_{T}^{*}) I=(i1,i2,,iT)
步骤: (1)初始化 δ 1 ( i ) = π i b i ( o 1 ) , i = 1 , 2 , … , N \delta_{1}(i)=\pi_{i}b_{i}(o_{1}),i=1,2,\dots,N δ1(i)=πibi(o1),i=1,2,,N Ψ 1 ( i ) = 0 , i = 1 , 2 , … , N \Psi_{1}(i)=0,i=1,2,\dots,N Ψ1(i)=0,i=1,2,,N(2)递推。对 t = 2 , 3 , … , T t=2,3,\dots,T t=2,3,,T δ t ( i ) = m a x 1 ≤ j ≤ N [ δ t − 1 ( j ) a j i ] b i ( o t ) , i = 1 , 2 , … , N \delta_{t}(i)=\underset {1\le j\le N}{max}[\delta_{t-1}(j)a_{ji}]b_{i}(o_{t}),i=1,2,\dots,N δt(i)=1jNmax[δt1(j)aji]bi(ot),i=1,2,,N Ψ t ( i ) = a r g m a x 1 ≤ j ≤ N [ δ t − 1 ( j ) a j i ] b i ( o t ) , i = 1 , 2 , … , N \Psi_{t}(i)=arg \underset {1\le j \le N}{max}[\delta_{t-1}(j)a_{ji}]b_{i}(o_{t}),i=1,2,\dots,N Ψt(i)=arg1jNmax[δt1(j)aji]bi(ot),i=1,2,,N(3)终止 P ∗ = m a x 1 ≤ j ≤ N δ T ( i ) P^{*}=\underset {1\le j\le N}{max}\delta_{T}(i) P=1jNmaxδT(i) i T ∗ = a r g m a x 1 ≤ j ≤ N [ δ T ( i ) ] i^{*}_{T}=arg \underset {1\le j\le N}{max} [\delta_{T}(i)] iT=arg1jNmax[δT(i)](4)最优路径回溯。对 t = T − 1 , T − 2 , … , 1 t=T-1,T-2,\dots,1 t=T1,T2,,1 i t ∗ = Ψ t + 1 ( i t + 1 ∗ ) i^{*}_{t}=\Psi_{t+1}(i^{*}_{t+1}) it=Ψt+1(it+1)求得最优路径 I ∗ = ( i 1 ∗ , i 2 ∗ , … , i T ∗ ) I^{*}=(i_{1}^{*},i_{2}^{*},\dots,i_{T}^{*}) I=(i1,i2,,iT)

参考资料

  1. 《统计学习方法》

http://www.ppmy.cn/news/1026906.html

相关文章

C#获取文件信息的方法汇总

前言 在.NET开发中,用C#获取文件信息是比较常见的操作。通过获取文件信息,我们可以了解文件的属性、大小、创建日期、修改日期等各种元数据信息。比如我们网站需要上传文件,可以用扩展名称控制上传的类型,获取文件的大小来限制上传…

【软件工程】数据流图/DFD概念符号/流程图分层/数据字典

【软件工程】数据流图/DFD概念符号/流程图分层/数据字典 目录 【软件工程】数据流图/DFD概念符号/流程图分层/数据字典 一、数据流图 ( DFD ) 简介 二、数据流图 ( DFD ) 概念符号 1、数据流 2、加工 ( 核心 ) 3、数据存储 4、外部实体 三、数据流图 ( DFD ) 分层 1、…

springboot3日志配置

简介 Spring 使用commons-logging作为内部日志,但是底层日志实现是开放的,可以对接其他日志框架 spring5以及以后common-logging被spring直接自己写了 支持jul, log4j2,logback,springBoot提供了默认的控制台输出配置,也可以配置…

Linux 命令 su 和 sudo 的区别

之前一直对 su 和 sudo 这两个命令犯迷糊,最近专门搜了这方面的资料,总算是把两者的关系以及用法搞清楚了,这篇文章来系统总结一下。 1. 准备工作 因为本篇博客中涉及到用户切换,所以我需要提前准备好几个测试用户,方…

centos安装指定版本的docker并添加多源加速器

1. 安装指定版本的docker yum -y install epel-release wget wget https://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo -O /etc/yum.repos.d/docker-ce.repo yum list docker-ce --showduplicates | sort -r #查看yum仓库中可以安装的docker版本 yum -y insta…

使用sqlplus连接oracle,提示ORA-01034和ORA-27101

具体内容如下 PL/SQL Developer 处 登录时 终端处 登录时 ERROR: ORA-01034: ORACLE not available ORA-27101: shared memory realm does not exist Process ID: 0 Session ID: 0 Serial number: 0 解决方法是执行以下命令 sqlplus /nolog conn / as sysdba startup …

猿人学刷题系列(第一届比赛)——第二题( js 混淆 - 动态cookie 1)

题目:提取全部5页发布日热度的值,计算所有值的加和 地址:https://match.yuanrenxue.cn/match/2 思路分析 本题我们会简单说一下两种不同的方式去处理,一种是不还原混淆代码直接从源代码硬扣生成逻辑,另一种则是还原…

ERROR: While executing gem ... (Gem::FilePermissionError)

sudo gem install -n /usr/local/bin cocoapodsERROR: While executing gem ... (Gem::FilePermissionError)You dont have write permissions for the /System/Library/Frameworks/Ruby.framework/Versions/2.6/usr/lib/ruby/gems/2.6.0 directory.解决办法: 1.删…