自然语言处理基础-句法分析

发表于 | 分类于 | | 阅读次数: |

本文主要是对宗成庆老师《自然语言理解》讲义，第9章的一个学习笔记，同时，也参考了刘群老师《计算语言学》的句法分析讲义，所有的配图均来自这两个讲义。通过该讲义能够对句法分析是做什么的以及怎么做，有一个基本的认识。

句法分析介绍

句法分析(syntactic parsing)的任务是识别句子的句法结构(syntactic structure)，是从单词串得到句法结构的过程。不同的语法形式，对应的句法分析算法也不尽相同。句法分析的类型可以分为两类：

  • 短语结构分析(Phrase parsing)
    • 完全句法分析（Full parsing)—>针对整个句子
    • 局部句法分析（Partial parsing)—>针对句子中的一部分
  • 依存句法分析

由于短语结构语法（特别是上下文无关语法）应用得最为广泛，因此以短语结构树为目标的句法分析器研究得最为彻底。很多其他形式语法对应的句法分析器都可以通过对短语结构语法的句法分析器进行简单的改造得到。

人们在正常交流中所使用的语言，放在特定的环境下看，一般是没有歧义的，否则人们将无法交流（某些特殊情况如幽默或双关语除外）。如果不考虑语言所处的环境和语言单位上下文，将发现语言的歧义现象无所不在。但是，一般来说，语言单位的歧义现象在引入更大的上下文范围或者语言环境时总是可以被消解的。句法分析的核心任务就是消解一个句子在句法结构上的歧义。例如，对于下面的句子,可以得到两种句法分析结果。


mark
mark
mark

句法分析策略

目前，比较成熟的句法分析主要是基于上下文无关的分析方法，本文也主要介绍基于上下文无关的句法分析方法。句法分析策略指的是句法分析的过程中按照何种方式进行分析，通常采用的策略有：

  • 自顶向下分析法；
  • 自底向上分析法；
  • 左角分析法；
  • 其他策略。

常见的上下文无关语法的句法分析算法有：

  • 线图分析法（Chart parsing）
  • CYK算法；
  • Earley算法；
  • Tomita算法；
  • …

句法分析的过程也可以理解为句法树的构造分析过程。所谓自顶向下分析法也就是先构造句法树的根节点，再逐步向下扩展，直到叶结点；所谓自底向上分析法就是先构造句法树的叶节点，再逐步上上合并， 直到根节点。左角分析法是一种自顶向下和自底向上相结合的方法。

自顶向下的方法又称为基于预测的方法，也就是说，这种方法产生对后面将要出现的成分的预期，然后再通过逐步吃进待分析的字符串来验证预期。如果预期得到了证明，就说明待分析的字符串可以被分析为所预期的句法结构。如果某一个环节上出现了差错，那就要用另外的预期来替换（即回溯）。如果所有环节上所有可能的预期都被吃进的待分析字符串所“反驳”，那就说明待分析的字符串不可能是一个合法的句子，分析失败。

自底向上的方法也叫基于规约的方法。就是说，这种方法是先逐步吃进待分析字符串，把它们从局部到整体层层规约为可能的成份。如果整个待分析字符串被规约为开始字符号S，那么分析成功。如果在某个局部证明不可能有任何从这里把整个待分析字符串规约为句子的方案，那么就需要回溯。

例如，对于下面的一个句子及语法规则：
mark

采用自顶向下分析出句法结构的步骤如下：
mark
mark
mark
mark
mark
自底向上分析法及左角分析法与自顶向下分析方法类似，具体就不一一在举例说明。

句法分析算法

基于上下文无关的句法分析有多种，本文简要介绍线图分析算法、CYK算法和概率上下文无关算法PCFG。

线图(Chart)分析算法

线图分析法同样有3种策略来构建句法分析树，分别是：

  • 自底向上；
  • 自顶向下；
  • 从上到下和从下到上结合。

本文介绍基于自底向上的Chart分析算法。算法的具体情况如下：

  • 给定一组CFG规则：$XP \rightarrow \alpha_1…\alpha_n(n \geq 1)$
  • 给定一个句子的词性序列：$S=W_1W_2…W_n$
  • 构造一个线图：一组结点和边的集合
    mark
  • 建立一个二维表：记录每一条边的起始位置和终止位置。

