机器学习数学推导（十）：半朴素贝叶斯与贝叶斯网络

引子。 朴素贝叶斯假定特征在给定类别后两两独立——这是个非常方便的谎言，让我们能用一遍数据扫描就训出一个分类器，但几乎在所有 UCI 基准上，基于树结构和小型概率图的模型都能稳稳地把它再压一个百分点。这一篇沿着「依赖关系」的轴线从 0 走到 d：先看从「全独立」到「全联合」之间的三个甜蜜点——SPODE、TAN、AODE，再把这套因子分解的思路推到极致，就得到贝叶斯网络。

你将学到

• 为什么完整的条件独立假设几乎总是失败，放松它会让参数量怎样增长；
• SPODE：所有特征共享一个「超父」；
• TAN：每个特征自己挑一个父亲，挑选规则是 Chow-Liu 的最大生成树；
• AODE：对所有合格的超父做平均，去掉模型选择带来的方差；
• 贝叶斯网络：DAG 因子分解、d-分离、马尔可夫毯、变量消除、联合树；
• 实战决策表：什么时候用 NB、TAN、AODE 还是完整 BN。

预备知识

• 联合分布、条件独立、互信息；
• 生成树、树上的动态规划；
• 熟悉 第 9 篇：朴素贝叶斯 。

1. 为什么要放松独立性？

1.1 那个「方便的谎言」

朴素贝叶斯的因子分解是

它假定一旦类别给定，特征之间就互不相关。这个假定几乎在每一类真实数据上都会失效：

• 文本。 即使限定在「机器学习文章」这一类内，二元组「machine learning」的频率也远远高于 $P(\text{machine})\,P(\text{learning})$ 给出的预测；
• 医学。 在「流感」病例中，发热 与 咳嗽 仍然高度相关——它们共享同一条下游生理通路；
• 图像。 不论类别为何，相邻像素几乎总是相似。

当条件独立被严重违反时，后验 $P(c\mid\mathbf{x})$ 会严重过自信：胜出的类别仍然能胜出，但置信度被吹得过高，相邻候选类之间的相对排序也会乱。

1.2 模型谱

其中 $S$ 是平均特征取值数，$K$ 是类别数。经验上的甜蜜点是 $k=1$：相比朴素贝叶斯只多付一个 $S$ 倍的代价，准确率却能拿到这一系列阶梯里最大的一档跳跃。

2. 单依赖估计（ODE）

2.1 SPODE：用一个共享的超父

挑一个特征 $x^{(p)}$ 作为「超父」，让所有其他特征同时依赖于类别和它：

怎么读这个模型。 朴素贝叶斯说「给定类别，所有特征互不相关」；SPODE 改口说「给定类别后，还有一个隐性的中间变量影响所有特征」。比如在垃圾邮件识别里，这个中间变量可能就是 free 这个词——它出不出现，会同时影响 click、offer、winner 这些词的概率。

带拉普拉斯平滑的极大似然估计。

怎么挑超父。 两个常见准则：

前者挑「跟 $Y$ 关系最紧」的特征，后者挑「条件化它之后能最大化解释其余特征」的那个。两个都是启发式——之所以后面要发明 AODE 和 TAN，恰恰因为这一步选择是脆弱的。

2.2 AODE：把所有合格超父都平均掉

思路。 既然挑哪个超父都不踏实，干脆把所有支撑量足够的超父对应的 SPODE 都加起来：

其中 $n_i$ 是训练集中取值 $x^{(i)}$ 出现的样本数，阈值 $m$（典型取 30）用来过滤掉支撑过少、估计不可靠的超父。

它好在哪。

1. 不需要做结构搜索。 模型固定，只需要数 counter；
2. 降方差。 把 $d$ 个高度相关的 SPODE 求平均，作用类似 bagging；
3. 实现极其简单。 跟 SPODE 完全相同的统计量，再对 $i$ 求一次和。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import numpy as np
from sklearn.naive_bayes import BernoulliNB
from sklearn.model_selection import cross_val_score

