贝叶斯分类器是各种分类器中分类错误概率最小或者在预先给定代价的情况下平均风险最小的分类器。它的设计方法是一种最基本的统计分类方法。其分类原理是通过某对象的先验概率,利用贝叶斯公式计算出其后验概率,即该对象属于某一类的概率,选择具有最大后验概率的类作为该对象所属的类。

注脚

展开查看详情

1.霍轩

2.第七 章 :贝叶斯分类器

3.章节目录 贝叶斯决策论 极大似然估计 朴素贝叶斯分类器 半朴素贝叶斯分类器 贝叶斯网 EM 算法

4.章节目录 贝叶斯决策论 极大似然估计 朴素贝叶斯分类器 半朴素贝叶斯分类器 贝叶斯网 EM 算法

5.贝叶斯决策论 贝叶斯决策论( Bayesian decision theory )是在概率框架下实施决策的基本方法 。 在分类问题情况下,在 所有相关概率都已知的理想情形下,贝叶斯决策考虑如何基于这些概率和误判损失来选择最优的类别标记。

6.贝叶斯决策论 贝叶斯决策论( Bayesian decision theory )是在概率框架下实施决策的基本方法 。 在分类问题情况下,在 所有相关概率都已知的理想情形下,贝叶斯决策考虑如何基于这些概率和误判损失来选择最优的类别标记。 假设有 种可能的类别标记,即 , 是将一个真实标记为 的样本误分类为 所产生的 损失。基于 后验概率 可获得将样本 分类为 所产生的期望损失( expected loss ),即在样本上的“条件风险”( conditional risk ) 我们的任务是寻找一个判定准则 以最小化总体风险

7.贝叶斯决 策论 显然,对每个样本 ,若 能最小化条件风险 , 则总体风险 也 将被最小化 。

8.贝叶斯决 策论 显然,对每个样本 ,若 能最小化条件风险 , 则总体风险 也 将被最小化 。 这 就产生了贝叶斯判定准则( Bayes decision rule ): 为最小化总体风险,只需在每个样本上选择那个能使条件风险 最小的类别标记, 即 此时,被称为贝叶斯最优分 类器 (Bayes optimal classifier ) ,与之对应的总体风险 称为贝叶斯风险 (Bayes risk) 反映了分类起所能达到的最好性能,即通过机器学习所能产生的模型精度的理论上限。

9.贝叶斯决策论 具体来说, 若目标是最小化分类错误率,则误判损失 可写 为

10.贝叶斯决策论 具体来说, 若目标是最小化分类错误率,则误判损失 可写 为 此时条件风险

11.贝叶斯决策论 具体来说, 若目标是最小化分类错误率,则误判损失 可写 为 此时条件风险 于是,最小化分类错误率的贝叶斯最有分类器 为 即对每个样本 , 选择能使后验 概率 最大 的类别 标记。

12.贝叶斯决策论 不难看出,使用贝叶斯判定准则来最小化决策风险,首先要获得后验 概率 。 然而,在 现实 中通常难以直接获得。机器 学习所要实现的是基于有限的训练样本尽可能准确地估计出后验 概率 。 主要有两种策略: 判别式模型( discriminative models ) 给 定 ,通过直接建模 , 来 预测 决策树, BP 神经网络,支持向 量机 生成式 模型( generative models ) 先 对联合概率分布 建模,再由此 获得 生成式模型考虑

13.贝叶斯决策论 生成式模型

14.贝叶斯决策论 生成式模型 基于贝叶斯定理, 可写成

15.贝叶斯决策论 生成式模型 基于贝叶斯定理, 可写成 先验概率 样本空间中各类样本所占的比例,可通过各类样本出现的频率估计(大数定理)

16.贝叶斯决策论 生成式模型 基于贝叶斯定理, 可写成 先验概率 样本空间中各类样本所占的比例,可通过各类样本出现的频率估计(大数定理) “证据” ( evidence ) 因子,与类标记无关

17.贝叶斯决策论 生成式模型 基于贝叶斯定理, 可写成 先验概率 样本空间中各类样本所占的比例,可通过各类样本出现的频率估计(大数定理) “证据” ( evidence ) 因子,与类标记无关 类标记 相对于样本 的 “ 类条件概率 ” ( class-conditional probability ), 或称“似然”。