执行如下操作：查看任意相邻几条边上的词性串是否与某条重写规则的右部相同，如果相同，则增加一条新的边跨越原来的相应的边，新增加边上的标记为这条重写规则的头（左部）。重复这个过程，直到没有新的边产生。

线图分析法中引入点规则，表示规则右部被规约（匹配）的程度。点规则的具体定义如下：
mark
线图分析法中用到如下数据结构：

  • 线图(Chart):保存分析过程中已经建立的成份（包括终结符和非终结符）、位置（包括起点和终点）。通常以n*n的数组表示（n为句子包含的词数）；
  • 代理表（代处理表）（Agenda):记录刚刚得到的一些重写规则所代表的成分，这些重写规则的右端符号串与输入的词性串（或短语标志串）中的一段完全匹配，通常以栈或线性队列表示；
  • 活动边集（ActiveArc）:记录那些右端符号串与输入串的某一段相匹配，但还未完全匹配的重写规则，通常以数组或列表存储。

基于如上定义的点规则和数据结构，线图分析法的算法描述如下：
从输入串的起始位置到最后位置，循环执行如下步骤：

(1) 如果待处理表（Agenda）为空，则找到下一个位置上的词，将该词对应的（所有）词类X附以(i,j)作为元素放到待处理表中，即X(i,j)。其中，i,j分别是该词的起始位置和终止位置，$j>i$,j-i为该词的长度。

(2) 从Agenda中取出一个元素X(i,j)

(3) 对于每条规则$A \rightarrow X\gamma$，将$A \rightarrow X \cdot \gamma(i,j)$加入到活动边集ActiveArc中，然后调用扩展弧子程序

扩展弧子程序:

(a) 将X插入图表(Chart)的(i，j)位置中。

(b) 对于活动边集(ActiveArc)中每个位置为$(k,i)(i \leq k < i)$的点规则，如果该规则具有如下形式：$A \rightarrow \alpha \cdot X$，如果A=S,则把S(1,n+1)加入到Chart中，并给出一个完整的分析结果；否则，将A(k,j)加入到Agenda表中。

(c) 对于每个位置为(k,i)的点规则:$A \rightarrow \alpha \cdot X \beta$，则将$A \rightarrow \alpha X \cdot \beta(k,j)$加入到活动边集中。

整体的流程大致可以描述为：从Agenda弹出元素，如果Agenda为空，则找下一个位置上的词，形成X(i,j)放入到Agenda中，然后对X(i,j)匹配所有的规则，形成点规则，加入到ActiveArc中，并扩展弧。扩展弧操作即将X(i,j)加入到Chart中，然后，检查活动边集上位置为(k,i)的点规则，进行合并，将合并出的点规则加入到ActiveArc中，并将(k,j)加入到Agenda表中，然后从Agenda中弹出元素，匹配规则，加入到Archive，然后在扩展弧，这样不断循环。

线图分析法的优点是算法简单，容易实现，开发周期短；但是，其算法效率低，时间复杂度为$Kn^3$且需要高质量的规则，分析结果与规则质量密切相关；也难以区分歧义结构。

CYK算法

CYK算法的全称是Coke-Younger-Kasami(CYK)算法，是一种自下而上的分析方法，其构造一个(n+1)*(n+1)的识别矩阵，n为输入句子长度。假设输入句子为$x=w_1w_2…w_n,w_i$为构成句子的单词，$n=|x|$。识别矩阵具有如下特点：

  • 方阵对角线以下全部为0；
  • 主对角线以上的元素由文法G的非终结符（句法成分）构成；
  • 主对角线上的元素由输入句子的终结符构成（单词）构成；

下图为识别矩阵的示例图：

mark

识别矩阵构造的步骤如下：

(1) 首先构造主对角线，另$t_{0,0}=0$，然后，从$t_{1,1}$到$t_{n,n}$在主对角线的位置上依次放入输入句子x的单词$w_i$。

(2) 构造主对角线上紧靠主对角线的元素$t_{i,i+1}$，其中，$i=0,1,2,…,n-1$。对于输入句子$x=w_1w_2…w_n$，从$w_1$开始分析。
如果在文法G的产生式集中有一条规则：$A \rightarrow w_1$，则$t_{0,1}=A$。以此类推，如果有$A \rightarrow w_{i+1}$则$t_{i,i+1}=A$。即，对于主对角线的每一个终结符$w_i$，所有可能推导出它的非终结符写在它的右边主对角线方的位置上。

