机器学习数学推导（十）半朴素贝叶斯与贝叶斯网络
Chen Kai BOSS
  2021-10-18 16:00:00 2021-10-18 16:00      4.2k 字  18 分钟  

朴素贝叶斯的条件独立假设过于严格，现实中特征往往存在复杂依赖关系。如何在保持计算效率的同时，放松独立性假设，学习更准确的概率模型？半朴素贝叶斯(Semi-Naive Bayes)给出了优雅的答案——通过引入受限的属性依赖，在模型复杂度与表达能力间取得平衡。本章将深入推导 SPODE 、 TAN 、 AODE 等半朴素贝叶斯模型，并初探贝叶斯网络的结构学习与参数估计。

属性依赖与独立性放松

朴素贝叶斯的局限

条件独立假设：

$$

P( Y=c_k) = _{j=1}^d P(x^{(j)} Y=c_k) $$

问题：现实中特征往往相关，如： - 文本："机器"和"学习"经常共现 - 医疗："发热"和"咳嗽"在流感诊断中相关 - 图像：相邻像素高度相关

后果：条件独立假设被严重违反时，后验概率估计偏差大，分类性能下降。

独立性放松策略

全联合分布：不假设任何独立性

$$

P( Y=c_k) = P(x^{(1)}, , x^{(d)} Y=c_k) $$

参数量：（ 是特征 的取值数），对于高维数据不可行。

半朴素贝叶斯：引入受限的依赖关系，在表达能力与计算复杂度间权衡。

核心思想：假设每个属性最多依赖于少数其他属性（如父节点、兄弟节点）。

单依赖估计（ ODE）

SPODE：超父单依赖估计

假设：所有属性依赖于类别 和同一个超父属性：

$$

P( Y=c_k) = P(x^{(p)} Y=c_k) _{j p} P(x^{(j)} Y=c_k, x^{(p)}) $$

图模型表示： - 是根节点 - 超父属性 连接 - 其余属性 连接 和

参数估计：

$ $

其中 表示类别 中 的样本数。

拉普拉斯平滑：

$

下图展示了条件概率表的具体示例，说明如何存储和查询 SPODE 模型中的条件概率参数：

超父选择： 1. 互信息准则：选择与 互信息最大的属性

$$

p^{*} = _{p} I(X^{(p)}; Y)

  1. 条件互信息准则：选择使其余属性与 条件互信息和最大的属性

$$

p^{*} = {p} {j p} I(X^{(j)}; Y X^{(p)}) $$

优势：捕获单属性与其他属性的依赖，参数量（ 是平均取值数），仍可高效估计。

AODE：平均单依赖估计

思想：不选择单一超父，而是对所有可能的超父 SPODE 模型平均，减少选择偏差。

模型：

$$

P(Y=c_k ) P(Y=c_k) {i: n_i m} P(x^{(i)} Y=c_k) {j i} P(x^{(j)} Y=c_k, x^{(i)}) $$

其中 是属性 出现的样本数， 是最小样本阈值（如），用于过滤稀少属性。

分类规则：

$$

y = {c_k} P(Y=c_k) {i: n_i m} P(x^{(i)} Y=c_k) _{j i} P(x^{(j)} Y=c_k, x^{(i)}) $$

优势： 1. 无需特征选择：自动平均多个模型，鲁棒性强 2. 性能稳定：通常优于单一 SPODE 和朴素贝叶斯 3. 易于实现：参数估计与 SPODE 相同

计算复杂度： - 训练：（需统计所有属性对的联合频率） - 预测：（枚举 个超父，每个计算）

TAN：树增广朴素贝叶斯

最大带权生成树

思想：用树结构表示属性间依赖，既放松独立性，又保持推理效率。

模型结构： - 类别 是所有属性的父节点 - 属性间形成有向树（每个属性最多一个父属性）

$$

P( Y=c_k) = _{j=1}^d P(x^{(j)} Y=c_k, x^{(_j)}) $$

其中 是 的父属性（若 是根，则无父节点）。

条件互信息与树学习

目标：最大化树结构的条件似然

$

等价问题：最大化属性间的条件互信息和

$

条件互信息：

$$

I(X^{(j)}; X^{(k)} Y) = _{y, x_j, x_k} P(x_j, x_k, y) $$

