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

引子： 朴素贝叶斯假设所有特征在给定类别下条件独立。这是一种便于计算的“善意谎言”——它让我们只需遍历一遍数据就能完成训练，但几乎所有 UCI 基准测试都表明，基于树结构或小型图的分类器总能稳定高出几个百分点的准确率。本文将沿着从“无依赖”（朴素贝叶斯）到“全依赖”（完整联合分布）的连续谱系，重点介绍实践中真正常用的三个甜点模型：SPODE、TAN 和 AODE。而将这种因子分解思想推广至一般形式，就得到了贝叶斯网络。

你将学到什么#

为何完全条件独立假设会失效，以及放松该假设时参数数量如何增长。
SPODE：所有特征共享一个“超父”节点。
TAN：每个特征拥有自己的父节点，通过条件互信息构建的最大生成树（Chow-Liu 算法）来选择。
AODE：对所有符合条件的超父取平均，以消除模型选择带来的方差。
贝叶斯网络：DAG 因子分解、d-分离、马尔可夫毯、变量消除与联合树算法。
实用决策准则：何时选用 NB、TAN、AODE 或完整 BN。

前置知识#

联合分布、条件独立性、互信息
生成树、树上的动态规划
已掌握第 9 篇：朴素贝叶斯

为什么要放松独立性假设？#

那个“便利的谎言”#

P(\mathbf{x}\mid c_k) \;=\; \prod_{j=1}^{d} P(x^{(j)}\mid c_k).

这个“谎言”在于：给定类别后，各特征彼此无关。然而在现实中，这一假设几乎总会被打破，典型场景包括：

文本处理：即使限定在“机器学习文章”这一类别中，“machine learning”这个二元组的出现频率也远高于 $P(\text{machine})\,P(\text{learning})$ 的乘积预测值。
医学诊断：在“流感”类别下，“发热”与“咳嗽”依然高度相关——它们共享同一条下游生理通路。
计算机视觉：无论图像属于哪一类，相邻像素的值通常都非常接近。

当条件独立性假设被严重违反时，后验概率 $P(c\mid\mathbf{x})$ 会出现校准偏差：虽然最终胜出的类别通常仍是正确的，但其置信度会被严重高估，且相近候选类别的排序也会显著退化。

模型谱系#

模型	允许的依赖关系	参数量	准确率
朴素贝叶斯	无	$$O(K d)$$	基线
一阶依赖（SPODE / TAN / AODE）	每个特征最多有一个父节点	$$O(K d S)$$	更优
$$k$$ -依赖	每个特征最多有 $$k$$ 个父节点	$O(K d S^{k})$	再优
完整联合分布	所有可能依赖	$O(K S^{d})$	最优，但不可行

其中 $$S$$ 是特征的平均取值数， $$K$$ 为类别数。经验表明， $$k=1$$ 是最佳平衡点：参数量仅增加一个 $$S$$ 因子，却能带来相比朴素贝叶斯最显著的准确率提升。

一阶依赖估计器（ODE）#

SPODE：单一超父节点#

P(\mathbf{x}\mid c_k) \;=\; P(x^{(p)}\mid c_k)\prod_{j eq p} P(x^{(j)}\mid c_k,\,x^{(p)}).

模型解读：朴素贝叶斯认为“给定类别后所有特征独立”，而 SPODE 则认为“除类别外，还有一个共同的调节变量影响所有特征”。例如在垃圾邮件检测中，这个调节变量可能是词 free：一旦知道 free 是否出现，click、offer、winner 等词的概率就会随之改变。

\hat{P}(x^{(j)}{=}v\mid c_k,\,x^{(p)}{=}u) \;=\; \frac{\#\{x^{(j)}{=}v,\,c_k,\,x^{(p)}{=}u\}+\alpha} {\#\{c_k,\,x^{(p)}{=}u\}+\alpha\,S_j}.

p^{*} \;=\; \arg\max_{p}\, I(X^{(p)};Y), \qquad p^{*} \;=\; \arg\max_{p}\,\sum_{j eq p} I(X^{(j)};Y\mid X^{(p)}).

前者选择与类别 $$Y$$ 最相关的特征；后者选择能最大程度解释其他特征的条件变量。这两种方法均为启发式——正因单一超父的选择过于脆弱，才催生了后续的 AODE 和 TAN。

AODE：对所有合格超父取平均#

\hat{P}(c_k\mid\mathbf{x})\;\propto\; \sum_{i:\;n_i\geq m} P(c_k)\,P(x^{(i)}\mid c_k)\prod_{j eq i} P(x^{(j)}\mid c_k,\,x^{(i)}).

其中 $$n_i$$ 是训练集中特征 $x^{(i)}$ 的出现次数， $$m$$ （通常取 30）是超父可信所需的最小支撑阈值。

为何有效？

无需结构搜索：模型结构固定，仅需统计频次。
方差缩减：对 $$d$$ 个相关的 SPODE 估计取平均，效果类似于 bagging。
易于部署：只需复用 SPODE 的计数器，并对所有 $$i$$ 求和即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
import numpy as np
from sklearn.naive_bayes import BernoulliNB
from sklearn.model_selection import cross_val_score

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))

