人工智能ArtificialIntelligence第四章

1、人工智能人工智能Artificial IntelligenceArtificial Intelligence第四章第四章史忠植史忠植 中国科学院计算技术研究所http:/ Reasoning史忠植 人工智能：不确定性推理 12022-3-8史忠植 人工智能：不确定性推理 2内容提要内容提要4.1 4.1 概述概述4.2 4.2 可信度方法可信度方法4.3 4.3 主观贝叶斯方法主观贝叶斯方法4.4 4.4 证据理论证据理论4.5 4.5 模糊逻辑和模糊推理模糊逻辑和模糊推理4.6 4.6 小结小结2022-3-8基本概念基本概念 什么是不确定性推理?不确定性推理是建立在非经典逻辑上的一种推理,

2、是对不确定性知识的运用与处理是从不确定性的初始证据出发,通过运用不确定性的知识,最终推出具有一定程度的不确定性但却合理或者近乎合理的结论的思维过程 为什么要研究不确定性推理?日常生活中含有大量的不确定的信息ES系统中大量的领域知识和专家经验，不可避免的包含各种不确定性。史忠植 人工智能：不确定性推理 32022-3-8基本概念基本概念 不确定性推理的基本问题:表示问题:即采用什么方法描述不确定性.一般有数值表示和非数值的语义表示方法.计算问题:主要指不确定性的传播和更新,也即获得新信息的过程.主要包括: 已知C(A), AB f(B,A),如何计算C(B) 已知C1(A),又得到C2(A),如

3、何确定C(A) 如何由C(A1),C(A2)计算C(A1A2), C(A1A2) 语义问题: 指的是上述表示和计算的含义是什么,如何进行解释.史忠植 人工智能：不确定性推理 42022-3-8基本概念基本概念不确定推理方法的分类形式化方法:在推理一级扩展确定性方法.逻辑方法:是非数值方法,采用多值逻辑、非单调逻辑来处理不确定性新计算方法:认为概率方法不足以描述不确定性,出现了确定性理论,确定性因子,模糊逻辑方法等新概率方法:在传统的概率框架内,采用新的计算工具以确定不确定性描述非形式化方法:在控制一级上处理不确定性如制导回溯、启发式搜索等等史忠植 人工智能：不确定性推理 52022-3-8史忠

4、植 人工智能：不确定性推理 6内容提要内容提要4.1 4.1 概述概述4.2 4.2 可信度方法可信度方法4.3 4.3 主观贝叶斯方法主观贝叶斯方法4.4 4.4 证据理论证据理论4.5 4.5 模糊逻辑和模糊推理模糊逻辑和模糊推理4.6 4.6 小结小结2022-3-8知识的不确定性表示知识的不确定性表示 产生式规则： If E Then H (CF(H, E)CF(H,E)是该条知识的可信度，称为可信度因子或规则强度，表示当前提条件E所对应的证据为真时，它对结论H为真的支持程度。CF是根据经验对一个事物或现象为真的可信程度的度量CF(H,E)取值为：-1,1，史忠植 人工智能：不确定性推

5、理 72022-3-8知识的不确定性表示 CF定义： CF(H,E)=MB(H,E)-MD(H,E) MB:信任增长度，它表示因与前提条件E匹配的证据的出现，使结论H为真的信任增长度 MD：不信任增长度，它表示因与前提条件E匹配的证据的出现，对结论H的不信任增长度史忠植 人工智能：不确定性推理 82022-3-8知识的不确定性表示知识的不确定性表示 MB的定义：由条件概率和先验概率定义 1 若P（H）=1MB(H,E)= maxP(H|E), P(H) P( H - 否则 1-P(H) MD的定义： 1 若P（H）=0MD(H,E)= min P(H|E), P(H) P(H) - 否则 -P

6、(H)史忠植 人工智能：不确定性推理 92022-3-8知识的不确定性知识的不确定性表示表示 MB的定义：由条件概率和先验概率定义 1 若P（H）=1MB(H,E)= maxP(H|E), P(H) P(H) - 否则 1-P(H) MD的定义： 1 若P（H）=0MD(H,E)= min P(H|E), P(H) P(H) - 否则 -P(H)史忠植 人工智能：不确定性推理 102022-3-8知识的不确定性表示知识的不确定性表示 MB(H,E)和MD(H,E)是互斥的：即一个证据不能既增加对H的信任度，又不能同时增加对H的不信任度 当MB(H,E) 0 , MD(H,E)=0 当MD(H,

7、E) 0, MB(H,E)=0( | )( ), ) 0( | )( )1( )PH EPHM BH EH EPHPH （ 若 P( | )( )0, )( | )( )( )PH EPHM DH EH EPHPH（ 若 P( , )0(| )( )F H EH EP H 若P史忠植 人工智能：不确定性推理 112022-3-8知识的不确定性表示知识的不确定性表示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, CF2(H)=0CF(H)= C

