文档章节

第十章-HMM模型以及相关推导

o
 osc_isezqdgg
发布于 2019/09/18 15:24
字数 3416
阅读 9
收藏 0

精选30+云产品,助力企业轻松上云!>>>

隐马尔可夫模型(Hidden Markov Model, HMM)是可用于标注问题的统计学习模型,描述由隐藏的马尔科夫链随机生成的观测序列的过程,属于生成模型,是概率模型的一种。本章主要是总结HMM模型的概率计算算法、学习算法以及预测算法。HMM在语音识别、自然语言处理NLP等领域有着广泛的应用。

概率图模型常常是为了描述随机变量之间的关系(是不是独立的),分为有向图和无向图,而HMM主要用有向图。

概率图模型

在有向图中,用圆圈⭕表示随机变量,可以是一维的,也可以是多维的,既可以是离散随机变量,也可以是连续的,⭕叫做结点,图是由结点和边构成的,在有向图中就是有向边,要描述Y受X影响的,就将X和Y连接起来,并用箭头描述从X指向Y的方向。

随机变量之间的关系

一个箭头可以表示两个随机变量之间的关系,引入条件独立的概念,在概率图模型中,假设有三个随机变量X,Y,Z,一般来说,隐变量在图模型中用⭕表示,如果能观察到一个变量取值的时候,用带阴影的圆\bullet表示。在掷硬币的例子中,第1个结果是观察不到的,用空心圆⭕表示,第2个结果是可以观察到的,用带阴影的圆●表示。为什么要强调隐变量和观测变量,圆是空心⭕还是阴影●会影响到随机变量的依赖性

第一种情况

随机变量都是空心圆,三个随机变量都是观测不到的。即: $$ P(X,Z) \neq P(X)(Z) $$

第二种情况

Y是带阴影的圆,随机变量Y是可以观测到的,可得P(X,Z|Y)=P(X|Y)P(Z|Y),从箭头的指向看,信息是从X传到Y,Y传到Z,一旦将Y固定了,信息的流通相当于被Y观察到的值堵住了,所以当观察到Y时,X和Z就是独立的

第三种情况

Y指向了两边,这个时候单看X和Z是不独立的,满足P(X,Z) ≠ P(X)P(Z),如果给定Y,X和Z是独立的,满足 $$ P(X,Z|Y)=P(X|Y)P(Z|Y) $$

第四种情况

随机变量满足: $$ P(X,Z)=P(X)P(Z),P(X,Z|Y)\neq P(X|Y)P(Z|Y) $$

HMM模型

定义

隐马尔科夫模型是关于时序的概率模型,描述由一个隐藏的马尔科夫链随机生成不可观测的状态随机序列,再由各个状态生成一个观测而产生观测随机序列的过程。隐藏的马尔科夫链随机生成的状态序列称为状态序列(state sequence),每个状态生成一个观测值,而由此生成的观测的随机序列称为观测序列(observation sequence).

HMM是一个三元组,由初始状态概率向量、状态转移概率矩阵和观测概率矩阵决定,即: $$ \lambda = (A,B,\pi),其中\pi是初始状态概率向量,A是状态转移概率矩阵,B是观测概率矩阵 $$ 定义的形式如下: $$ 设Q是所有可能的状态的集合,V是所有可能观测的集合。Q={q_1,q_2,q_3...q_N},V={v_1,v_2,..v_M},\ 其中N是所有可能的状态数,M是所有观测数。\ I是长度为T的状态序列,O是对应的观测序列。I=(i_1,i_2...i_T),O=(o_1,o_2...o_T).\ A是状态转移概率矩阵:\ A=[a_{ij}]{N \times N},其中a{ij}=P(i_{t+1}=q_j|i_t=q_t),i=1,2,3...N;j=1,2,...N\ 是时刻t处于状态q_i的条件下在时刻t+1转移到状态q_j的概率。\ B是观测概率矩阵:\ B=[b_j(k)]_{N \times M},其中,b_j(k)=P(o_t=v_k|i_t=q_t),k=1,2,..M;j=1,2,...N\ 是在时刻t处于状态q_j的条件下生成观测v_k的概率。\ \pi是初始状态概率向量:\ \pi=(\pi_i),其中,\pi_i=P(i_j=q_i),i=1,2,...N\ 是在时刻t=1处于状态q_i的概率。\ $$ 从定义可知,隐马尔科夫模型做了两个基本假设:

  • 齐次马尔可夫性假设。即假设隐藏的马尔可夫链在任意时刻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(o_t|i_T,o_T,o_{T-1},o_{T-1},...,i_{t+1},o_{t+1},i_{t},i_{t-1},o_{t-1},...,i_1,o_1)=P(o_t|i_t) $$

