[关闭]
@frank-shaw 2015-08-03T18:41:32.000000Z 字数 12119 阅读 4992

3月在线学习班第10课笔记--贝叶斯网络

机器学习


课程基础--贝叶斯公式及其应用

让我们首先来简单复习一下概率方面的基础知识:
条件概率:A,B是两个事件,且P(A)>0,称

P(B|A)=P(AB)P(A)
为在时间A发生的条件下事件B发生的条件概率。

全概率公式:设试验E的样本空间为EAE的事件,B1,B2,...,BnS的一个划分,且P(Bi)>0(i=1,2,...,n),则有

P(A)=i=1nP(A|Bi)P(Bi).

上式被称为全概率公式。该公式适用于某些问题中P(A)不容易求得,但是却容易找到S的一个划分B1,B2,...,Bn,且P(Bi)P(A|Bi)为已知或者容易求得的情况。

贝叶斯公式:由条件概率公式以及全概率公式很容易得到贝叶斯公式:

P(Bi|A)=P(BiA)P(A)=P(A|Bi)P(Bi)ni=1P(A|Bi)P(Bi)

让我们来看一下下面这道题,以加深对贝叶斯公式的理解:

8支步枪中有5支已经校准过,3支未校准。一名射手拿校准过的枪射击,中靶概率为0.8;用未校准的枪射击,中靶概率为0.3;现在从8支枪当中随机取出一支射击,结果中靶,求该枪是已经校准过的概率。
:令A0表示事件枪支未校准,A1表示事件枪支已校准,B表示中靶。那么我们可以得到:

P(A0)=3/8,P(A1)=5/8,P(B|A1)=0.8,P(B|A0)=0.3
现在要求的是P(A1|B)的概率。由贝叶斯公式可得:
P(A1|B)=P(B|A1)P(A1)P(B|A1)P(A1)+P(B|A0)P(A0)=81.63

朴素贝叶斯算法

朴素贝叶斯本身假设是一个较为简单的假设:一个特征出现的概率,与其他特征(条件)独立,即特征独立性。其实就是在给定类别的条件下,特征独立。
为了更好理解朴素贝叶斯的思想,我们以垃圾邮件过滤作为例子结合理解。朴素贝叶斯假设在实际中是一个不严谨的假设,但是将它应用到垃圾邮件过滤中的实际效果却很好。
邮件可以分为垃圾邮件和正常邮件,对应的标签y0,1。假设我们有了1000封邮件作为样本,每封邮件都已经被标记为垃圾邮件或正常邮件。给定第1001封邮件,想要确定它是垃圾邮件还是非垃圾邮件。这就是我们亟待解决的问题。
那么迎面的第一个难题来了,我们如何来表示一封邮件呢?说白了,邮件其实就是一个文档,由字词组成。我们会创建如下特征向量:
朴素贝叶斯文档表示向量
这就好比创建了一个词典向量,当我的邮件出现了词典中的某个词的时候,我就在对应处标记为"1",否则标记为"0"。上面就表示该邮件包含字母"a""buy"而不包含字母"aardvark""aardwolf""zygmurgy"。这是一种用特征向量来表示邮件的方式。

关于词典的创建,一般有两种方法:第一种是使用现成的单词词典,第二种是将样本中所有邮件出现的单词都统计出来,得到词典。

当想要构建模型的时候,我需要表示出P(x|y).假设特征的维数为5000(即此时的词典单词数为5000),则x0,1nn=5000,那么总共有25000个可能的特征向量。由于可能的特征向量过多,对于建模是一个极大的挑战。这个时候我们就是用朴素贝叶斯假设来解决这个问题:假设在给定y的前提下,xi是条件独立的。即

P(x1,x2,...,x5000|y)=P(x1|y)P(x2|y)...P(x5000|y)=i=15000P(xi|y)

这是个很强的假设,要知道使用标准的链式法则表示上面等式左边可是复杂得多。朴素贝叶斯假设意味着就是:即使已知邮件是否是垃圾邮件的前提下,xixj相互没有影响。很显然这个假设是错的,不可能成立,假如你在一封邮件中看到了单词"buy",那么你就会有更大的可能看到"price"。但事实证明,朴素贝叶斯算法对于邮件过滤的工作效果却出奇的好。

