人工智能课件140

人工智能原理第五章 不确定性推理第五章第五章 不确定性推理不确定性推理 概述 概率论基础 Bayes网络 主观Bayes方法 确定性方法 证据理论人工智能原理第五章 不确定性推理第五章第五章 不确定性推理不确定性推理 概述 概率论基础 Bayes网络 主观Bayes方法 确定性方法 证据理论人工智能原理第五章 不确定性推理概述概述 不精确思维并非专家的习惯或爱好所至，而是客观现实的要求。 很多原因导致同一结果 推理所需的信息不完备 背景知识不足 信息描述模糊 信息中含有噪声 规划是模糊的 推理能力不足 解题方案不唯一 在人类的知识和思维行为中，精确性只是相对的，不精确性才是绝对的。知识工程需要各种适应不同类的不精确性特点的不精确性知识描述方法和推理方法。人工智能原理第五章 不确定性推理概述概述-表示的表示的3 3方面问题方面问题 不确定问题的数学模型表示的3方面问题 表示问题：表达要清楚。表示方法规则不仅仅是数，还要有语义描述。 计算问题：不确定性的传播和更新。也是获取新信息的过程。人工智能原理第五章 不确定性推理不确定性推理例子不确定性推理例子例如，对于如下的推理过程： R1：A1A2B1 R2：A2A3B2 R3：B1B R4：B2B在描述这些规则时采用的都是不确定性知识表示方式人工智能原理第五章 不确定性推理推理树结果图推理树结果图 A A1 1A A2 2A A3 3ORORANDANDB B1 1B B2 2B BR R1 1R R2 2R R3 3R R4 4f f1 1f f4 4f f3 3f f2 2人工智能原理第五章 不确定性推理概述概述-表示的表示的3 3方面问题方面问题 语义问题：将各个公式解释清楚。语义问题语义问题：如何解释表示和计算的含义，目前多用概率方法。如：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）=?3）B 独立于A，f（B，A）=?对C（A）关心的是：1）A为TRUE，C（A）？2）A为FALSE, C（A）？ T：True，F：False人工智能原理第五章 不确定性推理概述概述-分类（分类（1 1）不确定性推理方法可分为形式化方法和非形式化方法。 形式化方法有逻辑法、新计算法和新概率法。逻辑法是非数值方法，采用多值逻辑和非单调逻辑来处理不确定性。传统的有基于概率理论的贝叶斯网络等。新计算法认为概率法不足以描述不确定性，从而出现了证据理论（也叫DempsterShafter， D-S方法），确定性方法（CF法）以及模糊逻辑方法。新概率法试图在传统的概率论框架内，采用新的计算方法以适应不确定性描述。 非形式化方法是指启发性方法，对不确定性没有给出明确的概念。 人工智能原理第五章 不确定性推理概述概述-分类（分类（2 2）不确定推理方法：工程方法、控制方法和并行确定性法。 工程法是将问题简化为忽略哪些不确定性因素。 控制法是利用控制策略来消除不确定性的影响，如启发式的搜索方法。 并行确定性法是把不确定性的推理分解为两个相对独立的过程：一个过程不计不确定性采用标准逻辑进行推理；另一过程是对第一个过程的结论加以不确定性的度量。前一过程决定信任什么，后一过程决定对它的信任程度。 人工智能原理第五章 不确定性推理第五章第五章 不确定性推理不确定性推理 概述 概率论基础 Bayes网络 主观Bayes方法 确定性方法 证据理论人工智能原理第五章 不确定性推理第五章第五章 不确定性推理不确定性推理 概述 概率论基础 Bayes网络 主观Bayes方法 确定性方法 证据理论人工智能原理第五章 不确定性推理概率论基础概率论基础 概率论是研究随机现象中数量规律的科学。所谓随机现象是指在相同的条件下重复进行某种实验时，所得实验结果不一定完全相同且不可预知的现象。众所周知的是掷硬币的实验。人工智能所讨论的不确定性现象，虽然不完全是随机的过程，但是实践证明，采用概率论的思想方法考虑能够得到较好的结果。在这节中我们简单给出概率论的基本概念和贝叶斯定理。 人工智能原理第五章 不确定性推理概率论基础概率论基础（随机事件）（随机事件） 随机实验：随机实验：随机实验是一个可观察结果的人工或自然的过程，其产生的结果可能不止一个，且不能事先确定会产生什么结果。 样本空间：样本空间：样本空间是一个随机实验的全部可能出现的结果的集合，通常记作，中的点（即一个可能出现的实验结果）成为样本点，通常记作。 随机事件随机事件：随机事件是一个随机实验的一些可能结果的集合，是样本空间的一个子集。常用大写字母A,B,C,表示。 人工智能原理第五章 不确定性推理概率论基础概率论基础（事件间的关系与运算事件间的关系与运算 ） 两个事件A与B可能有以下几种特殊关系： 包含：包含：若事件B发生则事件A也发生，称“A包含B”，或“B含于A”，记作AB或BA。 等价等价：若AB且BA，即A与B同时发生或同时不发生，则称A与B等价，记作A=B。 互斥互斥：若A与B不能同时发生，则称A与B互斥，记作AB= 对立：对立：若A与B互斥，且必有一个发生，则称A与B对立，记作或，又称A为B的余事件余事件，或B为A的余事件余事件。 任意两个事件不一定会是上述几种关系中的一种。 人工智能原理第五章 不确定性推理概率论基础概率论基础（事件间的关系与运算事件间的关系与运算 ） 设A，B，A1，A2，An为一些事件，它们有下述的运算： 交交：记C=“A与B同时发生”，称为事件A与B的交，C=|A且B，记作或。 类似地用表示事件“n个事件A1, A2, An同时发生”。 并并：记C=“A与B中至少有一个发生”，称为事件A与B的并，C=|A或B，记作。 类似地用表示事件“n个事件A1, A2, An中至少有一个发生”。 差差：记C=“A发生而B不发生”，称为事件A与B的差，C=|A但B，记作或。 求余求余：AA人工智能原理第五章 不确定性推理概率论基础概率论基础（运算的性质运算的性质 ） 事件的运算有以下几种性质： 交换率： 结合律： 分配律： 摩根率： 事件计算的优先顺序为：求余，交，差和并。 ABBABAAB )()(CBACBA)()(BCACAB)()()(BCACCBA)()(CBCACABiniiniAA)(11 iniiniAA)(11 人工智能原理第五章 不确定性推理概率论基础概率论基础（概率定义概率定义 ） 定义：定义：设为一个随机实验的样本空间，对上的任意事件A，规定一个实数与之对应，记为P(A)，满足以下三条基本性质，称为事件A发生的概率：若二事件AB互斥，即，则 以上三条基本规定是符合常识的。 1)(0AP， 1)(P0)(P)()()(BPAPBAP人工智能原理第五章 不确定性推理概率论基础概率论基础（概率性质概率性质 ） 定义定义：设An, n=1, 2, 为一组有限或可列无穷多个事件，两两不相交，且 ，则称事件族An, n=1, 2, 为样本空间的一个完备完备事件族事件族，又若对任意事件B有BAn=An或, n=1, 2, ，则称An, n=1, 2, 为基本事件族基本事件族。 完备事件族与基本事件族有如下的性质： 定理：若An, n=1, 2, 为一完备事件族，则 ，且对于一事件B有 有若An, n=1, 2, 为一基本事件族，则， nnA1)(nnAPnnBAPBP)()(BAnnAPBP)()(人工智能原理第五章 不确定性推理概率论基础概率论基础（统计（统计概率性质概率性质 ） 对任意事件A，有 必然事件的概率P() =1，不可能事件的概率P() = 0 对任意事件A，有 设事件A1，A2，An（kn）是两两互不相容的事件，即有，则 设A，B是两事件，则， 1)(0AP)(1)(APAP)(.)()()(211kikiAPAPAPAP)()()()(BAPBPAPBAP人工智能原理第五章 不确定性推理概率论基础概率论基础（条件（条件概率概率 ） 定义定义：设A，B为事件且P(A)0，称 为事件A已发生的条件下，事件B的条件条件概率概率，P(A)在概率推理中称为边缘概率边缘概率。 简称P(B|A)为给定A时B发生的概率。P(AB)称为A与B的联合概率。有联合概率公式：， )()()|(APABPABP)()|()(APABPABP人工智能原理第五章 不确定性推理概率论基础概率论基础（条件（条件概率性质概率性质 ） ， 若 ，则 乘法公式： 全概率公式：设A1，A2，An互不相交， ，且 ，则对于任意事件A有， 1)|(0ABP1)|( AP0)|(AP21BB)|()|()|(2121ABPABPABBP)|()()(ABPAPABP).|().|()|()().(12121312121nnnAAAAPAAAPAAPAPAAAPiiAniAPi,.,2 , 1, 0)(iiiAAPAPAP)|()()(人工智能原理第五章 不确定性推理概率论基础概率论基础（贝叶斯定理贝叶斯定理 ）， 设A，B1，B2，Bn为一些事件，P(A)0，B1，B2，Bn互不相交，P(Bi)0, i=1, 2, , n，且 ，则对于k=1, 2, , n，贝叶斯公式容易由条件概率的定义，乘法公式和全概率公式得到。在贝叶斯公式中，P(Bi), i=1, 2, , n称为先验概率先验概率，而P(Bi|A) i=1, 2, , n称为后验概率后验概率也是条件概率条件概率。 1)(iiBPiiikkkBAPBPBAPBPABP)|()()|()()|(人工智能原理第五章 不确定性推理没病的人有病的人检查结果正确检查结果错误各种情况的概率是多少？人工智能原理第五章 不确定性推理第五章第五章 不确定性推理不确定性推理 概述 概率论基础 Bayes网络 主观Bayes方法 确定性方法 证据理论人工智能原理第五章 不确定性推理第五章第五章 不确定性推理不确定性推理 概述 概率论基础 Bayes网络 主观Bayes方法 确定性方法 证据理论人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络二十世纪八十年代贝叶斯网络（Bayes Network）成功地应用于专家系统，成为表示不确定性专家知识和推理的一种流行的方法。基于贝叶斯方法的贝叶斯网络是一种适应性很广的手段和工具，具有坚实的数学理论基础。在综合先验信息（领域知识）和数据样本信息的前提下，还可避免只使用先验信息可能带来的主观偏见。虽然很多贝叶斯网络涉及的学习问题是NP难解的。但是，由于已经有了一些成熟的近似解法，加上一些限制后计算可大为简化，很多问题可以利用近似解法求解。 贝叶斯网络方法的不确定性表示基本上是保持了概率的表示方式，可信度计算也是概率计算方法，只是在实现时，各具体系统根据应用背景的需要采用各种各样的近似计算方法。推理过程称为概率推理。因此，贝叶斯网络没有其它确定性推理方法拥有的确定性表示、计算、语义解释等问题。由于篇幅关系，本节只介绍贝叶斯网络的基本概念和简单的推理方法。人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（事件的事件的独独立性立性） 独立：如果X与Y相互独立，则 P(X,Y) = P(X)P(Y) P(X|Y) = P(X) 条件独立：如果在给定Z的条件下，X与Y相互独立，则 P(X|Y, Z) = P(X|Z)实际中，条件独立比完全独立更重要人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（联合概率联合概率） 联合概率：P(X1, X2, , XN) 二值，则有2N可能的值，其中2N-1个独立。不是二值哪？ 如果相互独立： P(X1, X2, , XN) = P(X1) P(X2) P(XN) 条件概率： P(X1, X2, , XN) = P(X1|X2, , XN) P(X2, , XN)迭代表示：P(X1, X2, , XN) = P(X1) P(X2| X1) P(X3| X2X1)P(XN|XN-1, , X1) = P(XN) P(XN-1| XN) P(XN-2| XN-1XN)P(X1|X2, , XN)实际应用中就是利用条件独立性的性质简化网络复杂性的。人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（基本概念基本概念）贝叶斯网络： 一系列变量的联合概率分布的图形表示。 一个表示变量之间的相互依赖关系的数据结构；图论与概率论的结合。人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（因果关系网络因果关系网络）假设： 命题S(smoker)：该患者是一个吸烟者 命题C(coal Miner)：该患者是一个煤矿矿井工人 命题L(lung Cancer)：他患了肺癌 命题E(emphysema)：他患了肺气肿 由专家给定的假设可知，命题S对命题L和命题E有因果影响，而C对E也有因果影响。命题之间的关系可以描绘成因果关系网。每一个节点代表一个证据，每一条弧代表一条规则（假设），连接结点的弧表达了有规则给出的，节点间的直接因果关系。其中，节点S，C是节点L和E的父节点或称双亲节点，同时，L，E也称为是S和C的子节点或称后代节点。 人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（因果关系图例因果关系图例）其中， 节点S，C是节点L和E的父节点或称双亲节点，同时，L，E也称为是S和C的子节点或称后代节点。 SCEL因果关系图例 人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（贝叶斯网络贝叶斯网络） 贝叶斯网就是一个在弧的连接关系上加入连接强度的因果关系网络 。 人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（图例图例） BADEFCG贝叶斯网络图例无环图和指定概率值P(A), P(B), P(B|AC), P(E|C), P(D|C), P(F|E), P(G|DEF) 人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（图例图例） 非贝叶斯网络图例 BADCEGF人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（定义定义） 两个部分 贝叶斯网络结构图，这是一个有向无环图（DAG: Directed Acyclic Graph），其中图中的每个节点代表相应的变量。当有向弧由节点A指向节点B时，则称：A是B的父节点父节点；B是A的子节点子节点。节点和节点之间的条件概率表（Conditional Probability Table, CPT），也就是一系列的概率 值 ， 表 示 了 局 部 条 件 概 率 分 布 。P(node|parents) 。 目的：由证据得出原因发生的概率。 即观察到P(Y)，求P(X|Y)人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（如何构造如何构造） 选择变量，生成节点 从左至右（从上到下），排列节点 填充网络连接弧，表示节点之间的关系 得到条件概率关系表条件概率表示的概率网络有时叫“Belief Nets”人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（计算计算） 有向非循环图是各个节点变量关系传递的合理表达形式。 条件概率的引入使得计算较之全连接网络有了大大的简化。 CPT表相对比较容易得到。 有时可以用某种概率分布表示，需要做的指示计算表示的参数。人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（计算续计算续） 简单的联合概率可以直接从网络关系上得到如：P(X, Y) = P(X)P(Y|X)又如：P(X, Y, Z) = P(X)P(Y)P(Z|X, Y)XYP(X)P(Y|X)XZYP(X)P(Z|Y,X)P(Y)人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（例例）CPT表为： P(S) = .04 P(C) = 0.3 (E|S, C) = 0.9 P(E|S, C) = 0.3 P(E|S, C) = 0.5 贝叶斯网络实例图 P(E|S, C) = 0.1 。 SCELP(S)=0.4P(C)=0.3P(E|S,C)=0.9人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（例续例续）上图例中的联合概率密度为由图可知：E与L在S条件下独立，所以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) 以上三条等式的正确性，可以从贝叶斯网的条件独立属性：每个变量与它在图中的非继承节点在概率上是独立的推出。同样，从后面给出的D分离的定义的特性中也可以得到相同的结论。简化后的联合概率密度为， 显然，简化后的公式比原始的数学公式更加简单明了，计算复杂度低很多。如果原贝叶斯网中的条件独立语义数量较多，这种减少更加明显。)(*)|(*),|(*),|(),(SPSCPCSLPLCSEPELCSP)(*)(*)|(*),|(),(SPCPSLPCSEPELCSP人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（独立独立） 独立 P(X, Y) = P(X)P(Y) P(X|Y) = P(X) P(Y|X) = P(Y) 独立时求解 可以直接在网络图上求人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（条件独立条件独立） 对于X, Y, E: X与Y在给定E的条件下独立 P(X|Y,E) = P(X|E) P(Y|X,E) = P(Y|E) 多个变量组：d分离（d-separate） P(X1,X2,Xn|Y1,Y2,Ym,E1,E2,Ep) =P(X1,X2,Xn|E1,E2,Ep) 如果一组节点X在给定E的条件下，从Xi到Yj的每一条通路都被即Ekd分离，则称X独立于另一组节点Y (节点组E d分离X与Y)人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（D分离分离） 图中有三个节点S，L，E L（结果）影响S（起因），S影响E（另一个结果）。 如果给定原因S后，L并不能告诉我们有关E的更多事情。即对于S，L和E是相对独立的，那么在计算S和L的关系时就不用过多地考虑E，将会大大减少计算复杂度。 称S能D分离L和E。 D分离是一种寻找条件独立的有效方法。 SCELP(S)=0.4P(C)=0.3P(E|S,C)=0.9人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（ D分离分离-串行串行） Linear 串行连接中，事件X通过事件Z影响事件Y，反之事件Y也是通过事件Z影响事件X。但是，如果原因证据Z是给定的，X并不能给Y更多更多的东西，或者说，从X那里得到更多的更多的信息。此时称，如果Z是已知的，那么通道就被阻塞，X和Y就是独立的了。则称X和Y是被Z节点D分离的。 XZY人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（ D分离分离(分叉连接分叉连接)）Diverging 如果，父节点Z是已知的，没有更多的信息能够通过Z影响到所有子节点。同理，父节点Z是已知时，子节点X, , N是相互独立的。称子节点X, , N是被Z节点D分离的。 NYXZ。人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（ D分离分离(汇集连接汇集连接)）汇集(Converging)略有不同 如果不从父节点得到推断，子节点Z就一无所知，那么，父节点是相互独立的，它们之间没有相互影响。 如果，某事件影响了Z，那么，各个父节点就不是相互独立的了。该事件可以直接影响Z，也可以通过它的后代节点影响Z。这种现象称作条件依存。总之，如果子节点有了变化，或子节点的后代节点发生变化，信息是可以通过汇集连接传播的。 ZNYX。人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（ D分离分离(条件依存条件依存)） 事件e直接影响节点Z 事件e影响节点Z的后代节点 ZNYX。eZNYX。LMe人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（ D分离分离(定义定义)） 对于给定的结点集，如果对贝叶斯网中的结点Vi和Vj之间的每个无向路径（即不考虑DAG图中弧的方向性的路径），在路径上都有某个结点Vb，如果有属性： Vb在中，且路径上的两条弧都以Vb为尾（即弧在Vb处开始（出发），分叉连接） Vb在中，路径上的一条弧以Vb为头，一条以Vb为尾（串行连接） Vb和它的任何后继都不在中，路径上的两条弧都以Vb为头（即弧在Vb处结束，汇集连接，但没有后代节点） 则称Vi和Vj 被Vb结点阻塞。 如果Vi和Vj被证据集合中的任意结点阻塞，则称Vi和Vj是被集合D分离，结点Vi和Vj条件独立于给定的证据集合，可形式化表示为： ， 或 )|(),|(ijiVPVVP)|(),|(jijVPVVP)|,(jiVVI)|,(ijVVI人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（ D分离分离(图示图示)） V Vi iVb3VjVb1 V Vb2证据集给定证据结点集，Vi独立Vj：Vi到Vj的所有三条路径都被阻塞a)Vb1是证据结点，两条弧都以Vb1为尾b)Vb2是证据结点，一条以Vb2为头，一条以Vb2为尾c)Vb3及其任何后继都不在证据结点集中，两条弧都以Vb3为头人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（ 定义定义） 条件独立：条件独立： 如具有以上三个属性之一，就说结点Vi和Vj条件独立于给定的结点集。 阻塞：阻塞： 给定证据集合，当上述条件中的任何一个满足时，就说Vb阻塞相应的那条路径。 D D分离：分离： 如果Vi和Vj之间所有的路径被阻塞，就叫证据集合可以D分离Vi和Vj 人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（ D分离分离(例例1)） ZXYZX、Y独立X、Y条件独立YesYesXYZX、Y独立X、Y条件独立YesNoXYZX、Y独立X、Y条件独立YesNoXYZX、Y独立X、Y条件独立NoYesXYX、Y独立X、Y条件独立NoNo人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（ D分离分离(例例2)） ZXYX草湿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) ) P(X,Z)人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（ D分离分离(例例3)） XZWX草湿Y洒水者Z彩虹W长虫 P(X,Y) = P(X)P(Y)P(X|Y,Z) = P(X|Z)YXZWX草湿Y洒水者Z彩虹W长虫P(X,Y) P(X)P(Y)P(X|Y,Z) P(X|Z)Y人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（ 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 BatteryRadioIgnitionGasMovesStart人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（推理推理） 建立贝叶斯网络的目的 有了网络。可以提出问题： P(问题|证据)， 如：P(吸烟|肺癌） 进行概率推理 与谓词逻辑有相似之处 。如：患病（吸烟，肺癌） 在某些场合下有有效的推理方法。有一些工具包。 一般情况下是很困难的，原因 不是所有的CPT表都能够得到 网络结构大且复杂 NP-hard推理 我们要做的是，将问题正确的表示为合理的网络形式，选用适合的算法。人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（推理续推理续） 贝叶斯网络通常使用因果或诊断规则与推理 因果规则：X Cause Y with some probability 诊断规则 ：Y is evidence of X with some probability 因果推理：Given cause C, determine P(Query|C) 诊断推理：Given evidence E, determine P(Query|E)人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（推理续推理续） 推理需求：P(X|Y) 诊断推理是从效果到起因 证据是一些征兆：X是起因， Y是征兆 因果推理是从起因到效果 证据是一些起因： X是征兆， Y是起因 解释历史 X和Y是起因，Z是两个起因的征兆。这时可以用一个起因Y解释另一个起因X。人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（推理例推理例） 下雨、草湿、洒水P(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)洒水人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（推理例续推理例续） 条件： 下雨 草湿 出现虫子 求： P(Raining|Worm Sighting)P(Y|X)下雨草湿Query:P(X|Z)P(X)出现虫子P(Z|Y)人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（因果推理例因果推理例）给定患者是一个吸烟者（S），计算他患肺气肿（E）的概率P(E|S)。S称作推理的证据，E叫询问结点。 首先，E的另一个父结点（C），P(E|S)=P(E,C|S)+P(E,C|S);右边的第一项 ，P(E,C|S)P(E,C,S)/P(S)P(E|C,S)*P(C,S)/P(S)P(E|C,S)*P(C|S）同理可得公式的右边的第二项为：P(E,C|S) = P(E|C,S)*P(C)。由此可得：P(E|S) = P(E| C,S)*P(C)+P(E|C,S)*P(C)如果采用概述中的例题数据，有P(C) = 1 - P(C)，则有，P(E|S)0.9*0.3+0.3*(1-0.3)=0.48主要操作：按照给定证据的V和它的所有双亲的联合概率，重新表达给定证据的询问结点的所求条件概率。直到所有的概率值可从CPT表中得到，推理完成。人工智能原理第五章 不确定性推理贝叶斯网络贝叶斯网络（推理自学推理自学）Artificial Intelligence: A New Synthesis Nils. J. Nilsson, 机械工业出版社，1999Probabilistic Inference in Polytrees (p.332)人工智能原理第五章 不确定性推理第五章第五章 不确定性推理不确定性推理 概述 概率论基础 Bayes网络 主观Bayes方法 确定性方法 证据理论人工智能原理第五章 不确定性推理第五章第五章 不确定性推理不确定性推理 概述 概率论基础 Bayes网络 主观Bayes方法 确定性方法 证据理论人工智能原理第五章 不确定性推理主观主观贝叶斯贝叶斯方法方法( (概述概述） 在Prospector的探矿系统的研究过程中提出的。 原有贝叶斯公式只考虑A出现对B的影响，没有考虑A不出现的影响。 贝叶斯规则：当B为n个互不相容事件的集合时，贝叶斯公式可写为： P(A)B)P(B)|P(AA)|P(Bn1jjjiii)P(BB|P(A)P(BB|P(AA)|P(Bn 1i人工智能原理第五章 不确定性推理主观主观贝叶斯贝叶斯方法方法( (概述概述） 思路 先定好应该怎么办，再凑公式。主要是避开P(A| B)的计算。 人工智能原理第五章 不确定性推理主观主观贝叶斯贝叶斯方法方法( (概述概述） 规则的不确定性 定义：B)|P(AB)|P(ALS表示A为真时，对B的影响。（规则成立的充分性）B)|AP(B)|AP(LN 表示A为假时，对B的影响。（规则成立的必要性） （确定性理论中没有考虑这点）人工智能原理第五章 不确定性推理主观主观贝叶斯贝叶斯方法方法（规则的不确定性规则的不确定性） P(X)-1P(X)O(X) 几率函数O(X)|(1)|()|()|()|(ABPABPABPABPABO)(1)()(XOXOXPO(X)称为先验几率。表示证据X的出现概率和不出现的概率之比，显然O(X)是P(X)的增函数，且有：当P(X)0， 有O(X)0当P(X)0.5， 有 O(X)1当P(X)1， 有O(X)由此可见，几率函数实际上表示了证据X的不确定性。相应有， 称为后验几率 )|(ABO人工智能原理第五章 不确定性推理主观主观贝叶斯贝叶斯方法方法（规则的不确定性规则的不确定性） O(X)的性质 P(X) = 0时, O(X) = 0假 P(X) = 0.5时, O(X) = 1 P(X) = 1时, O(X) = 真 O(X)与LN，LS的关系 O(B|A) = LS O(B) O(B|A) = LN O(B)人工智能原理第五章 不确定性推理主观主观贝叶斯贝叶斯方法方法（规则的不确定性规则的不确定性）BA 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)A)|O(B 1LN不支持支持没影响对，且必须满足：人工智能原理第五章 不确定性推理主观主观贝叶斯贝叶斯方法方法（规则的不确定性规则的不确定性） LS、LN，不独立。 LS, LN不能同时 或 LS, LN可同时1人工智能原理第五章 不确定性推理主观主观贝叶斯贝叶斯方法方法（证据证据A的不确定性的不确定性）一般情况），（真当，假当0, 0)(1)()(AAAPAPAO P(A)或O(A)表示证据A的不确定性人工智能原理第五章 不确定性推理主观主观贝叶斯贝叶斯方法方法（推理计算推理计算1） A必出现时： O(B|A) = LSO(B) O(B|A) = LNO(B) 若需要概率时：)(1)()(AOAOAP人工智能原理第五章 不确定性推理主观主观贝叶斯贝叶斯方法方法（推理计算推理计算2）A不确定时：即P(A) 1 （1976年的算法） 向前看一步A， A 为与A有关的所有观察 P(B|A) = P(B|A)P(A| A)+P(B|A)P(A| A) P(A| A) = 1时，证据A必然出现（P95） P(A| A) = 0时，LN代替上式 的LS， 公式（2） P(A| A) = P(A) 时，(A对A无影响)，由上式 P(B| A) = P(B) 1 (1)() 1()()|() |(BPLSBPLSABPABP人工智能原理第五章 不确定性推理主观主观贝叶斯贝叶斯方法方法（推理计算推理计算2） P(A| A)与P(B| A)坐标系上的三点：(P96) 总之是找一些P(A| A)与P(B| A)的相关值， 两点也可以做曲线（或折线、直线）。由差值法从线上得到其它点的结果，具体过程可参考教科书上例题。)()()2(0) 1 (1) |(BPAPAAP公式公式人工智能原理第五章 不确定性推理主观主观贝叶斯贝叶斯方法方法（推理计算推理计算2）插值计算公式)/()()()/()(1)()/()()()/(0)/()()/()()/( )/(AAPAPAPAAPAPBPABPBPAPAAPAAPAPABPBPABPABP人工智能原理第五章 不确定性推理线性插值图线性插值图 0P(A)1P(A|A)P(B|A)P(B|A)P(B)P(B|A)插值点人工智能原理第五章 不确定性推理主观主观贝叶斯贝叶斯方法方法（推理计算推理计算3）两个证据时：) |(),|(min) |(2121AAPAAPAAAP) |(),|(max) |(2121AAPAAPAAAP人工智能原理第五章 不确定性推理主观主观贝叶斯贝叶斯方法方法（推理计算推理计算2）互相独立证据导出同一假设)()()/(.)()/()()/( )&.&/(2121BOBOABOBOABOBOABOAAABOnn人工智能原理第五章 不确定性推理例题（1）已知：P(A)=1,P(B1)=0.04, P(B2)=0.02R1:AB1 LS=20 LN=1R2:B1B2 LS=300 LN=0.001计算：P(B2|A)。分析：当使用规则R2时，证据B1并不是确定的发生了，即P(B1)1，因此要采用插值方法。解：先依照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.454然后假设P(B1|A)=1,计算： O(B2) = P(B2)/(1-P(B2) = 0.02P(B2|B1) = LS*O(B2)/(1+ LS*O(B2) = 300*0.02/(300*0.02+1)=0.857最后进行插值：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.38人工智能原理第五章 不确定性推理例题（2）已知：证据A1，A2必然发生，且P（B1）0.03 规则如下：R1：A1B1 LS=20 LN=1; R2：A2B1 LS=300LN=1求B1的更新值。解：依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.99464人工智能原理第五章 不确定性推理主观主观贝叶斯贝叶斯方法方法 主观Bayes方法的评价 优点： 计算方法直观、明了。 缺点： 要求Bj相互无关（实际不可能）。 P(A| B)与P(Bi) 很难计算。 应用困难。人工智能原理第五章 不确定性推理第五章第五章 不确定性推理不确定性推理 概述 概率论基础 Bayes网络 主观Bayes方法 确定性方法 证据理论人工智能原理第五章 不确定性推理第五章第五章 不确定性推理不确定性推理 概述 概率论基础 Bayes网络 主观Bayes方法 确定性方法 证据理论人工智能原理第五章 不确定性推理确定性方法确定性方法（可信度方法可信度方法） MYCIN系统研制过程中产生的不确定推理方法,第一个采用了不确定推理逻辑，70年代很有名。 提出该方法时应遵循的原则 不采用严格的统计理论。使用的是一种接近统计理论的近似方法。 用专家的经验估计代替统计数据 尽量减少需要专家提供的经验数据，尽量使少量数据包含多种信息。 新方法应适用于证据为增量式地增加的情况。 专家数据的轻微扰动不影响最终的推理结论。 人工智能原理第五章 不确定性推理 理论基础 以定量法为工具，比较法为原则的相对确认理论。 采用此方法的MYCIN系统的诊断结果不是只给出一个最可信结论及其可信度，而是给出可信度较高的前几位，供人们比较选用。 规则 规则的不确定性度量 证据（前提）的不确定性度量。 推理计算。确定性方法确定性方法人工智能原理第五章 不确定性推理 理论基础 以定量法为工具，比较法为原则的相对确认理论。 采用此方法的MYCIN系统的诊断结果不是只给出一个最可信结论及其可信度，而是给出可信度较高的前几位，供人们比较选用。 规则 规则的不确定性度量 证据（前提）的不确定性度量。 推理计算。确定性方法确定性方法人工智能原理第五章 不确定性推理 理论基础 以定量法为工具，比较法为原则的相对确认理论。 采用此方法的MYCIN系统的诊断结果不是只给出一个最可信结论及其可信度，而是给出可信度较高的前几位，供人们比较选用。 规则 规则的不确定性度量 证据（前提）的不确定性度量。 推理计算。确定性方法确定性方法人工智能原理第五章 不确定性推理 规则规则 ( (规则的不确定性度量）规则的不确定性度量） 规则 A B，可信度表示为CF(B, A)。P(B)A)|P(B , P(B)P(B)-A)|P(BP(B)A)|P(B , P(B)1P(B)-A)|P(BA) CF(B,当当人工智能原理第五章 不确定性推理 规则规则 ( (规则的不确定性度量）规则的不确定性度量） CF(B, A)表示的意义 证据为真时相对于P(B) = 1 - P(B)来说，A对B为真的支持程度。即A发生更支持B发生。 此时 CF(B, A) 0。 或，相对于P(B)来说，A对B为真的不支持程度。即A发生不支持B发生。 此时 CF(B, A) 0。 结论-1 CF(B, A) 1人工智能原理第五章 不确定性推理规则规则 ( (规则的不确定性度量）规则的不确定性度量） CF(B, A)的特殊值： CF(B, A) = 1，前提真，结论必真 CF(B, A) = -1，前提真，结论必假 CF(B, A) = 0 ， 前提真假与结论无关 实际应用中CF(B, A)的值由专家确定，并不是由P(B|A), P(B)计算得到的。人工智能原理第五章 不确定性推理 理论基础 以定量法为工具，比较法为原则的相对确认理论。 采用此方法的MYCIN系统的诊断结果不是只给出一个最可信结论及其可信度，而是给出可信度较高的前几位，供人们比较选用。 规则 规则的不确定性度量 证据（前提）的不确定性度量。 推理计算。确定性方法确定性方法人工智能原理第五章 不确定性推理 理论基础 以定量法为工具，比较法为原则的相对确认理论。 采用此方法的MYCIN系统的诊断结果不是只给出一个最可信结论及其可信度，而是给出可信度较高的前几位，供人们比较选用。 规则 规则的不确定性度量 证据（前提）的不确定性度量。 推理计算。确定性方法确定性方法人工智能原理第五章 不确定性推理规则规则 ( (证据的不确定性度量）证据的不确定性度量） 证据A的可信度表示为CF( A)同样有：-1 CF( A) 1 特殊值：CF( A) = 1， 前提肯定真 CF(A) = -1， 前提肯定假CF(A) = 0，对前提一无所知 CF( A) 0， 表示A以CF( A)程度为真CF( A) 0， 表示A以CF( A)程度为假人工智能原理第五章 不确定性推理 理论基础 以定量法为工具，比较法为原则的相对确认理论。 采用此方法的MYCIN系统的诊断结果不是只给出一个最可信结论及其可信度，而是给出可信度较高的前几位，供人们比较选用。 规则 规则的不确定性度量 证据（前提）的不确定性度量。 推理计算。确定性方法确定性方法人工智能原理第五章 不确定性推理 理论基础 以定量法为工具，比较法为原则的相对确认理论。 采用此方法的MYCIN系统的诊断结果不是只给出一个最可信结论及其可信度，而是给出可信度较高的前几位，供人们比较选用。 规则 规则的不确定性度量 证据（前提）的不确定性度量。 推理计算。确定性方法确定性方法人工智能原理第五章 不确定性推理规则规则 ( (推理计算推理计算 1 1） “与”的计算： A1 A2 BCF(A1 A2 ) = min CF(A1), CF(A2 ) “或”的计算：A1 A2 BCF(A1 A2 ) = max CF(A1), CF(A2 ) “非”的计算：CF(A ) = CF(A ) 由A， A B，求 B： CF(B) = CF(A )CF(B, ,A ) (CF(A ) 0 时可以不算即为“0”)人工智能原理第五章 不确定性推理规则规则 ( (推理计算推理计算 2 2） 合成，由两条规则求出再合并： 由CF(B)、 CF(B)，求 CF(B) 符号不同与当当 当(B)CF(B)CF (B)CF(B)CF0(B)CF0(B)CF (B)CF (B)CF(B)CF(B)CF0(B)CF0(B)CF (B)CF (B)CF-(B)CF(B)CFCF(B)2121212121212121，人工智能原理第五章 不确定性推理规则规则 ( (推理计算推理计算 3 3） 更新，由CF(A)、A B、CF(B, A )、CF(B)，求 B ： 当A必然发生，CF(A)=1时：符号不同与当当当A) CF(B,CF(B) A) CF(B,CF(B)0A) CF(B,0CF(B) CF(B)A)(1 CF(B,CF(B)0A) CF(B,0CF(B) CF(B)-A)(1 CF(B,CF(B)A)|CF(B，人工智能原理第五章 不确定性推理规则规则 ( (推理计算推理计算 4 4） 当A不必然发生，CF(A)1时： 0 CF(A) 1，用CF(A)CF(B, A)代替CF(A)=1时的CF(B, A)即可。 CF(A) 0，规则A B不可使用，即此计算不必进行。（如MYCIN系统CF(A)0.2就认为是不可使用的。其目的是使专家数据经轻微扰动不影响最终结果。） A)CF(B,)(CF(B)0A)CF(B,)(0CF(B) CF(B)A)(1CF(B,)(CF(B)0A)CF(B,)(0CF(B) CF(B)-A)(1CF(B,)(CF(B)A)|CF(B其他情形，ACFACFACFACFACF当 当人工智能原理第五章 不确定性推理规则规则 ( (推理计算推理计算 改进）改进） 注意：以上公式不满足组合交换性。 解决方法： 异号时 从定义上改进),(| |,)(min|1)(),(),()(ABCFBCFBCFABCFABCFBCF)()/(当)/(1)()()/()()/(当)(1)(/()()/(),(BPABPABPBPBPABPBPABPBPABPBPABPACBCF人工智能原理第五章 不确定性推理例题 已知：R1：A1B1CF（B1，A1）0.8 R2：A2B1 CF（B1，A2）0.5 R3：B1A3B2CF（B2，B1A3）0.8CF（A1）CF（A2）CF（A3）1；CF（B1）= CF（B2）=0； 计算 CF（B1）、CF（B2） 本题可图示为A1A2B1A3B2B1A30.80.50.8人工智能原理第五章 不确定性推理解：依规则R1，CF（B1|A1）CF（B1）CF（B1，A1）（1CF（B1）0.8， 即更新后CF（B1）0.8依规则R2：CF（B1|A2）CF（B1）CF（B1，A2）（1CF（B1）0.9 更新后CF（B1）0.9依R3，先计算CF（B1A3）min（CF（A3），CF（B1）0.9由于CF（B1A3）0且x为偶数人工智能原理第五章 不确定性推理证据理论证据理论 ( (预备知识（定义）预备知识（定义）) ) 子集定义：若B中的每个元素都是A中的元素，则称B是A的子集。也称A包含B或B含于A，记作B A，其符号化形式为B A x(x Bx A)若B不是A的子集，则记作B A，其符号化形式为B A x(x Bx A) 相等定义：若A包含B且B包含A，则称A与B相等,记作A=B，即 A=B x(x B x A) 真命题： AA 若AB且 AB，则 B A 若AB且 BC，则 A C人工智能原理第五章 不确定性推理证据理论证据理论 ( (预备知识（定义）预备知识（定义）) ) 真子集定义：若A为B的子集，且AB，则称A为B的真子集，或B真包含 A，记作AB。即 A B A BAB 真包含定义：若A为B的子集，且AB，则称A为B的真子集，或B真包含 A，记作AB。即 A B A BAB 全集定义：如果限定所讨论的集合都是某一集合的子集，则称该集合为全集。常记作E人工智能原理第五章 不确定性推理证据理论证据理论 ( (预备知识（定义）预备知识（定义）) ) 空集定义：不拥有任何元素的集合称为空集合，简称空集，记作。 定理：空集是一切集合的子集。 推论：空集是唯一的。人工智能原理第五章 不确定性推理证据理论证据理论 ( (预备知识（定义）预备知识（定义）) ) 幂集定义：称由A的所有子集组成的集合为A的幂集。记作2A 求幂集：设A=a,b,c0元子集为： 1元子集为：a,b,c2元子集为：a,b,a,c,b,c3元子集为：a,b,c=AA的幂集=,a,b,c,a,b,a,c,b,c,a,b,c 定理：A的元素个数| A |=n（n为自然数），则|2A |= n。人工智能原理第五章 不确定性推理证据理论证据理论 ( (预备知识（运算）预备知识（运算）) ) 并记定义：称A与B的所有元素组成的集合为A与B的并集。记作AB ， 称为并运算符。 AB 的描述表示 AB =x|x A x B A1, A2, An为n个集合，A1 A2 An = x| i(1in x Ai ,简记为iniA1人工智能原理第五章 不确定性推理证据理论证据理论 ( (预备知识（运算）预备知识（运算）) ) 交集定义：称A与B的公共元素组成的集合为A与B的交集。记作A B ， 称为交运算符。 A B 的描述表示 A B =x|x A x B A1, A2, An为n个集合，A1 A2 An = x| i(1in x Ai ,简记为iniA1人工智能原理第五章 不确定性推理证据理论证据理论 ( (预备知识（运算）预备知识（运算）) ) 互不相交定义：若A B= ， 称A，B是不交的，设 A1, A2, 可数个集合，若对任意i j，均有Ai Aj = ，则称A1, A2, 是互不相交的。人工智能原理第五章 不确定性推理证据理论证据理论 ( (预备知识（恒等式）预备知识（恒等式）) ) 等幂率：A A=A; A A=A 交换率：A B=BA; AB = BA 结合率：(A B)C= A (BC); (AB)C= A(BC) 分配率：A (BC)= (A B) (B C) A(B C)= (AB) (B C) 摩根率：(A B)=A B(AB) =AB人工智能原理第五章 不确定性推理证据理论证据理论 ( (预备知识（恒等式）预备知识（恒等式）) ) 吸 收 率 ： A ( A B ) = A ; A(AB)=A 零 率：AE=E; A = 同一率：A = A； A = 排中率：A A= E 矛盾率：AA= 全补率： =E; E= 双重否定率： （ A）= A 人工智能原理第五章 不确定性推理证据理论证据理论 ( (Evident Theory) )概述证据的不确定性规则的不确定性推理计算人工智能原理第五章 不确定性推理证据理论证据理论 ( (Evident Theory) )概述证据的不确定性规则的不确定性推理计算人工智能原理第五章 不确定性推理证据理论证据理论 ( (Evident Theory) ) 证据理论中，一个样本空间称为一个识别框架U， U由一系列对象构成，对象之间两两互斥，且包含当前要识别的全体对象。 证据理论的基本问题是，已知识别框架U，判明U中一个先验的未定元素属于U中某个子集A的程度。人工智能原理第五章 不确定性推理证据理论证据理论 ( (证据的不确定性证据的不确定性) ) 证据： 用集合U来表示：如U中的每个元素代表一种疾病。讨论一组疾病A发生的可能性时，A变成了单元（某些假设）的集合。 Ai中元素间是互斥的，但U内元素Ai间不是互斥的。人工智能原理第五章 不确定性推理据理论集合空间分布示意图据理论集合空间分布示意图 U UA1A2AnAiA3互斥单元集人工智能原理第五章 不确定性推理证据理论证据理论 ( (证据的不确定性证据的不确定性) ) 基本概率分配函数： m：0,1（在U的幂集上定义，取值0,1）m(A)表示了证据对的子集A成立的一种信任度有： 空集为零 意义若A属于，且不等于，表示对A的精确信任度若A等于，表示这个数不知如何分配1)(AmUA0)(m人工智能原理第五章 不确定性推理证据理论证据理论 ( (证据的不确定性证据的不确定性) ) 信任函数0,1。（在的幂集上定义，取值0,1）Bel(A) = 有: Bel() = m() = 0 , Bel() = = 1 Bel类似于概率密度函数，表示A中所有子集的基本概率分配数值的和，用来表示对A的总信任度。 UBm(B)ABBm)(人工智能原理第五章 不确定性推理证据理论证据理论 (