句法分析之转换生成语法——基于概率的短语结构树分析算法PCFG

/ NLP / 没有评论 / 1613浏览

如何评价句法树

句法分析,理论上可由两个阶段完成

生成句子的所有句法树
句法排歧,找出正确的句法树(需要评价句法树的优劣)

人们做了大量的研究,有的选择其他的句法思想,有的则通过开发树库资源来调整算法。

宾州树库就是基于人工标注短语结构树库

树库资源提供的优势

可以从现有的大规模语料中学习新的规则
可以很容易的获得每条规则概率信息

基本思路

引入概率,建立基于统计的句法分析

统计句法分析 90年代后期引起了较多的关注,并取得了较好的研究成果

对给定的句子S,该句子的统计句法分析结果为

$$\tilde{T} = \arg \max_{T} P(T|S)$$

根据贝叶斯公式,有

$$\tilde{T} = \arg \max_{T} P(T,S)$$

如何计算句法树的概率

概率上下文无关文法 ( PCFG )
改进的 PCFG

CKY算法

属于基于CFG的句法分析算法(与GLR、 Earley类似)
由Cocke、 Kasami及Younger上世纪60年代提出,故叫Cocke-Kasami-Younger算法(CKY)
属于自底而上的分析算法
可以处理一般的文法,但更适于处理乔姆斯基范式

乔姆斯基范式

文法中只能有下面两种形式的重写规则

$A \rightarrow BC$
$A \rightarrow w$

可以证明,对任何一个CFG,都存在与之等价的乔姆斯基范式

$S \rightarrow aAB|BA$
$A \rightarrow BBB|a$
$B \rightarrow AS|b$

假定文法符合乔姆斯基范式不会损失CKY算法的一般性

CKY算法的主要数据结构是一个二维表T[n,n],其中每个表元素定义如下

$$t_{i,j} = \{ A| A \Rightarrow w_{i}w_{i+1},...,w_{j}\}$$

即可以推导出词串wiwi+1…wj的非终结符号所组成的集合

算法过程

CKY算法自底而上填写表格,首先

$$t_{i,j} = \{ A| A \rightarrow w_{i} \in P \}$$

若有$A \rightarrow BC \in P$, $B \in t_{i,k}$及$C \in t_{k+1,j}$,则有$A \in t_{i,j}$

概率上下文无关文法 PCFG

在短语结构文法中,目前最成熟、精度最高的算法是PCFG算法,即基于概率上下文无关文法分析

PCFG是CFG的一种扩展

PCFG 形式化定义

一个PCFG G 是一个四元组 $G = (N,\sum,S, P)$

N 有限个非终结符号组成的集合
$\sum$ 有限个终结符号组成的集合
S 文法的开始符号
P 是一组带有概率信息的重写规则组成的集合,每条规则形式如下:

$$A \rightarrow \alpha \left[ P(A \rightarrow \alpha) \right] \qquad \alpha \in N \bigcup V_{T})^{*}$$

*表示闭包

$P(A \rightarrow \alpha)$ 是重写规则的概率, 且 $\sum_{j} P(A \rightarrow \alpha_{j}) = 1$

PCFG的三个基本问题

①、给定PCFG G 及句子S,如何计算句子 S 的概率 P(S|G)? 语言模型——概率计算问题
②、给定PCFG G 及句子S,最为可能的分析树是什么,即求最大概率的问题。最优句法分析问题
③、给定PCFG G 及句子S,如何得到G的参数?使得P(S|G)最大。模型训练——模型参数求解问题

PCFG计算分析树的概率

$$P(t,S) = \prod_{i=1}^{n}P(r_{i})$$

PCFG 用于句法分析

基于PCFG可以计算分析树的概率值
若一个句子有多棵分析树,可以依据概率值对所有的分析树进行排序
PCFG可以用来进行句法排歧。面对多个分析结果,选择概率最大者为最终分析结果

PCFG 用作语言模型

基于概率上下文无关文法,一个句子$w_{1m}$的概率为