TAN：树增广朴素贝叶斯#

每个特征自选父节点#

P(\mathbf{x}\mid c_k) \;=\; \prod_{j=1}^{d} P(x^{(j)}\mid c_k,\,x^{(\pi_j)}),

其中 $\pi_j$ 是特征 $$j$$ 在增广树中的父节点（根节点无父，对应项退化为 $P(x^{(j)}\mid c_k)$ ）。

树的学习——Chow-Liu 算法#

w_{jk} \;=\; I(X^{(j)};X^{(k)}\mid Y) \;=\; \sum_{y,x_j,x_k} P(x_j,x_k,y)\, \log\frac{P(x_j,x_k\mid y)}{P(x_j\mid y)\,P(x_k\mid y)}.

权重含义： $I(X^{(j)};X^{(k)}\mid Y)$ 衡量的是类别 $$Y$$ 未能解释的 $X^{(j)}$ 与 $X^{(k)}$ 之间的残余相关性。权重越高的边，越值得建模。

算法步骤：

在 $$d$$ 个特征上构建完全图；
将边 $$(j,k)$$ 的权重设为 $I(X^{(j)};X^{(k)}\mid Y)$ ；
使用 Kruskal 或 Prim 算法求最大生成树，复杂度为 $O(d^{2}\log d)$ ；
选定根节点（通常取 $\arg\max_j I(X^{(j)};Y)$ ）；
将无向树从根向外定向。

 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 算法正是利用这一差异优先连接高权重边。

贝叶斯网络#

朴素贝叶斯和 TAN 都是更一般模型——贝叶斯网络的特例。现在我们将其置于完整的图模型框架中审视。

DAG 因子分解#

四变量示例网络：Cloudy / Sprinkler / Rain / WetGrass

P(X_1,\dots,X_n) \;=\; \prod_{i=1}^{n} P\bigl(X_i\mid \mathrm{Pa}(X_i)\bigr).

为何分解重要？ 对于四个二值变量，完整联合分布需 $$2^4 - 1 = 15$$ 个自由参数，而按图分解仅需 $$1+2+2+4 = 9$$ 个。若扩展至 $$n=20$$ 个二值变量，且平均每个节点有 3 个父节点，则联合分布约含 $$10^6$$ 项，而分解形式仅需约 $20 \cdot 2^3 = 160$ 项。

我们已见过的特例：

朴素贝叶斯：星形图， $$Y$$ 为所有 $$X_j$$ 的父节点， $$X_j$$ 间无边；
TAN：星形图基础上，在 $$X_j$$ 上再叠加一棵树。

d-分离#

DAG 中的条件独立性由d-分离这一图形准则判定。所有情形均可归结为以下三种基本结构：

链 $A\to B\to C$ ：若 $$B$$ 未观测，则 $Aot\!\perp C$ ；若条件化 $$B$$ ，路径被阻断， $A\perp C\mid B$ 。
叉 $A\leftarrow B\to C$ ：行为与链相同：共同原因使 $$A,C$$ 相关，观测后相关性消失。
对撞 $A\to B\leftarrow C$ ：行为相反。若 $$B$$ 未观测，则 $A\perp C$ ；一旦观测 $$B$$ ，路径被激活，两个原因相互耦合——即著名的explaining-away（因因相消）效应。

一条路径被阻断，当且仅当：路径上存在一个链或叉节点被观测，或存在一个对撞节点未被观测（且其所有后代也未被观测）。两组变量在给定 $$Z$$ 下 d-分离，当且仅当它们之间的所有路径均被 $$Z$$ 阻断。这是图模型中所有条件独立性断言的理论基础。

马尔可夫毯#

\mathrm{MB}(X) \;=\; \mathrm{Pa}(X)\;\cup\;\mathrm{Ch}(X)\;\cup\;\bigl\{\text{X 的子节点的其他父节点}\bigr\}.

这些“共父节点”常被忽略，却至关重要——根据对撞规则，条件化一个子节点会激活通往其其他父节点的路径。马尔可夫毯也是 Gibbs 采样中重采样 $$X$$ 所需的最小变量集；从因果角度看，它是用网络其余部分预测 $$X$$ 的最小充分统计量。

推断：变量消除#

直接计算后验如 $P(D\mid \text{evidence})$ 需指数级求和。变量消除通过逐个消去变量并复用中间因子来降低复杂度：

