第5章不确定性推理

1、第五章 不确定性推理n概述概述n概率论基础概率论基础nBayes网络网络n主观主观Bayes方法方法n确定性方法确定性方法n证据理论证据理论1第五章 不确定性推理n概述概述n概率论基础概率论基础nBayes网络网络n主观主观Bayes方法方法n确定性方法确定性方法n证据理论证据理论2概述n不精确思维并非专家的习惯或爱好所至不精确思维并非专家的习惯或爱好所至, 而而是客观现实的要求。是客观现实的要求。q很多原因导致同一结果很多原因导致同一结果q推理所需的信息不完备推理所需的信息不完备q背景知识不足背景知识不足q信息描述模糊信息描述模糊q信息中含有噪声信息中含有噪声q规划是模糊的规划是模糊的q推理

2、能力不足推理能力不足q解题方案不唯一解题方案不唯一 3在人类的知识和思维行为中, 精确性只是相对的, 不精确性才是绝对的。知识工程需要各种适应不同类的不精确性特点的不精确性知识描述方法和推理方法。几个不确定性n证据的不确定性证据的不确定性q歧义性；不完全性；不精确性；模糊性；可信性；歧义性；不完全性；不精确性；模糊性；可信性；随机性；不一致性随机性；不一致性n规则的不确定性规则的不确定性q证据的组合的不确定性证据的组合的不确定性q规则自身的不确定性规则自身的不确定性q规则结论的不确定性规则结论的不确定性n推理的不确定性推理的不确定性4概述-表示的3方面问题n不确定问题的数学模型表示的不确定问题

3、的数学模型表示的3方面问题方面问题q表示问题：表示问题：n表达要清楚。表示方法规则不仅仅是数表达要清楚。表示方法规则不仅仅是数, 还要有语义描述。还要有语义描述。q计算问题：计算问题：n不确定性的传播和更新。也是获取新信息的过程。不确定性的传播和更新。也是获取新信息的过程。5不确定性推理例子例如例如, 对于如下的推理过程：对于如下的推理过程：nR1：A1 A2B1nR2：A2 A3 B2nR3：B1BnR4：B2B在描述这些规则时采用的都是不确定性知识在描述这些规则时采用的都是不确定性知识表示方式表示方式67推理树结果图 A A1 1A A2 2A A3 3ORORANDANDB B1 1B

4、B2 2B BR R1 1R R2 2R R3 3R R4 4f f1 1f f4 4f f3 3f f2 2概述-表示的3方面问题q语义问题：将各个公式解释清楚语义问题：将各个公式解释清楚。语义问题：如何解释表示和计算的含义语义问题：如何解释表示和计算的含义, 目前多用概率方法。目前多用概率方法。如：如：f(B, A)可理解为当前提可理解为当前提A为真时结论为真时结论B为真的一种影响程度为真的一种影响程度, C(A)可理解为可理解为A为真的程度。为真的程度。特别关心的是特别关心的是f(B, A)的值：的值：1)A(T) B(T), f(B, A)=?2)A(T) B(F), f(B, A)=

5、?3)B 独立于独立于A, f(B, A)=?对对C(A)关心的是：关心的是：1)A为为T, C(A)？2)A为为F, C(A)？ T：True, F：False8概述-分类(1)不确定性推理方法可分为形式化方法和非形式化方不确定性推理方法可分为形式化方法和非形式化方法。法。n形式化方法有形式化方法有逻辑法、新计算法和新概率法逻辑法、新计算法和新概率法。逻。逻辑法是非数值方法辑法是非数值方法, 采用多值逻辑和非单调逻辑采用多值逻辑和非单调逻辑来处理不确定性。新计算法认为概率法不足以描来处理不确定性。新计算法认为概率法不足以描述 不 确 定 性述 不 确 定 性 , 从 而 出 现 了 证 据

6、理 论从 而 出 现 了 证 据 理 论 ( 也 叫也 叫DempsterShafter, D-S方法方法), 确定性方法确定性方法(CF法法)以及模糊逻辑方法以及模糊逻辑方法。传统的有基于概率理论。传统的有基于概率理论的贝叶斯网络等。新的贝叶斯网络等。新概率法试图在传统的概率论概率法试图在传统的概率论框架内框架内, 采用新的计算方法以适应不确定性描述。采用新的计算方法以适应不确定性描述。n非形式化方法是指非形式化方法是指启发性方法启发性方法, 对不确定性没有对不确定性没有给出明确的概念。给出明确的概念。 9概述-分类(2)不确定推理方法：工程方法、控制方法和并行确定不确定推理方法：工程方法、

7、控制方法和并行确定性法。性法。n工程法是将问题简化为忽略哪些不确定性因素。工程法是将问题简化为忽略哪些不确定性因素。n控制法是利用控制策略来消除不确定性的影响控制法是利用控制策略来消除不确定性的影响, 如启发式的搜索方法。如启发式的搜索方法。n并行确定性法是把不确定性的推理分解为两个相并行确定性法是把不确定性的推理分解为两个相对独立的过程：一个过程不计不确定性采用标准对独立的过程：一个过程不计不确定性采用标准逻辑进行推理；另一过程是对第一个过程的结论逻辑进行推理；另一过程是对第一个过程的结论加以不确定性的度量。前一过程决定信任什么加以不确定性的度量。前一过程决定信任什么, 后一过程决定对它的信