$$P(S) = \sum_{t} P(S,t)$$

PCFG提供了一种统计语言模型,同 n-gram 模型相比,基于PCFG的语言模型考虑了句子的结构信息,而n-gram模型则认为句子是线性结构

可以通过计算每棵分析树的概率,然后以求和或求最大值的方式解决上述第1、2个问题,缺点是效率不高。

为了有效解答PCFG的三个问题,使用向内算法(inside variable) 和向外算法(outsidevariable)

向内算法解决概率计算问题

向内算法的基本思想是从给定的字符串的底层向上逐次推导出句子的全部概率

向内变量

$$\alpha_{A}(p,q) = P(A \Rightarrow w_{p}w_{p+1},...,w_{q}) = P(w_{p}w_{p+1},...,w_{q}|A)$$

非终结符号A推导出句子中子串$w_{p}w_{p+1},...,w_{q}$的概率
或者说以A为根、叶子为$w_{p}w_{p+1},...,w_{q}$的所有子树的概率

如何计算向内向量

当p = q 时, $\alpha_{A}(p,p) = P (A \rightarrow w_{p})$
当p < q 时,因为限制文法为Chomsky范式,因此第一条使用的重写规则必为$A \rightarrow BC$

子串$w_{pq}$一定在某个位置d被分成两个部分,使得B支配子串$w_{pd}$,而C支配子串$w_{(d+1)q}$

$$\begin{equation}\begin{split} &P(A \Rightarrow BC \Rightarrow w_{p}w_{p+1},...,w_{d}w_{d+1},...,w_{q}) \\ &= P(A \Rightarrow BC)P(B \Rightarrow w_{p}w_{p+1},...,w_{d}) · P(C \Rightarrow w_{d+1}w_{d+2},...,w_{q}) \\ &= P(A \rightarrow BC)\alpha_{B}(p,d)\alpha_{C}(d+1,q) \end{split}\end{equation}$$

而计算 $\alpha_{A}(p,q)$ 应该考虑所有可能的以A为左部的重写规则,而选定了重写规则后,也应该考虑将$w_{p}w_{p+1},...,w_{q}$分割成两个子串的不同情况,即要考虑为 d 做所有可能的选择。故有:

$$\alpha_{A}(p,q) = \sum_{B,C \in N} \sum_{p \le d \le q} P(A \Rightarrow BC \Rightarrow w_{p}w_{p+1},...,w_{d}w_{d+1},...,w_{q})$$

$$\alpha_{A}(p,q) = \sum_{B,C \in N} \sum_{p \le d \le q} P(A \rightarrow BC)\alpha_{B}(p,d)\alpha_{C}(d+1,q)$$

向内向量的递推公式

$$\alpha_{A}(p,p) = P (A \rightarrow w_{p})$$

$$\alpha_{A}(p,q) = \sum_{B,C \in N} \sum_{p \le d \le q} P(A \rightarrow BC)\alpha_{B}(p,d)\alpha_{C}(d+1,q)$$

向内算法描述

输入: 文法 G(S), 语句 $W = w_{1},w_{2},...,w_{n}$.
输出: $P(S \Rightarrow w_{1},w_{2},...,w_{n})$

初始化

$$\alpha_{A}(k,k) = P(A \rightarrow w_{k})$$

归纳计算$\alpha_{A}(p,q)$ ,其中p < q

$$\alpha_{A}(p,q) = \sum_{B,C \in N}\sum_{d=p}^{q-1}P(A \rightarrow BC)\alpha_{B}(p,d)\alpha_{C}(d+1,q)$$

归纳终止

$$P(w_{1}w_{2},...,w_{n}) = \alpha_{S}(1,n)$$

向外算法解决概率计算问题

向外算法的基本思想是从给定字符串的顶层向下逐次推导出句子的概率。

向外变量

$$\beta_{A}(p,q) = P(S \Rightarrow w_{1}w_{2},...,w_{p-1}Aw_{q+1},...,w_{n}) = P(w_{1}w_{2},...,w_{p-1}Aw_{q+1},...,w_{n}|S)$$