使用贝叶斯公式:P(y|x)=P(x|y)P(y)/P(x),这里的x是向量。根据贝叶斯特征条件独立假设,有:

P(x|y)=P(x1,x2,...,x5000|y)=i=15000P(xi|y)

同样根据全概率公式以及贝叶斯特征假设,有:
P(x)=P(x|y=0)+P(x|y=1)=i=15000P(xi|y=0)P(y=0)+i=15000P(xi|y=1)P(y=1)

代入到贝叶斯公式中去,可得新邮件被判为正常邮件的概率:
P(y=1|x)=P(x|y=1)P(y=1)P(x)=5000i=1P(xi|y=1)P(y=1)5000i=1P(xi|y=0)P(y=0)+5000i=1P(xi|y=1)P(y=1)

被判为垃圾邮件的概率为1P(y=1|x)
上式右侧各项的含义如下:
P(y=1)=5000i=11{y(i)=1}5000 5000P(xi|y=1)5000i=11{xi=1 and y(i)=1}5000i=11{y(i)=1} xiP(xi|y=0)5000i=11{xi=1 and y(i)=0}5000i=11{y(i)=0} xi

考虑单词出现次数的垃圾邮件过滤

假设这种情形:如果一封邮件中"buy"出现很多次,这可说明他有更大的可能趋向于垃圾邮件。但是上面的算法没有考虑这个问题。我们来看一个不一样的算法,称为朴素贝叶斯的事件模型,此模型会考虑每个单词出现的频率,它是这样做的:
给定第j封邮件,我们将邮件的每一个词按顺序看作是特征变量xi,即xi指向的是邮件中的第i个词,那么,邮件x(j)=(x(j)1,...,x(j)i,...,x(j)nj)nj表示第j封邮件的词汇总数。另外,x(j)i表示词典的一个索引,假设词典集的元素个数为5000,那么x(j)i{1,2,...,5000}。为了说明地更清楚,假设邮件j的第4个单词是"love","love"在字典中排在2040,那么x(j)4=2040

使用朴素贝叶斯假设,相应的表达式为:

P(y=1|x)=P(x|y=1)P(y=1)P(x)=5000k=1P(k|y=1)P(y=1)5000k=1P(k|y=0)P(y=0)+5000k=1P(k|y=1)P(y=1)

上式右侧各项的含义如下:
P(y=1)=5000i=11{y(i)=1}5000 5000P(k|y=1)5000i=1nij=11{x(i)j=k and y(i)=1}5000i=11{y(i)=1}ni kP(k|y=0)5000i=1nij=11{x(i)j=k and y(i)=0}5000i=11{y(i)=0}ni k

其实,通过物理意义的分析,可以看出两个模型的区别:相同点是--它们都使用了朴素贝叶斯的假设;不同点有:

  1. 特征向量的表示不同,一个没有考虑单词出现的次数,仅仅通过固定的词典向量作为特征向量,另一个则是将单词在词典中的索引作为特征向量,相同的索引号具有可加性,考虑了单词出现的次数;
  2. 特征向量的长度不同。

拉普拉斯平滑

拉普拉斯平滑是为了解决垃圾邮件过滤中的这样一个问题:对于一个已经训练好的朴素贝叶斯模型,来了一封新邮件,有某一个单词"Ye"(该单词在词典中排位设为4567),假设在训练集合中没有出现过这个词,那么就会使得在训练中所得到的参数Px4567|y=1=0Px4567|y=0=0。这样的后果就是使得最终的判别概率为0,即新来的邮件是正常邮件的概率为0,是垃圾邮件的概率也为0。显然这不是一个好的算法应该具有的性质。
拉普拉斯平滑,即给分式的每一项都加上1,使得结果可以接纳更多的可能性。如经过拉普拉斯平滑过后的第一个朴素贝叶斯算法中各个参数变为:
上式右侧各项的含义如下:

P(y=1)=5000i=11{y(i)=1}+15000+2 5000P(xi|y=1)5000i=11{xi=1 and y(i)=1}+15000i=11{y(i)=1}+5000 xiP(xi|y=0)5000i=11{xi=1 and y(i)=0}+15000i=11{y(i)=0}+5000 xi

