人工智能第4章 不确定与非单调推理

1、人工智能Artificial Intelligence,主讲：杨利英 西安电子科技大学 E_mail：,第五章不确定与非单调推理,4.1 基本概念 4.2 概率方法 4.3 主观Bayes方法 4.4 可信度方法 4.5 证据理论 4.6 模糊推理 4.7 非单调推理,4.1 基本概念,4.1.1 不确定性推理 不确定性推理是建立在非经典逻辑基础上的一种推理，它是对不确定性知识的运用与处理。 不确定性推理就是从不确定性的初始证据（即事实）出发，通过运用不确定性的知识，最终推出具有一定程度不确定性的结论。,1. 不确定性的表示与度量 2. 不确定性匹配算法及阈值的选择 3. 组合证据不确定性的计

2、算方法 4. 不确定性的传递算法 5. 结论不确定性的合成,4.1.2 不确定性推理中的基本问题,4.1.2 不确定性推理中的基本问题,1. 不确定性的表示与度量 不确定性推理中的“不确定性”一般分为两类：一是知识的不确定性，一是证据的不确定性。 知识不确定性的表示：目前在专家系统中知识的不确定性一般是由领域专家给出的，通常用一个数值表示，它表示相应知识的不确定性程度，称为知识的静态强度。 证据不确定性的表示：证据不确定性的表示方法与知识不确定性的表示方法一致，通常也用一个数值表示，代表相应证据的不确定性程度，称之为动态强度。,4.1.2 不确定性推理中的基本问题,2. 不确定性匹配算法及阈值

3、的选择 设计一个不确定性匹配算法：用来计算匹配双方相似程度。 指定一个匹配阈值。,4.1.2 不确定性推理中的基本问题,3. 组合证据不确定性的计算方法 最大最小法： T(E1 AND E2)=minT(E1),T(E2) T(E1 OR E2)=maxT(E1),T(E2) 概率法： T(E1 AND E2)=T(E1)T(E2) T(E1 OR E2)=T(E1)T(E2)T(E1)T(E2) 有界法： T(E1 AND E2)=max0,T(E1)T(E2)1 T(E1 OR E2)=min1,T(E1)T(E2) 其中，T(E)表示证据E为真的程度（动态强度），如可信度、概率等。,4.

4、1.2 不确定性推理中的基本问题,4. 不确定性的传递算法 在每一步推理中，如何把证据及知识的不确定性传递给结论，即如何计算结论的不确定性。,4.1.2 不确定性推理中的基本问题,5. 结论不确定性的合成 用不同知识进行推理得到了相同结论，但所得结论的不确定性却不同。此时，需要用合适的算法对结论的不确定性进行合成。,4.1.3 不确定性推理方法的分类,不确定性推理方法主要可分为模型法与控制法。 模型法：在推理一级对确定性推理进行扩展，引入证据的不确定性及知识的不确定性。 模型方法又分为数值方法和非数值方法两类。数值方法对不确定性进行定量的描述，按其所依据的理论又可分为基于概率的方法(概率方法、

5、主观Bayes方法、可信度方法、证据理论)和基于模糊理论的方法（模糊推理）。,4.2 概率方法,4.2.1 经典概率方法 （1）设有如下产生式规则： IFE THEN H 其中，E为前提条件，H为结论。条件概率P(H|E) 可以作为在证据E出现时结论H的确定性程度，即规则的 静态强度。 （2）对于复合条件 E=E1 AND E2 AND AND En 当已知条件概率P(H|E1,E2,En)时，就可把它作为在证据E1,E2,En出现时结论H的确定性程度。 （3）先验概率： P(H) 后验概率： P(H|E),若A1,A2,An是彼此独立的事件，对于事件B，则有 其中，P(Ai)是事件Ai的先验

6、概率；P(B|Ai)是在事件Ai发生条件下事件B的条件概率。 对于一组产生式规则 IFETHENHi 同样有后验概率如下（ Hi 确定性的程度，或规则的静态强度）：,4.2.2 逆概率方法,对于多个证据,逆概率方法举例,例 设H1,H2,H3分别是三个结论，E是支持这些结论的证据。已知： P(H1)=0.3, P(H2)=0.4, P(H3)=0.5 P(E|H1)=0.5, P(E|H2)=0.3, P(E|H3)=0.4 求P(H1|E),P(H2|E)及P(H3|E)的值各是多少？ 解： 同理可得： P(H2|E)=0.26, P(H3|E)=0.43,对应的产生式规则： IFETHEN