(3) 按平行于主对角线的方向，一层一层地向上填写矩阵的各个元素$t_{i,j}$，其中，$i=0,1,…,n-d,j=d+i, d=2,3,…,n$。如果存在一个正整数k，$i+1 \leq k \leq j-1$，在文法G的规则集中有产生式$A \rightarrow BC$，并且，$B \in t_{i,k},C \in t_{k,j}$，那么，将A写到矩阵$t_{i,j}$位置上。

算法的示意图如下：

mark

下面就用具体的实例，来看CYK算法是如何进行句法分析的，对于给定的如下文法：

mark

分析句子”他喜欢读书”的句法结构。

(1) 首先，进行分词和词性标注：

他/P喜欢/V 读/v 书/N n=4

(2) 构造识别矩阵，并执行分析过程，具体如下：

首先，由规则$VP \rightarrow V V$，产生如下结果：

mark

然后，继续执行分析过程，将没有匹配的直接复制到右边或者上面一个位置，如下图的P和N：

mark

然后，由规则$S \rightarrow P VP$，由于S不在最右上角的位置，说明匹配失败，不能执行这条规则的匹配，如下图：

mark

接着，可以执行规则$VP \rightarrow VP N$，如下图：

mark

然后，将没有匹配的直接复制到右边或上面一个位置，结果如下图所示：

mark

最后，匹配规则$S \rightarrow P VP$，完成句法分析过程：

mark

最终，句法分析的结果如下：

mark

CYK算法要比Chart算法要容易理解一些，其优点是：简单易行，执行效率高；但是，必须对文法进行范式化处理，且无法区分歧义。

概率上下文无关文法

上面介绍的句法分析算法都是基于规则的句法分析方法，其具有一定的缺陷：

  • 很难穷尽所有的句法规则；
  • 很难保证规则间的一致性；
  • 通常只能处理有限的比较规范的句子；
  • 对真实语料的处理能力不够；
  • 分析效率通常不高；

概率上下文无关文法，PCFG即Probabilistic CFG，直观的意义就是基于概率的短语结构分析。乔姆斯基的短语结构文法表示为一个四元组：G=(X,V,S,R)。而PCFG中增加了一个概率信息，变为五元组PCFG=(X,V,S,R,P)，其中：

  • X：是一个有限词汇的集合(词典)。它的元素被称为词汇或终结符；
  • V：是一个有限标注的集合，叫做非终结符集合。它的元素称为变量或非终结符；
  • $S \in V$：称为文法的开始符号；
  • R：是一个有序偶对$(\alpha, \beta)$的集合，也就是产生的规则集；
  • P：代表每个产生规则的统计概率。

如果把形如”->”看作一个运算符，PCFG可以写成如下形式：

形式： $A->\alpha, P$

约束： $\sum_{\alpha} P(A->\alpha)=1$

比如，对于如下给定的规则集：

mark

对于给定句子 S: Astronomers saw stars with ears。采用基于规则的句法分析会分析出如下两种结果：

mark

mark

利用PCFG能够计算出$t_1$和$t_2$产生的概率。最后，选择概率最大的作为句法分析的结果。PCFG计算分析树的概率作出了三个基本假设：

  • 位置不变性：子树的概率与其管辖的词在整个句子中所处的位置无关，即对于任意的k,$p(A_{k(k+C)} \rightarrow w)$一样。

  • 上下文无关性： 子树的概率与子树管辖范围以外的词无关，即$p(A_{kl} \rightarrow w| 任何超出$k~l$范围的上下文)=p(A_{kl} \rightarrow w)$。

  • 祖先无关性：子树的概率与推导出该子树的祖先结点无关，即$p(A_{kl}\rightarrow w|任何除A以外的祖先结点)=p(A_{kl}\rightarrow w)$。

下图为$t_1$基于三种基本假设下的计算过程：

mark

依据三个基本假设，可以得到$t_1$的产生的概率：