选定消元顺序（如查询 $$D$$ 时按 $$A,B,C$$ ）；
将所有含 $$A$$ 的因子相乘后对 $$A$$ 求和，得到新因子 $\tau_1(B)$ ；
重复：合并含 $$B$$ 的因子并求和得 $\tau_2(C)$ ，依此类推。

对链结构，复杂度从 $$O(S^n)$$ 降至 $$O(nS^2)$$ ；对一般图，复杂度由树宽决定——即消元过程中产生的最大中间因子的大小。这也解释了为何稠密图即便使用消除法仍难以处理。

联合树#

联合树算法将变量消除全局化，使所有边缘分布可通过两次消息传递计算：

道德化：为每对共父节点添加无向边，然后忽略方向；
三角化：添加弦边，使所有长度 $\geq 4$ 的环均有弦。此步控制树宽，最优三角化为 NP-hard，实践中常用 minimum fill-in 等启发式；
提取极大团；
构建团树：相邻团共享 separator 集，并满足 running-intersection 性质（任一变量出现的团构成连通子树）；
消息传递：先 collect 后 distribute。两轮后，每个团持有其变量的正确边缘分布。

总代价随最大团大小（即树宽 $$+1$$ ）指数增长——与变量消除复杂度一致，但可摊销至所有查询。

结构学习#

DAG 本身也可从数据中学习，主要有两类方法：

评分 + 搜索：在 DAG 空间中爬山（增/删/反转边），用似然加罚项的评分函数评估。经典评分如 BIC：

\mathrm{BIC}(\mathcal{G}) \;=\; \log p(\mathcal{D}\mid\hat{\theta},\mathcal{G}) \;-\; \tfrac{|\theta|}{2}\log N.

第一项奖励拟合度，第二项惩罚参数量；BIC 在标准假设下具有一致性（ $N\to\infty$ 时收敛至真实图）。

基于约束（PC、FCI 算法）：通过条件独立性检验构建骨架，再用对撞规则定向 v-结构。

一个硬事实：精确结构学习是 NP-hard 的（Chickering, Heckerman & Meek 2004）。实用算法通常限制每节点最大父数、使用随机重启，或引入先验知识固定某些边方向。

贝叶斯网络的推断复杂度#

结构分解 $P(\mathbf{x}) = \prod_i P(x_i \mid \mathrm{pa}(x_i))$ 节省了存储空间，但推断（即计算 $P(X_q \mid \mathbf{x}_e)$ ）通常是 #P-hard 的。复杂度取决于网络沿消元顺序的分解质量。

\phi'(\mathbf{Y}) = \sum_{x_k} \prod_{f \in \mathcal{F}_k} f(x_k, \mathbf{Y}).

单步成本随 width（即 $\mathbf{Y} \cup \{x_k\}$ 的最大规模）指数增长。最优消元顺序对应最小 induced treewidth，但寻找该顺序本身是 NP-hard 的。实践中，min-fill 或 min-neighbour 启发式在数百节点网络上表现良好。

对树状网络（道德图无环），树宽为 1，精确推断复杂度为 $O(N \cdot K^2)$ （ $$N$$ 个 $$K$$ 元变量）——这正是 HMM 前向-后向算法的复杂度（HMM 是链式特例）。但在全连接医疗诊断 BN 等稠密网络中，树宽随 $$N$$ 线性增长，当 $N \approx 30$ 时，精确推断已不可行。

近似替代方案：当树宽过大时，常用 loopy belief propagation（在含环图上直接运行 BP，期望收敛；实证有效但无理论保证）、Gibbs 采样（轮流从条件分布采样各变量），以及变分方法（见第 14 篇）。对树宽为 25 的二值稠密 BN，单条 Gibbs 链运行 10 万样本通常可获得边缘概率的 2–3 位有效精度——虽慢，但至少可行。

结构学习：真正的难点所在#

给定结构 $$G$$ ，条件概率表的 MLE 极其简单——只需计数再归一化。真正的挑战在于从数据中学习 $$G$$ 本身。主流方法有两类。

\mathrm{BIC}(G, \mathcal{D}) = \log P(\mathcal{D} \mid \hat\theta_G, G) - \frac{|\theta_G|}{2}\log N,

以及 BDeu（均匀 Dirichlet 先验下的边缘似然）。二者均可分解——评分可按局部结构 $(x_i, \mathrm{pa}(x_i))$ 分解，故局部边变更仅需重评受影响部分。即便如此， $$n$$ 节点的 DAG 空间规模为超指数级（ $\sim n! \cdot 2^{\binom{n}{2}}$ ），因此搜索多为贪心策略：如带随机重启的爬山法、禁忌搜索，或对小规模问题（ $n \lesssim 25$ ）使用 Silander-Myllymäki 的动态规划精确算法。