18.贝叶斯决策论 生成式模型 基于贝叶斯定理, 可写成 先验概率 样本空间中各类样本所占的比例,可通过各类样本出现的频率估计(大数定理) “证据” ( evidence ) 因子,与类标记无关 类标记 相对于样本 的 “ 类条件概率 ” ( class-conditional probability ), 或称“似然”。

19.极大似然估计 估计类条件概率的常用 策略:先假定其具有某种确定的概率分布形式,再基于训练样本对概率分布参数 估计。 记关于类别 的 类条件概率为 , 假设 具有 确定的形式被参数 唯一确定,我们的任务就是利用训练集 估计参数

20.极大似然估计 估计类条件概率的常用 策略:先假定其具有某种确定的概率分布形式,再基于训练样本对概率分布参数 估计。 记关于类别 的 类条件概率为 , 假设 具有 确定的形式被参数 唯一确定,我们的任务就是利用训练集 估计参数 概率 模型的训练过程就是参数估计过程,统计学界的两个学派提供了不同的方案: 频率主义学派 ( frequentist ) 认为参数虽然未知,但却存在客观值,因此可通过优化似然函数等准则来确定参数值 贝叶斯学派 (Bayesian) 认为参数是未观察到的随机变量、其本身也可由分布,因此可假定参数服从一个先验分布,然后基于观测到的数据计算参数的后验分布。

21.极大似然估计 令 表示训练集中第 类样本的组合的集合,假设这些样本是独立的,则参数 对于数据集 的似然 是 对 进行极大似然估计,寻找能最大化似然 的参数值 。直观上看,极大似然估计是试图在 所有可能的取值中,找到一个使数据出现的“可能性”最大值。

22.极大似然估计 令 表示训练集中第 类样本的组合的集合,假设这些样本是独立的,则参数 对于数据集 的似然 是 对 进行极大似然估计,寻找能最大化似然 的参数值 。直观上看,极大似然估计是试图在 所有可能的取值中,找到一个使数据出现的“可能性”最大值。 式 (7.9) 的连乘操作易造成下溢, 通常使用对数 似然 (log-likelihood) 此时 参数 的极大似然估计 为

23.极大似然估计 例如,在连续属性情形下,假设概率密度函数 ,则参数 和 的极大似然估计为 也就是说,通过极大似然法得到的正态分布均值就是样本均值,方差就是 的均值,这显然是一个符合直觉的结果。 需注意的是,这种参数化的方法虽能使类条件概率估计变得相对简单,但估计结果的准确性严重依赖于所假设的概率分布形式是否符合潜在的真实数据分布。

24.极大似然估计 例如,在连续属性情形下,假设概率密度函数 ,则参数 和 的极大似然估计为 也就是说,通过极大似然法得到的正态分布均值就是样本均值,方差就是 的均值,这显然是一个符合直觉的结果。 需注意的是,这种参数化的方法虽能使类条件概率估计变得相对简单,但估计结果的准确性严重依赖于所假设的概率分布形式是否符合潜在的真实数据分布。

25.朴素贝叶斯分类器 估计 后验概率 主要 困难:类条件概率 是所有属性上的联合 概率难以从有限的训练样本估计获得。 朴素贝叶斯 分类器 (Naïve Bayes Classifier) 采用 了“属性条件独立性假设 ” (attribute conditional independence assumption) : 每个属性独立地对分类结果发生 影响。 基于属性条件独立性假设 , (7.8) 可 重写 为 其中 为 属性数目, 为 在第 个属性上的取值。

26.朴素贝叶斯分类器

27.朴素贝叶斯分类器 由于 对所有类别来说 相同,因此 基于式 (7.6) 的贝叶斯 判定准则有 这就是朴素贝叶斯分类起的表达式子

28.朴素 贝叶斯分类器 朴素 贝叶斯分类器的训练器的训练过程就是基于训练集 估计类先验概率 并为每个属性估计条件概率 。 令 表示训练集 中第 类样本组合的集合,若有充足的独立同分布样本,则可容易地估计出类先验概率 对离散属性而言,令 表示 中在第 个属性上取值为 的样本组成的集合,则条件概率 可估计为 对连续属性而言可考虑概率密度函数,假定 ,其中 和 分别是第 类样本在第 个属性上取值的均值和方差,则有

