机器学习周志华.pptx

七、贝叶斯分类器
第一页，共二十三页。
贝叶斯决策论
(Bayesian decision theory)
概率框架下实施决策的基本理论
给定 N 个类别，令 λij 代表将第 j 类样本误分类为第 i 类所产生的
损失，性
第十页，共二十三页。
两种常见方法
 SPODE (Super-Parent ODE)：
假设所有属性都依赖于同一属性，称为“超父” (Super-Parent)，
然后通过交叉验证等模型选择方法来确定超父属性
 TAN (Tree Augmented naïve Bayes)：
以属性间的条件 ”互信息 ”(mutual information)为边的权重，构建完
全图，再利用最大带权生成树算法，仅保留强相关属性间的依赖性
第十一页，共二十三页。
AODE
(Averaged One-Dependent Estimator)
其中
是在第 i 个属性上取值为 xi 的样本的集合，m’ 为阈值常数
表示类别为 c 且在第 i 和第 j 个属性上取值分别为 xi 和 xj 的样本集合
• 尝试将每个属性作为超父构建 SPODE
• 将拥有足够训练数据支撑的 SPODE 集成起来作为最终结果
Geoff Webb
澳大利亚
Monash大学
第十二页，共二十三页。
高阶依赖
能否通过考虑属性间的高阶依赖来进一步提升泛化性能？
例如最简单的做法： ODE  kDE
将父属性 pai 替换为包含 k 个属性的集合 pai
明显障碍：随着 k 的增加，估计
所 需 的 样 本数
将以指数级增加
 训练样本非常充分  性能可能提升
 有限训练样本  高阶联合概率估计困难
考虑属性间的高阶依赖，需要其他办法
第十三页，共二十三页。
贝叶斯网 （Bayesian network; Bayes network）
亦称“信念网” (brief network)
Judea Pearl
(1936 - )
2011 图灵奖
有向无环图( DAG,
Directed Acyclic Graph)
贝叶斯网
结构
参数
概率图模型 (Probabilistic graphical model)
• 有向图模型  贝叶斯网
• 无向图模型  马尔可夫网
 第 14章
条件概率表 ( CPT,
Conditional Probability Table)
1985年 J. Pearl 命名为贝叶斯网，
为了强调：
•
输入信息的主观本质
•
•
对贝叶斯条件的依赖性
因果与证据推理的区别
第十四页，共二十三页。
贝叶斯网 （Bayesian network）
条件概率表 ( CPT,
Conditional Probability Table)
有向无环图( DAG,
Directed Acyclic Graph)
给定父结点集，贝叶斯网假设每个属性与其非后裔属性 独立
父结点集
第十五页，共二十三页。
三变量间的典型依赖关系
条件独立性
条件独立性
边际独立性
• 给定 x4, x1 与 x2 必不独立
• 若 x4 未知，则 x1 与 x2 独立
第十六页，共二十三页。
分析条件独立性
“有向分离”( D-separation)
先将有向图转变为无向图
• V 型结构父结点相连
• 有向边变成无向边
(根蒂)
x 1 (好瓜)
x 2 (甜度)
x 3 (敲声)
x 4 (色泽)
x
5
道德图
(moral graph)
由图可得：
若 x 和 y 能在图上被 z 分入
两个连通分支，则有
得到条件独立性关系之后，估计出条件
概率表，就得到了最终网络
第十七页，共二十三页。
结构学习
评分函数(score function)评估贝叶斯网与训练数据的契合程度
常用评分函数通常基于信息论准则
例如 最小描述长度
(MDL, Minimal Description Length)
给定数据集 D，贝叶斯网
• AIC:
• BIC:
• … …
搜索最优贝叶斯网络结构是 NP难问题
回忆“模型选择”
在 D 上的评分函数：
越小越好
是贝叶斯网的参数个数
表示描述每个参数 所需的字节数
第十八页，共二十三页。
推断
推断(inference