仅与最近的j个状态有关
• 一阶马尔可夫过程
• 任一时刻为某状态的概率仅与上一时刻的状态相关
仅与上一个状态有关
5
-
隐马尔可夫模型
• 隐马尔可夫模型（Hidden Markov Model，缩写 为HMM）
• 状态不可见
• 在t时刻，隐藏的状态以一定的概率激发出可见的 符号 x ( t )，其取值表示为 v1,v2,v3,
end
• 最后
for t=T-1 to 1（路径回溯）:
end
28
-
学习问题
• 从一组训练样本D={X1, X2,…, Xn} 中，学习HMM 的参数向量 θ
• 不存在根据训练集确定HMM最优参数的算法
• 常用算法
向前向后算法（forward-backward algorithm）
23
计算复杂度 O(c2T) O(cTT)
-
• HMM为
例子
24
-
例子
•
已知t=0时状态为
，即
1
0a100.2,1a110.3,
2a120.1,3a130.4
• 现观测到的序列为 V4{v1,v3,v2,v0} • 计算最可能的隐状态序列？
25
-
•解
例子
1(2) 1 .0027
练习：把此图填写完整，并回溯最佳状态路径
7
-
一个例子
• 盒子编号不可见 • 每次从任一盒子中取出一个小球 • 隐藏状态：盒子编号 • 可见符号：小球 • 盒子i中取出各种小球的概率
• Байду номын сангаас到某个特定小球序列的概率？
8
-
离散HMM的符号表示
• 隐藏状态集
• 可见符号集 • 状态序列
完整的HMM参数向量
• 观察序列
• 状态转移概率
• 观察到可见符号的概率
• 长度为T的离散时间上的可见符号序列
X T x ( 1 ),x (2 ), ,x ( T )
例如：X 6 v 5 ,v 1 ,v 1 ,v 5 ,v 2 ,v 3
• 观察到可见符号的概率
b jk P (x ( t) v k| ( t)j) b jk 1
k
6
-
隐马尔可夫模型
• 状态转移图
Ch 04. 参数模型
-2009
1
Part 1 隐马尔可夫模型
-2009
2
马尔可夫链
• 状态 i,i1,2,
• t时刻的状态 • 长度为T的离散时间上的状态序列
例如：
• 转移概率（矩阵）
为从状态
i 到
的转移概率
j
3
-
马尔可夫链
• 状态转移图
4
-
马尔可夫链
• j-阶马尔可夫过程
• 下一时刻为某个状态的概率仅与最近的j个状态有关
• 初始状态概率
9
-
HMM三大核心问题
• 估值问题
• 已知
• 观察到特定符号序列X • HMM模型参数向量
•求
• 似然函数
• 解码问题
• 已知
• 观察到特定符号序列X • HMM模型参数向量
•求
• 最有可能产生X的隐状态序列
10
-
HMM三大核心问题
• 学习（或参数估计）问题
• 已知
• 观察到特定符号序列X
26
-
解码问题
• 对于较长的序列，Viterbi算法可能导致计算机下 溢出
• 改进：基于对数的Viterbi算法
• 优点
• 变乘为加 • 避免下溢出 • 结果与Viterbi算法一样
27
-
解码问题
• 对数Viterbi算法
• 初始化
对每个隐状态i，计算
• 递归
for t=2 to T:
对每一个隐状态j，计算
t时刻的计算仅涉及上一步的结果，以及 ( t ) ，(t 1)，和 x ( t )
• HMM向前算法 • HMM向后算法
13
-
估值问题
• HMM向前算法
定义 i ( t )：t时刻在状态i，并且已观察到x(1)，x(2)，…… x(t)的概率
• 初始化
对每一个隐状态i，计算
• 递归
for t=2 to T
•
贝叶斯决策
P(θi | X)
P(X|θi)P(θi)
c
P(X|θi)P(θi)
i1
• 决策结果
i*argm ax(P (X |θ i)P (θ i))
i
20
-
HMM用于语音识别
• “从左到右”（left-to-right）HMM
发音“viterbi”的“从左到右”HMM
• 为每个单词发音建立一个HMM，其参数为 θ i • 用向前算法计算发音序列X的类条件概率 P(X| θi) • P (θ i ) 取决于语言本身和上下文语义 • 用贝叶斯公式计算X的后验概率 P(θi | X) • 最大后验概率指示语音内容
(T
)
bix(T c
)（假设T时刻每个状态的概率
• 递归
for t=T-1 to 1
对每一个隐状态i，计算 i(t)c aijj(t1)bix(t)
end
j1
• 最后
c
P(X|θ) ii(1) i1
计算复杂度 O(c2T) O(cTT)
16
-
• HMM为
例子
• ：吸收状态，即序列结束 时的必然状态。该状态产 生唯一的特殊可见符号v0 ，表示HMM过程结束
17
-
例子
•
已知t=0时状态为
，即
1
0a100.2,1a110.3,
2a120.1,3a130.4
• 现观测到的序列为 V4{v1,v3,v2,v0} • 计算HMM产生这个特定观测序列的概率？
18
-
例子
•解
19
-
HMM用于分类
• 为每一个类别建立一个HMM
• 每个HMM有自己的参数向量 θ i ，该参数向量可以从属于 类别i的样本中学习（估计）得到。
•求
• 模型参数向量 的估计值
例如：ML估计
11
-
估值问题
• 直接计算HMM模型产生可见长度为T的符号序列X 的概率
其中，
表示状态 (1 ) 的初始概率
假设HMM中有c个隐状态，则计算复杂度为 O (cT T ) ！
例如：c=10，T=20，基本运算1021次！
12
-
估值问题
• 解决方案
• 递归计算
对每一个隐状态j，计算
end
• 最后
计算复杂度 O(c2T) O(cTT)
14
-
估值问题
• HMM向前算法
15
-
估值问题
• HMM向后算法（向前算法的时间反演版本）
定义的概 i (率t )：t时刻在状态i，并且已逆向观察到x(T)，x(T-1)，…… x(t)
• 初始化
对每一个隐状态i，计算i
相同）
21
-
解码问题
• 已知一个观察序列XT，寻找最可能的隐状态序列 • 穷举法
• 把所有可能的隐状态序列的概率都计算一遍 • 计算复杂度O (cT T )
22
-
解码问题
• Viterbi算法
• 初始化
对每个隐状态i，计算
• 递归
for t=2 to T:
对每一个隐状态j，计算
end
• 最后
for t=T-1 to 1（路径回溯）: end