第七章贝叶斯网络.ppt

1,第七章贝叶斯网络,李伟生信科大厦19楼Tel：62471342liws,2,第7章贝叶斯网络,7.1贝叶斯网络及其推理模式7.2singletontreenetwork7.2singly-connectednetwork,3,7.1.1贝叶斯网络7.1.2d分离7.1.3贝叶斯网络的推理模式,7.1贝叶斯网络及其推理模式,4,7.1.1贝叶斯网络,贝叶斯网络也称为信念网、概率因果网，它是用来表示变量集合的连续概率分布的图形模式，是人工智能、概率理论、图论、决策理论相结合的产物。贝叶斯网络提供了一种自然地表示因果信息的方法，用来发现数据间的潜在关系。作为一种知识表示和进行概率推理的框架，贝叶斯网络在具有内在不确定性的推理和决策问题中得到了广泛的应用，例如诊断和故障检测、概率专家系统、交通管理、计算机视觉和数据挖掘等。贝叶斯推理是概率统计学中一种很重要的方法，贝叶斯网络是根据贝叶斯推理建立的各个变量之间依赖关系的图形模型。为了进行概率推理，需要给出一组随机变量的联合概率分布。,5,定义(条件独立)给定随机变量集合V、V和随机变量vi，如果下式成立，则称随机变量vi条件独立于变量集V，记作：给定集合V，如果一个随机变量vi条件独立于另一个变量vj，则有根据条件概率的定义，有组合上两式，得到因此，给定V，如果vi条件独立于vj，则同样有vj条件独立于vi。这一结果也可用于集合，即给定V，如果Vi和Vj是条件独立的，那么,贝叶斯网络,6,条件独立性能用贝叶斯网络结构方便地表示，用贝叶斯网络表示的条件独立能大量地节约概率推理计算。定义(贝叶斯网络),贝叶斯网络,给定随机变量集合，建立在该集合上的联合概率分布可以表示为一个贝叶斯网络，其中：,网络结构G，G是一个有向无环图(DAG)，其结点为V，图中的结点为随机变量，结点的状态对应于随机变量的值；A是图中弧（有向边）的集合，表示了结点之间的条件（因果）依赖关系。,网络参数P，P为贝叶斯网络的条件概率表集合，P中的每一个元素代表结点Vi的条件概率表（CPT），由概率的链规则有,根结点的概率,非根结点与它们先导结点的条件概率,7,由上式可以看出，为了确定贝叶斯网络的联合概率分布，要求给出如下先验概率：所有根结点的概率；所有非根结点与它们先导结点的条件概率。对于n个离散二值随机变量，要确定它们的联合概率分布，需要给出2n-1个条件概率值，当较大时，通过各个条件概率来计算联合概率往往是难以处理的。因此，变量间的条件独立性是很重要的。Pearl对贝叶斯网络中结点间的条件独立性进行了研究，给出了d分离条件（d-separationcondition）的定义。在贝叶斯网络中，独立关系表现为结点间的d分离。同理，其间没有d分离的结点是相互依赖的。,贝叶斯网络,8,7.1.2d分离,在贝叶斯网络中，如果对于结点Vi和Vj之间的每个无向路径，在路径上有某个结点Vb，若它具有如下三个属性之一，就说结点Vi和Vj条件独立于给定的结点集。这三个属性是：,(1)，且路径上的两条弧都以Vb开始。,(2)，路径上的一条弧以Vb开始，另一个以Vb结束。,(3)Vb和它的任何后继都不包含于，路径上的两条弧都以Vb开始。,这样，随机变量集合V上的一个贝叶斯网络唯一确定了一个V上的概率分布,Ui是vi在网络结构中的父结点集合,9,d分离,通过阻塞结点的条件独立,证据结点，两条弧都以Vb1开始,证据结点，一条弧以Vb1开始，一条弧以Vb1结束,Vb3及其任一后继都不是证据结点，两条弧都以Vb3开始,结论：给定证据集，d分离Vi和Vj。,10,7.1.3贝叶斯网络的推理模式,利用建立的贝叶斯网络模型解决实际问题的过程称为贝叶斯网络推理。在一次推理中，那些值已确定的变量构成的集合成为证据D，需要求解的变量集合称为假设X，一个推理问题就是求解给定证据条件下假设变量的后验概率P(X|D)。,因果推理：从原因到结果，反映了网络中祖先结点对子孙结点的预计支持；诊断推理（或自底向上推理）是从结果到原因，它反映了网络中子孙结点对祖先结点的回顾支持；辩解：上述两种推理模式的结合。,11,贝叶斯网络的推理模式,贝叶斯网络的推理算法可以分为两类：一类称为精确推理，即精确地计算假设变量的后验概率；另一类称为近似推理，即在不影响推理正确性的前提下，通过适当降低推理精度来达到提高计算效率的目的。精确推理一般用于结构较简单的贝叶斯网络，而对于结点数量大、结构复杂的贝叶斯网络常常采用近似推理。贝叶斯上的精确推理算法主要有：基于分层假设的证据推理算法、基于单连通网络结构的消息传播方法、用于多连通网络结构的联合树算法(JoinTreealgorithm)、条件割集法(Cutsetconditionalmethods)等。尽管贝叶斯网络以其坚实的概率理论基础及其有效性而被认为是目前最好的不确定推理算法之一，但任意复杂结构的贝叶斯网络推理计算是NP困难的。因此，对贝叶斯网络推理的研究中心已转向了近似推理算法的研究。目前已提出了多种近似推理算法，主要包含两类：一类是随机仿真法；另一类是解决网络某一方面的近似计算法，如状态空间提取(Statespaceabstraction)、弧删除方法(Arcremoval)等。,12,贝叶斯网络的推理模式,贝叶斯网络是一种统一的概率推理结构，它为不确定知识条件下的推理提供了一致连续的解决方法。一个贝叶斯网络包含了一组结点，这些结点代表了一些随机变量，结点间使用弧进行连接，反映了结点间的相互关系。在某些结点获得证据信息后，贝叶斯网络在结点间传播和融合这些信息，每个结点被分配一个与概率定理一致的置信度，直到网络达到新的平衡。,应用贝叶斯网络求解态势估计问题的基础在于态势可分解成由各事件组成的层次结构。其求解过程可以分为两步：建立表示态势估计模型的贝叶斯网络结构；建立置信度更新算法，反映事件在网络中的信息传播。,13,7.2singletontreenetwork,该网络中每个结点为单元素集，每个结点表示一种特定的命题。如果一个结点S1N的各个子集S1，S2，SN相互独立，则可以使用一层树结构来表示这些结点间的关系，且,14,在上式成立时，网络间的信息传播可由以下式子进行计算。假设由事件传来的证据e直接作用于结点S，有似然率反映了证据e支持态势S的程度。引入证据e后，结点S的置信度更新为：其中，为归一化因子，有,singletontreenetwork,15,singletontreenetwork,S向其邻近结点传播以下消息：向每个子孙结点传播；向父结点传递传播，。,S的子孙结点（比如Z）、父结点（比如X）和兄弟结点（比如Y）的置信度分别更新为：,16,7.3singly-connectednetwork,其基本思想是对每一个结点X，利用X的相邻结点传递来的消息更新X的置信度，并将结果向其余相邻结点传播。,树型贝叶斯网络：设影响结点X的证据结点集可表示为，