自然语言处理学习笔记-lecture07-句法分析01

算法的时间复杂度分析
设 $n$为输入句子的长度，$C$ 为上下文无关文法中的非终结符的数目，$S$ 为点规则的状态数目(大于 $CFG$ 规则的数目)，显然 $S>C$。因为 Agenda 表中的元素形式为 $X(i,j)$，因此, Agenda 表中最大的元素个数为:$C{n}^2$。由于ActiveArc 中的元素形式为:$A\to \alpha \circ X(i,j)$，所以ActiveArc 表中最大的元素数目为:$S{n}^2$，Chart 表中的边的形式为:$A(i,j)$，因此，Chart 表中最大的元素数目为:$C{n}^2$。由于算法对于长度为 n 的输入句子要执行 n 次循环，因此，Chart 算法最大执行的操作次数为:$O(K{n}^3)$

优点：算法简单
弱点：算法效率低，需要高质量的规则，分析结果与规则质量密切相关;难以区分歧义结构。

CYK分析算法

Coke-Younger-Kasami (CYK) 算法

• 对Chomsky 文法进行范式化:
• 自下而上的分析方法
• 构造$(n+1)\times (n+1)$的识别矩阵，$n$为输入句子长度，假设输入句子$x=w_1{w}_2\cdots w_n,w_i$为构成句子的单词$n=|x|$

其中识别矩阵构成：方阵对角线以下全部为0，主对角线以上的元素由文法G的非终结符构成，主对角线上的元素由输入句子的终结符号(单词)构成，构造步骤如下：

• 首先构造主对角线，令 $t_{0,0}=0$，然后，从 $t_{1,1}$ 到$t_{n,n}$，在主对角线的位置上依次放入输入句子$x$ 的单词$w_i$。
• 构造主对角线以上紧靠主对角线的元素$t_{i,i+1}$，其中$i=0,1,2,\cdots ,n-1$，对于输入句子$x=w_1{w}_2\cdots w_n$，从$w_1$开始分析
  假设在文法G 的产生式集中有一条规则:$A\to w_1$则$t_{0,1}=A$，以此类推，如果有$A\to w_{i+1}$则$t_{i,i+1}=A$
• 按平行于主对角线的方向，一层一层的向上填写矩阵的各个元素$t_{i,j}$，其中$i=0,1,\cdots ,n-d,j=d+i,d=2,3,\cdots ,n$，如果存在一个正整数$k,i+1\le k\le j-1$，在文法$G$的规则集中有产生式$A\to BC$，并且$B\in t_{i,k},C\in t_{k,j}$那么将$A$写到矩阵$t_{ij}$位置上，判断句子$x$由文法$G$所产生的充要条件是$t_{0,n}=S$

以“他/P 喜欢/V 读/V 书/N”为例：


优点：简单易行
弱点：必须对文法进行范式化处理，无法区分歧义

概率上下文无关文法

形式：$A\to \alpha ,p$
约束：${\sum }_{\alpha }p(A\to \alpha )=1$
计算分析树概率的基本假设

• 位置不变性:子树的概率与其管辖的词在整个句子中所处的位置无关，即对于任意的 $k,p(A_{k(k+C)}\to w)$一样
• 上下文无关性:子树的概率与子树管辖范围以外的词无关，即$p(A_{kl}\to w|任何超出k\sim l范围的上下文)=p(A_{kl}\to w)$
• 祖先无关性:子树的概率与推导出该子树的祖先结点无关，即$p(A_{kl}\to w|任何除A以外的祖先结点)=p(A_{kl}\to w)$

句法分析树的概率计算方法示例：

对于给定的句子 $S$ ，两棵句法分析树的概率不等，$P(t_1)>P(t_2)$，因此，可以得出结论:分析结果$t_1$正确的可能性大于$t_2$。

PCFG的三个问题

• 给定句子$W=w_1{w}_2\cdots w_n$和PCFG $G$，如何快速的计算$p(W|G)$
• 给定句子$W=w_1{w}_2\cdots w_n$和PCFG $G$，如何快速地选择最佳句法结构树?
• 给定句子$W=w_1{w}_2\cdots w_n$和PCFG $G$，如何调节$G$的参数，使得$p(W|G)$最大

假设文法$G(S)$的规则只有两种形式：
$$\begin{gathered} A\to w,w\in V_T \\ A\to BC,B,C\in V_N \end{gathered}$$
可以通过范式化处理，使CFG 规则满足上述形式。这种假设的文法形式称为乔姆斯基范式(Chomsky normal form, CNF)。

内向算法或外向算法

解决第一个问题-快速地计算句子的句法树概率

内向算法

