列，推测生成它的底层事件的序列。 例子：观察一个人每天带雨伞情况，推测天气情况。
隐藏的状态序列
表层的可观察序列
例子：
HMM应用例子
序列标注 分词
词性标注 句法分析
观察序列 字序列 词序列 词序列
隐藏的状态序列 词序列 词性序列 句子结构
HMM假设
一个随机过程，有一个观察序列 O=O1 , O2...OT ，该过 程隐含着一个状态序列 X=X1 , X2 ... XT
例：Markov模型描述道琼斯工业指数。
5 个连续上涨交易日的概率
Pup up up up up P s1,s1,s1,s1,s1
p1a11a11a11a11
0.5 0.64 0.0648
π{pi}[0.5,00.].32,
Markov模型
Bigram：一阶Markov模型.
p ( t) o p ( e t) p ( o |t) p ( e |o )
从一种疾病转变到另一种疾病的概率
输出概率：B
某一疾病呈现出某一症状的概率
初始分布p ：初始疾病的概率
问题：
给定：某人症状为：咳嗽→咽喉痛→流涕→发烧。 O = O1, O2 …OT 计算：这个观察序列的概率P(O)
HMM－例子
方案1
x1
xt-1
xt
xt+1
xT
o1
ot-1
ot
ot+1
HMM
HMM，从状态产生输出
HMM
HMM，不同状态可能产生相同输出
HMM
HMM，从弧中产生输出
HMM
HMM，输出带有概率
Hidden Markov Model（HMM）
模型原理
表层事件：可观察序列； 底层事件：隐藏的、不可见的；状态序列。 表层事件是由底层事件引起的。根据表层事件的可观察序
HMM－例子
假设：
某一时刻只有一种疾病，且只依赖于上一时刻疾病（有限历史假设） 一种疾病只有一种症状，且只依赖于当时的疾病（输出条件独立性假设）
症状(观察值)： O = O1, O2 …OT
发烧，咳嗽，咽喉肿痛，流涕
疾病(状态值)： X = X1 , X2…XT
感冒，肺炎，扁桃体炎
转移概率：A
oT
P(B)P(BX,)
X
P(A,B|C) = P(A|B,C)P(B|C)
P ( O |) P ( O ,X |) P ( O |X ,) P ( X |)输出条件独立假设
X
X
N
P ( O |X ,) P ( O 1 , O 2 .O . T |x . 1 x 2 .x T . ,. ) P ( o i|x i ) b x 1 o 1 b x 2 o 2 .b x . T o T .
模型参数学习、训练问题
HMM相关的算法
评价问题：向前算法
定义向前变量 采用动态规划算法
解码问题：Viterbi算法
采用动态规划算法
模型参数训练、学习问题：
向前-向后算法 EM算法
问题1：评价（Evaluation）
给定一个模型μ= (A,B,p) ，
计算某一观察序列 O = O1, O2…OT 的概率P(O|μ)
Markov链
（p, A）
状态序列 X1, X2 ... XT
符号输出 观察值序列 过程（B） O1 , O2 ... OT
HMM的组成示意图
状态序列
HMM模型－图示
X1
X2
XT-1
XT-1
状态空间
观察序列 时间
HMM模型－图示
x1
xt-1
xt
xt+1
xT
o1
ot-1
ot
ot+1
oT
HMM模型表示
i 1
有限历史假设
p N
P ( X |) P ( x 1 x 2 .x T .|. ) P ( x 1 ) P ( x i|x i 1 ) x 1 a x 1 x 2 a x 2 x 3 .a x . T 1 x T .
i 2
方案1
x1
xt-1
xt
xt+1
xT
o1
ot-1
ot
Markov模型
状态空间 S={t,i,p,a,h,e}
初始概率 p ={1.0,0,0,0,0}
状态转移概率矩阵
aij
t
i
p
a
h
e
t
0.3
0.3
0.4
4
0.6
h
1.0
e
1.0
Markov模型
计算状态序列的概率
P(X1,X2, Xt)P(X1)P(X2|X1) P(Xt |X1X2 Xt1)
假设
Markov假设 假设1：有限历史假设：P(Xi|X1 , X2…Xi-1) = P(Xi|Xi-1)
假设2：时间不动性假设
输出条件独立性假设
输出仅与当前状态有关
P(O1 , O2...OT | X1 , X2 ... XT) = Πt P(Ot|Xt)
HMM模型－图示
两个随机过程
P(X1)P(X2|X1) P(Xt|Xt1)
T1
p a X1
XTXT1
t1
例子：
P ( t,i,p ) P ( X 1 t) P ( X 2 i|X 1 t) P ( X 3 p |X 2 i) 1 .0 * 0 .3 * 0 .6 0 , 18
The Markov Chain – Ex 2
t = t+1
End
HMM的三个基本问题
给定一个观察序列O = O1, O2…OT和模型μ=(A,B,p)
问题1：
如何有效计算观察序列 O = O1, O2…OT 的概率P(O|μ) ？ 评价问题
问题2：
如何寻找最佳的状态序列 X = X1, X2… XT ？ 解码问题
问题3：
如何训练模型参数μ=(A,B,p) ，使得P(O|μ)概率最大？
模型表示
五元组(S, V, p ,A,B)
符号表
S ：状态集合， {s1, …, sN}。 V：输出字母表， {v1, …, vM}
模型参数
p ：初始状态概率。 p = {pi}; iS
A ：状态转移概率。 A = {aij}; i, jS B ：符号输出概率。 B = {bjk}; jS,kV
序列
状态序列： X = X1 , X2…XT 输出序列： O = O1 , O2 …OT
Xt S
Ot V
HMM过程
HMM过程描述
t = 1；
初始状态概率分布为p。从状态si开始的概率为pi；
Forever do 从状态si 向状态sj转移,并输出观察符号Ot = k 。 其中，状态转移概率为aij。符号输出概率为 bjk