29.朴素贝叶斯分类器 例子:用西瓜数据集 3.0 训练一个朴素贝叶斯分类器,对测试例“测 1 ”进行分类 (p151, 西瓜数据集 p84 表 4.3)

30.拉普拉斯修正 若某个属性值在训练集中没有与某个类同时出现过,则直接计算会出现问题, . 比如“敲声 = 清脆”测试例,训练集中没有该样例,因此连乘式计算的概率值为 0 ,无论其他属性上明显像好瓜,分类结果都是“好瓜 = 否”,这显然不 合理 。

31.拉普拉斯修正 若某个属性值在训练集中没有与某个类同时出现过,则直接计算会出现问题, . 比如“敲声 = 清脆”测试例,训练集中没有该样例,因此连乘式计算的概率值为 0 ,无论其他属性上明显像好瓜,分类结果都是“好瓜 = 否”,这显然不 合理 。 为了避免其他属性携带的信息被训练集中未出现的属性值“抹去”,在估计概率值时通常要进行“拉普拉斯修正”( Laplacian correction ) 令 表示训练集 中可能的类别数, 表示第 个属性可能的取值数 ,则式 ( 7.16 ) 和 ( 7.17 ) 分别修正为 现实任务中,朴素贝叶斯分类器的使用:速度要求高,“查表”;任务数据更替频繁,“懒惰学习 ” (lazy learning) ; 数据不断增加,增量 学习等等 。

32.拉普拉斯修正 若某个属性值在训练集中没有与某个类同时出现过,则直接计算会出现问题, . 比如“敲声 = 清脆”测试例,训练集中没有该样例,因此连乘式计算的概率值为 0 ,无论其他属性上明显像好瓜,分类结果都是“好瓜 = 否”,这显然不 合理 。 为了避免其他属性携带的信息被训练集中未出现的属性值“抹去”,在估计概率值时通常要进行“拉普拉斯修正”( Laplacian correction ) 令 表示训练集 中可能的类别数, 表示第 个属性可能的取值数 ,则式 ( 7.16 ) 和 ( 7.17 ) 分别修正为 现实任务中,朴素贝叶斯分类器的使用:速度要求高,“查表”;任务数据更替频繁,“懒惰学习 ” (lazy learning) ; 数据不断增加,增量 学习等等 。

33.半朴素贝叶斯分类器 为了降低贝叶斯公式中估计后验概率的困难,朴素贝叶斯分类器采用的属性条件独立性假设;对属性条件独立假设记性一定程度的放松,由此产生了一类称为“半朴素贝叶斯分类器 ” ( semi-naïve Bayes classifiers )

34.半朴素贝叶斯分类器 为了降低贝叶斯公式中估计后验概率的困难,朴素贝叶斯分类器采用的属性条件独立性假设;对属性条件独立假设记性一定程度的放松,由此产生了一类称为“半朴素贝叶斯分类器 ” ( semi-naïve Bayes classifiers ) 半朴素贝叶斯分类器最常用的一种策略:“独依赖估计” (One-Dependent Estimator, 简称 ODE) ,假设每个属性在类别之外最多仅依赖一个其他属性,即 其中 为属性 所依赖的属性,称为 的父属性 对每个属性 ,若其父属性 已知,则可估计概值 ,于是问题的关键转化为如何确定每个属性的父属性

35.SPODE 最直接的做法是假设所有属性都依赖于同一属性,称为“超父” (super- parenet ) ,然后通过交叉验证等模型选择方法来确定超父属性,由此形成了 SPODE (Super-Parent ODE) 方法。 图 7.1 朴素贝叶斯分类器与两种半朴素分类器所考虑的属性依赖关系 在图 7.1 (b) 中, 是超父属性。