基本思想:利用动态规划算法计算由非终结符 A 推导出的某个字串片段$w_i{w}_{i+1}\cdots w_j$的概率${\alpha }_{ij}(A)$，语句$W=w_1{w}_2\cdots w_n$的概率即为文法$G(S)$中$S$推导出的字串的概率${\alpha }_{1n}(S)$
$${\alpha }_{ij}(A)=p(A\Rightarrow w_i{w}_{i+1}\cdots w_j)$$
计算${\alpha }_{ij}(A)$的递推公式：
$$\begin{gathered} {\alpha }_{ii}(A)=p(A\to w_i) \\ {\alpha }_{ij}(A)=\sum _{B,C\in V_N}\sum _{i\le k\le j}p(A\to BC){\alpha }_{ik}(B){\alpha }_{(k+1)j}(C) \end{gathered}$$
内向算法描述：
输入：文法$G(S)$，语句$W=w_1{w}_2\cdots w_n$
输出：$p(S\Rightarrow w_1{w}_2\cdots w_n)$

• 初始化：${\alpha }_{ii}(A)=p(A\to w_i),A\in V_N,1\le i\le j\le n$
• 归纳计算：$j=1,\cdots ,n,i=1,\cdots ,n-j,$重复下列计算：外层循环为$j$
  $${\alpha }_{i(i+j)}(A)=\sum _{B,C\in V_N}\sum _{i\le k\le i+j}p(A\to BC){\alpha }_{ik}(B){\alpha }_{(k+1)(i+j)}(C)$$
• 终结：$p(S\Rightarrow w_1{w}_2\cdots w_n)={\alpha }_{1n}(S)$

外向算法

