第六章 马尔可夫模型
马尔可夫模型
马尔可夫模型是一种统计模型,广泛地应用在语音识别，词性自动标注，音字转换，概率文法等各个自然语言处理的应用领域。
马尔可夫(1856～1922)，苏联数学家。切比雪夫的学生。在概率论、数论、函数逼近论和微分方程等方面卓有成就。
经过长期发展，尤其是在语音识别中的成功应用，使它成为一种通用的统计工具。
马尔可夫模型的典型应用
语音识别
音字转换
词性标注
回顾:n-gram语言模型
链规则：
N-gram语言模型:
N-1阶马尔可夫过程（链）
仅适用一种概率分布进行统计推导，例如在trigram模型中，
马尔可夫假设（特征）
设 X=(X1, .., Xt)是随机变量序列，其中每个随机变量的取值 在有限集 S={s1, …, sn}, S称为状态空间, 马尔可夫特征是：
有限历史假设（Limited (Horizon，Context,History）):
P(Xt+1=sk|X1, .., Xt)=P(X t+1 = sk |Xt)
时间不变性假设（Time Invariant）（马尔可夫过程的稳定性假设）:
这种条件依赖，不随时间的改变而改变。
如果X具有这些特征，那么这个随机变量序列称为一个马尔可夫过程（链）
N阶马尔可夫模型
Trigram的情形：
只需修改状态空间的定义
定义新的变量 使得
并且约定：
马尔可夫模型的形式化表示
一个马尔可夫模型是一个三元组(S, , A)
其中 S是状态的集合，是初始状态的概率, A是状态间的转移概率。
马尔可夫模型的图形表示
状态集合
分布
由状态i到状态j之间的转移弧上有一个条件转移概率:
隐马尔可夫模型(HMM)
各个状态（或者状态转移弧）都有一个输出,但是状态是不可见的。
最简单的情形:不同的状态只能有不同的输出
隐马尔可夫模型
增加一点灵活性：不同的状态，可以输出相同的输出：
隐马尔可夫模型
再增加一点灵活性：输出在状态转移中进行。
隐马尔可夫模型
最大的灵活性：在状态转移中以特定的概率分布输出
HMM的形式化定义
HMM是一个五元组 (S, K, , A, B) ，其中 S是状态的集合，K是输出字符的集合， 是初始状态的概率，A是状态转移的概率。B是状态转移时输出字符的概率。
马尔可夫过程程序
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）
问题1评价（Evaluation）
给定一个模型 ，如何高效地计算某一输出字符序列的概率
oT
o1
ot
ot-1
ot+1
方案1
oT
o1
ot
ot-1
ot+1
x1
xt+1
xT
xt
xt-1
方案1（Cont.）
oT
o1
ot
ot-1
ot+1
x1
xt+1
xT
xt
xt-1
算法复杂度太高，需要
方案2向前过程（forward procedure）
使用动态规划方法实现更加高效的算法
动机：对于任意一个长度为t+1的状态序列来说，其前t个输出字符出现的概率是相同的
定义:向前变量
oT
o1
ot
ot-1
ot+1
x1
xt+1
xT
xt
xt-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
问题2 解码（decoding）
给定一个输出字符序列O，和一个模型 ，如何确定产生这一序列概率最大的状态序列
oT
o1
ot
ot-1
ot+1
问题2 解码（decoding）cont.
在t时刻到达状态j，输出字符Ot时，输出前面t-1个字符的最可能路径的概率
Viterbi algorithm
初始化
递归
结束
得到最优路径
1
2
3
states
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 参数估计
已知输出字符序列，找到产生该序列可能性最大的模型
无法用分析方法求解
给定一个模型和输出字符序列，任意设定初始参数值，通过不断循环更新参数的方法，设法达到最优
Baum 1970
oT
o1
ot
ot-1
ot+1
基本思想
1. 设定模型的初始值, μold.
2. 基于μold ，计算输出O 的概率
3. 如果 P(O|μnew)-P(O| μold) < 某个设定的阈值 (或者达到某个固定的循环次数), 停止.
4. 否则, μold ← μnew 返回步骤 2.
Baum-Welch算法
oT
o1
ot
ot-1
ot+1
A
B
A
A
A
B
B
B
B
状态转移弧Si->Sj的转移概率
处于状态Si的概率
Baum-Welch算法（cont.）
Baum-Welch (cont.)
oT
o1
ot
ot-1
ot+1
A
B
A
A
A
B
B
B
B
Now we can compute the new estimates of the model parameters.
Baum-Welch (cont.)
又称为向前向后算法（Forward-backward algorithm）
Baum 等人证明了
经常得到局部最优解-爬山法的固有缺点
一种通用机器学习算法-期望最大值（Expectation Maximum Algorithm）算法的特殊形式
一种无指导的机器学习算法，效果较有指导为差。
基于HMM的词性标注
词性标注（Part-of-Speech tagging）
回顾：
作用：句法分析的前期步骤
难点：兼类词
基于规则的词性标注
基于转换的错误驱动的词性标注
基于HMM的词性标注
基于HMM的词性标注
问题的形式化
设词性标记为M个
标记集合: {t_1,..,t_M}.
词表中词的个数为 V
词集合: {w_1,..,w_V}.
设有一个由n个词构成的词序列
S = w1,w2…wn
目标为找到最优的词性序列T = t1,t2…tn
基于HMM的词性标注
如何计算 和 ?
为使问题简化，假定：
词wi 的出现，仅仅依赖于它的词性标记，不依赖于其他因素（例如它前一个词的出现）
标记 ti 的出现仅仅条件依赖于它前面的标记ti-1 (马尔科夫假设)
基于HMM的词性标注
HMM的状态集合：词性标记集合
HMM输出字符集合：词汇集合
[notation:ti is the ith tag in a tag sequence <t>,
t_i represents the ith tag in the tag set {t_1,..,t_M}]
pi : [p(t_i|*start*)] 状态t_i的起始概率
aij : [p(t_j|t_i)] 从状态 t_i 到状态 t_j的转移概率
bjk : [p(w_k|t_j)] 状态t_j的词w_k发射概率
参数训练
模型的参数未知
假设有已经标注好的语料库:
S = w1,w2…wn
T = t1,t2…tn
如何从语料库中得到这样的参数
使用最大相似度估计
音字转换
状态集：词
发射字符集：拼音
pi : [p(t_i|*start*)] 状态t_i的起始概率
aij : [p(t_j|t_i)] 从状态 t_i 到状态 t_j的转移概率
bjk : [p(w_k|t_j)] 状态t_j的词w_k发射概率
结束语