8、F1(H)+CF2(H)+CF1(H) CF2(H) CF1(H)0, CF2(H)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) LS1时, 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) LN1时, O(H/E) O(H),E的不存在导致H为真的可能性下降，即E的不存在将反对H为真，说明E对H为真的必要性(4) LN=0时, O(H/E)=0,E

9、的不存在将使H为假。这里也可以看出E对H为真的必要性，所以也称LN为必要性度量史忠植 人工智能：不确定性推理 292022-3-8不确定性的传递算法不确定性的传递算法 从上面讨论知：(1)若E越是支持H为真时，则应使LS越大(2)若E对H越是必要时，则应使LN越小 LS、LN的取值情况：LS 0, LN 0 只能出现： 但不能出现： LS1 LS1, LN1 LS1, LN1 LS1, LN1 LS=LN=1史忠植 人工智能：不确定性推理 302022-3-8例一例一 设有如下知识：r1: if E1 then (10,1) H1 (0.03)r2: if E2 then (20,1) H2

10、(0.05)r3: if E3 then (1,0.002) H3 (0.3)求：当证据存在及不存在时，P(Hi/Ei)及 P(Hi/Ei) 的值各是多少史忠植 人工智能：不确定性推理 312022-3-8证据不确定证据不确定 证据不定时：0P(E/S)1,后验概率为： P(H/S)=P(H/E) P(E/S)+P(H/E) P(E/S) 分四种情况讨论如下：(1)P(E/S)=1 则有P(E/S)=0,证据肯定存在(2)P(E/S)=0 则有P(E/S)=1,证据肯定不存在(3)P(E/S)=P(E),说明E和S无关 P(H/S)=P(H)史忠植 人工智能：不确定性推理 322022-3-8

11、证据不确定证据不确定(4)当P(E/S)为其他值的时候，通过分段插值计算P(H/S)的值。0P(E/S)1P(E)P(H/E)P(H)P(H/E)P(H/S)史忠植 人工智能：不确定性推理 332022-3-8例二例二 当证据 E必然发生，H1的先验概率0.03, H2的先验概率0.01, 且有规则:r1: if E then (20,1) H1 r2: if H1 then (300, 0.0001) H2求：P(H2|E)史忠植 人工智能：不确定性推理 342022-3-8结论不确定性的合成结论不确定性的合成 若有n条知识都支持相同的结论，而且每条知识的前提所对应的证据Ei(i=1,n)都

12、有相应的观察Si与之对应，此时只要先对每条知识分别求出O(H/ Si)然后就可用下式求出结论不确定性的合成： O(H/ S1, ,Sn)= O(H/ S1) O(H/Sn) - - O(H) O(H) O(H)史忠植 人工智能：不确定性推理 352022-3-8例三例三当证据E1、E2、E3、E4必然发生后， H的先验概率为0.03,且有规则则:r1: if E1 then (20,1) Hr2: if E2 then (300,1) H求：结论H的概率变化化.史忠植 人工智能：不确定性推理 362022-3-8史忠植 人工智能：不确定性推理 37内容提要内容提要4.1 4.1 概述概述4.2

13、 4.2 可信度方法可信度方法4.3 4.3 主观贝叶斯方法主观贝叶斯方法4.4 4.4 证据理论证据理论4.5 4.5 模糊逻辑和模糊推理模糊逻辑和模糊推理4.6 4.6 小结小结2022-3-8证据理论证据理论n 证据理论（Theory of Evidence）也称为D-S (Dempster-Shafer)理论。证据理论最早基于德姆斯特（Dempster A P）所做的工作，他试图用一个概率范围而不是单个的概率值去模拟不确定性。谢弗（Shafer G A）进一步拓展了德姆斯特的工作，这一拓展称为证据推理Shafer 1976，用于处理不确定性、不精确以及间或不准确的信息。由于证据理论将概

