人工智能之不确定知识表示及推理.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,*,*,第 一 章,不确定知识表示及推理,10/1/,1,人工智能之不确定知识表示及推理,第1页,内容,1.1,概述,1.2,概率模型,1.3,主观Bayes方法,1.4,可信度方法,10/1/,2,人工智能之不确定知识表示及推理,第2页,1.1,概述,10/1/,3,人工智能之不确定知识表示及推理,第3页,所谓不确定性推理就是从不确定性初始事实（证据）出发，经过利用不确定知识，最终推出含有一定程度不确定性却是合理或者近乎合理结论思维过程。,需要处理问题：,不确定性表示,不确定性匹配,不确定性更新算法,10/1/,4,人工智能之不确定知识表示及推理,第4页,证据不确定性,一、不确定性表示,证据通常有两类：,一类为初始事实。这一类证据多起源于观察，因而通常含有不确定性；,另一类为推理过程中产生中间结果。,证据不确定性用C(E)表示，它代表对应证据不确定性程度，即表示证据E为真程度。,假如E为初始事实，则C(E)由用户给出。,假如E为推理过程中产生中间结果，则C(E)能够经过不确定性更新算法来计算。,知识不确定性,10/1/,5,人工智能之不确定知识表示及推理,第5页,规则：IF E THEN H,规则是知识，E是规则前提即证据，H是该规则结论，也能够是其它规则证据。,E,H,C(E),C(H),f,(E,H),规则不确定性通惯用一个数值,f,(E,H)表示，称为规则强度。,规则假设(结论)H也能够作为其它规则证据，其不确定用C(H)表示，C(H)必须经过不确定性更新算法来计算。,10/1/,6,人工智能之不确定知识表示及推理,第6页,在确定一个量度方法及其范围时，应注意以下几点：,量度要能充分表示对应知识和证据不确定性程度。,量度范围指定应便于领域教授及用户对不确定性预计。,量度要便于对不确定性更新进行计算，而且对结论算出不确定性量度不能超出量度范围,量度确实定应该是直观，同时应有对应理论依据。,10/1/,7,人工智能之不确定知识表示及推理,第7页,二、不确定性匹配算法,设计一个数用来计算匹配双方相同程度，另外再指定一个相同程度(称为阈值)，用来衡量匹配双方相同程度是否落在指定程度内。,假如落在指定程度内，就称它们是可匹配，对应知识可被应用。,不然就称它们是不可匹配，对应知识不可应用。,10/1/,8,人工智能之不确定知识表示及推理,第8页,三、不确定性更新算法,即在推理过程中怎样考虑知识不确定性动态积累和传递。,1、已知规则前提不确定性C(E)和规则强度,f,(E,H)，怎样求假设H不确定性C(H)。,即定义算法g,1,，使C(H)=g,1,C(E),f,(E,H),E,1,H,C(E,1,),C(H),f,(E,1,H),E,2,H,C(E,2,),C(H),f,(E,2,H),2、并行规则算法,定义算法g,2,：C(H)=g,2,C,1,(H),C,2,(H),10/1/,9,人工智能之不确定知识表示及推理,第9页,3、证据合取不确定性算法,C(E,1,E,2,)=g,3,C(E,1,),C(E,2,),C(E,1,E,2,)=g,4,C(E,1,),C(E,2,),4、证据析取不确定性算法,合取和析取不确定性算法统称为组合证据不确定性算法。,最大最小法,C(E,1,E,2,)=min C(E,1,),C(E,2,),C(E,1,E,2,)=max C(E,1,),C(E,2,),C(E,E,2,)=C(E,1,)C(E,2,),C(E,E,2,)=C(E,1,)C(E,2,)C(E,1,)C(E,2,),有界方法,概率方法,C(E,1,E,2,)=max 0,C(E,1,)+C(E,2,)1,C(E,1,E,2,)=min 1,C(E,1,)+C(E,2,),10/1/,10,人工智能之不确定知识表示及推理,第10页,设A,1,、A,2,、A,3,、A,4,为原始证据，不确定性分别为：,CA,1,)、C(A,2,)、C(A,3,)、C(A,4,),求A,5,、A,6,、A,7,不确定性。,举例,A,1,A,2,OR,A,4,A,3,AND,A,5,R,1,f,1,A,6,R,2,f,2,A,7,R,3,f,3,R,4,f,4,10/1/,11,人工智能之不确定知识表示及推理,第11页,由证据A,1,和A,2,不确定性C(A,1,)和C(A,2,),由A1和A2析取不确定性C(A,1,A,2,)和规则R,1,规则强度,f,1,依据算法4求出A,1,和A,2,析取不确定性C(A,1,A,2,)。,依据算法1求出A,5,不确定性C(A,5,)。,由证据A3和A4不确定性C(A,3,)和C(A,4,),由A3和A4合取不确定性C(A,3,A,4,)和规则R,2,规则强度,f,2,，,依据算法3求出A3和A4合取不确定性C(A,3,A,4,)。,依据算法1求出A,6,不确定性C(A,6,)。,10/1/,12,人工智能之不确定知识表示及推理,第12页,由A5不确定性C(A,5,)和规则R,3,规则强度,f,3,由A,6,不确定性C(A,6,)和规则R,4,规则强度,f,4,由A,7,两个依据独立证据分别求出不确定性C,(A,7,)和C,(A,7,),依据算法1求出A7其中一个不确定性C,(A7)。,依据算法1求出A,7,另外一个不确定性C,(A,7,)。,依据算法2求成A,7,最终不确定性C(A,7,)。,10/1/,13,人工智能之不确定知识表示及推理,第13页,1.2,概率方法,10/1/,14,人工智能之不确定知识表示及推理,第14页,一、基础,1、全概率公式,P(A,i,)0,；,两两互不相容，即当i,j时，有,设事件满足：,，D为必定事件,则对任何事件B有下式成立：,提供了一个计算P(B)方法。,10/1/,15,人工智能之不确定知识表示及推理,第15页,2、Bayes公式,定理：设事件满足上述定理条件，则对任何事件B有：,该定理称为Bayes定理，上式称为Bayes公式。,10/1/,16,人工智能之不确定知识表示及推理,第16页,假如把全概率公式代入,Bayes,公式中，就可得到：,即：,10/1/,17,人工智能之不确定知识表示及推理,第17页,二、概率推理模型,Bayes方法用于不准确推理条件是已知：P(E)，P(H)，P(E|H),IF E THEN H,若一组证据E,1,E,2,E,n,同时支持假设H时，则：,对于H，E,1,E,2,E,n,之间相互独立,对于普通不准确推理网络，必须做以下约定：,当一个证据E支持多个假设H,1,H,2,H,n,时，则：,假设H,1,H,2,H,n,之间互不相容,10/1/,18,人工智能之不确定知识表示及推理,第18页,假如一个证据E支持多个假设H,1,H,2,H,n,，即：IF E THEN H,i,并已知P(H,i,)和P(E|H,i,)，则,假如有多个证据E,1,E,2,E,m,和多个结论H,1,H,2,H,n,，则：,10/1/,19,人工智能之不确定知识表示及推理,第19页,设已知：P(H,1,)=0.4,P(H,2,)=0.3,P(H,3,)=0.3,P(E,1,|H,1,)=0.5,P(E,1,|H,2,)=0.6,P(E,1,|H,3,)=0.3,P(E,2,|H,1,)=0.7,P(E,2,|H,2,)=0.9,P(E,2,|H,3,)=0.1,=0.45,同理,求：P(H,1,|E,1,E,2,),P(H,2,|E,1,E,2,),P(H,3,|E,1,E,2,)举例,10/1/,20,人工智能之不确定知识表示及推理,第20页,概率推理模型优缺点,有较强理论背景和良好数学特征，当证据及结论都彼此独立时，计算复杂度比较低。,它要求给出结论Hi先验概率P(H,i,)及证据E,j,条件概率P(E,j,|H,i,)，要取得这些数据是一件相当困难工作。,Bayes公式应用条件很严格，它要求各事件相互独立，若证据之间存在依赖关系，就不能直接使用这个方法,10/1/,21,人工智能之不确定知识表示及推理,第21页,1.3,主观,Bayes,方法,10/1/,22,人工智能之不确定知识表示及推理,第22页,E,H,P(E),P(H),LS,LN,LS，LN(,0)分别称为充分性量度和必要性量度，这两个数值由领域教授给出。,一、不确定性表示,1、知识不确定性表示,IF E THEN(LS,LN)H(P(H),10/1/,23,人工智能之不确定知识表示及推理,第23页,O等价于概率函数P，定义以下：,P,越大则,O,越大，,P,和,O,在概率含义上等价，但取值范围不一样：,当P0.5时，O0.5时，O1,当P=0.5时，O=1,当P=0时，O=0,几率函数O(odds),10/1/,24,人工智能之不确定知识表示及推理,第24页,H先验几率O(H)和后验几率O(H|E),10/1/,25,人工智能之不确定知识表示及推理,第25页,同理可得：,O(H|,E)=LN,O(H),O(H|E)=LS,O(H),10/1/,26,人工智能之不确定知识表示及推理,第26页,LS：规则充分性量度,LS=1时，O(H|E)=O(H)，说明E对H没有影响；,LS1时，O(H|E)O(H)，说明E支持H，且LS越大，E对H支持越充分。可见，E出现对H为真是充分，故称LS为充分性度量。,LS1时，O(H|E)1时，O(H|E)O(H)，说明E支持H，且LN越大，E对H支持越充分。,当LN1时，O(H|E)1且LN1,LS1,LS=LN=1,因为E和,E,不可能同时支持H或同时反对H，所以领域教授在为一条知识中LS和LN赋值时，不应该同时大于1或同时小于1。,10/1/29,人工智能之不确定知识表示及推理,第29页,2、证据不确定性表示,在主观Bayes方法中，证据E不确定性由用户依据观察S给出后验概率P(E|S)或后验几率O(E|S)表示。,当E为真时，P(E|S)=1，O(E|S)=,当E为假时，P(E|S)=0，O(E|S)=0,当E不确定时，0P(E|S)0，所以使用CP公式后一部分：,10/1/,53,人工智能之不确定知识表示及推理,第53页,求O(H,1,|S,2,),因为C(E,2,|S,2,)=10，所以使用CP公式后一部分：,10/1/,54,人工智能之不确定知识表示及推理,第54页,求,O(H,1,|S,1,S,2,),10/1/,55人工智能之不确定知识表示及推理,第55页,求O(H,2,|S,1,S,2,),为了确定应用EH公式哪一部分，需要判断P(H,1,|S,1,S,2,)与P(H,1,)关系。,P(H,1,|S,1,S,2,)P(H,1,)，,必须用,EH,公式后半部分,：,10/1/,56,人工智能之不确定知识表示及推理,第56页,10/1/,57,人工智能之不确定知识表示及推理,第57页,求O(H,2,|S,3,),因为C(E,3,|S,3,)=-20，表示证据存在增加结论为真程度，CF(H，E)值越大结论H越真；,CF(H，E)=1，表示证据存在结论为真；,CF(H，E)0,证据出现越是支持H为真，就使CFH,E)值越大；,反之，使：CF(H,E)0,当证据必定为真时：CF(E)=1,当证据以某种程度为假时：CF(E)0，即证据以某种程度为真，则CF(H)=CF(H,E)CF(E),若CF(E)=1，即证据为真时，则CF(H)=CF(H,E)；,若CF(E)0，即证据以某种程度为假，则CF(H)=0；,在可信度方法不准确推理中，并没有考虑证据为假时对结论H所产生影响。,10/1/,73,人工智能之不确定知识表示及推理,第73页,IF E,1,THEN H (CF(H,E,1,),IF E,2,THEN H (CF(H,E,2,),3、多个独立证据推出同一假设合成算法,先分别求两条规则得出结论可信度。,CF,1,(H)=CF(H,E,1,),max0,CF(E,1,),CF,2,(H)=CF(H,E,2,),max0,CF(E,2,),利用下式求出E,1,和E,2,对H综合影响所形成CF,1,2,(H)。,CF,1,(H),0,CF,2,(H),0：CF,1,2,(H)=CF,1,(H)+CF,2,(H)-CF,1,(H),CF,2,(H),CF,1,(H)0,CF,2,(H)0：CF,1,2,(H)=CF,1,(H)+CF,2,(H)+CF,1,(H),CF,2,(H),CF,1,(H)和CF,2,(H)异号：CF,1,2,(H)=CF,1,(H)+CF,2,(H),10/1/,74,人工智能之不确定知识表示及推理,第74页,在MYCIN系统基础上形成教授系统工具EMYCIN，将其修改为：,在组合两个以上独立证据时，可先组合其中两个，再将结果与第三个证据组合，如此下去，直到组合完成为止。,当CF,1,(H),0,CF,2,(H),0 时：,CF,1,2,(H)=CF,1,(H)+CF,2,(H)-CF,1,(H),CF,2,(H),当CF,1,(H)0,CF,2,(H)0：,CF,1,2,(H)=CF,1,(H)+CF,2,(H)+CF,1,(H),CF,2,(H),当CF1(H)和CF2(H)异号 时：,10/1/,75,人工智能之不确定知识表示及推理,第75页,即：已知规则,IF E THEN H CF(H,E),及CF(H)，求CF(H|E),4、在已知结论原始可信度情况下，结论可信度更新计算方法,这时分三种情况进行讨论。,10/1/,76,人工智能之不确定知识表示及推理,第76页,CF(H),0,CF(H,E),0：,CF(H|E)=CF(H)+CF(H,E)-CF(H,E),CF(H),CF(H)0,CF(H,E)0：,CF(H|E)=CF(H)+CF(H,E)+CF(H,E),CF(H),CF(H)和CF(H,E)异号：,当CF(E)=1时，即证据必定出现时,10/1/,77,人工智能之不确定知识表示及推理,第77页,CF(H),0,CF(H,E),0：,CF(H|E)=CF(H)+CF(H,E),CF(E)-CF(H),CF(H,E),CF(E),CF(H)0,CF(H,E)0：,CF(H|E)=CF(H)+CF(H,E),CF(E)+CF(H),CF(H,E),CF(E),CF(H),和,CF(H,E),异号：,当0CF(E)1时,10/1/,78,人工智能之不确定知识表示及推理,第78页,当,CF(E),0,时,在MYCIN系统中就要求，当CF(E),0.2时，规则IF E THEN H不可使用。,结论可信度合成算法和更新算法本质上是一致，但对不一样前提条件，使用不一样方法，解题效果或难易程度不一样。有些题目使用合成法求解就比较轻易，而有些题目就需要使用更新法。,规则不可使用，对结论H可信度无影响。,10/1/,79,人工智能之不确定知识表示及推理,第79页,R1：IF A,1,THEN B,1,CF(B,1,A,1,)=0.8,R2：IF A,2,THEN B,1,CF(B,1,A,2,)=0.5,R3：IF B,1,A,3,THEN B,2,CF(B,2,B,1,A,3,)=0.8,而且已知：,CF(A,1,)=CF(A,2,)=CF(A,3,)=1,而对B,1,，B,2,一无所知。,求CF(B,1,)和CF(B,2,)。,三、可信度方法应用举例,1、多条知识下，合成法求结论可信度举例,举例1,10/1/,80,人工智能之不确定知识表示及推理,第80页,解：因为对B,1,，B,2,初始可信度一无所知，使用合成算法计算,A,1,B,1,R,1,A,2,R,2,A,3,B,2,R,3,对知识R,1,和R,2,，分别计算CF(B,1,),CF,1,(B,1,)=CF(B,1,A,1,),max0,CF(A,1,)=0.8,1=0.8,CF,2,(B,1,)=CF(B,1,A,2,),max0,CF(A,2,)=0.5,1=0.5,利用合成算法计算B,1,综合可信度,CF,1,2,(B,1,)=CF,1,(B,1,)+CF,2,(B,1,)-CF,1,(B,1,),CF,2,(B,1,)=0.8+0.5-0.8,0.5=0.9,计算B,2,可信度CF(B,2,),CF(B,2,)=CF(B,2,B,1,A,3,),max0,CF(B,1,A,3,),=0.8,max0,minCF(B,1,),CF(A,3,)=0.8,max0,min0.9,1,=0.8,max0,0.9=0.8,0.9=0.72,10/1/,81,人工智能之不确定知识表示及推理,第81页,R1：IF E,1,THEN H CF(H,E,1,)=0.8,R2：IF E,2,THEN H CF(H,E,2,)=0.6,R3：IF E,3,THEN H CF(H,E,3,)=0.5,R4：IF E,4,(E,5,E,6,)THEN E1,CF(E,1,E,4,(E,5,E,6,)=0.7,R5：IF E,7,E,8,THEN E,3,CF(E,3,E,7,E,8,)=0.9,在系统运行中已从用户处得：,CF(E,2,)=0.8，CF(E,4,)=0.5，CF(E,5,)=0.6，CF(E,6,)=0.7，CF(E,7,)=0.6，CF(E,8,)=0.9,求：CF(H),举例2,10/1/,82,人工智能之不确定知识表示及推理,第82页,解：由已知知识建立推理网络如图。,E,1,H,R,1,E,2,R,2,E,3,R,3,E,4,E,5,E,6,R,4,E,8,E,7,R,5,10/1/,83,人工智能之不确定知识表示及推理,第83页,由R4：,CF(E,1,),=CF(E,1,E,4,(E,5,E,6,),max0,CF(E,4,(E,5,E,6,),=0.7,max0,minCF(E,4,),CF(E,5,E,6,),=0.7,max0,minCF(E,4,),maxCF(E,5,),CF(E,6,),=0.7,max0,minCF(E,4,),max0.6,0.7,=0.7,max0,minCF(E,4,),0.7,=0.7,max0,min0.5,0.7,=0.7,max0,0.5=0.7,0.5=0.35,由R5：,CF(E,3,),=CF(E,3,E,7,E,8,),max0,CF(E,7,E,8),=0.9,max0,minCF(E,7,),CF(E,8,),=0.9,max0,min0.6,0.9 ,=0.9,max0,0.6=0.9,0.6=0.54,10/1/,84,人工智能之不确定知识表示及推理,第84页,由R1：,将R1和R2两条知识合成：,CF,1,2,(H),=CF,1,(H)+CF,2,(H)-CF,1,(H),CF,2,(H),=0.28+0.48-0.28,0.48=0.6256,CF,1,(H),=CF(H,E,1,),max0,CF(E,1,),=0.8,max0,0.35=0.8,0.35=0.28,由R2：,CF,2,(H),=CF(H,E,2,),max0,CF(E,2,),=0.6,max0,0.8=0.6,0.8=0.48,由R3：,CF,3,(H),=CF(H,E,3,),max0,CF(E,3,),=-0.5,max0,0.54=-0.5,0.54=-0.27,10/1/,85,人工智能之不确定知识表示及推理,第85页,将CF,1,2,(H)和CF,3,(H)合成,10/1/,86,人工智能之不确定知识表示及推理,第86页,规则可信度为：,2、多条知识下，更新法求结论可信度举例,证据可信度为：CF(A)=CF(B)=CF(C)=CF(D)=0.5,X,Y初始可信度为：CF,0,(X)=0.1,CF,0,(Y)=0.2,要求用MYCIN方法计算：,结论X可信度CF(X),结论Y可信度CF(Y),R1：A,XCF(X,A)=0.8,R2：B,XCF(X,B)=0.6,R3：C,XCF(X,C)=0.4,R4：X,D,Y CF(Y,X,D)=0.3,举例3,10/1/,87,人工智能之不确定知识表示及推理,第87页,解：考虑X,Y含有初始可信度，故用更新法计算结论可信度。,先计算X可信度更新值：,CF(A)=CF(B)=CF(C)=CF(D)=0.51,由R1：,CF(X|A),CF,0,(X)+CF(X,A),CF(A)-CF,0,(X),CF(X,A),CF(A),=0.1+0.8,0.5-0.1,0.8,0.5=0.46由R2：,CF(X|AB),=CF(X|A)+CF(X,B),CF(B)-CF(X|A),CF(X,B),CF(B),=0.46+0.6,0.5-0.46,0.6,0.5=0.622,10/1/,88,人工智能之不确定知识表示及推理,第88页,由R3：,CF(X|ABC),=CF(X|AB)+CF(X,C),CF(C)CF(X|AB),CF(X,C),CF(C),=0.622+0.4,0.5-0.622,0.4,0.5=0.698,则CF(X)=0.698,CF(X,D)=minCF(X),CF(D)=min0.698,0.5=0.5,由R4：,CF(Y|D),=CF,0,(Y)+CF(Y,D),CF(D)CF,0,(Y),CF(Y,D),CF(D),=0.2+0.3,0.5-0.2,0.3,0.5=0.32,则CF(Y)=0.32,10/1/,89,人工智能之不确定知识表示及推理,第89页,R1：IF A1 THEN B1 CF(B1,A1)=0.8,R2：IF A2 THEN B1 CF(B1,A2)=0.5,R3：IF B1,A3 THEN B2CF(B2,B1,A3)=0.8,而且已知：,CF(A1)=CF(A2)=CF(A3)=1,对B1，B2一无所知，其可信度为：CF,0,(B1)=CF,0,(B2)=0,求：CF(B1)和CF(B2),举例4,10/1/,90,人工智能之不确定知识表示及推理,第90页,由R1：,使用更新法。,因为CF(A1)=CF(A2)=CF(A3)=1,使用R1规则后，CF(B1)由0提升到0.8,由R2：,CF(B1|A1A2),=CF(B1|A1)+CF(B1,A2)CF(B1|A1),CF(B1|A1),=0.8+0.5-0.8,0.5=0.9,所以CF(B1)更新值为0.9,CF(B1,A3)=minCF(B1),CF(A3)=min0.9,1=0.9,CF(B1|A1),=CF,0,(B1)+CF(B1,A1)CF(B1,A1),CF,0,(B1)=0+0.8-0=0.8,10/1/,91,人工智能之不确定知识表示及推理,第91页,由R3：,使用合成算法前提是：结论原来可信度是0，即对结论情况一无所知。在这种情况下，这两种算法是等价。,从某种意义上来说，合成算法是更新算法一个特例。,CF(B2|B1,A3),=CF,0,(B2)+CF(B2,B1,A3),CF(B1,A3),CF,0,(B2),CF(B2,B1,A3),CF(B1,A3),=0+0.8,0.9-0=0.72,10/1/,92,人工智能之不确定知识表示及推理,第92页,