$$\begin{align}
P(t_1)&=S*NP*VP*V*NP*NP*PP*P*NP\\&=1.0*0.1*0.7*1.0*0.4*0.18*1.0*1.0*0.18\\&= 0.000 9072\\
P(t_2)&=S*NP*VP*VP*VP*V*NP*PP*P*NP\\&=1.0*0.1*0.3*0.7*1.0*0.18*1.0*1.0*1.0*0.18\\&=0.000 6804
\end{align}
$$

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

根据上述的例子，可以很自然地想到关于PCFG算法的如下三个基本问题：

(1) 给定句子$W=w_1w_2…w_n$和PCFG G，如何快速计算$p(W|G)$?

(2) 给定句子$W=w_1w_2…w_n$和PCFG G，如何快速地选择最佳句法结构树？

(3) 给定句子$W=w_1w_2…w_n$和CFG G，如何调节G的参数，使得$p(w|G)$最大？

内向算法与外向算法

内向算法与外向算法是解决第一个问题——计算句子的句法树概率的方法。假设文法G(S)的规则只有两种形式：
$$
A \rightarrow w, w\in V_{T}\\
A \rightarrow BC,B,C \in V_{N}
$$
可以通过规范式化处理，使CFG规则满足上述形式。这种假设的文法形式称为乔姆斯基范式（Chomsky Normal Form）。

内向算法的基本思想是从给定字符串的底层向上逐次推导出句子的全部概率。利用动态规划法计算非终结符A推导出的某个字串片段$w_1w_{i+1}…w_j$的概率$\alpha_{ij}(A)$。语句$W=w_1w_2…w_n$的概率即为文法G(S)中S推导出的子串概率$\alpha_{1n}(S)$。

定义： 内向变量$\alpha_{ij}(A)$是由非终结符A推导出的语句W中子字串$w_iw_{i+1}…w_j$的概率：
$$
\alpha_{ij}(A) = p(A \rightarrow w_iw_{i+1}…w_j)
$$
计算$\alpha_{ij}(A)$的递推公式：
$$\begin{align}
&\alpha_{ii}(A) = p(A \rightarrow w_i)\\
&\alpha_{ij}(A) = \sum_{B,C\in V_N}\sum_{i \leq k \leq j}p(A \rightarrow BC)\alpha_{ik}(B)\alpha_{(k+1)j}(C)
\end{align}
$$

mark

  • 当$i==j$时，字符串$w_iw_{i+1}…w_j$只有一个字$w_{ii}$，可以简单记作$w_i$，由A推导出$w_i$的概率就是产生式$A \rightarrow w_i$的概率$p(A \rightarrow w_i)$;
  • 当$i \neq j$时，也就是说，字符串$w_iw_{i+1}…w_j$至少有两个词，根据约定，A要推导出该词串，必须首先运用产生式$A \rightarrow BC$，那么，可用B推导出前半部$w_i…w_k$，用C推导出后半部$w_{k+1}…w_j$。由这一推导过程产生$w_iw_{i+1}…w_j$的概率为：$p(A \rightarrow BC)\alpha_{ik}(B)\alpha_{(k+1)j}(C)$。考虑到B、C和k取值的任意性，应计算各个概率的总和。

内向算法的描述如下：

输入：文法G(S)，语句$W=w_1w_2…w_n$

输出：$p(S\rightarrow w_1w_2…w_n)$

(1) 初始化：$\alpha_{ij}(A) = p(A \rightarrow w_i) A\in V_N, 1 \leq i \leq j \leq n$

(2) 归纳计算：$j=1…n,i=1…n-j$，重复下列计算：
$$
\alpha_{ij}(A) = \sum_{B,C\in V_N}\sum_{i \leq k \leq i+j}p(A \rightarrow BC)\alpha_{ik}(B)\alpha_{(k+1)j}(C)
$$

(3) 终结：$p(S\rightarrow w_1w_2…w_n)=\alpha_{1n}(S)$

外向算法的基本思想是从给定字符串的顶层向下逐次推导出句子的概率。