8、任程度。后一过程决定对它的信任程度。 10第五章 不确定性推理n概述概述n概率论基础概率论基础nBayes网络网络n主观主观Bayes方法方法n确定性方法确定性方法n证据理论证据理论11第五章 不确定性推理n概述概述n概率论基础概率论基础nBayes网络网络n主观主观Bayes方法方法n确定性方法确定性方法n证据理论证据理论12概率论基础n概率论是研究随机现象中数量规律的科学。概率论是研究随机现象中数量规律的科学。所谓随机现象是指在相同的条件下重复进行所谓随机现象是指在相同的条件下重复进行某种实验时某种实验时, 所得实验结果不一定完全相同所得实验结果不一定完全相同且不可预知的现象。众所周知的是

9、掷硬币的且不可预知的现象。众所周知的是掷硬币的实验。人工智能所讨论的不确定性现象实验。人工智能所讨论的不确定性现象, 虽虽然不完全是随机的过程然不完全是随机的过程, 但是实践证明但是实践证明, 采用采用概率论的思想方法考虑能够得到较好的结果。概率论的思想方法考虑能够得到较好的结果。在这节中我们简单给出概率论的基本概念和在这节中我们简单给出概率论的基本概念和贝叶斯定理。贝叶斯定理。 13概率论基础(随机事件)n随机实验随机实验：随机实验是一个可观察结果的：随机实验是一个可观察结果的人工或自然的过程人工或自然的过程, 其产生的结果可能不止其产生的结果可能不止一个一个, 且不能事先确定会产生什么结果

10、。且不能事先确定会产生什么结果。 n样本空间样本空间：样本空间是一个随机实验的全：样本空间是一个随机实验的全部可能出现的结果的集合部可能出现的结果的集合, 通常记作通常记作, 中中的点的点(即一个可能出现的实验结果即一个可能出现的实验结果)成为样本成为样本点点, 通常记作通常记作。n随机事件随机事件：随机事件是一个随机实验的一：随机事件是一个随机实验的一些可能结果的集合些可能结果的集合, 是样本空间的一个子集。是样本空间的一个子集。常用大写字母常用大写字母A, B, C, 表示。表示。 14概率论基础(事件间的关系与运算 )n两个事件两个事件A与与B可能有以下几种特殊关系：可能有以下几种特殊关

11、系：q包含包含：若事件：若事件B发生则事件发生则事件A也发生也发生, 称称“A包含包含B”, 或或“B含于含于A”, 记作记作A B或或B A。q等价等价：若：若A B且且B A, 即即A与与B同时发生或同时不发生同时发生或同时不发生, 则称则称A与与B等价等价, 记作记作A=B。q互斥互斥：若：若A与与B不能同时发生不能同时发生, 则称则称A与与B互斥互斥, 记作记作AB=q对立对立：若：若A与与B互斥互斥, 且必有一个发生且必有一个发生, 则称则称A与与B对立对立, 记记作或作或, 又称又称A为为B的余事件的余事件, 或或B为为A的余事件。的余事件。n任意两个事件不一定会是上述几种关系中的

12、一任意两个事件不一定会是上述几种关系中的一种。种。 15概率论基础(事件间的关系与运算 )n设设A, B, A1, A2, An为一些事件为一些事件, 它们有下述它们有下述的运算：的运算：q交交：记：记C=“A与与B同时发生同时发生”, 称为事件称为事件A与与B的交的交, C=|A且且B, 记作或。记作或。 类似地用表示事件类似地用表示事件“n个事件个事件A1, A2, An同时发生同时发生”。q并并：记：记C=“A与与B中至少有一个发生中至少有一个发生”, 称为事件称为事件A与与B的的并并, C=|A或或B, 记作。记作。 类似地用表示事件类似地用表示事件“n个事件个事件A1, A2, An

13、中至少有一个中至少有一个发生发生”。q差差：记：记C=“A发生而发生而B不发生不发生”, 称为事件称为事件A与与B的差的差, C=|A但但B, 记作或。记作或。q求余求余：16AA概率论基础(运算的性质 )n事件的运算有以下几种性质：事件的运算有以下几种性质：q交换律：交换律：A B=B A A B=B Aq结合律：结合律： (A B) C=A (B C) (A B) C=A (B C)q分配律：分配律： (A B)C=(AC) (BC) (A B) C=(A C) (B C)q摩根律：摩根律： ( Ai)= Ai ( Ai)= Ain事件计算的优先顺序为：求余事件计算的优先顺序为：求余, 交

14、交, 差和并。差和并。 17概率论基础(概率定义 )n定义：设定义：设为一个随机实验的样本空间为一个随机实验的样本空间, 对对上的任意事件上的任意事件A, 规定一个实数与之对应规定一个实数与之对应, 记为记为P(A), 满足以下三条基本性质满足以下三条基本性质, 称为事称为事件件A发生的概率：发生的概率：q0 P(A) 1qP( )=1 P( )=0q若二事件若二事件AB互斥互斥, 即即AB= , 则则P(A B)=P(A)+P(B)n以上三条基本规定是符合常识的。以上三条基本规定是符合常识的。 18, 概率论基础(概率性质 )n定义：设定义：设An, n=1, 2, 为一组有限或可列为一组有

15、限或可列无穷多个事件无穷多个事件, 两两不相交两两不相交, 且且 An=, 则称事则称事件族件族An, n=1, 2, 为样本空间为样本空间的一个完的一个完备事件族备事件族, 又若对任意事件又若对任意事件B有有BAn=An或或, n=1, 2, , 则称则称An, n=1, 2, 为基本事件为基本事件族。族。n完备事件族与基本事件族有如下的性质：完备事件族与基本事件族有如下的性质： 定理：若定理：若An, n=1, 2, 为一完备事件族为一完备事件族, 则则 P(An)=1, 且对于一事件且对于一事件B有有P(B)= P(AnB)n有若有若An, n=1, 2, 为一基本事件族为一基本事件族,