纯粹这样看定义,一堆的数学公式,可能看得不是很懂,那么可以采用概率图的方式来理解HMM模型,如图所示:

图中的一行⭕表示隐变量的集合,称为状态序列;●表示可观测的集合,称为观测序列,由图可看出,第一个状态变量会影响第二个状态变量,同时还会影响第一个观测变量,依次递推下去,隐马尔可夫模型从状态变量看是一个影响一个的,可以理解成时间序列模型,其适用范围为文本分析,比如标注问题

三个基本问题

概率计算算法

给定模型和观测序列,那么计算在该模型下观测序列出现的概率的方法有三种:直接计算法、前向算法、后向算法。

直接计算法

$$ \begin{aligned} P(O|\lambda) = \sum_I P(O|I,\lambda)P(I|\lambda) = \sum_{i_1,i_2,\cdots,i_T} \pi_{i_1}b_{i_1}(o_1)a_{i_1 i_2}b_{i_2}(o_2) \cdots a_{i_{T-1} i_T}b_{i_T}(o_T) \end{aligned}\ 首先观察求和符号中b有T项,a有T-1项,\pi有1项,一共有2T项,求和是从i_1,i_2,\cdots,i_T不同的取值求和,\对于i_1从状态集合{q_1,q_2,...q_N}中取值有N个,i_2取值有N个……i_T取值有N个,所以求和范围有N^T项,\要对N^T个范围进行求和,每一个求和范围都需要O(T)个计算量,所以计算复杂度为\2T \times N^T=2TN^T=O(TN^T)。 $$

前向算法

$$ 输入:隐马尔可夫模型\lambda,观测序列O。\ 输出:观测序列概率P(O|\lambda)。\ (1)初值:\alpha_1(i)=\pi_i b_i(o_1), \quad i=1,2,\cdots,N\ (2)递推,对t=1,2,\cdots,T-1,\alpha_{t+1}(i)=\left[\sum_{j=1}^N \alpha_t(j) a_{ji} \right]\ b_i(o_t+1), \quad i=1,2,\cdots,N\(3)终止。P(O|\lambda)=\sum_{i=1}^N \alpha_T(i) $$

可是为何是这样子计算的吗?从数学的角度来推导下具体的算法计算方式—— $$ 1.首先最终终止的那个公式的推导:\ 将\alpha_t(i)的时刻t的观测值o_1,o_2,\cdots,o_t及状态值q_i,记作\alpha_t(i)=P(o_1,o_2,\cdots,o_t,i_t=q_i)(忽略\lambda的条件概率)。\ 前向算法用来做的就是概率计算,当\lambda给定时,观测值o_1,o_2,\cdots,o_t出现的概率为P(o_1,o_2,\cdots,o_T),\这是边缘概率,而P(o_1,o_2,\cdots,o_T, i_T=q_i)是联合概率,可得\\displaystyle P(o_1,o_2,\cdots,o_T) = \sum_{i=1}^N P(o_1,o_2,\cdots,o_T, i_T=q_i)=\sum_{i=1}^N \alpha_T(i)。\ 2.在递推过程中的公式推导:\ \because 根据定义\alpha_{t+1}(i) = P(o_1,o_2,\cdots,o_t,o_{t+1},i_{t+1}=q_i),\对比\alpha_{t}(i)=P(o_1,\cdots,o_t,i_t=q_i)少了o_{t+1},i_{t+1}=q_i,\ \therefore \alpha_{t+1}(i) = P(o_1,o_2,\cdots,o_t,o_{t+1},i_{t+1}=q_i) ......................联合概率\ =\sum_{j=1}^N P(o_1,o_2,...o_t,o_{t+1},i_{t+1}=q_i,i_t=q_j) .....................边缘概率\ =\sum_{j=1}^N P(o_1,o_2,...o_t,i_t=q_j)P(o_{t+1}|i_{t+1}=q_i)P(i_{t+1}=q_i|i_t=q_t)\ 又 \because P(o_{t+1}|i_{t+1}=q_i)=b_i(o_{t+1}) \ P(i_{t+1}=q_i|i_t=q_j)=a_{ji} \ P(o_1,o_2,\cdots,o_t, i_t=q_j)=\alpha_t(j)\ \displaystyle \therefore \sum_{j=1}^N P(o_1,o_2,\cdots,o_t, i_t=q_j)P(o_{t+1}|i_{t+1}=q_i)P(i_{t+1}=q_i|i_t=q_j) = \left[ \sum_{j=1}^N \alpha_t(j) a_{ji}\right] b_i(o_{t+1}) \ \displaystyle \therefore \alpha_{t+1}(i) = \left[ \sum_{j=1}^N \alpha_t(j) a_{ji}\right] b_i(o_{t+1}) $$

