计算机视觉
图像处理

从朴素贝叶斯分类器到贝叶斯网络

一、贝叶斯公式(一些必备的数学基础)

贝 叶斯(Thomas Bayes)是生活在十八世纪的一名英国牧师和数学家。因为历史久远,加之他没有太多的著述留存,今天的人们对贝叶斯的研究所知甚少。唯一知道的是,他提 出了概率论中的贝叶斯公式。但从他曾经当选英国皇家科学学会会员(类似于院士)来看,他的研究工作在当时的英国学术界已然受到了普遍的认可。

事实上,在很长一段时间里,人们都没有注意到贝叶斯公式所潜藏的巨大价值。直到二十世纪人工智能、机器学习等崭新学术领域的出现,人们才从一堆早已蒙灰的 数学公式中发现了贝叶斯公式的巨大威力。为了方便后续内容的介绍,这里我们先来简单复习一下概率论中的一些基本知识。

事件A在另外一个事件B已经发生条件下的发生概率,称为条件概率,记为P(A|B)。

两个事件共同发生的概率称为联合概率。A与B的联合概率表示为 P(AB) 或者P(A,B)。

进而有,P(AB) = P(B)P(A|B)=P(A)=P(B|A)。这也就导出了最简单形式的贝叶斯公式,即

P(A|B)=P(B|A)*P(A)/P(B)

       以及条件概率的链式法则

P(A1,A2,…,An) = P(An|A1,A2,…,An-1)P(An-1|A1,A2,…,An-2)…P(A2|A1)P(A1)

概率论中还有一个全概率公式

由此可进一步导出完整的贝叶斯公式

二、朴素贝叶斯分类器(Naïve Baysian classifier)

分类是机器学习和数据挖掘中最基础的一种工作。假设现在我们一组训练元组(Training tuples),或称训练样例,以及与之相对应的分类标签(Class labels)。每个元组都被表示成n维属性向量X=(x1, x2, …, xn)的形式,而且一共有K个类,标签分别为C1, C2, …, Ck。分类的目的是当给定一个元组X时,模型可以预测其应当归属于哪个类别。

        朴素贝叶斯分类器的原理非常简单,就是基于贝叶斯公式进行推理,所以才叫做“朴素”。对于每一个类别Ci, 利用贝叶斯公式来估计在给定训练元组X时的条件概率p(Ci|X),即

P(Ci|X) = P(X|Ci)P(Ci)/P(X)

当且仅当概率P(Ci|X)在所有的P(Ck|X)中取值最大时,就认为X属于Ci更进一步,因为P(X)对于所有的类别来说都是恒定的,所以其实只需要P(Ci|X) = P(X|Ci)P(Ci)最大化即可。

        应用朴素贝叶斯分类器时必须满足条件:所有的属性都是条件独立的。也就是说,在给定条件的情况下,属性之间是没有依赖关系的。即

        为了演示贝叶斯分类器,来看下面这个例子。我们通过是否头疼、咽痛、咳嗽以及体温高低来预测一个人是普通感冒还是流感。

上面是我们提供的训练数据。现在有一个病人到诊所看病,他的症状是:severeheadache,  no soreness, normaltemperature and with cough。请问他患的是普通感冒还是流感?分析易知,这里的分类标签有Flu 和Cold两种。于是最终要计算的是下面哪个概率更高。

P( Flu| Headache = severe, Sore = no,Temperature = normal, Cough = yes)

≅P(Flu)*P(Headache= severe|Flu)*P(Sore= no|Flu)*P(Temperature= normal |Flu)*P(Cough = yes|Flu)

P( Cold| Headache = severe, Sore = no,Temperature = normal, Cough = yes)

≅P(Cold)*P(Headache= severe|Cold)*P(Sore= no|Cold)*P(Temperature= normal |Cold)*P(Cough = yes |Cold)

为了计算上面这个结果,我们需要通过已知数据(训练数据)让机器自己“学习”(建立)一个“模型”。由已知模型很容以得出下表中的结论

以及

e= small value = 10^-7(one can use e to be less than 1/n where n is the number of training instances)

P( Flu| Headache = severe, Sore = no,Temperature = normal, Cough = yes)

