不必一次列出整张联合分布表
概率模型可以由数张小表指定。回答查询时,把所有表乘成一张大表虽然可行,却未必必要。变量消去利用分配律,逐个对隐藏变量求和,同时保留其余相关的交互作用。
定义 12.1.1
(因子与因子乘积)
假设只有有限个离散变量,每个变量的取值域有限且非空。因子是在某一指定变量子集(其范围)上的非负实数表。因子乘积对其范围并集的一个赋值,乘起各表中与该赋值相符的项。标量是范围为空的因子。贝叶斯(Bayes)网络在有向无环图上提供因子 ,其乘积就是联合分布。以下计算也适用于其他明确给出的非负因子乘积,但须另行处理归一化。
定义 12.1.2
(限制与未归一化的查询质量)
固定查询变量 、取值为 的已观察变量 和隐藏变量 ;三者不相交且涵盖模型变量。先在每个含证据的因子中代入对应观察值,称为限制;其范围随之去掉那些变量。对查询赋值 ,所需未归一化质量为
分母须为正。若因子乘积是已归一化的联合分布,分母即 。更一般地,若未归一化权重的总和 为正,其诱导分布满足 ,后验比值不变。若 ,这些权重不能定义概率分布。第一式使用原因子;限制后证据参数已代入。若分母为零,此后验没有定义,不能把零向量归一化。
消去一步
定义 12.1.3
(消去一个变量)
选一个隐藏变量 。收集范围包含 的所有当前因子,设为 ,其范围并集为 。把它们换成单一因子
其中 是目前赋值在第 个因子范围上的限制,并令 。不含 的每个因子都保留,包括标量。若没有因子含 ,对它求和会产生等于其取值域大小的标量;一般网络输入通常为每个未观察变量保留一个因子,但这约定使步骤完整。对 中每个变量重复。读出查询值之前不要消去查询变量。
定理 12.1.4
(变量消去的不变式)
设隐藏变量按任意次序消去, 是目前已消去的集合。作为 以外变量的函数,当前因子的乘积等于限制后原因子乘积对 的所有赋值求和。特别是 时,不论次序如何,其余因子的乘积对每个查询赋值都等于 。
证明
(对已消去集合作归纳)
对已消去变量的个数作归纳。 时,当前因子就是限制后的原因子,命题是恒等式。假设命题对 成立,再消去 ,所用的组 是范围含 的所有当前因子。固定 以外变量的赋值 。组以外的因子范围都不含 ,所以它们的乘积 与 无关,可以从对 的求和中提出:
右边是新的当前因子在 的乘积;左边是旧的当前因子在 的乘积对 求和。由归纳假设,旧乘积的值是原乘积对 求和,而有限和可以重排,所以新乘积在 的值就是原乘积对 求和。归纳完成。这个论证只涉及哪些变量出现在哪个范围,并不断言随机变量在概率上独立。当 ,其余范围都在 内;若某查询变量不在任何范围,只是令所得函数沿它取常数。
证明透视
证明为何需要整组因子
证明只用了一个结构事实:收集了该组之后,其余因子的范围都不含 。这正是 能离开对 求和的原因,而它之所以成立,是因为该组包含了所有提到 的当前因子。只要有一个这样的因子留在组外,它就依赖 ,这一步便不成立,所以比“全部收集”更弱的做法都不足够。证明没有用到网络的无环性;无环性只影响范围会变得多大。
隐藏变量可以任意次序消去:有限求和与乘积可重新排列,精确算术下最终质量相同。然而中间因子范围可能不同,因而影响时间及存储量;浮点运算中不同次序也可能产生不同舍入误差。以共同正数缩放因子不改变最终归一化后验,但若要还原原证据质量,必须记录所有缩放常数;不要把数值下溢误作精确零值。
常见错误
(把范围当成独立性)
在下面的链中消去 时,因子 留在求和之外,是因为 不在它的范围内。这只是关于表的参数的陈述,并不表示 与 独立;它们其实相关,因为 ,而 。
带观察证据的链
例题 12.1.5
(链中第一个变量的后验)
考虑二元变量 ,明确假设分解为
设 、、、、,其余二元概率为补数。我们要求 。
先把最后因子限制为 ,再消去隐藏变量 :
对 ,;对 ,。剩余未归一化质量为 和 。因此证据概率为 ,而
常见错误
(把中间因子当成后验)
此处中间因子 是以 为变量的似然,不是 的后验分布。此例中两项恰好总和为一只是数值巧合,不能因此把 当成后验。只将 归一化并不能得到后验:仍须考虑先验。若先把 除以共同正数,再乘先验并于最后归一化,得到的后验不变,因为该常数会抵消。
概念视角算法
把链上的消去看成矩阵乘向量
令 (第一个下标对应 ,第二个对应 ),并令 。则 ,因为 。此处
与上面算出的各项相符。在链上,从证据一端起逐个消去隐藏变量,就是逐次作矩阵乘向量。范围较大时,各表是张量,同一求和就是张量缩并,这也说明为何消去次序决定成本。
例题 12.1.6
(中间变量的后验)
沿用同一条链,以证据 查询 ,这次消去隐藏变量 。含 的因子是 与 ,所以
得 ,。乘以限制后的因子 , 的质量为 , 为 。总和是 ,与先前的证据概率相同,这正是不变式所要求的与次序无关。因此 ,。
例题 12.1.7
(零项与不可能的证据)
把链改为 、。此时 、,质量为 和 。总和为 ,故 、。表中出现零项,并不使证据不可能。再令 :每个 都是 ,总质量为 , 没有定义。模型认为这个观察的概率为零,算法必须报告,而不是归一化。
反例模式
消去变量时漏掉证据因子
一个诱人的捷径,是只用因子 消去 ,理由是 说的是 。在这条链上,对 的两个值都得到 ,质量就是先验 与 ,于是声称 。正确值是 。被漏掉的因子范围含 ,属于该组;漏掉它就丢掉了证据。修正方法就是消去步骤的规则:收集范围含 的所有当前因子。
成本与模型限制
命题 12.1.8
(单步消去的成本)
从 个稠密因子中消去 ,这些因子的范围并集为 。这一步最多读取并相乘 个表项,新因子有 个项目。
证明
(数算范围并集的赋值)
的赋值共有 个。对每个赋值,从 个因子各读一项、相乘,再加进 中去掉 后的赋值所对应的项目。 是 上的稠密表。
即使原本每张表都小,若消去次序产生很大的范围,所需项目数仍可呈指数增长。变量消去对所指定模型是精确的,但它不证明分解或证据准确反映真实世界。
练习
快速检查
(在上述链中,对 求和以计算 。哪些概率须取补数?)
写出 。
解答 · 答案
。须取补数的是 、 与 。核对:。
快速检查
(为何证据概率为零必须报告,而不能归一化?若证据总量为正,其中一个查询项为零又表示什么?)
后验是质量除以证据总量;想想总量为零时这个商是什么。
解答 · 答案
后验是 。若总量为零,商是 :模型给所观察的证据概率为零,条件概率没有定义;改用均匀向量等于自行增加假设,所以必须报告。若总量为正而 ,则在该证据下 的后验概率为零,其余项照常归一化;这是合法答案,例如 时 。
快速检查
(若因子不含所消去变量,为何它可留在求和之外?为何这不证明其范围内的变量与所消去变量在概率上独立?)
把 写成 ,再在链上找反例。
解答 · 答案
范围内没有 的因子,对 求和时是常数,分配律给出 ;这只涉及表的参数。概率上的独立是联合分布的性质。在上述链中消去 时, 留在求和之外,但 ,所以 与 相关。