Lexicalized Probabilistic Context-Free Grammars

Weaknesses of PCFGs as Parsing Models

这一章是对上一章的优化，PCFGs主要有两个关键的弱点，第一个是缺乏对词汇信息的敏感度，第二个是缺乏对结构的偏好，第一个问题是我们使用lexicalized PCFGs的根本原因。 比如下面两棵 parse tree：

使用PCFGs来计算两棵树的概率： \[ p(a)=q(S\rightarrow NP\,\,VP)q(NP \rightarrow NNS)q(VP\rightarrow VP\,\,PP)q(VP\rightarrow VBD\,\,NP)\\q(pp\rightarrow IN \,\,NP)q(NP \rightarrow NNS)q(NP\rightarrow DT\,\,NN)...\\ p(b)=q(S\rightarrow NP\,\,VP)q(NP\rightarrow NNS)q(VP \rightarrow VBD\,\,NP)q(NP\rightarrow NP\,\,PP)\\q(NP\rightarrow NNS)q(PP\rightarrow IN\,\,NP)q(NP\rightarrow DT\,\,NN) \] 可以发现选择那棵树完全取决于\(q(VP \rightarrow VP\,\,PP)\)和\(q(NP \rightarrow NP\,\,PP)\)的大小，也就是说统计语料库中\(VP\rightarrow VP\,\,PP\)和\(NP \rightarrow NP\,\,PP\)的个数，那个更多，就选择那棵树，和词汇没有一点关系；但是如果PP是和介词into一起，统计的结果是VP PP出现的次数是NP PP的9倍；而如果介词是of，统计的结果是NP PP出现的次数是VP PP的100倍，这就说明了PP中的词汇是有一定作用的。 第二个问题是缺乏结构偏好，比如下面这两棵parse tree：

使用PCFGs计算的结果是一样的，无法区分这两棵树，但是我们可以通过在parse trees中统计上述两种树结构出现的次数来选取那一棵树，我们使用lexicalized PCFGs也可以做到这一点。

Lexicalized of a Treebank

见下图，a表示没有经过词汇标记的树，b表示使用Lexicalized标记的树：

Lexicalized PCFGs

用Chmosky normal 形式定义G=(N,∑,R,S,q,γ)，参数表示如下：

• N表示的是非终止符
• 其中$$表示词汇集合，也就是终止符
• R 是一个规则集合，这些规则属于下面三种中的一种： \[ X(h) \rightarrow_1 Y_1(h)Y_2(m) \,\,where\,\,X,Y_1,Y_2 \in N,h,m \in \sum\\ X(h) \rightarrow_2 Y_1(m)Y_2(h)\,\, where \,\,X,Y_1,Y_2 \in N,h,m \in \sum\\ X(h) \rightarrow h \,\,where\,\, X \in N,h \in \sum \] 这里的h就是head，m就是modify，也就是要改变的单词
• 对每一个规则\(r\)，用\(q(r)\)表示概率,有： \[ \sum_{r \in R: LHS(r)=X(h)} q(r)=1 \] 其中\(LHS(r)\)表示任何规则的左边
• 定义\(\gamma(X,h),X \in N,h \in \sum\)表示X的词汇是h的概率，有\(\sum_{X \in N,h \in \sum}\gamma(X,h)=1\) 这样parse tree的概率就可以如下表示，其中\(r_i\)表示R中的规则： \[ \gamma(LHS(r_1)) \prod_{i=1}^{N}q(r_i) \] 如下图，就可以计算下面解析树的概率了：

Parameter Estimation in Lexicalized PCFGs

举个例子，对于规则\(S(examined) \rightarrow_2 NP(laywer)\,\, VP(examined)\)，写成概率形式如下： \[ q(S(examined) \rightarrow_2 NP(lawyer)\,\,VP(examined))\\ =P(R=S\rightarrow_2 NP\,\,VP,M=lawyer|X=S,H=examined)\\ =P(R=S \rightarrow_2 NP\,\,VP|X=S,H=examined)\\P(M=lawyer|R=S\rightarrow_2 NP\,\,VP,X=S,H=examined) \] 最后一个式子是条件概率展开，分为两部分，这里使用平滑技术求解，可以想象成前面的3-gram模型，避免0的出现，第一部分用下面两个式子结合得到： \[ q_{ML}(S\rightarrow_2 NP\,\,VP|S,examined)=\frac{count(R=S\rightarrow_2 NP\,\,VP,X=S,H=examined)}{count(X=S,H=examined)}\\ q_{ML}(S\rightarrow_2 NP\,\,VP|S)=\frac{count(R=S\rightarrow_2 NP\,\,VP,X=S)}{count(X=S)} \] 使用\(\lambda_1,0<=\lambda_1<=1\)表示如下： \[ P(R=S\rightarrow_2 NP\,\,VP|X=S,H=examined)\\ =\lambda_1q_{ML}(S\rightarrow_2 NP\,\,VP|S,examined)+(1-\lambda_1)q_{ML}(S\rightarrow_2 NP\,\,VP|S) \] 第二部分式子可以作如下等价： \[ P(M=lawyer|R=S\rightarrow_2 NP\,\,VP,X=S,H=examined)\\ =P(M=lawyer|R=S\rightarrow_2 NP\,\,VP,H=examined) \] 继续使用平滑估计： \[ q_{ML}(lawyer|S\rightarrow_2 NP\,\,VP,examined)\\=\frac{count(M=lawyer,R=\rightarrow_2 NP\,\,VP,H=examined)}{count(R=S\rightarrow_2 NP\,\,VP,H=examinde)}\\ q_{ML}(lawyer|S\rightarrow_2 NP\,\,VP)\\=\frac{count(M=lawyer,R=\rightarrow_2 NP\,\,VP)}{count(R\rightarrow_2 NP\,\,VP)} \] 这样第二个式子使用\(\lambda_2,0<=\lambda_2<=1\)就可以表示如下： \[ \lambda_2 q_{ML}(lawyer|S\rightarrow_2 NP\,\,VP,examined)+(1-\lambda_2) q_{ML}(lawyer|S\rightarrow_2 NP\,\,VP) \] 如上，就是对于规则\(S(examined) \rightarrow_2 NP(laywer)\,\, VP(examined)\)的求解，那么一棵树的概率就可以通过这样的方式求解出来。最后当然是要找出一个概率最高的树了，下面讲到。

Parsing with Lexicalized PCFGs

和PCFGs的算法类似，定义\(\pi(i,j,h,X)\)表示对任意一棵以X为根节点，词汇索引为h，从\(i\)到\(j\)的单词串的树的最大概率，即\(i\)和\(j\)表示从第\(i\)个单词到第\(j\)个单词，\(h \in \{i...j\}\)表示在i到j这些单词中选择一个单词作为head，X表示树根，且其词汇信息为head。

给定初始条件：\(\pi(i,i,i,X)=q(X(x_i) \rightarrow x_i)\)

通项公式如下图所示：

说明一下：m是下一个head对应的索引，有两种情况，一种是分解后，根的head落到第一部分，一种是分解后根的head落到第二部分，不过这里倒是默认分解为两部分。 算法如下图所示：