# 三个二值特征，给定类别后 x1、x2 都依赖 x0，因此 NB 的独立性假设被破坏
np.random.seed(42)
N = 500
y  = np.random.binomial(1, 0.5, N)
x0 = np.random.binomial(1, 0.8 * y + 0.2 * (1 - y), N)
x1 = np.random.binomial(1, 0.7 * x0 + 0.1 * (1 - x0), N)  # 依赖 x0
x2 = np.random.binomial(1, 0.6 * x0 + 0.2 * (1 - x0), N)  # 依赖 x0
X  = np.column_stack([x0, x1, x2])

print("Naive Bayes 5 折 CV:",
      cross_val_score(BernoulliNB(), X, y, cv=5).mean().round(4))
# 在这种数据上 AODE 通常会稳稳地高出 NB 几个百分点。

3. TAN：树增广朴素贝叶斯

3.1 每个特征自己挑爸爸

SPODE 强迫所有特征共享同一个超父，TAN 则放宽一点：让每个特征自己挑一个额外的父亲——所有这些选择必须形成一棵树：

其中 $\pi_j$ 是特征 $j$ 在增广树中的唯一父亲（树根没有父亲，相应那一项退化为 $P(x^{(j)}\mid c_k)$）。

3.2 用 Chow-Liu 学这棵树

定理（Chow & Liu 1968；Friedman, Geiger, Goldszmidt 1997）。 在所有树结构的增广方案中，最大化条件似然的那个，等价于以条件互信息为权重的最大生成树：

这个权重在度量什么？ 度量的是「类别已经解释完之后，$X^{(j)}$ 与 $X^{(k)}$ 之间残留的相关性」。权重大的边，就是最值得我们花参数去建模的依赖。

算法。

1. 在 $d$ 个特征上建完全图；
2. 把边 $(j,k)$ 的权重设为 $I(X^{(j)};X^{(k)}\mid Y)$；
3. 用 Kruskal 或 Prim 求最大生成树，复杂度 $O(d^{2}\log d)$；
4. 选根（常用 $\arg\max_j I(X^{(j)};Y)$）；
5. 从根开始把无向树定向为有向树。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import numpy as np
from itertools import combinations

def conditional_mutual_info(X, y, j, k):
    """从数据计算 I(X_j ; X_k | Y)，自然对数。"""
    cmi = 0.0
    for c in np.unique(y):
        mask = (y == c); p_c = mask.mean()
        Xc = X[mask]
        for vj in np.unique(X[:, j]):
            for vk in np.unique(X[:, k]):
                p_jk = ((Xc[:, j] == vj) & (Xc[:, k] == vk)).mean()
                p_j  = (Xc[:, j] == vj).mean()
                p_k  = (Xc[:, k] == vk).mean()
                if min(p_jk, p_j, p_k) > 0:
                    cmi += p_c * p_jk * np.log(p_jk / (p_j * p_k))
    return cmi

在前面那个合成数据上，依赖对 $(x_0,x_1)$ 的 CMI 会显著大于独立对 $(x_0,x_2)$，而这正是 Kruskal 会优先连接的边。

4. 贝叶斯网络

NB 与 TAN 都是某个更一般对象的特例：贝叶斯网络。下面把镜头拉远，看看图模型的全貌。

4.1 DAG 因子分解

贝叶斯网络 是一个有向无环图 $\mathcal{G}=(V,E)$，每个节点配一张条件概率表（CPT）。联合分布按图的结构分解为

因子分解的价值。 上图四个二值变量，全联合需要 $2^4-1=15$ 个自由参数；分解后只需要 $1+2+2+4=9$ 个。把规模放大到 $n=20$、平均父节点数 3：全联合表有 $\approx 10^{6}$ 项，而分解形式只需要 $\sim 20\cdot 2^{3}=160$。

我们其实已经见过两种特例：

• 朴素贝叶斯：$Y$ 是星形结构的中心，所有 $X_j$ 之间无边；
• TAN：在星形之上再加一棵特征间的树。

4.2 d-分离

DAG 中的条件独立性由一个图形化准则d-分离完全决定。任何复杂情形都能拆成下面三种基本结构：