算法（ Chow-Liu 算法）： 1. 构造完全图：节点为所有属性 2. 计算边权：每条边 的权重为 3. 最大生成树：用 Kruskal 或 Prim 算法求最大带权生成树 4. 选择根节点：任选一个属性作为根（通常选互信息 最大的） 5. 定向：从根节点开始，将无向树转为有向树

参数估计

对于每个类别，独立学习一棵树。

边缘概率（根节点或叶节点）：

$

条件概率（有父节点）：

$

TAN 的理论保证

定理（ Friedman et al., 1997）：对于给定的树结构约束， TAN 是最大似然估计。

优势： - 表达能力强于朴素贝叶斯（允许树状依赖） - 结构学习高效（） - 推理高效（树结构保证 复杂度）

局限： - 树结构限制（不能表达环状依赖） - 每个类别独立学习树（树结构可能不一致）

贝叶斯网络初步

有向无环图与条件独立

贝叶斯网络（ Bayesian Network, BN）是一个有向无环图（ DAG） = (V, E)，其中：节点V = {X_1, , X_d, Y} 表示随机变量有向边E $ 表示条件依赖关系

联合分布分解：

$$

P(X_1, , X_d, Y) = _{i=1}^{d+1} P(X_i (X_i)) $$

其中(X_i)$ 是 的父节点集合。

下图对比了朴素贝叶斯、 TAN 和一般贝叶斯网络的结构差异，展示了属性依赖建模的演进过程：

条件独立性：在贝叶斯网络中，节点 在给定父节点(X)$ 时，与非后代节点条件独立。

d-分离（ d-separation）：判断贝叶斯网络中条件独立关系的图形化准则（详见第 20 章）。

下图说明了 d-分离的三种基本结构（链式、分叉式、碰撞式）及其条件独立性判断规则：

结构学习：评分-搜索方法

目标：从数据中学习最优网络结构^*$ $

评分函数：

BIC 评分（贝叶斯信息准则）

$

其中： - P( , )$ 是对数似然 - 是参数量 - N$ 是复杂度惩罚

解释： BIC 平衡拟合优度与模型复杂度，避免过拟合。

AIC 评分

$

AIC 的惩罚项比 BIC 小，倾向于选择更复杂的结构。

K2 评分

$

其中： - 是节点 的父节点配置数 - 是节点 的取值数 - 是父节点配置 下节点 取值 的样本数

搜索算法

爬山搜索（ Hill Climbing）

  1. 初始化：从空图或随机图开始
  2. 邻域操作：
    • 添加边：
    • 删除边：
    • 反转边：
  3. 贪心选择：选择评分增益最大的操作
  4. 终止：无操作能提升评分

问题：易陷入局部最优。

K2 算法

假设节点有固定顺序。对每个节点，贪心选择父节点：

  1. 初始
  2. 重复：从 中选择使 K2 评分最大的节点加入
  3. 终止：无节点能提升评分或父节点数达上限

优势：避免环路检测，复杂度。

局限：依赖节点顺序（需先验知识或启发式）。

完整实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
import numpy as np
from collections import defaultdict
from itertools import combinations