即文法开始符号S推导出句型$w_{1}w_{2},...,w_{p-1}Aw_{q+1},...,w_{n}$的概率

如何计算向外变量

向外向量$\beta_{A}(p,q)$指的是S推导出的句型$w_{1}w_{2},...,w_{p-1}Aw_{q+1},...,w_{n}$的概率。因为限制文法是乔姆斯基范式,因此必然存在重写规则$X \rightarrow AY$或重写规则$X \rightarrow YA$,使得

$$S \Rightarrow w_{1}w_{2},...,w_{p-1}Xw_{e+1},...,w_{n} \Rightarrow w_{1}w_{2},...,w_{p-1}AYw_{e+1},...,w_{n}$$

$$Y \Rightarrow w_{q+1}w_{q+2},...,w_{e}$$

或者

$$S \Rightarrow w_{1}w_{2},...,w_{e-1}Xw_{q+1},...,w_{n} \Rightarrow w_{1}w_{2},...,w_{e-1}YAw_{q+1},...,w_{n}$$

$$Y \Rightarrow w_{e}w_{e+1},...,w_{p-1}$$

若结点A是父节点X的左子女,则

$$P(S \Rightarrow w_{1}w_{2},...,w_{p-1}Xw_{e+1},...,w_{n} \Rightarrow w_{1}w_{2},...,w_{p-1}AYw_{e+1},...,w_{n})$$

$$=\beta_{X}(p,e)P(X \rightarrow AY)\alpha_{Y}(q+1,e)$$

同理,若结点A作为父结点X的右子女,则

$$P(S \Rightarrow w_{1}w_{2},...,w_{e-1}Xw_{q+1},...,w_{n} \Rightarrow w_{1}w_{2},...,w_{e-1}YAw_{q+1},...,w_{n})$$

$$=\beta_{X}(e,q)P(X \rightarrow YA)\alpha_{Y}(e,p-1)$$

计算$\beta_{A}(p,q)$时,对于这两种情况,都需要考虑各种可能的重写规则及选择所有的e值,故:

$$\beta_{A}(p,q) = \sum_{X,Y}\sum_{e=q+1}^{n} \beta_{X}(p,e)P(X \rightarrow AY)\alpha_{Y}(q+1,e) + \sum_{X,Y}\sum_{e=1}^{p-1}\beta_{X}(e,q)P(X \rightarrow YA)\alpha_{Y}(e,p-1)$$

因为句法树的根结点总是文法的开始符号,而不会是其它非终结符号,所以有

$$P(S \Rightarrow S) = 1 \qquad P(S \Rightarrow X) = 0$$

$$\beta_{S}(1,n) = 1, \qquad \beta_{X}(1,n) = 0 \quad (X \neq S)$$

此外,根据向内变量及向外变量的定义,有

$$\begin{equation}\begin{split} &P(S \Rightarrow w_{1}w_{2},...,w_{p-1}Aw_{q+1},...,w_{n} \Rightarrow w_{1}w_{2},...,w_{p-1}w_{p},...,w_{q}w_{q+1},...,w_{n}) \\ &= P(S \Rightarrow w_{1}w_{2},...,w_{p-1}Aw_{q+1},...,w_{n})P(A \Rightarrow w_{p}w_{p+1},...,w_{q})\\ &= \alpha_{A}(p,q)\beta_{A}(p,q) \end{split}\end{equation}$$

向外向量的递推公式

$$\beta_{S}(1,n) = 1, \qquad \beta_{X}(1,n) = 0 \quad (X \neq S)$$

$$\beta_{A}(p,q) = \sum_{X,Y}\sum_{e=q+1}^{n} \beta_{X}(p,e)P(X \rightarrow AY)\alpha_{Y}(q+1,e) + \sum_{X,Y}\sum_{e=1}^{p-1}\beta_{X}(e,q)P(X \rightarrow YA)\alpha_{Y}(e,p-1)$$

向外算法描述

