一张有向图怎样把联合概率拆成可计算的小表?
读后可检查:把 DAG、CPT 和条件独立对应起来,再核对警报例的推理和解释掉现象。
📑 本页目录(点开跳转)
17 · 贝叶斯网络
⏱ 30 分钟 | ⭐ 31 个数压成 10 个 —— 条件独立值多少钱,可以算出来
🎯 一句话
贝叶斯网 = 一张有向无环图 + 每个节点一张条件概率表;图里没画的那些边,就是你省下来的参数。
上一章说条件独立能把指数压回线性,这一章把它画出来,顺便把账算清楚。
🧮 一、先把账摆在桌面上
5 个布尔变量的完整联合分布有 $2^5 = 32$ 行,减去「加起来等于 1」这一个约束,还剩 31 个自由参数。每多一个变量翻一倍,20 个变量就是 100 多万个数。存不下只是小麻烦,真正要命的是:这一百万个数你从哪儿估? 每一格都要求「同时满足这 5 个条件」的样本,而这种样本几乎一个都没有。
⭐ 上一章的出路是条件独立。贝叶斯网就是把「谁在给定谁之后互不相干」画成一张图 —— 图是给人看的,省下来的参数是给机器用的。
🧱 二、结构:DAG 加 CPT
- 节点 = 一个随机变量;箭头 $A \to B$ = 「$A$ 是 $B$ 的直接原因」。
- 图必须有向无环(DAG)—— 有环等于某个变量是自己的祖先,下面那条分解式就没有定义。
- 根节点只存先验,非根节点存一张条件概率表(CPT),父节点每种取值组合占一行。
- ⭐ 全网联合分布由这些局部表相乘得到:
$$P(x_1, \dots, x_n) = \prod_{i=1}^{n} P\big(x_i \mid \mathrm{Pa}(x_i)\big)$$
这不是新公理,是链式法则加上一条结构假设:给定父节点之后,一个变量与它的所有非后代条件独立。链式法则里那些又长又估不出来的条件项 $P(x_i \mid x_1,\dots,x_{i-1})$,被砍成只依赖父节点的短项。参数个数因此是 $\sum_i 2^{|\mathrm{Pa}(i)|}$ —— 只跟每个节点有几个父节点有关。
🚨 三、警报网络:完整手算一遍
你在上班,家里的防盗警报对入室盗窃很灵,可偶尔地震也会把它震响。两个邻居说好听到警报就打你电话,但 John 听到电话铃也会打,Mary 常听不见。五个布尔变量:$B$ 盗窃、$E$ 地震、$A$ 警报响、$J$ John 打来、$M$ Mary 打来。
| 节点 | 要存的参数 | 值 |
|---|---|---|
| $B$ / $E$ | $P(b)$ / $P(e)$ | .001 / .002 |
| $A$ | $P(a \mid \cdot)$,父节点四种组合:$be$ / $b\lnot e$ / $\lnot be$ / $\lnot b\lnot e$ | .95 / .94 / .29 / .001 |
| $J$ | $P(j \mid a)$ / $P(j \mid \lnot a)$ | .90 / .05 |
| $M$ | $P(m \mid a)$ / $P(m \mid \lnot a)$ | .70 / .01 |
⭐ 压缩账:$1 + 1 + 4 + 2 + 2 = \mathbf{10}$ 个数,完整联合分布要 31 个。省下的 21 个不是丢掉了,是被图的结构推出来的:$J$ 只连 $A$,等于断言「知道警报响没响之后,盗窃和地震对 John 打不打电话再没影响」。
手算一:任意一条联合概率
「警报响了、两人都打了电话,但既没盗窃也没地震」——
$$P(j,m,a,\lnot b,\lnot e) = 0.999 \times 0.998 \times 0.001 \times 0.9 \times 0.7 = \mathbf{0.000628}$$
五个数相乘,全部直接从表里查 —— 这就是那条分解式的实用价值。
手算二:诊断推理(反着走)
两人都打来电话了,家里被盗的概率是多少?把没观测到的 $E$ 和 $A$ 枚举掉:
$$P(b \mid j,m) \;\propto\; P(b) \sum_{e}\sum_{a} P(e)\,P(a \mid b,e)\,P(j\mid a)\,P(m\mid a)$$
先备好内层两个常数:$P(j\mid a)P(m\mid a) = 0.63$,$P(j\mid \lnot a)P(m\mid \lnot a) = 0.0005$。
| 分支 | 对 $A$ 求和(响 + 不响) | 再乘 $P(e)$ |
|---|---|---|
| $b,\ e$ | .95×.63 + .05×.0005 = .598525 | ×.002 = .0011971 |
| $b,\ \lnot e$ | .94×.63 + .06×.0005 = .59223 | ×.998 = .5910455 |
| $\lnot b,\ e$ | .29×.63 + .71×.0005 = .183055 | ×.002 = .0003661 |
| $\lnot b,\ \lnot e$ | .001×.63 + .999×.0005 = .0011295 | ×.998 = .0011272 |
再乘各自的先验:$b$ 支 $= 0.001 \times (.0011971 + .5910455) = 5.922\times10^{-4}$;$\lnot b$ 支 $= 0.999 \times (.0003661+.0011272) = 1.492\times10^{-3}$。归一化:
$$P(b \mid j,m) = \frac{5.922}{5.922 + 14.92} = \mathbf{0.284}$$
⭐ 两个邻居同时打电话,被盗概率也只有 28%。 先验 0.1% 涨到 28.4%,翻了 284 倍,仍然连三成都不到 —— 又是上一章那个基础率:「没被盗、警报误响、两人都打来」这条路虽然稀薄,却架在 99.9% 的巨大底座上。
💻 四、十四行把它跑起来
P_B, P_E = 0.001, 0.002
P_A = {(1,1): 0.95, (1,0): 0.94, (0,1): 0.29, (0,0): 0.001} # ⭐ 警报的 CPT
P_J, P_M = {1: 0.90, 0: 0.05}, {1: 0.70, 0: 0.01}
def pr(x, t): # x=1 取 t,x=0 取 1-t
return t if x else 1 - t
def joint(b, e, a, j, m): # ⭐ 链式法则:五个因子相乘
return (pr(b, P_B) * pr(e, P_E) * pr(a, P_A[(b, e)])
* pr(j, P_J[a]) * pr(m, P_M[a]))
print(joint(0, 0, 1, 1, 1)) # 0.0006281112...
num = sum(joint(1, e, a, 1, 1) for e in (0,1) for a in (0,1))
den = sum(joint(b, e, a, 1, 1) for b in (0,1) for e in (0,1) for a in (0,1))
print(num / den) # ⭐ 0.2841718...
不用装任何库。⭐ 整个「模型」就是开头三行字典 —— 贝叶斯网的知识全在 CPT 里。
⏳ 五、推理要花多少钱
上一节把 局部条件概率表 当作因子,也就是按相关变量的取值查数的表。概率相乘得到一组完整赋值的权重,边缘化再把不查询的变量逐一求和。枚举法先算完整赋值再分组相加。若有 $n$ 个尚未固定的二值变量,全部赋值就有 $2^n$ 组。
如果某些因子与眼下要求和的变量无关,分配律允许把它们移到求和号外。所以可以只把涉及该变量的因子相乘,求和后存成一张新表,其余因子原样留下。这种逐个求和、复用中间表的方法叫变量消元(variable elimination)。例如警报算例中的 $P(j\mid a)P(m\mid a)$ 只看警报的状态,对不同的盗窃和地震取值可以复用。依据:Dechter §4.1。
同一查询,先消谁更省表格? 换一组专门用来比较顺序的演示数据。中心 $C$ 和叶子 $A,B,D,Q$ 都只取 $0,1$,查询保留 $Q$,没有观测证据。中心的一元权重 $g(c)$ 在 $c=0,1$ 时分别为 $1,2$。每条边的因子 $f(c,x)$ 在中心取值 $c$ 与叶子的取值 $x$ 相同时为 $2$,不同时为 $1$。这些是无单位的演示权重。完整联合权重由一张中心表和四张边表相乘,归一化后才是概率。
把当前共同出现在某张因子表里的两个变量用无向边连接,这就是交互图(interaction graph)。消掉一个变量时,它的邻居共同进入求和后的因子表。原本没有相连的邻居需要补边,称为填边(fill-in)。
一格对应一组取值。消元时,参与相乘的因子涉及哪些变量,就把哪些变量的取值数乘起来,得到乘积表的格数。对一个变量求和后,那一维从表里消失。下表分别统计两种顺序中最大的乘积工作区和最大的求和后因子。
| 顺序(从左到右) | 最大乘积工作区 | 最大求和后因子 |
|---|---|---|
| $C,A,B,D$ | 消 $C$:五个变量,$2^5=32$ 格 | $A,B,D,Q$,$2^4=16$ 格 |
| $A,B,D,C$ | 每步两个变量,例如 $C,A$,$2^2=4$ 格 | 每步一个变量,$2^1=2$ 格 |
手算核对,两条路都得到同一概率。 令 $a,b,d,q$ 分别是 $A,B,D,Q$ 的取值,求和下标 $c,a,b,d$ 都各自取遍 $0,1$。中心先消时,先计算四叶因子 $h$,再加总非查询叶的取值,得到 $Q=q$ 的边缘权重 $W(q)$:
$$h(a,b,d,q)=\sum_{c=0}^{1} g(c)f(c,a)f(c,b)f(c,d)f(c,q)$$
例如 $h(0,0,0,0)=1\times2^4+2\times1^4=18$。要算 $W(q)$,把 $h$ 中同一个 $q$ 的八格相加。把求和按中心取值分组,三个非查询叶各贡献 $(2+1)$,所以中心的两个分支分别乘上 $(2+1)^3=(1+2)^3=27$。
叶子先消时,固定 $c$,任一非查询叶的因子先求和,得到只含 $C$ 的两格表。对 $c=0$,两格边权相加是 $2+1=3$;对 $c=1$ 是 $1+2=3$。三个叶因子都做这一步,再与 $g(c)$ 和查询边 $f(c,q)$ 相乘、对 $c$ 求和。于是两条路都有:
$$W(q)=\sum_{c=0}^{1} g(c)f(c,q)\,3^3$$
$$W(0)=27(1\times2+2\times1)=108,\qquad W(1)=27(1\times1+2\times2)=135$$
两种查询结果的总权重为 $108+135=243$。各自除以 $243$ 得 $P(Q=0)=4/9$、$P(Q=1)=5/9$。精确求和中改变消元顺序等于重排同一批加法和乘法,所以这里改变的是计算过程中的表格大小。
试一试:如果改为查询中心 C,还会在叶子之间补边吗?
不会。保留 C,依次消去 A、B、D、Q。每个叶子被消去时都只剩 C 这一个邻居,求和后只产生关于 C 的一元因子。填边需要至少两个尚未相连的邻居。
这些是逐步显式建表时的单表格数。变量取值数变了,格数也变。比如只把 $A$ 改成三值,中心先消的第一步变成 $3\times2^4=48$ 格,求和后变成 $3\times2^3=24$ 格。若已有观测 $C=0$,可以先把 $c=0$ 代入每张表,四条边表各自只剩一个叶子变量,此时无须生成四叶因子。一般图上的精确推理具有 NP 难的最坏情况。在稠密表消元中,比较顺序时要看每一步的邻居范围和变量取值数;邻居范围的最大大小称为给定消元顺序的诱导宽度(induced width)。依据:Dechter §3、§4.2–4.3。
代码验证。 第一段穷举所有赋值并按 $Q$ 累加。eliminate 每轮选出有关因子、列出乘积表、按剩余变量的取值分组相加。最后复核两种顺序和穷举所得的权重,并用标准库分数精确归一化。
from fractions import Fraction
from itertools import product
from math import prod
states = (0, 1)
leaves = ("A", "B", "D", "Q")
variables = ("C",) + leaves
center = {0: 1, 1: 2}
def edge(c, x):
return 2 if c == x else 1
def assignments(scope):
for values in product(states, repeat=len(scope)):
yield dict(zip(scope, values))
# 直接枚举全体赋值,按查询叶 Q 的两个值累加。
weights = [0, 0]
for row in assignments(variables):
weight = center[row["C"]] * prod(edge(row["C"], row[x]) for x in leaves)
weights[row["Q"]] += weight
def eliminate(order):
# 每个因子由变量范围和对应的稠密数表组成。
factors = [(("C",), {(c,): center[c] for c in states})]
factors += [
(("C", x), {(c, v): edge(c, v) for c, v in product(states, repeat=2)})
for x in leaves
]
product_sizes, summed_sizes = [], []
for variable in order:
bucket = [factor for factor in factors if variable in factor[0]]
factors = [factor for factor in factors if variable not in factor[0]]
scope = tuple(x for x in variables if any(x in keys for keys, _ in bucket))
remaining = tuple(x for x in scope if x != variable)
# 先显式列出乘积表,再把仅在被消变量上不同的行相加。
workspace = []
for row in assignments(scope):
value = prod(table[tuple(row[x] for x in keys)] for keys, table in bucket)
workspace.append((tuple(row[x] for x in remaining), value))
summed = {}
for key, value in workspace:
summed[key] = summed.get(key, 0) + value
product_sizes.append(len(workspace))
summed_sizes.append(len(summed))
factors.append((remaining, summed))
assert all(set(keys) <= {"Q"} for keys, _ in factors)
result = [
prod(table[(q,) if keys else ()] for keys, table in factors)
for q in states
]
return result, product_sizes, summed_sizes
center_first = eliminate(("C", "A", "B", "D"))
leaf_first = eliminate(("A", "B", "D", "C"))
assert center_first == ([108, 135], [32, 16, 8, 4], [16, 8, 4, 2])
assert leaf_first == ([108, 135], [4, 4, 4, 4], [2, 2, 2, 2])
assert weights == center_first[0] == leaf_first[0]
probabilities = [Fraction(w, sum(weights)) for w in weights]
assert probabilities == [Fraction(4, 9), Fraction(5, 9)]
print("未归一化权重:", weights)
print("概率:", ", ".join(map(str, probabilities)))
for label, (_, products, summed) in (("中心先消", center_first), ("叶子先消", leaf_first)):
print(label, "乘积表峰值", max(products), "求和后因子峰值", max(summed))
未归一化权重: [108, 135]
概率: 4/9, 5/9
中心先消 乘积表峰值 32 求和后因子峰值 16
叶子先消 乘积表峰值 4 求和后因子峰值 2
于是有近似推理,全部基于采样:按 CPT 从根往下随机生成完整样本,再数比例。拒绝采样把不符证据的样本全扔(证据罕见时浪费惊人)、似然加权改成强制证据成立再给样本配权重、吉布斯采样每次只重采一个变量(属于 MCMC)。共同点:样本越多越准,但永远只是近似。
🧭 六、三种结构,和「解释掉」
要判断「哪两个变量在给定谁之后独立」,认三种局部形状就够(完整版叫 d-分离):
| 结构 | 形状 | 不给中间节点 | 给了中间节点 |
|---|---|---|---|
| 链式 | $A \to B \to C$ | 相关 | 独立 |
| 分叉(共因) | $A \leftarrow B \to C$ | 相关 | 独立 |
| 汇聚(共果) | $A \to B \leftarrow C$ | ⭐ 独立 | ⭐ 相关 |
前两行符合直觉:共同的原因知道了,两个结果就互相说明不了什么(上一章的牙疼与探针)。第三行反直觉,也最有用。警报网里 $B \to A \leftarrow E$ 正是汇聚:
- 没听到警报时,知道昨晚地震了,对「有没有被盗」一点信息都不提供。
- 可一旦知道警报响了,两者立刻相关:$P(b \mid a) = \dfrac{0.001 \times 0.94002}{0.00251642} = \mathbf{0.374}$。
- 再补一条「昨晚确实地震了」:$P(b \mid a, e) = \dfrac{0.001 \times 0.002 \times 0.95}{0.00058132} = \mathbf{0.0033}$。
⭐ 嫌疑从 37.4% 掉到 0.33%,跌了 114 倍 —— 地震把警报「解释掉」了(explaining away)。警报需要解释的份额有限,一个原因被证实,另一个就自动被洗清。⚠️ 单向传播的规则系统做不出这件事,下一节要用。
🧪 七、贝叶斯之外的两种老办法
贝叶斯网普及之前,专家系统用的是另一套。讲义提了两种,都值得知道为什么它们输了。
① 置信因子(certainty factors) —— 给每条规则挂一个 0 到 1 的数并定一套传播规则:规则本身只有 0.8 把握、前提也只有 0.8,结论就是 $0.8 \times 0.8 = 0.64$;两条独立证据各 0.8 都指向 $C$,先算「都不成立」$(1-0.8)^2 = 0.04$,反回去得 0.96;合取取 $\min$。
⚠️ 为什么被取代:① 这些数不来自任何形式模型,换个专家就换一套,彼此还互相矛盾;② 组合规则没有理论依据 —— $1-\prod(1-x)$ 悄悄假设了证据独立却从不检查,$\min$ 更是直接扔信息;③ 不满足概率公理,没法边缘化、没法回答「给定这些证据,$X$ 的分布是什么」。最致命的是第四条:CF 只能顺着规则单向传播,做不出「地震解释掉盗窃」—— 而那恰恰是诊断里最关键的一步。
② 溯因推理(abduction) —— 从结果找最佳解释:灯不亮,可能是灯泡坏、停电、开关没开。⚠️ 它不是有效推理(由 $B \to A$ 和 $A$ 推出 $B$ 是肯定后件谬误),只能给「最像的那个」。⭐ 但它没消失,而是在贝叶斯网里拿到了严格版本:MAP 解释 = 后验概率最大的那组原因赋值。溯因问的问题是对的,缺的只是尺子。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 16 · 不确定性下的推理 | 本章用的乘法法则、边缘化、归一化、条件独立全在那里;朴素贝叶斯就是最简单的贝叶斯网 |
| 机器学习的数学原理 13 · EM 与高斯混合 | 本章 CPT 都是给定的。要从数据里学、而网里还有看不见的变量时怎么办 —— EM 干的就是这个 |
| 机器学习的数学原理 02 · MAP 与正则化的真身 | 溯因推理的严格版是 MAP;那一章讲 MAP 怎么把先验变成正则项 |
| 18 · 经典计算机视觉 | 下一章换战场:从「不确定的知识」到「不确定的像素」 |
✅ 检查点
- 5 个布尔变量的完整联合分布有多少个自由参数?警报网络存了几个?省下来的那些去哪了?
- 写出贝叶斯网的链式法则分解式。它比一般的链式法则强在哪?为什么图必须无环?
- 手算 $P(j,m,a,\lnot b,\lnot e)$,写出五个因子。
- $P(b \mid j,m) = 0.284$ —— 两个人都打电话了,为什么被盗概率还是不到三成?
- 三种局部结构里,哪一种在「不给中间节点」时是独立的?给了之后呢?请用具体数字说明什么叫 explaining away。
- 精确推理的复杂度是什么级别?为什么还需要采样方法?
- 置信因子有哪三条硬伤?它做不到本章的哪个推理?
👀 答案
- $2^5 - 1 = \mathbf{31}$ 个;警报网只存 $1+1+4+2+2 = \mathbf{10}$ 个。省下的 21 个由图的结构推出来 —— 每条没画的边都是一句「给定父节点后这两个变量无关」的断言。
- $P(x_1,\dots,x_n) = \prod_i P(x_i \mid \mathrm{Pa}(x_i))$。一般链式法则的条件项要写全部前面的变量(长且估不出来),这里只写父节点。有环则某个变量是自己的祖先,这条乘积式没有定义。
- $0.999 \times 0.998 \times 0.001 \times 0.9 \times 0.7 = \mathbf{0.000628}$,五个因子依次是 $P(\lnot b)$、$P(\lnot e)$、$P(a\mid\lnot b,\lnot e)$、$P(j\mid a)$、$P(m\mid a)$。
- 因为先验只有 0.001。0.284 已是先验的 284 倍,但「没被盗、警报误响、两人都打来」那条路虽然概率低,却架在 99.9% 的底座上。
- 汇聚(共果,$A \to B \leftarrow C$):不给中间节点时两个原因独立,给了之后反而相关;链式和分叉正好相反。数字:$P(b\mid a) = \mathbf{0.374}$,补上「昨晚地震了」之后 $P(b\mid a,e) = \mathbf{0.0033}$,掉 114 倍 —— 地震认领了警报,盗窃的嫌疑被洗掉。
- NP-难(多树可以线性,一般图不行),所以要采样近似:拒绝采样、似然加权、吉布斯采样,样本越多越准但永远是近似。
- ① 数字不来自任何形式模型,换个专家就不一样;② $1-\prod(1-x)$ 和 $\min$ 这类组合规则没有理论依据;③ 不满足概率公理,没法边缘化。它做不出 explaining away,因为只能沿规则单向传播。
本节回顾
⚡ 走神救援
贝叶斯网 = 一张有向无环图 + 每个节点一张条件概率表。 箭头是「直接原因」。⭐ 联合分布由局部表相乘得到——链式法则加上「给定父节点后与所有非后代条件独立」,把估不出来的长条件项砍成只依赖父节点的短项。
⭐⭐ 省下的参数是被图的结构推出来的:那个警报网络里,完整联合分布要三十多个自由参数,而贝叶斯网只要十个。查表相乘就得到联合概率;反着走做诊断则要把没观测的变量枚举掉。
⭐ 诊断那个结果值得记住形状:两个邻居都打了电话,被盗的概率仍然不到三成——⚠️ 但它已经是先验的几百倍。⭐ 「仍然很小」和「涨了很多」同时成立,这正是基础率那一章的延续。
代价:精确推理是 NP-难的,枚举法随变量数指数增长,变量消元只能省一截——所以有采样类的近似方法。
⭐ 判独立认三种形状:链式和分叉都是「给了中间那个就独立」;⭐⭐ 而汇聚结构正好反过来——不给时独立,给了反而相关。 实测那个数掉了两个数量级:知道警报响了会大幅提高被盗的怀疑,而一旦又知道发生了地震,怀疑立刻塌回去——这就是「解释消除」。
两种老办法为什么输:置信因子的数字没有形式模型、组合规则没有依据、不满足概率公理,⭐ 而且它只能单向传播,做不出解释消除;溯因推理问的问题是对的,缺的是一把尺子——⭐ 在贝叶斯网里它变成了「找后验最大的那个解释」。
下一节 👉 18-经典计算机视觉.md