定义：外向变量${\beta }_{ij}(A)$是文法初始符号$S$推导出语句$W=w_1{w}_2\cdots w_n$的过程中，到达扩展符号串$w_1\cdots w_{i-1}A{w}_{j+1}\cdots w_n$的概率$(A=w_i\cdots w_j)$
$${\beta }_{ij}(A)=p(S\Rightarrow w_1\cdots w_{i-1}A{w}_{j+1}\cdots w_n)$$
${\beta }_{ij}(A)$表示除了以$A$为根节点的子树以外的概率，其递推公式：
$$\begin{gathered} {\beta }_{1n}(A)=\delta (A,S) \\ {\beta }_{ij}(A)=\sum _{B,C}\sum _{k>j}{\beta }_{ik}(B)p(B\to AC){\alpha }_{(j+1)k}(C)+\sum _{B,C}\sum _{k<i}{\beta }_{kj}(B)p(B\to CA){\alpha }_{k(i-1}(C) \end{gathered}$$
相应的示意图：

外向算法描述：
输入：PCFG $G=(S,N,T,P)$，语句$W=w_1{w}_2\cdots w_n$
输出：${\beta }_{ij}(A),A\in N,1\le i\le j\le n$

• 初始化：${\beta }_{1n}(A)=\delta (A,S),A\in N$
• 归纳：$j$从$n-1$到$0$，$i$从$1$到$n-j$，重复计算：
  $${\beta }_{i(i+j)}(A)=\sum _{B,C}\sum _{i+j<k\le n}p(B\to AC){\alpha }_{(i+j+1)k}(C){\beta }_{ik}(B)+\sum _{B,C}\sum _{1\le k<i}p(B\to CA){\alpha }_{k(i-1}(C){\beta }_{k(i+j)}(B)$$
• 终结：$p(S\Rightarrow w_1{w}_2\cdots w_n)={\beta }_{1n}(S)$

Viterbi 算法

解决第二个问题-最佳分析结果搜索
Viterbi 变量${\gamma }_{ij}(A)$是由非终结符 $A$ 推导出语句$W$中子字串$w_i{w}_{i+1}\cdots w_j$的最大概率。变量${\psi }_{i,j}$用于记忆字串$W=w_1{w}_2\cdots w_n$的Viterbi 语法分析结果。
Viterbi 算法描述:
输入：文法$G(S)$，语句$W=w_1{w}_2\cdots w_n$
输出：${\gamma }_{1n}(S)$

• 初始化：${\gamma }_{ii}(A)=p(A\to w_i),A\in V_N,1\le i\le j\le n$
• 归纳计算：$j=1\cdots n,i=1\cdots n-j$重复下列计算：
  $$\begin{gathered} {\gamma }_{i(i+j)}(A)=\underset{B,C\in V_N;i\le k\le i+j}{\max }p(a\to BC){\gamma }_{ik}(B){\gamma }_{(k+1)(i+j)}(C) \\ {\psi }_{i(i+j)}(A)=\underset{B,C\in V_N;i\le k\le i+j}{argmax}p(a\to BC){\gamma }_{ik}(B){\gamma }_{(k+1)(i+j)}(C) \end{gathered}$$
• 终结：$p(S\Rightarrow w_1{w}_2\cdots w_n)={\gamma }_{1n}(S)$

内外向算法

解决第三个问题-参数估计
基本思路：如果有大量已标注语法结构的训练语料，则可直接通过计算每个语法规则的使用次数，用最大似然估计方法计算 PCFG 规则的概率参数，即:
$$\hat{p}(N^j\to \zeta )=\frac{C(N^j\to \zeta )}{{\sum }_{\gamma }C(N^j\to \gamma )}$$
多数情况下，没有可利用的标注语料，只好借助 EM (Expectation Maximization) 迭代算法估计PCFG的 概率参数。
初始时随机地给参数赋值，得到语法G0，依据 G0 和训练语料，得到语法规则使用次数的期望值，以期望次数运用于最大似然估计，得到语法参数新的估计值，由此得到新的语法 G1，由 G1 再次得到语法规则的使用次数的期望值，然后又可以重新估计语法参数。循环这个过程，语法参数将收敛于最大似然估计值。
例如给定CFG $G$和训练数据$W=w_1{w}_2\cdots w_n$，语法规则$A\to BC$使用次数的期望值为：
C o u n t ( A → B C ) = ∑ 1 ≤ i ≤ k ≤ j ≤ n p ( A i j , B i k , C ( k + 1 ) j ∣ w 1 ⋯ w n , G ) = 1 p ( w 1 ⋯ w n ∣ G ) ∑ 1 ≤ i ≤ k ≤ j ≤ n p ( A i j , B i k , C ( k + 1 ) j , w 1 ⋯ w n ∣ G ) = 1 p ( w 1 ⋯ w n ∣ G ) ∑ 1 ≤ i ≤ k ≤ j ≤ n β i j ( A ) p ( A → B C ) α i k ( B ) α ( k + 1 ) j ( C )

• 初始化：随机给$p(A\to \mu )$，使加和为1，由此得到语法$G_0$，令$i=0$
• EM迭代：
  E步：由$G_i$根据上面的求期望值公式得到两个期望值
  M步：由M步得到的期望值，重新估计$p(A\to \mu )$，得到$G_{i+1}$
• 循环：重复EM步骤，直到$p(A\to \mu )$收敛。

PCFG的优点：可利用概率减少分析过程的搜索空间;可利用概率对概率较小的子树剪枝，加快分析效率;可以定量地比较两个语法的性能。
弱点：分析树的概率计算条件非常苛刻，甚至不够合理。

短语结构分析方法评估

内部评测 (intrinsic evaluation)-对评测方法本身的评测，用于指导句法分析系统及其语法的开发过程。主要指标有:

• 语法的覆盖性 (grammatical coverage)
• 平均分析基数 (average parse base)
• 结构一致性 (structural consistency)
• 排序的一致性 (best-first/ranked consistency)等

对比评测 (comparative evaluation )：用于对比不同系统之间的性能差别，主要评测指标和方法包括:

• 树相似性 (tree similarity)
• 模型的熵 (或困惑度) (entropy/perplexity)
• 语法评估兴趣小组 (grammar evaluation interest group, GIEG)的评测方案等

句法分析器性能评测：目前使用比较广泛的句法分析器评价指标是PARSEVAL测度，三个基本的评测指标:

• 精度(precision):句法分析结果中正确的短语个数所占的比例，即分析结果中与标准分析树(答案)中的短语相匹配的个数占分析结果中所有短语个数的比例
• 召回率(recall):句法分析结果中正确的短语个数占标准分析树中全部短语个数的比例
• F-measure
• 交叉括号数 (crossing brackets):一棵分析树中与其他分析树中边界相交叉的成分个数的平均值。

分析树中除了词性标注符号以外的其他非终结符节点通常采用如下标记格式:XP-(起始位置:终止位置)。其中，XP为短语名称;(起始位置:终止位置)为该节点的跨越范围，起始位置指该节点所包含的子节点的起始位置，终止位置为该节点所包含的子节点的终止位置。在计算PARSEVAL指标时，通常需要计算分析结果与标准分析树之间括号匹配的数目或括号交叉的数目。
例如标准答案:S-(0:11), NP-(0:2), VP-(2:9), VP-(3:9), NP- (4:6), PP-(6:9), NP-(7:9), *NP-(9:10)
系统结果:S-(0:11), NP-(0:2), VP-(2:10), VP-(3:10), NP- (4:10), NP-(4:6), PP-(6:10), NP-(7:10)
只有加粗的短语和标准一样，所以：
$$\begin{gathered} P=\frac{3}{8}\times 100\%=37.5\% \\ R=\frac{3}{8}\times 100\%=37.5\% \end{gathered}$$