贝叶斯网贝叶斯分类器.ppt

北京 第七章贝叶斯分类器 机器学习 2018 09 02 图形绘制 图片处理 图表设计 典型案例 贝叶斯决策论 Contents 目录 极大似然估计 朴素贝叶斯分类器 半朴素贝叶斯分类器 贝叶斯网 EM算法 机器学习贝叶斯分类器 图形绘制 图片处理 图表设计 典型案例 贝叶斯决策论 Chapter7 极大似然估计 朴素贝叶斯分类器 半朴素贝叶斯分类器 贝叶斯网 EM算法 机器学习贝叶斯分类器 图形绘制 判别式vs 生成式 贝叶斯定理 贝叶斯准则 7 1贝叶斯决策论 贝叶斯决策论 Bayesiandecisiontheory 概率框架下实施决策的基本理论 对于分类任务 基于已知相关概率和误判损失选择最优类别标记 1 后验概率 寻找一个判定准则h以最小化总体风险 给定N个类别标记 1 2 令 ij代表将第j类样本误分类为第i类所产生的损失 则基于后验概率 可知 将样本x分到第i类的条件风险 risk 为 图形绘制 判别式vs 生成式 贝叶斯定理 贝叶斯准则 7 1贝叶斯决策论 贝叶斯判定准则 Bayesdecisionrule h 称为贝叶斯最优分类器 Bayesoptimalclassifier 其总体风险称为贝叶斯风险 Bayesrisk 反映了学习性能的理论上限 argmin 1 arg 0 1 argmin 为最小化总体风险 只需在每个样本上选择那个能使条件风险 最小的类别标记 1 判别式vs 生成式 贝叶斯定理 贝叶斯准则 7 1贝叶斯决策论 判别式vs 生成式 在现实中通常难以直接获得从这个角度来看 机器学习所要实现的是基于有限的训练样本尽可能准确地估计出后验概率 两种基本策略 判别式 discriminative 模型思路 直接对 建模代表 生成式 generative 模型 决策树 BP神经网络SVM 代表 贝叶斯分类器 思路 先对联合概率分布 建模 再由此获得 判别式vs 生成式 贝叶斯定理 贝叶斯准则 7 1贝叶斯决策论 贝叶斯定理 ThomasBayes 1701 1761 根据贝叶斯定理 有 证据 evidence 因子 与类别无关 主要困难在于估计似然 样本相对于类标记的类条件概率 class conditionalprobability 亦称似然 likelihood 类先验概率 prior 样本空间中各类样本所占的比例 可通过各类样本出现的频率估计 大数定律 图形绘制 图片处理 图表设计 典型案例 贝叶斯决策论 Chapter7 极大似然估计 朴素贝叶斯分类器 半朴素贝叶斯分类器 贝叶斯网 EM算法 机器学习 先假设类条件概率某种概率分布形式 再基于训练样样本对参数进行估计 7 2极大似然估计 极大似然估计 MaximumLikelihoodEstimation MLE 使用对数似然 log likelihood 于是 的极大似然估计为 log log argmax 估计结果的准确性严重依赖于所假设的概率分布形式是否符合潜在的真实分布 假定 具有确定的概率分布形式 且被参数向量 唯一确定 则任务就是利用训练集D来估计参数 对于训练集D中第c类样本组成的集合Dc的似然 likelihood 为 例如 假设概率密度函数 2 则 和 2的极大似然估计为 7 2极大似然估计 log log 2 log12 2 22 2 分别对 2进行求导 在对应的一阶导函数的零点处即可取得对应的 2的极大似然估计 极大似然估计 MaximumLikelihoodEstimation MLE 图形绘制 图片处理 图表设计 典型案例 贝叶斯决策论 Chapter7 极大似然估计 朴素贝叶斯分类器 半朴素贝叶斯分类器 贝叶斯网 EM算法 机器学习 拉普拉斯修正 朴素贝叶斯分类器 7 3朴素贝叶斯分类器 朴素贝叶斯分类器 na veBayesclassifiers 基本思路 假定属性相互独立 d为属性数 xi为x在第i个属性上的取值 对所有类别相同 于是 分类器使用 1 argmax 1 对离散属性 令表示Dc中在第i个属性上取值为xi的样本组成的集合 则 拉普拉斯修正 朴素贝叶斯分类器 7 3朴素贝叶斯分类器 分类器使用 估计P c 估计P x c 对连续属性 考虑概率密度函数 假定 2 12 exp 22 2 朴素贝叶斯分类器 na veBayesclassifiers 拉普拉斯修正 朴素贝叶斯分类器 7 3朴素贝叶斯分类器 分类器使用 例如 朴素贝叶斯分类器 na veBayesclassifiers 首先估计类先验概率P c 拉普拉斯修正 朴素贝叶斯分类器 7 3朴素贝叶斯分类器 分类器使用 例如 朴素贝叶斯分类器 na veBayesclassifiers 拉普拉斯修正 朴素贝叶斯分类器 7 3朴素贝叶斯分类器 分类器使用 例如 分别计算 2 朴素贝叶斯分类器 na veBayesclassifiers 拉普拉斯修正 朴素贝叶斯分类器 7 3朴素贝叶斯分类器 分类器使用 例如 分别计算 2 朴素贝叶斯分类器 na veBayesclassifiers 拉普拉斯修正 朴素贝叶斯分类器 7 3朴素贝叶斯分类器 分类器使用 拉普拉斯修正 Laplaciancorrection 若某个属性值在训练集中没有与某个类同时出现过 则直接计算会出现问题 因为概率连乘将 抹去 其他属性提供的信息例如 若训练集中未出现 敲声 清脆 的好瓜 则模型在遇到 敲声 清脆 的测试样本时 1 1 令N表示训练集D中可能的类别数 Ni表示第i个属性可能的取值数 拉普拉斯修正 朴素贝叶斯分类器 7 3朴素贝叶斯分类器 分类器使用 朴素贝叶斯分类器的使用 若对预测速度要求高 则对给定的数据集 预计算所有概率估值 使用时 查表 若数据更替频繁 不进行任何训练 收到预测请求时再根据当前数据集进行估值 懒惰学习 lazylearning 若数据不断增加 基于现有估值 对新样本的属性值涉及的概率估值进行修正 增量学习 incrementallearning 图形绘制 图片处理 图表设计 典型案例 贝叶斯决策论 Chapter7 极大似然估计 朴素贝叶斯分类器 半朴素贝叶斯分类器 贝叶斯网 EM算法 机器学习 SPODE TAN 半朴素贝叶斯分类器 7 4半朴素贝叶斯分类器 AODE 半朴素贝叶斯分类器 semi na veBayesclassifiers 朴素贝叶斯分类器的 属性独立性假设 在现实中往往难以成立半朴素贝叶斯分类器 semi na veBayesclassifier 基本思路 适当考虑一部分属性间的相互依赖信息最常用策略 独依赖估计 One DependentEstimator ODE 假设每个属性在类别之外最多仅依赖一个其他属性 为xi的 父属性 1 如果确定了父属性 那么 1 1 关键是如何确定每个节点的父属性 SPODE TAN 半朴素贝叶斯分类器 7 4半朴素贝叶斯分类器 AODE 两种常用方法 SPODE Super ParentODE 假设所有属性都依赖于同一属性 称为 超父 Super Parent 然后通过交叉验证等模型选择方法来确定超父属性TAN TreeAugmentedna veBayes 以属性间的条件 互信息 mutualinformation 为边的权重 构建完全图 再利用最大带权生成树算法 仅保留强相关属性间的依赖性 SPODE TAN 半朴素贝叶斯分类器 7 4半朴素贝叶斯分类器 AODE AODE AveragedOne DependentEstimator 尝试将每个属性作为超父构建SPODE 将拥有足够训练数据支撑的SPODE集成起来作为最终结果 其中 是在第i个属性上取值为xi的样本的集合 m 为阈值常数 默认为30 表示类别为c且在第i和第j个属性上取值分别为xi和xj的样本集合 1 1 1 1 GeoffWebb澳大利亚Monash大学 SPODE TAN 半朴素贝叶斯分类器 7 4半朴素贝叶斯分类器 AODE 高阶依赖 训练样本非常充分 性能可能提升 有限训练样本 高阶联合概率估计困难考虑属性间的高阶依赖 需要其他办法 能否通过考虑属性间的高阶依赖来进一步提升泛化性能 例如最简单的做法 ODE kDE将父属性pai替换为包含k个属性的集合 障碍 随着k的增加 准确估计 所需的样本数量将以指数增加 图形绘制 图片处理 图表设计 典型案例 贝叶斯决策论 Chapter7 极大似然估计 朴素贝叶斯分类器 半朴素贝叶斯分类器 贝叶斯网 EM算法 机器学习 学习 结构 7 5贝叶斯网 推断 贝叶斯网 Bayesiannetwork 贝叶斯网 亦称 信念网 beliefnetwork 有向无环图 DirectedAcyclicGraph 条件概率表 CPT ConditionalProbabilityTable JudeaPearl 1936 2011图灵奖 贝叶斯网 结构 参数 西瓜问题的一种贝叶斯网结构以及属性 根蒂 的条件概率表 1985年J Pearl命名为贝叶斯网 为了强调 输入信息的主观本质 对贝叶斯条件的依赖性 因果与证据推理的区别 学习 结构 7 5贝叶斯网 推断 结构 贝叶斯网 贝叶斯网联合概率分布定义 给定父结点集 贝叶斯网假设每个属性与其非后裔属性独立 1 2 1 1 1 2 3 4 5 1 2 3 1 4 1 2 5 2 例如 学习 结构 7 5贝叶斯网 推断 结构 贝叶斯网 显然 3和 4在给定 1的取值时独立 4和 5在给定 2的取值时独立 分别简记为 3 4 1 4 5 2 3 4 1 3 4 1 1 1 3 1 4 1 1 3 1 4 1 学习 结构 7 5贝叶斯网 推断 结构 贝叶斯网 条件独立性 条件独立性 边际独立性 给定x4 x1与x2必不独立 若x4未知 则x1与x2独立 3 4 1 贝叶斯网中三变量间的典型依赖关系 对于三个随机变量a b c若a的值完全未知 而b c此时独立 则称之为边际独立 1 2 4 1 2 4 4 1 2 4 1 2 4 1 4 2 4 1 2 学习 结构 7 5贝叶斯网 推断 结构 贝叶斯网 分析条件独立性 有向分离 D separation 先将有向图转变为无向图 V型结构父结点相连 有向边变成无向边 道德图 moralgraph 由图可得 若x和y能在图上被z分入两个连通分支 则有 得到条件独立性关系之后 估计出条件概率表 就得到了最终网络 3 4 1 4 5 2 3 2 1 3 5 1 3 5 2 例如最小描述长度 MDL MinimalDescriptionLength 给定数据集D 贝叶斯网在D上的评分函数 越小越好 学习 结构 7 5贝叶斯网 推断 学习 贝叶斯网 评分函数 scorefunction 评估贝叶斯网与训练数据的契合程度 常用评分函数通常基于信息论准则 表示描述每个参数 所需的字节数 1 log 是贝叶斯网络B的对数似然 是贝叶斯网的参数个数 学习 结构 7 5贝叶斯网 推断 学习 贝叶斯网 AIC BIC 搜索最优贝叶斯网络结构是NP难问题 1 12log 若贝叶斯网的结构G固定 则评分函数 的第一项为常数 此时最小化评分函数等价于对参数 的极大似然估计 一旦结构固定 由上节可知 网络中的条件独立情况就全可获得同时 参数 可以直接在训练集D上通过计数获得 即 为了最小化评分函数 只需对网络结构进行搜索 而候选结构的最优参数可以直接在训练集上计算得到 学习 结构 7 5贝叶斯网 推断 推断 贝叶斯网 推断 inference 基于已知属性变量的观测值 推测其他属性变量的取值已知属性变量的观测值称为 证据 evidence 精确推断 直接根据贝叶斯网定义的联合概率分布来精确计算后验概率 NP难 近似推断 降低精度要求 在有限时间内求得近似解常见做法 吉布斯采样 Gibbssampling 变分推断 variationalinference 学习 结构 7 5贝叶斯网 推断 推断吉布斯采样思想 贝叶斯网 随机产生一个与证据E e一致的样本q0作为初始点例如 证据E e 色泽 敲声 根蒂 青绿 浊响 蜷缩 查询目标Q q 好瓜 甜度 是 高 随机产生q0 否 高 进行T次采样 每次采样中逐个考察每个非证据变量 假定所有其他属性取当前值 推断出采样概率 然后根据该概率采样取值 假定经过T次采样的得到与 查询目标 q一致的样本共有nq个 则可近似估算出后验概率 e 学习 结构 7 5贝叶斯网 推断 贝叶斯网 推断吉布斯采样算法 例如 先假定 色泽 青绿 敲声 浊响 根蒂 蜷缩 甜度 高 推断出 好瓜 的采样概率 然后采样 假设采样结果为 好瓜 是 然后根据 色泽 青绿 敲声 浊响 根蒂 蜷缩 好瓜 是 推断出 甜度 的采样概率 然后采样 假设采样结果为 甜度 高 证据E e 色泽 敲声 根蒂 青绿 浊响 蜷缩 查询目标Q q 好瓜 甜度 是 高 图形绘制 图片处理 图表设计 典型案例 贝叶斯决策论 Chapter7 极大似然估计 朴素贝叶斯分类器 半朴素贝叶斯分类器 贝叶斯网 EM算法 机器学习 7 6EM算法 如何处理 未观测到的 变量 例如 西瓜已经脱落的根蒂 无法看出是 蜷缩 还是 坚挺 则训练样本的 根蒂 属性变量值未知未观测变量 隐变量 latentvariable 令X表示已观测变量