= P(Flu)*P(Headache = severe|Flu)*P(Sore= no|Flu)*P(Temperature = normal |Flu)*P(Cough = yes|Flu)

=   3/5   ×  2/3    ×     e     ×        2/3       ×      3/3    = 0.26e

P( Cold| Headache = severe, Sore = no,Temperature = normal, Cough = yes)

~ P(Cold)*P(Headache =severe|Cold)*P(Sore = no|Cold)*P(Temperature = normal |Cold)*P(Cough = yes|Cold)

=  2/5     ×      e        ×      ½       ×   1       ×        ½    = 0.1e

显然P(Flu) > P(Cold),所以我们的诊断(预测,分类)结果是 Flu。

最后讨论一下朴素贝叶斯分类器的特点(来自网上资料总结,我就不翻译了):

• Naïve Bayesian Classifier is very simple to build, extremely fast to make decisions, and easy to change the probabilities when the new data becomes available (especially when the new data is additional information not modification to previously used data).
• Works well in many application areas.
• Scales easily for large number of dimensions (100s) and data sizes.
• Easy to explain the reason for the decision made.
• One should apply NB first before launching into more sophisticated classification techniques.

三、贝叶斯网络

贝 叶斯网络(Bayesian Network)是一种用于表示变量间依赖关系的数据结构,有时它又被称为信念网络(Belief Network)或概率网络(Probability Network)。在统计学习领域,概率图模型(PGM,Probabilistic Graphical Models)常用来指代包括贝叶斯网络在内的更加宽泛的一类机器学习模型,例如隐马尔可夫模型(HMM,Hidden Markov Model)也是一种PGM。

具体而言,贝叶斯网络是一个有向无环图(Directed Acyclic Graph),其中每个节点都标注了定量的概率信息,并具有如下结构特点:

(1)一个随机变量集构成了图结构中的节点集合。变量可以是离散的,也可以是连续的。

(2)一个连接节点对的有向边集合反映了变量间的依赖关系。如果存在从节点X指向节点Y的有向边,则称X是Y的一个父节点。

(3)每个节点Xi都有一个(在给定父节点情况下的)条件概率分布,这个分布量化了父节点对其之影响。

在 一个正确构造的网络中,箭头显式地表示了X对Y的直接影响。而这种影响关系往往来自于现实世界的经验分析。一旦设计好贝叶斯网络的拓扑结构,只要再为每个 节点指定当给定具体父节点时的条件概率,那么一个基本的概率图模型就建立完成了。尽管现实中贝叶斯网络的结构可能非常复杂,但无论多么复杂的拓扑本质上都 是由一些基本的结构单元经过一定之组合演绎出来的。而且最终的拓扑和对应的条件概率完全可以给出所有变量的联合分布,这种表现方式远比列出所有的联合概率 分布要精简得多。图1给出了三种基本的结构单元,下面我们将分别对它们进行介绍。

图1  三种基本的结构单元

首先,如果几个随机变量之间是完全独立的,那么它们之间将没有任何的边进行连接。而对于朴素贝叶斯中的假设,即变量之间是条件独立(Conditionally Independent)的,那么可以画出此种结构如图1中的左图所示。这表明在给定Y的情况下,X和Z是条件独立的。其次,另外一种与之相反的情况如图1中的中图所示。此时X和Z是完全独立的。我们通常把左图的情况称为“Common Cause”,而把中图的情况称为“Common Effect”。

最后,对于图1中右图所示的链式结构,X和Z不再是相互独立的。但在给定Y时,X和Z就是独立的。因为P(Z|X,Y)=P(Z|Y)。

文 献[1]中给出了一个简单的贝叶斯网络示例,如图2所示。假设你在家里安装了一个防盗报警器。这个报警器对于探测盗贼的闯入非常可靠,但是偶尔也会对轻微 的地震有所反应。你还有两个邻居John和Mary,他们保证在你工作时如果听到警报声就给你打电话。John听到警报声时总是会给你打电话,但是他们有 时候会把电话铃声当成警报声,然后也会打电话给你。另一方面,Mary特别喜欢大声听音乐,因此有时候根本听不见警报声。给定了他们是否给你打电话的证 据,我们希望估计如果有人入室行窃的概率。

图2  贝叶斯网络示例

