6. 贝叶斯分类器
文章链接
6.1 贝叶斯决策论
6.1.1 概念
贝叶斯分类器是一类分类算法的总称,贝叶斯定理是这类算法的核心,因此统称为贝叶斯分类。
贝叶斯决策论通过相关概率已知的情况下利用误判损失来选择最优的类别分类。
6.1.2 数学准备
1) 先验概率和后验概率
概念
先介绍两个概念:先验概率(prior probability)和后验概率(posterior probability)。
先验概率 是指在事件未发生时,估计该事件发生的概率。比如投掷一枚匀质硬币,“字”朝上的概率。
后验概率是指基于某个发生的条件事件,估计某个事件的概率,它是一个条件概率。比如一个盒子里面有5个球,两个红球,三个白球,求在取出一个红球后,再取出白球的概率。
例子介绍
例一
玩英雄联盟占到中国总人口的60%,不玩英雄联盟的人数占到40%:
为了便于数学叙述,这里我们用变量X来表示取值情况,根据概率的定义以及加法原则,我们可以写出如下表达式:
P(X=玩lol)=0.6;P(X=不玩lol)=0.4,这个概率是统计得到的,或者你自身依据经验给出的一个概率值,我们称其为先验概率(prior probability);
另外玩lol中80%是男性,20%是小姐姐,不玩lol中20%是男性,80%是小姐姐,这里我用离散变量Y表示性别取值,同时写出相应的条件概率分布:
P(Y=男性|X=玩lol)=0.8,P(Y=小姐姐|X=玩lol)=0.2
P(Y=男性|X=不玩lol)=0.2,P(Y=小姐姐|X=不玩lol)=0.8
那么我想问在已知玩家为男性的情况下,他是lol玩家的概率是多少:
依据贝叶斯准则可得:
最后算出的P(X=玩lol|Y=男性)称之为X的后验概率,即它获得是在观察到事件Y发生后得到的
例二
先验概率是 以全事件为背景下,A事件发生的概率,P(A|Ω)
后验概率是 以新事件B为背景下,A事件发生的概率, P(A|B)
全事件一般是统计获得的,所以称为先验概率,没有实验前的概率
新事件一般是实验,如试验B,此时的事件背景从全事件变成了B,该事件B可能对A的概率有影响,那么需要对A现在的概率进行一个修正,从P(A|Ω)变成 P(A|B),
所以称 P(A|B)为后验概率,也就是试验(事件B发生)后的概率
2) 全概率
3) 贝叶斯定理
参考资料
https://www.zhihu.com/question/61298823/answer/1583165405
https://www.zhihu.com/question/19725590
https://www.matongxue.com/madocs/279/
说白了就是一个公式
通用公式
简单公式
对于每个特征x,我们想要知道样本在这个特性x下属于哪个类别,即求后验概率P(c|x)最大的类标记。这样基于贝叶斯公式,可以得到:
出现原因
如果能掌握事情的全部信息,当然能够计算出一个客观概率(古典概率)
但是生活中的大多数决策面临的信息都是不全的,我们手中只有有限的信息,既然无法得到全部信息,我们就在信息有限的情况下,尽可能做出一个好的预测。也就是在主观判断的基础上先估一个值(先验概率),然后根据观察的新的信息不断修正(可能性函数)
例子介绍
例一
你认识一个女孩,突然你知道她喜欢去夜店蹦迪。
假如女孩中十个有一个就是渣女,那么女孩中渣女的比例占全体的0.1,正经女孩的比例占全体的0.9;
0.1 | 0.9 |
---|---|
渣女 | 正经女孩 |
找出正经女孩和渣女蹦迪的概率,我们没有相关数据,但是不要紧,我们可以设定先验概率;
众所周知,蹦迪的女孩经常穿着暴露,经常和陌生男人“不小心”会有敏感部位的肢体接触,
可以断定,是渣女的概率远远超过正经女孩;我们可以预设:
类别 | 爱蹦迪 | 不爱蹦迪 |
---|---|---|
正经女孩 | 0.05 | 0.95 |
渣女 | 0.5 | 0.5 |
一共存在四种可能性:渣女爱蹦迪、渣女不爱蹦迪、正经女孩爱蹦迪、正经女孩不爱蹦迪;它们的面积分别为:0.05、0.05、 0.045、 0.855;
0.1 | 0.9 |
---|---|
渣女爱蹦迪0.05=0.1*0.5 | 正经女孩爱蹦迪0.045=0.05*0.9 |
渣女不爱蹦迪0.05=0.1*0.5 | 正经女孩不爱蹦迪0.855=0.95*0.9 |
作为一个男人,现在你面临的情况是:这个女孩爱蹦迪。这意味着,你观察到了该女孩的某一种行为。这条信息的内容是:“该女孩不蹦迪”的可能性消失了。上面提到,女孩分为“渣女”和“正经女孩”两类,女孩的行为分为“爱蹦迪”和“不爱蹦迪”两类,可能的世界一共分为四种。
在现实世界中,因为已经观测到“爱蹦迪”这一行为,因此“不爱蹦迪”这一行为覆盖的世界就不存在了。在一部分可能性不复存在,而一部分可能性又在现实中受到限制的情况下,概率发生了 变化;
0.1 | 0.9 |
---|---|
渣女爱蹦迪0.05 | 正经女孩爱蹦迪0.045=0.05*0.9 |
最初,4种世界的概率相加之和为1,但是由于不爱蹦迪的可能性不复存在,此时:渣女爱蹦迪、正经女孩爱蹦迪的概率相加之和便不等于1。为此,我们需要保持之前的比例关系,通过回复标准化条件,从而使概率发生变化。
(左边渣女爱蹦迪长边形面积):(右边正经女孩爱蹦迪长边形面积)=0.05:0.045=10:9;
从上面我们可以看出,渣女爱蹦迪的概率为0.5263.这个概率,被称为“贝叶斯概率”。
渣男同理。
数学解释如下:
例二
例三
那贝叶斯定理到底是什么呢?
可见
由条件概率的公式也可以写成
算出来的结果就是事件在样本空间下发生的概率。
先发生再发生的事件
计算事件在样本空间下的概率
那么发生在中的概率
这就是贝叶斯公式
6.1.3 贝叶斯分类器
参考文章
https://zhuanlan.zhihu.com/p/42991859
1) 数学解释
概率知识+对决策带来的损失的认识→最优决策
有种可能的标记,样本分类
是将的样本错误的分类为所带来的损失
基于后验概率可获得将样本分类为所产生的期望损失,即在样本上的条件风险
任务是寻找一个判定标准以最小化风险(即在所有样本上的条件风险的期望)
显然,对每个样本x,若h能最小化条件风险,则总体风险也将最小化,这就产生了贝叶斯判定准则(Bayes decision rule)
为最小化总体风险,只需在每个样本上选择那个能使条件风险最小的类别标记,即
叫做贝叶斯最优分类器,与之对应的总体风险叫做贝叶斯风险,反映分类器所能到达的最好性能
具体来说,若目标是最小化分类错误率,把误判损失可写为
此时条件风险
于是,最小化分类错误率的贝叶斯最优分类器为
即对每个样本x,选择能使后验概率P(c|x)最大的类别标记。
欲使用贝叶斯判定准则来最小化决策风险,首先要获得后验概率P(c|x)。然而,在现实任务中这通常难以直接获得。机器学习所要实现的是基于有限的训练样本集尽可能准确地估计出后验概率P(c|x)。
分类问题被划分成了两个阶段:推断inference阶段和决策decision阶段
- 推断阶段:使用训练数据学习后验概率
- 决策阶段:使用这些后验概率来进行最优的分类
估计后验概率主要有两种策略:
判别式模型(discriminative models):直接对类后验概率p(c|x)进行推断
生成式模型(generative models):对类条件概率P(x|c)和先验概率P(c)进行推断。
其中P(c)是类“先验”(prior)概率;P(x|c)是样本x相对于类标记c的类条件概率(class-conditional probability),或称为“似然”(likelihood);
P(x)是用于归一化的“证据”(evidence)因子。对给定样本x,证据因子P(x)与类标记无关,因此估计P(c|x)的问题就转化为如何基于训练数据D来估计先验P(c)和似然P(x|c)。
类先验概率P(c) 表达了样本空间中各类样本所占的比例。根据大数定律,当训练集包含充足的独立同分布样本时, P(c) 可通过各类样本出现的频率来进行估计.
对类条件概率P(x|c) 来说,由于它涉及关于x 所有属性的联合概率,直接根据样本出现的频率来估计将会遇到严重的困难.
例如,假设样本的d个属性都是二值的,则样本空间将有种可能的取值,在现实应用中,这个值往往远大于训练样本数m,
也就是说,很多样本取值在训练集中根本没有出现,直接使用频率来估计P(x|c)显然不可行,因为"未被观测到"与"出现概率为零"通常是不同的。
2) 具体例子
例子
假设数据
解释如下:
首先我们假定在买商品,商品生产出来优秀1,良好2,不及格3规格。
真实情况 | 优秀1 | 良好2 | 不及格3 |
---|---|---|---|
优秀1 | 损失为0。因为本来就是优秀 | 损失为1.因为优秀的产品,被划分到不良好,卖亏了 | 损失为1.因为优秀的产品被划分到不 |
良好2 | 损失为1,。因为自己卖亏了 | 损失为0,因为本来就是良好 | 损失为1. |
不及格3 | 损失为1,因为不及格的产品被判断为1 | 损失为1.因为本来是不及格变成良好了,对用户是欺骗。降低用户信任度 | 损失为0,因为本来就是不及格 |
变成 | |||
真实情况 | 优秀1 | 良好2 | 不及格3 |
-------- | ---------------- | ---------------- | ---------------- |
优秀1 | |||
良好2 | |||
不及格3 |
代表优秀,代表良好,代表不及格
所以
首先由公式得
同理
看出
数学解释如下
6.2 极大似然估计
参考资料
https://www.matongxue.com/madocs/447/
6.2.1 概念
极大似然估计是估计类条件概率的常用策略
估计类条件概率的一种常用策略是先假定其具有某种确定的概率分布形式,再基于训练样本对概率分布的参数进行估计。
具体地,记关于类别c的类条件概率为,假设具有确定的形式并且被参数向量唯一确定,则我们的任务就是利用训练集D估计参数 。
为明确起见,我们将记为 。
事实上,概率模型的训练过程就是参数估计(parameter estimation) 过程.
对于参数估计,统计学界的两个学派分别提供了不同的解决方案:
- 频率主义学派(Frequentist)认为参数虽然未知,但却是客观存在的固定值,因此,可通过优化似然函数等准则来确定参数值;
- 贝叶斯学派(Bayesian)则认为参数是未观察到的随机变量,其本身也可有分布,因此,可假定参数服从一个先验分布,然后基于观测到的数据来计算参数的后验分布.
本节介绍源自频率主义学派的极大似然估计(Maximum Likelihood Estimation,简称MLE) ,这是根据数据采样来估计概率分布参数的经典方法.
我们假设硬币有两面,一面是“花”,一面是“字”。
一般来说,我们都觉得硬币是公平的,也就是“花”和“字”出现的概率是差不多的。
如果我扔了100次硬币,100次出现的都是“花”。
在这样的事实下,我觉得似乎硬币的参数不是公平的。你硬要说是公平的,那就是侮辱我的智商。
这种通过事实,反过来猜测硬币的情况,就是似然。
而且,我觉得最有可能的硬币的情况是,两面都是“花”:
通过事实,推断出最有可能的硬币情况,就是最大似然估计。
1) 概率vs似然
概率
让我们先来比较下概率和似然。
为了避免和我们想讨论的概率混淆,我们把硬币的“花”出现的概率称为硬币的参数。
已知硬币的参数,就可以去推测抛硬币的各种情况的可能性,这称为概率。
比如已知硬币是公平的,也就是硬币的参数为0.5。
那么我们就可以推测,扔10次硬币,出现5次“花”朝上的概率为(抛硬币遵循二项分布,这个就不多解释了):
似然
正如开头所说,我们对硬币的参数并不清楚,要通过抛硬币的情况去推测硬币的参数,这称为似然。
我们根据朋友圈里两个人突然发在一起的图片。虽然没有发文字。
但是呢??我们根据他们两个人平时的亲密,在一起的图片。
进一步发现,两人在同一个地方跨年:
我觉得最大的可能性,关系的“参数”是“在一起”。
通过证据,对两人的关系的“参数”进行推断,叫做似然,得到最可能的参数,叫做最大似然估计。
2) 最大似然估计
一次实验
我们实验的结果是,10次抛硬币,有6次是“花”。
所谓最大似然估计,就是假设硬币的参数,然后计算实验结果的概率是多少,概率越大的,那么这个假设的参数就越可能是真的。
我们先看看硬币是否是公平的,就用0.5作为硬币的参数,实验结果的概率为:
单独的一次计算没有什么意义,让我们继续往后面看。
再试试用0.6作为硬币的参数,实验结果的概率为:
之前说了,单次计算没有什么意义,但是两次计算进行比较就有意义了。
可以看到:
我们可以认为,0.6作为参数的可能性是0.5作为参数的可能性的1.2倍。
我们设硬币的参数为%22%20aria-hidden%3D%22true%22%3E%0A%3Cg%20class%3D%22mjx-svg-mrow%22%3E%0A%3Cg%20class%3D%22mjx-svg-mi%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-3B8%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E),可以得到似然函数为:
这样我们就可以作图了:
我们可以从图中看出两点:
- 参数为0.6时,概率最大
- 参数为0.5、0.7也是有可能的,虽然可能性小一点
所以更准确的说,似然(现在可以说似然函数了)是推测参数的分布。
而求最大似然估计的问题,就变成了求似然函数的极值。在这里,极值出现在0.6。
如果实验结果是,投掷100次,出现了60次“花”呢?
似然函数为:
用0.5作为硬币的参数,实验结果的概率为:
再试试用0.6作为硬币的参数,实验结果的概率为:
此时:
此时,0.6作为参数的可能性是0.5作为参数的可能性的8倍,新的实验结果更加支持0.6这个参数。
图像为:
多次实验
之前的例子只做了一次实验。只做一次实验,没有必要算这么复杂,比如投掷100次,出现了60次“花”,我直接:
不就好了?
最大似然估计真正的用途是针对多次实验
比如,我有如下的二项分布,%22%20aria-hidden%3D%22true%22%3E%0A%3Cg%20class%3D%22mjx-svg-mrow%22%3E%0A%3Cg%20class%3D%22mjx-svg-mi%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-3B8%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E)为出现"花"的概率(硬币抛10次):
在实际生活中,%22%20aria-hidden%3D%22true%22%3E%0A%3Cg%20class%3D%22mjx-svg-mrow%22%3E%0A%3Cg%20class%3D%22mjx-svg-mi%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-3B8%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E)往往是不知道的,这里你可以看得到,就好像你是上帝一样。
要提醒大家注意的一点,上面的图像只有上帝才能看到的,包括:
- 二次分布的柱状图
- 二次分布的曲线图
- %22%20aria-hidden%3D%22true%22%3E%0A%3Cg%20class%3D%22mjx-svg-mrow%22%3E%0A%3Cg%20class%3D%22mjx-svg-mi%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-3B8%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E)值为多少
我把只有上帝能看到的用虚线表示,用淡一点的颜色表示:
通过多次实验进行最大似然估计
根据上面的二项分布,我进行了6次实验(也就是总共6次,每次抛10次硬币),把实验结果用点的形式标记在图像上。为了方便观察,我把6个点的值用文字表示出来:
上图中的就是6次实验的结果,分别表示:
- 第一次实验,4次出现“花”
- 第二次实验,5次出现“花”
- 第三次实验,5次出现“花”
- 以此类推
我们用表示每次实验结果,因为每次实验都是独立的,所以似然函数可以写作(得到这个似然函数很简单,独立事件的联合概率,直接相乘就可以得到):
表示在同一个参数下的实验结果,也可以认为是条件概率。
下面这幅图,分为两部分,上面除了实验结果外,都是上帝看到的,而下面是通过实验结果,利用似然函数对值的推断:
可以看出,推断出来的%22%20aria-hidden%3D%22true%22%3E%0A%3Cg%20class%3D%22mjx-svg-mrow%22%3E%0A%3Cg%20class%3D%22mjx-svg-mi%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-3B8%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E)值和上帝看到的差不多。之所以有差别是因为实验本身具有二项随机性,相信试验次数越多,推测会越准确。
6.2.2 数学解释
对进行极大似然估计,就是去寻找能最大化上述似然的参数值 。极大似然的思想就是找到那个使得观测数据出现的可能性最大的参数值。
连乘操作易造成下溢,通常使用对数似然(log-likelihood)
此时参数的极大似然估计
这种参数化的方法虽能使类条件概率估计变得相对简单, 但估计结果的准确性严重依赖于所假设的概率分布形式是否符合潜在的真实数据分布.在现实应用中,欲做出能较好地接近潜在真实分布的假设,往往需在一定程度上利用关于应用任务本身的经验知识,否则若仅凭"猜测"来假设概率分布形式,很可能产生误导性的结果.
6.3 朴素贝叶斯估计
资料参考
https://zhuanlan.zhihu.com/p/26262151
https://blog.csdn.net/weixin_39762441/article/details/111159764
6.3.1 概念
朴素朴素贝叶斯分类是贝叶斯分类中最简单,也是常见的一种分类方法。
基于贝叶斯公式来估计后验概率的主要困难在于:类条件概率是所有属性上的联合概率,难以从有限的训练样本直接估计而得。
(基于有限训练样本直接估计联合概率,在计算上斗争会遭遇纽合爆炸问题,在数据上将会遭遇样本稀疏问题,属性数越多,问题越严重.)
为避开这个障碍,朴素贝叶斯分类器(naÏve Bayes classifier)采用了"属性条件独立性假设" (attribute conditional independence assumption): 对已知类别,假设所有属性相互独立.换言之,假设每个属性独立地对分类结果发生影响.
基于属性条件独立性假设
根据式子可以重写为
其中d为属性数目, 为x在第i个属性上的取值。
由于对所有类别来说P(x)相同,因此基于式的贝叶斯判定准则有
这就是朴素贝叶斯分类器的表达式。
朴素贝叶斯的训练过程就是基于训练集D来估计类先验概率P(c),并为每个属性估计条件概率 。
为了避免其他属性携带的信息被训练集中未出现的属性值"抹去',在估计概率值时通常要进行"平滑" (smoothing) ,常用"拉普拉斯修正" (Laplacian correction)。拉普拉斯修正实质上假设了属性值与类别均匀分布。
6.3.2 具体流程
首先看数据集。
然后我们对一个测试集进行分类
编号 | 色泽 | 根蒂 | 敲声 | 纹理 | 脐部 | 触感 | 密度 | 含糖率 | 好瓜 |
---|---|---|---|---|---|---|---|---|---|
测试1 | 青绿 | 蜷缩 | 浊响 | 清晰 | 凹陷 | 硬滑 | 0.697 | 0.460 | ? |
首先我们计算出先验概率P(c),显然有
对每个属性估计条件概率
下面是离散值
下面是连续值
于是,好瓜
由于.我们判断测试1位好瓜
6.3.3 拉普拉斯修正
对于此数据集,对"敲声=清脆”的测试用例。
由于连乘的公式概率值为0,不管其他分类结果如何。结果都是否。不符合常理
所以为了避免其他属性携带的信息被训练集中未出现的属性值"抹去"。常用拉普拉斯修正
令N表示训练集D中可能的类别,表示第i个属性可能的取值数。
所以其中类先验概率
6.4 半朴素贝叶斯分类器
参考资料
https://www.cnblogs.com/wangzhongqiu/p/10412228.html
https://blog.csdn.net/weixin_43649997/article/details/109262144
6.4.1 概念
提出原因
现实情况是属性全部独立基本上是不可能的,而如果完全考虑各属性之间的相关性会大大增加计算复杂度,所以才引入半朴素贝叶斯网络:进一步放松条件独立性假设,即假设部分属性之间存在依赖关系。
解决办法
独依赖估计(One Dependent Estimator,简称ODE):每个其他属性最多只依赖于一个属性,公式如下:
于是,问题的关键变成了如何确定每个属性的父属性。不同的做法产生了不同的独依赖分类器。
- SPODE(Super-Parent ODE)假设所有的属性都依赖于同一个属性,称为超父。
- TAN(Tree Augmented naive Bayes)则在最大带权生成树算法的基础上发展的一种方法。
- AODE(Averaged ODE)是一种集成学习的方法,尝试将每个属性作为超父来构建SPODE,与随机森林的方法有所相似。
下面具体描述一下TAN。
6.4.2 TAN
基于最大带权生成树算法:
流程如下
计算任意属性之间的条件互信息
以属性为结点构件完全图,任意两个结点之间边的权重设置为
构建此完全图的最大带权生成树,挑选根变量,将边置为有向
加入类别结点y,增加从y到每个属性的有向边
条件互信刻画了属性和在已知类别情况下的相关性因此,通过最大生成树算法,TAN实际上仅保留了强相关属性之间的依赖性。
在这里,我们通过将属性条件独立性假设放松为独立依赖假设,获得了泛化性能的提升。那么如果更进一步,考虑属性间的高阶依赖,能否可以进一步提升泛化性能呢?也就是说,将中的扩展为包含k个属性的几个,从而将ODE扩展为KDE.需要注意的是,随着kk的增加,准确地估计概率所需的训练样本数量将以指数级增加。因此,若训练数据非常充分,泛化性能有可能提升;但在有限样本的条件下,则会陷入估计高阶联合概率的泥沼。
6.4.3 AODE
一种基于集成学习机制,更为强大的独依赖分类器
尝试将每个属性作为超父来构建SPODE,将具有足够训练数据支撑的SPODE集成起来作为最终结果。即
显然AODE需估计
6.4.4 例子
例一:书上的
对于这个数据集
例二
数据集如下。判断是否为好的果子
# | 大小 | 颜色 | 形状 | 标签 |
---|---|---|---|---|
1 | 小 | 青色 | 非规则 | 否 |
2 | 大 | 红色 | 非规则 | 是 |
3 | 大 | 红色 | 圆形 | 是 |
4 | 大 | 青色 | 圆形 | 否 |
5 | 大 | 青色 | 非规则 | 否 |
6 | 小 | 红色 | 圆形 | 是 |
7 | 大 | 青色 | 非规则 | 否 |
8 | 小 | 红色 | 非规则 | 否 |
9 | 小 | 青色 | 圆形 | 否 |
10 | 大 | 红色 | 圆形 | 是 |
测试集上要预测的某个样本如下:
# | 大小 | 颜色 | 形状 | 标签 |
---|---|---|---|---|
11 | 大 | 青色 | 圆形 | ? |
采用拉普拉斯修正后的先验概率P(c)的计算公式:
基于类c和类外的依赖属性pai的条件概率计算公式如下:
属性的依赖关系定义如下:
大小的依赖属性为:形状,且属性取值为大时依赖形状为圆形;
颜色不存在依赖属性;
形状的依赖属性为大小,且属性取值为圆形时依赖大小为大;
好果
一般
$P(c=好果)\times P(大小=大|c=好果,形状=圆形) \times P(颜色=青色 | c=好果) \times P(形状=圆形|c=好果,大小=大) $
= 0.025
= 0.0875
因此,测试集上要预测的这个样本和朴素贝叶斯分类器要预测的结果是相同的,都为一般的果子。
6.5 贝叶斯网
参考资料
https://blog.csdn.net/gdp12315_gu/article/details/50002195
6.5.1 概念
1) 贝叶斯网
借助有向无环图来刻画属性之间的依赖关系,并使用条件概率表(Conditional Probability Table)来描述属性的联合概率分布。
一个贝叶斯网B由结构G和参数Θ两部分构成,即。
2) 网络结构网G
网络结构G: 一个有向无环图,其每一个结点对应于一个属性,若两个属性有直接依赖关系,则它们由一条边连接起来。
3) 参数Θ
参数Θ: 描述属性间的直接依赖关系,假设属性在G中的父节点集为,则Θ包含了每个属性的条件概率表。
举个例子
下雪A1是一个原因结点,它会导致堵车A2和摔跤A3。
而我们知道堵车A2和摔跤A3都可能最终导致上班迟到A4。另外如果在路上摔跤严重的话还可能导致骨折A5。这是一个简单的贝叶斯网络的例子。
在贝叶斯网中像A1这样没有输入的结点被称作根结点(root),其他结点被统称为非根结点。
从上图中我们可以看出,节点间的有向路径可以不只一条,一个祖先结点可以通过不同的途径来影响它的后代结点。如我们说下雪可能会导致迟到,而导致迟到的直接原因可能是堵车,也可能是在雪天滑倒了、摔了一跤。这里每当我们说一个原因结点的出现会导致某个结果的产生时,都是一个概率的表述,而不是必然的,这样就需要为每个结点添加一个条件概率。一个节点在其双亲节点(直接的原因接点)的不同取值组合条件下取不同属性值的概率,就构成了该结点的条件概率表。
将结点A1下雪当作证据结点,那么发生A2堵车的概率如何呢?下表给出了相应的条件概率:
A1 | P(A2|A1) | P(A2|A1) |
---|---|---|
堵车 | 不堵车 | |
True-下雪 | 0.8 | 0.2 |
False-不下雪 | 0.1 | 0.9 |
如果有不只一个双亲结点的话,那么情况会变得更为复杂一些,见上图:
由表中可以看出,当堵车A2和摔跤A3取不同的属性值时,导致迟到A4的概率是不同的。
贝叶斯网条件概率表中的每个条件概率的都是以当前结点的双亲结点做为条件集的。
如果一个结点有n个父节点,在最简单的情况下(即每个结点都是二值结点,只有两个可能的属性值:True或者False),那么它的条件概率表有行;
如果每个属性结点有k个属性值,则有行记录,其中每行有k-1项(因为k项概率的总和为1,所以只需知道其中的k-1项,最后一项可以用减法求得),这样该条件概率表将一共有项记录。
6.5.2 结构
参考资料
https://blog.csdn.net/u013058162/article/details/78499713
给定父节点集,贝叶斯网假设每个属性与它的非后裔属性独立,于是,将属性的联合概率分布定义为
贝叶斯网中三个变量之间的典型依赖关系:
- 同父结构:已知,则;未知,则不成立。
- V型结构:已知,则不成立;未知,则成立。
- 顺序结构:x已知,则y⊥z|x成立,但y╨z不成立。
其中,以V型结构为例,边际独立性的验证如下:
6.5.3 学习
若已知结构,只需要学习参数即可,然后估计出条件概率表即可。
但现实中并不知晓网络结构,于是贝叶斯网络就是找出结构最巧当的贝叶斯网络,
常用“评分搜索”的方法来进行结构好坏的评判,就是先定义一个评分函数,然后评估贝叶斯网络与训练数据集的契合程度,然后基于评分函数来寻找最优网络结构。
评分函数是基于信息论的原则,即找到一个能以最短编码长度来描述训练数据的模型。长度包括模型自身的长度和描述该模型所需的参数的字节长度
给定训练集
若
若
若贝叶斯网的网络结构G固定,则评分函数第一项的值为固定值。此时,最小化评分函数就是对进行极大似然估计。
其中是D上的经验分布。
经验分布函数-设是总体X的一组容量为n的样本观察值,将他们从小到大的顺序重新排序
,对于任意实数x,定义函数
从所有可能的网络结构空间搜索最优贝叶斯网结构是一个NP难问题。有两种常用的策略能在有限时间内求得近似解:
- 贪心法,例如从某个网络结构出发,每次调整一条边,直到评分函数值不再降低为止;
- 通过给网络结构施加约束来削减搜索空间,例如将网络结构限定为树形结构等。
6.5.4 推断
6.6 EM算法
参考资料
https://zhuanlan.zhihu.com/p/40991784
https://www.zhihu.com/question/40797593/answer/275171156
6.6.1 概念
资料
EM(Expectation-Maximum)算法也称期望最大化算法,曾入选“数据挖掘十大算法”中,可见EM算法在机器学习、数据挖掘中的影响力。
EM算法是最常见的隐变量估计方法,在机器学习中有极为广泛的用途,例如常被用来学习高斯混合模型(Gaussian mixture model,简称GMM)的参数;隐式马尔科夫算法(HMM)、LDA主题模型的变分推断等等。
例子
以上介绍了考虑属性间有依赖关系时的半朴素贝叶斯分类器。这些(半)朴素贝叶斯分类器,都有一个共同特点:假设训练样本所有属性变量的值都已被观测到,训练样本是完整的。
然后,现实生活中,有时候拿到的数据集缺少某个属性的观测值(这种变量称为隐变量),在这种存在“未观测”变量的情形下,是否仍能对模型参数进行估计呢?
比如,两箱苹果,其中从A箱中取到一个好苹果的概率大于从B箱中取得,如果有一堆苹果来自于A箱和B箱,但是不知道某个苹果来自于A箱还是B箱,进行了5组实验,每组抽取10个苹果,每组抽到的好苹果和一般苹果都记录到纸上,通过这些观测数据,能得出从A或B箱中取到一个好苹果的概率吗?
这个预测,无形中增加了一个隐变量:苹果出处这属性吧(取值:A箱或B箱)。在这种情况下,介绍一种常用的估计类似参数隐变量的利器:Expectation-Maximization 算法(期望最大算法)。EM算法正如它的名字那样每轮迭代经过两步:E步和M步,迭代,直至收敛。
6.6.2 数学准备
1) 极大似然函数
资料参考
https://blog.csdn.net/zengxiantao1994/article/details/72787849
概念
极大似然估计的原理,用一张图片来说明,如下图所示:
极大似然估计提供了一种给定观察数据来评估模型参数的方法,即:“模型已定,参数未知”。通过若干次试验,观察其结果,利用试验结果得到某个参数值能够使样本出现的概率为最大,则称为极大似然估计。
由于样本集中的样本都是独立同分布,可以只考虑一类样本集D,来估计参数向量θ。记已知的样本集为:
似然函数(linkehood function):联合概率密度函数称为相对于的似然函数如下:
如果是参数空间能够使得似然函数最大的值,则是最可能的参数值值,那么就是的极大似然估计量
求解过程
未知参数只有一个(θ为标量)
在似然函数满足连续、可微的正则条件下,极大似然估计量是下面微分方程的解:未知参数只有一个(θ为标量)
未知参数有多个(θ为向量)
则θ可表示为具有S个分量的未知向量:
记梯度算子:
若似然函数满足连续可导的条件,则最大似然估计量就是如下方程的解。
方程的解只是一个估计值,只有在样本数趋于无限多的时候,它才会接近于真实值。
例子
设样本服从正态分布,则似然函数为
他的对数为
求导,得方程组:
联合解得:
2) Jensen不等式
设f是定义域为实数的函数,如果对所有的实数x,f(x)的二阶导数都大于0,那么f是凸函数。
Jensen不等式定义如下:
如果f是凸函数,X是随机变量,那么:.当且仅当X是常量时,该式取等号。其中,E(X)表示X的数学期望。
注:Jensen不等式应用于凹函数时,不等号方向反向。当且仅当x是常量时,该不等式取等号。
例子
图2中,实线f表示凸函数,X是随机变量,有0.5的概率是a,有0.5的概率是b。X的期望值就是a和b的中值,从图中可以看到成立
3) 联合概率
https://blog.csdn.net/libing_zeng/article/details/74625849
一时忘了联合概率、边际概率、条件概率是怎么回事,回头看看。
某离散分布:
联合概率、边际概率、条件概率的关系:
为“XY的联合概率”; 为“X的边际概率”; 为“X基于Y的条件概率”; 为“Y的边际概率”;
从上式子中可以看到: 即:“XY的联合概率”=“X基于Y的条件概率”乘以“Y的边际概率” 这个就是联合概率、边际概率、条件概率之间的转换计算公式。 前面表述的是离散分布,对于连续分布,也差不多。 只需要将“累加”换成“积分”。
6.6.3 例子
资料参考
https://www.cnblogs.com/bigmoyan/p/4550375.html
https://blog.csdn.net/u010834867/article/details/90762296
https://blog.csdn.net/v_july_v/article/details/81708386
最大期望算法经过两个步骤交替进行计算:
- 第一步是计算期望(E),利用对隐藏变量的现有估计值,计算其最大似然估计值;
- 第二步是最大化(M),最大化在E步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个E步计算中,这个过程不断交替进行。
举个例子,抛硬币,有两个硬币,但是两个硬币的材质不同导致其出现正反面的概率不一样,目前我们只有一组观测数据,要求出每一种硬币投掷时正面向上的概率。总共投了五轮,每轮投掷五次,现在先考虑一种简单的情况,假设我们知道这每一轮用的是哪一个硬币去投掷的:
硬币 | 结果 | 统计 |
---|---|---|
A | 正正反正反 | 3正-2反 |
B | 反反正正反 | 2正-3反 |
A | 正反反反反 | 1正-4反 |
B | 正反反正正 | 3正-2反 |
A | 反正正反反 | 2正-3反 |
那么我们拿着这样的一组数据,就可以很轻松的估计出A硬币和B硬币出现正面的概率,如下:
现在把问题变得复杂一点,假设我们不知道每一次投掷用的是哪一种硬币,等于是现在的问题加上了一个隐变量,就是每一次选取的硬币的种类。
硬币 | 结果 | 统计 |
---|---|---|
Unknown | 正正反正反 | 3正-2反 |
Unknown | 反反正正反 | 2正-3反 |
Unknown | 正反反反反 | 1正-4反 |
Unknown | 正反反正正 | 3正-2反 |
Unknown | 反正正反反 | 2正-3反 |
那么现在可以想一想,假设我们把每一次硬币的种类设为z,则这五次实验生成了一个5维的向量,现在问题来了,如果我们要根据观测结果去求出PA,PB,那么首先需要知道z,但是如果用最大似然估计去估计z,又要先求出PA,PB。这就产生了一个循环。那么这个时候EM算法的作用就体现出来了,EM算法的基本思想是:先初始化一个PA,PB,然后我们拿着这个初始化的PA,PB用最大似然概率估计出z,接下来有了z之后就用z去计算出在当前z的情况下的PA,PB是多少,然后不断地重复这两个步骤直到收敛。
有了这个思想之后现在用这个思想来做一下这个例子,
轮数 | 若是硬币A | 若是硬币B |
---|---|---|
1 | 0.00512,即0.2 0.2 0.2 0.8 0.8,3正-2反 | **0.03087,**3正-2反 |
2 | 0.02048,即0.2 0.2 0.8 0.8 0.8,2正-3反 | 0.01323,2正-3反 |
3 | **0.08192,**即0.2 0.8 0.8 0.8 0.8,1正-4反 | 0.00567,1正-4反 |
4 | 0.00512,即0.2 0.2 0.2 0.8 0.8,3正-2反 | **0.03087,**3正-2反 |
5 | **0.02048,**即0.2 0.2 0.8 0.8 0.8,2正-3反 | 0.01323,2正-3反 |
按照最大似然法则: 第1轮中最有可能的是硬币B 第2轮中最有可能的是硬币A 第3轮中最有可能的是硬币A 第4轮中最有可能的是硬币B 第5轮中最有可能的是硬币A
按照最大似然估计,z=(B,A,A,B,A),有了z之后我们反过来重新估计一下PA,PB:
可以看到PA,PB的值已经更新了,假设PA,PB的真实值0.4和0.5,那么你在不断地重复这两步你就会发现PA,PB在不断地靠近这两个真实值。
初始化的PA | 估计出的PA | 真实的PA | 初始化的PB | 估计出的PB | 真实的PB |
---|---|---|---|---|---|
0.2 | 0.33 | 0.4 | 0.7 | 0.6 | 0.5 |
6.6.4 算法推导
参考资料
https://www.cnblogs.com/pinard/p/6912636.html
假设我们有一个样本集,包含m个独立的样本,根据前面极大似然函数的介绍,我们得出
如果我们得到的观察数据有未观察到的隐含数据,此时我们的极大化模型分布p(x,z)的对数似然函数如下:
上面这个式子是没有办法直接求出的。因此需要一些特殊的技巧,我们首先对这个式子进行缩放如下,使用了Jensen不等式
引入了一个未知的新的分布,用到了Jensen不等式:
此时如果要满足Jensen不等式的等号,则有:
由于是一个分部,所以满足
从上面的式子,可以得到
如果,Jensen 不等式包含隐藏数据的对数似然的一个下界,如果我们能够极大化这个下界,则我们也在极大化对数似然。即我们需要极大化下式
上式也就是我们的EM算法的M步,那E步呢?注意到上式中是一个分布,因此是基于条件概率的期望
6.6.5 算法流程
输入:观察数据,联合分布,条件分布,最大迭代次数J
for i in range(J): E步:计算联合分布的条件概率期望
M步:极大化
if 已经收敛,则算法结束