不确定性推理-2015

不确定性推理方法,华北电力大学计算机系,2020/5/5,华北电力大学,2,主要内容,什么是不确定性推理？为什么要采取不确定性推理？不确定性推理的理论依据是什么？不确定性推理有哪几种主要方法？CF方法的推理主观Bayes方法的推理,2020/5/5,华北电力大学,3,第五章不确定性推理方法,概述概率论基础确定性方法主观Bayes方法,2020/5/5,华北电力大学,4,第五章不确定性推理方法,概述概率论基础确定性方法主观Bayes方法,2020/5/5,华北电力大学,5,概述,不确定性推理的研究发展：概率论是解决不确定性问题的主要理论基础之一贝叶斯网络方法受到多方面关注DURA等人与1976年在PROSPECTOR基础上给出了同属概率推理的主观贝叶斯方法Shortliffe等人与1975年结合MYCIN系统建立了确定性理论DempsterShaferter同年也提出了证据理论Zadeh提出可能性理论，1983年提出了模糊逻辑,2020/5/5,华北电力大学,6,概述,不确定性推理实际上是一种从不确定的初始证据出发，通过运用不确定性知识，最终推出即保持一定不确定性，又合理或基本合理的结论的推理过程,2020/5/5,华北电力大学,7,概述不确定性,不确定性的主要性质随机性指由于不确定性推理所处理的事件的真实性是不完全肯定的，含有一定的可能性，只能给出一个估计值模糊性主要指命题中出现的表达形式是不明确的不完全性产生于信息的不充分、不全面由于种种的不确定因素，及其在推理过程中的累计，导致了一些结论的不一致性,2020/5/5,华北电力大学,8,概述不确定性,在不确定性推理中，规则前件、后件以及规则本身在某种程度上都是不确定的证据的不确定性歧义性：证据中含有多种意义明显不同的解释，如果离开具体的上下文和环境，往往难以判断其明确含义不完全性：对于某事物来说，对于它的知识还不全面、不完整、不充分不精确性：证据的观测值与真实值存在一定的差别模糊性：命题中的词语从概念上讲不明确，无明确的内涵和外延可信性：专家主观上对证据可靠性不能完全确定随机性：命题的事实的真假性不能完全肯定，而只能对其真伪给出一个估计不一致性：在推理过程中发生了前后不相容的结论，或者随着时间的推移或范围的扩大，原来成立的命题变得不成立了,2020/5/5,华北电力大学,9,概述不确定性,规则一般是经验知识，存在着不确定性因素证据的组合的不确定性：一些规则有若干证据作为前提条件，或几个证据都可以激活某一规则。此时，组合起来的证据到底有多大程度符合前提条件，其中包含某些不确定的主观度量规则自身的不确定性：有时领域专家对规则持有某种信任程度，即专家有时也没有十足把握某种前提下得到结果必为真的结论，只能给出一个发生可能性及可能性的度量规则结论的不确定性：包含各种不确定性的前提条件，运用不确定的规则，引出的结论或动作不可避免的含有不确定性因素从系统高层看，规则的不确定性还源于各个规则之间的冲突，来源于单个规则、规则间的冲突消解和规则后件的不相容,2020/5/5,华北电力大学,10,概述不确定性,推理的不确定性由于知识不确定性的动态累计和传播过程所造成的寻找尽可能符合客观世界的计算，最终得到结论的不确定性度量,2020/5/5,华北电力大学,11,概述-不确定性推理的基本问题,在不确定性推理中，除了解决在确定性推理过程中所提到的推理方向、推理方法、控制策略等基本问题外，一般还需要解决不确定性的表示与度量问题不确定性的匹配问题不确定性的传递算法问题不确定性的合成问题将不确定性问题用确定的数学公式表示出来，是不确定性推理研究的基础,2020/5/5,华北电力大学,12,概述-不确定性推理的基本问题,3方面问题表示问题：如何描述不确定性计算问题：不确定性的传播和更新语义问题：如何解释表示和计算的含义,2020/5/5,华北电力大学,13,概述-不确定性推理的基本问题,表示问题：指用什么方法描述不确定性，是解决不确定推理的关键一步通常的方法有：数值表示方法，如CH(A)非数值表示的语义表示方法，如“很可能”,2020/5/5,华北电力大学,14,概述-不确定性推理的基本问题,计算问题：不确定性的传播和更新。也是获取新信息的过程如：已知证据A的不确定性度量P(A),规则AB,规则的可信度度量P(B，A)，如何计算结论的可信度度量P(B)从一个规则得到A的可信度度量P1(A)，又从另一个规则得到A的另一个可信度度量P2(A)，如何从两个规则合成最终的可信度度量P(A)如何由P(A1)、P(A2)来计算P(A1A2),P(A1A2),2020/5/5,华北电力大学,15,不确定性推理例子,初始命题的不确定性度量的获得也是非常重要的，一般由领域内的专家从经验得出推理过程可以用推理树直观的表示出来。例如，对于如下的推理过程：R1：A1A2B1R2：A2A3B2R3：B1BR4：B2B用推理树可以表示如下：,2020/5/5,华北电力大学,16,推理树结果图,最下层的是初始证据经过一些“与”和“或”的组合，形成推理中的临时证据，由这些临时证据推导出最终的结论Ri所表示的是推理弧上所使用的规则，fi表示证据或规则的不确定度量值,2020/5/5,华北电力大学,17,概述-不确定性推理的基本问题,语义问题：将各个公式解释清楚。如何解释表示和计算的含义，目前多用概率方法。如：P(B，A)可理解为当前提A为真时结论B为真的一种影响程度P(A)可理解为A为真的程度对于规则，特别关心P(B，A)的特殊值的意义：1）A(T)B(T),P(B，A)=?2）A(T)B(F),P(B，A)=?3）B独立于A，P(B，A)=?,2020/5/5,华北电力大学,18,概述-不确定性推理的基本问题,对证据的可信度度量P(A)关心的也是一些特殊状态下的意义：1）A为TRUE，P(A)？2）A为FALSE,P(A)？T：True，F：False,2020/5/5,华北电力大学,19,概述-分类（1）,不确定性推理方法可分为形式化方法和非形式化方法形式化方法有逻辑法：逻辑法是非数值方法，采用多值逻辑和非单调逻辑来处理不确定性。传统的有基于概率理论的贝叶斯网络等新计算法：新计算法认为概率法不足以描述不确定性，从而出现了证据理论（也叫DempsterShafter，D-S方法），确定性方法（CF法）以及模糊逻辑方法新概率法：试图在传统的概率论框架内，采用新的计算方法以适应不确定性描述非形式化方法是指启发性方法，对不确定性没有给出明确的概念,2020/5/5,华北电力大学,20,概述-分类（2）,另外一种观点，把不确定推理方法分为工程方法、控制方法和并行确定性法工程法是将问题简化为忽略哪些不确定性因素控制法是利用控制策略来消除不确定性的影响，如启发式的搜索方法并行确定性法是把不确定性的推理分解为两个相对独立的过程：一个过程不计不确定性采用标准逻辑进行推理；另一过程是对第一个过程的结论加以不确定性的度量。前一过程决定信任什么，后一过程决定对它的信任程度,2020/5/5,华北电力大学,21,第五章不确定性推理方法,概述概率论基础确定性方法主观Bayes方法,2020/5/5,华北电力大学,22,第五章不确定性推理方法,概述概率论基础确定性方法主观Bayes方法,2020/5/5,华北电力大学,23,概率论基础,概率论研究随机现象中数量规律的科学随机现象在相同的条件下重复进行某种实验时，所得实验结果不一定完全相同且不可预知的现象。掷硬币的实验人工智能所讨论的不确定性现象，虽然不完全是随机的过程，但是实践证明，采用概率论的思想方法考虑能够得到较好的结果概率论的基本概念和贝叶斯定,2020/5/5,华北电力大学,24,概率论基础（基本定义）,随机实验：随机实验是一个可观察结果的人工或自然的过程，其产生的结果可能不止一个，且不能事先确定会产生什么结果样本空间：样本空间是一个随机实验的全部可能出现的结果的集合，通常记作，中的点（即一个可能出现的实验结果）称为样本点，通常记作随机事件：随机事件是一个随机实验的一些可能结果的集合，是样本空间的一个子集。常用大写字母A,B,C,表示,2020/5/5,华北电力大学,25,概率论基础（事件间的关系与运算）,两个事件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的余事件，或B为A的余事件任意两个事件不一定会是上述几种关系中的一种,2020/5/5,华北电力大学,26,概率论基础（事件间的关系与运算）,设A，B，A1，A2，An为一些事件，它们有下述的运算：交：记C=“A与B同时发生”，称为事件A与B的交，C=|A且B，记作C=AB或C=AB并：记C=“A与B中至少有一个发生”，称为事件A与B的并，C=|A或B，记作C=AB差：记C=“A发生而B不发生”，称为事件A与B的差，C=|A但B，记作或C=AB或C=A-B求余：A=A,2020/5/5,华北电力大学,27,概率论基础（运算的性质）,事件的运算有以下几种性质：交换率：结合律：分配律：摩根率：事件计算的优先顺序为：求余，交，差和并,2020/5/5,华北电力大学,28,概率论基础（概率定义）,定义：设为一个随机实验的样本空间，对上的任意事件A，规定一个实数与之对应，记为P(A)，满足以下三条基本性质，称为事件A发生的概率：若二事件AB互斥，即AB=，则以上三条基本规定是符合常识的,2020/5/5,华北电力大学,29,概率论基础（概率性质）,定义：设An,n=1,2,为一组有限或可列无穷多个事件，两两不相交，且，则称事件族An,n=1,2,为样本空间的一个完备事件族又若对任意事件B有BAn=An或,n=1,2,，则称An,n=1,2,为基本事件族,2020/5/5,华北电力大学,30,概率论基础（概率性质）,完备事件族与基本事件族有如下的性质：定理：若An,n=1,2,为一完备事件族，则，且对于一事件B有又若An,n=1,2,为一基本事件族，则,2020/5/5,华北电力大学,31,概率论基础（统计概率性质）,统计概率也称古典概率，是通过对某一事件出现的频率定义的。统计概率具有以下性质：对任意事件A，有必然事件的概率P()=1，不可能事件的概率P()=0对任意事件A，有设事件A1，A2，An（kn）是两两互不相容的事件，则设A，B是两事件，则,2020/5/5,华北电力大学,32,概率论基础（条件概率）,定义：设A，B为事件且P(A)0，称为事件A已发生的条件下，事件B的条件概率，P(A)在概率推理中称为边缘概率简称P(B|A)为给定A时B发生的概率。P(AB)称为A与B的联合概率。有联合概率公式：,2020/5/5,华北电力大学,33,概率论基础（条件概率性质）,，若，则乘法公式：全概率公式：设A1，A2，An互不相交，且，则对于任意事件A有,2020/5/5,华北电力大学,34,概率论基础（贝叶斯定理）,设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称为后验概率也是条件概率,2020/5/5,华北电力大学,35,第五章不确定性推理方法,概述概率论基础确定性方法主观Bayes方法,2020/5/5,华北电力大学,36,第五章不确定性推理方法,概述概率论基础确定性方法主观Bayes方法,2020/5/5,华北电力大学,37,确定性方法（可信度方法）,MYCIN系统研制过程中产生的不确定推理方法,第一个采用了不确定推理逻辑，70年代很有名这个系统提出该方法时遵循了以下原则：不采用严格的统计理论。使用的是一种接近统计理论的近似方法用专家的经验估计代替统计数据尽量减少需要专家提供的经验数据，尽量使少量数据包含多种信息新方法应适用于证据为增量式地增加的情况专家数据的轻微扰动不影响最终的推理结论,2020/5/5,华北电力大学,38,MYCIN系统,帮助医生对住院的血液感染患者进行诊断和用抗菌素类药物进行治疗的专家系统美国斯坦福大学研制，LISP语言写成，知识用产生式方法表示功能分两部分以患者的病史、症和化验结果等为原始数据，运用医疗专家的知识进行向推理，找出导致感染的细菌。若是多种细菌，则用0到1的数字给出每种细菌的可能性在上述基础上,给出针对这些可能的细菌的药方,2020/5/5,华北电力大学,39,MYCIN系统,它通过以下的测试，显示出较高的水平在互相隔离的情况下，用MYCIN系统和九位斯坦福大学医学院医生，分别对十名不清楚感染源的患者进行诊断和处方，由八位专家进行评判，结果是MYCIN和三位医生所开出的处方对症有效在是否对其它可能的病原体也有效而且用药又不过量方面，MYCIN则胜过了九位医生知识表达方式和控制结构基本上与应用领域不相关，导致了后来建造专家系统工具EMYCIN的出现,2020/5/5,华北电力大学,40,理论基础以定量法为工具，比较法为原则的相对确认理论采用此方法的MYCIN系统的诊断结果不是只给出一个最可信结论及其可信度，而是给出可信度较高的前几位，供人们比较选用规则规则的不确定性度量证据（前提）的不确定性度量推理计算,确定性方法,2020/5/5,华北电力大学,41,理论基础以定量法为工具，比较法为原则的相对确认理论采用此方法的MYCIN系统的诊断结果不是只给出一个最可信结论及其可信度，而是给出可信度较高的前几位，供人们比较选用规则规则的不确定性度量证据（前提）的不确定性度量。推理计算,确定性方法,2020/5/5,华北电力大学,42,规则(规则的不确定性度量）,在逻辑推理过程中，常常以AB表示规则。其中A表示前提，可以是一些命题的析取或和取；B表示结论或推论，是在前提A下的直接逻辑结果在精确逻辑推理中，通常只有真假的描述：若A真，则B也必为真在不确定推理过程中，通常要考虑的是A为真时对B为真的支持程度，甚至还考虑A为假（不发生）时对B为真的支持程度在MYCIN系统中，考虑的是A发生的前提下对B的不支持程度，为此，引入规则的不确定性度量,2020/5/5,华北电力大学,43,规则(规则的不确定性度量）,在MYCIN系统中，最初确定性因子定义为信任与不信任二者之差，有规则AB，其可信度CF(B,A)定义为CF(B,A)=MB(B,A)-MD(B,A)CF是由证据A得到假设B的确定性因子MB是由证据A得到假设B的信任增加度量MD是由证据A得到假设B的不信任增加度量确定性因子把信任与不信任组合到了一起对MB和MD又有相关的定义根据CF定义，重写得到确定性因子的概率表示形式,2020/5/5,华北电力大学,44,规则(规则的不确定性度量）,规则AB，可信度表示为CF(B,A),2020/5/5,华北电力大学,45,规则(规则的不确定性度量）,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结论-1CF(B,A)1,2020/5/5,华北电力大学,46,规则(规则的不确定性度量）,CF(B,A)的特殊值：CF(B,A)=1，前提真，结论必真CF(B,A)=-1，前提真，结论必假CF(B,A)=0，前提真假与结论无关实际应用中CF(B,A)的值由专家确定，并不是由P(B|A),P(B)计算得到的,2020/5/5,华北电力大学,47,理论基础以定量法为工具，比较法为原则的相对确认理论采用此方法的MYCIN系统的诊断结果不是只给出一个最可信结论及其可信度，而是给出可信度较高的前几位，供人们比较选用规则规则的不确定性度量证据（前提）的不确定性度量。推理计算,确定性方法,2020/5/5,华北电力大学,48,规则(证据的不确定性度量）,在精确的逻辑推理过程中，前提要么为真，要么为假，不允许不真不假的情况出现但是在很多不确定性推理问题中，前提或证据本身是不确定的，介于完全的真和完全的假之间。为了描述这种不确定性的程度，引入了证据的可信度证据A的可信度用CF(A)来表示,2020/5/5,华北电力大学,49,规则(证据的不确定性度量）,证据A的可信度表示为CF(A)，-1CF(A)1特殊值：CF(A)=1，前提肯定真CF(A)=-1，前提肯定假CF(A)=0，对前提一无所知CF(A)0，表示A以CF(A)程度为真CF(A)0，表示A以CF(A)程度为假实际使用时初始证据的CF值由专家根据经验提供其它证据的CF通过规则进行推理计算得到,2020/5/5,华北电力大学,50,理论基础以定量法为工具，比较法为原则的相对确认理论采用此方法的MYCIN系统的诊断结果不是只给出一个最可信结论及其可信度，而是给出可信度较高的前几位，供人们比较选用规则规则的不确定性度量证据（前提）的不确定性度量推理计算,确定性方法,2020/5/5,华北电力大学,51,规则(推理计算1）,在推理过程中，可能计算：原始证据的与、或、非多条规则的使用对计算结果的综合影响关键问题:在已知规则和原始证据的可信度度量的情况下，如何计算新的组合证据或规则的不确定性在不确定性的传播与更新中，必须解决：证据的与、或、非的不确定性计算问题多条规则使用后的组合不确定性计算问题,2020/5/5,华北电力大学,52,规则(推理计算1）,“与”的计算：A1A2BCF(A1A2)=minCF(A1),CF(A2)“或”的计算：A1A2BCF(A1A2)=maxCF(A1),CF(A2)“非”的计算：CF(A)=-CF(A)由A，AB，求B：CF(B)=max0,CF(A)CF(B,A)(CF(A)0时可以不算即为“0”),2020/5/5,华北电力大学,53,规则(推理计算2）,合成，由两条规则求出再合并：由CF1(B)、CF2(B)，求CF(B),2020/5/5,华北电力大学,54,规则(推理计算2）,注意：以上公式不满足组合交换性，即，如果有n个证据同时作用于一个假设，设A1、A2、An为证据通过规则R1、R2、Rn作用于B，那么使用上式进行逐一计算时，计算结果与各条规则采用的先后顺序有关同时，MYCIN规定证据的可信度CF(A)0.2时，就认为该证据引入的规则不可使用。即CF(B)=max(0.2,CF(A)CF(B,A)，而不是CF(B)=max(0,CF(A)CF(B,A)。,2020/5/5,华北电力大学,55,规则(推理计算2-关于组合交换性的改进）,EMYCIN系统（MYCIN发展而成）对CF1(B)和CF2(B)符号不同时，进行修正：,202