人工智能chapter8uncertaintyppt课件

第八章不确定知识与推理,概述非精确性推理不确定性人工智能的数学基础贝叶斯网络,8.1概述,知识的不确定性,随机性模糊性自然语言中的不确定性常识知识的不确定性知识的其他不确定性,随机性以牛顿理论为代表的确定性科学，创造了给世界以精确描绘的方法，将整个宇宙看作是钟表式的动力学系统，处于确定、和谐、有序的运动之中。客观世界上随机的，映射到人脑的客观世界，即主观世界也应该是随机的。因此，人类在认知过程中表现出的智能和知识，不可避免地伴随有随机性。随机性无处不在，随机性使得世界更为复杂，也更为丰富多彩。,8.1概述,模糊性直到20世纪，人们才认识到，模糊性并不是坏事。它能够用较少的代价，传递足够的信息，并能对复杂事物做出高效率的判断和处理。模糊性的客观性哲学家罗素早在1923年一篇题为Vagueness的论文中明确指出：“认为模糊知识必定是靠不住的，这种看法是大错特错的”。随着科学技术的发展，科学家们已经认识到：硬要把模糊事物人为地精确化，不仅会以方法的复杂性为代价，而且会降低结果的意义性。,8.1概述,自然语言中的不确定性语言带有不确定性是很自然的，是人类思维的本质特征之一。计算机自然语言理解、机器翻译等研究，从20世纪40年代兴起至今已经有60多年的历史，人们寄希望于表示概念的语言值的不确定性研究取得突破,8.1概述,常识知识的不确定性在人工智能界，常识知识的表示、处理和验证是非常困难的。常识知识的相对性目前，人工智能界有这样的共识：有无常识是人和机器的根本区别之一。,8.1概述,知识的其他不确定性知识的不完备性知识的不协调性知识的非恒常性,8.1概述,不确定性知识的表示、处理和模拟，寻找并且形式化地表示不确定性知识中的规律性，让机器模拟人类知识客观世界和人类自身的认知过程，使机器具有不确定性智能，成为人工智能学家的重要任务。,8.1概述,8.2非精确性推理,非精确性推理方法研究产生的原因大致如下：很多原因导致同一结果推理所需的信息不完备背景知识不足信息描述模糊信息中含有噪声划分是模糊的推理能力不足解题方案不唯一,ES是通过大量专家知识来取得高水平的问题求解能力。由于专家知识是不确定的，因此ES要达到高性能,必须解决好不确定性问题。传统的概率统计方法受限制放弃传统程序求解的逻辑完备性,8.2非精确性推理,Shortliffe等人1975年结合MYCIN系统的建立提出了确定性理论。DURA等人1976在PROSPECTOR的基础上给出了概率法。DempsterShafter同年提出证据理论。Zadeh两年后提出了可能性理论，1983年提出了模糊逻辑。,8.2非精确性推理,非确定性推理的研究和发展,MYCIN系统是第一个采用了不确定推理逻辑的专家系统，在20世纪70年代非常有名。这个系统提出该确定性方法时遵循了下面的原则：（1）不采用严格的统计理论。使用的是一种接近统计理论的近似方法。（2）用专家的经验估计代替统计数据（3）尽量减少需要专家提供的经验数据，尽量使少量数据包含多种信息。（4）新方法应适用于证据为增量式地增加的情况。（5）专家数据的轻微扰动不影响最终的推理结论。,确定性理论,MYCIN概述,用户,解释模块,咨询模块,知识获取模块,感染病专家与知识工程师,知识库,动态数据库(推理记录),患者数据库(原始数据库),MYCIN系统结构图,MYCIN推理策略,采用反向推理和深度优先搜索。诊断治疗过程如下：(1)确定患者有无细菌性感染。(2)确定可能引起感染的有机体。(3)确定对其有抑制作用的药物。(4)选择对治疗最合适的药物。这四个步骤由目标规则来执行。,MYCIN知识表示,如：RULE037PREMISE:($AND(NOTKNOWNCONTXTIDENT)(SAMECONTXTGRAMGRAMNEG)(SAMECONTXTMORPHROD)(SAMECONTXTAIRAEROBIC)ACTION:(CONCLUDECONTXTCLASSENTEROBACTERIACEAETALLY0.8),可信度是指人们根据以往经验对某个事物或现象为真的程度的一个判断，或者说是人们对某个事物或现象为真的相信程度。,可信度的概念,可信度具有一定的主观性，较难把握。但对某一特定领域，让该领域专家给出可信度还是可行的。,8.3.2CF模型,表示形式：在C-F模型中，知识是用产生式规则表示的，其一般形式为：IFETHENH(CF(H,E)其中，E是知识的前提条件；H是知识的结论；CF(H,E)是知识的可信度。,1.知识不确定性的表示:,例子：IF发烧AND流鼻涕THEN感冒(0.8),说明：当某人确实有“发烧”及“流鼻涕”症状时，则有80%的把握是患了感冒。,说明：(1)E可以是单一条件，也可以是复合条件。例如：E=(E1ORE2)ANDE3ANDE4(2)H可以是单一结论，也可以是多个结论(3)CF是知识的静态强度，CF(H,E)的取值为-1,1，表示当E为真时，证据对H的支持程度，其值越大，支持程度越大。(4)CF(H,E)可以理解为规则的可信度,可信度的定义在CF模型中，把CF(H,E)定义为CF(H,E)=MB(H,E)-MD(H,E),2.可信度的定义与性质,MB:信任增长度，MB(H,E)定义为:,MD:不信任增长度，MB(H,E)定义为:,MB和MD的关系:,当MB(H,E)0时:P(H|E)P(H)E的出现增加了H的概率当MD(H,E)0时：P(H|E)0时，MD(H,E)=0当MD(H,E)0时，MB(H,E)=0,值域,典型值(1)当CF(H,E)=1时，有P(H/E)=1，它说明由于E所对应证据的出现使H为真。此时，MB(H,E)=1，MD(H,E)=0。(2)当CF(H,E)=-1时，有P(H/E)=0，说明由于E所对应证据的出现使H为假。此时，MB(H,E)=0，MD(H,E)=1。(3)当CF(H,E)=0时，有MB(H,E)=0、MD(H,E)=0。前者说明E所对应证据的出现不证实H；后者说明E所对应证据的出现不否认H。(4)对H的信任增长度等于对非H的不信任增长度,对H的信任增长度等于对非H的不信任增长度对H的可信度与非H的可信度之和等于0可信度不是概率概率满足：P(H)+P(H)=1和0P(H),P(H)1但可信度不满足。,(5)对同一前提E，若支持若干个不同的结论Hi(i=1,2,n)，则：,若：专家给出的知识有如下情况CF(H1,E)=0.7,CF(H2,E)=0.4,非法，应进行调整或规范化,证据（E）不确定性的表示：证据的不确定性也是用可信度来表示的，其取值范围也为-1,1若E为初始证据，其值由用户给出。若E为中间结论，其值可通过计算得到。不确定性的含义：对E，其可信度CF(E)的含义如下：CF(E)=1，证据E肯定它为真CF(E)=-1，证据E肯定它为假CF(E)=0，对证据E一无所知0CF(E)1，证据E以CF(E)程度为真-1CF(E)0，证据E以CF(E)程度为假,3.证据不确定性的表示,4.否定证据不确定性的计算CF(E)=-CF(E)5.组合证据不确定性的计算“合取”与“析取”两种基本情况。,析取:当组合证据是多个单一证据的析取时即E=E1ORE2OROREn时，若已知CF(E1)，CF(E2)，CF(En)，则CF(E)=maxCF(E1),CF(E2),CF(En),合取:当组合证据是多个单一证据的组合时即E=E1ANDE2ANDANDEn时，若已知CF(E1)，CF(E2)，CF(En)，则CF(E)=minCF(E1),CF(E2),CF(En),CF模型中的不确定性推理实际上是从不确定的初始证据出发，不断运用相关的不确性知识，逐步推出最终结论和该结论可信度的过程。每一次运用不确定性知识，都需要由证据的不确定性和知识的不确定性去计算结论的不确定性。,6.不确定性推理,不确定性的更新公式:CF(H)=CF(H,E)max0,CF(E),若CF(E)0,称为事件B出现条件下，事件A发生的条件概率。,条件概率及贝叶斯定理,条件概率的意义在于：如果在随机试验中，已经观察到了事件B的发生，那么可以利用事件B发生的概率，去认识事件A的不确定性。,贝叶斯定理（Bayes）设事件A1，A2，A3，An中任意两个事件都不相交，则对任何事件B有下式成立：该定理就叫Bayes定理，上式称为Bayes公式。,条件概率及贝叶斯定理,贝叶斯定理,设Ai是导致事件B发生的所有可能原因，已知他们的概率为P（Ai）,这些概率被称为先验概率;设Ai在随机试验中不能或者没有被直接观察到，只能观察到与之联系的B的发生;在此条件下，对事件Ai出现的可能性作出判断，即求出关于B的条件概率P（Ai|B），又称为Ai的后验概率。,例如：用B代表发烧，A代表感冒:P（A|B）-P（B|A）,贝叶斯公式给出用先验概率P（B|A），求后验概率P（A|B）的方法,例子：,已知：s表示病人脖子强直；m表示病人患有脑膜炎p（s|m）=0.5;p(m)=1/50000;p(s)=1/20,p(m|s)=?,p(m|s)=p(s|m)p(m)/p(s)=0.0002,8.3.2粗糙集理论（RoughSet）,1965年，L.A.Zadeh提出FuzzySets的概念，试图通过这一理论解决G.frege的含糊概念。FS方法：利用隶属函数描述边界上的不确定对象。,1982年，波兰华沙理工大学Z.Pawlak教授针对G.frege的边界线区域思想提出了RoughSets理论。RS方法：把无法确认的个体都归属于边界区域，把边界区域定义为上近似集和下近似集的差集。,Roughsettheoryisstillanotherapproachtovagueness.Similarlytofuzzysettheoryitisnotanalternativetoclassicalsettheorybutitisembeddedinit.RoughsettheorycanbeviewedasaspecificimplementationofFregesideaofvagueness,i.e.,imprecisioninthisapproachisexpressedbyaboundaryregionofaset,andnotbyapartialmembership,likeinfuzzysettheory.Roughsetconceptcanbedefinedbyapproximations.,1982Z.Pawlak波兰,1问题,医生,症状头痛？肌肉痛？体温？,患病？流感？,条件属性,决策属性,条件属性,决策属性,是,不可分辨关系,RS理论是基于不可分辨关系的（等价关系）。,1问题,医生,症状头痛？肌肉痛？体温？,患病？流感？,表达条件属性等价类和决策属性等价类的关系（其中存在vague）,在条件属性下的等价类,在决策属性下的等价类,b1=p1,p2,p3b2=p5b3=p4,p6b4=p7,X=p1,p4,p5Y=p2,p3,p6,p7,条件属性下,决策属性下,决策属性,是,X=p1,p4,p5,上近似b1Ub2Ub3,下近似b1,边界域b2Ub3,直观理解:,对于上近似集外的元素,一定不属于X,对于边界域内的元素,可能属于X,也可能不属于X,对于下近似内的元素,一定属于X,RoughSet的能力,属性约简,属性的重要度,规则生成,8.4贝叶斯网络,根据概率理论的法则建立网络模型，对不确定性进行推理。贝叶斯网络是一系列变量的联合概率分布的图形表示。,8.4.1贝叶斯网络的表示,包含两个部分：贝叶斯网络结构图：有向无环图（DAG），其中图中的每个节点代表相应的变量，节点之间的连接关系代表了贝叶斯网络的条件独立语义。节点和节点之间的条件概率表（CPT）：一系列的概率值。,命题S(moker)：吸烟者命题C(oalMiner)：煤矿矿井工人命题L(ungCancer)：他患了肺癌命题E(mphysema)：他患了肺气肿,贝叶斯网有时也叫因果网，因为可以将连接结点的弧认为是表达了直接的因果关系。,如果一个贝叶斯网络提供了足够的条件概率值，足以计算任何给定的联合概率，我们就称，它是可计算的，即可推理的。贝叶斯网的两个要素：其一为贝叶斯网的结构，也就是各节点的继承关系，其二就是条件概率表CPT。若一个贝叶斯网可计算，则这两个条件缺一不可。,贝叶斯网络,例：,给定了他们是否给你打电话的证据，估计有人入室行窃的概率,7.4.2贝叶斯网络的语义,贝叶斯网络能表示任意概率分布的同时，它们为这些能用简单结构表示的分布提供了可计算优势。假设对于顶点xi，其双亲节点集为Pai，每个变量xi的条件概率P(xi|Pai)。则顶点集合X=x1,x2,xn的联合概率分布可如下计算：,贝叶斯网络的联合概率分布,Burglary,Earthquake,P(B),0.001,JohnCalls,Alarm,P(E),0.002,MaryCalls,BEP(A),tt.95,tf.90,ft.30,ff.001,AP(J),t.90,f.05,AP(M),t.70,f.01,计算报警器响了，但既没有盗贼闯入，也没有发生地震，同时John和Mary都给你打电话的概率,P(jmabe)=P(j|a)P(m|a)P(a|be)P(b)P(e)=0.90*0.70*0.001*0.999*0.998=0.00062,贝叶斯网络的联合概率分布,该等式暗示了早先给定的图结构有条件独立语义。它说明贝叶斯网络所表示的联合分布作为一些单独的局部交互作用模型的结果具有因式分解的表示形式。,7.4.3贝叶斯网的推理模式,因果推理（由上向下推理）诊断推理辩解,在确定某个已观察事件也就是一组证据变量值的某个赋值后，任何概率推理系统的基本任务都是要计算一组查询变量的后验概率。,因果推理（由上向下推理）,7.4.3贝叶斯网络的推理模式,给定患者是一个吸烟者（S），计算他患肺气肿（E）的概率P(E|S)。,S：推理的证据，E：询问结点。,P(E|S)=P(E,C|S)+P(E,C|S);/全概率公式=P(E|C,S)*P(C|S)+P(E|C,S)*P(C|S);/贝叶斯公式在图中，C和S并没有双亲关系，符合条件独立条件：P(C|S)=P(C),P(C|S)=P(C),由此可得：P(E|S)=P(E|S,C)*P(C)+P(E|C,S)*P(C),P(E,C|S)P(E,C,S)/P(S)P(E|C,S)*P(C,S)/P(S)(贝叶斯定理)P(E|C,S)*P(C|S)(反向利用贝叶斯定理,因果推理的主要操作：1）按照给定证据的V和它的所有双亲的联合概率，重新表达给定证据的询问结点的所求条件概率。2）回到以所有双亲为条件的概率，重新表达这个联合概率。3）直到所有的概率值可从CPT表中得到，推理完成。,贝叶斯网络的推理,诊断推理,计算“不得肺气肿的不是矿工”的概率P(C|E),即在贝叶斯网中，从一个子结点计算父结点的条件概率。也即从结果推测一个起因，这类推理叫做诊断推理。,贝叶斯网络的推理,P(C|E)P(E|C)*P(C)/P(E)，P(E|C)=P(E,S|C)+P(E,S|C)=P(E|S,