14、率论中的单点赋值扩展为集合赋值，弱化了相应的公理系统，满足了比概率更弱的要求，因此可看作一种广义概率论。史忠植 人工智能：不确定性推理 382022-3-8证据理论证据理论 在D-S理论中，可以分别用信任函数、似然函数及类概率函数来描述知识的精确信任度、不可驳斥信任度及估计信任度，即可以从各个不同角度刻画命题的不确定性。 D-S理论采用集合来表示命题，为此，首先应该建立命题与集合之间的一一对应关系，把命题的不确定性问题转化为集合的不确定性问题。史忠植 人工智能：不确定性推理 392022-3-8概率分配函数概率分配函数 定义：U为样本空间，设函数M：2U0, 1，且满足： M() =0 AUM

15、(A)=1 则称M为2U上的概率分配函数，M(A)称为A的基本概率数(1)M(A)的作用是把U的任意一个子集A都映射为0,1上的一个数M(A)。它表示证据对U的子集A成立的一种信任度量，是对U的子集的信任分配。(2)概率分配函数不是概率。史忠植 人工智能：不确定性推理 402022-3-8证据理论证据理论例： U=红，黄，蓝假设： M(红)=0.3, M(黄)=0, M(蓝)=0.1, M(红,黄)=0.2, M(红,蓝)=0.2, M(黄,蓝)=0.1, M(红,黄,蓝)=0.1, M()=0史忠植 人工智能：不确定性推理 412022-3-8信任函数信任函数定义：命题的信任函数Bel: 2

16、U0, 1，且 Bel(A) = BAM(B) 对所有的AU(1)命题A的信任函数的值，是A的所有子集的基本概率分配函数值的和，用来表示对A的总的信任(2) Bel函数又称为下限函数(3) Bel() = M() =0 Bel(U) = BUM(B) = 1史忠植 人工智能：不确定性推理 422022-3-8似然函数似然函数定义：似然函数Pl: 2U0, 1，且 Pl(A) =1- Bel(A) 对所有的AU(1) Bel(A)表示对A为真的信任度，则 Bel(A)表示对A为真，即A为假的信任度，所以 Pl(A)表示A非假的信任度，它又称为上限函数。(2) Pl(A) =1- Bel(A) =