36.TAN TAN (Tree augmented Naïve Bayes) [Friedman et al., 1997] 则在最大带权生成树 (Maximum weighted spanning tree) 算法 [Chow and Liu, 1968] 的基础上,通过以下步骤将属性间依赖关系简约为图 7.1 (c) 。 计算任意两个属性之间的条件互信息 (conditional mutual information) 以属性为结点构建完全图,任意两个结点之间边的权重设为 构建此完全图的最大带权生成树,挑选根变量,将边设为有 向; 加入类别节点 y ,增加从 y 到每个属性的有向边。

37.AODE AODE (Averaged One-Dependent Estimator) [Webb et al. 2005] 是一种基于集成学习机制、更为强大的分类器 。 尝试将每个属性作为超父构建 SPODE 将具有足够训练数据支撑的 SPODE 集群起来作为最终 结果 其中 , 是在第 个属性上取值 的样本的集合, 为阈值 常数 其中, 是在第 个属性上取值数, 是类别为 且在第 个属性上取值为 的样本集合,

38.AODE AODE (Averaged One-Dependent Estimator) [Webb et al. 2005] 是一种基于集成学习机制、更为强大的分类器 。 尝试将每个属性作为超父构建 SPODE 将具有足够训练数据支撑的 SPODE 集群起来作为最终 结果 其中 , 是在第 个属性上取值 的样本的集合, 为阈值 常数 其中, 是在第 个属性上取值数, 是类别为 且在第 个属性上取值为 的样本集合,

39.贝叶斯网 贝叶斯网 ( Bayesian network ) 亦称“信念网” ( brief network ) ,它借助有向无 环图 ( Directed Acyclic Graph, DAG ) 来刻 画属性间的依赖关系,并使用条件概率 表 ( Conditional Probability Table, CPT ) 来表述属性的联合概率分布 。

40.贝叶斯网 贝叶斯网 ( Bayesian network ) 亦称“信念网” ( brief network ) ,它借助有向无 环图 ( Directed Acyclic Graph, DAG ) 来刻 画属性间的依赖关系,并使用条件概率 表 ( Conditional Probability Table, CPT ) 来表述属性的联合概率分布 。 图 7.2 西瓜问题的一种贝叶斯网结构以及属性“根蒂”的条件概率表 从 网络图结构可以看出 -> “色泽”直接依赖于“好瓜”和“甜度 ” 从条件概率表可以得到 -> “ 根蒂”对“甜度”的量化依赖关系 P ( 根蒂=硬挺 | 甜度=高 ) = 0.1

41.贝叶斯网:结构 贝叶斯网有效地表达了属性间的条件独立性。给定父结集,贝叶斯网假设每个属性与他的非后裔属性独立。 将属性 的 联合概率分布定义 为 图 7.2 的联合概率分布定义为 : 显然 , 和 在给定 的取值时独立, 和 在给定 的取值时独立 ,记为 和 。

42.贝叶斯网:结构 贝叶斯网中三个变量之间的典型依赖关系 : 同父结构 V 型结构 顺序 结构

43.贝叶斯网:结构 贝叶斯网中三个变量之间的典型依赖关系 : 分析有向图中变量间的条件独立性,可使用“有向分离 ” ( D-separation ) V 型结构父结点相连 有向边变成无向边 由此产生的图称为道德 图 ( moral graph) 同父结构 V 型结构 顺序 结构 ( 好瓜 ) ( 敲声 ) ( 甜度 ) ( 色泽 ) ( 根蒂 )

44.贝叶斯网:学习 贝叶斯网络首要任务:根据训练 集找 出结构最“恰当”的贝叶斯网 。 我们用评分 函数评估 贝叶斯网与训练数据的契合程度 。 “最小描述长度”( Minimal Description Length, MDL )综合编码长度(包括描述网路和编码数据)最 短

45.贝叶斯网:学习 贝叶斯网络首要任务:根据训练 集找 出结构最“恰当”的贝叶斯网 。 我们用评分 函数评估 贝叶斯网与训练数据的契合程度 。 “最小描述长度”( Minimal Description Length, MDL )综合编码长度(包括描述网路和编码数据)最 短 给定训练 集 , 贝叶斯网 在 上 的 评价 函数可以写为 其中 , 是贝叶斯网的参数个数 ; 表示 描述每个 参数 ; 所 需的字节数, 而 是贝叶斯网的对数似然。