• 链 $A\to B\to C$。 不观测 $B$ 时 $A\not\!\perp C$；条件化 $B$ 后路径被阻断，$A\perp C\mid B$。
• 叉 $A\leftarrow B\to C$。 行为同链：共因 $B$ 制造了 $A,C$ 的相关，观测它就消去这个相关。
• 对撞 $A\to B\leftarrow C$。 行为反向。不观测 $B$ 时 $A\perp C$；一旦观测了 $B$，原本独立的两个原因被「耦合」起来——这就是著名的 explaining away（因因相消）。

判定规则：路径上若有任意一个 chain/fork 节点被观测，路径就被阻断；反之，路径上若有任何对撞节点既没被观测，其后代也未被观测，这条路径同样阻断。两个集合在给定 $Z$ 时被 d-分离，当且仅当它们之间所有路径都被 $Z$ 阻断。

4.3 马尔可夫毯

马尔可夫毯 $\mathrm{MB}(X)$ 是使得「给定它之后 $X$ 与外界条件独立」的最小集合。在贝叶斯网络中，它正好是

那些「co-parent（孩子的另一个父亲）」特别容易被忽略，但缺一不可——根据对撞规则，条件化一个孩子会激活穿过它通向其它父亲的路径。马尔可夫毯也是 Gibbs 采样里采样 $X$ 时唯一需要看的变量集合，从因果视角看就是「用网络其余部分预测 $X$ 所需的最小充分统计量」。

4.4 推断：变量消除

要算诸如 $P(D\mid \text{evidence})$ 之类的后验，暴力求和是 $n$ 的指数。变量消除 一次只消去一个变量，并复用中间因子：

1. 选定消除顺序，例如查询 $D$ 时按 $A,B,C$ 顺序；
2. 把所有含 $A$ 的因子相乘后对 $A$ 求和，得到新因子 $\tau_1(B)$；
3. 重复：含 $B$ 的因子相乘并求和得 $\tau_2(C)$，依此类推。

链结构下复杂度从 $O(S^{n})$ 降到 $O(nS^{2})$；一般图上的复杂度由图的树宽控制——也就是消除过程中产生的最大中间因子的大小。这就是为什么稠密图即使做了消除依然难算。

4.5 联合树

联合树算法把变量消除「全局化」，让所有边缘分布都能通过两次消息传递得到：

1. 道德化（moralise）： 在每对 co-parent 之间补无向边，再去掉所有箭头方向；
2. 三角化（triangulate）： 添加弦边，使所有长度 $\geq 4$ 的圈都至少有一条弦。这一步控制树宽，最优三角化是 NP-hard，实践中用 minimum fill-in 等启发式；
3. 抽出极大团；
4. 构造团树，相邻团共享一个 separator 集，并满足 running-intersection 性质：任何变量出现的团构成一个连通子树；
5. 沿树传消息（先 collect 后 distribute）。两轮之后每个团都持有自己变量上的正确边缘。

总开销与最大团大小（即树宽 + 1）成指数关系——和变量消除同阶，但所有查询共享一次预计算。

4.6 结构学习

DAG 本身也可以从数据学。两大流派：

• 打分 + 搜索。 在 DAG 空间上爬山（增/删/反一条边），用「似然 + 罚项」的打分函数评价候选。最经典的是 BIC：

第一项奖励拟合，第二项惩罚参数量；BIC 在标准假设下是相合的（$N\to\infty$ 时收敛到真实图）。

• 基于约束 （PC、FCI 算法）。先做条件独立性检验得到骨架，再用对撞规则对 v 形结构定向。

一个硬事实：精确的结构学习是 NP-hard 的（Chickering, Heckerman & Meek 2004）。实践中所有算法都需要限制每个节点的最大父节点数、加随机重启、或者借助先验把某些边的方向钉死。

5. 习题

习题 1 —— SPODE 参数估计

