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

1 ≤i ≤n 2) 归纳计算:j从1到n,i从1到n-j,重复下面的计算 3) 结束:P(t*) = δ1, n(S) t*的根节点为S(文法开始符号);

从?1,n(S)开始回溯,得到S的最优树结构 ) ( ) ( ) ( max ) ( ,

1 , ;

, , C B BC A P A j i k k i j i k i V C B j i i N + + + ≤ ≤ ∈ + → = δ δ δ ) ( ) ( ) ( max arg ) ( ,

1 , ;

, , C B BC A P A j i k k i j i k i V C B j i i N + + + ≤ ≤ ∈ + → = ? δ δ ? 变量 用于记 录分析 过程的 历史

14 Viterbi算法过程示例 NP 0.1 V 1.0 NP 0.18 P 1.0 NP 0.18 VP 0.126 NP 0.01296 S 0.0126 PP 0.18 VP 0.006804 VP 0.009072 S 0.0009072 John ate fish with bone

1 5

3 2

4 15 Viterbi算法过程示例(续) (1,11) 0.0009072

5 1 S

12 (2,9) 0.009072

5 2 VP

11 (4,8) 0.006804

5 2 VP

10 (3,8) 0.01296

5 3 NP

9 (6,7) 0.18

5 4 PP

8 0.18

5 5 NP

7 1.0

4 4 P

6 (1,4) 0.0126

3 1 S

5 (2,3) 0.126

3 2 VP

4 0.18

3 3 NP

3 1.0

2 2 V

2 0.1

1 1 NP

1 ? δ 终点 起点 节点 节点号

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

17 外部概率公式 ? ? ? ≠ = = S A S A A n ,

0 ,

1 ) ( ,

1 β ) | ... , , ... ( ) (

1 1

1 , G w w A w w P A n j i j i + ? = β ∑ ∑ <

? + ? <

+ + ? → → + → → = i h C B i h n j h k j C B k j n k i w w B P BA C P w w C w w P w w B P AB C P w w C w w P , ,

1 1

1 1 , ,

1 1

1 1 ) ... ( ) ( ) ... , , ... ( ) ... ( ) ( ) ... , , ... ( ∑ ∑ <

? <

+ → + → = i h C B i h j h k j C B k j k i B BA C P C B AB C P C , ,

1 , , , , ,

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

18 计算外部概率示例(自顶向下) with bone NP V NP S P NP PP NP VP VP S VP S α =0.1 α=1.0 α=0.18 α=1.0 α=0.18 α=0.126 α=0.01296 α=0.0126 α=0.18 α=0.009072 α=0.0009072 α=0.0006804 β =1.0 β=1.0 β=0.0015876 β =0.1 β =0.1 β =0.0054 β=0.0015876 β=0.0015876 β =0.07 β =0.00882 β=0.0015876 β =0.00882 β=0.0015876 β=0.0015876 β =0.00882 β=0.0015876 α=0.006804 β=0.015876 ate John fish

5 3

2 4

1 19 规则的概率 文法中每条规则的概率,可以用下面公式估计: ∑ → → = → γ γ ξ ξ ) ( ) ( ) ( A Number A Number A P S?NP VP P(S?NP VP) VP ? V NP P(VP?V NP) NP ? N P(NP?N) NP ? NP 的NP P(NP?NP 的NP) NP ? VP 的NP P(NP?VP 的NP) S?NP VP VP ? V NP NP ? N NP ? NP 的NP NP ? VP 的NP ) ( ) ( ) ( ) ( ) ( NP VP NP Number NP NP NP Number N NP Number N NP Number N NP P 的的→+→+→→=→20 规则使用次数的数学期望 规则 A?B C 使用次数的数学期望是给定语句条件下, A, B, C 这三个非终结符同时出现的概率 ) , ... | , , ( ) (

1 1

1 , G w w C B A P C B A Number n j k i n ,j k i,k j i ∑≤ ≤ ≤ ≤ + = → ) ... ( ) ... , , , (

1 1 ,

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

1 1

1 , n ,j k n j k i i,k j i w w P C B BC P(A A + ≤ ≤ ≤ ≤ ∑ → = α α β 公式①

21 规则的概率(续) ∑ → → = → γ γ ) ( ) ( ) ( A Number C B A Number C B A P ∑ ∑ ≤ ≤ ≤ + ≤ <

≤ ≤ → = n j i j i j i ,j k n j k i i,k j i A A C B BC P(A A

1 , ,

1 1 , ) ( ) ( ) ( ) ( ) ) ( α β α α β 公式②

22 向内向外算法过程描述 ? 初始化:随机地给P(A??) 赋值,使得Σ?P(A? ?) =1, 得到语法Gi , i =

0 ? 循环执行下面步骤,直至P(A??)收敛: ? 1) 根据公式①计算每条规则使用次数的期望值 ? 2) 根据上一步所得期望值,即根据公式②,重新估计 P(A??) , 得到语法Gi+1 向内向外算法示例,可参见陈小荷2000,第12章23 PCFG的优缺点 ? 优点 ? 可以对句法分析的歧义结果进行概率排序 ? 提高文法的容错能力(robustness) ? 缺点 ? 没有考虑词对结构分析的影响 ? 没有考虑上下文对结构分析的影响