[西瓜书]学习笔记五:贝叶斯分类器

贝叶斯:机遇理论中一个问题的解

贝叶斯基础

在《概率论与数理统计》当中,我们学过了贝叶斯公式。公式表示如下:

  • 先验概率: 根据以往经验和分析得到的概率。
  • 后验概率:后验概率是基于新的信息,修正原来的先验概率后所获得的更接近实际情况的概率估计。

公式的具体表征就是条件概率的转换,利用先验概率和后验概率对条件概率重新评估。

在贝叶斯出现之前,都是以频率派都思维来进行思考。

  • 频率派把需要推断的参数θ看做是固定的未知常数,即概率虽然是未知的,但最起码是确定的一个值,同时,样本X是随机的,所以频率派重点研究样本空间,大部分的概率计算都是针对样本X的分布。

  • 贝叶斯派的观点则截然相反,他们认为参数是随机变量,而样本X 是固定的,由于样本是固定的,所以他们重点研究的是参数的分布。

在贝叶斯公式中,若将上述定义中样本空间的划分Bi看做为类标,A看做为一个新的样本,则很容易将条件概率理解为样本A是类别Bi的概率。在机器学习训练模型的过程中,往往我们都试图去优化一个风险函数,因此在概率框架下我们也可以为贝叶斯定义“条件风险”(conditional risk)。

我们需要寻找一个判定准则最小化所有样本的条件风险总和,因此就有了贝叶斯判定准则(Bayes decision rule):为最小化总体风险,只需在每个样本上选择那个使得条件风险最小的类标。

即对于每个样本x,选择其后验概率P(c|x)最大所对应的类标,能使得总体风险函数最小,从而将原问题转化为估计后验概率P(c|x)。一般这里有两种策略来对后验概率进行估计:

  • 判别式模型:直接对 P(c|x)进行建模求解。例我们前面所介绍的决策树、神经网络、SVM都是属于判别式模型。
  • 生成式模型:通过先对联合分布P(x,c)建模,从而进一步求解 P(c|x)。

贝叶斯公式属于生成式模型,由此对于给定的样本x,P(x)与类标无关,P(c)称为类先验概率,p(x|c)称为类条件概率。这时估计后验概率P(c|x)就变成为估计类先验概率和类条件概率的问题。

为了更好的理解贝叶斯在分类中的应用,给出一个wiki上的例子进行说明。

对于类先验概率P(c),p(c)就是样本空间中各类样本所占的比例,根据大数定理(当样本足够多时,频率趋于稳定等于其概率),这样当训练样本充足时,p(c)可以使用各类出现的频率来代替。因此只剩下类条件概率p(x|c),它表达的意思是在类别c中出现x的概率,它涉及到属性的联合概率问题,若只有一个离散属性还好,当属性多时采用频率估计起来就十分困难,因此这里一般采用极大似然法进行估计。

极大似然估计

极大似然估计(Maximum Likelihood Estimation,简称MLE),是一种根据数据采样来估计概率分布的经典方法。常用的策略是先假定总体具有某种确定的概率分布,再基于训练样本对概率分布的参数进行估计。运用到类条件概率p(x|c)中,假设p(x|c)服从一个参数为θ的分布,问题就变为根据已知的训练样本来估计θ。极大似然法的核心思想就是:估计出的参数使得已知样本出现的概率最大,即使得训练数据的似然最大。

贝叶斯分类器的训练过程就是参数估计。总结最大似然法估计参数的过程,一般分为以下四个步骤:

  • 1.写出似然函数;
  • 2.对似然函数取对数,并整理;
  • 3.求导数,令偏导数为0,得到似然方程组;
  • 4.解似然方程组,得到所有参数即为所求。

采用最大似然法估计参数的效果很大程度上依赖于作出的假设是否合理,是否符合潜在的真实数据分布。这就需要大量的经验知识,搞统计越来越值钱也是这个道理,大牛们掐指一算比我们搬砖几天更有效果。

朴素贝叶斯分类器

基于贝叶斯公式来估计后验概率p(x|c)的主要问题在于,首先需要根据经验来假设联合概率分布,其次当属性很多时,训练样本往往覆盖不够,参数的估计会出现很大的偏差。朴素贝叶斯分类器(naive Bayes classifier)采用了“属性条件独立性假设”,即样本数据的所有属性之间相互独立。因此贝叶斯式转换为下式。

西瓜书给出了一个分类的例子。朴素贝叶斯分类器的训练过程就是根据训练集D来估计类先验概率P(c)。离散属性考虑对应样本的频率,连续属性考虑其概率密度函数。计算好每个概率值后累乘得到相应类别的概率。

需要注意的是:若某个属性值在训练集中和某个类别没有一起出现过(例子当中的敲声),这样会抹掉其它的属性信息,因为该样本的类条件概率被计算为0。因此在估计概率值时,常常用进行平滑(smoothing)处理,拉普拉斯修正(Laplacian correction)就是其中的一种经典方法,具体计算方法如下:

当训练集越大时,拉普拉斯修正引入的影响越来越小。对于贝叶斯分类器,模型的训练就是参数估计,因此可以事先将所有的概率储存好,当有新样本需要判定时,直接查表计算即可。

半朴素贝叶斯