100 个样本，类别 $c_1$ 有 60 个；其中 $x^{(p)}{=}1$ 的有 30 个，再其中 $x^{(j)}{=}1$ 的有 18 个。取拉普拉斯平滑 $\alpha=1$，$|x^{(j)}|=3$：

习题 2 —— TAN 参数计数

二值特征 + $K$ 类：

• 朴素贝叶斯：每个 (类, 特征) 对 1 个参数，共 $K\cdot d$；
• TAN：每个非根特征还要再多一个二值父亲，因此 (类, 特征) 对要存 2 项，共 $2Kd$。

TAN 把参数预算翻倍，换来对成对依赖的建模能力。若特征是 $S$ 元的，倍数从 2 变为 $S$。

习题 3 —— Chow-Liu 选边

设 $I(X_1;X_2\mid Y)=0.8$，$I(X_1;X_3\mid Y)=0.5$。最大生成树先选权重大的，因此 $X_1\!-\!X_2$ 先入树，$X_1\!-\!X_3$ 只有在不构成圈时才会被加进来。

习题 4 —— d-分离

在 $A\to C\leftarrow B$ 中：

• (a) $A\perp B$？是。 $C$ 是对撞节点，未观测时阻断路径；
• (b) $A\perp B\mid D$（$D$ 与 ABC 无关）？是。 $D$ 不是 $C$ 的后代，对撞节点仍处于阻断状态；
• (c) $A\perp B\mid C$？否。 条件化对撞节点会激活路径，explaining away 把 $A,B$ 耦合起来。

习题 5 —— 数据稀少时 AODE 还是 TAN

• $d$ 大、数据多：TAN 的 $O(d)$ 预测速度优于 AODE 的 $O(d^{2})$；
• $N$ 小：AODE 的平均效应天然有正则，往往比 TAN 鲁棒——TAN 在这种情形下从噪声 CMI 估计里学出的 MST 边可能本身就是过拟合。

实战默认策略：先上 AODE；当 $N$ 远超 CMI 表所需的格子数时，再切到 TAN。

Q&A

为什么不直接学一个完整的贝叶斯网络？

结构学习是 NP-hard 的，DAG 空间是超指数的。TAN、AODE 通过限制结构（树形/平均超父）让学习变得可行，同时仍能抓住最重要的依赖。

有向边等于因果吗？

不是。同一个条件独立结构可以由多个 DAG 表达（叫等价类），它们在统计上无法区分。要做因果推断需要额外的干预性假设——Pearl 的 do-演算、工具变量等。

TAN 怎么处理连续特征？

三种常见做法：(i) 离散化（等宽/等频/基于熵的离散化）；(ii) 假定条件高斯（条件高斯贝叶斯网络）；(iii) 用核密度估计本地条件分布。

AODE 还是 TAN？

AODE 更简单、小样本更稳、不需要结构学习；TAN 在 $d$ 很大时预测更快、能为不同特征选不同的父亲。文本分类里 AODE 是更常见的默认；稠密数值表上 TAN 通常更胜。

深度生成模型与之有什么关系？

现代隐变量模型（VAE、流模型、PixelCNN 之类的自回归模型）本质上就是连续型贝叶斯网络，只是把 CPT 换成神经条件密度。因子分解的思想完全相同，变化的只是 $P(X_i\mid \mathrm{Pa}(X_i))$ 的参数化方式。

参考文献

• Friedman, N., Geiger, D. & Goldszmidt, M. (1997). Bayesian network classifiers. Machine Learning, 29(2-3), 131-163.
• Webb, G. I., Boughton, J. R. & Wang, Z. (2005). Not so naive Bayes: Aggregating one-dependence estimators. Machine Learning, 58(1), 5-24.
• Chow, C. & Liu, C. (1968). Approximating discrete probability distributions with dependence trees. IEEE Transactions on Information Theory, 14(3), 462-467.
• Chickering, D. M., Heckerman, D. & Meek, C. (2004). Large-sample learning of Bayesian networks is NP-hard. JMLR, 5, 1287-1330.
• Koller, D. & Friedman, N. (2009). Probabilistic Graphical Models: Principles and Techniques. MIT Press.
• Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann.

系列导航