《不确定与非单调推理课件》由会员分享,可在线阅读,更多相关《不确定与非单调推理课件(61页珍藏版)》请在金锄头文库上搜索。
1、第五章 不确定与非单调推理n5.1 基本概念n5.2 概率方法n5.3 主观Bayes方法n5.4 可信度方法n5.5 证据理论n5.6 模糊理论n5.7 基于框架表示的不确定性推理n5.8 基于语义网络表示的不确定性推理n5.9 非单调推理不确定与非单调推理5.1 基本概念5.1.1 什么是不确定性推理什么是不确定性推理n不确定性推理是建立在非经典逻辑基础不确定性推理是建立在非经典逻辑基础上的一种推理,它是对不确定性知识的上的一种推理,它是对不确定性知识的运用与处理。运用与处理。n具体地说,所谓不确定性推理就是从不具体地说,所谓不确定性推理就是从不确定性的初始证据(即事实)出发,通确定性的初
2、始证据(即事实)出发,通过运用不确定性的知识,最终推出具有过运用不确定性的知识,最终推出具有一定程度不确定性的结论。一定程度不确定性的结论。不确定与非单调推理5.1.2 不确定性推理中的基本问题1. 不确定性的表示与度量不确定性的表示与度量不确定性推理中的不确定性推理中的“不确定性不确定性”一般分为两类:一是知一般分为两类:一是知识的不确定性,一是证据的不确定性。识的不确定性,一是证据的不确定性。知识不确定性的表示:目前在专家系统中知识的不确定知识不确定性的表示:目前在专家系统中知识的不确定性一般是由领域专家给出的,通常用一个数值表示,它性一般是由领域专家给出的,通常用一个数值表示,它表示相应
3、知识的不确定性程度,称为知识的静态强度。表示相应知识的不确定性程度,称为知识的静态强度。证据不确定性的表示:证据不确定性的表示方法与知识证据不确定性的表示:证据不确定性的表示方法与知识不确定性的表示方法一致,通常也用一个数值表示,代不确定性的表示方法一致,通常也用一个数值表示,代表相应证据的不确定性程度,称之为动态强度。表相应证据的不确定性程度,称之为动态强度。不确定与非单调推理2. 不确定性匹配算法及阈值的选择不确定性匹配算法及阈值的选择设计一个不确定性匹配算法;设计一个不确定性匹配算法;指定一个匹配阈值。指定一个匹配阈值。不确定与非单调推理3. 组合证据不确定性的计算方法最大最小法:T(E
4、1 AND E2)=minT(E1),T(E2)T(E1 OR E2)=maxT(E1),T(E2)概率法:T(E1 AND E2)=T(E1)T(E2)T(E1 OR E2)=T(E1)T(E2)T(E1)T(E2)有界法:T(E1 AND E2)=max0,T(E1)T(E2)1T(E1 OR E2)=min1,T(E1)T(E2)其中,T(E)表示证据E为真的程度(动态强度),如可信度、概率等。不确定与非单调推理4. 不确定性的传递算法不确定性的传递算法 在每一步推理中,如何把证据及知识的不确定在每一步推理中,如何把证据及知识的不确定性传递给结论,即如何计算结论的不确定性。性传递给结论,
5、即如何计算结论的不确定性。5. 结论不确定性的合成结论不确定性的合成用不同知识进行推理得到了相同结论,但所得用不同知识进行推理得到了相同结论,但所得结论的不确定性却不同。此时,需要用合适的结论的不确定性却不同。此时,需要用合适的算法对结论的不确定性进行合成。算法对结论的不确定性进行合成。不确定与非单调推理5.1.3 不确定性推理方法的分类n不确定性推理方法主要可分为模型法与控不确定性推理方法主要可分为模型法与控制法。制法。n模型法:在推理一级对确定性推理进行扩模型法:在推理一级对确定性推理进行扩展,引入证据的不确定性及知识的不确定展,引入证据的不确定性及知识的不确定性。性。n模型方法又分为数值
6、方法和非数值方法两模型方法又分为数值方法和非数值方法两类。数值方法对不确定性进行定量的描述,类。数值方法对不确定性进行定量的描述,按其所依据的理论又可分为基于概率的方按其所依据的理论又可分为基于概率的方法和基于模糊理论的方法。法和基于模糊理论的方法。不确定与非单调推理5.2 概率方法5.2.1 经典概率方法经典概率方法(1)设有如下产生式规则:)设有如下产生式规则:IFE THEN H其中,其中,E为前提条件,为前提条件,H为结论。条件概率为结论。条件概率P(H|E)可以作为在证据可以作为在证据E出现时结论出现时结论H的确定性程度,即规则的的确定性程度,即规则的静态强度。静态强度。(2)对于复
7、合条件)对于复合条件E=E1 AND E2 AND AND En当已知条件概率当已知条件概率P(H|E1,E2,En)时,就可把它作为在证时,就可把它作为在证据据E1,E2,En出现时结论出现时结论H的确定性程度。的确定性程度。(3)先验概率:)先验概率: P(H) 后验概率:后验概率: P(H|E)不确定与非单调推理若A1,A2,An是彼此独立的事件,对于事件B,则有其中,P(Ai)是事件Ai的先验概率;P(B|Ai)是在事件Ai发生条件下事件B的条件概率。对于一组产生式规则IFETHENHi同样有后验概率如下( Hi 确定性的程度,或规则的静态强度):5.2.2 逆概率方法不确定与非单调推
8、理对于多个证据对于有多个证据对于有多个证据E1,E2,Em和多个和多个结论结论H1,H2, Hn,并且每个证据都,并且每个证据都以一定程度支持结论的情况,上面的式子以一定程度支持结论的情况,上面的式子可进一步扩展为可进一步扩展为不确定与非单调推理逆概率方法举例例5.1 设H1,H2,H3分别是三个结论,E是支持这些结论的证据。已知:P(H1)=0.3, P(H2)=0.4, P(H3)=0.5P(E|H1)=0.5, P(E|H2)=0.3, P(E|H3)=0.4求P(H1|E),P(H2|E)及P(H3|E)的值各是多少?解:同理可得: P(H2|E)=0.26, P(H3|E)=0.43
9、不确定与非单调推理对应的产生式规则:对应的产生式规则:IFETHENH1IFETHENH2IFETHENH3 规则的静态强度规则的静态强度(Hi为真的程度、或不确定性程度为真的程度、或不确定性程度)P(H1|E)=0.32P(H2|E)=0.26P(H3|E)=0.43不确定与非单调推理逆概率法的特点优点:优点:n逆概率法有较强的理论背景和良好的数学特性,逆概率法有较强的理论背景和良好的数学特性,当证据彼此独立时计算的复杂度比较低。当证据彼此独立时计算的复杂度比较低。缺点:缺点:n逆概率法要求给出结论逆概率法要求给出结论Hi的先验概率的先验概率P(Hi)及条及条件概率件概率P(Ej|Hi)。不
10、确定与非单调推理n PROSPECTOR是国际上著名的一个用于勘察固体矿的专家系统,1982年美国地质调查资源分析局利用PROSPECTOR预测了华盛顿州一个勘探地段的钼矿位置,随后的实际钻井证明了其预测的正确性。基于贝叶斯理论的PROSPECTOR采用规则表达领域知识,每条规则有两个规则强度,LS和LN . 当领域专家和知识工程师在抽取 规则时,LS和LN是由领域专家给出的,且有LS , LN 0 . 一条规则,可表成如下形式:5.3 主观Bayes方法LS , LNEH不确定与非单调推理方框表示节点,方框表示节点,E表示规则前提,表示规则前提,H表示规则表示规则后件或结论,后件或结论,LS
11、是规则的充分性度量是规则的充分性度量,LN是是规则的必要性度量。除初始节点外,每个节规则的必要性度量。除初始节点外,每个节点都有一个先验概率,记为点都有一个先验概率,记为P(H)。 这个先验概率这个先验概率P(H)是在抽取规则的同时,是在抽取规则的同时,由领域专家给出的。由领域专家给出的。PROSPECTOR的不确定性的不确定性推理过程,就是根据证据的概率推理过程,就是根据证据的概率P(E)或或P(E|S),利用LS或LN,把结论把结论H的先验概率的先验概率P(H)更新更新为后验概率为后验概率P(H|E)的过程的过程。 不确定与非单调推理5.3.1 知识不确定性的表示 在主观Bayes方法中,
12、知识是用产生式规则表示的,具体形式为:IFE THEN (LS,LN) H (P(H)其中,nP(H)是结论H的先验概率,由专家根据经验给出。nLS称为充分性度量,用于指出E对H的支持程度,取值范围为0,),其定义为:LS=P(E|H)/P(E|H)。nLN称为必要性度量,用于指出 E对H的支持程度,取值范围为0,),其定义为:LN=P(E|H)/P(E|H)=(1-P(E|H)/(1-P(E|H)。nLS和LN的值由领域专家给出,相当于知识的静态强度。不确定与非单调推理5.3.2 证据不确定性的表示n在主观Bayes方法中,证据的不确定性也用概率表示。对于证据E,由用户根据观察S给出P(E|
13、S),即动态强度。用P(E|S)描述证据的不确定性 (证据E不是可以直接观测的)。n由于主观给定P(E|S)有所困难,所以实际中可以用可信度C(E|S)代替P(E|S)。n例如,在PROSPECTOR中C(E|S)取整数:-5,.5 C(E|S)=-5表示在观测S下证据E肯定不存在P(E|S)=0 C(E|S)= 5表示在观测S下证据E肯定存在P(E|S)=1 C(E|S)= 0表示S与E无关,即P(E|S)= P(E) 不确定与非单调推理n给定C(E|S)后,P(E|S)可近似计算如下:不确定与非单调推理5.3.3 组合证据不确定性的算法(1)最大最小法当组合证据是多个单一证据的合取时,即E
14、=E1 AND E2 AND AND En则:P(E|S)=minP(E1|S),P(E2|S),P(En|S)当组合证据是多个单一证据的析取时,即E=E1 OR E2 OR OR En则:P(E|S)=maxP(E1|S),P(E2|S),P(En|S)(2)对于“”运算则:P(E|S)=1-P(E|S)不确定与非单调推理 采用主观Bayes方法 IF E THEN (LS,LN) H (P(H) 时要解决的主要问题:(1)证据肯定存在时,如何计算P(H|E)? 此时P(E|S)=1。(2)证据肯定不存在时,如何计算P(H| E)? 此时P(E|S)=0。(3)证据具有不确定性时,如何计算P
15、(H|S)? 此时0P(E|S)1。这里S是对E的有关观察。不确定与非单调推理5.3.4 不确定性的传递算法(1)根据证据E的条件概率P(E|S) 及LS、LN的值,把H的先验概率P(H)更新为后验概率P(H|E) 。(2) 分以下3种情况讨论: 证据肯定存在: P(E|S)=1,即P(E)=1 证据肯定不存在: P(E|S)=0,即P(E)=0 证据不确定: 0P(E|S)1时,(H|E)=LS(H)(H),相应有P(H|E)P(H),表明由于证据E的存在,可增强H为真的程度(有利证据)。一般情况下LS1。n当LS1时,(H|E)=LS(H)(H),表明E与H无关(无关证据)。n当LS1时,
16、(H|E)=LS(H)(H),表明由于证据E的存在,减小了H为真的程度(不利证据)。n当LS0时,(H|E)=LS(H)0,表明由于证据E的存在,导致H为假(否定性的证据)。不确定与非单调推理证据肯定不存在时在证据肯定不存在时,P(E)=P(E|S)=0, P(E)=1。由Bayes公式得:P(H|E)=P(E|H)P(H)/P(E)(1)P(H|E)=P(E|H)P(H)/P(E)(2)(1)式除以(2)式得:P(H|E)/P(H|E)=P(E|H)/P(E|H)P(H)/P(H)根据必要性度量LN和几率函数的定义,可得:(H|E)=LN(H)即P(H|E)=LNP(H)/(LN-1)P(H
17、)+1不确定与非单调推理必要性度量LN的意义n对于知识: IF E THEN (LS,LN) H (P(H) 在证据E肯定不存在时,可以根据LN给出结论H的可信度P(H|E) 。n当LN1时,(H|E)=LN(H)(H),表明由于证据E不存在,减小了H为真的程度( E 为不利证据)。 一般情况下LN1时 , (H|E)=LN(H)(H), 相 应 有P(H|E)P(H),表明由于证据E不存在,增强了H为真的程度( E 为有利证据)。不确定与非单调推理LS1: 表明证据 E是对H有利的证据。 LN1:表明证据E是对H有利的证据。所以: 不能出现LS1且LN1的取值。LS1: 表明证据 E是对H不
18、利的证据。 LN1:表明证据E是对H不利的证据。所以: 不能出现LS1且LN1, LN1。不确定与非单调推理证据不确定时n当0P(E|S)0P(H1|S1)=P(H1)+P(H1|E1)-P(H1)1/5C(E1|S1) =0.122(H1|S1)=P(H1|S1)/(1- P(H1|S1)=0.14不确定与非单调推理R1:IF E1THEN(2, 0.001) H1R2:IF E2THEN(100, 0.001) H1R3:IF H1THEN(200, 0.01 ) H22. 计算(H1|S2)P(H1|E2)=(H1|E2)/(1+(H1|E2)= LS2(H1)/(1+LS2(H1)=0
19、.91C(E2|S2)=10P(H1|S2)=P(H1)+P(H1|E2)-P(H1)1/5C(E2|S2) =0.254(H1|S2)=P(H1|S2)/(1- P(H1|S2)=0.34不确定与非单调推理R1:IF E1THEN(2, 0.001) H1R2:IF E2THEN(100, 0.001) H1R3:IF H1THEN(200, 0.01 ) H23. 计算(H1|S1S2)(H1|S1S2)=(H1|S1)/(H1)(H1|S2)/(H1)(H1) =0.4764. 计算(H2|S1S2)(H1|S1S2)=0.476(H1)=0.1P(H2|S1S2)=P(H2)+ P(H
20、2|H1)-P(H2) /1-P(H1) P(H1|S1S2)-P(H1) =0.175(H2|S1S2)=P(H2|S1S2)/(1- P(H2|S1S2)=0.212不确定与非单调推理主观Bayes方法的特点优点:n主观Bayes方法中的计算公式大多是在概率论的基础上推导出来的,具有较坚实的理论基础。n知识的静态强度LS及LN是由领域专家给出,避免了大量的数据统计工作。n主观Bayes方法不仅给出了证据肯定存在、肯定不存在时更新后验概率的方法,还给出了证据不确定时的更新方法,实现了不确定性的逐级传递。缺点:n它要求领域专家在给出知识时,同时给出H的先验概率P(H),这比较困难。nBayes
21、定理要求事件间独立,使其应用受限制。不确定与非单调推理5.4 可信度方法n4.1 可信度的概念n根据经验对一个事物和现象为真的相信程度称为可信度。n在可信度方法中,由专家给出规则或知识的可信度,从而可避免对先验概率、或条件概率的要求。不确定与非单调推理5.4.2 C-F模型知识不确定性的表示:在C-F模型中,知识是用产生式规则表示的,其一般形式为:IFETHENH(CF(H,E)其中,CF(H,E)是该知识的可信度,称为可信度因子或规则强度,即静态强度。一般情况下,CF(H,E)-1,1。 CF(H,E)0对应于P(H|E)P(H); CF(H,E)0对应于P(H|E)P(H)时: 信任增长度
22、MB(H,E)0, 不信任增长度MD(H,E)=0 。n当P(H|E)0, 信任增长度MB(H,E) =0。nMB(H,E)与MD(H,E)是互斥的: 当MB(H,E)0时,MD(H,E)0 当MD(H,E)0时,MB(H,E)0不确定与非单调推理CF(H,E)的计算公式根据定义CF(H,E)=MB(H,E)-MD(H,E),及MB(H,E)与MD(H,E)的互斥性,可得:从上式可看出:CF(H,E)0对应于P(H|E)P(H);CF(H,E)0对应于P(H|E)0:表示证据以某种程度为真。 CF(E)0:表示结论以某种程度为真。 CF(H)0。不确定与非单调推理5.4.3 带有阈值限度的不确
23、定性推理1. 知识不确定性的表示知识用下述形式表示:IFETHENH(CF(H,E),)其中:nCF(H,E)为知识的可信度,取值范围为0,1。 CF(H,E)=0 对应于 P(H|E)=0 (证据绝对否定结论) CF(H,E)=1 对应于 P(H|E)=1 (证据绝对支持结论)n是阈值,明确规定了知识运用的条件:只有当CF(E)时,该知识才能够被应用。的取值范围为(0,1。不确定与非单调推理 IFETHENH(CF(H,E),)2. 证据不确定性的表示证据E的可信度仍为CF(E),但其取值范围为:0,1 CF(E)=1 对应于 P(E)=1 (证据绝对存在) ; CF(E)=0 对应于 P(
24、E)=0; (证据绝对不存在)3. 不确定性的传递算法当CF(E)时,CF(H)=CF(H,E)CF(E)不确定与非单调推理4. 结论不确定性的合成算法设有多条规则有相同的结论,即IFE1THEN H(CF(H,E1),1)IFE2THEN H(CF(H,E2),2)IFEnTHEN H(CF(H,En),n)如果这n条规则都满足:CF(Ei)i,i=1,2,n且都被启用,则首先分别对每条知识求出它对CFi(H);然后求结论H的综合可信度CF(H)。不确定与非单调推理求综合可信度的几种方法极大值法:CF(H)=maxCF1(H),CF2(H),CFn(H)加权求和法:有限和法:递推法:C1=C
25、F(H,E1)CF(E1)Ck=Ck-1+(1-Ck-1)CF(H,Ek)CF(Ek)不确定与非单调推理5.4.4 加权的不确定性推理1. 知识不确定性的表示IFE1(1) AND E2(2) ANDAND En(n) THEN H (CF(H,E),)其中i(i=1,2,n)是加权因子,是阈值,其值均由专家给出。加权因子的取值范围一般为0,1,且应满足归一条件,即2. 组合证据不确定性的算法若有CF(E1),CF(E2),CF( En),则组合证据的可信度为:不确定与非单调推理3. 不确定性的传递算法当一条知识的CF(E)满足如下条件时,CF(E)该知识就可被应用。结论H的可信度为:CF(H
26、)=CF(H,E)CF(E)n加权因子的引入不仅可以区分不同证据的重要性,同时还可以解决证据不全时的推理问题。不确定与非单调推理加权不确定性推理举例(1)例5.6 设有如下知识:R1: IF E1(0.6) AND E2(0.4) THEN E6(0.8,0.75)R2: IF E3(0.5) AND E4(0.3) AND E5(0.2) THEN E7(0.7,0.6)R3: IF E6(0.7) AND E7(0.3) THEN H(0.75,0.6)已知:CF(E1)=0.9, CF(E2)=0.8, CF(E3)=0.7,CF(E4)=0.6, CF(E5)=0.5求:CF(H)=?
27、解:由R1得到:CF(E1(0.6) AND E2(0.4)=0.861=0.75R1可被应用。不确定与非单调推理加权不确定性推理举例(2)由R2得到:CF(E3(0.5) AND E4(0.3) AND E5(0.2)0.632 =0.6R2可被应用。 CF(E1(0.6) AND E2(0.4)CF(E3(0.5) AND E4(0.3) AND E5(0.2)R1先被应用。由R1得到:CF(E6)=0.69由R2得到:CF(E7)=0.44由R3得到:CF(E6(0.7) AND E7(0.3)=0.6153 =0.6R3可被应用,得到:CF(H)=0.46即最终得到的结论H可信度为0.
28、46不确定与非单调推理5.4.5 前提条件中带有可信度因子的不确定性推理1. 知识不确定性的表示IFE1(cf1) AND E2(cf2) ANDAND En(cfn) THEN H (CF(H,E),)其中,cfi子条件Ei(i=1,2,n)的可信度。cfi在0,1上取值,其值由专家给出。核心思想:知识的前提条件不一定为真,只要前提条件满足一定的可信度,或具备一定的为真的可能性,就可以推出结论H。IFE1(cf1,1) AND E2(cf2,2) ANDAND En(cfn,n) THEN H (CF(H,E),2. 证据不确定性的表示证据Ei的可信度记为cfi,其取值范围在0,1上。不确定
29、与非单调推理3. 不确定性匹配算法n不带加权因子的不确定性匹配算法:知识:IFE1(cf1) AND E2(cf2) ANDAND En(cfn) THEN H (CF(H,E),)条件:E1(cf1),E2(cf2), En(cfn)匹配算法: max0,cf1-cf1+max0,cf2-cf2+ max0,cfn-cfnn带加权因子的不确定性匹配算法:知识:IFE1(cf1,1) AND E2(cf2,2) ANDAND En(cfn,n) THEN H (CF(H,E),)匹配算法:(1max0,cf1-cf1)+(2max0,cf2-cf2)+(nmax0,cfn-cfn) 不确定与非
30、单调推理4. 不确定性的传递算法不带加权因子时:CF(H)=(1-max0,cf1-cf1)(1-max0,cf2-cf2)(1-max0,cfn-cfn)CF(H,E)带加权因子时:CF(H)=(1(1-max0,cf1-cf1)(2(1-max0,cf2-cf2)(n(1-max0,cfn-cfn)CF(H,E)CF(H)=(1- 1 max0,cf1-cf1)(1- 2 max0,cf2-cf2)(1- n max0,cfn-cfn)CF(H,E)不确定与非单调推理基于可信度的不确定性推理方法的特点优点:n简单、直观。缺点:n可信度因子依赖于专家主观指定,没有统一、客观的尺度,容易产生片面性。n随着推理延伸,可信度越来越不可靠,误差越来越大。当推理深度达到一定深度时,有可能出现推出的结论不再可信的情况。不确定与非单调推理5.5 证据理论n证据理论是由A.P.Dempster首先提出,并由G.Shafer进一步发展起来的一种处理不确定性的理论,因此又称为D-S理论。1981年J.A.Barnett把该理论引入专家系统,同年J.Garvey等人用它实现了不确定性推理。由于该理论满足比概率论弱的公理,能够区分“不确定”与“不知道”的差异,并能处理由“不知道”引起的不确定性,具有较大的灵活性。不确定与非单调推理完谢谢不确定与非单调推理