概率上下文无关语法(PCFG)

October 27, 2017

在 NLP 任务中,我们可以根据一组 grammar 规则来生成一个句子。

下面这个 grammar 例子表示,一个句子能够由名词短语 I 和动词短语 want a morning filght 组成;名词短语能够由代词 I 组成,或由名词 Los Angeles 组成等。

194 example grammar

Context-Free Grammar(CFG)

什么是“上下文无关”?

考虑下图这个 parse tree(语法树):

194 parse tree

我们来模拟一下这句话生成的过程:

  1. S \rightarrow NP VP
  2. S \rightarrow NP VP \rightarrow DT NN VP
  3. S \rightarrow NP VP \rightarrow DT NN VP \rightarrow the NN VP
  4. S \rightarrow NP VP \rightarrow DT NN VP \rightarrow the NN VP \rightarrow the man VP
  5. S \rightarrow NP VP \rightarrow DT NN VP \rightarrow the NN VP \rightarrow the man VP \rightarrow the man Vi
  6. S \rightarrow NP VP \rightarrow DT NN VP \rightarrow the NN VP \rightarrow the man VP \rightarrow the man sleeps

在第一步到第二步时,DT 和 NN 的生成只与 NP 有关(根据 NP \rightarrow DT NN 这条规则),而与 VP 无关,也就是说,所有规则的左侧只有一个符号,这种形式称为上下文无关

CFG 定义

CFG 由一个四元组 NNΣ\SigmaRRSS 组成。其中,

  • NN 是 non-terminal 符号的集合,理解为语法树中的非叶节点(S、NP……)
  • Σ\Sigma 是 terminal 符号的集合,也就是各个单词(叶节点 the、man、sleeps)
  • RR 代表 grammar 中的规则,如 S\rightarrow NP VP
  • SS 代表开始的标记,也就是语法树的根节点

上面例子的语法树是根据下面这个 grammar 生成的。由一句话和一个 grammar 生成 parse tree 的过程叫做 parsing。在这里由于句子是由 grammar 生成的,这种建模方法也被称为 generative grammar。

194 grammar

现在我们使用这个 grammar 来生成这样一句话:the man saw the dog with the telescope,会产生什么样的 parse tree 呢?

194 ambiguity

看,两个 parse tree 都是有效的,但却是两种语义。为了解决这种歧义的现象,我们在 CFG 中引入了概率的概念。

Probabilistic Context-Free Grammar(PCFG)

给定一个上下文无关语法 GG,称 TG\mathcal{T}_{G} 为 grammar GG 下的所有 parse tree 的集合,简写为 T\mathcal{T}。那么就有

tTGp(t)=1\sum_{t\in\mathcal{T}_{G}}p(t)=1

因此如果知道了概率分布 p(t)p(t),那么我们就可以通过排序找到一句话最有可能的 parse tree。

PCFG 定义

  1. 一个上下文无关语法 G=(N,Σ,S,R)G=(N,\Sigma,S,R)
  2. 对应每个规则 αβR\alpha\rightarrow\beta\in R 的概率为 q(αβ)q(\alpha\rightarrow\beta),实际上这是在给定α\alpha 为规则左侧符号时,αβ\alpha\rightarrow\beta 这条规则的条件概率。因此在任意 XNX\in N 时,有
αβR:α=Xq(αβ)=1\sum_{\alpha\rightarrow\beta\in R:\alpha=X}q(\alpha\rightarrow\beta)=1

因此,如果一个 parse tree tTGt\in\mathcal{T}_{G} 包含α1β1,α2β2,,αnβn\alpha_{1}\rightarrow\beta_{1},\alpha_{2}\rightarrow\beta_{2},…,\alpha_{n}\rightarrow\beta_{n}这些规则,那么 tt 在 PCFG 下的概率为

p(t)=i=1nq(αiβi)p(t)=\prod_{i=1}^{n}q(\alpha_{i}\rightarrow\beta{i})

194 pcfg

上图为一个 PCFG,可以验证其满足

αβR:α=VPq(αβ)=q(VPVi)+q(VPVtNP)+q(VPVPPP)=0.3+0.5+0.2=1.0\begin{aligned} \sum_{\alpha \rightarrow \beta \in R: \alpha=\mathrm{VP}} q(\alpha \rightarrow \beta) &=q(\mathrm{VP} \rightarrow \mathrm{Vi})+q(\mathrm{VP} \rightarrow \mathrm{Vt} \mathrm{NP})+q(\mathrm{VP} \rightarrow \mathrm{VP} \mathrm{PP}) \\ &=0.3+0.5+0.2 \\ &=1.0 \end{aligned}

如果 parse tree 是这样:

194 parse tree pcfg

那么这个 parse tree 的概率就是

p(t)=q(SNP    VP)×q(NPDT    NN)×q(DTthe)×q(NNdog)×q(VPVi)×q(Visleeps)p(t)=q(\mathrm{S}\rightarrow \mathrm{NP\;\;VP})\times q(\mathrm{NP}\rightarrow \mathrm{DT\;\;NN})\times q(\mathrm{DT}\rightarrow \mathrm{the}) \times q(\mathrm{NN}\rightarrow \mathrm{dog})\times q(\mathrm{VP}\rightarrow \mathrm{Vi})\times q(\mathrm{Vi}\rightarrow \mathrm{sleeps})

References


Profile picture

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]