16、 则则nP(B)= An BP(An)19, 概率论基础(统计概率性质 )n对任意事件对任意事件A, 有有0 P(A) 1n必然事件必然事件的概率的概率P() =1, 不可能事件不可能事件的概率的概率P() = 0n对任意事件对任意事件A, 有有P( A)=1- P(A)n设事件设事件A1, A2, An(kn)是两两互不相容的事是两两互不相容的事件件, 即有即有, 则则qP( i=1kAi)=P(A1)+P(Ak )n设设A, B是两事件是两事件, 则则qP(A B)=P(A)+P(B)-P(A B)20, 概率论基础(条件概率 )n定义：设定义：设A, B为事件且为事件且P(A)0, 称称

17、 P(B|A)=P(AB)/P(A)n为事件为事件A已发生的条件下已发生的条件下, 事件事件B的条件概的条件概率率, P(A)在概率推理中称为在概率推理中称为边缘概率边缘概率。简称。简称P(B|A)为给定为给定A时时B发生的概率。发生的概率。nP(AB)称为称为A与与B的的联合概率联合概率。有联合概率。有联合概率公式：公式：P(AB)=P(B|A)P(A)21概率论基础(条件概率性质 )n0 P(B|A) 1 nP( |A)=1, P( |A)=0n若若B1B2= , 则则qP(B1+B2|A)=P(B1|A)+P(B2|A)n乘法公式：乘法公式：P(AB)=P(A)P(B|A)P(A1An)

18、=P(A1)P(A2|A1)P(An|A1An-1)n全概率公式：设全概率公式：设A1, A2, An互不相交互不相交, Ai= , 且且P(Ai)0, 则对于任意事件则对于任意事件A有有P(A)= P(Ai)P(A|Ai)22概率论基础(贝叶斯定理 )n设设A, B1, B2, , Bn为一些事件为一些事件, P(A)0, B1, B2, , Bn互不相交互不相交, P(Bi)0, i=1, 2, , n, 且且 P(Bi)=1, 则对于则对于k=1, 2, , n, n贝叶斯公式容易由条件概率的定义贝叶斯公式容易由条件概率的定义, 乘法公式乘法公式和全概率公式得到。在贝叶斯公式中和全概率公