基于约束的搜索：通过条件独立性检验定向边。PC 算法从完全图出发，若找到分离集 $\mathbf{Z}$ 使 $X \perp Y \mid \mathbf{Z}$ ，则删除边 $$(X,Y)$$ ；再用 Meek 规则定向对撞结构。该方法理论更清晰（在忠实性假设下可恢复马尔可夫等价类），但对有限样本下条件独立性检验的 I 类错误极为敏感。笔者仅在玩具数据上见其有效；在真实噪声数据中，基于评分的爬山法通常更优。

重审 TAN 的优势：TAN 将结构限制为以类别为根的树增广形式，该问题可通过 Chow-Liu 算法精确求解——基于条件互信息的最大权生成树可在 $$O(n^2 N)$$ 时间内构建。这正是 TAN 成为实践折衷方案的原因：它几乎保留了朴素贝叶斯的鲁棒性，又具备接近完整 BN 的表达能力，且结构学习具有多项式复杂度。

练习题#

练习 1 — SPODE 参数估计#

\hat{P}\bigl(x^{(j)}{=}1\mid c_1, x^{(p)}{=}1\bigr) \;=\; \frac{18+1}{30+1\cdot 3} \;=\; \frac{19}{33} \;\approx\; 0.576.

练习 2 — TAN 参数量#

对二值特征、 $$K$$ 个类别：

朴素贝叶斯： $K \cdot d$ 个参数（每类每特征一项）；
TAN：每个非根特征依赖类别和一个二值父节点，故每类每特征需 2 项，总计 $$2Kd$$ 。

TAN 将参数预算翻倍，换取对成对依赖的建模能力。若特征为 $$S$$ 元，则倍数变为 $$S$$ 。

练习 3 — Chow-Liu 边选择#

设 $I(X_1;X_2\mid Y)=0.8$ ， $I(X_1;X_3\mid Y)=0.5$ 。Chow-Liu 最大生成树优先选择权重更大的边，故 $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$$ 无关）？是。 $$D$$ 非 $$C$$ 后代，对撞仍阻断。
(c) $A\perp B\mid C$ ？否。条件化对撞节点激活路径，导致 $$A$$ 与 $$B$$ 耦合。

练习 5 — 小样本下 AODE vs TAN#

大 $$d$$ 、充足数据：TAN 预测复杂度 $$O(d)$$ 优于 AODE 的 $$O(d^2)$$ ；
小 $$N$$ ：AODE 的平均操作具正则化效果，通常比 TAN 更稳健——后者易因噪声 CMI 估计导致 MST 边过拟合。

合理默认策略：先用 AODE；当样本量 $$N$$ 显著超过需估计的 CMI 格子数时，再切换至 TAN。

常见问题#

为何不总用完整贝叶斯网络？#

结构学习是 NP-hard 问题，DAG 搜索空间为超指数级。TAN 和 AODE 通过约束结构（如树形或平均超父）使学习可行，同时捕获最关键依赖。

有向边是否表示因果？#

否。多个 DAG 可编码相同的条件独立结构（即等价类），在统计上不可区分。因果推断需干预或反事实假设——如 Pearl 的 do-演算或工具变量。

TAN 如何处理连续特征？#

三种方案：(i) 离散化（等宽/等频分箱）；(ii) 假设条件高斯分布（条件高斯贝叶斯网络）；(iii) 用核密度估计局部 CPD。

AODE 还是 TAN？#

AODE 更简单，小样本更稳健，无需结构学习；TAN 在高维下预测更快，允许异构父选择。文本分类中 AODE 更常用；稠密数值表中 TAN 往往更优。

深度生成模型与此有何关联？#

现代隐变量模型（如 VAE、标准化流、PixelCNN 等自回归模型）本质是连续贝叶斯网络，仅将 CPT 替换为神经条件密度。因子分解思想完全一致，变化的只是 $P(X_i\mid \mathrm{Pa}(X_i))$ 的参数化形式。

下一步#

贝叶斯网络让我可以显式画出变量之间的依赖结构，但它也暴露了一个新问题：单个模型再准，也可能因为数据噪声、初始化、特征采样的偶然性而方差很大。下一章我换一个完全不同的解题思路——集成学习。

集成的核心赌注是：与其把一个模型调到极致，不如训练一群"基学习器"，然后通过投票（Bagging）或加权（Boosting）把它们的错误抵消掉。Bagging 通过重采样降低方差，随机森林进一步通过特征子采样去相关；Boosting 把弱学习器按梯度方向逐个叠加，把偏差吃掉。这两条路线都建立在一个共同的代数事实上——加权平均的方差受相关性 $\rho$ 控制——理解这一点，比记住具体算法重要得多。

参考文献#

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.