分子都加1,而分母的添加则是为了保证概率和为1.

对朴素贝叶斯的思考

  1. 如何判断两个文档的距离?
    A:夹角余弦。
  2. 如何判定该分类器的正确率?
    A:可以将m个总样本中的K个作为训练集,m-k个作为测试集。第二种方法是交叉验证。
  3. 编程的限制:小数乘积溢出怎么办?
    A:在计算朴素贝叶斯时,因为连乘的原因,小数乘积有可能溢出,此时转化为使用log可以较好解决问题。

贝叶斯网络

我们把某个研究系统中涉及的随机变量,根据是否条件独立绘制在一个有向图中,就形成了贝叶斯网络。贝叶斯网络(Bayesian Network),又称信念网络(Belief Network),有向无环图模型(directed acyclic graphical model, DAG),是一种概率图模型,于1985年由Judea Pearl首先提出。

一般而言,贝叶斯网络的有向无环图中的结点表示随机变量X1,X2,...,Xn,它们可以是可观察到的变量,或者隐变量、未知参数等。连接两个结点的箭头代表此两个随机变量之间具有因果关系(或非条件独立)。若两个结点间以一个单箭头连接在一起,表示其中一个结点是"因(parents)",另一个是"果(children)",两个结点就会产生一个条件概率值。

好吧,说了这么多概念,让我们来看一例子:
全概率贝叶斯网络
在图中我们看到:结点a作为父亲结点,影响结点b,而结点a和结点b共同影响结点c(也就是说结点c有俩爹)。这是个全连接图模型,我们写下联合概率公式可以表示为:

P(a,b,c)=P(c|a,b)P(b|a)P(a)

在这里,联合概率公式的链式法则展开表达式与上图表达的含义是完全一致的。通过分析可以知道,由贝叶斯网络的图模型来描写联合概率公式时,对每一个结点,如果该结点有父结点,那么将父结点作为条件,写下概率表达式;最终将每个结点的表达式乘起来,即为联合概率公式。即:
P(x1,...,xn)=i=1nP(xi|parents(xi))

上面这个贝叶斯网络是较为理想的全连接图,实际上,很多情况下,一个"正常"的贝叶斯网络是长这样:
贝叶斯网络正常实例
有一些边是缺失的,直观上理解这个"正常"的贝叶斯网络:可以看到,x1,x2x3之间是相互独立的;x6x7x4
我们依照刚刚的经验,对着图可以写下x1,x2,...,x7的联合分布:

P(x1)P(x2)P(x3)P(x4|x1,x2,x3)P(x5|x1,x3)P(x6|x4)P(x7|x4,x5)

相比于使用万能的条件概率的链式法则来展开联合分布,由贝叶斯网络得出来的联合分布会简单很多。这是使用贝叶斯网络的优势之一。

贝叶斯网络的实例

给定如下图所示的贝叶斯网络:
11
其中,各个单词、表达式表示的含义如下:

我们现在想要考察一下,如果我们想要表达这五个结点,应该怎么做呢?以结点D为例,它有两个父结点,C和B。通过分析各种情况,便可得到dyspnoea的一张概率表,如上图的最右下角所示。即假如C=0,B=0,即没有肺癌也没有支气管炎,那么D=0的概率为0.9,即有90%的可能性不会产生呼吸困难。接下去的各种情况以此类推。实际上,只需要用4个数据(表中D=0那一列或者D=1那一列的四个数),就可以完全表示结点D。类似的,完全表示结点X、结点C、结点B、结点S分别需要4、2、2、1个数据。一共需要13个数据就可以完全表示这五个结点。相比于列举所有可能性的情况下需要的数据量25(假设没有任何先验知识),贝叶斯网络可以大大减小计算复杂度。如果结点数增加,那么贝叶斯网络的优越性更加明显:
打印机故障实例
这个打印机故障的实例中,需要的数据量为99个即可完全表达这26个结点,但是没有任何先验知识的情况下有226个数据。

经验总结:每个结点所需要参数的个数:假设某结点的parent数目为M,该结点及其parent的可能取值数为K,那么该结点所需的参数个数为KM(K1)

