人工智能：第5章 不确定性推理

1、*第5章 不确定性推理*本章内容不确定性推理中的基本问题证据理论概率方法主观Bayes方法4163可信度方法5不确定性推理方法分类 2*5.1 不确定性推理1. 什么是不确定性推理泛指除精确推理以外的其它各种推理问题。包括不完备、不精确知识的推理，模糊知识的推理，非单调性推理等。不确定性推理过程是从不确定的初始证据出发，通过运用不确定性知识，最终推出具有一定不确定性但却又是合理或基本合理的结论的思维过程。2. 为什么要采用不确定性推理证据不足或证据的不确定性规则的不确定性研究方法的不确定性天空有乌云，比较浓乌云很浓下雨的概率大很可能下雨*5.1 不确定性推理中的基本问题要实现对不确定性知识的处

2、理，须要解决1. 不确定知识表示问题知识不确定性的表示考虑因素：问题的描述能力 推理中不确定性的计算含义：知识的不确定性程度，或动态强度表示：用概率，0,1，0接近于假，1接近于真 用可信度，-1,1，大于0接近于真 小于0接近于假证据的不确定性表示证据来源：初始证据，中间结论 表示：用概率或可信度(EH,f(H，E)(命题E，C(E)前提假设规则强度不确定性*5.1 不确定性推理中的基本问题2.不确定信息计算问题不确定性的传递算法如何把证据及知识的不确定性传递给结论 把当前结论及其不确定性作为新的结论放入综合数据库，依次传递，直到得出最终结论已知规则的前提E的不确定性C(E)和规则强度f(H

3、,E)，求假设H的不确定性C(H)，即定义函数f1，使得： C(H)=f1(C(E),f(H,E)*5.1 不确定性推理中的基本问题2.不确定信息计算问题结论不确定性的合成多个不同知识推出同一结论，不确定性程度不同方法：视不同推理方法而定从不同角度给出：张三：下雨的概率0.8李四：下雨的概率0.6即已知由两个独立的证据E1和E2求得的假设H的不确定性度量C1(H)和C2(H)，求证据E1和E2的组合导致的假设H的不确定性C(H)，即定义函数f2，使得： C(H)=f2(C1(E),C2(H) *5.1 不确定性推理中的基本问题组合证据的不确定性算法知识的前提条件是多个证据的组合最大最小方法，C

4、(E1E2)=min(C(E1),C(E2) C(E1E2)=max(C(E1),C(E2)概率方法，C(E1E2)=C(E1)C(E2) C(E1E2)= C(E1)+C(E2)-C(E1)C(E2)有界方法，C(E1E2)=max0,C(E1)+C(E2)-1 C(E1E2)=min1,C(E1)+C(E2) 3.计算的语义解释问题知识的不确定性度量证据的不确定性度量长短不一木板组成桶能装多少水？木桶有多高?我班成绩全年级最高*5.1 不确定性推理方法分类模型方法模糊推理基于概率的方法主观Bayes方法确定性理论/可信度方法证据理论数值方法非数值方法不确定性推理模型法框架推理 语义网络推理

5、 常识推理经典概率方法*5.1 不确定性推理方法分类一、模型方法 特点：把不确定的证据和不确定的知识分别与某种度量标准对应起来，并且给出更新结论不确定性的算法，从而构成了相应的不确定性推理的模型。非数值方法是指出数值方法外的其他各种处理不确定性的方法 ,它采用集合来描述和处理不确定性，而且满足概率推理的性质。数值方法是对不确定性的一种定量表示和处理方法。*2、模糊推理1、基于概率的方法 对于数值方法，按其依据的理论不同又可分为以下两类： 5.1 不确定性推理方法分类纯概率方法虽然有严密的理论依据，但它通常要求给出事件的先验概率和条件概率，而这些数据又不易获得，因此其应用受到了限制。为了解决这这

6、个问题，人们在概率理论的基础上发展起来了一些新的方法及理论: P(支气管炎|咳嗽)*5.1 不确定性推理方法分类1、主观Bayes方法2、可信度方法3、证据理论它是PROSPECTOR专家系统中使用的不确定推理模型，是对Bayes公式修正后形成的一种不确定推理方法。 它是MYCIN专家系统中使用的不确定推理模型，它以确定性理论为基础。它通过定义信任函数、似然函数，把知道和不知道区别开来。* 设有如下产生式规则： IF E THEN H其中，E为前提条件，H为结论，具有随机性。条件概率表示该产生式规则的不确定性程度:在证据出现的条件下，结论H成立的确定性程度。对于复合条件 E = E1 AND

7、E2 AND AND En可以用条件概率作为在证据出现时结论的确定程度。5.2 主观Bayes方法经典概率方法*概率复习：样本空间在概率论中，把试验中每一个可能出现的结果称为试验的一个样本点，由全体样本点构成的集合称为样本空间。表示 通常，用D表示样本空间，d表示样本点。 例子 在掷币试验中，若用d1表示硬币的正面向上，用d2表示硬币的反面向上，则该试验的样本空间为： D=d1, d2*随机事件由样本点构成的集合称为随机事件例子：在掷币试验中，若用A表示硬币正面向上这一事件，则有 A=d1 运算 并事件 事件A与事件B至少有一个发生 记为AB 交事件 事件A与事件B同时发生 记为AB 互逆事件

8、 事件A与B之间满足“AB=, AB=D ” *统计概率频率： fn(A)=m/n A-事件，n-试验的总次数，m-实验中A发生的次数统计概率是通过某一事件出现的频率定义的： 在同一组条件下所进行大量重复试验时，如果事件A出现的频率总是在区间0,1上的一个确定常数p附近摆动，并且稳定于p，则称p为事件A的统计概率。即 P(A)=p *统计概率的性质(1) 对任一事件A，有 0P(A)=1 (2) 必然事件D 的概率P(D) =1， 不可能事件的概率P()=0。(3) 对任一事件A，有（否事件） P(A) = 1-P(A) (4) 设事件A1, A2 , Ak (kn)是两两互不相容的事件，即有

9、 AiAj= (ij)，则(5) 设A、B是两个事件，则 P(AB)=P(A)+P(B)-P(AB) 硬币正面、反面 下雨、不下雨 数10次下雨前打雷、闪电*条件概率定义：设A与B是两个随机事件，P(B)0，则称： P(A|B)=P(AB)/P(B) 为在事件B发生的条件下事件A 的条件概率 。*全概率公式定理：设事件A1,A2,An满足： (1) 任意两个事件都互不相容，即当ij时，有 AiAj= (i=1,2,n；j=1,2,n)； (2) P(Ai)0 (i=1, 2, ,n); (3) D= 则对任何事件B下式成立： 该全概率公式提供了一种计算P(B)的方法 下雨不、灯亮不P(地湿)=

10、P(雨)P(湿|雨)+ P(无雨)P(湿|无雨)*5.2 主观Bayes方法Bayes定理 设 为一些事件， 互不相交，P(Bi)0，i=1,2,n，且 则对于 有， 称？为先验概率/后验概率 P(Bk|A)不好计算时方法 P(Bk|A)大P(Bk)小说明Bk与A关系紧密P(胖|甜食)= P(胖)P(甜食|胖) P(胖)P(甜食|胖)+ P(瘦)P(甜食|瘦)+ P(适中)P(甜食|适中)*5.2 主观Bayes方法逆概率方法的基本思想 1单个证据的情况 如果用产生式规则 IF E THEN Hi （i1,2, , n）中前提条件E 代替Bayes公式中B，用Hi 代替Ai 就可得到 已知结论

11、Hi 的先验概率,逆概率：Hi 成立时E对应的证据出现的条件概率P(E|Hi)容易求一些。统计支气管炎病人中多少咳嗽*5.2 主观Bayes方法2多个证据的情况 对于有多个证据 和多个结论 ，并且每个证据都以一定程度支持结论的情况，上面的式子可进一步扩充为 *优点是有较强的理论背景和良好的数学特征，当证据及结论彼此独立时计算的复杂度比较低。缺点是要求给出结论 的先验概率 及证据 的条件概率 ，有些时候 比 相对容易得到,但总的来说，得到这些数据仍是相当困难的工作。Bayes公式的应用条件很严格：各事件互相独立等。若证据间存在依赖关系，不能直接使用。5.2 主观Bayes方法逆概率方法的优缺点*

12、5.2主观Bayes方法一、知识不确定性的表示 主观Bayes方法中，知识是用产生式规则表示： IF E THEN (LS，LN) H(P(H) E 是该知识的前提条件，简单或复合条件。H 是结论。P(H)是H 的先验概率，它指出在没有任何证据情况下的结论H为真的概率，即H 的一般可能性。其值由领域专家根据以往的实践及经验给出。（LS，LN）为规则强度，由领域专家给出值*充分性度量LS(指出E对H的支持程度)：0,+)必要性度量LN(指出E对H的支持程度)：0,+) E出现对H的影响E出现对H的影响P(湿|雨)/P(湿|无雨)P(干|雨)/P(干|无雨)*为讨论方便，下面引入几率函数X的几率等

13、于X出现的概率与X不出现的概率之比，P(X)与O(X)的变化一致，且有： P(X)=0 时有 O(X)=0 P(X)=1 时有 O(X)=+P(X)的0,1取值放大为O(X)的0,+ 取值*(1) LS当LS1时，O(H|E)O(H)，说明E支持H，LS越大，支持越充分。 当LS时，P(H/E)1，说明E的存在将导致H为真。当LS=1时，O(H|E)=O(H)，说明E对H没有影响。当LS1时，O(H|E)1时，O(H|E)O(H)，说明E支持H，LN得越大，支持就越强。 当LN时，P(H|E)1，E的存在，将导致H为真。当LN=1时，O(H|E)=O(H)，说明E对H没有影响。当LN1时，O(

14、H|E)0时，MD(H,E)=0 当MD(H,E)0时，MB(H,E)=0（2）值域 0MB(H,E)1 0MD(H,E)1 -1CF(H,E)1根据CF、MB、MD的定义，可得性质：2022/7/2047 当CF(H,E)=1时，有P(H|E)=1，它说明由于E所对应证据的出现使H为真。此时 MB(H,E)=l，MD(H,E)=0 当CF(H,E)=-1时，有P(H|E)=0，说明由于E所对应证据的出现使H为假。此时 MB(H,E)=O，MD(H,E)=1 当CF(H,E)=0时，则P(H|E)=P(H)，表示H与E独立即E所对应的证据的出现对H没有影响。（3）典型值根据CF、MB、MD的定

15、义，可得性质：2022/7/2048根据MB、MD的定义及概率的性质（4）对H的信任增长度等于对非H的不信任增长度根据CF、MB、MD的定义，可得性质：2022/7/2049再根据CF的定义及MB、MD的互斥性有 CF(H,E)+CF(H,E) =(MB(H,E)-MD(H,E)+(MB(H,E)-MD(H,E) =(MB(H,E)-0)+(O-MD(H,E) =MB(H,E)-MD(H,E)=0（4）对H的信任增长度等于对非H的信任增长度根据CF、MB、MD的定义，可得性质：2022/7/2050 对H的信任增长度等于对非H的不信任增长度。 对H的可信度与对非H的可信度之和等于0。 可信度不

16、是概率。对概率有 P(H)P(H)l 且 OP(H)，P(H)1而可信度不满足此条件。为此得到以下3个结论：根据CF、MB、MD的定义，可得性质：2022/7/20512.可信度的计算(1)规则不确定性的表示 在C-F模型中，规则用产生式规则表示: If E Then H (CF(H，E)E是规则的前提条件；H是规则的结论；注意： CF(H，E)是规则的可信度，也称为规则强度或知识强度，它描述的是知识的静态强度。这里前提和结论都可以是由复合命题组成。2022/7/2052在CF模型中，证据E的不确定性也是用可信度因子CF(E)来表示的，其取值范围同样是 -1，1，其典型值为: 当证据E肯定为真

17、时：CF(E)=1； 当证据E肯定为假时：CF(E)=-1； 当证据E一无所知时：CF(E)=0。(2)证据不确定性的表示2.可信度的计算*(3)组合证据不确定性的算法2.可信度的计算 1）当组合证据是多个单一证据的合取时，即 E = E1 and E2 and and En 时，如果已知 则 CF(E)=min 2）当组合证据E是多个单一证据的析取时，即 E = E1 or E2 or or En 时，如果已知 则， CF(E)=max *（4） 不确定性的传递算法 从不确定性的初始证据出发，运用相关的不确定性知识，最终推出结论及其可信度。 CF(H) = CF(H,E) max0, CF(

18、E) CF(E) 0 时， CF(H) = ? CF(E) = 1 时， CF(H) = ? 上限？下限？排除了什么？ 没考虑证据为假时对结论H产生的影响！2.可信度的计算*5.结论不确定性的合成算法设有如下知识 IF E1 THEN H (CF(H, E1) IF E2 THEN H (CF(H, E2)分别对每条知识求出CF(H) CF1(H) = CF(H,E1) max0, CF(E1) CF2(H) = CF(H,E2) max0, CF(E2)综合*5.3 可信度方法例5.4 已知 R1：IF A1 THEN B1 CF(B1,A1)=0.8； R2: IF A2 THEN B1

19、CF(B1,A2)=0.5； R3: IF B1A3 THEN B2 CF(B2,B1A3)=0.8;初始证据为A1,A2,A3的可信度CF均设为1， 即 CF(A1)= CF(A2)= CF(A3)=1,对B1,B2一无所知,求CF(B1)和CF(B2)。*5.3 可信度方法解:由于对B1,B2一无所知，所以使用合成算法进行计算。由题意得到推理网络如下图所示。B2B1A3A1A2*5.3 可信度方法(1)对于知识 ,分别计算 对每条知识求出CF(H) CF1(H) = CF(H,E1)max0,CF(E1)(2)利用合成算法计算 的综合可信度*5.3 可信度方法(3)计算 的可信度 这时，

20、作为 的证据，其可信度已由前面计算出来：CF( )=0.9 的可信度为初始的CF(A3)=1 。所以，可信度更新值分别为*5.4 证据理论证据理论也称DS(Dempster-Shafer)理论，是由德普斯特(A.P.Dempster)首先提出，他试图用一个概率范围而不是一个概率值来模拟不确定性。沙佛(G.Shafer)进一步发展该理论,处理不确定性 它将概率论中的单点赋值扩展为集合赋值，可以处理由“不知道”所引起的不确定性，比主观Bayes方法有着更大的灵活性。 概率理论怎么处理不知道？ N种可能性,不知道每种可能性的概率,怎么给值？ P=1/N （平均分配，无差别原理）*5.4 证据理论基本

21、概念 证据理论假设有一个不变的两两相斥的完备元素集合U，如下图所示，这里U 为 例如,U =三轮车，汽车，火车U =赤，橙，黄，绿，青，蓝，紫U =马，牛，羊，鸡，狗，兔图4.4 证据理论说明图*5.4 证据理论D-S理论证据理论是用集合表示命题的。设D是变量x所有可能取值的集合，且D中的元素是互斥的，在任一时刻x都取D中的某一个元素为值，则称D为x的样本空间。在证据理论中，D的任何一个子集A都对应于一个关于x的命题，称该命题为“x的值在A中”。 证据理论中，为了描述和处理不确定性，引入了概率分配函数、信任函数及似然函数等概念。* 5.4 证据理论DS理论处理集合上的不确定性问题，需先建立命题

22、与集合之间的一一对应关系，以把命题的不确定性问题转化为集合的不确定性问题。设为样本空间，且中的每个元素都相互独立，则由的所有子集构成的幂集记为2 。例. 设=红，黄，白，求的幂集2。解：的幂集可包括如下子集： A0=, A1=红, A2=黄, A3=白, A4=红，黄, A5=红，白, A6=黄，白, A7=红，黄，白其中，表示空集。上述子集的个数正好是23=8* 设D为样本空间，领域内的命题都用D的子集表示，则概率分配函数（Function of Probability Assignment）：定义4.6.1 设函数M ： ,且满足则称M是 上的概率分配函数，M(A)称为A的基本概率函数，即

23、对于样本空间D的任一子集都分配一个概率值。5.4 证据理论1、概率分配函数*对前面的例子 ，若定义2上的一个基本函数m： m( , 红, 黄, 白, 红，黄, 红，白, 黄，白, 红，黄，白) =(0, 0.3, 0, 0.1, 0.2, 0.2, 0, 0.2)其中，(0, 0.3, 0, 0.1, 0.2, 0.2, 0, 0.2)分别是幂集2中各个子集的基本概率数。显然m满足概率分配函数的定义。*概率分配函数的说明1. 作用是把的任一子集A映射为0,1上一个数m(A)A由单个元素组成，m(A)表示对A的精确信任度；A由多个元素组成，m(A)表示对A的精确信任度，但不知道这部分信任度该分给

24、A中哪些元素；例如当A=红有m(A)=0.3，表示对命题“x是红色”的精确信任度为0.3。 当B=红,黄有m(B)=0.2，表示对命题“x是红色或黄色”的精确信任度为0.2，却不知道该把这0.2分给红还是分给黄。2. 概率分配函数不是概率 如m(红)+m(黄)+m(白)=0.3+0+0.1=0.41* 定义4.6.2 设函数Bel： ,且 （ ）则称为命题A的信任函数（Function of Belief）,即命题A的信任函数值，就是A的所有子集的基本概率分配函数之和，用来表示对A的总信任。Bel函数又称为下限函数，以Bel（A）表示对命题A为真的信任程度。5.4 证据理论2. 信任函数*例如

25、， Bel(红)=0.3 Bel(红,白)=m(红) +m(白)+ m(红，白) =0.3+0.1+0.2=0.6 Bel() = m()=0 Bel(红，黄，白) =m()+m(红)+m(黄)+m(白)+m(红,黄)+ m(红,白)+ m(黄,白)+ m(红,黄,白) =0+0.3+0+0.1+0.2+0.2+0+0.2=1* 定义4.6.3 似然函数: ,且 （ ） 命题A的似然函数值就是所有与A相交的子集的基本概率分配函数之和，用来表示不否定A的信任度。似然函数（Plausible Function）又称为不可驳斥函数或上限函数5.4 证据理论3. 似然函数*例如 Pl(红)=1-Bel

26、(红) =1-Bel(黄,白) =1-(m黄+m白+m黄,白) =1-(0+0.1+0)=0.9这里的0.9是“红”为非假的信任度。由于“红”为真的精确信任度为0.3，而剩下的0.9-0.3=0.6，则是知道非假，但却不能肯定为真的那部分。再如 Pl(黄，白)=1-Bel(黄，白) =1-Bel(红)=1-0.3=0.7*由于可见，公式：似然函数的另外一种计算办法* 因 ,所以即 由于 表示对A为真的信任程度， 表示对A为非假的信任程度，因此可分别称 和 为对A信任程度的下限和上限，记作 (支持-不反对)5.4 证据理论4信任函数与似然函数的关系* 例如前面的例子 Bel(红)=0.3 Pl(

27、红)=0.9即： 红0.3, 0.9 它表示对红的精确信任度为0.3，不可驳斥部分为0.9，肯定不是红的为0.1。*一些典型值的含义 A0, 1：说明对A 一无所知。（表达出不知道） 其中，Bel(A)=0，说明对A无信任； 由Pl(A)=1知Bel(A)=0，说明对A也没有信任 不相信A为真，也不相信A为假 A0, 0：说明A为假。 即Bel(A)=0，Bel(A)=1。 A1, 1：说明A为真。 即Bel(A)=1，Bel(A)=0。*一些典型值的含义 A0.6, 1：说明对A部分信任。 即Bel(A)=0.6，Bel(A)=0。 A0, 0.4：说明对A部分信任。 即Bel(A)=0，B

28、el(A)=0.6。 A0.3, 0.9：说明对A和A都有部分信任。 Bel(A)=0.3，说明对A 为真有0.3的信任度； Bel(A)=1-0.9=0.1,说明对A为假有0.1的信任度*当证据来源不同时，可能会得到不同的概率分配函数。例如，对=红，黄假设从不同知识源得到两个概率分配函数分别为：m1( ,红,黄,红,黄)=(0,0.4,0.5,0.1)m2( ,红,黄,红,黄)=(0,0.6,0.2,0.2) 此时需要对它们进行组合，德普斯特提出的组合方法可对这两个概率分配函数进行正交和运算。5.4 证据理论5概率分配函数的正交和*5.4 证据理论定义4.6.4设 是两个概率分配函数，则其正

29、交和 为 其中， 如果 ,则正交和M也是一个概率分配函数；如果K0,则不存在正交和M，称 矛盾。 *5.4 证据理论定义4.6.5对于多个概率分配函数 ，如它们可组合，则可通过正交和运算将它们组合为一个概率分配函数。 设 是n个概率分配函数，则其正交 和 为其中 。*例. 设=a，b，且从不同知识源得到的概率分配函数分别为 m1(, a, b, a, b)=(0, 0.3, 0.5, 0.2) m2(, a, b, a, b)=(0, 0.6, 0.3, 0.1)求正交和m=m1 m2。解：先求K* 再求m(, a, b, a, b)，由于 同理可求得 m(b)=0.43 m(a, b)=0.

30、03故有 m(, a, b, a, b)=0, 0.54, 0.43, 0.03*5.4 证据理论定义4.6.56类概率函数 除了可以利用区间(Bel(A),Pl(A)表示A的不确定性以外，还可以用A的类概率函数表示A的不确定性。定义4.6.6 命题A的类概率函数为 其中，|A|和|D|分别是A及D中元素的个数。 具有如下性质：GOTO 也按元素个数分配 *例. 设=红，黄，白，概率分配函数m(,红,黄,白,红,黄,白)=(0, 0.6, 0.2, 0.1, 0.1)若A=红，黄，求f(A)的值。解： GOTOGOTO 也按元素个数分配 *5.4 证据理论知识的不确定性的表示用产生式规则表示： IF E THEN CF = (复合)前提条件E是样本空间D的子集结论H用样本空间中的子集表示， 是该子集中的元素。CF是可信度因子，用集合形式表示。 用来指出 的可信度， 应满足如下条件*5.4 证据理论4.6.4 证据的不确定性的表示不确定性证据E的确定性CER(E)，取值范围0,1。初始证据确定性由用户给出；当用前面推理所得结论作为当前推理的证据时，其确定性由推理