两个假设：
有限视野： P(Xt+1| X1, X2…Xt) = P(Xt+1|Xt) 时间不变性: 这种条件依赖，不随时间的改变而改变。
若随机过程满足上述假设，则是一个Markov 过程（链）。
Markov模型
模型表示：
三元组(S, p , A)
S ：状态的集合， S = {s1,s2 …sN}。
列，推测生成它的底层事件的序列。 例子：观察一个人每天带雨伞情况，推测天气情况。
隐藏的
序列标注 分词
词性标注 句法分析
观察序列 字序列 词序列 词序列
隐藏的状态序列 词序列 词性序列 句子结构
HMM假设
一个随机过程，有一个观察序列 O=O1 , O2...OT ，该过 程隐含着一个状态序列 X=X1 , X2 ... XT
p(toe) p(t) p(o | t) p(e | o)
HMM
HMM，从状态产生输出
HMM
HMM，不同状态可能产生相同输出
HMM
HMM，从弧中产生输出
HMM
HMM，输出带有概率
Hidden Markov Model（HMM）
模型原理
表层事件：可观察序列； 底层事件：隐藏的、不可见的；状态序列。 表层事件是由底层事件引起的。根据表层事件的可观察序
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|μ)概率最大？
假设
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模型－图示
两个随机过程
序列
状态序列： 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
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模型表示
例：Markov模型描述道琼斯工业指数。
5 个连续上涨交易日的概率
Pup up up up up P s1,s1,s1,s1,s1
p1a11a11a11a11
0.5 0.64 0.0648
π {p i } [0.5,0.2,0.3]
Markov模型
Bigram：一阶Markov模型.
初始概率 p ={1.0,0,0,0,0}
状态转移概率矩阵
aij
t
i
p
a
h
e
t
0.3
0.3
0.4
i
0.4
0.6
p
1.0
a
0.4
0.6
h
1.0
e
1.0
Markov模型
计算状态序列的概率
P( X1, X 2 , X t ) P( X1)P( X 2 | X1) P( X t | X1X 2 X t1)
P( X1)P( X 2 | X1) P( X t | X t1)
T 1
p X1
a XT XT 1
t 1
例子：
P(t,i, p) P( X1 t)P( X 2 i | X1 t)P( X 3 p | X 2 i) 1.0*0.3*0.6 0,18
The Markov Chain – Ex 2
模型表示
五元组(S, V, p ,A,B)
符号表
S ：状态集合， {s1, …, sN}。 V：输出字母表， {v1, …, vM}
模型参数
p ：初始状态概率。 p = {pi}; i S
A ：状态转移概率。 A = {aij}; i, j S B ：符号输出概率。 B = {bjk}; j S, k V
模型参数学习、训练问题
HMM相关的算法
评价问题：向前算法
定义向前变量 采用动态规划算法
解码问题：Viterbi算法
采用动态规划算法
模型参数训练、学习问题：
向前-向后算法 EM算法
问题1：评价（Evaluation）
给定一个模型μ= (A,B,p) ，
计算某一观察序列 O = O1, O2…OT 的概率P(O|μ)
p：初始状态的概率。 p ={p1,p2…pN}; pi =P(X1= si)
A ：状态转移概率矩阵。 A={aij}; aij = P(Xt+1=sj|Xt=si)
状态图
n
pi 1
i 1
n
aij 1
j 1
相当于一个有限状态自动机 转移弧上有概率
Markov模型
状态空间 S={t,i,p,a,h,e}
HMM－例子
假设：
某一时刻只有一种疾病，且只依赖于上一时刻疾病（有限历史假设） 一种疾病只有一种症状，且只依赖于当时的疾病（输出条件独立性假设）
症状(观察值)： O = O1, O2 …OT
发烧，咳嗽，咽喉肿痛，流涕
疾病(状态值)： X = X1 , X2…XT
感冒，肺炎，扁桃体炎
转移概率：A
Markov模型 HMM 词性标注
目录
Markov模型
描述：
一个随机过程上的随机变量序列，X = X1, X2…Xt
随机变量取值于有限集 S = {s1,s2 …sN}。S称为状态空间。
状态序列
X
X
X
X
Markov模型
模型描述
一个随机过程，存在着一个随机变量序列 X = X1, X2…Xt 随机变量的取值于有限集 S = {s1,s2 …sN}, S称为状态空间。