任何状态下的联合分布计算

在上面吸烟的例子中,我想要知道P(S,C,B¯,X¯,D)的大小,即一个人抽烟、有肺癌、没有支气管炎、没有发现X光异常、会有呼吸困难的概率,怎么计算呢?其实挺简单,我们分析一下各个结点以及其父结点在待求概率中的状态及其概率,代入计算即可得:

P(S,C,B¯,X¯,D)=P(S)P(C|S)P(B¯|S)P(X¯|C,S)P(D|C,B¯)

通过这种方式可以计算出任何状态下该贝叶斯网络的概率。

如果某一种状态缺省了怎么办呢?比如我们想要知道P(S,B¯,X¯,D)的大小,这里并没有出现结点C。此时,我们可以使用类似于全概率计算公式的思想,人为添加结点C,表示为:

P(S,B¯,X¯,D)=P(S,C,B¯,X¯,D)+P(S,C¯,B¯,X¯,D)

然后再对等式右边的两项分开求解,即可。

更多的,我还想知道:在给定一个人抽烟、有肺癌、没有支气管炎、没有发现X光异常的前提下,他会有呼吸困难的概率是多少?这个时候可以根据条件概率公式求解得到:

P(D|S,C,B¯,X¯)=P(D,S,C,B¯,X¯)P(S,C,B¯,X¯)

通过贝叶斯网络判定条件独立

形式一:tail-to-tail
贝叶斯网络的第一种结构形式如下图所示:
条件独立-1
看图可以知道:P(a,b,c)=P(c)P(a|c)P(b|c),而条件概率:P(a,b|c)=P(a,b,c)P(c),两条公式联立,可以得到:

P(a,b|c)=P(a|c)P(b|c)

即:在c给定的条件下,a,b被阻断(blocked),是独立的,称之为tail to tail 条件独立。

形式二:head-to-tail
贝叶斯网络的第二种结构形式如下图所示:
条件独立-2
看图可知:P(a,b,c)=P(a)P(c|a)P(b|c)。又P(a,b|c)=P(a,b,c)P(c),代入可得:

P(a,b|c)=P(a)P(c|a)P(b|c)P(c)=P(a,c)P(b|c)P(c)=P(a|c)P(b|c)

即:在c给定的条件下,a,b被阻断(blocked),是独立的,称之为head to tail条件独立。

形式三:head-to-head
贝叶斯网络的第三种结构形式如下图所示:
条件独立-3
看图可知:P(a,b,c)=P(a)P(b)P(c|a,b)。进一步有:

cP(a,b,c)=cP(a)P(b)P(c|a,b)P(a,b)=P(a)P(b)

即:在c未知的条件下,a,b被阻断(blocked),是独立的,称之为head to head独立。

知道了这三种判断条件独立的形式,让我们用示例来说明:
判断条件独立示例
左图是head-to-tail型,如果以任意一群人作为样本统计,“去过亚洲”和“检查X光的时候出现问题”是有可能有关联的。因为“去过亚洲”可能导致肺结核,而肺结核会导致“检查X光的时候出现问题”。但是假设已知的是一群人都得过肺结核,那么以这群人作为样本统计,“去过亚洲”与“检查X光的时候出现问题”就是独立的了。
右上图是tail-to-tail型,同样以任意一群人作为样本统计,“得肺癌”和“得支气管炎”是有可能有关联的。因为“得肺癌”可能是吸烟导致的,而吸烟同样会导致“得支气管炎”。但是假设已知的是一群人都是吸烟的,那么“得肺癌”与“得支气管炎”就是独立的了。
右下图是head-to-head型,同样以任意一群人作为样本统计,“得肺癌”和“得支气管炎”是有可能有关联的。因为如果我已经观察到某些人有呼吸困难的症状,那么就可以联想到该症状可能是支气管炎引起的,也可能是肺癌引起的。但是假设我观察的一群人并没有表现出呼吸困难的症状(并未获得该信息),那么“得肺癌”与“得支气管炎”就是独立的了。

