机器学习7周志华.ppt

七、贝叶斯分类器 贝叶斯决策论(Bayesian decision theory)概率框架下实施决策的基本理论给定 N 个类别，令 ij 代表将第 j 类样本误分类为第 i 类所产生的损失，则基于后验概率将样本 x 分到第 i 类的条件风险为：贝叶斯判定准则(Bayes decision rule)： h* 称为 贝叶斯最优分类器(Bayes optimal classifier)，其总体风险称为 贝叶斯风险 (Bayes risk) 反映了 学习性能的理论上限 判别式(discriminative)模型生成式(generative)模型建模思路：直接对代表： 决策树 BP 神经网络 SVM判别式 vs. 生成式在现实中通常难以直接获得从这个角度来看，机器学习所要实现的是基于有限的训练样本尽可能准确地估计出后验概率两种基本策略：思路：先对联合概率分布建模，再由此获得代表：贝叶斯分类器注意：贝叶斯分类器 贝叶斯学习(Bayesian learning) 贝叶斯定理根据贝叶斯定理，有先验概率（prior ） 样本空间中各类样本所占的比例，可通过各类样本出现的频率估计（大数定律）证据 (evidence)因子，与类别无关Thomas Bayes(1701?-1761)样本相对于类标记的 类条件概率 (class-conditionalprobability), 亦称 似然(likelihood)主要困难在于估计似然 极大似然估计先假设某种概率分布形式，再基于训练样例对参数进行估计假定具有确定的概率分布形式，且被参数唯一确定，则任务就是利用训练集 D 来估计参数对于训练集 D 中第 c 类样本组成的集合 Dc 的似然(likelihood)为连乘易造成下溢，因此通常使用对数似然 (log-likelihood)于是，的极大似然估计为估计结果的准确性严重依赖于所假设的概率分布形式是否符合潜在的真实分布 朴素贝叶斯分类器(nave Bayes classifier)主要障碍：所有属性上的联合概率难以从有限训练样本估计获得组合爆炸；样本稀疏基本思路：假定属性相互独立？d 为属性数， x i 为 x 在第 i 个属性上的取值对所有类别相同，于是 朴素贝叶斯分类器 估计 P(c): 估计 P(x|c): 对离散属性，令表示 Dc 中在第 i 个属性上取值为xi 的样本组成的集合，则 对连续属性，考虑概率密度函数，假定 拉普拉斯修正(Laplacian correction)若某个属性值在训练集中没有与某个类同时出现过，则直接计算会出现问题，因为概率连乘将“抹去”其他属性提供的信息例如，若训练集中未出现“敲声=清脆”的好瓜，则模型在遇到“敲声 =清脆”的测试样本时 令 N 表示训练集 D 中可能的类别数，Ni 表示第 i 个属性可能的取值数 假设了属性值与类别的均匀分布，这是额外引入的 bias 朴素贝叶斯分类器的使用 若对预测速度要求高 预计算所有概率估值，使用时“查表” 若数据更替频繁 不进行任何训练，收到预测请求时再估值(懒惰学习 , lazy learning) 若数据不断增加 基于现有估值，对新样本涉及的概率估值进行修正 (增量学习 , incremental learning) 半朴素贝叶斯分类器朴素贝叶斯分类器的“属性独立性假设”在现实中往往难以成立半朴素贝叶斯分类器 (semi-nave Bayes classifier)基本思路：适当考虑一部分属性间的相互依赖信息最常用策略： 独依赖估计(One-Dependent Estimator, ODE)假设每个属性在类别之外最多仅依赖一个其他属性 xi 的“父属性”关键是如何确定父属性 两种常见方法 SPODE (Super-Parent ODE)：假设所有属性都依赖于同一属性，称为“超父” (Super-Parent)，然后通过交叉验证等模型选择方法来确定超父属性 TAN (Tree Augmented nave Bayes)：以属性间的条件 ”互信息 ”(mutual information)为边的权重，构建完全图，再利用最大带权生成树算法，仅保留强相关属性间的依赖性 AODE (Averaged One-Dependent Estimator)其中是在第 i 个属性上取值为 x i 的样本的集合，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)给定父结点集，贝叶斯网假设每个属性与其非后裔属性 独立 父结点集 三变量间的典型依赖关系条件独立性条件独立性边际独立性 给定 x 4, x1 与 x2 必不独立 若 x4 未知，则 x1 与 x2 独立 分析条件独立性“有向分离”( D-separation)先将有向图转变为无向图 V 型结构父结点相连 有向边变成无向边(根蒂)x 1 (好瓜) x 2 (甜度)x 3 (敲声) x 4 (色泽) x5道德图(moral graph)由图可得：若 x 和 y 能在图上被 z 分入两个连通分支，则有 得到条件独立性关系之后，估计出条件概率表，就得到了最终网络 结构学习评分函数(score function)评估贝叶斯网与训练数据的契合程度常用评分函数通常基于信息论准则例如 最小描述长度(MDL, Minimal Description Length)给定数据集 D，贝叶斯网 AIC: BIC: 搜索最优贝叶斯网络结构是 NP难问题回忆“模型选择”在 D 上的评分函数：越小越好是贝叶斯网的参数个数表示描述每个参数 所需的字节数 推断推断(inference)：基于已知属性变量的观测值，推测其他属性变量的取值已知属性变量的观测值称为“证据” (evidence) 精确推断：直接根据贝叶斯网定义的联合概率分布来精确计算后验概率NP 难 近似推断：降低精度要求，在有限时间内求得近似解常见做法： 吉布斯采样 (Gibbs sampling) 变分推断 (variational inference) 吉布斯采样 随机产生一个与证据 E = e 一致的样本 q0 作为初始点例如 证据 E = e：(色泽; 敲声 ;根蒂) = (青绿 ; 浊响; 蜷缩)查询目标 Q = q: (好瓜 ;甜度)= (是;高)随机产生 q0: (否; 高) 进行 T 次采样，每次采样中逐个考察每个非证据变量：假定所有其他属性取当前值，推断出采样概率，然后根据该概率采样例如：先假定 色泽=青绿; 敲声=浊响; 根蒂=蜷缩; 甜度=高，推断出“好瓜”的采样概率，然后采样；假设采样结果为“ 好瓜=是”;然后根据 色泽=青绿 ; 敲声=浊响; 根蒂 =蜷缩;好瓜 =是，推断出“甜度” 的采样概率，然后采样；假设采样结果为“ 甜度=高”; 假定经过 T 次采样的得到与“查询目标” q 一致的样本共有 n q个，则可近似估算出后验概率 EM算法如何处理“未观测到的”变量？例如，西瓜已经脱落的根蒂，无法看出是“蜷缩”还是“坚挺”,则训练样本的“根蒂”属性变量值未知未观测变量 隐变量(latent variable)EM(Expectation-Maximization) 算法是估计隐变量的利器做令 X 表示已观测变量集， Z 表示隐变量集，欲对模型参数极大似然估计，则应最大化对数似然函数 Z 是隐变量，无法直接求解。怎么办？ 以初始值 基于为起点，迭代执行以下步骤直至收敛 :推断隐变量 Z 的期望，记为 基于已观测变量 X 和对参数做极大似然估计，记为E步 : 当已知 根据训练数据推断出最优隐变量 ZM步 : 当 Z 已知 对做极大似然估计EM算法 (续 )对隐变量 Z 计算期望，最大化已观测数据的对数“边际似然”(marginal likelihood) 前往第八站