7、H1 IFETHENH2 IFETHENH3 规则的静态强度(Hi为真的程度、或不确定性程度) P(H1|E)=0.32 P(H2|E)=0.26 P(H3|E)=0.43,逆概率法的特点,优点： 逆概率法有较强的理论背景和良好的数学特性，当证据彼此独立时计算的复杂度比较低。 缺点： 逆概率法要求给出结论Hi的先验概率P(Hi)及条件概率P(Ej|Hi)。,4.3 主观Bayes方法,4.3.1 知识不确定性的表示 在主观Bayes方法中，知识是用产生式规则表示的，具体形式为： IFE THEN (LS,LN) H (P(H) 其中， P(H)是结论H的先验概率，由专家根据经验给出。 LS称为

8、充分性度量，用于指出E对H的支持程度，取值范围为0,)，其定义为： LS=P(E|H)/P(E|H)。 LN称为必要性度量，用于指出 E对H的支持程度，取值范围为0,)，其定义为： LN=P(E|H)/P(E|H)=(1-P(E|H)/(1-P(E|H)。 LS和LN的值由领域专家给出，相当于知识的静态强度。,4.3.2 证据不确定性的表示,主观Bayes方法中，证据的不确定性也用概率表示。对于证据E，由用户根据观察S给出P(E|S)，即动态强度。用P(E|S)描述证据的不确定性 （证据E不是可以直接观测的）。 由于主观给定P(E|S)有所困难，所以实际中可以用可信度C(E|S)代替P(E|S

9、)。 在探矿专家系统PROSPECTOR中C(E|S)取整数：-5，.5 C(E|S)=-5表示在观测S下证据E肯定不存在P(E|S)=0 C(E|S)= 5表示在观测S下证据E肯定存在P(E|S)=1 C(E|S)= 0表示S与E无关,即P(E|S)= P(E),给定C(E|S)后，P(E|S)可近似计算如下（分段线性插值）：,采用主观Bayes方法 IF E THEN (LS,LN) H (P(H) 时要解决的主要问题： （1）证据肯定存在时，如何计算P(H|E)？ 此时P(E|S)=1。 （2）证据肯定不存在时，如何计算P(H| E)？ 此时P(E|S)=0。 （3）证据具有不确定性时，

10、如何计算P(H|S)？ 此时0P(E|S)1。,4.3.3 组合证据不确定性的算法,（1）最大最小法 当组合证据是多个单一证据的合取时，即 E=E1 AND E2 AND AND En 则：P(E|S)=minP(E1|S),P(E2|S),P(En|S) 当组合证据是多个单一证据的析取时，即 E=E1 OR E2 OR OR En 则：P(E|S)=maxP(E1|S),P(E2|S),P(En|S) （2）对于“”运算：P(E|S)=1-P(E|S),4.3.4 不确定性的传递算法,（1）根据证据E的条件概率P(E|S) 及LS、LN的值，把H的先验概率P(H)更新为后验概率P(H|E)

11、。 （2） 分以下3种情况讨论： 证据肯定存在： P(E|S)=1，即P(E)=1 证据肯定不存在： P(E|S)=0，即P(E)=0 证据不确定： 0P(E|S)1 （3）引入几率函数(x),它与概率的关系为： (x)=P(x)/(1-P(x),P(x)=(x)/(1+(x) 可以看出，概率函数与几率函数具有相同的单调性。,证据肯定存在时,(x)=P(x)/(1-P(x),P(x)=(x)/(1+(x) 在证据肯定存在时，P(E)=P(E|S)=1。 由Bayes公式得： P(H|E)=P(E|H)P(H)/P(E)(1) P(H|E)=P(E|H)P(H)/P(E)(2) (1)式除以(2

12、)式得： P(H|E)/P(H|E)=P(E|H)/P(E|H)P(H)/P(H) 由充分性度量LS和几率函数的定义可得： (H|E)=LS(H) 即 P(H|E)=LSP(H)/(LS-1)P(H)+1,充分性度量LS的意义,对于知识： IF E THEN (LS,LN) H (P(H) 在证据E肯定存在时，可以根据LS给出结论H的可信度P(H|E)。 当LS1时，(H|E)=LS(H)(H)，相应有P(H|E)P(H)，表明由于证据E的存在，可增强H为真的程度（有利证据）。一般情况下LS1。 当LS1时，(H|E)=LS(H)(H)，表明E与H无关（无关证据）。 当LS1时，(H|E)=L

13、S(H)(H)，表明由于证据E的存在，减小了H为真的程度（不利证据）。 当LS0时，(H|E)=LS(H)0，表明由于证据E的存在，导致H为假（否定性的证据）。,证据肯定不存在时,在证据肯定不存在时，P(E)=P(E|S)=0， P(E)=1。 由Bayes公式得： P(H|E)=P(E|H)P(H)/P(E)(1) P(H|E)=P(E|H)P(H)/P(E)(2) (1)式除以(2)式得： P(H|E)/P(H|E)=P(E|H)/P(E|H)P(H)/P(H) 根据必要性度量LN和几率函数的定义，可得： (H|E)=LN(H) 即 P(H|E)=LNP(H)/(LN-1)P(H)+1,必

14、要性度量LN的意义,对于知识： IF E THEN (LS,LN) H (P(H) 在证据E肯定不存在时，可以根据LN给出结论H的可信度P(H|E) 。 当LN1时，(H|E)=LN(H)(H)，相应有P(H|E)P(H)，表明由于证据E不存在，增强了H为真的程度（ E 为有利证据）。,对LS 和 LN 的说明,LS1: 表明证据 E是对H有利的证据。 LN1：表明证据E是对H有利的证据。 所以： 不能出现LS1且LN1的取值。 LS1， LN1。,证据不确定时,当0P(E|S)1时，可以证明（Duda等人于1976年证明）: P(H|S)=P(H|E)P(E|S)+P(H|E)P(E|S)

15、当P(E|S)=1时，证据肯定存在，此时P(H|S)=P(H|E) 。 当P(E|S)=0时，证据肯定不存在，此时P(H|S)=P(H| E) 。 当P(E|S)=P(E)时，证据E与观察S无关。由全概率公式得： P(H|S)=P(H|E)P(E)+P(H|E)P(E)P(H) 当P(E|S)为其它值时，通过分段线性插值计算P(H|S)，即,对于知识： IF E THEN (LS,LN) H (P(H) 给定证据E的不确定性度量P(E|S)，则结论的可信度可以表示为： 该公式称为EH公式。用C(E/S) 代替P(E/S)，可得到等价的CP公式。,对于初始证据，由于其不确定性是用可信度C(E/S

16、) 给出的，此时只要把EH公式中的P(E/S)转换为C(E/S) ，就得到用可信度C(E/S) 计算P(H/S)的CP公式：,4.3.5 结论不确定性的合成算法,若有n条知识都支持相同的结论，而且每条知识的前提条件所对应的证据Ei(i=1,2,n)都有相应的观察Si与之对应，此时只要先对每条知识分别求出几率函数(H|Si)，然后就可运用下述公式求出(H|S1S2Sn):,主观Bayes方法推理示例,例 (王永庆教材 P169) 设有如下知识： R1:IF E1THEN(2, 0.001) H1 R2:IF E2THEN(100, 0.001) H1 R3:IF H1THEN(200, 0.01

17、 ) H2 已知：(H1)0.1， (H2)0.01 C(E1|S1)=2, C(E2|S2)=1 求： (H2|S1S2)=? 1. 计算(H1|S1) P(H1)=(H1)/(1+(H1)=0.09 P(H1|E1)=(H1|E1)/(1+(H1|E1)= LS1(H1)/(1+LS1(H1)=0.17 C(E1|S1)=20 P(H1|S1)=P(H1)+P(H1|E1)-P(H1)1/5C(E1|S1) =0.122 (H1|S1)=P(H1|S1)/(1- P(H1|S1)=0.14,R1:IF E1THEN(2, 0.001) H1 R2:IF E2THEN(100, 0.001)

18、 H1 R3:IF H1THEN(200, 0.01 ) H2 2. 计算(H1|S2) P(H1|E2)=(H1|E2)/(1+(H1|E2)= LS2(H1)/(1+LS2(H1)=0.91 C(E2|S2)=10 P(H1|S2)=P(H1)+P(H1|E2)-P(H1)1/5C(E2|S2) =0.254 (H1|S2)=P(H1|S2)/(1- P(H1|S2)=0.34,R1:IF E1THEN(2, 0.001) H1 R2:IF E2THEN(100, 0.001) H1 R3:IF H1THEN(200, 0.01 ) H2 3. 计算(H1|S1S2) (H1|S1S2)=

19、(H1|S1)/(H1)(H1|S2)/(H1)(H1) =0.476 4. 计算(H2|S1S2) (H1|S1S2)=0.476(H1)=0.1 P(H2|S1S2)=P(H2)+ P(H2|H1)-P(H2) /1-P(H1) P(H1|S1S2)-P(H1)=0.175 (H2|S1S2)=P(H2|S1S2)/(1- P(H2|S1S2)=0.212,优点： 主观Bayes方法中的计算公式大多是在概率论的基础上推导出来的，具有较坚实的理论基础。 知识的静态强度LS及LN是由领域专家给出，避免了大量的数据统计工作。 主观Bayes方法不仅给出了证据肯定存在、肯定不存在时更新后验概率的方

20、法，还给出了证据不确定时的更新方法，实现了不确定性的逐级传递。,主观Bayes方法的特点,主观Bayes方法的特点,缺点： 它要求领域专家在给出知识时，同时给出H的先验概率P(H)，这比较困难。 Bayes定理要求事件间独立，使其应用受限制。,4.4 可信度方法,4.4.1 可信度的概念 根据经验对一个事物和现象为真的相信程度称为可信度。 在可信度方法中，由专家给出规则或知识的可信度，从而可避免对先验概率、条件概率的要求。 可信度方法首先在专家系统MYCIN中得到了成功的应用。,4.4.2 C-F模型,C-F模型是基于可信度表示的不确定推理的基本方法。 1、C-F模型中知识不确定性的表示 知识

21、是用产生式规则表示的，其一般形式为： IFETHENH(CF(H,E) 其中，CF(H,E)是该知识的可信度，称为可信度因子或规则强度，即静态强度。一般情况下，CF(H,E)-1,1。 CF(H,E)0对应于P(H|E)P(H); CF(H,E)0对应于P(H|E)P(H); CF(H,E)=0对应于P(H|E)=P(H)。,可信度因子的定义,IFETHENH(CF(H,E) CF(H,E)定义为： CF(H,E)=MB(H,E)-MD(H,E) MB反映了证据对结论有利的一面，MD反映了证据对结论不利的一面。MB(Measure Belief)称为信任增长度。MD(Measure Disbe

22、lief)称为不信任增长度。 MB和MD的定义如下：,当P(H|E)P(H)时： 信任增长度MB(H,E)0， 不信任增长度MD(H,E)=0 。 当P(H|E)0， 信任增长度MB(H,E) =0。 MB(H,E)与MD(H,E)是互斥的： 当MB(H,E)0时，MD(H,E)0 当MD(H,E)0时，MB(H,E)0,CF(H,E)的计算公式,根据定义CF(H,E)=MB(H,E)-MD(H,E)，及 MB(H,E)与MD(H,E)的互斥性，可得: 从上式可看出： CF(H,E)0对应于P(H|E)P(H); CF(H,E)0对应于P(H|E)P(H); CF(H,E)=0对应于P(H|E

23、)=P(H)。,IFETHENH(CF(H,E) 当且仅当P(H|E)=1时, CF(H,E)=1 当且仅当P(H|E)=0时, CF(H,E)=-1 CF(H,E)定性地反映了P(H|E)的大小,因此可以用CF(H,E)近似表示P(H|E)的大小,从而描述了规则的可信度。,2. C-F模型中证据不确定性的表示 证据的不确定性也用可信度因子表示。如 CF(E)=0.6 CF(E)的取值范围：-1，+1。 CF(E)0:表示证据以某种程度为真。 CF(E)0:表示证据以某种程度为假。 CF(E)表示证据的强度，即动态强度。,3. C-F模型中组合证据不确定性的算法,可采用最大最小法。 若 E=E

24、1 AND E2 ANDAND En, 则 CF(E)=minCF(E1),CF(E2),CF(En) 若 E=E1 OR E2 OROR En, 则 CF(E)=maxCF(E1),CF(E2),CF(En),4. 不确定性的传递算法,IFETHENH(CF(H,E) 结论H的可信度由下式计算：CF(H)=CF(H,E)max0,CF(E) 可以看出： (1)若证据为假，即CF(E)0时,有 CF(H)=0，说明该模型没有考虑证据为假时对结论产生的影响。 (2) 若证据为真，即CF(E)1时，有CF(H)=CF(H,E)，说明知识中的规则强度CF(H,E)实际上就是在前提条件对应的证据为真时

25、结论H的可信度。,5. 结论不确定性的合成算法 若由多条不同知识推出了相同的结论，但可信度不同，则用合成算法求出综合可信度。 设有如下知识： IFE1THENH(CF(H,E1) IFE2THENH(CF(H,E2) 则结论H的综合可信度分如下两步算出： 首先分别对每一条知识求出CF(H): 计算CF1(H)、CF2(H) 然后用下述公式求出E1与E2对H的综合可信度CF12(H):,C-F模型推理示例,例 (王永庆教材 P175) 设有如下一组知识： R1: IFE1THENH(0.8) R2: IFE2THENH(0.6) R3: IFE3THENH(-0.5) R4: IFE4 AND

26、(E5 OR E6)THENE1(0.7) R5: IFE7 AND E8 THENE3(0.9) 已知：CF(E2)=0.8, CF(E4)=0.5, CF(E5)=0.6 CF(E6)=0.7, CF(E7)=0.6, CF(E8)=0.9 求：CF(H)=？ 解：由R4得到： CF(E1)=0.7max0,CFE4 AND (E5 OR E6) =0.7max0,minCF(E4),CF(E5 OR E6) =0.35 由R5得到： CF(E3)=0.9max0,CFE7 AND E8 =0.54,R1: IFE1THENH(0.8) R2: IFE2THENH(0.6) R3: IFE

27、3THENH(-0.5) 由R1得到： CF1(H)=0.8max0,CF(E1)=0.28 由R2得到： CF2(H)=0.6max0,CF(E2)=0.48 由R3得到： CF3(H)=-0.5max0,CF(E3)=-0.27 根据结论不确定性的合成算法： CF12(H)=CF1(H)+CF2(H)-CF1(H)CF2(H)=0.63 CF123(H)=CF12(H)+CF3(H)/1-min|CF12(H)|,|CF3(H)| =0.49 即最终的综合可信度为CF(H)=0.49。,IFETHEN H(CF(H,E) C-F模型的核心问题是三个可信度： (1) 知识的可信度CF(H,E

28、)：取值范围-1，1 CF(H,E)=1 对应于 P(H|E)=1 (证据绝对支持结论) CF(H,E)=-1 对应于 P(H|E)=0 (证据绝对否定结论) CF(H,E)=0 对应于 P(H|E)=P(H) (证据与结论无关) (2) 证据的可信度CF(E)：取值范围-1，1 CF(E)=1 对应于 P(E)=1 (证据绝对存在) ; CF(E)=-1 对应于 P(E)=0; (证据绝对不存在) CF(E)=0 对应于 P(E)=0.5 (对证据一无所知)。 (3) 结论的可信度CF(H)：取值范围-1，1 CF(H)=CF(H,E)max0,CF(E) 该公式隐含了一个知识运用的条件,

29、即CF(E)0。,4.4.3 带有阈值限度的不确定性推理,1. 知识不确定性的表示 知识用下述形式表示： IFETHENH(CF(H,E),) 其中： E为知识的前提条件，可以是简单条件，也可以是复合条件。 CF(H,E)为知识的可信度，取值范围为（0,1， CF(H,E) 的值越大，表示相应知识的可信度越高。 是阈值，明确规定了知识运用的条件：只有当CF(E)时，该知识才能够被应用。的取值范围为(0,1。,IFETHENH(CF(H,E),) 2. 证据不确定性的表示 证据E的可信度仍为CF(E)，其取值范围为：0，1 CF(E)=1 对应于 P(E)=1 (证据绝对存在) ; CF(E)=

30、0 对应于 P(E)=0; (证据绝对不存在) 3.组合证据不确定性的算法 取大取小原则 4. 不确定性的传递算法 当CF(E)时，CF(H)=CF(H,E)CF(E),5. 结论不确定性的合成算法 设有多条规则有相同的结论，即 IFE1THEN H(CF(H,E1),1) IFE2THEN H(CF(H,E2),2) IFEnTHEN H(CF(H,En),n) 如果这n条规则都满足：CF(Ei)i，i=1,2,n 且都被启用，则首先分别对每条知识求出它对CFi(H)； 然后求结论H的综合可信度CF(H)。,求综合可信度的几种方法,极大值法： CF(H)=maxCF1(H),CF2(H),C

31、Fn(H) 加权求和法： 有限和法： 递推法： C1=CF(H,E1)CF(E1) Ck=Ck-1+(1-Ck-1)CF(H,Ek)CF(Ek),4.4.4 加权的不确定性推理,1. 知识不确定性的表示 IFE1(1) AND E2(2) ANDAND En(n) THEN H (CF(H,E),) 其中i(i=1,2,n)是加权因子，是阈值，其值均由专家给出。 加权因子的取值范围一般为0,1,且应满足归一条件，即,4.4.4 加权的不确定性推理,2. 组合证据不确定性的算法 若有CF(E1)，CF(E2)，CF( En)，则组合证据的可信度为：,3. 不确定性的传递算法 当一条知识的CF(E

32、)满足如下条件时， CF(E) 该知识就可被应用。结论H的可信度为： CF(H)=CF(H,E)CF(E) 加权因子的引入不仅可以区分不同证据的重要性，同时还可以解决证据不全时的推理问题。,加权不确定性推理举例(1),例（王永庆教材 P181） 设有如下知识： R1: IF E1(0.6) AND E2(0.4) THEN E6(0.8,0.75) R2: IF E3(0.5) AND E4(0.3) AND E5(0.2) THEN E7(0.7,0.6) R3: IF E6(0.7) AND E7(0.3) THEN H(0.75,0.6) 已知：CF(E1)=0.9, CF(E2)=0.

33、8, CF(E3)=0.7, CF(E4)=0.6, CF(E5)=0.5 求：CF(H)=? 解：由R1得到： CF(E1(0.6) AND E2(0.4)=0.861=0.75 R1可被应用。,加权不确定性推理举例(2),由R2得到： CF(E3(0.5) AND E4(0.3) AND E5(0.2)0.632 =0.6 R2可被应用。 0.860.63 R1先被应用。 由R1得到：CF(E6)=0.69 由R2得到：CF(E7)=0.44 由R3得到： CF(E6(0.7) AND E7(0.3)=0.6153 =0.6 R3可被应用,得到： CF(H)=0.46 即最终得到的结论H可

34、信度为0.46,4.4.5 前提条件中带有可信度因子的不确定推理,1. 知识不确定性的表示 IFE1(cf1) AND E2(cf2) ANDAND En(cfn) THEN H (CF(H,E),) 其中，cfi子条件Ei(i=1,2,n）的可信度。cfi在0,1上取值，其 值由专家给出。 核心思想：知识的前提条件不一定为真，只要前提条件满足一 定的可信度，或具备一定的为真的可能性，就可以推出结论H。 加入加权因子后得到： IFE1(cf1,1) AND E2(cf2,2) ANDAND En(cfn,n) THEN H (CF(H,E),) 2. 证据不确定性的表示 证据Ei的可信度记为c

35、fi,其取值范围在0,1上。,3. 不确定性匹配算法 不带加权因子的不确定性匹配算法： 知识：IFE1(cf1) AND E2(cf2) ANDAND En(cfn) THEN H (CF(H,E),) 条件：E1(cf1)，E2(cf2)， En(cfn) 匹配算法： max0,cf1-cf1+max0,cf2-cf2+ max0,cfn-cfn 带加权因子的不确定性匹配算法： 知识：IFE1(cf1,1) AND E2(cf2,2) ANDAND En(cfn,n) THEN H (CF(H,E),) 匹配算法： (1max0,cf1-cf1)+(2max0,cf2-cf2)+(nmax0

36、,cfn-cfn) ,4. 不确定性的传递算法,不带加权因子时： CF(H)=(1-max0,cf1-cf1)(1-max0,cf2-cf2)(1-max0,cfn-cfn)CF(H,E) 带加权因子时： CF(H)=(1(1-max0,cf1-f1)(2(1-max0,cf2-cf2)(n(1-max0,cfn-cfn)CF(H,E),基于可信度的不确定性推理方法的特点,优点： 简单、直观。 缺点： 可信度因子依赖于专家主观指定，没有统一、客观的尺度，容易产生片面性。 随着推理延伸，可信度越来越不可靠，误差越来越大。当推理深度达到一定深度时，有可能出现推出的结论不再可信的情况。,4.5 证据

37、理论,证据理论是A.P.Dempster于1967年研究统计问题时首先提出的，他给出了上、下限概率的概念及其合成规则，第一次明确给出了不满足可加性的概率。Dempster的学生G.Shafer把证据理论推广到更加一般的情形，并使之系统化、理论化。因此证据理论又称为D-S证据理论(The D-S theory of evidence)。 1981年J.A.Barnett把该理论引入专家系统，同年J.Garvey等人用它实现了不确定性推理。 该理论满足比概率论弱的公理，能够区分“不确定”与“不知道”的差异，并能处理由“不知道”引起的不确定性，具有较大的灵活性。,4.5.1 D-S理论,证据理论是建

38、立在一个非空集合D上的理论。D为辨别框架(the frame of discernment)，它是关于某个问题域中所有可能的答案组成的有限集合，并且这些问题相互排斥，对于问题的描述是完备的。 由D的所有子集组成的集类 ，表示判断该问题正确答案的所有命题构成的集合。 为了描述和处理不确定性，引入了概率分配函数 (BPA, Basic Probability Assignment)，信任函数(Belief Function)以及似然函数(Plausibility Function)等概念。,1.概率分配函数,设D为样本空间，领域内的命题都用D的子集表示，则概率分配函数定义如下： 定义 设函数M：

39、0，1， 满足 M()0， 则称M是 上的概率分配函数，M(A)称为A的基本概率数。 若子集A满足M(A)0，则称A为焦元 (focal element)。,对概率分配函数的说明,概率分配函数的作用是把D的任意一个子集A都映射为0，1上的一个数M(A)。 当A是D的真子集时，M(A)表示对相应命题的精确信度度。当A由多个元素组成时，M(A)不包括对A的子集的精确信任度，而且也不知道该如何进行分配。当AD时，M(A)是对D的各子集进行基本可信度分配后剩下的部分，表示不知道如何分配这部分。 概率分配函数不是概率。,2. 信任函数（Belief Function）,定义 命题的信任函数Bel： 0，

40、1， 且满足 Bel函数也称为下限函数，Bel(A)表示对命题A为真的信任程度。 由信任函数和概率分配函数的定义，可以推出：,3.似然函数(Plausibility Function),似然度函数又称为不可驳斥函数或上限函数. 定义 似然函数Pl： 0，1， 且满足 由于Bel(A)表示对A为真的信任程度，所以Bel(A)表示对A为真，即A为假的信任程度，由此Pl(A)表示对A为非假的信任程度。,似然函数Pl (A)的另一种表达形式,证明过程：,4.Bel(A)与Pl(A)的关系,由上面两个公式可以看出，Bel(A)=Pl(A)。 分别称Bel(A)和Pl (A)为对A信任程度的下限和上限，记

41、为 A(Bel(A)，Pl (A) Pl (A)Bel(A)表示对A不知道的程度，即既非信任又非不信任的那部分。 减小Pl (A)Bel(A)，即减小对A不知道的程度是证据理论的目的之一。,D-S不确定区间,证据理论一个很吸引人的地方是能够很好的表达未知信息的程度，当D-S证据理论把一个信度赋给一个子集的同时,并不要求把剩余的信度赋给子集的补，即Bel(B)+Bel(B)1，而1-Bel(B)-Bel(B)=Pl (B)Bel(B)0就表示了未知的程度，用D-S不确定区间(uncertainty interval)表示这种关系。,D-S不确定区间,关于信任程度下限和上限的例子,A(Bel(A)

42、，Pl (A) A(0，0)：A为假 A(0，1)：对A一无所知 A(1，1)：A为真 A(0.25，1)：对A为真有0.25的信任度 A(0，0.85)：对A为假有0.15的信任度 A(0.25，0.85)：对A为真的信任度比对A为假的信任度稍高一点,5.概率分配函数的正交和,两个概率分配函数的合成 设M1和M2是同一样本空间D上的两个概率分配函数，根据Dempster合成规则，其正交和定义为：,上式中，若分母为0，则表明M1和M2矛盾，正交和不存在。,多个概率分配函数的合成,设M1、M2、，Mn是同一样本空间D上的n个概率分配函数，如果它们不矛盾，可以通过正交和运算将它们组合为一个概率分配

43、函数，定义如下：,两种合成方式的等效性,Dempster规则的多证据组合和两个证据的组合是等效的，而且组合运算具有可交换性和可结合性。因而，多个证据的合成还可以通过两个证据合成的递归运算得到。,两种合成方式的等效性,Dempster合成规则的空间解释,Dempster合成规则的空间解释,横条和竖条的交是一个小矩形，其测度为m1(Ai)m2(Bj)。由于该小矩形是同时分配到Ai和Bj上的，所以M1和M2的联合作用就是把m1(Ai)m2(Bj)确切的分配到AiBj上。 对于给定的子集A，确切的分配到A上的总概率为 当分配到空集上的总概率不为0时，需对其他非空集合上的总概率进行归一化。,4.5.2

44、一个具体的不确定性推理模型,在D-S理论中，Bel(A)和Pl (A)分别表示对命题A信任程度的下限和上限，因而可用(Bel(A)，Pl (A)表示证据的不确定性，同理，也可以用来表示不确定性知识规则强度的下限和上限。这样就可以建立相应的不确定性推理模型。 由于Bel(A)和Pl (A)建立在概率分配函数的基础之上，概率分配函数定义的不同，将产生不同的推理模型。 本节根据一个特殊的概率分配函数，讨论一个具体的不确定性推理模型。,1.概率分配函数与类概率函数,在该模型中，样本空间Ds1,s2,sn上的概率分配函数满足： 可以看出，在此概率分配函数中，只有单个元素构成的子集及样本空间D的概率分配函

45、数有可能大于0，其它子集的概率分配函数都为0。,此概率分配函数的特性,概率分配函数的正交和,由该概率分配函数的定义，可以把M1和M2的正交和简化为：,类概率函数,定义 命题A的类概率函数为： f(A)具有如下性质(证明过程 王永庆教材P192)：,关于类概率函数的推论,2.知识不确定性的表示,在该模型中，不确定性知识用如下形式的产生式规则表示： IF E THEN Hh1,h2,hn CFc1,c2,cn 其中： （1）E为前提条件，可以是简单条件，也可以是用AND或OR连接起来的复合条件； （2）H是结论，用样本空间中的子集表示， h1,h2,hn是该子集中的元素； （3）CF是可信度因子，

46、用集合形式表示，其中ci用来指出hi（i=1,.,n）的可信度，ci满足：,3.证据不确定性的表示,不确定性证据E的确定性用CER(E)表示。 初始证据的确定性由用户给出。 对于用前面推理所得结论作为当前推理的证据，其确定性由推理得到。 CER(E)的取值范围为0,1。,4.组合证据不确定性的算法,最大最小法 当组合证据是多个单一证据的合取时，即 E=E1 AND E2 AND AND En 则：CER(E)=minCER(E1), CER(E2), CER(En) 当组合证据是多个单一证据的析取时，即 E=E1 OR E2 OR OR En 则： CER(E)=maxCER(E1), CER

47、(E2), CER(En),5.不确定性的传递算法,对于知识：IF E THEN Hh1,h2,hn CFc1,c2,cn 结论H的确定性通过下述步骤给出： （1）求出H的概率分配函数 如果有N条知识都支持同一个结论H，则先分别求出N个概率分配函数，然后计算其正交和，从而得到H的概率分配函数。,5.不确定性的传递算法,（2）求出Bel(H),Pl(H),f(H),5.不确定性的传递算法,（3）按如下公式求出H的确定性CER(H) CER(H)=MD(H|E) f(H) 其中， MD(H|E)是知识的前提条件与相应证据E的匹配度，定义为：,D-S理论的不足与改进,不足： 复杂度成指数级增长。 要

48、求样本空间D中元素互斥，这点在许多应用领域中很难满足。 改进： Barnett提出，将D划分为若干组，每组只包含互斥的元素，称为一个辨识框架(the frame of discernment)。求解问题时，只需要在各自的辨别框架中考虑概率分配的影响。,4.6 模糊推理,模糊推理是指基于模糊理论进行的推理。,4. 6.1 模糊命题,含有模糊概念、模糊数据的语句称为模糊命题。 它的一般表示形式为： xis A 或者 x is A(CF) 其中，A是模糊概念或者模糊数，用相应的模糊集及隶属函数刻画； x是论域上的变量，用以代表所论述对象的属性； CF是该模糊命题的可信度，它既可以是一个确定的数，也可

49、以是一个模糊数或者模糊语言值。 模糊语言值是指表示大小、长短、多少等程度的一些词汇。如：极大、很大、相当大、比较大。模糊语言值同样可用模糊集描述。,4.6.2 模糊知识的表示,（1）模糊产生式规则的一般形式是： IFETHENH(CF,) 其中，E是用模糊命题表示的模糊条件；H是用模糊命题表示的模糊结论；CF是知识的可信度因子，它既可以是一个确定的数，也可以是一个模糊数或模糊语言值。是匹配度的阈值，用以指出知识被运用的条件。例如： IFx is A THEN y is B (CF,) （2）推理中所用的证据也用模糊命题表示，一般形式为 xisA 或者 xisA(CF) （3）模糊推理要解决的问

50、题：证据与知识的条件是否匹配：如果匹配，如何利用知识及证据推出结论。,4.6.3 模糊匹配与冲突消解,在模糊推理中，知识前提条件中的A与证据中的A不一定完全相同，因此首先必须考虑匹配问题。例如： IF x is 小THENy is 大(0.6) x is 较小 两个模糊集或模糊概念的相似程度称为匹配度。常用的计算匹配度的方法主要有贴近度、语义距离及相似度等。,1. 贴近度 设A与B分别是论域U=u1,u2,un上的两个模糊集，则它们的贴近度定义为： (A,B)= AB+(1-AB) /2 其中,计算匹配度的方法,2. 语义距离 (1)海明距离 (2)欧几里得距离 (3)明可夫斯基距离 (4)切

51、比雪夫距离 匹配度为：1-d(A,B),计算匹配度的方法,3. 相似度 (1) 最大最小法,计算匹配度的方法,计算匹配度的方法,3. 相似度 (2) 算术平均法,计算匹配度的方法,3. 相似度 (3) 几何平均最小法,计算匹配度的方法,3. 相似度 (4) 相关系数法,计算匹配度的方法,3. 相似度 (5) 指数法,匹配度举例,设U=a,b,c,d A=0.3/a+0.4/b+0.6/c+0.8/d B=0.2/a+0.5/b+0.6/c+0.7/d 贴近度： AB=(0.30.2)(0.40.5)(0.60.6)(0.80.7)=0.7 AB=(0.30.2)(0.40.5)(0.60.6)

52、(0.80.7)=0.3 (A,B)=1/2AB+(1-AB)=1/20.7+(1-0.3)=0.7 海明距离： d(A,B)=1/4(|0.3-0.2|+|0.4-0.5|+|0.6-0.6|+|0.8-0.7|)=0.075 (A,B)=1-d(A,B)=1-0.075=0.925 相似度： 最大最小法： r(A,B)=(0.30.2)+(0.40.5)+(0.60.6)+(0.80.7)/(0.30.2)+(0.40.5)+(0.60.6)+(0.80.7) =1.9/2.2=0.86,(1) 分别计算出每一个子条件与其证据的匹配度 例如对复合条件 E=x1 is A1 AND x2 i

53、s A2 AND x3 is A3 及相应证据E: x1 is A1 , x2 is A2 , x3 is A3 分别算出Ai与Ai的匹配度match(Ai,Ai),i=1,2,3。 (2) 求出整个前提条件与证据的总匹配度。目前常用的方法有“取极小”和“相乘”等。 match(E,E)=minmatch(A1,A1),match(A2,A2), match(A3,A3) match(E,E)=match(A1,A1)match(A2,A2)match(A3,A3) (3) 检查总匹配度是否满足阈值条件，如果满足就可以匹配，否则为不可匹配。,复合条件的模糊匹配,模糊推理中的冲突消解,1. 按匹

54、配度大小排序 2. 按加权平均值排序(把两个模糊概念的匹配度问题转换为一个对另一个的隶属度) 例如，设U=u1,u2,u3,u4,u5, A=0.9/u1+0.6/u2+0.4/u3 B=0.6/u2+0.8/u3+0.5/u4 C=0.5/u3+0.8/u4+1/u5 D=0.8/u1+0.5/u2+0.1/u3 并设有如下模糊知识： R1:IFx is A THEN y is H1 R2:IFx is B THEN y is H2 R3:IFx is C THEN y is H3 用户提供的初始证据为： E: x is D,match(A,D)=D(u1)/A(u1)+D(u2)/A(u2

55、)+D(u3)/A(u3) =0.8/0.9+0.5/0.6+0.1/0.4 同理可得： match(B,D)=0.8/0+0.5/0.6+0.1/0.8 match(C,D)=0.8/0+0.5/0+0.1/0.5 以上D与A、B、C的匹配度用模糊集形式表示。 下面求匹配度的加权平均值AV： AV(match(A,D)=(0.80.9+0.50.6+0.10.4)/(0.9+0.6+0.4)=0.56 同理可得： AV(match(B,D)=0.27 AV(match(C,D)=0.1 于是得到： AV(match(A,D)AV(match(B,D)AV(match(C,D) 所以R1是当前

56、首先被选用的知识。,3. 按广义顺序关系排序 由上例可得： match(A,D)=0.8/0.9+0.5/0.6+0.1/0.4 match(B,D)=0.8/0+0.5/0.6+0.1/0.8 match(C,D)=0.8/0+0.5/0+0.1/0.5 下面以match(A,D)与match(B,D)为例说明广义顺序排序的方法： 首先用match(B,D)的每一项分别与match(A,D)的每一项进行比较。比较时D(ui)与D(uj)中取其小者， A(ui)与B(uj)按如下规则取值：若A(ui)B(uj)则取“1”；若A(ui)0 ，则就认为match(A,D)优于match(B,D)

57、，记为match(A,D) match(B,D) 。,按这种方法，对match(A,D)与match(B,D)可以得到： 0.8/1+0.5/1+0.1/1+0.5/1+0.5/1+0.1/0+0.1/1+0.1/0+0.1/0 =0.8/1+0.1/0 由于1=0.80=0.1，所以得到： match(A,D) match(B,D) 同理可得： match(A,D) match(C,D) match(B,D) match(C,D) 最后得到： match(A,D) match(B,D)match(C,D) 由此可知R1应该是首先被选用的知识。,4.6.4 模糊推理的基本模式,1. 模糊假言推理 知识：IF x is A THEN y is B 证据：x is A - 结论：y is B 对于复合条件有： 知识：IF x1 is A1 AND x2 is A2 ANDAND xn is An THEN y is B 证据： x1 is A1 ， x2 is A2 ， ， xn is An - 结论： y is B,2. 模糊拒取式推理 知识：IF x is A THEN y is B 证据：y is B - 结