【人工智能_人工智能原理与应用】第四章不确定性推理.ppt

1、第四章 不确定性推理,本章内容,不确定性推理中的基本问题,证据理论,概率方法,主观Bayes方法,4,1,6,3,可信度方法,5,不确定性推理方法分类,2,4.1 不确定性推理中的基本问题,要实现对不确定性知识的处理，必须要解决不确定知识的表示问题，不确定信息的计算问题，以及不确定性表示和计算的语义解释问题。,1表示问题,1、知识不确定性的表示2、证据的不确定性表示,2. 计算问题,1、不确定性的传递算法2、结论不确定性的合成3、组合证据的不确定性算法,3. 语义问题,1、知识的不确定性度量2、证据的不确定性度量,4.2 不确定性推理方法分类,1、模型方法 特点:把不确定的证据和不确定的知识分

2、别与某种度量标准对应起来，并且给出更新结论不确定性的算法，从而构成了相应的不确定性推理的模型。,非数值方法是指出数值方法外的其他各种处理不确定性的方法 ,它采用集合来描述和处理不确定性，而且满足概率推理的性质。,非数值方法,数值方法是对不确定性的一种定量表示和处理方法。,数值方法,数值方法,分类,2、模糊推理,1、基于概率的方法,对于数值方法，按其依据的理论不同又可分为以下两类：,4.2 不确定性推理方法分类,4.2 不确定性推理方法分类,纯概率方法虽然有严密的理论依据，但它通常要求给出事件的先验概率和条件概率，而这些数据又不易获得，因此其应用受到了限制。为了解决这这个问题，人们在概率理论的基

3、础上发展起来了一些新的方法及理论:,1、主观Bayes方法,2、可信度方法,3、证据理论,它是PROSPECTOR专家系统中使用的不确定推理模型，是对Bayes公式修正后形成的一种不确定推理方法。,它是MYCIN专家系统中使用的不确定推理模型，它以确定性理论为基础，方法简单、易用。,它通过定义信任函数、似然函数，把知道和不知道区别开来。,4.2 不确定性推理方法分类,2、控制方法 特点:通过识别领域中引起不确定性的某些特征及相应的控制策略来限制或减少不确定性对系统产生的影响，这类方法没有处理不确定性的统一模型，其效果极大地依赖于控制策略。,相关性制导回溯,机缘控制,启发式搜索,设有如下产生式规

4、则： IF E THEN H其中，E为前提条件，H为结论，具有随机性。 根据概率论中条件概率的含义，我们可以用条件概率表示上述产生式规则的不确定性程度，即表示为在证据出现的条件下，结论H成立的确定性程度。 对于复合条件 E = E1 AND E2 AND AND En可以用条件概率作为在证据出现时结论的确定程度。,4.3 概率方法,4.3.1 经典概率方法,4.3 概率方法,4.3.2 Bayes定理,设 为一些事件， 互不相交，P(Bi)0，i=1,2,n，且 则对于 有， (4.3.1),Bayes公式容易由条件概率的定义、乘法公式和全概率公式得到。在Bayes公式中，称为先验概率，而称为