现在暂时忽略图中的条件概率分布,而是将注意力集中于网络的拓扑结构上。在这个防盗网络的案例中,拓扑结构表明盗贼和地震直接影响到警报的概率(这相当于一个Common Effect的结构),但是John或者Mary是否打电话仅仅取决于警报声(这相当于一个Common Cause的结构)。因此网络表示出了我们的一些假设:“John和Mary不直接感知盗贼,也不会注意到轻微的地震”(这表明当给定随机变量Alarm时,“盗贼或地震”都独立于“打电话”),并且他们不会在打电话之前交换意见(所以在给定随机变量Alarm时,John打电话和Mary打电话就是条件独立的)。

注 意网络中没有对应于Mary当前正在大声听音乐或者电话铃声响起来使得John误以为是警报的节点。这些因素实际上已经被概括在与从Alarm到 JohnCalls或者到MaryCalls这两条边相关联的不确定性中了。这同时体现了操作中的惰性与无知:要搞清楚为什么那些因素会以或多或少的可能 性出现在任何特殊情况下,需要大量的工作,而且无论如何我们都没有合理的途径来获取相关信息。上面的概率实际上概括了各种情况的潜在无限集合,其中包括报 警器可能会失效的情况(诸如环境湿度过高、电力故障、电线被切断、警铃里卡了一只死老鼠等等)或者John和Mary没有打电话报告的情况(诸如出去吃午 饭了、外出度假、暂时性失聪、直升机刚巧飞过而噪声隆隆等)。如此一来,一个小小的智能体可以处理非常庞大的世界,至少是近似地处理。如果我们能够引入附 加的相关信息,近似的程度还可以进一步地提高。
现在 回到图中的条件概率分布上。每一个分布都被显示为一个条件概率表(CPT, Conditional Probability Table)。这种形式的表格适用于离散型随机变量。本文也仅讨论这种类型的表示方法。CPT中的每一行包含了每个节点值在给定条件下的条件概率。这个所 谓的“给定条件”就是所有父节点取值的某个可能组合。每一行概率加起来和必需是1,因为行中条目表示了该对应变量的一个无遗漏的情况集合。对于布尔变量, 一旦知道它为真的概率是p,那么它为假的概率就应该是1-p。所以可以省略第二个数值。通常,一个具有k个布尔父节点的布尔变量的CPT中有2^k个独立 的可指定概率。而对于没有父节点的节点而言,它的CPT只有一行,表示了该变量可能取值的先验概率(例如图中的Burglary和Earthquake对 应的CPT)。

四、模型推理

当我们已经确定了一个贝叶斯网络的结构时,如何利用它进行推理将成为焦点。例如现在我们想知道当John和Mary都打电话时发生地震的概率。即 P(E = T | J = T, M = T) = ?

总的来说,通常可采用的方法有三种:1)首先是利用与朴素贝叶斯类似方法来进行推理(其中同样用到贝叶斯公式),我们称其为枚举法;2)其次是一种更为常用的算法,我们称之为消去法;3)最后还有一种基于蒙特卡洛法的近似推理方法,本文将仅讨论前两种算法。

4.1  枚举法

为了详细地说明原委,我们还是从一个简单的概率论知识点开始。众所周知,由n个随机变量X1, X2, …, Xn构成的向量

X = (X1, X2, …, Xn) 称为n维随机向量(或称n维随机变量)。首先我们以二维随机向量(X,Y)为例来说明边缘分布的概念。随机向量(X,Y)的分布函数F(x,y)完全决定了其分量的概率特征。所以由F(x,y)便能得出分量X的分布函数FX(x),以及分量Y的分布函数FY(y)。而相对于联合分布F(x,y),分量的分布FX(x)和FY(y)称为边缘分布。由

FX(x) = P{X ≤ x} = P{X ≤ x, Y ≤ +∞} = F(x, +∞)

FY(y) = P{Y ≤ y} = P{X ≤ +∞,Y ≤ y} = F(+∞, y)

可得

FX(x) = F(x, +∞),  FY(y) = F(+∞, y)

若(X,Y)为二维离散随机变量,则

若(X,Y)为二维连续随机变量,设密度函数为p(x,y),则

