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表示的是非终止符
  • 其中$\sum $表示词汇集合,也就是终止符
  • 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落到第二部分,不过这里倒是默认分解为两部分。
算法如下图所示:




评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×