5、后验概率，也就是条件概率。,4.3 概率方法,4.3.3 逆概率方法的基本思想,1单个证据的情况,如果用产生式规则 IF E THEN Hi i 1, 2, , n其中前提条件E 代替Bayes公式中B，用Hi 代替公式中的Ai 就可得到 i1,2, ,n (4.3.2) 这就是说，当已知结论Hi 的先验概率，并且已知结论Hi(i=1,2,）成立时前提条件E 所对应的证据出现的条件概率P(E|Hi)，就可以用上式求出相应证据出现时结论Hi 的条件概率P(Hi|E)。,4.3 概率方法,2多个证据的情况,对于有多个证据 和多个结论 并且每个证据都以一定程度支持结论的情况，上面的式子可进一步扩充为

6、 (4.3.3),逆概率公式的优点是它有较强的理论背景和良好的数学特征，当证据及结论彼此独立时计算的复杂度比较低。其缺点是要求给出结论 的先验概率 及证据 的条件概率 ，尽管有些时候 比 相对容易得到，但总的来说，要想得到这些数据仍然是一件相当困难的工作。另外，Bayes公式的应用条件是很严格的，它要求各事件互相独立等，如若证据间存在依赖关系，就不能直接使用这个方法。,4.3 概率方法,4.3.4 逆概率方法的优缺点,4.4 主观Bayes方法,4.4.1 知识不确定性的表示,在主观Bayes方法中，知识是用产生式规则表示的，具体形式为 IF E THEN (LS，LN) H (P(H)其中（

7、1）E 是该知识的前提条件。它既可以是一个简单条件，也可以是复合条件。（2）H 是结论。P(H)是 H 的先验概率，它指出在没有任何证据情况下的结论 H 为真的概率，即 H 的一般可能性。其值由领域专家根据以往的实践及经验给出。（3）（LS，LN）为规则强度。其值由领域专家给出。LS，LN相当于知识的静态强度。,4.4 主观Bayes方法,4.4.2 证据不确定性的表示,若以O(A) 或P(A)表示证据A的不确定性，则转换公式是：,4.4 主观Bayes方法,4.4.3 不确定性的遗传算法,1证据肯定存在的情况 在证据E 肯定存在时，把先验几率O(H)更新为后验几率O(H/E)的计算公式为 (

8、4.4.1) 如果将上式换成概率，就可得到 (4.4.2) 这是把先验概率P(H)更新为后验概率P(H/E)的计算公式。,4.4 主观Bayes方法,2证据肯定不存在的情况 在证据E肯定不存在时，把先验几率O(H)更新为后验几率O(H/E)的计算公式为 (4.4.3) 如果将上式换成概率，就可得到 (4.4.4) 这是把先验概率P(H)更新为后验概率P(H/E)的计算公式。,4.4 主观Bayes方法,3证据不确定的情况 在证据不确定的情况下，不能再用上面的公式计算后验概率，而要用杜达等人1976年证明了的公式 (4.4.5) 来计算。,下面分四种情况讨论这个公式(4.4.5)：（1）当P(E

9、/S)=1时，此时式(4.4.5)变成这就是证据肯定存在的情况。（2）当P(E/S)=0时，此时式(4.4.5)变成这就是证据肯定不存在的情况。,4.4 主观Bayes方法,（3）当P(E/S)=P(E)时，表示E与S无关，利用全概率公式将公式(4.4.5)变为（4）当P(E/S)为其它值时，通过分段线性插值就可得计算P(H/S)的公式 该公式称为EH公式或UED公式。,4.4 主观Bayes方法,4组合证据的情况 （1）当组合证据是多个单一证据的合取时，即 E = E1 and E2 and and En 时，如果已知 则 P(E/S)=min （2）当组合证据E是多个单一证据的析取时，即

10、E = E1 or E2 or or En 时，如果已知 则， P(E/S)=max “非”运算用下式计算,4.4 主观Bayes方法,若有n条知识都支持相同的结论，而且每条知识的前提条件所对应的证据 都有相应的观察 与之对应，此时只要先对每条知识分别求出 然后就可运用下述公式求出,4.4 主观Bayes方法,4.4.4 结论不确定性的合成算法,4.4 主观Bayes方法,例2 设有如下知识R1：IF A THEN (20，1) B1(0.03)R2：IF B1 THEN (300，0.0001) B2(0.01)求：当证据A不存在时,P(B2 /A)的值是多少？,解:（1）由于A必发生，由R

11、1得,（2）由于B1不是必发生的，所以需作插值处理。,设,4.4.5 例子,4.4 主观Bayes方法,当,时，有,，所以在此区间插值。,由于,主观Bayes方法的主要优点如下：（1）主观Bayes方法中的计算公式大多是在概率论的基础上推导出来的，具有较坚实的理论基础。（2）知识的静态强度LS及LN是由领域专家根据实验经验给出的，这就避免了大量的数据统计工作。另外，它既用LS指出了证据E对结论H的支持程度，又用LN指出了E对H的必要性程度，这就比较全面地反映了证据与结论间因果关系，符合现实世界中某些领域的实际情况，使推出的结论有较准确的确定性。,4.4 主观Bayes方法,4.4.6 主观Ba

12、yes方法的主要优缺点,（3）主观Bayes方法不仅给出了在证据肯定存在或肯定不存在情况下由H的先验概率更新为后验概率的方法，而且还给出了在证据不确定情况下更新先验概率为后验概率的方法。另外，由其推理过程可以看出，它确实实现了不确定性的逐级传递。因此，可以说主观Bayes方法是一种比较实用且较灵活的不确定性推理方法。 它的主要缺点如下（1）要求领域专家在给出知识的同时给出H的先验概率P(H)，这是比较困难的。（2）Bayes方法中关于事件间独立性的要求使主观Bayes方法的应用受到了限制。,4.4 主观Bayes方法,所谓可信度就是在实际生活中根据自己的经验对某一事物或现象进行观察，判断相信其

13、为真得程度。 例如，张三昨天没有上课，他的理由是肚子疼，就此理由而言，听话的人可能完全相信，也可能完全不相信，也可能在某种程度上相信，这与张三平时的表现和人们对他的话相信程度有关。 这里的相信程度就是我们说的可信度。可信度也称为确定性因子。,4.5 可信度方法,4.5.1 可信度的概念,在以产生式作为知识表示的专家系统MYCIN中，用以度量知识和证据的不确定性。 显然，可信度具有较大的主观性和经验性，其准确性是难以把握的。但是，对于某一具体领域而言，由于该领域的专家具有丰富的专业知识和实践经验，要给出该领域知识的可信度还是完全有可能的。另外，人工智能所面临的问题，通常都较难用精确的数学模型进行

14、描述，而且先验概率及条件概率的确定也比较困难，因此用可信度来表示知识及证据的不确定性仍然不失为一种可行的方法。,4.5 可信度方法,4.5 可信度方法,4.5.2 C-F模型,C-F模型是基于可信度表示的不确定性推理的基本方法，其他可信度方法都是在此基础上发展起来的。,1知识不确定性的表示,2证据不确定性的表示,3组合证据不确定性的算法,4不确定性的传递算法,5结论不确定性的合成算法,4.5 可信度方法,4.5.3 可信度方法应用举例,已知 R1：IF A1 THEN B1 CF(B1,A1)=0.8； R2: IF A2 THEN B1 CF(B1,A2)=0.5； R3: IF B1A3

15、THEN B2 CF(B2,B1A3)=0.8;初始证据为A1,A2,A3的可信度CF均设为1，即,CF(A1)= CF(A2)= CF(A3)=1,对B1,B2一无所知,求CF(B1)和CF(B2)。,例4.5.1,4.5 可信度方法,解:由于对B1,B2一无所知，所以使用合成算法进行计算。由题意得到推理网络如下图所示。,4.5 可信度方法,(1)对于知识 ,分别计算,(2)利用合成算法计算 的综合可信度,(3)计算 的可信度，这时， 作为 的证据，其可信度已由前面计算出来。CF( )=0.9，而 的可信度为初始制定的1。由规则 和公式(4.5.1)得到,所以，所求得的 ， 的可信度更新值分

16、别为,4.6 证据理论,4.6.1 基本概念,证据理论假设有一个不变的两两相斥的完备元素集合U，如下图所示，这里U为,例如,U =三轮车，汽车，火车U =赤，橙，黄，绿，青，蓝，紫U =马，牛，羊，鸡，狗，兔,图4.4 证据理论说明图,4.6 证据理论,4.6.2 D-S理论,证据理论是用集合表示命题的。设D是变量x所有可能取值的集合，且D中的元素是互斥的，在任一时刻x都取D中的某一个元素为值，则称D为x的样本空间。在证据理论中，D的任何一个子集A都对应于一个关于x的命题，称该命题为“x的值在A中”。,证据理论中，为了描述和处理不确定性，引入了概率分配函数、信任函数及似然函数等概念。,设D为样

17、本空间，领域内的命题都用D的子集表示，则概率分配函数（Function of Probability Assignment）定义如下。定义4.6.1 设函数M： ,且满足则称M是 上的概率分配函数，M(A)称为A的基本概率函数（Function of Basic Probability Assignment），即对于样本空间D的任一子集都分配一个概率值。,4.6 证据理论,1、概率分配函数,定义4.6.2 设函数Bel： ,且 （ ）则称为命题A的信任函数（Function of Belief）,即命题A的信任函数值，就是A的所有子集的基本概率分配函数之和，用来表示对A的总信任。Bel函数又称

18、为下限函数，以Bel（A）表示对命题A为真的信任程度。,4.6 证据理论,2. 信任函数,似然函数（Plausible Function）又称为不可驳斥函数或上限函数，下面给出它的定义。 定义4.6.3 似然函数: ,且 （ ） 命题A的似然函数值就是所有与A相交的子集的基本概率分配函数之和，用来表示不否定A的信任度。,4.6 证据理论,3. 似然函数,因为 ，所以即 由于 表示对A为真的信任程度， 表示对A为非假的信任程度，因此可分别称 和 为对A信任程度的下限和上限，记作,4.6 证据理论,4信任函数与似然函数的关系,有时对同样的证据会得出两个不同的概率分配函数。例如，对于样本空间 ，从不

19、同的来源可分别得到如下两个概率分配函数： 此时需要对它们进行组合，德普斯特提出的组合方法可对这两个概率分配函数进行正交和运算。,4.6 证据理论,5概率分配函数的正交和,4.6 证据理论,设 是两个概率分配函数，则其正交和 为 其中， 。 如果 ,则正交和M也是一个概率分配函数；如果K0,则不存在正交和M，称 矛盾。,定义4.6.4,4.6 证据理论,定义4.6.5,对于多个概率分配函数 ，如果它们可以组合，则也可通过正交和运算将它们组合为一个概率分配函数，其定义如下。,设 是n个概率分配函数，则其正交 和 为其中， 。,4.6 证据理论,定义4.6.5,6类概率函数,除了可以利用区间(Bel

20、(A)和 )表示A的不确定性以外，还可以用A的类概率函数表示A的不确定性。 定义4.6.6 命题A的类概率函数为 其中，分别是A及D中元素的个数。 具有如下性质：,4.6 证据理论,4.6.3 知识的不确定性的表示,在该模型中，不确定性知识用如下的产生式规则表示： IF E THEN CF = 其中，（1）E为前提条件，它是样本空间D的子集。E既可以是简单条件，也可以是用AND或OR连接起来的复合条件。（2）H是结论，它用样本空间中的子集表示， 是该子集中的元素。（3）CF 是可信度因子，用集合形式表示，其中，用来指出 的可信度， 与 一一对应, 应满足如下条件,4.6 证据理论,4.6.4

21、证据的不确定性的表示,不确定性证据E的确定性用CER(E)表示。对于初始证据，其确定性由用户给出；当用前面推理所得结论作为当前推理的证据时，其确定性由推理得到。CER(E)的取值范围为 。1 组合证据不确定性的算法 当组合证据是多个证据的合取，即 时，则E的确定性CER(E)为 当组合证据是多个证据的析取，即 时，则E的确定性CER(E)为,4.6 证据理论,2 不确定性的传递算法 1）如果只有一条知识支持结论H，即 IF E THEN 结论H的确定性通过下述步骤求出。 对于上述知识，H的概率分配函数规定为这样便求得M(H)。,4.6 证据理论,2）如果有两条知识支持同一结论，即 IF THE

22、N IF THEN 结论H的确定性通过下述步骤求出。 首先分别对每一条知识求出概率分配函数：然后再用公式对 求正交和，从而得到H的概率分配函数M。,4.6 证据理论,3）如果有n条知识都支持同一结论H，则用公式 对 求其正交和，从而得到H的概率分配函数M。 最后求出,4.6 证据理论,4）按如下公式求出H的确定性CER(H) CER (H)=MD(H/E)f(H)其中，MD(H/E)是知识的前提条件与相应证据E的匹配度，定义为MD(H/E) 这样，就对一条知识或者多条有相同结论的知识求出了结论的确定性。如果该结论不是最终结论，即它又要作为另一条知识的证据继续进行推理，则重复上述过程就可得到新的

23、结论及其确定性。如此反复运用该过程，就可推出最终结论及它的确定性。,4.6 证据理论,4.6.5 例子,例4.6.1,已知 计算CER(B)。,解 先计算组合证据 的正确性再计算结论的分配函数M(b1,b2)= (0.60.3,0.60.5)=(0.18,0.3),4.6 证据理论,4.6.5 例子,得到结论的信任函数随之有而对于D的其他子集的M值均赋予0。得到结论的似然函数 最后得到,4.6 证据理论,4.6.6 证据理论的主要优缺点,最后需要说明的是，当D中的元素很多时，信任函数Bel及正交和等的运算将是相当复杂的，工作量很大，这是由于需要穷举D的所有子集，而子集的数量是 的缘故。另外，证

24、据理论要求D中的元素是互斥的，这一点在许多应用领域也难以做到。为解决这些问题，巴尼特提出了一种方法，运用这种方法可以降低计算的复杂性并解决互斥的问题。该方法的基本思想是把D划分为若干组，每组只包含相互排斥的元素，称为一个辨别框，求解问题时，只需在各自的辨别框上考虑概率分配的影响。,4.6 证据理论,证据理论的优点是它只需满足比概率论更弱的公理系统，能处理由“不知道”所引起的不确定性，由于D的子集可以是多个元素的集合，因而知识的结论部分可以是更一般的假设，这就便于领域专家从不同的语义层次上表达他们的知识，不必被限制在由单元素所表示的最明确的层次上。在应用证据理论时需要注意的是合理地划分辨别框及有效地控制计算的复杂性等。,谢 谢 !,