回 想在朴素贝叶斯中所使用的策略。我们根据已经观察到的证据计算查询命题的后验概率。并将使用全联合概率分布作为“知识库”,从中可以得到所有问题的答案。 这其中贝叶斯公式发挥了重要作用,而下面的示例同样演示了边缘分布的作用。从一个非常简单的例子开始:一个由3个布尔变量Toothache、 Cavity以及Catch (由于牙医的钢探针不洁而导致的牙龈感染)组成的定义域。其全联合分布是一个2 × 2 × 2 的表格,如下表所示。

根据概率公理的要求,联合分布中的所有概率之和为1 。无论是简单命题还是复合命题,我们只需要确定在其中命题为真的那些原子事件,然后把它们的概率加起来就可获得任何命题的概率。例如,命题Cavity ∨ Toothache在 6 个原子事件中成立,所以可得

P(Cavity ∨ Toothache) = 0.108 + 0.012 + 0.072 + 0.008 + 0.165 + 0.064 = 0.28

一个特别常见的任务是将随机变量的某个子集或者某单个变量的分布抽取出来,也就是我们前面提到的边缘分布。例如,将所有Cavity取值为真的条目抽取出来在求和就得到了Cavity的无条件概率(也就是边缘概率)

P(Cavity) = 0.108 + 0.012 + 0.072 + 0.008 = 0.2

该 过程称为边缘化(Marginalisation),或者称为“和出”(Summing Out)——因为除了Cavity以外的变量都被求和过程排除在外了。对于任何两个变量集合Y和Z,可以写出如下的通用边缘化规则(这其实就是前面给出的 公式,我们只是做了简单的变量替换)

也就是说,Y的分布可以通过根据任何包含Y的联合概率分布对所有其它变量进行求和消元得到。根据乘法规则,这条规则的一个变形涉及条件概率而不是联合概率:

这条规则称为条件化。以后会发现,对于涉及概率表达式的所有种类的推导过程,边缘 化和条件化具有非常强大的威力。

在大部分情况下,在给定关于某些其它变量的条件下,我们会对计算某些变量的条件概率产生感兴趣。条件概率可以如此找到:首先根据条件概率的定义式得到一个无条件概率的表达式,然后再根据全联合分布对表达式求值。例如,在给定牙疼的条件下,可以计算蛀牙的概率为

P(Cavity | Toothache) = P(Cavity ∧ Toothache) / P(Toothache)

=( 0.108 +0.012) / (0.108 + 0.012 + 0.016 + 0.064) = 0.6

为了验算,还可以计算已知牙疼的条件下,没有蛀牙的概率为

P(┐Cavity | Toothache) = P(┐Cavity ∧ Toothache) / P(Toothache)

=( 0.016 +0.064) / (0.108 + 0.012 + 0.016 + 0.064) = 0.4

注意这两次计算中的项 1/P(Toothache) 是保持不变的,与我们计算的Cavity的值无关。事实上,可以把它看成是P(Cavity I Toothache)  的一个归一化常数,保证其所包含的概率相加等于1,也就是忽略P(Toothache) 的值,这一点我们在朴素贝叶斯部分已经讲过。

此外,我们将用α来表示这样的常数。用这个符号我们可以把前面的两个公式合并写成一个:

P(Cavity | Toothache) =α P(Cavity, Toothache)

=α [P(Cavity, Toothache, Catch) + P(Cavity, Toothache, ┐Catch)]

[〈0.108, 0.016〉+〈0.012, 0.064〉] = α〈0.12, 0.08〉=〈0.6, 0.4〉

在很多概率的计算中,归一化都是一个非常有用的捷径。

从 这个例于里可以抽取出一个通用推理过程。我们将只考虑查询仅涉及一个变量的情况。我们将需要使用一些符号表示:令X 为查询变量(前面例子中的Cavity);令E 为证据变量集合(也就是给定的条件,即前面例子中的Toothache ), e 表示其观察值;并令 Y 为其余的未观测变量(就是前面例于中的Catch) 。查询为P(X I e),可以对它求值:

其中的求和针对所有可能的y (也就是对未观测变量Y的值的所有可能组合)。注意变量 X, E 以及Y一起构成了域中所有布变量的完整集合,所以P(X, e, y)只不过是来自全联合分布概率的一个子集。算法对所有X和Y的值进行循环以枚举当 e 固定时所有的原子事件,然后根据全联合分布的概率表将它们的概率加起来,最后对结果进行归一化。