为了降低后验概率p(x|c)的计算困难,在朴素贝叶斯当中引入了属性条件独立性的假设,然而这在现实当中很难成立。对独立条件进行一定程度上的放松,就是“半朴素贝叶斯分类器”的学习方法。

假定每个属性只依赖另外的一个。这样,更能准确描述真实情况。式改写如下。

现在问题就转换为确定每个属性的父属性,不同的做法产生不同的分类器。

那么确定如何依赖?

  1. SOPDE方法。这种方法是假定所有的属性都依赖于共同的一个父属性。

  2. TAN方法。每个属性依赖的另外的属性由最大带权生成树来确定。

    (1). 先求每个属性之间的互信息来作为他们之间的权值。

    (2)构件完全图。权重是刚才求得的互信息。然后用最大带权生成树算法求得此图的最大带权的生成树。

    (3)找一个根变量,然后依次将图变为有向图。

    (4)添加类别y到每个属性的的有向边。

贝叶斯网

贝叶斯网络借助有向无环图(DAG)来刻画属性之间的依赖关系,使用条件概率表(CPT)描述联合条件概率分布。

其表达式为:

其中x表示其属性集

结构

贝叶斯网络有三种依赖关系,如下图所示。

  • 第一种同父结构,被看作 ,即在c给定的条件下,a,b被阻断(blocked),是独立的。
  • 第二种V型结构,,即在c未知的条件下,a、b被阻断(blocked),是独立的。
  • 第三种顺序结构,, 即:在c给定的条件下,a,b被阻断(blocked),是独立的。(这个就是马尔可夫链)

学习

若网络结构(属性间依赖关系)已知,只需要对样本计数,估计每个结点条件概率即可完成学习过程。第一步就是找到最恰当的贝叶斯网。

“评分搜索”是求解的常用方法。先定义评分函数,通常基于信息论准则,它将学习问题看作数据压缩任务。它的目标数选择综合编码长度最短的贝叶斯网络,称为“最小长度描述”(MDL)准则。

给定训练集D和贝叶斯网B,评分函数可些为:

其中|B|为贝叶斯网的参数个数,$f(\theta)$表示每个参数所需字节数,

表示贝叶斯网的对数似然。由此学习任务转化为一个优化任务,寻找一个贝叶斯网B使得评分函数s(B|D)最小。

根据$f(\theta)$的不同可以得到不同的评分函数。从所有网络结构空间中搜素最优贝叶斯网结构是一个NP难问题,难以快速求解。常用的策略有贪心法和网络结构约束法。

推断

训练完成之后,就能用来推断,即通过一些属性变量的值来推测其他属性的取值。最理想的情况是根据贝叶斯的联合概率分布来精确计算后验概率,然而这样的“精确推断”是NP难的问题。即在网络结点多连接稠密时,需要借助“近似推断”,在有限时间求得近似解。

贝叶斯网的近似推断常常使用吉布斯采样来完成,这是一种随机采样方法。它先随机产生一个与证据E=e一致的样本$q^{0}$作为初始点,然后从当前样本出发产生下一个样本。实质上是在样本子空间中进行随机漫步的过程,是一个马尔可夫链。当第t步($t \rightarrow \infty $)时必趋于一个平稳分布,采样算法流程如下图。

由于马尔可夫链需要长时间才能趋于平稳分布,因此吉布斯采样收敛速度较慢。且贝叶斯网中存在极端概率会导致吉布斯采样错误估计。

EM算法

EM算法是一种迭代算法,主要应用于训练集样本不完整即存在隐变量时的情形(例如某个属性值未知),通过其独特的“两步走”策略能较好地估计出隐变量的值。每次迭代有两步组成:E步,求期望;M步,求极大值。因此被称为期望极大算法(expectation maximization algorithm)。

基本思想

若样本服从的分布参数θ已知,则可以根据已观测到的训练样本推断出隐变量Z的期望值(E步),若Z的值已知则运用最大似然法估计出新的θ值(M步)。重复这个过程直到Z和θ值不再发生变化。

简单来讲:假设我们想估计A和B这两个参数,在开始状态下二者都是未知的,但如果知道了A的信息就可以得到B的信息,反过来知道了B也就得到了A。可以考虑首先赋予A某种初值,以此得到B的估计值,然后从B的当前值出发,重新估计A的取值,这个过程一直持续到收敛为止。

现在再来回想聚类的代表算法K-Means:【首先随机选择类中心=>将样本点划分到类簇中=>重新计算类中心=>不断迭代直至收敛】,不难发现这个过程和EM迭代的方法极其相似,事实上,若将样本的类别看做为“隐变量”(latent variable)Z,类中心看作样本的分布参数θ,K-Means就是通过EM算法来进行迭代的,与我们这里不同的是,K-Means的目标是最小化样本点到其对应类中心的距离和,上述为极大化似然函数。

推导

令X表示观测变量集,Z表示隐变量集,$\Theta$表示模型参数。最大化对数似然

由于Z是隐变量,无法直接求解,通过对Z计算期望来最大化已观测数据的对数边际似然。

参考链接及书目

统计学习方法,李航

机器学习,周志华

https://blog.csdn.net/zdy0_2004/article/details/41096141?tdsourcetag=s_pctim_aiomsg

https://www.cnblogs.com/zhoulujun/p/8893393.html?tdsourcetag=s_pctim_aiomsg