贝叶斯网络

第5章贝叶斯网络(40-2)贝叶斯网络贝叶斯网络(BayesianNetworks)结合图论和统计学方面的知识，提供了一种自然表达因果信息的方法，用于表达随机变量之间复杂的概率不确定性，发现数据间的潜在关系。本章介绍如下几个方面的内容：•贝叶斯网络基本概念•不确定性推理与联合概率分布•贝叶斯网络中的独立关系•贝叶斯网络学习•贝叶斯网络分类器(40-3)引言•贝叶斯网络将图论和统计学相结合，用于表达随机变量之间复杂的概率不确定性，发现数据间的潜在关系。•优点：(1)知识表示形式更加直观。(2)对于问题域的建模，当条件或行为等发生变化时，不需要修正模型。(3)以图形化表示随机变量间的联合概率，处理不确定性信息。(4)没有确定的输入或输出结点，结点之间相互影响，可以用于估计预测。(5)将知识表示与知识推理结合统一为整体。•1988年，Pearl建立了贝叶斯网基础理论体系，将概率理论和图论有机结合，用一种紧凑的形式表示联合概率分布。(40-4)贝叶斯网络基本概念•给定一个随机变量集X={X1,X2,…,Xn}，其中Xi是一个m维向量。贝叶斯网络说明X上的联合条件概率分布。定义为•G是有向无环图，节点分别对应于有限集X中的随机变量X1,X2,…,Xn，每条弧代表一个函数依赖关系。•如果有一条由变量Y到X的弧，则Y是X的双亲(直接前驱)，X是Y的后继。Xi的所有双亲变量用集合Pa(Xi)表示。•一旦给定双亲，图G中的每个变量就与其非后继节点相独立。•代表用于量化网络的一组参数。对于Xi的取值xi，参数•贝叶斯网络表明变量集合X上的联合条件概率分布：(40-5)贝叶斯网络基本概念•贝叶斯网络提供一种方便表示因果知识的途径。•网络内节点可以选作“输出”节点，代表类标号属性。可以有多个输出节点。分类过程返回类标号属性的概率分布，预测每个类的概率。(40-6)不确定性推理与联合概率分布•不确定性的主要来源：⑴领域专家对自己掌握知识的不确定性；⑵所要建模的领域本身内在的不确定性；⑶知识工程师试图翻译、表示知识所产生的不确定性；⑷关于知识自身的精确性和知识获取方面存在的不确定性。•使用概率方法进行不确定性推理的步骤：①将待处理问题域抽象为一组随机变量的集合X={X1,X2,…,Xn}；②把关于该问题的知识表示为一个联合概率分布P(X)；按照概率论原则进行推理计算。•例（Alarm问题）：Pearl教授的家里装有警铃，地震和盗窃都可能触发警铃。听到警铃后，两个邻居Marry和John可能会打电话给他。如果Pearl教授接到Mary的电话，说听到他家警铃响，那么Pearl教授家遭盗窃的概率是多大?(40-7)不确定性推理与联合概率分布•5个随机变量：–盗窃(Burgle，B)接到John的电话(JohnCall，J)–地震(EarthQuake，E)接到Marry的电话(MarryCall，M)–警铃响(Alarm，A)(40-8)不确定性推理与联合概率分布•从联合概率P(A,B,E,J,M)出发，先计算边缘分布（5.4）得到联合概率边缘化分布：再按照条件概率定义，得到(40-9)不确定性推理与联合概率分布•问题：•随着变量数目增加，联合概率分布的参数个数成指数级增长。–n个二值随机变量的联合概率分布包含2n-1个独立参数。•当变量很多时，联合概率的获取、存储和运算都十分困难。•在六、七十年代，大多数学者认为概率论不适合于解决人工智能中的不确定性问题。(40-10)贝叶斯网络中的独立关系•利用变量间的条件独立关系可以将联合概率分布分解成多个复杂度较低的概率分布，从而降低模型复杂度，提高推理效率。•例如：由链规则可以把联合概率分布P(A,B,E,J,M)改写为：独立参数：1+2+4+8+16=31–E与B相互独立，即P(E|B)=P(E)–给定A时，J与B和E相互独立，即P(J|B,E,A)=P(J|A)–给定A时，M与J、B和E都相互独立，即P(M|J,A,B,E)=P(M|A)则有：独立参数：l+2+4+2+2=11(40-11)贝叶斯网络中的独立关系•利用链规则将包含n个变量的联合分布写为：对于任意Xi，如果存在Pa(Xi)∈{X1，…，Xi-1}，使得己知Pa(Xi)条件下，Xi与{X1，…，Xi-1}中的其它变量条件独立，即则联合概率分布可改写为•独立性可以减少表示联合概率分布所需的信息量。•独立性断言通常来源于领域知识。•贝叶斯网络中存在三类独立关系：–条件独立–因果影响独立–环境独立(40-12)贝叶斯网络中的独立关系(一)条件独立•贝叶斯网络的网络结构表达节点间的条件独立关系。•三种局部结构–顺连(serialconnection)–分连(divergingconnection)–汇连(convergingconnection)(40-13)贝叶斯网络中的独立关系(二)有向分离和条件独立•贝叶斯网络中任意两个节点之间的条件独立关系可由有向分离来判断。•定义5.1设E为节点集合，X和Y是不在E中的两个节点。X和Y之间的通路α如果满足下面条件之一，则称α被E所阻塞1.α上存在一个顺连节点Z，且Z在E中；2.α上存在一个分连节点Z，且Z在E中；3.α上存在一个汇连节点Z，且Z和Z的后代节点均不在E中。(40-14)贝叶斯网络中的独立关系•定义5.2X，Y，E是三个互不相交的节点集，说E有向分离X和Y，当且仅当X和Y之间的通路都被E所阻塞。•推论5.3设X和Y为贝叶斯网络中的两个变量。Z为贝叶斯网络中一个不包含X和Y的节点集合。如果Z分离X和Y，则X和Y在给定Z的条件下相互独立。•推论5.4一个节点的马尔科夫覆盖包括该节点的父节点，子节点，以及子节点的父节点。•推论5.5在一个贝叶斯网中，给定变量X的马尔可夫覆盖时，则X条件独立于网络中所有其它变量。•推论5.6在一个贝叶斯网中，给定变量X的父节点Pa(X)，则X条件独立于它的所有非后代节点。(40-15)贝叶斯网络中的独立关系(三)因果影响独立(causalindependence)因果影响独立指的是多个原因独立地影响同一个结果。•定义5.7节点Y的各个父亲节点X1,X2,…,Xn对于Y是因果影响独立的，如果对应于X1,X2,…,Xn存在和Y有相同取值范围的随机变量，并且下面两个条件成立：1.对任意i，依赖于Xi，在Xi已知条件下，独立于所有其它的和(j≠i)；2.在ΩY上存在一个满足交换律和结合律的二元算子*，使得(40-16)贝叶斯网络中的独立关系(四)环境独立(contextindependence)•环境独立是指在特定环境下才成立的条件独立关系。•一个环境是一组变量及其取值的组合。设环境中涉及变量的集合用C表示，C的一种取值用c表示，则C=c表示一个环境。•定义5.8设X，Y，Z，C是4个两两交空的变量集合，如果P(X,Y,Z,C=c)0且P(X|Y,Z,C=c)=P(X|Z,C=c)则称X,Y在环境C=c下关于Z条件独立。若Z为空，则称X,Y在环境C=c下环境独立。(40-17)贝叶斯网络学习贝叶斯网络由结构(有向无环图)和参数(条件概率)两部分构成，分别用于定性与定量地描述依赖关系。网络中的有向边具有因果语义。贝叶斯网络学习的核心问题是结构学习，包括结构和数据集参数。有时网络学习和结构学习不加区分。(一)结构学习目标是基于训练数据找到数据匹配程度最高的贝叶斯网络结构。无约束贝叶斯网络可归结为在给定数据集T后，寻找具有极大似然P(G|T)的结构G的问题。有n个变量的问题域，对应的网结构空间为n个结点构成的所有可能的有向无环图，结构空间大小是n的指数次。•贝叶斯网络结构学习方法：–基于打分搜索的方法–基于依赖关系分析的方法(40-18)贝叶斯网络学习(1)基于打分搜索的学习算法采用某个评分标准，评判网络结构反映出的独立及依赖关系和数据的匹配程度。给定一个关于结构的测度后，在结构空间中按照一定的搜索策略，依次计算各结构的测度值，选择测度值最优的结构。•两类评分标准：①基于编码理论–最小描述长度(MinimumDescriptionLength，MDL)–贝叶斯信息标准(BayesianInformationCriterion，BIC)②源于贝叶斯统计–BDe评分方法•最小描述长度函数MDLMDL原理认为最优模型是总描述长度最短的模型。贝叶斯网络B=G,θ描述每一个样本Di的概率，按编码策略对每个样本Di进行编码。网络结构G要使得网络描述长度和数据D的编码长度之和最小，必须在网络结构的复杂性与网络结构的准确性之间确定平衡点。(40-19)贝叶斯网络学习•网络结构的MDL测度由3部分组成：1.网络结构的描述长度：保存网络结构G，要记录各节点的父节点的编号。贝叶斯网络包含n个节点，|πXi|为节点Xi的父节点数目。网络结构的描述长度是：2.参数的描述长度：为描述局部条件概率表，须存贮每个节点的条件概率表的所有参数。Xi的条件概率表需要存贮|πXi|(|Xi|-1)个参数，|Xi|表示变量Xi所有可能状态的数目。存储每个参数，需要logn/2二进制位，其中N是训练样本的数目。3.数据集合的描述长度：将数据D中每个样本Di建立Huffman编码，每个码字的确切长度依赖于P(Di|G,θ)，其概率越大，编码长度越小，概率越小，编码长度越大。Di的二进制编码长度近似等于log(1/P(Di|G,θ))。因而数据集合的描述长度为：•其中H(Xi|πXi)为条件熵。•综上，结构MDL测度为：(40-20)贝叶斯网络学习•贪婪搜索:令E表示所有可能添加到网络中的候选边集合，表示边e加入到网络中后评分函数的变化。•步骤1.选择一个网络。•步骤2.选择集合E中的边e，使得，如果找不到满足条件的边，则停止，否则继续。•步骤3.加入边e到网络中，并从集合E中删除e，转步骤2。•MDL优缺点：•目标是结构简单、参数较少的稀疏网络•具有一致性•没有用到先验知识•对两个具有等价性的结构，不能保证得到相同MDL测度值。(40-21)贝叶斯网络学习•BDe函数–Heckerman等扩展BD(BayesianDirichlet)度量，提出BDe函数。–定义一个离散变量G表示未知的网络结构，其取值范围是所有可能网络结构；–估计G的先验概率P(G)；–计算网络结构后验概率P(G|D)和参数后验概率P(θ|D,G)，并计算目标期望值。•BDe函数取做网络结构同数据集的联合概率分布的对数形式：（5.11）其中P(D|G)称边际似然函数。•定义一个随机变量Sh表示网络结构对应的状态，并赋予先验概率分布P(Sh)。对任意样本D，计算后验概率分布有其中P(D)是一个与结构无关的正规化常数，P(D|Sh)是边界似然。(40-22)贝叶斯网络学习•度量公式如下：•先验概率分布的计算依据先验知识。•优缺点：–使用先验知识，其对训练数据集的依赖性比MDL测度要低–没有明确地包含结构复杂性指标，会倾向于选择较复杂的网络结构。(40-23)贝叶斯网络学习•(二)搜索算法搜索算法在某个评分函数下搜索分值最高的网络结构。•当数据完备时，搜索算法借助评分函数的“可分解性”来提高搜索效率。•所谓评分函数可分解是指：G的分值可以通过其各个家族的分值之和求得。–家族即一个节点和其所有父节点所构成的简单图。•搜索算法执行过程：–从一个初始的网络结构开始，对当前结构进行某些的修改；–计算修改后结构的分值，根据分值决定是否更新结构。•定义5.9.如果给定某一问题领域的各个变量，用一个结点表示其中的一个变量，由任意两个结点间的无向边连接构成的图模型，称为完全潜在图。•定义5.10.如果变量X、Y和变量集Z之间存在以下关系：即在变量集Z已知的条件下，变量Y的状态和概率不会造成对变量X的影响，称为在给定变量集Z的前提下，X条件独立于Y。(40-24)贝叶斯网络学习•定义5.11.设X、Y和Z为有向无环图中3个互不相交的结点子集，当且仅当没有一条从X中一个结点到Y中一个结点的所有路径之间，存在结点W满足下列条件之一：i.每个汇聚结点要么是Z中的结点，要么有子