🏠 总目录📚 本教程 17 · 贝叶斯网络 ← →

一张有向图怎样把联合概率拆成可计算的小表?

读后可检查:把 DAG、CPT 和条件独立对应起来,再核对警报例的推理和解释掉现象。

📑 本页目录(点开跳转)

17 · 贝叶斯网络

⏱ 30 分钟 | ⭐ 31 个数压成 10 个 —— 条件独立值多少钱,可以算出来


🎯 一句话

贝叶斯网 = 一张有向无环图 + 每个节点一张条件概率表;图里没画的那些边,就是你省下来的参数。

上一章说条件独立能把指数压回线性,这一章把它画出来,顺便把账算清楚。


🧮 一、先把账摆在桌面上

5 个布尔变量的完整联合分布有 $2^5 = 32$ 行,减去「加起来等于 1」这一个约束,还剩 31 个自由参数。每多一个变量翻一倍,20 个变量就是 100 多万个数。存不下只是小麻烦,真正要命的是:这一百万个数你从哪儿估? 每一格都要求「同时满足这 5 个条件」的样本,而这种样本几乎一个都没有。

⭐ 上一章的出路是条件独立。贝叶斯网就是把「谁在给定谁之后互不相干」画成一张图 —— 图是给人看的,省下来的参数是给机器用的。


🧱 二、结构: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 打来。

P(B) = .001 P(E) = .002 B · 入室盗窃 E · 地震 A · 警报响 J · John 打来 M · Mary 打来 P(J|A)=.90 P(J|¬A)=.05 P(M|A)=.70 P(M|¬A)=.01
警报网络:两个原因汇聚到警报,再分叉出两个证据。箭头是因果方向,推理常要反着走。
节点 要存的参数 值
$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 先消 消 C 后 再消 A、B、D 叶子先消 消 A、B、D 后 再消 C ABC DQ AB DQQ ABC DQ CQQ 无填边
上下从同一张星形图出发,虚线标出新添的边。依据:Dechter §4.2。

一格对应一组取值。消元时,参与相乘的因子涉及哪些变量,就把哪些变量的取值数乘起来,得到乘积表的格数。对一个变量求和后,那一维从表里消失。下表分别统计两种顺序中最大的乘积工作区和最大的求和后因子。

顺序(从左到右)最大乘积工作区最大求和后因子
$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$ 正是汇聚:

⭐ 嫌疑从 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 · 经典计算机视觉 下一章换战场:从「不确定的知识」到「不确定的像素」

✅ 检查点

  1. 5 个布尔变量的完整联合分布有多少个自由参数?警报网络存了几个?省下来的那些去哪了?
  2. 写出贝叶斯网的链式法则分解式。它比一般的链式法则强在哪?为什么图必须无环?
  3. 手算 $P(j,m,a,\lnot b,\lnot e)$,写出五个因子。
  4. $P(b \mid j,m) = 0.284$ —— 两个人都打电话了,为什么被盗概率还是不到三成?
  5. 三种局部结构里,哪一种在「不给中间节点」时是独立的?给了之后呢?请用具体数字说明什么叫 explaining away。
  6. 精确推理的复杂度是什么级别?为什么还需要采样方法?
  7. 置信因子有哪三条硬伤?它做不到本章的哪个推理?
👀 答案
  1. $2^5 - 1 = \mathbf{31}$ 个;警报网只存 $1+1+4+2+2 = \mathbf{10}$ 个。省下的 21 个由图的结构推出来 —— 每条没画的边都是一句「给定父节点后这两个变量无关」的断言。
  2. $P(x_1,\dots,x_n) = \prod_i P(x_i \mid \mathrm{Pa}(x_i))$。一般链式法则的条件项要写全部前面的变量(长且估不出来),这里只写父节点。有环则某个变量是自己的祖先,这条乘积式没有定义。
  3. $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)$。
  4. 因为先验只有 0.001。0.284 已是先验的 284 倍,但「没被盗、警报误响、两人都打来」那条路虽然概率低,却架在 99.9% 的底座上。
  5. 汇聚(共果,$A \to B \leftarrow C$):不给中间节点时两个原因独立,给了之后反而相关;链式和分叉正好相反。数字:$P(b\mid a) = \mathbf{0.374}$,补上「昨晚地震了」之后 $P(b\mid a,e) = \mathbf{0.0033}$,掉 114 倍 —— 地震认领了警报,盗窃的嫌疑被洗掉。
  6. NP-难(多树可以线性,一般图不行),所以要采样近似:拒绝采样、似然加权、吉布斯采样,样本越多越准但永远是近似。
  7. ① 数字不来自任何形式模型,换个专家就不一样;② $1-\prod(1-x)$ 和 $\min$ 这类组合规则没有理论依据;③ 不满足概率公理,没法边缘化。它做不出 explaining away,因为只能沿规则单向传播。

本节回顾

⚡ 走神救援

贝叶斯网 = 一张有向无环图 + 每个节点一张条件概率表。 箭头是「直接原因」。⭐ 联合分布由局部表相乘得到——链式法则加上「给定父节点后与所有非后代条件独立」,把估不出来的长条件项砍成只依赖父节点的短项。

⭐⭐ 省下的参数是被图的结构推出来的:那个警报网络里,完整联合分布要三十多个自由参数,而贝叶斯网只要十个。查表相乘就得到联合概率;反着走做诊断则要把没观测的变量枚举掉。

⭐ 诊断那个结果值得记住形状:两个邻居都打了电话,被盗的概率仍然不到三成——⚠️ 但它已经是先验的几百倍。⭐ 「仍然很小」和「涨了很多」同时成立,这正是基础率那一章的延续。

代价:精确推理是 NP-难的,枚举法随变量数指数增长,变量消元只能省一截——所以有采样类的近似方法。

⭐ 判独立认三种形状:链式和分叉都是「给了中间那个就独立」;⭐⭐ 而汇聚结构正好反过来——不给时独立,给了反而相关。 实测那个数掉了两个数量级:知道警报响了会大幅提高被盗的怀疑,而一旦又知道发生了地震,怀疑立刻塌回去——这就是「解释消除」。

两种老办法为什么输:置信因子的数字没有形式模型、组合规则没有依据、不满足概率公理,⭐ 而且它只能单向传播,做不出解释消除;溯因推理问的问题是对的,缺的是一把尺子——⭐ 在贝叶斯网里它变成了「找后验最大的那个解释」。

下一节 👉 18-经典计算机视觉.md

打卡记录保存在你的浏览器里,首页能看到总进度