后向算法

$$ 输入:隐马尔可夫模型\lambda,观测序列O。\ 输出:观测序列概率P(O|\lambda)。\ (1)\beta_T(i)=1,\quad i=1,2,\cdots,N。\ (2)对t=T-1,T-2,\cdots,1,\beta_t(i)=\sum_{j=1}^N a_{ij}b_j(o_{t+1})\beta_{t+1}(j), \quad i=1,2,\cdots,N\(3)P(O|\lambda)=\sum_{i=1}^N \pi_i b_i(o_1) \beta_1(i) $$

学习问题

已知观测序列,需要估计参数。和之前讲过的很多模型是类似的,需要用一组训练数据集估计模型,之前可能是估计分类超平面,常用的两个方法:监督学习方法Baum-Welch算法,这两种方法的区别在于哪个算法更贴近应用,这两个方法的学习设定是不一样的。

监督学习方法

$$ 假设已给训练数据包含S个长度相同的观测序列和对应的状态序列{(O_1,I_1),(O_2,I_2),\cdots,(O_S,I_S)},\那么可以利用极大似然估计法来估计隐马尔可夫模型的参数。具体方法如下:\ (1)转移概率a_{ij}的估计。\ 设样本中时刻t处于状态i时刻t+1转移到状态j记为A_{ij},那么a_{ij}的估计是:\ \hat{a}{ij}=\frac{A{ij}}{\displaystyle \sum_{j=1}^N A_{ij}}, \quad i=1,2,\cdots,N; j=1,2,\cdots,N\ (2)观测概率b_j(k)的估计。\ 设样本中状态为j观测为k的频数是B_{jk},那么b_j(k)的估计是:\\hat{b}j(k)=\frac{B{jk}}{\displaystyle \sum_{k=1}^M B_{jk}}, \quad j=1,2,\cdots,N;k=1,2,\cdots,M\ (3)初始状态概率\pi_i的估计\hat{\pi}_i为S个样本中初始状态为q_i的频率。 $$

$$ 观测序列和状态序列都有S个样本,需要估计的参数:\ 首先初始状态\pi,如果直接用极大似然估计,就是看这S个样本中在初始状态时的各个取值的频率。\ 概率转移矩阵A,前一个状态i_t=q_i,后一个状态i_{t+1}=q_j的概率记作a_{ij},考察在S个观测序列中,\每个观测序列都是有(i_1,i_2,\cdots,i_{T-1},i_T),一共有S个这样的马尔可夫链,总计S(T-1)组,\在这些序列组中有多少是观测序列为q_i,然后在这些组中,又有多少组后一项的状态取值为q_j,\这样的比例就是a_{ij}的估计。 观测概率b_j(k)的估计也是类似的。 $$

Baum-Welch算法(EM算法)

$$ 输入:观测数据O=(o_1,o_2,\cdots,o_T)\ 输出:隐马尔可夫模型\ (1)初始化。\ 对n=0,选取a_{ij}^{(0)},b_j(k)^{(0)},\pi_i^{(0)}$,得到模型$\lambda^{(0)}=(A^{(0)},B^{(0)},\pi^{(0)})\ (2)递推,对n=1,2,\cdots,a_{ij}^{(n+1)}=\frac{\displaystyle \sum_{t=1}^{T-1} \xi_t(i,j)}{\displaystyle \sum_{t=1}^{T-1} \gamma_i(i)} \ b_j(k)^{(n+1)}=\frac{\displaystyle \sum_{t=1,o_t=v_k}^T \gamma_t(j)}{\displaystyle \sum_{t=1}^T \gamma_t(j)} \ \pi_i^{(n+1)} = \gamma_1(i) \其中\displaystyle \gamma_t(i)=\frac{\alpha_t(i)\beta_t(i)}{P(O|\lambda)}=\frac{\alpha_t(i)\beta_t(i)}{\displaystyle \sum_{j=1}^N \alpha_t(j)\beta_t(j)} \ \displaystyle \xi_t(i,j)=\frac{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{\displaystyle \sum_{i=1}^N \sum_{j=1}^N \alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)} $$

预测问算法

该算法其实就是一个标注问题,已知观测序列和模型参数,让计算机标注每一个观测值的状态,书中提出了两个算法:近似算法(得到的结果并不是全局最优解)、维特比算法(用动态规划思想求最优路径)。但是最常用的还是维特比算法。

维特比算法

