PDF《第八章 句法分析（三）》

第八章 句法分析

(三) 詹卫东 http://ccl.

pku.edu.cn/doubtfire/

2 提纲 ?

1 概率上下文无关文法(probabilistic context free grammar) ? 1.1 向内算法 ? 1.2 Viterbi算法 ? 1.3 向内向外算法 ?

2 部分分析方法(partial parsing / shallow parsing / chunking) ? 2.1 基于HMM的部分分析技术 ? 2.2 基于有限状态自动机的部分分析技术 ? 2.3 基于转换的错误驱动的部分分析技术

3 1 概率上下文无关文法 PCFG: 为CFG中的每条规则增加一个概率值 ∑ = → α α

1 ) (A P S?NP VP VP ? V NP NP ? N NP ? NP 的NP NP ? VP 的NP S?NP VP 1.0 VP ? V NP 1.0 NP ? N 0.3 NP ? NP 的NP 0.5 NP ? VP 的NP 0.2 CFG PCFG

4 分析树及其概率 老虎 咬死了 猎人 的狗NVN的NSVP NP NP NP NP N V N 的N1.0 1.0 0.3 0.5 0.3 0.3 P(S)=1.0*0.3*1.0*0.3*0.5*0.3 =0.0135

5 用概率来帮助判别歧义 sentence = John ate fish with bone S NP VP V NP ate NP PP fish P with bone John NP S NP VP V NP ate PP fish P with bone John NP VP t 1: t 2:

6 分析树的概率 与 句子的概率 S→NP VP 1.0 NP→NP PP 0.4 PP→P NP 1.0 NP→John 0.1 VP→V NP 0.7 NP→bone 0.18 VP→VP PP 0.3 NP→star 0.04 P→with 1.0 NP→fish 0.18 V→ate 1.0 NP→telescope 0.1

0009072 .

0 18 .

0 0 .

1 0 .

1 18 .

0 4 .

0 0 .

1 7 .

0 1 .

0 0 .

1 ) (

1 = * * * * * * * * = t P

0006804 .

0 18 .

0 0 .

1 0 .

1 18 .

0 0 .

1 7 .

0 3 .

0 1 .

0 0 .

1 ) (

2 = * * * * * * * * = t P

0015876 .

0 ) ( ) ( ) (

2 1 = + = t P t P sentence P

7 PCFG的三个问题 ) , | ( max arg G W tree P tree ) | ( max arg G W P G 给定一个符号串W=w1w2…wn和一部概率上下文无关文法G, (1) 如何快速计算由G产生符号串W的概率 P(W|G)? (2) 如果W有多种可能的语法树,如何选择一棵最好的树? (3) 如何调整G的规则概率参数,使得P(W|G)最大?

8 1.1 向内算法 S w1… wi-1 wi … wk wk+1 … wj wj+1 … wn A B C 非终结符A的内部概率(inside probability)定义为: 根据文法G从A推出词串wi…wj的概率,记做 αi , j(A) i ≤ j 向内变量

9 内部概率公式 ) | ... ( ) ( , A w w P A j i j i = α i <

j ∑ + = k C B j k k i A C w w B w w P , ,

1 ) | , ... , , ... ( ∑ + = k C B k i j k k i C B A w w w w P C B A w w P A C B P , ,

1 ) , , , ... | ... ( ) , , | ... ( ) | , ( 独立性假设 ∑ + = k C B j k k i C w w P B w w P A C B P , ,

1 ) | ... ( ) | ... ( ) | , ( ∑ + → = k C B j k k i C B BC A P , , ,

1 , ) ( ) ( ) ( α α i = j ) ( ) ( , i j i w A P A → = α

10 向内算法过程描述(自底向上) 输入:G=(S,VN,VT, P), 字符串W=w1w2…wn 输出:P(w1…wn|G)= α1,n(S) 1) 初始化: αi,i(A) =P(A?wi), A∈ VN ,

1 ≤i ≤n 2) 归纳计算:j从1到n,i从1到n-j,重复下面的计算 3) 结束: P(S?w1…wn|G)= α1,n(S) ∑ ∑ ∈ + ≤ ≤ + + + → = N V C B j i k i j i k k i j i i C B BC A P A , ,

1 , , ) ( ) ( ) ( ) ( α α α

11 向内算法计算过程示例 bone with fish ate John

5 4

3 2

1 1

2 3

4 5 α(NP)=0.18 α(P)=1.0 α(PP)=0.18 α(NP)=0.01296 α(NP)=0.18 α(VP)=0.015876 α(VP)=0.126 α(V)=1.0 α(S)=0.0015876 α(NP)=0.1 α(S)=0.0126

12 1.2 Viterbi算法 ? Viterbi变量δi, j(A):根据文法G,从非终结符A推导出词 串wi…wj,每个推导都有对应的概率值,其中概率最大 的记做δ i, j(A) . ? 比较: 向内变量αi , j(A) 是从A产生出词串wi…wj的所有推导的 概率之和.

13 Viterbi算法过程描述 输入:G=(S,VN,VT, P), 字符串W=w1w2…wn 输出:t* ( W在G下最可能的分析树 ) 1) 初始化: δi, i(A) = P(A?wi) A∈ VN ,