17、 ABM(B) (3) 0 Bel(A) Pl(A) 1(4) Pl(A) - Bel(A):表示既不信任A，也不信任A的一种度量，可表示对不知道的度量 史忠植 人工智能：不确定性推理 432022-3-8证据的不确定性度量证据的不确定性度量(1)以区间(Bel(A), Pl(A)作为证据A的不确定性度量：表示了对A信任程度的上限和下限。 A(0,0): 表示A为假 A(0,1): 表示对A一无所知 A(1,1): 表示A为真(2)以函数： f1(A)=Bel(A)+(|A| |U|) (Pl(A)-Bel(A)表示证据A的不确定性度量。 f1()=0， f1(U)=1 0 f1(A) 1 A

18、U史忠植 人工智能：不确定性推理 442022-3-8规则的规则的不确定性度量不确定性度量设U=u1, un,A和B为U的子集，如： A=a1, am, B=b1, bk规则表示如下： A B=b1, bk c1, ck (1)B是结论，用样本空间的子集表示，b1, bk是该子集中的元素(2) c1, ck表示规则的不确定性度量 ，ci表示bi的可信度(3) ci0， ni=1ci1史忠植 人工智能：不确定性推理 452022-3-8推理计算推理计算 f1(A1A2) = minf1(A1), f1(A2) f1(A1A2) = maxf1(A1), f1(A2) 已知f1(A) A B =b

19、1, bk c1, ck， 求 f1(B) (1)求出B的概率分配函数 M(B)=M(b1, bk)=f1(A) c1, f1(A) ck M(U)=1 - ki=1 f1(A) ci 史忠植 人工智能：不确定性推理 462022-3-8推理计算推理计算如果有两条知识支持同一条结论： A1 B =b1, bk c1, ck， A2 B =b1, bk c1, ck，则首先分别对每一条知识求出概率分配函数： M1(b1, bk) M2(b1, bk)然后由：M=M1M2求出结论B的概率分配函数M史忠植 人工智能：不确定性推理 472022-3-8推理计算推理计算概率分配函数的合成定义：设M1和M

20、2是两个概率分配函数，则合成M=M1M2定义为： M() =0 M(A) =K XY=A M1(X) M2(Y) 其中x,y是U的子集，并且： K-1=1- XY= M1(X) M2(Y) = XY M1(X) M2(Y)史忠植 人工智能：不确定性推理 482022-3-8推理计算推理计算概率分配函数的合成示例：例一：设U=黑，白，且 M1(黑,白,黑,白,)=(0.3, 0.5, 0.2, 0) M2(黑,白,黑,白,)=(0.6, 0.3, 0.1, 0)例二：设U=a,b,c,d M1(b,c,d,U)=(0.7, 0.3) M2(a,b,U)=(0.6, 0.4) 史忠植 人工智能：不

21、确定性推理 492022-3-8推理计算 求出Bel(B) ,Pl(B),f1(B) Bel(B) = ABM(A) Pl(B) =1- Bel(B) f1(B)=Bel(B)+(|B| |U|) (Pl(B)-Bel(B)史忠植 人工智能：不确定性推理 502022-3-8证据理论示例证据理论示例例一：已知 f1(A1)=0.8, f1(A2)=0.6, |U|=20 A1A2B=b1,b2 (c1,c2)=(0.3,0.5)求：f1(B)例二：已知 f1(A1)=0.53, f1(A2)=0.52, |U|=20 A1B=b1,b2 ,b3 (c1,c2 ,c3)=(0.1,0.5,0,3

22、) A2B=b1,b2 ,b3 (c1,c2 ,c3)=(0.4,0.2,0,1)求：f1(B)史忠植 人工智能：不确定性推理 512022-3-8史忠植 人工智能：不确定性推理 52内容提要内容提要4.1 4.1 概述概述4.2 4.2 可信度方法可信度方法4.3 4.3 主观贝叶斯方法主观贝叶斯方法4.4 4.4 证据理论证据理论4.5 4.5 模糊逻辑和模糊推理模糊逻辑和模糊推理4.6 4.6 小结小结2022-3-8模糊推理模糊推理 处理随机性的理论基础是概率论 处理模糊性的基础是模糊集合论 本节主要内容：模糊集合与操作语言变量模糊推理史忠植 人工智能：不确定性推理 532022-3-

23、8模糊集合与操作模糊集合与操作 经典集合是清晰的，即： 一个元素x是否属于某一个集合A是明确的，要么x属于A，要么x不属于A，两者必居其一，而且只能居其一。 C(x)为特征函数 AxAxxC 0 1)(史忠植 人工智能：不确定性推理 542022-3-8n 模糊集合模糊集合定义1设是一个论域,到区间0, 1的一个映射 : 0，1就确定了的一个模糊子集。映射称为A的隶属函数, 记为A(u)。对于任意的u, A(u)0, 1称为u属于模糊子集A的程度, 简称隶属度。 模糊集合与操作模糊集合与操作史忠植 人工智能：不确定性推理 552022-3-8由定义, 模糊集合完全由其隶属函数确定, 即一个模糊

24、集合与其隶属函数是等价的。 可以看出, 对于模糊集,当中的元素u的隶属度全为0时, 则就是个空集；反之,当全为1时,就是全集；当仅取0和1时, 就是普通子集。 这就是说,模糊子集实际是普通子集的推广, 而普通子集就是模糊子集的特例。 论域上的模糊集合, 一般可记为,/ )(,/ )(,/ )(332211uuuuuuAAAA模糊集合与操作模糊集合与操作史忠植 人工智能：不确定性推理 562022-3-8或 332211/ )(/ )(/ )(uuuuuuAAAA或 UuAuuA/ )(或 ),(,(),(),(,(332211uuuuuuAAAA对于有限论域, 甚至也可表示成 )(,),(),

25、(),(321nAAAAuuuuA模糊集合与操作模糊集合与操作史忠植 人工智能：不确定性推理 572022-3-8n 通常所说的“高个”、“矮个”、“中等个”就是三个关于身高的语言值。我们用模糊集合为它们建模。 取人类的身高范围1.0, 3.0为论域U, 在U上定义隶属函数矮(x)、中等(x)、高(x)如下(函数图像如图8-5所示)。 这三个隶属函数就确定了U上的三个模糊集合,它们也就是相应三个语言值的数学模型。 015. 065. 11)(xx矮0 . 365. 165. 150. 150. 10 . 1xxx模糊集合例子模糊集合例子史忠植 人工智能：不确定性推理 582022-3-8005

26、.08.1115.05.10)(xxx中等0.380.10.31xxxxx105.075.10)(xx高0 .375.10 .1xxx模糊集合例子模糊集合例子史忠植 人工智能：不确定性推理 592022-3-8身高论域上的模糊集“矮”、 “中等”、 “高”的隶属函数 模糊集合例子模糊集合例子史忠植 人工智能：不确定性推理 602022-3-8n 除了有些性质概念是模糊概念外，还存在不少模糊的关系概念。如“远大于”、“基本相同”、“好朋友”等就是一些模糊关系。模糊关系也可以用模糊集合表示。下面我们就用模糊子集定义模糊关系。

27、n 定义定义 集合U1，U2，Un的笛卡尔积集U1U2Un的一个模糊子集 ，称为U1，U2，Un间的一个n元模糊关系。特别地，Un的一个模糊子集称为U上的一个n元模糊关系。模糊关系模糊关系史忠植 人工智能：不确定性推理 612022-3-8n 普通集合一样, 也可定义模糊集合的交、并、补运算。 n 定义定义设A、B是X的模糊子集, A、B的交集AB、并集AB和补集A, 分别由下面的隶属函数确定： )(1)()(),(max()()(),(min()(xxxxxxxxAABABABABA模糊集合的运算模糊集合的运算史忠植 人工智能：不确定性推理 622022-3-8语言变量语言变量 模糊集合的一

28、种应用是计算语言学，目的是对自然语言的语句进行计算，就象对逻辑语句进行运算一样。 语言变量可以看作是用某种自然语言和人工语言的词语或句子来表示变量的值和描述变量间的内在联系的一种系统化的方法 模糊集合和语言变量可用于量化自然语言的含义，因而可用来处理具有指定值的语言变量。 Fuzzy logic=computing with words 史忠植 人工智能：不确定性推理 632022-3-8模糊逻辑是研究模糊命题的逻辑。 设n元谓词 ),(21nxxxP表示一个模糊命题。定义这个模糊命题的真值为其中对象x1, x2, , xn对模糊集合P的隶属度, 即 ),(),(2121nPnxxxxxxPT

29、此式把模糊命题的真值定义为一个区间0, 1中的一个实数。 那么,当一个命题的真值为0时, 它就是假命题；为1时,它就是真命题；为0和1之间的某个值时, 它就是有某种程度的真(又有某种程度的假)的模糊命题。 模糊逻辑模糊逻辑史忠植 人工智能：不确定性推理 642022-3-8在上述真值定义的基础上, 我们再定义三种逻辑运算： (PQ)min(P),(Q) (PQ)max(P),(Q) (P)1-(P) 其中P和Q都是模糊命题。 这三种逻辑运算称为模糊逻辑运算。由这三种模糊逻辑运算所建立的逻辑系统就是所谓的模糊逻辑。 可以看出, 模糊逻辑是传统二值逻辑的一种推广。 模糊逻辑模糊逻辑史忠植 人工智能

30、：不确定性推理 652022-3-8n 模糊推理是基于不确切性知识(模糊规则)的一种推理。 例如 如果x小, 那么 y大。 x较小 y? 就是模糊推理所要解决的问题。n模糊推理是一种近似推理, 一般采用Zadeh提出的语言变量、 语言值、模糊集和模糊关系合成的方法进行推理。 模糊推理模糊推理史忠植 人工智能：不确定性推理 662022-3-81965年，Zadeh 提出模糊集合的概念, 1974 年他又将模糊集引入推理领域开创了模糊推理技术以来, 模糊推理就成为一种重要的近似推理方法。特别是 20 世纪 90 年代初, 日本率先将模糊控制用于家用电器并取得成功, 引起了全世界的巨大反响和关注。

31、之后, 欧美各国都竞相在这一领域展开角逐。模糊技术已向自动化、计算机、 人工智能等领域全面推进，出现模糊推理机、 模糊控制器、 模糊芯片、模糊计算机等, 模糊逻辑、模糊语言、 模糊数据库、模糊知识库、模糊专家系统、模糊神经网络等新概念层出不穷。模糊推理模糊推理史忠植 人工智能：不确定性推理 672022-3-8n Zadeh给出的模糊推理方法, 一般称为模糊推理的CRI (Compositional Rule of Inference)法。 CRI法的关键有两步:一步是由模糊规则导出模糊关系矩阵R, 一步是模糊关系的合成运算。在第一步中, Zadeh给出的求R的公式,其依据是把模糊规则AB作为明晰规则AB的推广,并且利用逻辑等价式 ABAB(AB)(AA) ABA 再运用他给出的模糊集合的交、并、补运算而得出来的。但仔细分析,不难看出, 这样做是存在问题的。因为,规则前提模糊集与结论模糊集元素之间的关系应该是函数关系,而不是逻辑关系, 但这里是用逻辑关系来处理函数关系的。 模糊推理模糊推理史忠植 人工智能：不确定性推理 682022-3-8模糊推理模糊推理 模糊化:模糊化借助于输