输入: 文法 G(S), 语句 $W = w_{1},w_{2},...,w_{n}$.
输出: $\beta_{A}(i,j),\quad A \in N, 1 \le i \le j \le n$

初始化,令

$$\beta_{A}(1,n) = \begin{cases} & 1 \qquad { if } A=S \\ & 0 \qquad { if } A \neq S \end{cases} $$

归纳计算, 对所有的p、q, 且$p \lt q$, 令

$$\beta_{A}(p,q) = \sum_{X,Y}\sum_{e=q+1}^{n} \beta_{X}(p,e)P(X \rightarrow AY)\alpha_{Y}(q+1,e) + \sum_{X,Y}\sum_{e=1}^{p-1}\beta_{X}(e,q)P(X \rightarrow YA)\alpha_{Y}(e,p-1)$$

归纳终止,对任意非终结符号

$$P(w_{1}w_{2},...,w_{n}) = \sum_{A} \alpha_{A}(p,q)\beta_{A}(p,q)$$

韦特比算法寻找最佳的分析树

PCFG的第二个基本问题是在给定文法G和句子$w_{1}w_{2},...,w_{n}$的前提下,如何有效找出最为可能的分析树,这可以通过韦特比算法求得

韦特比变量

$\delta_{A}(p,q)$ 表示以A为根并且叶结点是$w_{p}w_{p+1},...,w_{q}$的所有子树中概率最大的子树的概率,即

$$\delta_{A}(p,q) = \max (P(t_{1}),P(t_{2}),...,P(t_{k}))$$

$\Psi_{A}(p,q)$ 用于记忆字符串$w_{p}w_{p+1},...,w_{q}$的Viterbi语法分析结果,即每一次状态转移方程的来源

$$\Psi_{A}(p,q) = \arg \max_{t} (P(t_{1}),P(t_{2}),...,P(t_{k}))$$

韦特比算法(DP算法)描述

输入: 文法 G(S), 语句 $W = w_{1},w_{2},...,w_{n}$.
输出: $\delta_{S}(1,n)$

初始化, 对所有的 $k (1 \le k \le n)$, 令

$$\delta_{A}(k,k) = P(A \rightarrow w_{k})$$

归纳计算,对所有的p、q, 且 $p \lt q$, 令

$$\delta_{A}(p,q) = \max_{p \le d \lt q, BC \in N} P(A \rightarrow BC) \delta_{B}(p,d)\delta_{C}(d+1,q)$$

$$\Psi_{A}(p,q) = \arg \max_{B,C,d}P(A \rightarrow BC) \delta_{B}(p,d)\delta_{C}(d+1,q)$$

归纳终止

$$P(\tilde{t}) = \delta_{S}(1,n)$$

根据数组$\Psi_{A}(p,q)$中的记录构造概率最大的分析树 $\tilde{t}$

$\tilde{t}$ 的根结点为S
若A是 $\tilde{t}$ 的内部结点(非叶子结点),并且$\Psi_{A}(p,q) = (B,C,d)$, 则
A 的左子女是B,右子女是C, 且B支配子串 $w_{p}w_{p+1},...,w_{d}$, C 支配子串$w_{d+1}w_{d+2},...,w_{q}$

模型训练解决模型参数问题

如何为文法规则选择参数,使得训练句子的概率最大?也就是如何得到文法规则的参数的问题

有指导的训练

树库(Treebank),是标记了句法树结构的语料库

$$\tilde{P}(A \rightarrow BC) = \frac{C(A \rightarrow BC)}{\sum_{\gamma}C(A \rightarrow \gamma)} \qquad \tilde{P}(A \rightarrow w) = \frac{C(A \rightarrow w)}{\sum_{\gamma}C(A \rightarrow \gamma)}$$

树库的构建工作量巨大,耗时耗力,但在没有可靠的无指导训练技术的前提下,树库的构造必须进行
美国宾夕法尼亚大学一直致力于树库的构建工作,其构建的树库被称作Penn Treebank。
其中英文树库规模较大、汉语树库的规模较小
Penn treebank尽管规模很小,但为统计句法分析研究提供了一个很好的基础

