人工智能-5不确定与非单调推理.ppt

人工智能Artificial Intelligence,主讲：鲍军鹏西安交通大学电信学院计算机系E_mail：,第五章不确定与非单调推理,5.1 基本概念5.2 概率方法5.3 主观Bayes方法5.4 可信度方法5.5 证据理论5.6 模糊理论5.7 基于框架表示的不确定性推理5.8 基于语义网络表示的不确定性推理5.9 非单调推理,5.1 基本概念,5.1.1 什么是不确定性推理不确定性推理是建立在非经典逻辑基础上的一种推理，它是对不确定性知识的运用与处理。严格地说，所谓不确定性推理就是从不确定性的初始证据出发，通过运用不确定性的知识，最终推出具有一定程度的不确定性但却是合理或者近乎合理的结论的思维过程。,5.1.2 不确定性推理中的基本问题(1),1.不确定性的表示与度量不确定性推理中的“不确定性”一般分为两类：一是知识的不确定性，一是证据的不确定性。知识不确定性的表示：目前在专家系统中知识的不确定性一般是由领域专家给出的，通常是一个数值，它表示相应知识的不确定性程度，称为知识的静态强度。证据不确定性的表示：一般来说，证据不确定性的表示方法与知识不确定性的表示方法保持一致，以便于推理过程中对不确定性进行统一的处理。通常也用一个数值表示，代表相应证据的不确定性程度，称之为动态强度。不确定性的度量：可有多种度量方法和范围，例如0,1或者-1,1。在确定一种度量方法及其范围时，应注意以下几点：度量要能充分表达相应知识及证据不确定性的程度。度量范围的指定应便于领域专家及用户对不确定性的估计。度量要便于对不确定性的传递进行计算，而且对结论算出的不确定性度量不能超出度量规定的范围。度量的确定应当是直观的，同时应有相应的理论依据。,5.1.2 不确定性推理中的基本问题(2),2.不确定性匹配算法及阈值的选择设计一个不确定性匹配算法；指定一个匹配阈值。3.组合证据不确定性的算法在匹配时，一个简单条件对应于一个单一的证据，一个复合条件对应于一组证据，称这一组证据为组合证据。常用的组合证据不确定性计算方法有：最大最小法：T(E1 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为真的程度，如可信度、概率等。,5.1.2 不确定性推理中的基本问题(3),4.不确定性的传递算法在每一步推理中，如何把证据及知识的不确定性传递给结论。在多步推理中，如何把初始证据的不确定性传递给最终结论。5.结论不确定性的合成用不同知识进行推理得到了相同结论，但不确定性的程度却不同。此时，需要用合适的算法对它们进行合成。,5.1.3 不确定性推理方法的分类,关于不确定性推理方法的研究沿着两条不同的路线发展。一条路线是模型法：在推理一级上扩展确定性推理。其特点是把不确定的证据和不确定的知识分别与某种度量标准对应起来，并且给出更新结论不确定的算法。这类方法与控制策略一般无关，即无论用何种控制策略，推理的结果都是唯一的。一条线路是控制法：在控制策略一级处理不确定性。其特点是通过识别领域中引起不确定性的某些特征及相应的控制策略来限制或者减少不确定性对系统产生的影响。这类方法没有处理不确定性的统一模型，其效果极大地依赖于控制策略。例如：相关性制导回溯、启发式搜索等等。模型方法又分为数值方法和非数值方法两类。对于数值方法按其所依据的理论又可分为基于概率的方法和基于模糊理论的模糊推理。,5.2 概率方法,5.2.1 经典概率方法设有如下产生式规则：IFE THEN H其中，E为前提条件，H为结论。条件概率P(H|E)可以作为在证据E出现时结论H的确定性程度。对于复合条件E=E1 AND E2 AND AND En当已知条件概率P(H|E1,E2,En)时，就可把它作为在证据E1,E2,En出现时结论H的确定性程度。,5.2.2 逆概率方法,经典概率方法要求给出条件概率P(H|E)，在实际中比较困难。例如E代表咳嗽，H代表支气管炎，则P(H|E)表示在咳嗽的人群中患支气管炎的概率。这个比较困难。而逆概率P(H|E)表示在得支气管炎的人群中咳嗽的概率。这个相对容易获得。我们根据Bayes定理可以从P(H|E)推出P(E|H)。,若A1,A2,An是彼此独立的事件，其中，P(Ai)是事件Ai的先验概率；P(B|Ai)是在事件Ai发生条件下事件B的条件概率。如果用产生式规则IFETHENHi中的前提条件E代替Bayes公式中的B，用Hi代替公式中的Ai，就可得到,Bayes公式,对于多个证据,逆概率方法举例,例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,逆概率法的特点,逆概率法在实际中有很多应用。比如：把Hi(i=1,2,n)当作可能发生的疾病；把Ej(j=1,2,n)当作相应的症状；P(Hi)是从大量实践中得到的疾病Hi的先验概率；P(Ej|Hi)是疾病Hi发生时观察到症状Ej的条件概率。则当对某病人观察到有症状E1,E2,Em时，应用上述Bayes公式就可计算出P(Hi|E1E2Em)，从而得知病人患疾病Hi的可能性。优点：逆概率法有较强的理论背景和良好的数学特性，当证据及结论都彼此独立时计算的复杂度比较低。缺点：逆概率法要求给出结论Hi的先验概率P(Hi)及证据Ej的条件概率P(Ej|Hi)。尽管有些时候P(Ej|Hi)比P(Hi|Ej)相对容易得到，但仍然相当困难。另外Bayes公式的应用条件很严格。,5.3 主观Bayes方法,1976年R.O.Duda等人在Bayes公式的基础上适当改进提出了主观Bayes方法，建立了相应的不确定性推理模型，并在地矿勘探专家系统PROSPECTOR中得到了成功应用。5.3.1 知识不确定性的表示在主观Bayes方法中，知识是用产生式规则表示的，具体形式为：IFE THEN(LS,LN)H(P(H)其中，P(H)是结论H的先验概率，由专家根据经验给出。LS称为充分性度量，用于指出E对H的支持程度，取值范围为0,)，其定义为：LS=P(E|H)/P(E|H)。LN称为必要性度量，用于指出E对H的支持程度，取值范围为0,)，其定义为：LN=P(E|H)/P(E|H)=(1-P(E|H)/(1-P(E|H)。LS和LN的值由领域专家给出，相当于知识的静态强度。,5.3.2 证据不确定性的表示,在主观Bayes方法中，证据的不确定性也用概率表示。对于证据E，由用户根据观察S给出P(E|S)，即动态强度。由于主观给定P(E|S)有所困难，所以实际中可以用可信度C(E|S)代替P(E|S)。例如在PROSPECTOR中C(E|S)和P(E|S)遵从如下关系：,5.3.3 组合证据不确定性的算法,可以采用最大最小法。当组合证据是多个单一证据的合取时，即E=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)对于“”运算则：P(E|S)=1-P(E|S),5.3.4 不确定性的传递算法,主观Bayes方法推理的任务就是根据证据E的概率P(E)及LS、LN的值，把H的先验概率P(H)更新为后验概率P(H|E)或P(H|E)。即确定后验概率的方法随着证据肯定存在，肯定不存在，或者不确定而有所不同。,证据肯定存在时,引入几率函数(x),它与概率的关系为：(x)=P(x)/(1-P(x),P(x)=(x)/(1+(x)在证据肯定存在时，P(E)=P(E|S)=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)由LS和几率函数的定义得：(H|E)=LS(H)即P(H|E)=LSP(H)/(LS-1)P(H)+1,充分性度量LS的意义,当LS1时，(H|E)=LS(H)(H)，表明由于证据E的存在，增强了H为真的程度。当LS1时，(H|E)=LS(H)(H)，表明E与H无关。当LS1时，(H|E)=LS(H)(H)，表明由于证据E的存在，减小了H为真的程度。当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)+1,必要性度量LN的意义,当LN1时，(H|E)=LN(H)(H)，表明由于证据E不存在，增强了H为真的程度。当LN1时，(H|E)=LN(H)(H)，表明E与H无关。当LN1,LN1LS1,LN1,证据不确定时,当0P(E|S)1时，应该用杜达等人1976年证明的下述公式计算后验概率P(H|S)：P(H|S)=P(H|E)P(E|S)+P(H|E)P(E|S)当P(E|S)=1时，证据肯定存在。当P(E|S)=0时，证据肯定不存在。当P(E|S)=P(E)时，证据E与观察S无关。由全概率公式得：P(H|S)=P(H|E)P(E)+P(H|E)P(E)P(H)当P(E|S)为其它值时，通过分段线性插值计算P(H|S)，即,5.3.5 结论不确定性的合成算法,若有n条知识都支持相同的结论，而且每条知识的前提条件所对应的证据Ei(i=1,2,n)都有相应的观察Si与之对应，此时只要先对每条知识分别求出(H|Si)，然后运用下述公式求出(H|S1S2Sn):,主观Bayes方法推理示例(1),例5.4 设有如下知识：R1:IF E1THEN(2,0.001)H1R2:IF E2THEN(100,0.001)H1R3:IF H1THEN(200,0.01)H2已知：(H1)0.1，(H2)0.01 C(E1|S1)=2,C(E2|S2)=1求：(H2|S1S2)=?1.计算(H1|S1)P(H1)=(H1)/(1+(H1)=0.09P(H1|E1)=(H1|E1)/(1+(H1|E1)=LS1(H1)/(1+LS1(H1)=0.17C(E1|S1)=20P(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,主观Bayes方法推理示例(2),2.计算(H1|S2)P(H1|E2)=(H1|E2)/(1+(H1|E2)=LS2(H1)/(1+LS2(H1)=0.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.343.计算(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(H1|S1S2)-P(H1)/1-P(H1)P(H2|H1)-P(H2)=0.175(H2|S1S2)=P(H2|S1S2)/(1-P(H2|S1S2)=0.212,主观Bayes方法的特点,优点：主观Bayes方法中的计算公式大多是在概率论的基础上推导出来，具有较坚实的理论基础。知识的静态强度LS及LN是由领域专家给出，避免了大量的数据统计工作。LS和LN比较全面的反映了证据与结论间的因果关系，使推出的结论有较准确的确定性。主观Bayes方法不仅给出了证据肯定存在、肯定不存在时更新后验概率的方法，还给出了证据不确定时的方法，实现了不确定性的逐级传递。缺点：它要求领域专家在给出知识时，同时给出H的先验概率P(H)，这比较困难。Bayes定理要求事件间独立，使其应用受限制。,5.4 可信度方法,可信度方法是E.H.Shortliffe等人在确定性理论(Theory of Confirmation)的基础上，结合概率论等提出的一种不确定性推理方法，首先在专家系统MYCIN中得到了成功应用。5.4.1 可信度的概念根据经验对一个事物和现象为真的相信程度称为可信度。可信度带有交大的主观性和经验性，其准确性难以把握。但人工智能面向的多是结构不良的复杂问题，难以给出精确的数学模型，先验概率及条件概率的确定又比较困难。所以可信度方法是一种比较实用的方法。,5.4.2 C-F模型,C-F模型是基于可信度表示的不确定性推理的基本方法，其它可信度方法都是在此基础上发展起来的。1.知识不确定性的表示在该模型中，知识是用产生式规则表示的，其一般形式为：IFETHENH(CF(H,E)其中，CF(H,E)是该条知识的可信度，称为可信度因子或规则强度，即静态强度。一般CF(H,E)-1,1。,可信度因子的定义,在C-F模型中，把CF(H,E)定义为：CF(H,E)=MB(H,E)-MD(H,E)其中，MB(Measure Belief)称为信任增长度。它表示由于证据E的出现，使结论为真的信任增长程度。MD(Measure Disbelief)称为不信任增长度。它表示由于证据E的出现，使结论为真的不信任增长程度。MB和MD的定义为当MB(H,E)0时，P(H|E)P(H);当MD(H,E)0时，P(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)的互斥性可得:从上式可看出：当CF(H,E)0时，P(H|E)P(H);当CF(H,E)0时，P(H|E)P(H);当CF(H,E)=0时，P(H|E)=P(H)。,2.证据不确定性的表示证据的不确定性也用可信度因子表示。如CF(E)=0.6注意：CF(H,E)表示知识的强度，即静态强度；CF(E)表示证据的强度，即动态强度。3.组合证据不确定性的算法可采用最大最小法。若E=E1 AND E2 ANDAND En,则CF(E)=minCF(E1),CF(E2),CF(En)若E=E1 OR E2 OROR En,则CF(E)=maxCF(E1),CF(E2),CF(En),4.不确定性的传递算法结论H的可信度由下式计算：CF(H)=CF(H,E)max0,CF(E)5.结论不确定性的合成算法若由多条不同知识推出了相同的结论，但可信度不同，则用合成算法求出综合可信度。设有如下知识：IFE1THENH(CF(H,E1)IFE2THENH(CF(H,E2)则结论H的综合可信度分如下两步算出：首先分别对每一条知识求出CF(H):然后用下述公式求出E1与E2对H的综合可信度CF12(H):,C-F模型推理示例(1),例5.5 设有如下一组知识：R1:IFE1THENH(0.8)R2:IFE2THENH(0.6)R3:IFE3THENH(-0.5)R4:IFE4 AND(E5 OR E6)THENE1(0.7)R5:IFE7 AND E8 THENE3(0.9)已知：CF(E2)=0.8,CF(E4)=0.5,CF(E5)=0.6CF(E6)=0.7,CF(E7)=0.6,CF(E8)=0.9求：CF(H)=？解：由R4得到：CF(E1)=0.7max0,CFE4 AND(E5 OR E6)=0.7max0,minCF(E4),CF(E5 OR E6)=0.35由R5得到：CF(E3)=0.9max0,CFE7 AND E8=0.54,C-F模型推理示例(2),由R1得到：CF1(H)=0.8max0,CF(E1)=0.28由R2得到：CF2(H)=0.6max0,CF(E2)=0.48由R3得到：CF3(H)=-0.5max0,CF(E3)=-0.27根据结论不确定性的合成算法：CF12(H)=CF1(H)+CF2(H)-CF1(H)CF2(H)=0.63CF123(H)=CF12(H)+CF3(H)/1-min|CF12(H)|,|CF3(H)|=0.49即最终的综合可信度为CF(H)=0.49。,5.4.3 带有阈值限度的不确定性推理,1.知识不确定性的表示知识用下述形式表示：IFETHENH(CF(H,E),)其中：CF(H,E)为知识的可信度因子，取值范围为(0,1。是阈值，它对相应知识的可用性规定了一个限度，只有当前提条件E的可信度CF(E)达到或超过这个限度，即CF(E)时，相应的知识才有可能被应用。的取值范围为(0,1。,2.证据不确定性的表示与C-F模型相同3.组合证据不确定性的算法与C-F模型相同4.不确定性的传递算法当CF(E)时，CF(H)=CF(H,E)CF(E)5.结论不确定性的合成算法设有多条规则有相同的结论，即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=CF(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.组合证据不确定性的算法若证据E=E1(1)AND E2(2)ANDAND En(n)则其可信度CF(E)为：,3.不确定性的传递算法当一条知识的CF(E)满足如下条件时，CF(E)该知识就可被应用。结论H的可信度为：CF(H)=CF(H,E)CF(E)加权因子的引入不仅可以解决证据的重要性、独立性问题，还可以解决证据不完全的推理问题，并为冲突消解提供了一种解决途径。,加权不确定性推理举例(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 E670.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)=?解：由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.46,5.4.5 前提条件中带有可信度因子的不确定性推理,前述的几种不确定性推理方法，没有在知识中指出前提条件或者子条件的可信度值，它们都是在前提条件E为真的前提下为CF(H,E)取值。在实际中，这样有时不能准确反映领域专家的知识。1.知识不确定性的表示IFE1(cf1)AND E2(cf2)ANDAND En(cfn)THEN H(CF(H,E),)或者IFE1(cf1,1)AND E2(cf2,2)ANDAND En(cfn,n)THEN H(CF(H,E),)其中，cfi是对子条件Ei(i=1,2,n)指出的可信度。cfi在0,1上取值，其值由专家给出。2.证据不确定性的表示证据Ei的可信度记为cfi,其取值范围在0,1上。,3.不确定性匹配算法不带加权因子的不确定性匹配算法：max0,cf1-cf1+max0,cf2-cf2+max0,cfn-cfn带加权因子的不确定性匹配算法：(1max0,cf1-cf1)+(2max0,cf2-cf2)+(nmax0,cfn-cfn)这里“”运算可以改为“”运算。显然：若所有cficfi则前提条件必然匹配；若cficfi或部分小于cfi则能否匹配取决于值。,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),基于可信度的不确定性推理方法的特点,优点：简单、直观。缺点：可信度因子依赖于专家主观指定，没有统一、客观的尺度，容易产生片面性。可信度数字上的语义不标准。随着推理延伸，可信度越来越不可靠，误差越来越大。当推理深度达到一定深度时，有可能出现推出的结论不再可信的情况。,5.5 证据理论,证据理论是由A.P.Dempster首先提出，并由G.Shafer进一步发展起来的一种处理不确定性的理论，因此又称为D-S理论。1981年把该理论引入专家系统，同年J.Garvey等人用它实现了不确定性推理。由于该理论满足比概率论弱的公理，能够区分“不确定”与“不知道”的差异，并能处理由“不知道”引起的不确定性，具有较大的灵活性。,完谢谢,