资源描述
,Artificial Intelligence,Uncertainty Reasoning,:,*,Click to edit Master text styles,Second level,Third level,Graduate University,Chinese academy of Sciences.,人工智能,Artificial Intelligence,不确定性推理,Uncertainty Reasoning,本章主要内容,基本概念,主观,Bayes,方法,确定性方法,证据理论,模糊推理,基本概念(1/3),什么是不确定性推理?,不确定性推理是建立在非经典逻辑上的一种推理,是对不确定性知识的运用与处理,是从不确定性的初始证据出发,通过运用不确定性的知识,最终推出具有一定程度的不确定性但却合理或者近乎合理的结论的思维过程,为什么要研究,不确定性推理?,日常生活中含有大量的不确定的信息,ES,系统中大量的领域知识和专家经验,不可避免的包含各种不确定性。,基本概念(2/3),不确定性推理的基本问题:,表示问题,:即采用什么方法描述不确定性.一般有数值表示和非数值的语义表示方法.,计算问题,:主要指不确定性的传播和更新,也即获得新信息的过程.主要包括:,已知,C(A),A,B f(B,A),如何计算,C(B),已知,C,1,(A),又得到,C,2,(A),如何确定,C(A),如何由,C(A,1,),C(A,2,),计算,C(A,1,A,2,),C(A,1,A,2,),语义问题:,指的是上述表示和计算的含义是什么,如何进行解释.,基本概念(3/3),不确定推理方法的分类,形式化方法,:在推理一级扩展确定性方法.,逻辑方法:是非数值方法,采用多值逻辑、非单调逻辑来处理不确定性,新计算方法:认为概率方法不足以描述不确定性,出现了确定性理论,确定性因子,模糊逻辑方法等,新概率方法:在传统的概率框架内,采用新的计算工具以确定不确定性描述,非形式化方法:,在控制一级上处理不确定性,如制导回溯、启发式搜索等等,本章主要内容,基本概念,主观,Bayes,方法,可信度方法,证据理论,模糊推理,主观,Bayes,方法,1976年提出的,应用于地矿勘探专家系统,Prospector,中,不确定推理系统包括:,不确定性的表示:,规则,/知识,事实/证据,不确定性的计算,组合证据的不确定算法,不确定性的传递算法,结论的不确定算法,规则不确定的表示(1/2),if E then (LS,LN)H (P,(,H),(1)E是规则的前提条件,H是结论,P,(,H),是,H,的先验概率,是指在没有任何证据的情况下结论,H,为真的概率。,(2),LS是充分性度量:表示E对H的支持程度,取值范围0,+,),其定义为:,P(E/H),LS=-,P(E/H),规则不确定的表示(2/2),(3),LN是必要性度量:表示E对H的支持程度,取值范围0,+,),其定义为:,P(E/H)1-P(E/H),L,N,=-=-,P(E/H)1-P(E/H),证据不确定的表示,对于初始证据E,由用户根据观察S给出,P(E/S).,引入可信度函数,C(E/S),:,(1),C(E/S)=-5,表示在,S,下,,E,肯定不存在,P(E/S)=0,(2)C(E/S)=0,表示在,S,与,E,无关,,P(E/S)=P(E),(3)C(E/S)=5,表示在,S,下,,E,肯定存在,,P(E/S)=1,(4)C(E/S),为其他值的时候,,P(E/S),可以通过线性插值得到。,组合证据不确定的表示,(1),E=E,1,E,2,E,n,如果已知,P(E,1,/S),P(E,n,/S),则:,P(E,n,/S)=,min,P(E,1,/S),P(E,n,/S),(2)E=E,1,E,2,E,n,如果已知,P(E,1,/S),P(E,n,/S),则:,P(E,n,/S)=,max,P(E,1,/S),P(E,n,/S),(3),对于“非”:,P(E/S)=1-P(E/S),不确定性的传递算法,主观,Bayes,方法推理的任务就是根据证据E的概率,P(E),和,LS,LN,的值,把,H,的先验概率,P(H),更新为,P(H/E),或,P(H/E)。,分下面三种情况讨论:,证据肯定存在,证据肯定不存在,证据不确定,证据肯定存在(1/2),证据肯定存在时:,P(E)=P(E/S)=1,P(H/E)=P(H),P(E/H)/P(E),P(H/E)=P(H),P(E/H)/P(E),P(H/E)P(H)P(E/H),-=-,P(H/E)P(H)P(E/H),引入几率函数,O(x),定义为,:,O(x)=P(x)/(1-P(x),P(x)=O(x)/(1+O(x),证据肯定存在(2/2),O(H/E)=LS,O(H),P(H/E)=LS,P(H)/(LS-1),P(H)+1),LS的意义:,(1),LS,1时,O(H/E),O(H),P(H/E),P(H),,说明,E,的存在将增强,H,为真的概率。,E,的存在对,H,为真是充分的,所以称,LS,为充分性度量,(2),LS,=1时,O(H/E)=,O(H),(3),LS,1时,O(H/E)1,时,O(H/E),O(H),P(H/E),P(H),,说明,E,的不存在将增强,H,为真的概率。,(2),LN,=1,时,O(H/E)=,O(H),(3),LN,1,时,O(H/E)1,LN1,LS1,LN1,LS1,LN1,LS=LN=1,例,一,设有如下知识:,r,1,:if E,1,then(10,1)H,1,(0.03),r,2,:if E,2,then(20,1)H,2,(0.05),r,3,:if E,3,then(1,0.002)H,3,(0.3),求:当证据存在及不存在时,,P(H,i,/E,i,),及,P(H,i,/E,i,),的值各是多少,证据不确定(1/2),证据不定时:0,P(E/S)0,MD(H,E)=0,当,MD(H,E)0,MB(H,E)=0,知识的不确定性表示(续),CF(H,E),的直观意义:,(1),CF(H,E)0,则,P(H|E)P(H):,E,的出现增加了,H,为真的概率,增加了,H,为真的可信度,(2),CF(H,E),0,则,P(H|E)0,表示,E,以,CF(E),为真,CF(E)=0,CF,2,(H)=0,CF(H)=,CF,1,(H)+CF,2,(H)+CF,1,(H)CF2(H),CF,1,(H)0,CF,2,(H)0,CF,1,(H)+CF2(H),其他,可信度,模型-,例一,r1:A,1,B,1,CF(B,1,A,1,)=0.8,r2:A,2,B,1,CF(B,1,A,2,)=0.5,r3:,B,1,A,3,B,2,CF(B,2,B,1,A,3,)=0.8,初始证据,A,1,,,A,2,,,A,3,的,CF,值均设为1,而初始未知证据,B,1,,,B,2,的,CF,值为0,即对,B,1,,,B,2,是一无所知的。,求:,CF(B,1,),CF(B,2,),的更新值,可信度,模型-,例二,r1:A,1,B,1,CF(B,1,A,1,)=0.8,r2:A,2,B,1,CF(B,1,A,2,)=0.6,初始证据,A,1,,,A,2,的,CF,值均设为0.5,而初始未知证据,B,1,的,CF,值为0.1。,求:,CF(B,1,)的更新值,本章主要内容,基本概念,主观,Bayes,方法,确定性方法,证据理论,模糊推理,证据理论,主要内容:,概率分配函数,信任函数,似然函数,证据的不确定性度量,规则的不确定性度量,推理计算,概率分配函数,定义:,U,为样本空间,设函数,M:2,U,0,1,,且满足:,M(),=0,AU,M(A)=1,则称,M,为,2,U,上的,概率分配函数,,,M(A),称为,A,的基本概率数,(1),M(A),的作用是把,U,的任意一个子集,A,都映射为0,1上的一个数,M(A),。,它表示证据对,U,的子集,A,成立的一种信任度量,是对,U,的子集的信任分配。,(2)概率分配函数不是概率。,证据理论,例:,U=,红,黄,蓝,假设:,M(,红,)=0.3,M(,黄)=0,M(,蓝)=0.1,M(,红,黄)=0.2,M(,红,蓝)=0.2,M(,黄,蓝)=0.1,M(,红,黄,蓝)=0.1,M(,)=0,信任函数,定义:命题的信任函数,Bel,:,2,U,0,1,,且,Bel,(A,)=,BA,M(B),对所有的,AU,(1),命题,A,的信任函数的值,是,A,的所有子集的基本概率分配函数值的和,用来表示对,A,的总的信任,(2),Bel,函数又称为下限函数,(3),Bel,()=M()=0,Bel,(U,)=,BU,M(B)=1,似然函数,定义:似然函数,Pl,:,2,U,0,1,,且,Pl,(A)=1-,Bel,(A,),对所有的,AU,(1),Bel,(A,),表示对,A,为真的信任度,则,Bel,(A,),表示对,A,为真,即,A,为假的信任度,所以,Pl,(A),表示,A,非假的信任度,它又称为上限函数,。,(2),Pl,(A)=1-,Bel,(A,)=,AB,M(B),(3)0,Bel,(A,),Pl,(A),1,(4),Pl,(A)-,Bel,(A,):,表示既不信任,A,,也不信任,A,的一种度量,可表示对不知道的度量,证据的不确定性度量,(1)以区间,(,Bel,(A,),Pl,(A),作为证据,A,的不确定性度量:表示了对,A,信任程度的上限和下限。,A(0,0):,表示,A,为假,A(0,1):,表示对,A,一无所知,A(1,1):,表示,A,为真,(2)以函数:,f,1,(A)=,Bel,(A)+(|A,|,|U|)(,Pl,(A)-,Bel,(A,),表示证据,A,的不确定性度量。,f,1,(,)=0,f,1,(U)=1,0,f,1,(A),1 AU,规则的,不确定性度量,设U=,u,1,u,n,A,和,B,为,U,的子集,如:,A=a,1,a,m,B=b,1,b,k,规则表示如下:,A B=b,1,b,k,c,1,c,k,(1)B是结论,用样本空间的子集表示,,b,1,b,k,是该子集中的元素,(2),c,1,c,k,表示规则的不确定性度量,,c,i,表示,b,i,的可信度,(3),c,i,0,,n,i,=1,c,i,1,推理计算,f,1,(A,1,A,2,)=,min,f,1,(A,1,),f,1,(A,2,),f,1,(A,1,A,2,)=,max,f,1,(A,1,),f,1,(A,2,),已知,f,1,(A,),A B=b,1,b,k,c,1,c,k,,,求,f,1,(B,),(1)求出,B,的概率分配函数,M(B)=M(,b,1,b,k,)=,f,1,(A,),c,1,f,1,(A,)c,k,M(U)=1-,k,i,=1,f,1,(A,),c,i,推理计算(续),如果有两条知识支持同一条结论:,A,1,B=b,1,b,k,c,1,c,k,,,A,2,B=b,1,b,k,c,1,c,k,,,则首先分别对每一条知识求出概率分配函数:,M,1,(,b,1,b,k,),M,2,(,b,1,b,k,),然后由:,M=M,1,M,2,求出结论B的概率分配函数M,推理计算(续),概率分配函数的合成定义:,设,M,1,和,M,2,是,两个概率分配函数,则合成,M=M,1,M,2,定义为:,M(),=0,M(A),=K,XY=A,M,1,(X,),M,2,(Y,),其中,x,y,是U的子集,并且:,K,-1,=1-,XY=,M,1,(X,),M,2,(Y,),=,XY,M,1,(X,),M,2,(Y,),推理计算(续),概率分配函数的合成示例:,例一:设,U=,黑,白,且,M,1,(,黑,白,黑,白,)=(0.3,0.5,0.2,0),M,2,(,黑,白,黑,白,)=(0.6,0.3,0.1,0),例二:设,U=a,b,c,d,M,1,(,b,c,d,U,)=(0.7,0.3),M,2,(a,b,U,)=(0.6,0.4),推理计算(续),(2)求出,B,el,(B),Pl,(B),f,1,(B),Bel,(B,)=,AB,M(A),Pl,(B)=1-,Bel,(B,),f,1,(B)=,Bel,(B)+(|B,|,|U|)(,Pl,(B)-,Bel,(B,),证据理论示例,例一:,已知,f,1,(A,1,)=0.8,f,1,(A,2,)=0.6,|U|=20,A,1,A,2,B=b,1,b,2,(c,1,c,2,)=(0.3,0.5),求:,f,1,(B),例二:,已知,f,1,(A,1,)=0.53,f,1,(A,2,)=0.52,|U|=20,A,1,B=b,1,b,2,b,3,(c,1,c,2,c,3,)=(0.1,0.5,0,3),A,2,B=b,1,b,2,b,3,(c,1,c,2,c,3,)=(0.4,0.2,0,1),求:,f,1,(B),本章主要内容,基本概念,主观,Bayes,方法,确定性方法,证据理论,模糊推理,模糊推理,处理随机性的理论基础是概率论,处理模糊性的基础是模糊集合论,本节主要内容:,模糊集合与操作,语言变量,模糊推理,模糊集合与操作(1),经典集合是清晰的,即:,一个元素,x,是否属于某一个集合,A,是明确的,要么,x,属于,A,,,要么,x,不属于,A,,,两者必居其一,而且只能居其一。,C(x),为特征函数,模糊集合与操作(,2,),例子,:,Rule:,If the temperature is higher than 80F,it is hot;otherwise,it is not hot.,Cases:,Temperature=100F Hot,Temperature=80.1F Hot,Temperature=79.9F Not hot,Temperature=50F Not hot,情绪逻辑的不足,The membership function of crisp logic fails to distinguish between members of the same set.,模糊集合与操作(,3,),Conception of Fuzzy Logic,Many decision-making and problem-solving tasks are too complex to be defined precisely,however,people succeed by using imprecise knowledge,Fuzzy logic resembles human reasoning in its use of approximate information and uncertainty to generate decisions.,模糊集合与操作(,4,),Natural Language,Consider:,Joe is tall -what is tall?,Joe is very tall -what does this differ from tall?,Natural language(like most other activities in life and indeed the universe)is not easily translated into the absolute terms of 0 and 1.,“,false,”,“,true,”,模糊集合与操作(,5,),Fuzzy logic is a superset of,boolean,logic,It was created by Dr.,Lotfi,Zadeh,in 1960s for the purpose of modeling the uncertainty inherent in natural language,In fuzzy logic,it is possible to have partial truth values.,And is an approach to uncertainty that combines real values 01 and logic operations,Fuzzy logic is based on the ideas of fuzzy set theory and fuzzy set membership often found in natural(e.g.,spoken)language.,模糊集合与操作(,6,),模糊集合:把传统集合论中由特征函数决定的绝对隶属关系模糊化,把集合(,0,,,1,)扩散到区间,0,,,1,,以表示元素,x,隶属于子集,A,的模糊程度。,模糊集合与操作(,7,),Fuzzy Set,deals with degrees of membership and degrees of truth,it,is,a set with fuzzy boundaries.,In classical set theory;,f,A,(,x,):X,0,1,where,f,A,(,x,)=,In fuzzy sets;,A,(,x,):X,0,1,where,A,(,x,)=1,if,x,is totally in,A,;,A,(,x,)=0,if,x,is not in,A,;,0 ,A,(,x,)1.80,THEN select_for_team,In fuzzy rules;,IF height is,tall,THEN select_for_team,模糊推理(,2,),A fuzzy rule can have multiple antecedents.,IF height is tall,AND age is small,THEN select_for_team,Or,another example,IF service is excellent,OR food is delicious,THEN tip is generous,模糊推理(,3,),模糊推理过程,Crisp Input,Fuzzy Input,Fuzzy Output,Crisp Output,Fuzzification,Rule Evaluation,Defuzzification,Input Membership Functions,Rules/Inferences,Output Membership Functions,模糊推理(,4,),常用的隶属函数,:,模糊推理(,5,),模糊化,:,模糊化借助于输入模糊集合的隶属函数转变输入值为隶属度,即模糊化是根据模糊集合转变输入值为隶属度值的过程。,模糊估值,:,由于模糊控制规则的部分匹配特性和规则的前提条件相重叠的事实,通常在一个时刻可能有多于一条的模糊规则被激活,用来决定执行哪个控制规则的方法称为冲突消解过程。规则估值过程确定了每个规则被满足的程度。,常用的方法,:,MinMax,方法,Product,方法,BoundedSum,方法,模糊推理(,6,),清晰化,:,通过规则估值得到规则强度后,仍然需要进一步的处理,这个处理给出就是输出的清晰化。这一必须执行的过程,要生成非模糊化的控制动作,为了从截取后的输出模糊集中确定出一个清晰的值,必须首先合并这些输出模糊集。这是通过把所有的输出模糊连接起来,并且在所有的点上取大值来进行的。,常用方法,:,重心法,Truth Value Flow,模糊推理(,7,),Two Inputs(x,y)and one output(z),Membership functions:,low(t,)=1-(t/10),high(t,)=t/10,Low,High,1,0,t,X=0.32,Y=0.61,0.32,0.68,Low(x,)=0.68,High(x,)=0.32,Low(y,)=0.39,High(y,)=0.61,Crisp Inputs,模糊推理(,8,),规则库,:,Rule 1:If x is low AND y is low Then z is high,Rule 2:If x is low AND y is high Then z is low,Rule 3:If x is high AND y is low Then z is low,Rule 4:If x is high AND y is high Then z is high,模糊推理(,9,),推理,:,Rule1:,low(x,)=0.68,low(y,)=0.39=,high(z,)=MIN(0.68,0.39)=0.39,Rule2:,low(x,)=0.68,high(y,)=0.61=,low(z,)=MIN(0.68,0.61)=0.61,Rule3:,high(x,)=0.32,low(y,)=0.39=,low(z,)=MIN(0.32,0.39)=0.32,Rule4:,high(x,)=0.32,high(y,)=0.61=,high(z,)=MIN(0.32,0.61)=0.32,模糊推理(,10,),估值,:,Low(z,)=MAX(rule2,rule3)=MAX(0.61,0.32)=0.61,High(z,)=MAX(rule1,rule4)=MAX(0.39,0.32)=0.39,Low,High,1,0,t,0.61,0.39,模糊推理(,11,),清晰化,:,Center of Gravity,Low,High,1,0,0.61,0.39,Crisp output,Center of Gravity,模糊推理(,12,),清晰化,:,Center of Gravity,模糊推理(,13,),
展开阅读全文