无指导训练

无指导训练算法是IO算法——向内向外算法(inside-outside算法)

同Baum-Welch 算法类似, IO算法也是一个反复迭代、逐步求精的算法
通常要首先给定一组不准确的参数,以反复迭代计算的方式调整模型参数
最终使参数稳定在一个可以接受的精度
IO算法不能保证求得最优模型,一般能得到一个局部最优模型

向内向外算法的基本原理

没有树结构,无法准确统计 $C(A \rightarrow BC)$、 $C(A \rightarrow w)$
通过CKY算法,可得到给定句子的所有树结构
基于所有树结构,计算规则的期望频次

$$C^{'}(A) = \sum P(t|S)C(A,C)$$ $$C^{'}(A \rightarrow BC) = \sum P(t|S)C(A \rightarrow BC,t)$$ $$C^{'}(A \rightarrow w) = \sum P(t|S)C(A \rightarrow w,t)$$

基于上述期望频次,进行参数估计

$$P^{'}(A \rightarrow BC) = \frac{C^{'}(A \rightarrow BC)}{C^{'}(A)}$$ $$P^{'}(A \rightarrow w) = \frac{C^{'}(A \rightarrow w)}{C^{'}(A)}$$

如何计算P(t|S)?

$$P(t|S) = \frac{P(t,S)}{P(S)} = \frac{P(t,S)}{\sum_{t}P(t,S)}$$

循环迭代、逐步求精

首先给定一组初始参数
循环,直到得到一组合理的参数
基于当前参数,计算P(t|S)
计算$C^{'}(A)$、$C^{'}(A \rightarrow BC)$, 以及$C^{'}(A \rightarrow w)$
计算新参数

树的概率公式推导

首先,非终结符号A在句法树中支配子串$w_{p}w_{p+1},...,w_{q}$的期望频次,可由下面的公式给出:

$$\begin{equation}\begin{split} &P(A \Rightarrow w_{p}w_{p+1},...,w_{q} | S \Rightarrow w_{1}w_{2},...,w_{n}) \\ &=\frac{P(A \Rightarrow w_{p}w_{p+1},...,w_{q}, S \Rightarrow w_{1}w_{2},...,w_{n})}{P(S \Rightarrow w_{1}w_{2},...,w_{n})}\\ &=\frac{P(S \Rightarrow w_{1}w_{2},...,w_{p-1}Aw_{q+1},...,w_{n} \Rightarrow w_{1}w_{2},...,w_{p-1}w_{p},...,w_{q}w_{q+1},...,w_{n})}{P(S \Rightarrow w_{1}w_{2},...,w_{n})}\\ &=\frac{\alpha_{A}(p,q)\beta_{A}(p,q)}{P(S \Rightarrow w_{1}w_{2},...,w_{n})} \end{split}\end{equation}$$

令 $\pi = P(S \Rightarrow w_{1}w_{2},...,w_{n})$, 则

$$P(A \Rightarrow w_{p}w_{p+1},...,w_{q} | S \Rightarrow w_{1}w_{2},...,w_{n}) = \frac{\alpha_{A}(p,q)\beta_{A}(p,q)}{\pi} $$

考虑到所有的 p < q, 则非终结符号 A 在句法树中出现的期望次数为

P(A在句法树中出现) = $\sum_{p=1}^{n}\sum_{q = p}^{n} \frac{\alpha_{A}(p,q)\beta_{A}(p,q)}{\pi}$

同理, 考虑重写规则 $A \rightarrow BC$在句法树中出现的期望次数:

$$ \begin{equation}\begin{split} &P(A \Rightarrow BC \Rightarrow w_{p}w_{p+1},...,w_{q}| S \Rightarrow w_{1}w_{2},...,w_{n}) \\ &=\frac{P(A \Rightarrow BC \Rightarrow w_{p}w_{p+1},...,w_{q}, B \Rightarrow w_{p},...,w_{d}, C \Rightarrow w_{d+1},...,w_{q}, S \Rightarrow w_{1}w_{2},...,w_{n})}{P(S \Rightarrow w_{1}w_{2},...,w_{n})}\\ &=\frac{\sum_{d = p}^{q-1}\alpha_{A}(p,q)P(A \rightarrow BC)\beta_{B}(p,d)\beta_{C}(d+1,q)}{\pi} \end{split}\end{equation} $$

考虑到所有可能的 p < q, 重写规则 $A \rightarrow BC$ 在句法树中出现的期望次数 P($A \rightarrow BC$在句法树中出现) =

$$\frac{\sum_{p=1}^{n-1}\sum_{q = p+1}^{n}\sum_{d = p}^{q-1}\alpha_{A}(p,q)P(A \rightarrow BC)\beta_{B}(p,d)\beta_{C}(d+1,q)}{\pi}$$

因此有$\tilde{P}(A \rightarrow BC) = \frac{P(A \rightarrow BC)}{P(A)}$,即

$$\tilde{P}(A \rightarrow BC) = \frac{\sum_{p=1}^{n-1}\sum_{q = p+1}^{n}\sum_{d = p}^{q-1}\alpha_{A}(p,q)P(A \rightarrow BC)\beta_{B}(p,d)\beta_{C}(d+1,q)}{\sum_{p=1}^{n}\sum_{q = p}^{n} \alpha_{A}(p,q)\beta_{A}(p,q)}$$

对$A \rightarrow w$, 也可作类似的推导, 若$w_{k} = w$, 有

$$\begin{equation}\begin{split} &P(A \rightarrow w_{k} | S \Rightarrow w_{1}w_{2},...,w_{n}) \\ &= \frac{P(A \rightarrow w_{k}, S \Rightarrow w_{1}w_{2},...w_{k-1}Aw_{k+1},...w_{n})}{P(S \Rightarrow w_{1}w_{2},...,w_{n})} \\ &= \frac{\alpha_{A}(k,k)\beta_{A}(k,k)}{\pi} \end{split}\end{equation}$$

考虑到所有的位置k, 根据 $w_{k} $是否为w, 则 P( $A \rightarrow w$ 在句法树中出现 ) =

$$\frac{\sum_{k=1}^{n} \alpha_{A}(k,k)\beta_{A}(k,k)\delta(w_{k},w)}{\pi}$$

$$\tilde{P}(A \rightarrow w) = \frac{P(A \rightarrow w)}{P(A)} = \frac{\sum_{k=1}^{n} \alpha_{A}(k,k)\beta_{A}(k,k)\delta(w_{k},w)}{\sum_{p=1}^{n}\sum_{q = p}^{n} \alpha_{A}(p,q)\beta_{A}(p,q)}$$

IO算法描述

(1)、任意设定一组概率文法参数$\tilde{P}{0}(A \rightarrow BC)$ 及 $\tilde{P}{0}(A \rightarrow w)$
(2)、令 i = 1
(3)、循环执行下面的步骤,直到文法参数收敛

①、E-Step : 基于$\tilde{P}{i-1}(A \rightarrow BC)$ 及 $\tilde{P}{i-1}(A \rightarrow w)$ 计算 $P(A), \tilde{P}(A \rightarrow BC), \tilde{P}(A \rightarrow w)$的值

P( A在句法树中出现)
P( $A \rightarrow BC$在句法树中出现)
P( $A \rightarrow w$ 在句法树中出现)

②、M-Step :将 E-Step 的计算结果代入

$\tilde{P}(A \rightarrow BC)$
$\tilde{P}(A \rightarrow w)$

得到一组更新的参数$\tilde{P}{i}(A \rightarrow BC)$ 和 $\tilde{P}{i}(A \rightarrow w)$

③、令i = i+1

(4)、算法结束, 输出概率文法参数

基于PCFG的句法分析

PCFG缺陷

PCFG把概率引入上下文无关文法,将统计方法和规则方法进行了有效的融合,具有十分重要的意 义,但是PCFG缺陷也是十分明显的

作为一种统计句法分析方法,基于PCFG的句法分析效果有限

PCFG没有考虑结构之间的依存关系
PCFG没有考虑词汇对句法结构的影响

PCFG作为一种统计语言模型,其效果甚至还不如n-gram模型以及HMM模型

需要针对PCFG的句法分析表现出来的缺陷进行改进

结构依存关系

(1)、代词作为主语的可能性高于作为宾语的可能性

陈述句中91%的主语是代词
陈述句中66% 的直接宾语不是代词

NP $\rightarrow$ Pron, NP $\rightarrow$ Det Noun 的概率应和其在句中所处的位置有关,处在 VP 前后概率应该不同。

PP 可以修饰 VP, PP也可以修饰 NP, 但不同的动词, PP修饰NP和VP的可能性并不相同。

词汇化的句法分析简介

词汇化PCFG

为避免数据稀疏问题,概率计算需要分解

在词汇化PCFG中

$$P(h) \rightarrow L_{n}(l_{n}),...,L_{1}(l_{1})H(h)R_{1}(r_{1}),...,R_{n}(r_{n})$$

H是短语的中心成分
h是成分的中心词
$L_{i}$和$R_{i}$分别是中心成分左右的修饰性成分
$l_{i}$和$r_{i}$分别是左右修饰成分的中心词

在左右两端增加STOP

令$L_{n+1} = STOP \qquad R_{n+1} = STOP$

$$\begin{equation}\begin{split} &P(L_{n+1}(l_{n+1}),...,L_{1}(l_{1})H(h)R_{1}(r_{1}),...,R_{m+1}(r_{m+1})| P(h)) \\ &=P_{h}(H | P(h)) \\ & \times \prod_{i = 1,...,n+1}P_{l}(L_{i}(l_{i})| L_{1}(l_{1}),...,L_{i-1}(l_{i-1}), P(h), H) \\ & \times \prod_{j=1,...,m+1} P_{r}(R_{j}(r_{j}) | L_{1}(l_{1}),...,L_{n+1}(l_{n+1}), R_{1}(r_{1}),...,R_{j-1}(r_{j-1}), P(h), H ) \end{split}\end{equation}$$

作如下的独立性假设

$$P_{l}(L_{i}(l_{i})| L_{1}(l_{1}),...,L_{i-1}(l_{i-1}), P(h), H) = P_{l}(L_{i}(l_{i})|P(h),H)$$

$$P_{r}(R_{j}(r_{j}) | L_{1}(l_{1}),...,L_{n+1}(l_{n+1}), R_{1}(r_{1}),...,R_{j-1}(r_{j-1}), P(h), H ) = P_{r}(R_{j}(r_{j})|P(h),H)$$

$$\begin{equation}\begin{split} &P(L_{n+1}(l_{n+1}),...,L_{1}(l_{1})H(h)R_{1}(r_{1}),...,R_{m+1}(r_{m+1})| P(h)) \\ &=P_{h}(H | P(h)) \\ & \times \prod_{i = 1,...,n+1} P_{l}(L_{i}(l_{i})|P(h),H) \\ & \times \prod_{j=1,...,m+1} P_{r}(R_{j}(r_{j})|P(h),H) \end{split}\end{equation}$$

句法树可以视为自顶向下按照三个步骤产生

(1)、以概率 $P_{H}(H| P,h)$ 生成短语的中心成分标签
(2)、以概率 $\prod_{i = 1,...,n+1} P_{l}(L_{i}(l_{i}) | P, h , H)$生成中心词左边的修饰成分

其中$L_{n+1}(l_{n+1}) = STOP$ , STOP可视作一个特殊的非终结符号, 模型在生成STOP标记时结束生成

(3)、以概率 $\prod_{j=1,...,m+1} P_{r}(R_{j}(r_{j})|P, h,H)$ 生成中心词右边的修饰成分

其中$R_{m+1}(r_{m+1}) = STOP$