chapter12-句法分析

  • ambiguous and disambiguation

  • PCFGs

  • 如何从语料库中得到PCFGs,极大似然估计,也就是计算频率

  • Chomsky 范式

  • SKY,一种bottom-up的dynamic programming算法~

前言: 为什么要做句法分析呢?主要是避免歧义。在 grammar checking,semantic analysis,question answering, information extraction 中都有很重要的作用。

如何从Treebanks中找到某一个sentence的tree呢?这个章节中会介绍一种动态规划的算法 Cocke-Kasami-Younger(CKY).

歧义 Ambiguity

在词性标注中我们遇到了 part-of-speech ambiguity and part-of-speech disambiguation, 在句法分析中也会遇到类似的问题 structure ambiguity.

举个栗子:

先有这样的一个简单的 Treebank $L_1$.

对于同样的一句话,可以从上述Treebank中生成两种 parse tree.

I shot an elephant in my pajamas.

显然右边的parse tree才是我们想要的,但左边的也是满足 $L_1$ 的语法规则的。

结构歧义通常分为两种:附着歧义(attachment ambiguity),并列歧义(coordination ambiguity。

事实上,在自然语言处理中,会有很多语法正确,但是语义上不合理的parse。因此我们需要句法消歧 syntactic disambiguation.一个有效的句法消歧算法需要很多语义semantic和语境contextual知识, 但幸运的是,统计的方法就可以很好的解决~

Probabilistic Context-Free Grammars (PCFGs)

Speech and language Processing 这本书中关于PCFG内容实在是有点多,而且纯英文的难度看起来真的有点大。。。于是找到Columbia University,Michael Collins 的NLP课程,相比之下内容少了很多,而且老师讲的也很清楚~所以这部分以Michael Collins的NLP讲义为主。

context-free grammars

上下文无关语法CFG可定义为4元祖 $G=(N,\Sigma, R, S)$

(left-most) Derivations

给定一个上下文无关语法,一个left-most derivation是一个序列 $s_1…s_n$,其中:

  • $s_1 = S$, the start symbol

  • $s_n\in \Sigma^*$, $\Sigma^*$ 表示任何从 $\Sigma$ 中得到的words组成

  • $s_i$, 表示找到 $s_{i-1}$ 中left-most的非终极符号X,并用 $\beta$ 代替它,并且 $X\rightarrow \beta \in R$

Probabilistic Context-Free Grammars (PCFGs)

用 $T_G$ 表示对应与上下文无关语法G所有的left-most 推导的parse tree.

如果 $s\in \Sigma^* $, 那么 $T_G(s)$ 表示:

$$t:t\in T_G, yield(t)=s$$

$T_G(s)$ 表示在语法G下,s对应的所有parse tree的集合。

  • 如果一个sentence是有歧义ambiguous的,那么 $|T_G(s)|\ge 1$

  • 如果一个sentence是符合语法G的grammatical, 那么 $|T_G(s)|\ge 0$

给一个可能的推导,也就是parse tree一个概率,p(t),那么对于任意 $t\in T_G$:

$$p(t)\ge 0$$

并且:

$$\sum_{t\in T_G}p(t)=1$$

咋一看,这似乎很复杂。每一个parse tree就很复杂,然后这样的parse tree可能是infinite.那么如何定义概率分布p(t)呢?

知道了p(t),我们也就知道了一个给定的sentence对应的最有可能的parse tree.也就是:

$$arg\ max_{t\in T_G(s)p(t)}$$

有了这个我们就能很好的消除语言中存在的ambiguous了~~~

那么问题来了:

  • How do we define the function p(t)?

  • How do we learn the parameters of our model of p(t) from training examples?

  • For a given sentence s, how do we find the most likely tree, namely

$$arg\ max_{t\in T_G(s)p(t)}?$$

definition of PCFGs

一个PCFG包括:

  • 上下文无关语法 $G=(N,\Sigma,S,R)$

  • 参数

$$q(\alpha \rightarrow \beta)$$

那么对于 $t\in T_G$包含rules $\alpha_2\rightarrow \beta_1,\alpha_2\rightarrow \beta_2,…,\alpha_n\rightarrow \beta_n$,则有:

$$p(t)=\prod_{i=1}^nq(\alpha_i\rightarrow \beta_i)$$

那么对于所有的非终极符号 $X\in N$:

$$\sum_{\alpha\rightarrow \beta \in R:\alpha=X}q(\alpha\rightarrow \beta)=1$$

也就是从一个非终极符号展开的概率之和为1.

对于一个parse tree的概率,举个例子:

根据直觉,可以将parse tree的生成看做随机过程 stochastical process,其过程如下:

Deriving a PCFG from a Corpus

Having defined PCFGs, the next question is the following: how do we derive a PCFG from a corpus?

We will assume a set of training data, which is simply a set of parse trees $t_1,t_2,…,t_m$. $yield(t_i)$ is the i’th sentence in the corpus.

Each parse tree t i is a sequence of context-free rules: we assume that every parse tree in our corpus has the same symbol, S, at its root. We can then define a PCFG (N, Σ, S, R, q) as follows:

有点疑惑:

  • 一个语料库对应一个PCFG

  • 一个语料库中所有的parse tree的start symbol是相同的S

  • $t_1,t_2,…,t_m$ 具体有多少我们并不知道,也不需要知道吧。。但是有多少sentences是知道的。

比如figure5中显示的那样~

Chomsky Normal Form

collins 教授举的例子:

VP -> VT NP PP 0.2

转换成 Chomsky Normal Form:

VP -> VT-NP 0.2

VP-NT -> VT NP 1

总结下这个过程就是:

Parsing using the CKY Algorithm

在前面最小编辑距离,Viterbi,Froward算法中,都是先填写表格,表格中包含有所有的子问题。而在句法分析也是类似的,子问题是展示所有成分的parse tree,也可以展示在表格中,但它是三维的,因为不仅仅包含句子长度这一维度,还有对应的短语结构.

对于一个sentence $s=x_1\cdots x_n$,其中 $x_i$ 表示句子中第i个词。也就是找出概率最大的parse tree

$$arg\ max_{t\in T_G}p(t)$$

CKY算法是一个动态规划算法~ 具体思路:

  1. 给sentence标上index

  1. fill the table $(n+1)\times (n+1)$, 每个 cell 对应一个三维的量 $\pi[i,j,X]$,$X\in N, 1\le i\le j\le n$, 其中non-terminal总个数有V个,那么 table 的维度是 $(n+1)\times (n+1)\times V$

sentence其中的一部分 $x_i\cdots x_j$,并且对应的root为非终极符号X.

$$\pi(i,j,X) = max_{t\in T(i,j,X)}p(t)$$

那么我们要求的sentence对应的parse tree:

$$\pi(1,n,S) = arg\ max_{t\in T_G(s)}$$

  1. 用递归的方法填写table

这里是一种 bottom-up,从下到上的方法,只需要矩阵的上三角部分~

  • Initialization 初始值, 也就是主对角线的值

$$\pi(i,i,X) =\begin{cases}

q(X\rightarrow x_i), & \text{if $X \rightarrow x_i \in$ R} \

0, & \text{otherwise}

\end{cases} $$

  • 递归 recursive

$$\pi(i,j,X)=max_{X\rightarrow Y Z \in R,s\in {i…(j-1)}}(q(X\rightarrow Y Z)\times \pi(i,s,Y)\times \pi(s+1,j,Z))\tag{1}$$

伪代码:

填表的过程:

The algorithm fills in the $\pi$ values bottom-up: first the $\pi(i, i, X)$ values, using the base case in the recursion; then the values for $\pi(i, j, X)$ such that j = i + 1; then the values for $\pi(i, j, X)$ such that j = i + 2; and so on.

Justification for the Algorithm

考虑 $\pi(3,8,VP)$

在语法中 $VP\rightarrow Y Z$ 只有两种情况 $VP \rightarrow Vt\ NP\ and\ VP\rightarrow VP\ PP$,那么 $\pi(3,3)$ 这个cell有两个维度,同样的 $\pi(3,4),…,\pi(8,8)$ 都有两个维度.

总的计算复杂度是 $O(n^3|N|^3)$,怎么来的呢?

  • table中选择cell[i,j],复杂度 $n^2$

  • 对于每个cell[i,j]要考虑 N 个non-terminal,所以是 $n^2N$

  • 然后 $X\rightarrow Y Z$ Y Z都有 N 种情况,所以 $n^2N^3$

  • 然后 $s\in {i…(j-1)}$ 所以是 $O(n^3|N|^3)$

整个回顾下,就是我们先从下到上 bottom-up 填写三维table[i,j,V] ,然后直接计算 $\pi(1,n,S)$, 同样的类似于HMM中需要backpoints.

weaknesses of PCFGs

  • Lack of sensitivity to lexical information

  • Lack of sensitivity to structural frequencies

  1. Lack of sensitivity to lexical information

在PCFGs中 $NNP\rightarrow IBM$ 是一个独立的过程,并没有考虑到其他的words,这在NLP中显然是不合理的。

附着歧义(attachment ambiguity):

可以看到对于同一句话的两种parse tree,它们的区别只有图中黑色加粗的rule,那么比较两个parse tree那个更好仅仅取决于 $q(NP\rightarrow NP PP) q(VP\rightarrow VP PP)$ 的大小。

边上的举例 dumped sacks into bin 没太懂,准确率是怎么来的。。。

  1. Lack of sensitivity to structural frequencies

close attachment:

通过两个例子,说明PCFGs的劣势,failed to capture the structural preferences.

两个parse tree的rules完全相同,那么对应的概率p(t)也一样。PCFGs failed to display a preference for one parse tree or the other and in particular it completely ignores the lexical information.

参考:

作者

Xie Pan

发布于

2018-04-20

更新于

2021-06-29

许可协议

评论