为什么要为文法加上概率?
同一个句子可能有多个合法的句法分析。前面的 CKY 表格能判断分析是否存在,也能记录不同的切分,但它本身不能衡量各个分析的相对权重。概率上下文无关文法(PCFG)给每条产生式赋予概率,进而给完整的分析树赋权。这提供了明确的排序方法,却不能保证得分最高的树就是说话者原本的意思。
对同一个句子,我们将计算两个不同的量:内部概率把所有分析树的权重相加;维特比(Viterbi)概率取其中单棵最优树的权重。前者衡量模型赋予整个观测句子的概率,后者帮助我们选出一个分析。把求和换成取最大值,回答的问题就变了。
模型和条件
定义 32.1.1
(二元概率文法与树的权重)
设非终结符集 、词汇集 和带标签的产生式集合 都有限,起始符为 。推导树在每个节点记录所选规则的标签:即使书写的左右两侧相同,不同规则标签仍算不同推导。每条规则形如 或 ,其中 ,。同一左侧的规则概率非负且总和为一。在标记为 的每个节点,按照这些概率选择规则;各节点使用独立的随机抽取,抽取分布由该节点的标记决定。有限分析树的概率,即权重,是树上所有规则概率的乘积。
局部概率归一化并不保证生成过程最终停止。例如若 的概率为一,就永远无法生成终结符句子。额外假设从 出发的过程几乎必然终止,此时有限终结树的总概率才是一。即使缺少这一假设,下述有限表格仍给出指定有限句子的无条件概率;但只要存在正概率不终止,所有有限句子的概率之和就小于一。零权重规则可以省略。
定义 32.1.2
(内部值与维特比值)
对非空句子 、非终结符 及 ,令 为根为 、叶子恰好是 的所有有限树的权重和,并令 为这类树中单棵树的最大权重;没有这样的树时为零。句子的内部概率是 ,维特比概率是 。
记规则概率为 或 。内部值满足
如果文法把拼写相同的词汇规则用不同标签分别表示,第一项就把它们的权重加起来。若只按节点符号与分支结构区分树,而不区分书写完全相同的规则标签,可先把这些选项的概率相加,再用一条规则表示。终止模型赋予整个句子的概率是 ,不需要除以句长或分析数。
为什么递推是正确的
定理 32.1.3
(内部概率递推)
对于上述二元/词汇规则文法和固定的非空句子,这个递推恰好计算每个 所有对应分析树的权重和。如果从起始符开始几乎必然终止, 就是生成该句子的概率。
证明
(对跨度归纳)
对跨度归纳。跨度为一时,树根必须使用一条词汇规则;把所有匹配规则的概率相加,就得到正确结果。对较长的跨度,根必用某条二元规则 。两个子树都产生非空片段,所以左片段有唯一确定的结束位置 。反过来,一条根规则、一个切分以及左右子树唯一确定一棵父树。这样的组合既不遗漏,也不重复。
由归纳假设,左右子树的权重和已经正确。把两者相乘,由分配律得到每一对左右子树的权重乘积;再乘以根规则概率,就是父树的权重。对所有规则和切分求和,便得到全部父树的权重和。固定 时,一棵二叉树有 个叶节点和 个二元节点,所以带规则标记的推导只有有限个,不涉及无穷求和的交换。
证明透视
独立性用在什么地方
证明用到三个事实,各用在一处。树与它的组成部分(根规则、切分、左子树、右子树)之间的一一对应是关键一步;它要求每条规则都是二元规则或词汇规则,使父节点恰有一个切分点。分配律再把两个和的乘积化为对全部左右子树配对的求和。生成模型只用在“树的权重等于其规则概率之积”这一句上,由各节点独立选择规则来保证。若规则的选择依赖整句之前的上下文,就需要换一种状态或递推;结论不能自动用于所有语言模型。若允许 与 这类一元规则,同一跨度就有无穷多棵树,按跨度归纳便走不到基例。
最优树与总概率
维特比值服从同一个递推,只是把每个求和换成取最大值。词汇基例对匹配规则取最大值,二元递推为
空集合上的最大值约定为零。
定理 32.1.4
(带回溯指针的维特比递推)
对固定的非空句子,上述递推计算 ,即根为 、覆盖 的树的最大权重(没有树时为零)。若 ,取达到最大值的规则与切分,并在左右子树中递归地照做,就重建出权重为 的一棵树。
证明
(独立因子之积的最大值)
对跨度归纳。单个词元的树只含一条词汇规则,所以最大权重就是匹配规则概率中的最大者。对较长的跨度,每棵树都有根规则 、切分 、覆盖 的左子树 和覆盖 的右子树 ,其权重为 。固定规则与切分后, 与 的选择互不影响,且所有权重非负,所以 的最大值就是两个最大值之积;由归纳假设,两者分别是 和 。再对规则和切分取最大值,便得到所述递推。
若最大值为正,则达到最大值的规则与切分满足 且 。由归纳假设,两个子片段各有达到相应权重的最优树,在根规则下把它们合并,就得到权重为 的树。
概念视角结构
同一个表格形状,不同的运算
两个表格的形状都是 。内部表格在非负数上取 、;维特比表格取 、。上面两个证明的区别,只在于乘法为什么能穿过 :对和有 ,对最大值,当 时有 。若把每条规则概率换成“真”,把 换成“或”、 换成“且”,就得到 CKY 的识别表格,它只记录是否存在某棵树。三个表格针对同一批树回答三个不同的问题:总权重、最重的一棵,以及有没有树。
沿回溯指针可以恢复一棵最优树。出现并列时,可能有几棵同样好的树;保存所有最优见证才能恢复全部并列最优树。数值零既可能表示没有分析,也可能表示存在权重为零的合法分析;若要区分,应另存一张布尔(Boole)表。
命题 32.1.5
(两个表格的代价)
设句子有 个词元, 与 分别是二元规则与词汇规则,并假设算术运算的成本为常数。直接遍历规则时,至多计算 个“规则加切分”项和 个词汇项,所以时间为 。数值表格有 个格子,即 。
证明
(数跨度与切分)
格子 ()有 个可能的切分 ,每条二元规则对每个切分给出一项。令 ,长度为 的格子有 个,所以“规则加切分”项的个数是 。 个单词元格子各把每条词汇规则检查一次。表格对每个非终结符和每个跨度 各有一个格子,跨度共有 个。保存全部回溯指针可能比数值表格占用更多空间。
例题
例题 32.1.6
(三个词元的两个分析)
设 概率为 , 概率为 。此分支过程几乎必然终止:终止概率 是 中方程 的最小解,即 。为什么取最小根:设 为所有分支在深度 之前停止的概率,从 出发,递推 递增并趋于终止概率;它始终不超过任何非负不动点。aaa 的两种括号结构是 和 。每棵树都使用两条二元规则、三条词汇规则,权重为 。所以 ,而 ;两棵树都是维特比解。总概率更大,是因为两种推导是不同的事件。
例题 32.1.7
(为两个权重不等的分析填写两个表格)
取产生式 (概率 )、(概率 ),以及 、、、、(概率均为 )。对句子 abc,单词元格子为 ,其他非终结符均为零。长度为二时,,;维特比值相同。其余长度为二的格子全为零。特别地, 在 ab 上的格子为零: 需要单独一个 a 构成 , 需要单独一个 b 构成 ,两者都不可能。所以 ab 是一个 ,却不是 ;这个零来自缺少分析,而不是规则权重为零。
对整个句子,规则 在切分 处贡献 , 在切分 处贡献 。因此 ,,回溯指针是 ,对应的树为 。给定句子时这棵树的条件概率是 。内部值 与模型一致:abc 是唯一概率为正的句子。
例题 32.1.8
(下溢与 log-sum-exp 一步)
设一个长句子恰有两个分析,权重分别为 和 。两个数都小于双精度浮点数能表示的最小正数,直接连乘会下溢成零,表格就无法区分它们。取对数后,第一个权重是 ,第二个是 。维特比值取较大者,即 。内部值需要求和:。若用最大值代替 log-sum-exp,会报告 ,把内部概率低估为实际的 。
常见错误与细微之处
反例模式
最重的树不一定属于概率最大的句子
论断:最优分析树更重的句子,就是概率更大的句子。取 与 (概率各 )、(概率 ),以及 、、、、、(概率均为 )。同一左侧的规则概率之和为一,每个推导改写两层后即停止,所以有限树的总权重为 。句子 ab 有两棵树 与 ,权重各为 ,故 ,。句子 cd 只有一棵树 ,权重 ,故 。维特比值把 cd 排在前面,但两句的概率分别是 和 ,概率更大的是 ab。比较句子必须用内部概率;维特比只用来为给定句子挑一棵树。
在已经观察到句子的条件下,某棵树的后验概率等于该树的权重除以 ,前提是分母为正。它不同于维特比表给出的联合权重。在上面的反例中,ab 的两棵树条件概率各为 ;若句子的概率为零,这个条件式没有定义。实际计算中,许多小概率相乘可能下溢;取对数可以把乘法变成加法,但求和时需要数值稳定的 log-sum-exp,而不是简单取最大值。
常见错误
(数词串,而不是数推导)
对文法 (概率 )、(概率 )中的 aaa,括号结构 与 给出同一个词串,容易把它们算作一个分析,报告 。它们是两棵不同的树,所以内部概率是 。求和是对推导进行的,不是对不同的词串进行的。
常见错误
(局部归一化不等于会终止)
取 概率 、 概率 。左侧为 的规则概率之和为一,但有限树的总权重只有 (即 的较小根),所以由表格得到的各句子概率之和是 ,而不是 。把每组规则各自归一化,并不能使整个生成过程成为有限句子上的概率分布。
练习
快速检查
(对文法 (概率 )、(概率 ),求 和 aaaa 的总概率,并解释后者根节点的三种切分。)
记 个 a 的内部值为 ,并对各切分长度求和。
解答 · 答案
两个词元只有一棵树,其权重为 。四个词元的根切分长度分别是 ,所以
也可以数出五棵二叉树,每棵有三条二元规则和四条词汇规则,权重各为 。
快速检查
(一个句子恰有两棵正权重的分析树,权重为 和 ,没有其他分析。求内部值、维特比值,以及给定句子后第二棵树的后验概率。)
一个用求和,一个用取最大值,再用树的权重除以内部值。
解答 · 答案
内部值为 ,维特比值为 。给定句子,第二棵树的概率为 。最大值与总和回答的是不同的问题。
快速检查
(若 概率为 , 概率为 ,求 在 中的最小解。为什么局部归一化不能保证几乎必然终止?)
整理成二次方程,找出不等于 的根。
解答 · 答案
方程的两个解是 和 ,因此终止概率是较小的 。虽然每个节点的选项概率之和为一,仍有 的概率产生无穷推导。局部归一化只规定了每一步的选择,不能证明整个过程会停止。
快速检查
(在 abc 例题的文法中,把 与 的概率改为 和 。求顶层格子的内部值、维特比值与回溯指针。)
只有顶层的两项改变;长度为二的各项不变。
解答 · 答案
在切分 处的项为 , 在切分 处的项为 。内部值为 ,维特比值为 ,回溯指针是 ,对应的树是 。最优树的条件概率为 。