维特比算法是求解给定的观测条件下,使得概率最大的状态变量的序列预测,也就是说,求解已知观测序列的出现的概率最大。 $$ 输入:模型\lambda=(A,B,\pi)和观测O=(o_1,o_2,\cdots,o_T)。 输出:最优路径I^=(i_1^,i_2^,\cdots,i_T^)。\ (1)初始化。\delta_1(i) = \pi_i b_i(o_1),\quad i=1,2,\cdots,N \ \psi_1(i)=0,\quad i=1,2,\cdots,N\(2)递推,对t=2, 3,\cdots,T \delta_t(i)=\mathop{\max} \limits_{1 \leqslant j \leqslant N}\left[\delta_{t-1}(j)a_{ji} \right] b_i(o_t),\quad i=1,2,\cdots,N \ \psi_t(i) = \mathop{\arg \max} \limits_{1 \leqslant j \leqslant N} \left[\delta_{t-1}(j)a_{ji} \right], \quad i=1,2,\cdots,N。\(3)终止。P^=\mathop{\max} \limits_{1 \leqslant i \leqslant N} \delta_T(i) \ i_T^=\mathop{\max} \limits_{1 \leqslant i \leqslant N} \left[\delta_T(i) \right] \(4)最优路径回溯,对t=T-1,T-2,\cdots,1 i_t^=\psi_{t+1}(i_{t+1}^)求得最优路径I^=(i_1^,i_2^,\cdots,i_T^). $$

具体的例子可以看书中的简单例子。但是要注意的是,在求得每个时刻的观测出现的概率的过程中,一定要记录每个概率最大路径的前一个状态,还有即使在回溯的过程中,要注意通过终点逐步逆向回溯的计算

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
鲁棒与最优控制 周克敏 高清中文版pdf

下载地址:网盘下载 内容简介   《鲁棒与最优控制》阐述了当代鲁棒与最优控制的主要和基本的内容,其中包含了作者对该理论作出的重要贡献。   《鲁棒与最优控制》共分二十一章。第一章为...

osc_d9817zy2
2018/07/07
40
0
《机器学习》升级版VI

(选填) 图片描述 http://www.chinahadoop.cn/course/984 主讲老师:邹博 小象学院独家签约计算机博士,现科学院从事科研教学工作;主持国家级科研项目2个,副负责1个,国家专利2项,研究方向...

wusejason
2017/10/18
2
0
《机器学习》升级版V 五

主讲老师: 邹博 小象学院独家签约 计算机博士,现科学院从事科研教学工作;主持国家级科研项目2个,副负责1个,国家专利2项,研究方向机器学习、数据挖掘、计算几何,应用于股票交易与预测、...

wusejason
2017/09/14
9
0
留给人类的时间不多了?现在不学机器学习更待何时!

立即参团 原价 ¥899.00 目前已达最低价 ¥399.00 >>点击文末阅读原文参团<< 机器学习(升级版Ⅶ) 课程目标:本课程特点是从数学层面推导最经典的机器学习算法,以及每种算法的示例和代码实...

bjweimengshu
2017/11/21
0
0
学好机器学习,这里有你需要的一切

立即参团 原价 ¥899.00 目前已达最低价 ¥399.00 >>点击文末阅读原文参团<< 机器学习(升级版Ⅶ) 课程目标:本课程特点是从数学层面推导最经典的机器学习算法,以及每种算法的示例和代码实...

燕哥带你学算法
06/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

什么是token及怎样生成token

什么是token   Token是服务端生成的一串字符串,以作客户端进行请求的一个令牌,当第一次登录后,服务器生成一个Token便将此Token返回给客户端,以后客户端只需带上这个Token前来请求数据即...

osc_zzg7fpke
47分钟前
10
0
往事不堪回首

开局一张图,内容全靠编 从12年大学毕业到如今,兜兜转转,依然在码工,码农,码代码的路上徘徊着,从最初的用asp.net写站点,写内部的CRM,内部管理系统,内部的XXX,很难想象内部的系统居然...

osc_9os5791s
48分钟前
23
0
java 事件监听器

package com.qimh.springbootfiledemo.listener;/** * 事件监听器 * 监听person 事件源的eat 和 sleep 的方法 * @author */public interface PersonListener { void doEa...

qimh
49分钟前
21
0
[原创.数据可视化系列之四]跨平台,多格式的等值线和等值面的生成

这些年做项目的时候,碰到等值面基本都是arcgis server来支撑的,通过构建GP服务,一般的都能满足做等值线和等值面的需求。可是突然有一天,我发现如果没有arcgis server 的话,我既然没法生...

osc_bvincwvq
49分钟前
16
0
个人作业——软件工程实践总结&个人技术博客

这个作业属于哪个课程 2020春|S班(福州大学) 这个作业要求在哪里 个人作业——软件工程实践总结&个人技术博客 这个作业的目标 总结软件工程课程以及实践中的收获 作业正文 其他参考文献 一...

osc_9piujk2x
49分钟前
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部