46.贝叶斯网 :推断 通过已知变量观测值来推测待推测查询变量的过程称为“推断 ” ( inference ),已知变量观测值称为“证据 ” ( evidence ) 。 最理想的是根据贝叶斯网络定义的联合概率分布来精确计算后验概率 ,在 现实应用中,贝叶斯网的近似推断常使用吉布斯采样 (Gibbs sampling) 来完成 。

47.贝叶斯网 :推断 通过已知变量观测值来推测待推测查询变量的过程称为“推断 ” ( inference ),已知变量观测值称为“证据 ” ( evidence ) 。 最理想的是根据贝叶斯网络定义的联合概率分布来精确计算后验概率 ,在 现实应用中,贝叶斯网的近似推断常使用吉布斯采样 (Gibbs sampling) 来完成 。 吉布斯采样随机产生一个与证据 一致的样本 作为初始点,然后每步从当前样本出发产生下一个样本。假定经过 次采样的得到与 一致的样本共有 个,则可近似估算出后验概率 吉布斯采样可以看做,每一步仅依赖于前一步的状态,这是一个“马尔可夫链” (Markov Chain) 。更多马尔可夫链和吉布斯采样内容参见 14.5 章节。

48.贝叶斯网:推断 图 7.5 吉布斯采样算法

49.贝叶斯网:推断 图 7.5 吉布斯采样算法

50.EM 算法 “不完整”的样本:西瓜已经脱落的根蒂,无法看出是“蜷缩”还是 “坚挺” , 则 训练样本的“根蒂”属性变量值未知,如何计算 ?

51.EM 算法 “不完整”的样本:西瓜已经脱落的根蒂,无法看出是“蜷缩”还是 “坚挺” , 则 训练样本的“根蒂”属性变量值未知,如何计算 ? 未观测的变量称为“隐变量” ( latent variable ) 。 令 表示 已观测变量集 , 表示 隐变量集,若预对模型参数 做 极大似然估计, 则应最大化对数似然 函数

52.EM 算法 “不完整”的样本:西瓜已经脱落的根蒂,无法看出是“蜷缩”还是 “坚挺” , 则 训练样本的“根蒂”属性变量值未知,如何计算 ? 未观测的变量称为“隐变量” ( latent variable ) 。 令 表示 已观测变量集 , 表示 隐变量集,若预对模型参数 做 极大似然估计, 则应最大化对数似然 函数 由于 是 隐变量,上式无法直接求解。此时我们可以通过 对 计算 期望,来最大化已观测数据的对数“边际似然” ( marginal likelihood )

53.EM 算法 EM (Expectation-Maximization ) 算法 [ Dempster et al., 1977] 是常用的估计参数隐变量的利器。 当参数 已知 - > 根据训练数据推断出最优隐变量 的值 ( E 步 ) 当 已知 - > 对 做极大似然估计 ( M 步 )

54.EM 算法 EM (Expectation-Maximization ) 算法 [ Dempster et al., 1977] 是常用的估计参数隐变量的利器。 当参数 已知 - > 根据训练数据推断出最优隐变量 的值 ( E 步 ) 当 已知 - > 对 做极大似然估计 ( M 步 ) 于是 ,以 初始值 为 起点,对式子 (7.35), 可迭代执行以下步骤直至收敛: 基于 推断 隐 变量 的期 望 , 记为 ; 基于 已观测到 变量 和 对参数 做 极大 似然估计,记为 ; 这就是 EM 算法的原型 。

55.EM 算法 进一步 ,若我们不是取 Z 的期望,而是 基于 计算 隐 变量 的概率分布 , 则 EM 算法的两个步骤是: E 步 ( Expectation ): 以当前 参数 推断隐变量分布 , 并计算 对数似然 关于 的期 望 : M 步 ( Maximization ): 寻找参数最大化期望似然,即 EM 算法使用两个步骤交替计算:第一步计算期望 ( E 步 ) ,利用当前估计的 参数值计算 对数似然的参数值;第二步最大化 ( M 步 ) ,寻找能使 E 步产生的似然期望最大化的参数值 …… 直至收敛到全局最优解 。

56.小结 贝叶斯决策论 极大似然估计 朴素贝叶斯分类器 半朴素贝叶斯分类器 贝叶斯网 EM 算法