- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
P ( O , | Q ,) P ( O | Q ,) P ( Q |) i 1 b i 1 ( O 1 ) a i 1 i 2 b i 2 ( O 2 ) . . . a i T 1 i T b i T ( O T )
9
（3）求和：P ( O | )P ( O |Q ,) P ( Q | ) i 1 b i 1 ( O 1 ) a i 1 i2 b i2 ( O 2 ) ...a iT 1 iT b iT ( O T )
Markov模型
4
2.隐马尔科夫模型
隐马尔可夫模型（HMM）是一种在Markov链的基础上发展起来的统计信号模型， 能够利用收集的训练样本进行自适应学习。 一个HMM是不确定的、随机的有限状态自动机，由不可观测的状态转移过程(一 个Markov链)和可观测的观察生成过程组成。按观测值是离散还是连续的，HMM 可分为离散型和连续型。我们这里主要介绍离散HMM。
则显然有：
aij≥0，i, j
N
aij 1, i, j
j 1
3
上述模型称为一阶Markov模型。 如把条件（1）适当放松，任一时刻的随机变量只依赖于前两（三，…，k）个时刻 的随机变量，则此模型为两（三，…，k）阶Markov模型。 以上随机过程可以称为可观测Markov模型，因为此过程的输出在每一个时间点是一 个状态，并且每一个状态对应一个可观测事件。
隐马尔科夫模型（HMM）
1
Table of Contents
1. 马尔科夫模型 2. 隐马尔科夫模型 3. HMM基本问题
3.1 HMM评估问题 3.2 HMM解码问题 3.3 HMM学习问题
4. HMM应用背景
4.1 自动文本分类 4.2 汉语词性标注 1. 4.3 汉语自动分词 2. 4.4 文本信息抽取 3. 4.5 其他应用领域
Ii 1 ,i2ຫໍສະໝຸດ ,...,i T3、算法评价
由于每一时刻点所到达的状态有N种可能，所以总的不同的状态序列有 N T 种。其中
每一个状态序列需要2T-1次乘法运算。所以总的运算量为 N T (2T 1) 次乘法运算
（此外还需要 N T 1 次加法运算）。
穷举算法的时间复杂度为 O (T N T ) ，在求解 P(O | ) 的过程中存在大量的重复计
1(i)=ibi(O 1), 1 ≤ i ≤ N
(2)递归，计算t+1时刻处于各隐状态（对应观测值为
O
）的概率:
t1
N t+ 1 (j) [ t(i)a ij]b j(O t 1 ), 1 ≤ t ≤ T - 1 ,1 ≤ j ≤ N
7
3.HHM基本问题
HMM理论有3个基本问题： （1）评估问题
给定一个HHM的模型 和观测序列 O(O1,O2,...,OT)，如何高效的计算此模型产生 的观测序列的概率 P(O | )
（2）解码问题
给定一个HHM的模型 和观测序列 O(O1,O2,...,OT)，如何选择对应最佳的状态序
列，使它在某种状态下最优（出现的概率最大），以较好地解释观测值 （3）学习问题（训练问题）
给定观测序列 O(O1,O2,...,OT)，如何调整模型参数 ，以使得观察序列出现的概
率 P(O | ) 最大化
8
3.1评估问题
解决HHM评估问题的典型算法有穷举搜索直接计算法、前向算法和后向算法： 一、穷举搜索直接计算 1、算法思想 列举长度为T的所有可能的状态序列 Q{q1,q2,...,qT}，分别求解各个状态序
算，不适用于大的模型和较长的序列。
10
二、前向算法
1、算法思想 到达某网格节点的概率可以用前一时刻N个 节点的概率表示出来。 前向算法通过已经保存了的子路径来计算新 路径的概率。
HHM网状结构
11
2、算法过程
定义到时刻t，部分观测序列为O{O1,O2,...,Ot}，状态 q i 的前向概率为： t( i ) P ( O 1 ,O 2 ,...,O t,q t S i|),2 ≤ t ≤ T (1)初始化,计算t=1时处于各隐状态（对应观测值为 O 1 ）的概率:
2
1.马尔科夫模型
马尔科夫(Markov)模型是由俄罗斯数学家Andrei A．Markov于20世纪初提出的一个 统计模型。
有限状态的离散时间Markov链是一个长度为T的随机变量序列Q={q1,q2...qT}，q t 的
取值范围是有限状态集 {S1,S2...SN}。
假定它满足以下两个条件：（1）任一时刻的随机变量只依赖于前一时刻的随机 变量：
P ( q t= S j |q t 1 = S i , q t 2 = S k . . . ) P ( q t= S j |q t 1 = S i)
（2）时间无关性（马尔科夫性）：
P ( q t= S j |q t 1 = S i ) P ( q 2 = S j |q 1 = S i ) a i j , 1 ≤ i ,j ≤ N
列与观测序列的联合概率 P(O,Q| )，最后求和得到 P(O | )
2、算法过程
（1）状态序列 Q{q1,q2,...,qT}出现的概率为：P (Q | )i1 a i1 i2a i2 i3...a iT 1 iT （2）对依于据其贝中叶一斯种公状式态：序列，观测序列的概率为：P ( O |Q ,) b i 1 ( O 1 ) b i2 ( O 2 ) ...b i T ( O T )
B为观察值概率分布矩阵，表示在j状态输出观察值k的概率：
B(bj(k))N*M ，其中:b j( k ) = P ( O t= k |q t= S j) , 1 ≤ j ≤ N ,1 ≤ k ≤ M
5
隐马尔科夫模型
6
HMM拓扑结构
左右型的HMM
含间隔跳转的HMM
含并行结构的HMM
全连通的HMM
一阶离散HMM是一个五元组：{N ,M ,,A ,B }，可以简写为 {A,B,}，
其中N是Markov链状态数;M是状态可能生成的观察值数;(1,...,N) 表示初
始状态概率向量，其中 iP (q 1= S i), 1 ≤ i≤ N
A为状态转换概率分布矩阵，表示i状态向j状态转换的概率：
A(aij)N*N ，其中: a ij= P (q t 1 = S j|q t= S i), 1 ≤ i,j≤ N