19、式得到。在贝叶斯公式中, P(Bi), i=1, 2, , n称为称为先验概率先验概率, 而而P(Bi|A) i=1, 2, , n称为称为后验概率后验概率也是条件概率。也是条件概率。 23() (|)(|)() (|)kkkiiiP B P A BP BAP B P A B).(,005. 0)(,005. 0,.95. 0)(,95. 0)(,:,ACPCPCAPCAPCA试试求求即即的的概概率率为为设设被被试试验验的的人人患患有有癌癌症症进进行行普普查查现现在在对对自自然然人人群群有有则则有有癌癌症症”表表示示事事件件“被被诊诊断断者者患患以以为为阳阳性性”表表示示事事件件“试试验验反反

20、应应若若以以验验具具有有如如下下的的效效果果某某种种诊诊断断癌癌症症的的试试根根据据以以往往的的临临床床记记录录 解解,95. 0)( CAP因为因为,995. 0)(,005. 0)( CPCP,05. 0)(1)( CAPCAP24由由贝叶斯公式得所求概率为贝叶斯公式得所求概率为)()()()()()()(CPCAPCPCAPCPCAPACP .087. 0 即平均即平均1000个具有阳性反应的人中大约只有个具有阳性反应的人中大约只有87人人患有癌症患有癌症.25第五章 不确定性推理n概述概述n概率论基础概率论基础nBayes网络网络n主观主观Bayes方法方法n确定性方法确定性方法n证据

21、理论证据理论26第五章 不确定性推理n概述概述n概率论基础概率论基础nBayes网络网络n主观主观Bayes方法方法n确定性方法确定性方法n证据理论证据理论27贝叶斯网络n二十世纪八十年代贝叶斯网络二十世纪八十年代贝叶斯网络(Bayes Network)成功地应用于成功地应用于专家系统专家系统, 成为表示不确定性专家知识和推理的一种流行的方成为表示不确定性专家知识和推理的一种流行的方法。基于贝叶斯方法的贝叶斯网络是一种适应性很广的手段和法。基于贝叶斯方法的贝叶斯网络是一种适应性很广的手段和工具工具, 具有坚实的数学理论基础。在综合先验信息具有坚实的数学理论基础。在综合先验信息(领域知识领域知识

22、)和数据样本信息的前提下和数据样本信息的前提下, 还可避免只使用先验信息可能带来还可避免只使用先验信息可能带来的主观偏见。虽然很多贝叶斯网络涉及的学习问题是的主观偏见。虽然很多贝叶斯网络涉及的学习问题是NP难解难解的。但是的。但是, 由于已经有了一些成熟的近似解法由于已经有了一些成熟的近似解法, 加上一些限制后加上一些限制后计算可大为简化计算可大为简化, 很多问题可以利用近似解法求解。很多问题可以利用近似解法求解。n贝叶斯网络方法的不确定性表示基本上是保持了概率的表示方贝叶斯网络方法的不确定性表示基本上是保持了概率的表示方式式, 可信度计算也是概率计算方法可信度计算也是概率计算方法, 只是在实

23、现时只是在实现时, 各具体系统各具体系统根据应用背景的需要采用各种各样的近似计算方法。推理过程根据应用背景的需要采用各种各样的近似计算方法。推理过程称为概率推理。因此称为概率推理。因此, 贝叶斯网络没有其它确定性推理方法拥贝叶斯网络没有其它确定性推理方法拥有的确定性表示、计算、语义解释等问题。由于篇幅关系有的确定性表示、计算、语义解释等问题。由于篇幅关系, 本本节只介绍贝叶斯网络的基本概念和简单的推理方法。节只介绍贝叶斯网络的基本概念和简单的推理方法。28贝叶斯网络(事件的独立性)n独立独立：如果：如果X与与Y相互独立相互独立, 则则 P(X, Y) = P(X)P(Y) P(X|Y) = P

24、(X)n条件独立条件独立：如果在给定：如果在给定Z的条件下的条件下, X与与Y相互相互独立独立, 则则 P(X|Y, Z) = P(X|Z)实际中实际中, 条件独立比完全独立更重要条件独立比完全独立更重要29贝叶斯网络(联合概率)n如果相互独立：如果相互独立：qP(X1, X2, , XN) = P(X1) P(X2) P(XN)n条件概率：条件概率：qP(X1, X2, , XN) = P(X1|X2, , XN) P(X2, , XN)n迭代表示：迭代表示：qP(X1, X2, , XN) = P(X1) P(X2| X1) P(X3| X2X1)P(XN|XN-1, , X1)= P(X

25、N) P(XN-1| XN) P(XN-2| XN-1XN)P(X1|X2, , XN)实际应用中就是利用条件独立性的性质简化网实际应用中就是利用条件独立性的性质简化网络复杂性的。络复杂性的。30贝叶斯网络(基本概念)贝叶斯网络：贝叶斯网络：n一系列变量的联合概率分布的图形表示。一系列变量的联合概率分布的图形表示。n一个表示变量之间的相互依赖关系的数一个表示变量之间的相互依赖关系的数据结构；图论与概率论的结合。据结构；图论与概率论的结合。31贝叶斯网络(因果关系网络)假设：假设：n命题命题S(smoker)：该患者是一个吸烟者：该患者是一个吸烟者n命题命题C(coal Miner)：该患者是一

26、个煤矿矿井工人：该患者是一个煤矿矿井工人n命题命题L(lung Cancer)：他患了肺癌：他患了肺癌n命题命题E(emphysema)：他患了肺气肿：他患了肺气肿n由专家给定的假设可知由专家给定的假设可知, 命题命题S对命题对命题L和命题和命题E有因果影有因果影响响, 而而C对对E也有因果影响。命题之间的关系可以描绘成因也有因果影响。命题之间的关系可以描绘成因果关系网。每一个节点代表一个证据果关系网。每一个节点代表一个证据, 每一条弧代表一条每一条弧代表一条规则规则(假设假设), 连接结点的弧表达了有规则给出的连接结点的弧表达了有规则给出的, 节点间的节点间的直接因果关系。其中直接因果关系。

27、其中, 节点节点S, C是节点是节点L和和E的父节点或称的父节点或称双亲节点双亲节点, 同时同时, L, E也称为是也称为是S和和C的子节点或称后代节的子节点或称后代节点。点。 32贝叶斯网络(因果关系图例)其中其中, 节点节点S, C是节点是节点L和和E的的父节点父节点或或称双亲节点称双亲节点, 同同时时, L, E也称为也称为是是S和和C的的子节子节点点或称后代节点。或称后代节点。 33SCEL因果关系图例 贝叶斯网络(贝叶斯网络)n贝叶斯网就是一个在弧的连接关贝叶斯网就是一个在弧的连接关系上加入连接强度的因果关系网系上加入连接强度的因果关系网络络 。 34贝叶斯网络(图例) 35BADE

28、FCG贝叶斯网络图例贝叶斯网络图例无环图和指定概率值无环图和指定概率值P(A), P(C), P(B|AC), P(E|B), P(D|B), P(F|E), P(G|DEF) 贝叶斯网络(图例) 非贝叶斯网络图例非贝叶斯网络图例 36BADCEGF贝叶斯网络(定义)n两个部分两个部分q贝叶斯网络结构图贝叶斯网络结构图, 这是一个有向无环图这是一个有向无环图(DAG: Directed Acyclic Graph), 其中图中的每个节点代其中图中的每个节点代表相应的变量。当有向弧由节点表相应的变量。当有向弧由节点A指向节点指向节点B时时, 则称：则称：A是是B的父节点；的父节点；B是是A的子节

29、点。的子节点。q节点和节点之间的条件概率表节点和节点之间的条件概率表(Conditional Probability Table, CPT), 也就是一系列的概率值也就是一系列的概率值, 表示了局部条件概率分布。表示了局部条件概率分布。P(node|parents) 。n目的：由证据得出原因发生的概率。目的：由证据得出原因发生的概率。 即观察到即观察到P(Y), 求求P(X|Y)37贝叶斯网络(如何构造)n选择变量选择变量, 生成节点生成节点n 从左至右从左至右(从上到下从上到下), 排列节点排列节点n填充网络连接弧填充网络连接弧, 表示节点之间的关系表示节点之间的关系n得到条件概率关系表得到

30、条件概率关系表条件概率表示的概率网络有时叫条件概率表示的概率网络有时叫“Belief Nets”38贝叶斯网络(计算)n有向非循环图是各个节点变量关系传递的合理有向非循环图是各个节点变量关系传递的合理表达形式。表达形式。n条件概率的引入使得计算较之全连接网络有了条件概率的引入使得计算较之全连接网络有了大大的简化。大大的简化。nCPT表相对比较容易得到。表相对比较容易得到。 有时可以用某种概率分布表示有时可以用某种概率分布表示, 需要做的指示计算需要做的指示计算表示的参数。表示的参数。39贝叶斯网络(计算续)n简单的联合概率可以直接从网络关系上得到简单的联合概率可以直接从网络关系上得到如：如：P

31、(X, Y) = P(X)P(Y|X)又如：又如：P(X, Y, Z) = P(X)P(Y)P(Z|X, Y)40XYP(X)P(Y|X)XZYP(X)P(Z|Y, X)P(Y)贝叶斯网络(例)CPT表为：表为：nP(S) = 0.4nP(C) = 0.3nP(E|S, C) = 0.9nP(E|S, C) = 0.3nP(E|S, C) = 0.5 贝叶斯网络实例图贝叶斯网络实例图nP(E|S, C) = 0.1 。 41SCELP(S)=0.4P(C)=0.3P(E|S, C)=0.9贝叶斯网络(例续)n上图例中的联合概率密度为上图例中的联合概率密度为n由图可知：由图可知：E与与L在在S条

32、件下独立条件下独立, 所以所以P(E|S, C, L) P(E|S, C), L与与C在在S, E条件下独立条件下独立, 所以所以P(L|S, C)= P(L|S), C与与S在在E条件下独立条件下独立, 所以所以P(C|S)=P(C) n以上三条等式的正确性以上三条等式的正确性, 可以从贝叶斯网的条件独立属性：每个变量可以从贝叶斯网的条件独立属性：每个变量与它在图中的非继承节点在概率上是独立的推出。同样与它在图中的非继承节点在概率上是独立的推出。同样, 从后面给出从后面给出的的D分离的定义的特性中也可以得到相同的结论。分离的定义的特性中也可以得到相同的结论。n简化后的联合概率密度为简化后的联

33、合概率密度为, 显然显然, 简化后的公式比原始的数学公式更加简单明了简化后的公式比原始的数学公式更加简单明了, 计算复杂度低很计算复杂度低很多。如果原贝叶斯网中的条件独立语义数量较多多。如果原贝叶斯网中的条件独立语义数量较多, 这种减少更加明显。这种减少更加明显。42)(*)|(*),|(*),|(),(SPSCPCSLPLCSEPELCSP)(*)(*)|(*),|(),(SPCPSLPCSEPELCSP贝叶斯网络(独立)n独立独立qP(X, Y) = P(X)P(Y)qP(X|Y) = P(X)qP(Y|X) = P(Y)n独立时求解独立时求解 q可以直接在网络图上求可以直接在网络图上求4

34、3贝叶斯网络(条件独立)n对于对于X, Y, E: X与与Y在给定在给定E的条件下独立的条件下独立qP(X|Y, E) = P(X|E)qP(Y|X, E) = P(Y|E)n多个变量组：多个变量组：d分离分离(d-separate) qP(X1, X2, , Xn|Y1, Y2, , Ym, E1, E2, , Ep) =P(X1, X2, , Xn|E1, E2, , Ep) q如果一组节点如果一组节点X在给定在给定E的条件下的条件下, 从从Xi到到Yj的每一条通的每一条通路都被即路都被即Ekd分离分离, 则称则称X独立于另一组节点独立于另一组节点Y (节点组节点组E d分离分离X与与Y)

35、44贝叶斯网络(D分离)n图中有三个节点图中有三个节点S, L, EnL(结果结果)影响影响S(起因起因), S影响影响E(另一个结果另一个结果)。n如果给定原因如果给定原因S后后, L并不能告并不能告诉我们有关诉我们有关E的更多事情。即的更多事情。即对于对于S, L和和E是相对独立的是相对独立的, 那么在计算那么在计算S和和L的关系时就的关系时就不用过多地考虑不用过多地考虑E, 将会大大将会大大减少计算复杂度。减少计算复杂度。n称称S能能D分离分离L和和E。nD分离是一种寻找条件独立的分离是一种寻找条件独立的有效方法。有效方法。 45SCELP(S)=0.4P(C)=0.3P(E|S, C)

36、=0.9贝叶斯网络( D分离-串行)nLinear 串行连接中串行连接中, 事件事件X通过事件通过事件Z影响事件影响事件Y, 反之反之事件事件Y也是通过事件也是通过事件Z影响事件影响事件X。但是。但是, 如果如果原因证据原因证据Z是给定的是给定的, X并不能给并不能给Y更多的东西更多的东西, 或者说或者说, 从从X那里得到更多的信息。此时称那里得到更多的信息。此时称, 如如果果Z是已知的是已知的, 那么通道就被阻塞那么通道就被阻塞, X和和Y就是独就是独立的了。则称立的了。则称X和和Y是被是被Z节点节点D分离的。分离的。 46XZY贝叶斯网络( D分离(分叉连接)Divergingn如果如果,

37、 父节点父节点Z是已知是已知的的, 没有更多的信息能没有更多的信息能够通过够通过Z影响到所有子影响到所有子节点。同理节点。同理, 父节点父节点Z是已知时是已知时, 子节点子节点X, , N是相互独立的。称子是相互独立的。称子节点节点X, , N是被是被Z节节点点D分离的。分离的。 47NYXZ。贝叶斯网络( D分离(汇集连接)汇集汇集(Converging)略有不同略有不同n如果不从父节点得到推断如果不从父节点得到推断, 子节子节点点Z就一无所知就一无所知, 那么那么, 父节点是父节点是相互独立的相互独立的, 它们之间没有相互它们之间没有相互影响。影响。n如果如果, 某事件影响了某事件影响了Z

38、, 那么那么, 各各个父节点就不是相互独立的了。个父节点就不是相互独立的了。该事件可以直接影响该事件可以直接影响Z, 也可以也可以通过它的后代节点影响通过它的后代节点影响Z。这种。这种现象称作条件依存。总之现象称作条件依存。总之, 如果如果子节点有了变化子节点有了变化, 或子节点的后或子节点的后代节点发生变化代节点发生变化, 信息是可以通信息是可以通过汇集连接传播的。过汇集连接传播的。 48ZNYX。贝叶斯网络( D分离(条件依存) 事件事件e直接影响节点直接影响节点Z 事件事件e影响节点影响节点Z的后代节点的后代节点 49ZNYX。eZNYX。LMe贝叶斯网络( D分离(定义)n对于给定的结

39、点集对于给定的结点集 , 如果对贝叶斯网中的结点如果对贝叶斯网中的结点Vi和和Vj之之间的每个无向路径间的每个无向路径(即不考虑即不考虑DAG图中弧的方向性的路图中弧的方向性的路径径), 在路径上都有某个结点在路径上都有某个结点Vb, 如果有属性：如果有属性：qVb在在 中中, 且路径上的两条弧都以且路径上的两条弧都以Vb为尾为尾(即弧在即弧在Vb处开始处开始(出发出发), 分叉分叉连接连接)qVb在在 中中, 路径上的一条弧以路径上的一条弧以Vb为头为头, 一条以一条以Vb为尾为尾(串行连接串行连接)qVb和它的任何后继都不在和它的任何后继都不在 中中, 路径上的两条弧都以路径上的两条弧都以

40、Vb为头为头(即弧在即弧在Vb处结束处结束, 汇集连接汇集连接, 但没有后代节点但没有后代节点) 则称则称Vi和和Vj 被被Vb结点阻塞。结点阻塞。n如果如果Vi和和Vj被证据集合被证据集合 中的任意结点阻塞中的任意结点阻塞, 则称则称Vi和和Vj是被是被 集合集合D分离分离, 结点结点Vi和和Vj条件独立于给定的证据集条件独立于给定的证据集合合 , 可形式化表示为：可形式化表示为：qP(Vi|Vj, )=P(Vi| )qP(Vj|Vi, )=P(Vj| )qI(Vj, Vi| )或或I(Vj, Vi| )50贝叶斯网络( D分离(图示) 51V Vi iVb3VjVb1 V Vb2证据集给定

41、证据结点集，Vi独立Vj：Vi到Vj的所有三条路径都被阻塞a)Vb1是证据结点，两条弧都以Vb1为尾b)Vb2是证据结点，一条以Vb2为头，一条以Vb2为尾c)Vb3及其任何后继都不在证据结点集中，两条弧都以Vb3为头贝叶斯网络( 定义)n条件独立条件独立：q如具有以上三个属性之一如具有以上三个属性之一, 就说结点就说结点Vi和和Vj条件独立于条件独立于给定的结点集给定的结点集 。n阻塞阻塞：q给定证据集合给定证据集合 , 当上述条件中的任何一个满足时当上述条件中的任何一个满足时, 就说就说Vb阻塞相应的那条路径。阻塞相应的那条路径。nD分离分离：q如果如果Vi和和Vj之间所有的路径被阻塞之间

42、所有的路径被阻塞, 就叫证据集合就叫证据集合 可以可以D分离分离Vi和和Vj52贝叶斯网络( D分离(例1) 53ZXYZX、Y独立独立X、Y条件独立条件独立YesYesXYZX、Y独立独立X、Y条件独立条件独立YesNoXYZX、Y独立独立X、Y条件独立条件独立YesNoXYZX、Y独立独立X、Y条件独立条件独立NoYesXYX、Y独立独立X、Y条件独立条件独立NoNo贝叶斯网络( D分离(例2) 54ZXYX草湿草湿Y彩虹彩虹Z下雨下雨P(X, Y)P(X)P(Y)P(X|Y, Z) = P(X|Z)ZXYX下雨下雨Y洒水洒水Z草湿草湿P(X, Y)= P(X)P(Y)P(X|Y, Z)

43、) P(X|Z)贝叶斯网络( D分离(例4)Radio and Ignition, given Battery? YesRadio and Start, given Ignition? YesGas and Radio, given Battery? YesGas and Radio, given Start? NoGas and Battery, given Moves? No 55BatteryRadioIgnitionGasMovesStart贝叶斯网络(推理)n建立贝叶斯网络的目的建立贝叶斯网络的目的q有了网络。可以提出问题：有了网络。可以提出问题：nP(问题问题|证据证据), 如：如

44、：P(吸烟吸烟|肺癌肺癌)q进行概率推理进行概率推理q与谓词逻辑有相似之处与谓词逻辑有相似之处 。如：患病。如：患病(吸烟吸烟, 肺癌肺癌)n在某些场合下有有效的推理方法。有一些工具包。在某些场合下有有效的推理方法。有一些工具包。n一般情况下是很困难的一般情况下是很困难的, 原因原因q不是所有的不是所有的CPT表都能够得到表都能够得到q网络结构大且复杂网络结构大且复杂qNP-hard推理推理n我们要做的是我们要做的是, 将问题正确的表示为合理的网络形式将问题正确的表示为合理的网络形式, 选用选用适合的算法。适合的算法。56贝叶斯网络(推理续)n贝叶斯网络通常使用因果或诊断规则与推理贝叶斯网络通

45、常使用因果或诊断规则与推理q因果规则：因果规则：X Cause Y with some probabilityq诊断诊断规则：规则：Y is evidence of X with some probabilityq因果推理：因果推理：Given cause C, determine P(Query|C)q诊断推理：诊断推理：Given evidence E, determine P(Query|E)57贝叶斯网络(推理续)n推理需求：推理需求：P(X|Y)q诊断诊断推理是从效果到起因推理是从效果到起因 证据是一些征兆：证据是一些征兆：X是起因是起因, Y是征兆是征兆q因果因果推理是从起因到效果

46、推理是从起因到效果 证据是一些起因：证据是一些起因： X是征兆是征兆, Y是起因是起因q解释解释历史历史 X和和Y是起因是起因, Z是两个起因的征兆。这时可以用一是两个起因的征兆。这时可以用一个起因个起因Y解释另一个起因解释另一个起因X。58贝叶斯网络(推理例)n下雨、草湿、洒水下雨、草湿、洒水59P(X)P(Y)下雨下雨草湿草湿Query:P(X|Y)P(X)P(Y)草湿草湿下雨下雨Query:P(X|Y)P(X)P(Z|X, Y)下雨下雨草湿草湿Query:P(X|Y, Z) and P(X|Z)P(Y)洒水洒水贝叶斯网络(推理例续)n条件：条件：q下雨下雨q草湿草湿q出现虫子出现虫子 n

47、 求：求：qP(Raining|Worm Sighting)60P(Y|X)下雨下雨草湿草湿Query:P(X|Z)P(X)出现出现虫子虫子P(Z|Y)贝叶斯网络(因果推理例)给定患者是一个吸烟者给定患者是一个吸烟者(S), 计算他患肺气肿计算他患肺气肿(E)的概率的概率P(E|S)。S称作推称作推理的证据理的证据, E叫询问结点。叫询问结点。 n首先首先, E的另一个父结点的另一个父结点(C), P(E|S)=P(E, C|S)+P(E, C|S);n右边的第一项右边的第一项 , P(E, C|S)P(E, C, S)/P(S)P(E|C, S)*P(C, S)/P(S)P(E|C, S)*

48、P(C|S)n同理可得公式的右边的第二项为：同理可得公式的右边的第二项为：P(E, C|S) = P(E|C, S)*P(C)。n由此可得：由此可得：nP(E|S) = P(E| C, S)*P(C)+P(E|C, S)*P(C)n如果采用概述中的例题数据如果采用概述中的例题数据, 有有P(C) = 1 - P(C), 则有则有, nP(E|S)0.9*0.3+0.3*(1-0.3)=0.48主要操作：主要操作：n按照给定证据的按照给定证据的V和它的所有双亲的联合概率和它的所有双亲的联合概率, 重新表达给定证据的重新表达给定证据的询问结点的所求条件概率。询问结点的所求条件概率。n直到所有的概率

49、值可从直到所有的概率值可从CPT表中得到表中得到, 推理完成。推理完成。61贝叶斯网络(推理自学)Artificial Intelligence: A New Synthesis Nils. J. Nilsson, 机械工业出版社机械工业出版社, 1999Probabilistic Inference in Polytrees (p.332)62第五章 不确定性推理n概述概述n概率论基础概率论基础nBayes网络网络n主观主观Bayes方法方法n确定性方法确定性方法n证据理论证据理论63第五章 不确定性推理n概述概述n概率论基础概率论基础nBayes网络网络n主观主观Bayes方法方法n确定性

50、方法确定性方法n证据理论证据理论64主观贝叶斯方法(概述)n在在Prospector的探矿系统的研究过程中提出的探矿系统的研究过程中提出的。的。 原有贝叶斯公式只考虑原有贝叶斯公式只考虑A出现对出现对B的影响的影响, 没有考虑没有考虑A不出现的影响。不出现的影响。 n贝叶斯规则：贝叶斯规则：当当B为为n个互不相容事件的集合时个互不相容事件的集合时, 贝叶斯公式可写为：贝叶斯公式可写为： 65P(A|B)P(B)P(B|A)P(A)n1jjjiii)P(BB|P(A)P(BB|P(AA)|P(Bn 1i跳过跳过主观贝叶斯方法(概述)n思路思路q先定好应该怎么办先定好应该怎么办, 再凑公式。主要是

51、避开再凑公式。主要是避开P(A| B)的计算。的计算。 66主观贝叶斯方法(概述)n规则的不确定性规则的不确定性q定义：定义：67(|)(|)(|)( )(|)()P B AP A BPB ALSP BP ABPB表示表示A A为真时为真时, , 对对B B的影响。的影响。( (规则成立的规则成立的充分性充分性) )(|)(|)(|)( )(|)()P BAPA BPBALNP BPABPB表示表示A为假时为假时, , 对对B的影响。的影响。( (规则成立的规则成立的必要性必要性) ) ( (确定性理论中没有考虑这点确定性理论中没有考虑这点) )主观贝叶斯方法(规则的不确定性)68P(X)-1

52、P(X)O(X) 几率函数几率函数O(X)|(1)|()|()|()|(ABPABPABPABPABO)(1)()(XOXOXPO(X)O(X)称为称为先验几率先验几率。表示证据。表示证据X X的出现概率和不出现的概率的出现概率和不出现的概率之比之比, , 显然显然O(X)O(X)是是P(X)P(X)的增函数的增函数, , 且有：且有：当当P(X)P(X)0, 0, 有有O(X)O(X)0 0当当P(X)P(X)0.5, 0.5, 有有 O(X)O(X)1 1当当P(X)P(X)1, 1, 有有O(X)O(X)由此可见由此可见, , 几率函数实际上表示了证据几率函数实际上表示了证据X X的不确

53、定性。的不确定性。相应有相应有, , 称为后验几率称为后验几率 )|(ABO主观贝叶斯方法(规则的不确定性)qO(X)的性质的性质nP(X) = 0时时, O(X) = 0假假nP(X) = 0.5时时, O(X) = 1nP(X) = 1时时, O(X) = 真真qO(X)与与LN, LS的关系的关系nO(B|A) = LS O(B)nO(B|A) = LN O(B)69主观贝叶斯方法(规则的不确定性)70BA O(B)A)|B O( 1BA O(B)A)|O(B 1BA O(B)A)|O(B 1LS不支持支持没影响对BA O(B)A)|B O( 1BA O(B)A)|O(B 1BA O(B

54、)A)|O(B 1LN不支持支持没影响对, , 且必须满足且必须满足：主观贝叶斯方法(规则的不确定性)qLS, LN0, 不独立。不独立。qLS, LN不能同时不能同时 1或或 1qLS, LN可同时可同时171主观贝叶斯方法(证据A的不确定性)nP(A)或或O(A)表示证据表示证据A的不确定性的不确定性72一般情况），（真当，假当0, 0)(1)()(AAAPAPAO主观贝叶斯方法(推理计算1)nA必出现时：必出现时：qO(B|A) = LSO(B)qO(B|A) = LNO(B) 若需要概率时：若需要概率时：73)(1)()(AOAOAP主观贝叶斯方法(推理计算2)A不确定时：即不确定时：

55、即P(A) 1 (1976年的算法年的算法)q向前看一步向前看一步A, A 为与为与A有关的所有观察有关的所有观察 P(B|A) = P(B|A)P(A| A)+P(B|A)P(A| A) nP(A| A) = 1时时, 证据证据A必然出现必然出现(P95)nP(A| A) = 0时时, LN代替上式代替上式 的的LS, 公式公式(2)nP(A| A) = P(A) 时时, (A对对A无影响无影响), 由上式由上式 P(B| A) = P(B)74) 1 (1)() 1()()|() |(BPLSBPLSABPABP主观贝叶斯方法(推理计算2)P(A| A)与与P(B| A)坐标系上的三点：坐

56、标系上的三点：(P96) 总之是找一些总之是找一些P(A| A)与与P(B| A)的相关值的相关值, 两点也可以做曲线两点也可以做曲线(或折线、直线或折线、直线)。由差值法从。由差值法从线上得到其它点的结果线上得到其它点的结果, 具体过程可参考教科书具体过程可参考教科书上例题。上例题。75)()()2(0) 1 (1) |(BPAPAAP公式公式主观贝叶斯方法(推理计算2)插值计算公式插值计算公式76)/()()()/()(1)()/()()()/(0)/()()/()()/( )/(AAPAPAPAAPAPBPABPBPAPAAPAAPAPABPBPABPABP线性插值图 770P(A)1P

57、(A|A)P(B|A)P(B|A)P(B)P(B|A)插值点主观贝叶斯方法(推理计算3)两个证据时：两个证据时：78) |(),|(min) |(2121AAPAAPAAAP) |(),|(max) |(2121AAPAAPAAAP主观贝叶斯方法(推理计算2)互相独立证据导出同一假设互相独立证据导出同一假设791212( /.)( /)( /)( /) .( )( )( )( )nnO B AAAO B AO B AO B AO BO BO BO B 例题(1)n已知：已知：P(A)=1, P(B1)=0.04, P(B2)=0.02R1:AB1 LS=20 LN=1R2:B1B2 LS=30

58、0 LN=0.001n计算：计算：P(B2|A)。分析：当使用规则。分析：当使用规则R2时时, 证据证据B1并不是确定的发生并不是确定的发生了了, 即即P(B1)1, 因此要采用插值方法。因此要采用插值方法。n解：先依照解：先依照A必然发生必然发生, 由定义和由定义和R1得：得：O(B1) = P(B1)/(1-P(B1) = 0.04/(1-0.04) = 0.0417O(B1|A) = LS*O(B1)=0.83P(B1|A) = O(B1|A )/(1+O(B1|A ) = 0.83/(1+0.83) = 0.454n然后假设然后假设P(B1|A)=1, 计算：计算： O(B2) = P

59、(B2)/(1-P(B2) = 0.02P(B2|B1) = LS*O(B2)/(1+ LS*O(B2) = 300*0.02/(300*0.02+1)=0.857n最后进行插值：最后进行插值：P(B1|A) P(B1), P(B2)=0.02, P(B1)=0.04 (已知已知), P(B2|A) = 0.02 + (0.857-0.02)(0.454-0.04)/(1-0.04) = 0.3880例题(2)n已知：证据已知：证据A1, A2必然发生必然发生, 且且P(B1)0.03 规则如下：规则如下：R1：A1B1 LS=20 LN=1; R2：A2B1 LS=300LN=1n求求B1的

60、更新值。的更新值。n解：解：依依R1, P1(B)0.03O(B1)0.03/(1-0.03)=0.030927O(B1|A1)=LSO(B1)=200.030927=0.61855P(B1|A1)= 0.61855/(1+0.61855)=0.382使用规则使用规则R1后后, B1的概率从的概率从0.03上升到上升到0.382依依R2：O(B1|A1A2)=300O(B1|A1)=185.565P(B1|A1A2)= 185.565/(1+185.565)=0.99464使用规则使用规则R2后后, B1的概率从的概率从0.382上升到上升到0.9946481主观贝叶斯方法n主观主观Bayes