class AODE:
    """平均单依赖估计"""
    def __init__(self, m=30, alpha=1.0):
        """
        参数:
            m: 最小样本阈值
            alpha: 拉普拉斯平滑参数
        """
        self.m = m
        self.alpha = alpha
        self.classes = None
        self.class_prior = {}
        self.feature_counts = defaultdict(lambda: defaultdict(int))
        self.feature_pair_counts = defaultdict(lambda: defaultdict(lambda: defaultdict(int)))
        
    def fit(self, X, y):
        N, d = X.shape
        self.classes = np.unique(y)
        self.d = d
        
        # 先验概率
        for c in self.classes:
            self.class_prior[c] = np.sum(y == c) / N
        
        # 单特征计数
        for c in self.classes:
            for j in range(d):
                for i in range(N):
                    if y[i] == c:
                        val = X[i, j]
                        self.feature_counts[(c, j, val)] += 1
        
        # 特征对计数
        for c in self.classes:
            for j1 in range(d):
                for j2 in range(d):
                    if j1 != j2:
                        for i in range(N):
                            if y[i] == c:
                                val1, val2 = X[i, j1], X[i, j2]
                                self.feature_pair_counts[(c, j1, val1, j2, val2)] += 1
        
        return self
    
    def predict_log_proba(self, X):
        N = X.shape[0]
        K = len(self.classes)
        log_proba = np.full((N, K), -np.inf)
        
        for idx, c in enumerate(self.classes):
            N_c = sum(1 for key in self.feature_counts if key[0] == c)
            
            for i in range(N):
                # 枚举所有可能的超父
                super_parent_scores = []
                
                for p in range(self.d):
                    # 检查样本阈值
                    n_p = self.feature_counts.get((c, p, X[i, p]), 0)
                    if n_p < self.m:
                        continue
                    
                    # 计算 SPODE 分数
                    score = np.log(self.class_prior[c])
                    
                    # P(x^(p) | Y=c)
                    score += np.log((n_p + self.alpha) / (N_c + self.alpha * 2))
                    
                    # P(x^(j) | Y=c, x^(p))
                    for j in range(self.d):
                        if j == p:
                            continue
                        count = self.feature_pair_counts.get((c, p, X[i, p], j, X[i, j]), 0)
                        score += np.log((count + self.alpha) / (n_p + self.alpha * 2))
                    
                    super_parent_scores.append(score)
                
                # 对数求和技巧： log(sum(exp(scores)))
                if super_parent_scores:
                    max_score = max(super_parent_scores)
                    log_proba[i, idx] = max_score + np.log(
                        sum(np.exp(s - max_score) for s in super_parent_scores)
                    )
        
        return log_proba
    
    def predict(self, X):
        log_proba = self.predict_log_proba(X)
        return self.classes[np.argmax(log_proba, axis=1)]
    
    def score(self, X, y):
        return np.mean(self.predict(X) == y)

