为什么需要图
个二元变量的联合分布有 个自由参数。直接指定并不现实,而且整张表也看不出哪些变量影响哪些变量。贝叶斯(Bayes)网络用一个有向无环图,加上每个变量一张小型条件表,取代整张联合表。图所记录的建模假设是:每个变量只直接依赖其父节点。本单元证明由此得到的乘积确实是概率分布,并说明图决定了一族条件独立性,可以用纯图形的 d-分离判据读出。本单元建立在“条件独立与证据”一课之上,也为“变量消元”一课作准备,因为后者的因子正是这里定义的各张表。
定义
定义 33.1.1
(贝叶斯网络及其联合分布)
设 为随机变量,各自取值于有限非空集合。贝叶斯网络包括:
- 一个有向无环图(DAG),节点为 ;用 表示 的父节点集合;
- 对每个 给出条件概率表(CPT):对每个取值 及父节点的每个联合取值 ,有数值 ,且对每个 都有 。没有父节点的节点则给出普通的表 。
网络定义联合分布
其中 是 在 的父节点上的限制。拓扑序把节点排成每个父节点都先于其子节点;因为 无环,拓扑序必然存在。若某分布对某些 CPT 等于上述乘积,就称它按 因子分解。
定义 33.1.2
(条件独立)
对三个互不相交的变量集合 ,若对所有 的取值都有 ,则称在给定 时 与 条件独立,记作 。
因子分解定理
定理 33.1.3
(贝叶斯网络的因子分解)
设 按拓扑序排列。上述乘积是概率分布,并且对每个 及每个满足 的赋值,
证明
(对最后一个变量求和)
乘积非负。先对 求和。由于次序是拓扑序, 不是任何 ()的父节点,所以只有最后一个因子含 ,而 。因此乘积对 的和等于前 个因子的乘积,即删去 后的网络所对应的同类表达式。重复这一步,全部变量的总和等于 ,并且 的边缘分布为 。把第 个边缘分布除以第 个,即得第二个结论。
证明透视
无环性用在哪里
证明从次序的尾端逐个移走变量。无环性只在一处起作用:移走 之后,其余因子必须不含 ,而这成立,是因为次序较前的变量都不以 为父节点。于是 使最后一个因子消失,剩下同类的 个节点的网络,归纳便可继续。没有无环性,这一步会失效:取两个二元变量,边为 与 ,两张表在两个值相同时都是 ,否则是 。乘积在 时为 ,其余为 ,总和是 而不是 。
因子分解定理就是链式法则 ,只是每个条件集合都缩小为父节点。这个缩小才是实质性的建模主张:给定父节点时,变量与次序中其余前驱独立。因此自由参数个数为 ,父节点集合较小时数目很小。
概念视角算法
把乘积看作抽样过程
按拓扑序依次访问各节点,根据父节点已抽得的取值选出表中对应的一行 ,再从该行抽取 。因为父节点总是排在前面,每次运行都有明确定义;运行得到 的概率,等于各次抽取概率的乘积,也就是定义中的那个乘积。在警报网络中,运行结果 的概率为 。因此贝叶斯网络既是一组数表,也是生成数据的配方。
d-分离
定义 33.1.4
(路径、阻断与 d-分离)
图所蕴涵的独立性,可以通过检查无向路径(即互异节点的序列,相邻节点之间有任一方向的边)得到。设 是路径上的节点,其在路径上的邻点为 与 ,则该三元组称为
- 链: 或 ;
- 叉:;
- 对撞:。
设 为已观察节点集合。若路径含有
- 一个中间节点 的链或叉,或
- 一个中间节点 且 没有后代在 中的对撞,
则称该路径被 阻断。对互不相交的集合 以及与两者都不相交的 ,若每条由 的节点到 的节点的路径都被 阻断,就称 与 被 d-分离;否则称在给定 时 与 d-连通。
定理 33.1.5
(d-分离的可靠性)
若在 中 与 被 d-分离,则对每个按 因子分解的分布,都有 。
证明
(链、叉与对撞三种情形)
我们证明三种基本情形,以说明各条规则的来源,一般情形只陈述不证明。条件化时均设 。
- 链 :。
- 叉 :。
- 对撞 :对 求和得 ,故 。然而 一般不是乘积,所以观察 或其后代可以产生相关性。
反过来并不成立:d-连通只表示对某些 CPT 的选取,相关性有可能出现,并非对所有选取都成立。
反例模式
对撞点的后代也会使路径畅通
一个诱人的简化说法是:只要对撞点本身没有被观察,经过它的路径就被阻断。取网络 并加上子节点 ,其中 是独立的公平二元位, 恰在 或 时成立,而 。对撞点 虽未被观察,但以 为条件就等于以 为条件:,而 ,所以给定 时 与 并不独立。正确的规则就是定义中的那一条:只有对撞点及其所有后代都没有被观察时,经过它的路径才被阻断。
例题
例题 33.1.6
(读出联合分布的一项并计算参数个数)
取二元变量:入室盗窃 、地震 、警报 ,以及两位邻居 、,边为 、、、。各表为
而 时 依次为 。对应于 的联合分布值为
该网络共有 个自由参数(、 各一个, 四个,、 各两个),而不受限制的联合表需要 个。
例题 33.1.7
(d-分离查询与解释消除)
在同一个图中, 与 被 d-分离:唯一的路径 以 为对撞, 未被观察,也没有被观察的后代。给定 时两者 d-连通,因为 是 的后代;给定 时同样 d-连通。另外, 与 在 下 d-连通(叉 是畅通的),但被 d-分离。 与 也被 d-分离:唯一路径是经过已观察节点 的链 。
数值显示对撞效应。首先 ( 一项贡献 )。于是
得知发生了地震会降低盗窃的概率:警报被“解释掉”了,尽管 与 在先验下彼此独立。
例题 33.1.8
(链上的相关性与给定中间节点后的独立性)
取二元变量构成的链 ,、、、、。网络有 个自由参数,完整联合表则需要 个。其中一项联合值是 。
没有观察时链是畅通的:,而 ,所以 与 相关。给定 后链被阻断:不论 取何值,、,故 。边界情形:若 ,链仍然 d-连通,但 与 实际上独立;图只容许相关,并不强制相关。
常见错误与细微之处
常见错误
(把边读成因果)
只要给定 CPT,因子分解定理对任何 DAG 都成立;边的方向只决定给出哪些条件表。不同的 DAG 可以定义同一族分布。
常见错误
(把 d-连通读成相关)
d-分离只能证明独立,从不证明相关。若 是二元变量 的唯一父节点,而 ,则在该网络中 ,尽管边 是一条 d-连通路径。
常见错误
(以为观察节点必定阻断路径)
观察 会阻断链 ,却会使对撞 畅通。观察一个节点的效果取决于它在路径上的角色,所以先把每个三元组分类为链、叉或对撞,再下判断。
另有两点。以一个既不在某条路径上、也不是该路径上某个对撞点后代的节点为条件,不会改变该路径的状态。此外,只有条件事件概率为正时,条件独立的陈述才有意义。
习题
快速检查
(在第一个例题的警报网络中,计算 。)
每个变量取一项表值相乘,需要时用互补概率。
解答 · 答案
。
快速检查
(在边为 、、、、 的 DAG 中,判断下列各项在 d-分离意义下是否成立:(a) 给定 时的 与 ;(b) 给定 时的 与 ;(c) 给定 时的 与 ;(d) 给定 时的 与 。)
把每条路径上的三元组分类为链、叉或对撞,再判断路径是否被阻断。
解答 · 答案
(a) 成立。叉 因 已观察而被阻断;路径 的对撞点 未被观察,其唯一后代 也未被观察,故被阻断。(b) 不成立。此时 是对撞点 的后代且已被观察,所以 畅通;另一条路径仍被阻断,但只要有一条畅通路径就是 d-连通。(c) 不成立。叉 的中间节点未被观察,路径畅通。(d) 成立。由 到 的每条路径( 与 )都以 为链上节点,而 已观察,故两条都被阻断。
快速检查
(设 为独立的公平二元位,而 恰在 或 时成立。计算 、 与 。)
先写出 的联合分布,再对该事件条件化。
解答 · 答案
事件 的概率为 ,其中 的概率为 ,所以第一个值是 。给定 与 , 仍是公平二元位:。给定 与 ,必有 ,值为 。三个值 展示了解释消除的模式。
快速检查
(网络有边 ,且 。证明 ,尽管 与 d-连通。)
由各表算出 ,并与 比较。
解答 · 答案
无论 为何,对每个 都有 。边缘分布 ,故 ,即 。单独一条边就是畅通路径,所以两者 d-连通;这说明 d-连通只是允许相关。