这样X是一个Markov链
Markov模型中的概率
• 随机转移矩阵 A aij=P(Xt+1=sj|Xt=si)
i, j, aij 0 • 初始状态的概率
i P( X1 si )
and
N
i, aij 1
j 1
N

i 1
i
1
Markov模型和n元文法
• N元文法模型是 Markov 模型 2元词模型就是Markov模型：当前的词 仅依赖于前一个词，而且这个依赖型 不随着词序列而变化。
i
下一状态名
Viterbi Algorithm
x1 xt-1 xt xt+1 xT
o1
ot-1
ot
ot+1
oT
ˆ T arg max (T ) X i
i
自后向前“读出” 最可能的状态序列
ˆ ^ (t 1) X t
X t 1
ˆ ) arg max (T ) P( X i
i
Viterbi algorithm(a Trellis algorithm)
S0: 他/r 做/v 了/u 一/m 个/q 报告/v 运用T1 S1: 他/r 做/v 了/u 一/m 个/q 报告/n
转换规则的模板（template）
• 改写规则：将词性标记x改写为y • 激活环境：
（1）当前词的前（后）面一个词的词性标记是z； （2）当前词的前（后）面第二个词的词性标记 是z； （3）当前词的前（后）面两个词中有一个词的 词性标记是z；……其中x，y，z是任意的词性 标记代码。
C(?) 是出现次数
平滑
• 为什么需要平滑呢？ 数据稀疏!
1. 收集更多的数据 从实用角度这并不是一个通用的解决方法， 在训练文本中总会遗漏一些情况。 2. 平滑 估计在训练文本中没有出现情况的出现概 率。降低已出现情况的概率，这样留下一 些概率“分给”没有出现的情况。
平滑
• 因为一些冷僻词不会在训练语料中出现，所以平滑词生成 概率比平滑转移概率更为的重要 • 加一( 简单平滑 )
• 为了和隐Markov模型相区别，我们有时也把 Markov模型成为显Markov模型（HMM）。
Markov假设
• 一序列（可能按时间排列）的随机变量不是相互 独立的，每一个随机变量的值依赖于序列中前一 个随机变量。对于许多这样的系统，我们可以合 理的假设：我们只需要知道当前的随机变量的值， 就可以来预测所有将来的随机变量，我们并不需 要知道随机变量序列中所有过去的值。
P( w1,n | t1,n ) P(t1,n ) P( wi | t1,n )
i 1 n
词的相互独立性
一个词的词形只依 赖于它自身的词性
P(tn | t1,n1 ) P(tn1 | t1,n2 ) ... P(t2 | t1 )
P( wi | ti )
i 1 n
arg max P(t1,...,n | w1,...,n )
t1,..., n
应用贝叶斯规则
arg max
t1,n t1,n
P ( w1,n | t1,n ) P (t1,n ) P ( w1,n )
arg max P ( w1,n | t1,n ) P (t1,n )
VMM Tagger原理
Markov假设
• 假设X=(X1,……,XT) 是随机变量的序列，它从某 个有限集S={s1,……,sN} 中取值，这个有限集被称 作是状态空间。
• 当X满足Markov性质时，X被称作Markov链。什 么是Markov性质呢？
Markov性质
• 有限历史 Limited Horizon: P(Xt+1=sk|X1,……,Xt)=P(Xt+1=sk|Xt) • 时间不变 Time invariant(stationary): P(Xt+1=sk|Xt) = P(X2= sk|X1)
l k C ( w , t ) 1 l j P( w | t ) C (t j ) K j
高效的标注算法
• 为了计算下面的式子，是不是需要知道长度为n的 句子中所有可能的标注序列t1,n呢？

t 1,n arg max P(t1,n | w1,n ) P(wi | ti ) P(ti | ti 1 )
P(Ot k | X t si , X t 1 s j ) bijk
HMMs vs VMMs
O
b12k
a11
O
b11k
a12 s1 a21
b21k
a22 s2
b22k
O
O
Markov Model Taggers
• X—标注序列, S—标注集, O—词集
(―O‖ 是HMM中的观察值，那我们为什么称它为MM taggers呢? 为什么不是HMM taggers? 后面会有解释)
o1
ot-1
ot
ot+1
oT
j (0) j
DP 递归的开始
Viterbi Algorithm
x1 xt-1 xt xt+1
o1
ot-1
ot
ot+1
oT
j (0) j
j (t 1) max i (t )aijb jo
i
t 1
递归开始 下一状态概率
t 1
j (t 1) arg max i (t )aijb jo
• 模型 μ=(A, B, )
状态集 输出 初始状态概率 状态转移概率
S {s1 ,...,s N } K {k1 ,...,k M } { i }, i S A {aij }, i, j S B {bijk }, i, j S , k K
符号发射概率
Viterbi algorithm
t1,n i 1
n
这样算法的复杂度就是指数阶的。 一个高效的算法就是 Viterbi algorithm
Viterbi Algorithm
• 动态规划 • 寻径算法
Viterbi Algorithm
t1
…
tj
(j) (j)
Viterbi Algorithm
x1 xt-1 j
o1
ot-1
ot
t
2. 递推
j (t 1) arg max i (t )aijbijo ,1 j N
1i N
t
结束
X T 1 arg max i (T 1)
1 i N

Xt

X t 1

(t 1)
注意
• 在训练时，我们能够观察到Markov模型的状态，但是在 标注时我们只能观察到词。所以我们说在MM Tagging时 我们使用的实际上是一个混合的方法： • 在训练时构造VMMs ，但是在标注时把它们当作是 HMMs。 • 但为什么不称它为HMM Tagger呢？
根据模板可能学到的转换规则
• T1：当前词的前一个词的词性标记是量词（q） 时，将当前词的词性标记由动词（v）改为名词 （n）； • T2：当前词的后一个词的词性标记是动词（v） 时，将当前词的词性标记由动词（v）改为名词 （n）； • T3：当前词的后一个词的词性标记是形容词（a） 时，将当前词的词性标记由动词（v）改为名词 （n）； • T4：当前词的前面两个词中有一个词的词性标记 是名词（n）时，将当前词的词性标记由形容词 （v）改为数词（m）；……
词性标注
关于标注
总体说来，汉语的词性标注和英语的词 性标注在方法上没有明显的不同。 比较典型的标注算法有：
基于规则的方法。国外在70年代初主要采用 这种方法，著名的TAGGIT系统，利用3300条上下 文规则，对100万词次的Brown语料库标注正确率 到77%。
关于标注
基于统计的方法。80年代初，随着经验主义方 法在计算语言学中的重新崛起，统计方法在语料库词 性标注中又占据了主导地位。CLAWS标注系统对LOB语 料库的标注正确率达到96%左右。 混合策略。国内北京大学计算语言学研究所 提出了一种先规则、后统计的规则和统计相结合的标 注算法，其准确率达到了96.6%。
• Markov model taggers: 假定一个词的词性 只依赖于前一个词的词性(有限历史) ，而且， 这个依赖性不随着时间而变化（时间不变） • 如同大多数的概率模型，这两个Markov假 设只是对于实际情况一个近似。例如，有 限历史假设并不能覆盖长距离依存的问题。
VMM Tagger原理
转换规则的形式
• 转换规则由两部分组成
– 改写规则（rewriting rule） – 激活环境（triggering environment）
• 一个例子：转换规则T1
– 改写规则：将一个词的词性从动词（v）改为名词 （n）； – 激活环境：该词左边第一个紧邻词的词性是量词（q）， 第二个词的词性是数词（m）
ot+1
oT
j (t ) max P( x1...xt 1 , o1...ot 1 , xt j , ot )
x1 ...xt 1
一个状态序列，使得：观察到直到t-1时刻 的各观察值，当前状态是状态j以及t时刻的 观察值出现的概率最大。
Viterbi Algorithm
x1 xt-1 j
HMM tagger
• 标注过程和 VMM tagger一样。 • 区别在于怎样训练这个模型。 • 如果我们没有足够的训练语料，我们可以使用HMM来学 习标注序列（使用Forward-Backward算法）
基于转换的错误驱动 的词性标注方法
• Eric Brill (1992,1995) • Transformation-based error-driven part of speech tagging • 基本思想：