定义：外向变量$\beta_{ij}(A)$是由文法初始符号S推导出语句$W=w_1w_2…w_n$的过程中，到达扩展符号串$w_1…w_{i-1}Aw_{j+1}…w_n$的概率$A=w_i…w_j$:
$$
\beta_{ij}(A) = p(S\rightarrow w_1…w_{i-1}Aw_{j+1}…w_n)
$$
同样，$\beta_{ij}(A)$可由动态规划算法求得，其递推公式为：
$$
\begin{align}
&\beta_{1n}=\delta(A,S) (初始化) \\
&\beta_{ij}(A)=\sum_{B,C}\sum_{k>j} \beta_{ik}(B)p(B \rightarrow AC)\alpha_{(j+1)k}(C)+\sum_{B,C}\sum_{k_i}\beta_{kj}(B)p(B\rightarrow CA)\alpha_{k(i-1)}(C)
\end{align}
$$

具体的解释如下：

(1) 当$i=1,j=n$时，即$w_iw_{i+1}…w_j$是整个语句W时，根据乔姆斯基语法范式的约定，不可能有规则$S \rightarrow A$，因此，由S推导出W的过程中，如果$A \neq S$的话，A推导出W的概率为0，即$\beta_{1n}(A)=0$。如果$A=S,\beta_{1n}(A)$为由初始符S推导出W的概率，因此，$\beta_{1n}(A)=1$

(2) 当$i\neq 1$或者$j \neq n$时，如果在S推导出W的过程中出现字符串$w_1…w_{i-1}Aw_{j+1}…w_n$，则推导过程必定使用规则$B \rightarrow AC$或$B \rightarrow CA$。假定运用了规则$B \rightarrow AC$推导出$w_i…w_j w_{j+1}…w_k$，则该推导可以分解为以下三步：

  • 由S推导出$w_1…w_{i-1}Bw_{k+1}…w_n$，其概率为$\beta_{ik}(B)$;
  • 运用产生式$B \rightarrow AC$扩展非终结符B，其概率为$p(B \rightarrow AC)$;
  • 由非终结符C推导出$w_{j+1}…w_k$，其概率为$\alpha_{(j+1)k}(C)$。

考虑到B、C和k的任意性，在计算$\beta_{ik}(B)$时，必须考虑所有可能的B、C和k，因此，计算概率时必须要考虑所有情况下的概率之和。同样方法，可以计算出运用产生式$B \rightarrow CA$推导出$w_i…w_jw_{j+1}…w_k$的概率。

其示意图如下：
mark

外向算法描述如下：

输入：PCFG G=(S,N,T,P)，语句$W=w_1w_2…w_n$
输出：$\beta_{ij},A,A\in N, 1\leq i \leq j \leq n$

(1) 初始化： $\beta_{1n}(A) = \delta(A,S),A \in N$;
(2) 归纳： j从n-1到0，i从1到n-j，重复计算：
$$
\beta_{i(i+j)}(A) = \sum_{B,C}\sum_{i+j\leq k \leq n}p(B \rightarrow AC)\alpha_{(i+j+1)k}(C)\beta_{ik}(B)+\sum_{B,C}\sum_{1 \leq k \leq i}p(B \rightarrow CA)\alpha_{k(i-1)}(C)\beta_{k(i+j)}(B)
$$
(3) 终结： $p(S \rightarrow w_1w_2…w_n)=\beta_{1n}(S)$

Viterbi算法

第二个问题是如何选择最佳的句法树，其解决方法是使用Viterbi算法，在短语结构文法中，Viterbi的定义如下：

  • Viterbi变量的$\gamma_{ij}(A)$是由非终结符A推导出语句W中子字串$w_iw_{i+1}…w_j$的最大概率;
  • 变量$\psi_{i,j}$用于记忆字串$W=w_1w_2…w_n$的Viterbi语法分析结果。

Viterbi算法描述如下：

输入：文法G(S)，语句$W=w_1w_2…w_n$
输出：$\gamma_{1n}(S)$

(1) 初始化： $\gamma_{ii}A=p(A\rightarrow w_i),A\in V_N, 1\leq i \leq j \leq n$

(2) 归纳计算： j=1…n, i=1…n-j，重复下列计算：
$$
\begin{align}
&\gamma_{i(i+j)}(A) = max_{B,C\in V_N;i\leq k \leq i+j}p(A\rightarrow BC)\gamma_{ik}(B)\gamma_{(k+1)(i+j)}(C)\\
&\psi_{i(i+j)}(A) = max_{B,C\in V_N;i\leq k \leq i+j}p(A\rightarrow BC)\gamma_{ik}(B)\gamma_{(k+1)(i+j)}(C)
\end{align}
$$
(3) 终结：$p(S\rightarrow w_1w_2…w_n)=\gamma_{1n}(S)$

