湘潭大学-人工智能课件-非经典推理-part-3.ppt

1、Artificial Intelligence (AI)人工智能人工智能第三章：非经第三章：非经典推理典推理内容提要1.1.经典推理和非经典推理经典推理和非经典推理2.2.不确定性推理不确定性推理3.3.概率推理概率推理4.4.主观贝叶斯方法主观贝叶斯方法5.5.可信度方法可信度方法可信度方法v可信度：可信度：是指人们根据以往经验对某个事物或现是指人们根据以往经验对某个事物或现象为真的程度的一个判断，或者说是人们对某个象为真的程度的一个判断，或者说是人们对某个事物或现象为真的相信程度。在可信度方法中，事物或现象为真的相信程度。在可信度方法中，由专家给出规则或知识的可信度，从而由专家给出规则或知

2、识的可信度，从而避免对先避免对先验概率、条件概率的要求验概率、条件概率的要求。v可信度方法是肖特里菲（可信度方法是肖特里菲（Shortliffe）等人在确定）等人在确定性理论基础上结合概率论等理论提出的一种不精性理论基础上结合概率论等理论提出的一种不精确推理模型。确推理模型。v由于该方法直观、简单而且效果好，在专家系统由于该方法直观、简单而且效果好，在专家系统等领域获得了较为广泛的应用。等领域获得了较为广泛的应用。知识的不确定性表示vC-F模型：模型：基于可信度表示的不确定性推理的基本基于可信度表示的不确定性推理的基本方法，其他可信度方法都是基于此发展而来。方法，其他可信度方法都是基于此发展而