class TAN:
    """树增广朴素贝叶斯"""
    def __init__(self, alpha=1.0):
        self.alpha = alpha
        self.classes = None
        self.trees = {}  # 每个类别一棵树
        self.class_prior = {}
        
    def _conditional_mutual_info(self, X, y, j, k, c):
        """计算条件互信息 I(X^(j); X^(k) | Y=c)"""
        X_c = X[y == c]
        N_c = len(X_c)
        
        if N_c == 0:
            return 0
        
        # 统计联合频率
        counts_jk = defaultdict(int)
        counts_j = defaultdict(int)
        counts_k = defaultdict(int)
        
        for i in range(N_c):
            val_j, val_k = X_c[i, j], X_c[i, k]
            counts_jk[(val_j, val_k)] += 1
            counts_j[val_j] += 1
            counts_k[val_k] += 1
        
        # 计算互信息
        mi = 0
        for (val_j, val_k), count_jk in counts_jk.items():
            p_jk = count_jk / N_c
            p_j = counts_j[val_j] / N_c
            p_k = counts_k[val_k] / N_c
            if p_jk > 0 and p_j > 0 and p_k > 0:
                mi += p_jk * np.log(p_jk / (p_j * p_k))
        
        return mi
    
    def _learn_tree(self, X, y, c):
        """学习类别 c 的树结构（ Chow-Liu 算法）"""
        d = X.shape[1]
        
        # 计算所有边的条件互信息
        edges = []
        for j, k in combinations(range(d), 2):
            mi = self._conditional_mutual_info(X, y, j, k, c)
            edges.append((mi, j, k))
        
        # 最大生成树（ Kruskal 算法）
        edges.sort(reverse=True)
        parent = list(range(d))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x, y):
            px, py = find(x), find(y)
            if px != py:
                parent[px] = py
                return True
            return False
        
        tree_edges = []
        for mi, j, k in edges:
            if union(j, k):
                tree_edges.append((j, k))
                if len(tree_edges) == d - 1:
                    break
        
        # 构建父节点映射（选择节点 0 为根）
        adj = defaultdict(list)
        for j, k in tree_edges:
            adj[j].append(k)
            adj[k].append(j)
        
        # BFS 定向
        parent_map = {0: None}
        queue = [0]
        visited = {0}
        
        while queue:
            node = queue.pop(0)
            for neighbor in adj[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    parent_map[neighbor] = node
                    queue.append(neighbor)
        
        return parent_map
    
    def fit(self, X, y):
        N, d = X.shape
        self.classes = np.unique(y)
        self.d = d
        
        # 先验概率
        for c in self.classes:
            self.class_prior[c] = np.sum(y == c) / N
        
        # 为每个类别学习树
        for c in self.classes:
            self.trees[c] = self._learn_tree(X, y, c)
        
        # 参数估计（简化：存储条件概率）
        self.params = defaultdict(lambda: defaultdict(lambda: defaultdict(float)))
        
        for c in self.classes:
            X_c = X[y == c]
            N_c = len(X_c)
            
            for j in range(d):
                parent_j = self.trees[c].get(j)
                
                if parent_j is None:
                    # 根节点： P(x^(j) | Y=c)
                    values = np.unique(X_c[:, j])
                    for val in values:
                        count = np.sum(X_c[:, j] == val)
                        self.params[c][j][(None, val)] = (count + self.alpha) / (N_c + len(values) * self.alpha)
                else:
                    # 非根节点： P(x^(j) | Y=c, x^(parent))
                    for i in range(N_c):
                        parent_val = X_c[i, parent_j]
                        val = X_c[i, j]
                        self.params[c][j][(parent_val, val)] = self.params[c][j].get((parent_val, val), 0) + 1
                    
                    # 归一化
                    parent_counts = defaultdict(int)
                    for (pval, val), count in self.params[c][j].items():
                        if pval is not None:
                            parent_counts[pval] += count
                    
                    for (pval, val) in list(self.params[c][j].keys()):
                        if pval is not None:
                            self.params[c][j][(pval, val)] = (self.params[c][j][(pval, val)] + self.alpha) / (parent_counts[pval] + self.alpha * 2)
        
        return self
    
    def predict_log_proba(self, X):
        N = X.shape[0]
        K = len(self.classes)
        log_proba = np.zeros((N, K))
        
        for idx, c in enumerate(self.classes):
            for i in range(N):
                score = np.log(self.class_prior[c])
                
                for j in range(self.d):
                    parent_j = self.trees[c].get(j)
                    val = X[i, j]
                    
                    if parent_j is None:
                        prob = self.params[c][j].get((None, val), self.alpha / (len(self.params[c][j]) * self.alpha))
                    else:
                        parent_val = X[i, parent_j]
                        prob = self.params[c][j].get((parent_val, val), self.alpha / 2)
                    
                    score += np.log(prob + 1e-9)
                
                log_proba[i, idx] = score
        
        return log_proba
    
    def predict(self, X):
        log_proba = self.predict_log_proba(X)
        return self.classes[np.argmax(log_proba, axis=1)]
    
    def score(self, X, y):
        return np.mean(self.predict(X) == y)

# 示例使用
if __name__ == '__main__':
    from sklearn.datasets import load_iris
    from sklearn.model_selection import train_test_split
    from sklearn.preprocessing import KBinsDiscretizer
    
    # 加载数据并离散化
    iris = load_iris()
    discretizer = KBinsDiscretizer(n_bins=3, encode='ordinal', strategy='uniform')
    X_discrete = discretizer.fit_transform(iris.data).astype(int)
    
    X_train, X_test, y_train, y_test = train_test_split(
        X_discrete, iris.target, test_size=0.3, random_state=42
    )
    
    # AODE
    print("=== AODE ===")
    aode = AODE(m=10, alpha=1.0)
    aode.fit(X_train, y_train)
    print(f"测试准确率: {aode.score(X_test, y_test):.4f}")
    
    # TAN
    print("\n=== TAN ===")
    tan = TAN(alpha=1.0)
    tan.fit(X_train, y_train)
    print(f"测试准确率: {tan.score(X_test, y_test):.4f}")
    print(f"类别 0 的树结构: {tan.trees[0]}")

对比分析

模型复杂度比较

模型 参数量 训练复杂度 预测复杂度
朴素贝叶斯
SPODE
AODE
TAN

（ 是平均取值数）

性能对比

实验（ UCI 数据集， Friedman et al., 1997）：

数据集 NB SPODE AODE TAN
Vote 90.1 92.3 93.5 94.2
Mushroom 95.8 97.1 98.2 99.1
Chess 87.9 89.5 91.2 92.7

结论： - TAN 通常最优（结构学习最灵活） - AODE 稳定性好（无需特征选择） - SPODE 依赖超父选择（方差较大）

Q&A 精选

Q1： AODE 为什么不选择单一超父？

A：单一超父选择引入偏差和方差： - 偏差：若选错超父，性能下降 - 方差：小样本下选择不稳定

AODE 通过模型平均（ Model Averaging）减少方差，类似集成学习中的 Bagging 。

Q2： TAN 的树结构为什么对每个类别独立学习？

A：不同类别的属性依赖关系可能不同。例如： - 垃圾邮件："free"和"money"强相关 - 正常邮件："meeting"和"schedule"强相关

独立学习捕获类别特定的依赖模式。

Q3：如何扩展到多依赖（ k-dependence）？

A：k-dependence Bayesian Classifier：允许每个属性最多依赖 个其他属性。 - ：朴素贝叶斯 - ： ODE（ SPODE, AODE, TAN） - $ k=2：二依赖估计（计算复杂度O (d^3)$）

越大，表达能力越强，但参数量指数增长。

Q4：贝叶斯网络结构学习的难度？

A：结构学习是 NP-hard 问题（证明： Chickering et al., 2004）。原因： - 搜索空间： 个节点的 DAG 数量是超指数的 - 评分非凸：局部搜索易陷入局部最优

实用方法： - 约束搜索空间（如固定顺序、限制父节点数） - 启发式搜索（爬山、模拟退火、遗传算法） - 基于约束的方法（ PC 算法、 GES 算法）

Q5：如何处理连续特征？

A： 1. 离散化：等宽、等频、基于熵的离散化 2. 高斯假设：条件高斯贝叶斯网络（参数为均值和协方差） 3. 混合模型：离散+连续混合分布

Q6：半朴素贝叶斯与特征选择的关系？

A：半朴素贝叶斯隐式进行特征选择： - SPODE：超父是最重要特征 - AODE：样本阈值 过滤不重要特征 - TAN：树结构反映特征重要性（条件互信息）

可先用互信息、卡方检验等方法预选特征，再用半朴素贝叶斯建模。

Q7：贝叶斯网络能做因果推断吗？

A：有向边不一定表示因果关系（可能是相关性）。因果推断需要： - 干预（ Do-演算）： Pearl 的因果图框架 - 反事实推理：潜在结果框架

标准贝叶斯网络只能做关联推断，需额外因果假设（如工具变量、后门准则）才能做因果推断（详见第 20 章）。

Q8：如何可视化贝叶斯网络？

A：使用图可视化工具（如 NetworkX + Matplotlib）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import networkx as nx
import matplotlib.pyplot as plt

def plot_bn(adj_matrix, labels):
    G = nx.DiGraph()
    d = len(labels)
    G.add_nodes_from(range(d))
    
    for i in range(d):
        for j in range(d):
            if adj_matrix[i, j]:
                G.add_edge(i, j)
    
    pos = nx.spring_layout(G)
    nx.draw(G, pos, labels={i: labels[i] for i in range(d)},
            node_color='lightblue', node_size=1500, 
            with_labels=True, arrows=True, arrowsize=20)
    plt.show()

Q9：半朴素贝叶斯在大数据上的可扩展性？

A： - AODE：需存储所有属性对的联合计数，空间 - TAN：条件互信息计算，大规模数据可采样估计 - 并行化：参数估计可并行（每个类别、每个属性对独立计算） - 在线学习：增量更新计数统计，支持数据流

Q10：半朴素贝叶斯与深度学习的关系？

A：现代深度生成模型（如 VAE 、 GAN）本质上是高维贝叶斯网络： - VAE：隐变量 生成观测$ x（类似Y ） - 自回归模型（如 PixelCNN）：链式分解（类似 TAN 的有向链）

半朴素贝叶斯是理解概率生成模型的基础。

参考文献

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

半朴素贝叶斯在朴素贝叶斯的简单与贝叶斯网络的灵活之间架起桥梁，以适度的复杂度换取显著的性能提升。从 SPODE 的超父依赖到 TAN 的树结构学习，从 AODE 的模型平均到贝叶斯网络的结构搜索，这些方法展现了概率图模型的强大表达能力与优雅数学结构。掌握半朴素贝叶斯，是通往贝叶斯网络、马尔可夫网络等高级概率推理技术的必经之路。

  • 本文标题：机器学习数学推导（十）半朴素贝叶斯与贝叶斯网络
  • 本文作者：Chen Kai
  • 创建时间：2021-10-18 16:00:00
  • 本文链接：https://www.chenk.top/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0%E6%95%B0%E5%AD%A6%E6%8E%A8%E5%AF%BC%EF%BC%88%E5%8D%81%EF%BC%89%E5%8D%8A%E6%9C%B4%E7%B4%A0%E8%B4%9D%E5%8F%B6%E6%96%AF%E4%B8%8E%E8%B4%9D%E5%8F%B6%E6%96%AF%E7%BD%91%E7%BB%9C/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
 评论