贝叶斯网贝叶斯分类器课件

贝叶斯网贝叶斯分类器贝叶斯网贝叶斯分类器贝叶斯网贝叶斯分类器第1页图形绘制图片处理图表设计经典案例*贝叶斯决议论1346Contents目 录*25极大似然预计朴素贝叶斯分类器半朴素贝叶斯分类器贝叶斯网EM算法机器学习贝叶斯分类器贝叶斯网贝叶斯分类器第2页图形绘制图片处理图表设计经典案例*贝叶斯决议论1346Chapter 7*25极大似然预计朴素贝叶斯分类器半朴素贝叶斯分类器贝叶斯网EM算法机器学习贝叶斯分类器贝叶斯网贝叶斯分类器第3页图形绘制判别式vs.生成式贝叶斯定理*贝叶斯准则7.1 贝叶斯决议论贝叶斯决议论（Bayesiandecisiontheory）概率框架下实施决议基本理论。对于分类任务：基于已知相关概率和误判损失选择最优类别标识后验概率寻找一个判定准则h以最小化总体风险：贝叶斯网贝叶斯分类器第4页图形绘制判别式vs.生成式贝叶斯定理*贝叶斯准则7.1 贝叶斯决议论贝叶斯判定准则（Bayesdecisionrule）h*称为贝叶斯最优分类器(Bayes optimal classifier)，其总体风险称为贝叶斯风险(Bayes risk)反应了学习性能理论上限贝叶斯网贝叶斯分类器第5页判别式vs.生成式贝叶斯定理*贝叶斯准则7.1 贝叶斯决议论判别式vs.生成式生成式(generative)模型 决议树 BP 神经网络SVM代表：贝叶斯分类器贝叶斯网贝叶斯分类器第6页判别式vs.生成式贝叶斯定理*贝叶斯准则7.1 贝叶斯决议论贝叶斯定理Thomas Bayes(1701?-1761)依据贝叶斯定理，有证据(evidence)因子，与类别无关主要困难在于预计似然样本相对于类标识类条件概率(class-conditional probability),亦称似然(likelihood)类先验概率（prior）样本空间中各类样本所占百分比，可经过各类样本出现频率预计（大数定律）贝叶斯网贝叶斯分类器第7页图形绘制图片处理图表设计经典案例*贝叶斯决议论1346Chapter 7*25极大似然预计朴素贝叶斯分类器半朴素贝叶斯分类器贝叶斯网EM算法机器学习贝叶斯网贝叶斯分类器第8页先假设类条件概率某种概率分布形式，再基于训练样样本对参数进行预计*7.2 极大似然预计极大似然预计（MaximumLikelihoodEstimation,MLE）使用对数似然(log-likelihood)预计结果准确性严重依赖于所假设概率分布形式是否符合潜在真实分布贝叶斯网贝叶斯分类器第9页*7.2 极大似然预计极大似然预计（MaximumLikelihoodEstimation,MLE）贝叶斯网贝叶斯分类器第10页图形绘制图片处理图表设计经典案例*贝叶斯决议论1346Chapter 7*25极大似然预计朴素贝叶斯分类器半朴素贝叶斯分类器贝叶斯网EM算法机器学习贝叶斯网贝叶斯分类器第11页拉普拉斯修正*朴素贝叶斯分类器7.3 朴素贝叶斯分类器朴素贝叶斯分类器（naveBayesclassifiers）基础思绪：假定属性相互独立d 为属性数，xi 为x 在第i 个属性上取值对所有类别相同，于是分类器使用贝叶斯网贝叶斯分类器第12页对离散属性，令表示Dc 中在第i 个属性上取值为xi 样本组成集合，则拉普拉斯修正*朴素贝叶斯分类器7.3 朴素贝叶斯分类器分类器使用 估计P(c):估计P(x|c):对连续属性，考虑概率密度函数，假定朴素贝叶斯分类器（naveBayesclassifiers）贝叶斯网贝叶斯分类器第13页拉普拉斯修正*朴素贝叶斯分类器7.3 朴素贝叶斯分类器分类器使用比如：朴素贝叶斯分类器（naveBayesclassifiers）首先预计类先验概率P(c):贝叶斯网贝叶斯分类器第14页拉普拉斯修正*朴素贝叶斯分类器7.3 朴素贝叶斯分类器分类器使用比如：朴素贝叶斯分类器（naveBayesclassifiers）贝叶斯网贝叶斯分类器第15页拉普拉斯修正*朴素贝叶斯分类器7.3 朴素贝叶斯分类器分类器使用比如：朴素贝叶斯分类器（naveBayesclassifiers）贝叶斯网贝叶斯分类器第16页拉普拉斯修正*朴素贝叶斯分类器7.3 朴素贝叶斯分类器分类器使用比如：朴素贝叶斯分类器（naveBayesclassifiers）贝叶斯网贝叶斯分类器第17页拉普拉斯修正*朴素贝叶斯分类器7.3 朴素贝叶斯分类器分类器使用拉普拉斯修正（Laplaciancorrection）若某个属性值在训练集中没有与某个类同时出现过，则直接计算会出现问题，因为概率连乘将“抹去”其他属性提供信息比如，若训练集中未出现“敲声=清脆”好瓜，则模型在碰到“敲声=清脆”测试样本时 令N 表示训练集D 中可能类别数，Ni 表示第i 个属性可能取值数贝叶斯网贝叶斯分类器第18页拉普拉斯修正*朴素贝叶斯分类器7.3 朴素贝叶斯分类器分类器使用朴素贝叶斯分类器使用 若对预测速度要求高，则对给定数据集，预计算所有概率估值，使用时“查表”若数据更替频繁 不进行任何训练，收到预测请求时再根据当前数据集进行估值(懒惰学习,lazy learning)若数据不断增加 基于现有估值，对新样本属性值涉及概率估值进行修正(增量学习,incremental learning)贝叶斯网贝叶斯分类器第19页图形绘制图片处理图表设计经典案例*贝叶斯决议论1346Chapter 7*25极大似然预计朴素贝叶斯分类器半朴素贝叶斯分类器贝叶斯网EM算法机器学习贝叶斯网贝叶斯分类器第20页SPODE&TAN*半朴素贝叶斯分类器7.4 半朴素贝叶斯分类器AODE半朴素贝叶斯分类器（semi-naveBayesclassifiers）朴素贝叶斯分类器“属性独立性假设”在现实中往往难以成立半朴素贝叶斯分类器(semi-naveBayesclassifier)基本思路：适当考虑一部分属性间相互依赖信息最常见策略：独依赖估计(One-DependentEstimator,ODE)假设每个属性在类别之外最多仅依赖一个其它属性假如确定了父属性，那么关键是如何确定每个节点父属性?贝叶斯网贝叶斯分类器第21页SPODE&TAN*半朴素贝叶斯分类器7.4 半朴素贝叶斯分类器AODE两种常见方法SPODE(Super-ParentODE)：假设全部属性都依赖于同一属性，称为“超父”(Super-Parent)，然后经过交叉验证等模型选择方法来确定超父属性TAN(TreeAugmentednaveBayes)：以属性间条件”互信息”(mutualinformation)为边权重，构建完全图，再利用最大带权生成树算法，仅保留强相关属性间依赖性贝叶斯网贝叶斯分类器第22页SPODE&TAN*半朴素贝叶斯分类器7.4 半朴素贝叶斯分类器AODEAODE(AveragedOne-DependentEstimator)尝试将每个属性作为超父构建SPODE将拥有足够训练数据支撑SPODE集成起来作为最终止果其中是在第i 个属性上取值为xi 样本集合，m 为阈值常数(默认为30)表示类别为c 且在第i 和第j 个属性上取值分别为xi 和xj 样本集合Geoff Webb 澳大利亚Monash大学贝叶斯网贝叶斯分类器第23页SPODE&TAN*半朴素贝叶斯分类器7.4 半朴素贝叶斯分类器AODE高阶依赖 训练样本非常充分 性能可能提升 有限训练样本 高阶联合概率预计困难考虑属性间高阶依赖，需要其它方法能否经过考虑属性间高阶依赖来深入提升泛化性能？比如最简单做法：ODE kDE将父属性pai 替换为包含k 个属性集合障碍：伴随k 增加，准确预计所需样本数量将以指数增加贝叶斯网贝叶斯分类器第24页图形绘制图片处理图表设计经典案例*贝叶斯决议论1346Chapter 7*25极大似然预计朴素贝叶斯分类器半朴素贝叶斯分类器贝叶斯网EM算法机器学习贝叶斯网贝叶斯分类器第25页学习*结构7.5 贝叶斯网推断贝叶斯网（Bayesiannetwork）贝叶斯网亦称“信念网”(beliefnetwork)有向无环图(DirectedAcyclicGraph)&条件概率表(CPT,ConditionalProbabilityTable)Judea Pearl(1936-)2011 图灵奖贝叶斯网结构参数西瓜问题一个贝叶斯网结构以及属性“根蒂”条件概率表1985年J.Pearl 命名为贝叶斯网，为了强调：输入信息主观本质对贝叶斯条件依赖性因果与证据推理区分贝叶斯网贝叶斯分类器第26页学习*结构7.5 贝叶斯网推断结构贝叶斯网比如：贝叶斯网贝叶斯分类器第27页学习*结构7.5 贝叶斯网推断结构贝叶斯网贝叶斯网贝叶斯分类器第28页学习*结构7.5 贝叶斯网推断结构贝叶斯网条件独立性条件独立性边际独立性给定x4,x1 与x2 必不独立若x4 未知，则x1 与x2 独立贝叶斯网中三变量间经典依赖关系对于三个随机变量a,b,c若a值完全未知，而b,c此时独立，则称之为边际独立贝叶斯网贝叶斯分类器第29页学习*结构7.5 贝叶斯网推断结构贝叶斯网分析条件独立性“有向分离”(D-separation)先将有向图转变为无向图V型结构父结点相连有向边变成无向边道德图(moralgraph)由图可得：若x 和y 能在图上被z 分入两个连通分支，则有得到条件独立性关系之后，预计出条件概率表，就得到了最终网络贝叶斯网贝叶斯分类器第30页例如最小描述长度(MDL,MinimalDescriptionLength)给定数据集D，贝叶斯网在D上评分函数：越小越好学习*结构7.5 贝叶斯网推断学习贝叶斯网评分函数(scorefunction)评定贝叶斯网与训练数据契合程度常见评分函数通常基于信息论准则贝叶斯网贝叶斯分类器第31页学习*结构7.5 贝叶斯网推断学习贝叶斯网AIC:BIC:搜索最优贝叶斯网络结构是NP难问题贝叶斯网贝叶斯分类器第32页学习*结构7.5 贝叶斯网推断推断贝叶斯网推断(inference)：基于已知属性变量观察值，推测其它属性变量取值已知属性变量观察值称为“证据”(evidence)准确推断：直接依据贝叶斯网定义联合概率分布来准确计算后验概率NP难 近似推断：降低精度要求，在有限时间内求得近似解常见做法：吉布斯采样(Gibbssampling)变分推断(variationalinference)贝叶斯网贝叶斯分类器第33页学习*结构7.5 贝叶斯网推断推断吉布斯采样思想贝叶斯网随机产生一个与证据E=e 一致样本q0作为初始点比如：证据E=e：(色泽;敲声;根蒂)=(青绿;浊响;蜷缩)查询目标Q=q:(好瓜;甜度)=(是;高)随机产生q0:(否;高)进行T 次采样，每次采样中逐个考察每个非证据变量：假定所有其它属性取当前值，推断出采样概率，然后根据该概率采样取值假定经过T 次采样得到与“查询目标”q 一致样本共有nq 个，则可近似估算出后验概率贝叶斯网贝叶斯分类器第34页学习*结构7.5 贝叶斯网推断贝叶斯网推断吉布斯采样算法比如：先假定色泽=青绿;敲声=浊响;根蒂=蜷缩;甜度=高，推断出“好瓜”采样概率，然后采样；假设采样结果为“好瓜=是”;然后依据色泽=青绿;敲声=浊响;根蒂=蜷缩;好瓜=是，推断出“甜度”采样概率，然后采样；假设采样结果为“甜度=高”;证据E=e：(色泽;敲声;根蒂)=(青绿;浊响;蜷缩)查询目标Q=q:(好瓜;甜度)=(是;高)贝叶斯网贝叶斯分类器第35页图形绘制图片处理图表设计经典案例*贝叶斯决议论1346Chapter 7*25极大似然预计朴素贝叶斯分类器半朴素贝叶斯分类器贝叶斯网EM算法机器学习贝叶斯网贝叶斯分类器第36页*7.6 EM算法Z 是隐变量，无法直接求解。怎么办？EM算法贝叶斯网贝叶斯分类器第37页*7.6 EM算法EM算法对隐变量Z 计算期望，最大化已观察数据对数“边际似然”(marginal likelihood)以初始值为起点，迭代执行以下步骤直至收敛:基于推断隐变量Z 期望，记为 基于已观察变量X 和对参数做极大似然估计，记为E步:当已知 依据训练数据推断出最优隐变量ZM步:当Z 已知 对做极大似然预计EM(Expectation-Maximization)算法是预计隐变量利器，一个迭代方法贝叶斯网贝叶斯分类器第38页机器学习贝叶斯分类器贝叶斯网贝叶斯分类器第39页