下面我们就用枚举法来解决本节开始时抛出的问题: P(E = T | J = T, M = T) = ?

P(E|j,m) = α P(E, j, m)

其中,我们用小写字母 j 和 m 来表示 J = T,以及M = T(也就是给定J和M)。但表达式的形式是P(E|j,m)而非P(e|j,m),这是因为我们要将E = T 和 E = F这两个公式合并起来写成一个。同样,α 是标准化常数。然后就要针对其他未观测变量(也就是本题中的Burglary和Alarm)的值的所有可能组合进行求和,则有

根据图2中所示之贝叶斯网络,应该很容易可以写出下列关系式。

如果你无法轻易地看出这种关系,也可以通过公式推导一步一步的得出。首先,在给定条件a的情况下,J和M条件独立,所以有P(j,m|a) = P(j|a)P(m|a)。B和E独立,所以有P(b)P(E)=P(b,E)。进而有P(b)P(E)P(a|b,E)=P(a,b,E)。在给定a的时候,b、E和j、m独立(对应图1中的第3种情况),所以有P(j,m|a) = P(j,m|a,b,E)。由这几个关系式就能得出上述结论。

下面我们来循环枚举并加和消元。

在计算上还可以稍微做一点改进。因为P(E)对于ΣaΣb来说是一个常数,所以可以把它提出来。这样就避免了多次乘以P(E)所造成的低效。

上式中所有的值都可以基于CPT求得,算术当然是很繁杂的,我们这里不具体给出最终的结果。但一个显而易见的事实是当变量的数目变多时,全联合分布的表长增长是相当惊人的!所以我们非常希望能够有一种更轻巧的办法来替代这种枚举法,于是便有了下面将要介绍的消去法。

4.2  消去法

变量消去算法(Variable Elimination Algorithm)是一种基于动态规划思想设计的算法。而且在算法执行的过程中需要使用因子表来储存中间结果,当再次需要使用时无需重新计算而只需调用已知结果,这样就降低了算法执行的时间消耗。

Each factor is a matrix indexed by the values of its argument variable. 例如,与P(j|a)和P(m|a)相对应的因子fJ(A)和fM(A)只依赖于A,因为J和M在我们的问题里是已知的,因此fJ(A)和fM(A)都是两个元素的矩阵(也是向量)

在这种记法中括号里的参数表示的是变量,而下标仅仅是一种记号,所以你也可以使用f4(A)和f5(A)来代替fJ(A)和fM(A)。但我们这里使用J和M来作为下标的意图是考虑用P( _ | A)的 _ 来作为标记。所以P(a|b,E)可以写成fA(A, B, E),注意因为A,B,  E都是未知的,所以fA(A, B, E) 就是一个2×2×2的矩阵,即

最初的因子表是经CPT改造而来的,如下图所示。

然后进行自底向上的计算,Step1: fJ(A)×fM(A) = fJM(A),A仍然是变量,则有

此时新产生的因子表为

Step2: fA(A, B, E)×fJM(A) = fAJM(A, B, E),即

此时新产生的因子表为

Step3:

此时新产生的因子表为

Step4:

此时新产生的因子表为

Step5:

此时新产生的因子表为

Step6:

此时新产生的因子表为

由此便可根据上表算得问题之答案

P(E=T | j,m) = P(E=T | j,m) / [P(E=T | j,m) + P(E=F | j,m)]  = 0.0037/(0.0037 + 0.0069) = 0.3491

最后总结一下消去算法的执行步骤:

参考文献

[1] Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach.
[2] Some examples from: Kevin B. Korb and Ann E. Nicholson. Bayesian Artificial Intelligence
[3] Some slides derived from The University of Melbourne Statistical Machine Learning (COMP90051)

转载注明来源:CV视觉网 » 从朴素贝叶斯分类器到贝叶斯网络

分享到:更多 ()
扫描二维码,给作者 打赏
pay_weixinpay_weixin

请选择你看完该文章的感受:

0不错 0超赞 0无聊 0扯淡 0不解 0路过

评论 5

评论前必须登录!