Markov模型
及隐马尔科夫模型
Markov模型概况
Markov模型是一种统计模型，广泛
地应用在语音识别，词性自动标注，
音字转换，概率文法等各个自然语
言处理的应用领域。
Markov(1856～1922)，苏联数学家。
切比雪夫的学生。在概率论、数论、
函数逼近论和微分方程等方面卓有
成就。
Markov模型概况
经过长期发展，尤其是在语音识别
中的成功应用，使它成为一种通用
的统计工具。
语音识别、音字转换、分词、词性
标注、命名实体识别、句法分析
……
回顾：n-gram语言模型
链规则：
N-gram语言模型
N-1阶马尔可夫过程（链）
回顾：n-gram语言模型（续）
仅使用一类概率分布进行统计推导
例如在trigram模型中，使用
位置 1 2 3 4 5 6
词 忘 不 了 我 的 老师
7 8 9 10 11 12 13
也 忘 不 了 我 的 同学
Markov假设（特征）
设 是随机变量
序列，其中每个随机变量的取值在
有限集
，称为状态空间，
Markov特征是：
有限历史假设(Limited History
(Horizon,Context))：
Markov假设（特征）
时间不变性假设（Time
Invariant）（马尔可夫过程的稳
定性假设）:
这种条件依赖，不随时间的改
变而改变
如果X具有这些特征，那么这个随
机变量序列称为一个马尔可夫过程
（链）
N阶Markov模型
只需修改状态空间的定义
定义新的变量 使得
并且约定：
Markov模型的形式化表示
一个马尔可夫模型是一个三元组(S, π,
A)，其中 S是状态的集合，π是初始状
态的概率， A是状态间的转移概率
Markov模型的图形表示
状态集合
概率分布
由状态 到状态 之间的转移弧上有条
件转移概率:
Markov模型的图形表示
S={*,t,e,a,o}
π=(1,0,0,0,0)
A=
* t e a o
*
t
e 1
a
o 1
隐Markov模型(Hidden Markov
M Model)
各个状态（或者状态转移弧）都有一个
输出，但是状态是不可见的
最简单的情形:不同的状态只能有不同的
输出
隐Markov模型
增加一点灵活性：不同的状态，可以输
出相同的输出：
隐Markov模型
再增加一点灵活性：输出在状态转移中
进行。
隐Markov模型
最大的灵活性：在状态转移中以特定的
概率分布输出
HMM的形式化定义
HMM是一个五元组 (S, K, π, A, B) ，其
中 S是状态的集合，K是输出字符的集
合， π是初始状态的概率，A是状态转
移的概率。B是状态转移时输出字符的
概率。
HMM的形式化定义
S={*,1,2,3,4}
K={t,o,e}
π=(1,0,0,0,0)
A=
p(1|*)=
p(3|*)=
p(4|1)=
p(2|1)=
p(4|2)=1
p(2|4)=1
p(1|3)=1
B=
p*1(t)=
p*1(o)=
p*1(e)=
马尔可夫过程程序
t:= 1;
以概率πi在状态 si 开始 (., X1=i)
Forever do
Move from state si to state sj with
probability aij (., Xt+1 = j)
Emit observation symbol ot = k with probability bijk
t:= t+1
End
隐马尔科夫模型的三个基本问题
给定一个模型 ，如何高效
地计算某一输出字符序列的概率
给定一个输出字符序列O，和一个模型
，如何确定产生这一序列概率最大的状
态序列
给定一个输出字符的序列O，如何调整
模型的参数使得产生这一序列的概率最
大
网格（Trellis）
网格（Trellis）
问题1：评价（Evaluation）
给定一个模型 ，如何
高效地计算某一输出字符序列的概率
oTo1 otot-1 ot+1
方案1
oTo1 otot-1 ot+1
x1 xt+1 xTxtxt-1
方案1（Cont.）
oTo1 otot-1 ot+1
x1 xt+1 xTxtxt-1
算法复杂度太高，需要
方案2向前过程（forward
procedure）
使用动态规划方法实现更加高效的算法
定义:向前变量
oTo1 otot-1 ot+1
x1 xt+1 xTxtxt-1
方案2向前过程（forward
procedure）cont.
方案2向前过程（forward
procedure）cont.
向前过程算法
1、初始化
2、推导
3、总合
向前过程例
R R G B
1×.6
.6
0×.2
.0
0×.0
.0
.6
.2
.2
.2
.5
.3
.0
.3
.7
R
G
B
.5
.6
.4
.4
.1
=[1 0 0]T
.5×.6
.18
.6×.2
.048
.0
.4×.2
.1×.0
.4×.0
.5×.2
.018
.6×.5
.0504
.01116
.4×.5
.1×.3
.4×.3
.5×.2
.0018
.6×.3
.01123
.01537
.4×.3
.1×.7
.4×.7
向后过程概述
定义 βt(i) = P(ot+1ot+2…oT|qt=Si,λ).
在某一特定状态下看到尾部输出为
ot+1ot+2…oT 的概率
算法：
- 初始化: βT(i) ← 1,1 ≤ i ≤ N
- 推导: βt(i) ← ∑1≤j≤N aijbj,ot+1βt+1(j)
T-1 ≥ t ≥ 1, 1 ≤ i ≤ N
向后过程概述
P(O|λ)= ∑1≤j≤Nπibi,o1β1(i)).
- 算法效率与向前算法相同
- 用途：
参数训练问题的一个重要的组成部分
问题2 解码（decoding）
给定一个输出字符序列O，和一个模型
，如何确定产生这一序列概率最大的状
态序列？
oTo1 otot-1 ot+1
问题2 解码（decoding）
问题2 解码（decoding）cont
Delta 为在t时刻到达状态j，输出字符Ot时，输出前面t-1
个字符的最可能路径的概率
Viterbi algorithm
初始化
递归
结束
得到最优路径
Viterbi算法例
.6
.2
.2
.2
.5
.3
.0
.3
.7
R
G
B
.5
.6
.4
.4
.1
π =[1 0 0]T
R R G B
.5×.2
.0018
.00648
.01008
.4×.3
.1×.7
.4×.7
.6×.3
.6
1×.6
0×.2
.0
0×.0
.0
.5×.2
.018
.6×.5
.036
.00576
.4×.5
.1×.3
.4×.3
.5×.6
.18
.6×.2
.048
.0
.4×.2
.1×.0
.4×.0
问题3 参数估计
oTo1 otot-1 ot+1
问题3 参数估计
已知输出字符序列，找到产生该序列可
能性最大的模型
无法用分析方法求解
给定一个模型和输出字符序列，任意设
定初始参数值，通过不断循环更新参数
的方法，设法达到最优
Baum 1970
基本思想
设定模型的初始值, μold.
2. 基于μold ，计算输出μnew 以及O 的
概率
3. 如果 P(O|μnew)-P(O| μold) < 某个设
定的阈值 (或者达到某个固定的循环次
数), 停止.
4. 否则, μold ← μnew 返回步骤 2.
Baum-Welch算法
oTo1 otot-1 ot+1
A
B
AAA
BBB B
状态转移弧Si
->Sj的转移概
率
处于状态Si的
概率
Baum-Welch算法（cont.）
Baum-Welch (cont.)
oTo1 otot-1 ot+1
A
B
AAA
BBB B
采用此式估算隐
马模型的初始概
率，转移概率以
及字符发射概率
Baum-Welch算法
又称为向前向后算法（Forward-
backward algorithm）
Baum 等人证明了
经常得到局部最优解-爬山法的固有缺点
Baum-Welch算法
一种通用机器学习算法-期望最大值
（Expectation Maximum Algorithm）
算法的特殊形式
一种无指导的机器学习算法，效果较有
指导为差
基于HMM的词性标注
词性标注（Part-of-Speech tagging）
回顾：
作用：句法分析的前期步骤
难点：兼类词
基于规则的词性标注
基于转换的错误驱动的词性标注
基于HMM的词性标注
基于HMM的词性标注
如何计算 和 ?
为使问题简化，假定：
词wi 的出现，仅仅依赖于它的词性标记，不依赖
于其他因素（例如它前一个词的出现）
标记 ti 的出现仅仅条件依赖于它前面的标记ti-1 (马
尔科夫假设)
基于HMM的词性标注
HMM的状态集合：词性标记集合
HMM输出字符集合：词汇集合
ti 为词性标记集中的第i个词性标记
基于HMM的词性标注
pi : [p(ti|*start*)] 词性标记ti的起始概率
aij : [p(tj|ti)] 从词性标记 ti 到词性标记tj的
转移概率
bjk : [p(wk|tj)] 词性标记tj对应的词wk的发
射概率
参数训练
模型的参数未知
假设有已经标注好的语料库:
S = w1,w2…wn
T = t1,t2…tn
如何从语料库中得到这样的参数
使用最大相似度估计
音字转换
状态集：词汇的集合
发射字符集：拼音
pi : p(ti|*start*) 状态ti的起始概率
aij : p(tj|ti)从状态 ti到状态 tj的转移概率
bjk :p(wk|tj) 状态tj的词wk发射概率
词网格分词的情形如何？
附录1 音字转换系统
回顾：音字转换
理论：
yi zhi mei li de xiao hua
一
以
…
一 直
一 致
之
枝
每
没
美 丽
美
… …
里
李
丽
…
的
地
得
德
…
肖
小
校 花
…
花
话
…
消 化
规则与统计相结合
我们需要的音字转换结果是：
“一枝美丽的小花”
采用规则的方法
短语结合规则：
A+NP->NP
A+“的”+NP->NP
M+“枝”+NP->NP
短语匹配算法
规则与统计相结合
从词网格到元素网格
yi zhi mei li de xiao hua
一
以
…
一 直
一 致
之
枝
每
没
美 丽
美
… …
里
李
丽
…
的
地
得
德
…
肖
小
校 花
…
花
话
…
消 化
小 花
美 丽 的 小 花
一 枝 美 丽 的 小 花
其他问题
系统挂接问题
万能挂接
Windows支持
Mac OS, Linux, Windows CE, Symbian
OS,……
知识产权问题
合作沟通问题
营销策略问题
……
结 束