3、来。v知识的不确定性表示：知识的不确定性表示：在在C-F模型中，知识是用产模型中，知识是用产生式规则表示的，其一般形式为：生式规则表示的，其一般形式为： IF E THEN H (CF(H, E)E：知识的前提条件，可以是单一或复合条件知识的前提条件，可以是单一或复合条件H：知识的结论，可以是单一结论或多个结论知识的结论，可以是单一结论或多个结论CF(H, E)：知识的可信度，称为知识的可信度，称为可信度因子可信度因子 ( Certainty Factor) 或或规则强度规则强度。知识的不确定性表示一般情况下，一般情况下， CF(H, E)的取值为的取值为-1, 1，表示当证据，表示当证据E为

4、真时，对结论为真时，对结论H的支持程度。其值越大，表示支持程的支持程度。其值越大，表示支持程度越大。度越大。p CF(H,E)0对应于对应于P(H|E)P(H);p CF(H,E)=0对应于对应于P(H|E)=P(H)；p CF(H,E)0对应于对应于P(H|E)P(H)时：时： E的出现增加了的出现增加了H的概率的概率pMB(H,E)0，MD(H,E)=0 当当P(H|E)0v因此，因此，CF(H, E)的计算公式：的计算公式：(| )() (,) 00 (| )()1()(,) 0 (| )()()(| ) 0(,)0(| )()()P H EP HMB H EP H EP HP HCF

5、H EP H EP HP HP H EMD H EP H EP HP H 当当当知识的不确定性表示v可信度的性质：可信度的性质：互斥性：互斥性：对同一证据，不可能既增加对对同一证据，不可能既增加对H的信任程度，的信任程度，又同时增加对又同时增加对H的不信任程度，即的不信任程度，即MB与与MD是互斥的是互斥的p 当当MB(H, E)0时，时，MD(H, E)=0p 当当MD(H, E)0时，时，MB(H, E)=0值域：值域：MB(H, E) 0,1; MD(H, E) 0,1; CF(H, E) -1,1,p当且仅当当且仅当P(H|E)=1时时, CF(H,E)=1 p当且仅当当且仅当P(H|

6、E)=0时时, CF(H,E)=-1pCF(H,E)定性地反映了定性地反映了P(H|E)的大小，因此可以用的大小，因此可以用CF(H,E)近似表示近似表示P(H|E) ，描述规则的可信度。，描述规则的可信度。知识的不确定性表示v可信度的性质：可信度的性质：对对H的信任增长度等于对非的信任增长度等于对非H的不信任增长度的不信任增长度再根据再根据CF的定义和的定义和MB、MD的互斥性有的互斥性有 CF(H,E)+CF(H,E)=0(|)()(1(|)(1()()(1()(|)()( (|)()(1()(1()(|)()()1(,)(,)PH EPHP H EP HPHP HP H EP HP H

7、EP HP HP HP H EMPBMDHPH EEHH信任增长度知识的不确定性表示v可信度的性质：可信度的性质：对前提对前提E，若支持若干个不同的结论，若支持若干个不同的结论Hi(i=1,2,n)，则，则因此，如果发现专家给出的知识有如下情况因此，如果发现专家给出的知识有如下情况 CF(H1, E)=0.7, CF(H2, E)=0.4则因则因0.7+0.4=1.11为非法，应进行调整或规范化。为非法，应进行调整或规范化。niiEHCF11),(证据不确定性的表示v证据不确定性的表示证据不确定性的表示证据的证据的E不确定性也用可信度因子不确定性也用可信度因子CF(E)表示表示CF(E)的取值

8、范围：的取值范围：-1，+1。 p CF(E)=1，证据，证据E肯定它为真肯定它为真p CF(E)=-1，证据，证据E肯定它为假肯定它为假p CF(E)=0，对证据，对证据E一无所知一无所知p 0CF(E)1，证据，证据E以以CF(E)程度为真程度为真p -1CF(E)0，证据，证据E以以CF(E)程度为假程度为假组合证据的不确定性v否定证据的不确定性计算否定证据的不确定性计算 CF(E)= CF(E)v组合证据的不确定性计算：组合证据的不确定性计算：可采用最大最小法可采用最大最小法 当组合证据当组合证据E是多个单一证据的合取时，若已知是多个单一证据的合取时，若已知CF(E1), , CF(E

9、n)，则，则: CF(E)=minCF(E1), CF(E2), ,CF(En) 当组合证据当组合证据E是多个单一证据的析取时，若已知是多个单一证据的析取时，若已知CF(E1), , CF(En)，则，则: CF(E)=maxCF(E1), CF(E2), ,CF(En) 不确定性的更新v不确定性的更新不确定性的更新IF E THEN H (CF(H, E)v结论结论H的可信度由下式计算：的可信度由下式计算： CF(H)=CF(H,E)max0,CF(E)CF(H)的取值范围：的取值范围：-1，+1。 CF(H)=0: CF(E)0: 表示结论以某种程度为真表示结论以某种程度为真CF(H)0:

10、 表示结论以某种程度为假表示结论以某种程度为假结论不确定性的合成v结论不确定性的合成结论不确定性的合成若由多条不同知识推出了相同的结论，但可信度不同，若由多条不同知识推出了相同的结论，但可信度不同，则用合成算法求出综合可信度。设有知识：则用合成算法求出综合可信度。设有知识： IF E1 THEN H (CF(H, E1)IF E2 THEN H (CF(H, E2)则结论则结论H 的综合可信度可分以下两步计算：的综合可信度可分以下两步计算：(1) 分别对每条知识求出其分别对每条知识求出其CF(H)。即。即 CF1(H)=CF(H, E1) max0, CF(E1) CF2(H)=CF(H, E

11、2) max0, CF(E2)结论不确定性的合成v结论不确定性的合成结论不确定性的合成(2) 用如下公式求用如下公式求E1与与E2对对H的综合可信度的综合可信度 121212121212121122()()()()()0()0()()()()()0()()0()()()1min() ,()()CF HCF HCF HCF HCF HCF HCF HCF HCF HCF HCF HCF HCF HCF HCF HCF HCF HCF HCF H若且若且若与异号可信度方法v例：例：设有如下一组知识：设有如下一组知识：r1：IF E1 THEN H (0.9)r2：IF E2 THEN H (0.6

12、)r3：IF E3 THEN H (-0.5)r4：IF E4 AND ( E5 OR E6) THEN E1 (0.8)已知：已知：CF(E2)=0.8，CF(E3)=0.6，CF(E4)=0.5，CF(E5)=0.6, CF(E6)=0.8求：求：CF(H)=? 可信度方法 解：解：由由r4得到：得到： CF(E1) = 0.8max0, CF(E4 AND (E5 OR E6) = 0.8max0, minCF(E4), CF(E5 OR E6) = 0.8max0, minCF(E4), maxCF(E5), CF(E6) = 0.8max0, minCF(E4), max0.6, 0

13、.8 = 0.8max0, min0.5, 0.8 = 0.8max0, 0.5 = 0.4 由由r1得到：得到： CF1(H) = CF(H, E1)max0, CF(E1) = 0.9max0, 0.4 = 0.36可信度方法 由由r2得到：得到： CF2(H) = CF(H, E2)max 0, CF(E2) = 0.6max 0, 0.8 = 0.48由由r3得到：得到： CF3(H) = CF(H, E3)max 0, CF(E3) = -0.5max 0, 0.6 = -0.3 根据结论不精确性的合成算法，根据结论不精确性的合成算法，CF1(H)和和CF2(H)同同号，有：号，有：

14、1,21212()()()()()0.360.480.360.480.840.170.67CFHCF HCF HCF HCF H可信度方法 CF12(H)和和CF3(H)异号，有：异号，有：1,231,2,31,23()()()1min() ,()0.670.30.371min 0.67,0.30.70.53CFHCF HCFHCFHCF H综合可信度为综合可信度为CF(H)=0.53内容提要1.1.经典推理和非经典推理经典推理和非经典推理2.2.不确定性推理不确定性推理3.3.概率推理概率推理4.4.主观贝叶斯方法主观贝叶斯方法5.5.可信度方法可信度方法6.6.证据理论证据理论证据理论v证

15、据理论是由德普斯特证据理论是由德普斯特 (A. P. Dempster) 首先提出，首先提出，并由沙佛并由沙佛 (G. Shafer) 进一步发展起来的用于处理不确进一步发展起来的用于处理不确定性的一种理论，也称定性的一种理论，也称DS (DempsterShafer)理论。理论。 v它将概率论中的它将概率论中的单点赋值扩展为集合赋值单点赋值扩展为集合赋值，能够，能够区分区分“不确定不确定”与与“不知道不知道”的差异，的差异，并能处理并能处理由由“不知不知道道”引起的不确定性，引起的不确定性，比主观比主观Bayes方法更具灵活性。方法更具灵活性。v在在DS理论中，可以分别用理论中，可以分别用信

16、任函数信任函数、似然函数似然函数及及类概类概率函数率函数来描述知识的来描述知识的精确信任度精确信任度、不可驳斥信任度不可驳斥信任度及及估计估计信任度信任度。DS理论的形式描述vDS理论是用集合表示命题的。理论是用集合表示命题的。v设设是变量是变量x所有可能取值的集合，且所有可能取值的集合，且中的元素是中的元素是互互斥的斥的，即在任一时刻，即在任一时刻，x都能且只能取都能且只能取中的某一个元中的某一个元素值，则称素值，则称为为x的的样本空间样本空间。v在在DS理论中，理论中，的任何一个子集的任何一个子集A都对应于一个都对应于一个关于关于x的命题的命题，称该命题为，称该命题为“x的值在的值在A中中

17、”。v例如：例如：用用x表示打靶击中的环数，表示打靶击中的环数，=1,., 10，则，则A=5表示命题表示命题“x值是值是5”或或“击中环数为击中环数为5”；A =5, 6,7,8表示命题表示命题“击中环数为击中环数为5,6,7,8中的某一个中的某一个”。DS理论的形式描述v DS理论处理的是集合上的不确定性问题，为此需要先建立理论处理的是集合上的不确定性问题，为此需要先建立命题与集合之间的一一对应关系，以把命题与集合之间的一一对应关系，以把命题的不确定性问命题的不确定性问题转化为集合的不确定性问题。题转化为集合的不确定性问题。v 设设为样本空间，且为样本空间，且中的每个元素都相互独立，则由中

18、的每个元素都相互独立，则由的所有子集构成的的所有子集构成的幂集幂集记为记为2。v 当当中的元素个数为中的元素个数为N时，则其幂集时，则其幂集2的元素个数为的元素个数为2N，且其中每一个元素都对应一个关于且其中每一个元素都对应一个关于x取值情况的命题。取值情况的命题。v 例如：设例如：设=红红,黄黄,白白，的幂集的幂集2包括如下子集包括如下子集 A0=, A1=红红, A2=黄黄, A3=白白, A4=红，黄红，黄, A5=红，白红，白, A6=黄，黄，白白, A7=红，黄，白红，黄，白。其中，。其中，表示空集，表示空集，DS理论的形式描述设函数设函数M：20，1，且满足，且满足则称则称M是是2

19、上的上的概率分配函数概率分配函数，M(A)称为称为A的的基本概基本概率数率数。概率分配函数实质上是对概率分配函数实质上是对的各个子集进行信任分配，的各个子集进行信任分配， M(A)表示分给表示分给A的那部分。的那部分。概率分配函数不是概率。概率分配函数不是概率。M ()0 M ()1AA DS理论的形式描述信任函数和似然函数都是在概率分配函数的基础上定信任函数和似然函数都是在概率分配函数的基础上定义的，不同的概率分配函数将得到不同的推理模型。义的，不同的概率分配函数将得到不同的推理模型。一种具体的概率分配函数的定义：一种具体的概率分配函数的定义：设设=s1,sn，M为定义在为定义在2上的概率分

20、配函数，且上的概率分配函数，且M满足满足 11(1)M 0(2)M 1(3)M( )1M (4)| 1| 0,0iiniiniissssAAAM A 对任何当且或时DS理论的形式描述命题的命题的信任函数信任函数Bel : 2 0，1为为 其中，其中，2是是的幂集。的幂集。Bel又称为又称为下限函数下限函数，Bel(A)表示表示对对A的的总的信任度总的信任度。 根据定义还可以得到：根据定义还可以得到：( )M( )BABel ABA 对所有的()M ()0()M ()1BBelBelB DS理论的形式描述似然函数似然函数Pl：20，1为为其中，其中，A =A。 似然函数又称为似然函数又称为不可驳

21、斥函数不可驳斥函数或或上限函数上限函数。 由于由于Bel(A)表示对表示对A的信任度，即的信任度，即A为假的信任度，因为假的信任度，因此，此，Pl(A)表示对表示对A为非假的信任度为非假的信任度。 似然函数的另外一种计算办法似然函数的另外一种计算办法( )1Pl ABelAA 对所有的( )M( )ABPl AB DS理论的形式描述Pl(A)Bel(A)由于由于Bel(A)和和Pl(A)分别表示分别表示A为真的信任度为真的信任度和和A为为非假的信任度非假的信任度，因此，可分别称，因此，可分别称Bel(A)和和Pl(A)为为对对A信任程度的下限和上限信任程度的下限和上限，记为：，记为：A Bel

22、(A), Pl(A) 例如：例如：若若Bel(红红)=0.3，Pl(红红)=0.9即：即： 红红0.3, 0.9表示对表示对红红的精确信任度为的精确信任度为0.3，不，不可驳斥部分为可驳斥部分为0.9，肯定不是，肯定不是红红的为的为0.1。DS理论的形式描述对任何命题对任何命题A属于属于,其似然函数为其似然函数为因此，对任意命题因此，对任意命题A 和和B属于属于均有：均有：)()(M )()(M1 1 )(M)(M1 )(M1)(1)(1ABelABelsssABelAPlniAsiiAsiii)(M)(-)(ABelAPl)(M)(-)()(-)(BBelBPlABelAPl表示对命题不表示

23、对命题不知道的程度知道的程度DS理论的形式描述 A0, 1：说明对说明对A 一无所知。一无所知。 A0, 0：说明说明A为假。为假。 A1, 1：说明说明A为真。为真。 A0.6, 1：说明对说明对A部分信任，部分信任， Bel(A)=0.6 。 A0, 0.4：说明对说明对A部分信任，部分信任， Bel(A)=0.6。 A0.3, 0.9：说明对说明对A和和A都有部分信任。都有部分信任。p Bel(A)=0.3，说明对，说明对A 为真有为真有0.3的信任度；的信任度；p Bel(A)=1-0.9=0.1，说明对，说明对A为假有为假有0.1的信任度。的信任度。DS理论的形式描述当证据来源不同时

24、，可能会得到不同的概率分配函数当证据来源不同时，可能会得到不同的概率分配函数例如，对例如，对=红，黄红，黄，假设从不同知识源得到的两个，假设从不同知识源得到的两个概率分配函数分别为：概率分配函数分别为： M1( , 红红, 黄黄, 红红, 黄黄)=(0, 0.4, 0.5, 0.1) M2( , 红红, 黄黄, 红红, 黄黄)=(0, 0.6, 0.2, 0.2)可采用德普斯特提出的求正交和的方法组合这些函数可采用德普斯特提出的求正交和的方法组合这些函数设设M1和和M2是两个不同的概率分配函数，则两者的正交是两个不同的概率分配函数，则两者的正交和和 满足满足12MMMDS理论的形式描述其中：其

25、中：如果如果K0，则正交和也是一个概率分配函数；，则正交和也是一个概率分配函数；如果如果K=0，则不存在正交和，则不存在正交和M，称，称M1与与M2矛盾。矛盾。例子例子P133，例，例4.512121( )( )( )( )xyxyKMxMyMxMy 112()0( )( )( )xy AMM AKMxMy DS理论的形式描述设设为有限域，对任何命题为有限域，对任何命题A属于有限域属于有限域，命题，命题A的的类概率函数类概率函数为为 类概率函数类概率函数f(A)的性质的性质)()()()(ABelAPlAABelAf (2)对任何对任何 ,有有Bel(A)f(A)Pl(A) A1()1niif

26、S (1) (3)对任何对任何 ，有，有f(A)=1f(A) A知识不确定性的表示IF E THEN H=h1, h2, , hn CF=c1, c2, , cnE为前提条件，它既可以是简单条件，也可以是用合取为前提条件，它既可以是简单条件，也可以是用合取或析取词连接起来的复合条件；或析取词连接起来的复合条件；H是结论，它用是结论，它用样本空间中的子集样本空间中的子集表示，表示，h1, h2, , hn 是该子集中的元素；是该子集中的元素；CF是是可信度因子可信度因子，用集合形式表示。该集合中的元素，用集合形式表示。该集合中的元素c1, c2, , cn 用来指出用来指出h1, h2, , h

27、n 的可信度；的可信度；ci与与hi一一对应，且应满足如下条件：一一对应，且应满足如下条件：11,0,1,2,niiiccin证据不确定性的表示不确定性证据不确定性证据E的确定性用的确定性用CER(E)表示，表示， CER(E)的取的取值范围为：值范围为：0,1初始证据的不确定性初始证据的不确定性由用户给出由用户给出设设H是规则结论部分命题，是规则结论部分命题，E是外部输入的证据和已证是外部输入的证据和已证实的命题，命题实的命题，命题H所要求的证据与所要求的证据与E的的匹配程度匹配程度为：为：结论命题结论命题H的确定性为的确定性为: CER(H)=MD(H/E)f(H)否则否则中中 要求的证据

28、都出现在要求的证据都出现在如果如果01) /(EHEHMD Certainty组合证据不确定性的表示当组合证据是多个证据的合取时：当组合证据是多个证据的合取时：E=E1 AND E2 AND AND En 此时此时CER(E)=minCER(E1), CER(E2), ,CER(En)当组合证据是多个证据的析取时：当组合证据是多个证据的析取时：E=E1 OR E2 OR OR En 此时此时CER(E)=maxCER(E1), CER(E2), . CER(En) 不确定性的更新设有知识设有知识 IF E THEN H=h1, , hn CF=c1, c2, , cn 则求结论则求结论H的确定

29、性的确定性CER(H)的方法如下：的方法如下：(1)求求H的概率分配函数的概率分配函数 12311 , ,., ( ),( )( )1( )nniiMhhhCER EcCER EcMCRE Ec 不确定性的更新(1)求求H的概率分配函数的概率分配函数 p如果有两条或多条知识支持同一结论如果有两条或多条知识支持同一结论H，例：，例：IF E THEN H=h1, , hn CF=c11, , c1nIF E THEN H=h1, , hn CF=c21, , c2np则按正交和求则按正交和求CER(H)，即先求出：，即先求出：M1=M(h1,h2,hn)M2=M(h1,h2,hn) p然后再用公式然后再用公式 求求M1和和M2的正交和，最的正交和，最后求得后求得H的的M。12MMM不确定性的更新(2)求求Bel(H)、Pl(H)及及f(H) (3)求求H的确定性的确定性CER(H)1()( )niiBel HMh)(1)(HBelHPl()()()()Hf HBel HPl HBel H()CER HMD H Ef H