有向分离(Directed-seperation)
我们想要考察结点集的情况下的条件独立的判断条件。首先定义有向分离的概念:对于任意的结点集A,B,C,考察所有通过A中任意结点到B中任意结点的路径,若要求A,B条件独立,则需要所有的路径都被阻断(即结点集A、B是有向分离的),即满足下列两个前提之一:

如果结点集A、B被结点集C有向分离,那么当结点集Z给定的情况下,结点集A、B是条件独立的。

特殊的贝叶斯网络--马尔科夫模型

形如下图的贝叶斯网络我们称之为马尔科夫模型。
马尔科夫模型图
如上图所示,M个离散结点形成一条链(各个结点只有一个父结点),每一个结点有K个状态,那么根据之前的结论,可以知道描述这M个结点需要的参数个数为K1+(M1)K(K1)(有一个结点不包含父结点,剩余M-1个都包含父结点)。可以知道,这是关于长度M的线性函数。
由有向分离可知,在xi给定的条件下,xi+1x1,x2,...,xi1条件独立。即xi+1的分布状态只和xi有关,和其他变量条件独立,这种顺序演变的随机过程模型,叫做马尔科夫模型,因为其满足马尔科夫性质:

P(Xn+1=x|X0,X1,...,Xn)=P(Xn+1=x|Xn)

马尔科夫毯

一个结点的马尔科夫毯是一个集合,该集合中的结点包括:该结点的父结点、该结点的子结点以及该结点子结点的另外所有父结点(亲家)。在这个集合中的结点都给定的条件下,该结点条件独立与其他所有结点。我们看图:
马尔科夫毯例图
着色背景区域即为结点Cancer的马尔科夫毯。一个结点的马尔科夫毯构成的是这样一个网络,那么所有其他结点构成的马尔科夫毯所构成的将会是一个更大的网络。这将会在以后有机会研究。

贝叶斯网络的构建

假设我们手头上已经有了足够多的数据了,各个数据之间的概率关系也已经有了,那么如何构建一个贝叶斯网络呢?
我们需要一次计算每个变量的有向分离(D-separation)的局部测试结果,综合每个结点得到贝叶斯网络。其中一种直接的算法过程如下:

  • 选择变量的一个合理顺序:X1,X2,...,Xn
  • 对于i=1,...,n,有:
    • 在网络上添加结点Xi
    • X1,X2,...,Xi1中选择Xi的父结点(与Xi有关联的结点),使得
      P(Xi|parent(Xi))=P(X|X1,X2,...,Xi1)

这种做法的关键在于如何选择变量的合理顺序。如果选择得不好,会直接毁了贝叶斯网络。那么如何才能做到变量之间的顺序是合理的呢?在实际的问题中,我们可以根据实际变量间的因果关系逐步插入变量。当然也有很多方法去探讨这个问题的具体做法,在此忽略。

混合(离散+连续)网络

之前我们分析的网络中各结点变量都是离散型的,实际上也有很多网络中的结点变量是连续型的呀?如果混合型结点构成的贝叶斯网络,我们如何求取各概率呢?
混合变量网络
上图展示的即为混合型结点构成的贝叶斯网络。其中Subsidy(补贴)、Buys为离散型的(取值为0,1),而Harvest(收成)、Cost都是连续型的变量。这个时候我们需要分情况讨论:

子结点是连续的
这个时候,需要针对父节点的不同的情况来给予子节点构建条件密度函数。考察上图中的Cost结点,此结点是连续型的,那么可以使用线性高斯模型来建模,具体如下:由于父结点有一个是离散型的,那么需要根据该离散型父结点的不同取值,结合另一连续型结点来建模:

P(Cost=c|Harvest=h,Subsidy ?=ture)=N(ath+bt,σt)(c)=1σt2πexp(12(c(ath+bt)σt)2)

其中at,btσt是常数,会根据离散型变量Subsidy的不同而取值不同。这个建模方法在连续型变量Harvest变化范围较小的时候效果较好。

子结点是离散的,父结点是连续的
这种情况相对较为简单,只需要将父节点离散化即可。通常采用的离散化方法有:sigmoid函数、高斯函数积分。通过这些函数,可以设定阈值,使得最后的离散化结果为{0,1}之间。针对上图中的结点Buys,相应的sigmoid函数如下图所示:
sigmoid函数

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注