参数估计

如果有大量已经标注语法结构的训练语料，则可以通过语料直接计算每个语法规则的使用次数。已知训练语料中的语法结构，记录每个语法规则的使用次数，使用最大似然估计来计算PCFG的参数。

一般来说，树库的标注需要投入较大的人力，时间和资金投入都比较大。而且，树库也不可能覆盖所有的词汇信息，在NLP中，使用有限的资源预估目标的概率分布，这种情况是常态。所谓参数估计，就是对未知现象出现概率的一种计算方法。PCFG中常用的方式是EM算法。

EM算法的基本思想是：初始时随机地给参数赋值，得到语法$G_0$，依据$G_0$和训练语料，得到语法规则使用次数的期望值，以期望次数用于最大似然估计，得到语法参数新的估计值，由此得到新的语法$G_1$，由$G_1$再次得到语法规则的使用次数的期望值，然后又可以重新估计语法参数。循环这个过程，语法参数将收敛与最大似然估计值。

PCFG中使用的方法称为内向、外向算法：给定CFG G和训练数据$W=w_1w_2…w_n$，语法规则$A\rightarrow BC$使用次数的期望值为：
$$
\begin{align}
Count(A \rightarrow BC) &=\sum_{1\leq i\leq k \leq j \leq n}P(A_{ij},B_{ik},C_{(k+1)j}|w_1…w_n,G)\\&=\frac {1}{p(w_1…w_n|G)}\sum_{1\leq i\leq k \leq j \leq n} p(A_{ij},B_{ik},C_{(k+1)j},w_1,…w_n|G)\\&=\frac {1}{p(w_1…w_n|G)}\sum_{1\leq i\leq k \leq j \leq n} \beta_{ij}(A)p(A\rightarrow BC)\alpha_{ik}(B)\alpha_{(k+1)j}(C)
\end{align}
$$

上面的公式的解释：给定了语句$W=w_1…w_n$PCFG G中产生$A\rightarrow BC$在产生的W的过程中被使用次数的期望值为：在所有可能的情况下，即在条件$1\leq i\leq k \leq j \leq n$下，W的语法分析结构中$w_i…w_k$由B导出，$w_{k+1},…w_{j}$由C导出，$w_i…w_j$由A导出的概率总和。

类似的，语法规则$A\rightarrow a$的使用次数的期望值为：
$$
\begin{align}
Count(A\rightarrow a) &=\sum_{1 \leq i \leq n} p(A_{ii}|w_1…w_n,G)\\&=\frac {1}{p(w_1…w_n|G)}\sum_{1 \leq i \leq n}p(A_{ii},w_1…w_n|G)\\&= \frac {1}{p(w_1…w_n|G)}\sum_{1 \leq i \leq n}\beta_{ii}(A)p(A\rightarrow a)\delta(a,w_i)
\end{align}
$$
G的参数可由如下公式重新估计：
$$
\hat p(A\rightarrow \mu)= \frac {C(A\rightarrow \mu)}{\sum_{\mu}C(A \rightarrow \mu)}
$$
其中，$\mu$要么为终结符号，要么为两个非终结符号串，即$A\rightarrow \mu$为乔姆斯基语法范式要求的两种形式。

内向、外向算法的步骤如下：

(1) 初始化：随机地给出$P(A\rightarrow \mu)$的赋值，使得$\sum_{\mu}P(A\rightarrow \mu)=1$，由此得到语法$G_0$,令$i=0$。

(2) EM算法步骤如下：

  • E步：根据$G_i$的公式，计算期望值$Count(A\rightarrow BC)$和$Count(A \rightarrow a)$；
  • M步:用E-步所得的期望值，根据公式重新估计$p(A\rightarrow \mu)$，得到$G_(i+1)$

(3) 循环：i=i+1，重复EM步骤，直至$p(A\rightarrow \mu)$值收敛。

依存句法分析

这一部分暂时先挖个坑

参考

  • 宗成庆《自然语言理解》讲义-第9章
  • 刘群《计算语言学》讲义-第7章
坚持原创技术分享，您的支持将鼓励我继续创作!