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^* $, 那么 \(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.

参考: