不确定性推理推理方法.ppt

第 6 讲 不确定性处理 不确定性及其类型 不确定性知识的表示 不确定性推理及实现一、一、不确定性及其类型不确定性及其类型1.1.随机性随机性2.2.模糊性模糊性3.3.不完全性不完全性4.4.不一致性不一致性二、二、不确定性知识的表示不确定性知识的表示 P160-166P160-166三、三、不确定性推理及实现不确定性推理及实现1.1.基本概念基本概念 (1)(1)为什么要研究不确定性推理问题为什么要研究不确定性推理问题 现实世界的问题求解大部分是不良结构；现实世界的问题求解大部分是不良结构；对不良结构的知识描述具有不确定性（或叫不精确性）对不良结构的知识描述具有不确定性（或叫不精确性）：1)1)问题问题证据证据（初始事实、中间结论）的不确定性；（初始事实、中间结论）的不确定性；2)2)专门专门知识知识（规则）的不确定性。（规则）的不确定性。(2)(2)什么是不确定性推理什么是不确定性推理 不确定性推理就是从不确定性推理就是从不确定性的初始证据不确定性的初始证据出发，通出发，通过运用过运用不确定性的知识不确定性的知识，最终推出，最终推出具有一定程度的不确具有一定程度的不确定性定性但却合理或者近乎合理的但却合理或者近乎合理的结论结论的思维过程。的思维过程。(3)(3)不确定性推理中的基本问题不确定性推理中的基本问题 在不确定性推理中，知识和证据都具有某种程度在不确定性推理中，知识和证据都具有某种程度的不确定性，这就为推理机的设计与实现增加了复杂性的不确定性，这就为推理机的设计与实现增加了复杂性和难度。和难度。它除了必须解决它除了必须解决推理方向推理方向、推理方法推理方法、控制策略控制策略等等基本问题外，一般还需要解决基本问题外，一般还需要解决不确定性的表示和量度不确定性的表示和量度、不确定性匹配不确定性匹配、不确定性的传递算法不确定性的传递算法以及以及不确定性的合不确定性的合成成等重要问题。等重要问题。.不确定性的表示与量度不确定性的表示与量度 知识不确定性的表示知识不确定性的表示 在确立其表示方法时，有两个直接相关的因素需要考在确立其表示方法时，有两个直接相关的因素需要考虑：虑：1)1)要能根据领域问题的特征把其不确定性比较准确地要能根据领域问题的特征把其不确定性比较准确地描述出来，满足问题求解的需要；描述出来，满足问题求解的需要；2)2)要便于推理过程中对不确定性的推算。要便于推理过程中对不确定性的推算。证据不确定性的表示证据不确定性的表示 在推理中，有两种来源不同的证据：在推理中，有两种来源不同的证据：1)1)一种是用户在求解问题时提供的初始证据；一种是用户在求解问题时提供的初始证据；2)2)另一种是在推理中用前面推出的结论作为当前推另一种是在推理中用前面推出的结论作为当前推理的证据。理的证据。对于初始证据，其值由用户给出；对于初始证据，其值由用户给出；对推理所得证据，其值由推理中不确定性的传递算对推理所得证据，其值由推理中不确定性的传递算法通过计算得到。法通过计算得到。*证据的不确定性表示方法应与知识的不确定性表证据的不确定性表示方法应与知识的不确定性表示方法保持一致，以便于推理过程中对不确定性进行统示方法保持一致，以便于推理过程中对不确定性进行统一处理。一处理。不确定性的量度不确定性的量度 对于不同的知识和不同的证据，其不确定性的程度对于不同的知识和不同的证据，其不确定性的程度一般是不相同的，需要用不同的数据表示其不确定性的一般是不相同的，需要用不同的数据表示其不确定性的程度，同时还要事先规定它的取值范围。程度，同时还要事先规定它的取值范围。例如，在专家系统例如，在专家系统 MYCIN 中，用可信度表示知识中，用可信度表示知识与证据的不确定性，取值范围为与证据的不确定性，取值范围为-1，1。.不确定性匹配算法及阈值的选择不确定性匹配算法及阈值的选择 对于不确定性推理，由于知识和证据都具有不确定对于不确定性推理，由于知识和证据都具有不确定性，而且知识所要求的不确定性与证据实际具有的不确性，而且知识所要求的不确定性与证据实际具有的不确定性程度不一定相同，因而就出现了定性程度不一定相同，因而就出现了“怎样才算匹配成怎样才算匹配成功功”的问题。的问题。对于这个问题，目前常用的解决方法是：对于这个问题，目前常用的解决方法是：设计一个算法用来计算匹配双方相似的程度，另外设计一个算法用来计算匹配双方相似的程度，另外再指定一个相似的再指定一个相似的“限度限度”，用来衡量匹配双方相似的，用来衡量匹配双方相似的程度是否落在指定的限度内。如果落在指定的限度内，程度是否落在指定的限度内。如果落在指定的限度内，就称它们是可匹配的，相应知识可被应用。就称它们是可匹配的，相应知识可被应用。用来计算匹配双方相似程度的算法称为用来计算匹配双方相似程度的算法称为不确定性不确定性匹配算法匹配算法。用来指出相似的用来指出相似的“限度限度”称为称为阈值阈值。.不确定性的传递算法不确定性的传递算法 推理过程中不确定性的传递过程，包括如下两个密推理过程中不确定性的传递过程，包括如下两个密切相关的子问题：切相关的子问题：在每一步推理中，如何把证据及知识的不确定在每一步推理中，如何把证据及知识的不确定性传递给结论；性传递给结论；在多步推理中，如何把初始证据的不确定性传在多步推理中，如何把初始证据的不确定性传递给最终结论。递给最终结论。对前一个问题，在不同的不确定推理方法中所采对前一个问题，在不同的不确定推理方法中所采用的处理方法各不相同。用的处理方法各不相同。对第二个问题，各种推理方法所采用的处理方法基对第二个问题，各种推理方法所采用的处理方法基本相同，即：本相同，即：把当前推出的结论及其不确定性程度作为证据放把当前推出的结论及其不确定性程度作为证据放入数据库中，供以后推理使用。入数据库中，供以后推理使用。.结论不确定性的合成结论不确定性的合成 推理时有时会出现这样的情况：用不同的知识进推理时有时会出现这样的情况：用不同的知识进行推理得到了相同的结论，但不确定性的程度却不同。行推理得到了相同的结论，但不确定性的程度却不同。此时，需要用合适的算法对它们进行合成。在不同的此时，需要用合适的算法对它们进行合成。在不同的不确定推理方法中所采用的处理方法各不相同。不确定推理方法中所采用的处理方法各不相同。2.常用的不确定性推理方法介绍常用的不确定性推理方法介绍 (1)可信度方法可信度方法 可信度方法是由可信度方法是由E.H.Shortliffe等人在确定性理论的基础上，结合等人在确定性理论的基础上，结合概率提出的一种不确定性推理方法，首先在概率提出的一种不确定性推理方法，首先在Mycin系统中得到了成功的系统中得到了成功的应用。应用。其核心思想是：其核心思想是：利用确定性因子利用确定性因子CF（值）值）.联系于具体的断言联系于具体的断言 .联系于每条规则联系于每条规则 .通过通过CF的计算传播不确定性的计算传播不确定性 (2)(2)主观主观 BayesBayes 方法方法 利用新的信息将先验概率利用新的信息将先验概率P(H)P(H)更新为后验概率更新为后验概率P(H|E)P(H|E)的一种计的一种计 算方法算方法.主观主观 BayesBayes方法由方法由 Dnda Dnda 等人于等人于 1976 1976 年提出，其首先在年提出，其首先在 Prospector Prospector 专家系统中使用，它以概率论中的专家系统中使用，它以概率论中的 BayesBayes公式为基础。公式为基础。其核心思想是：其核心思想是：.根据证据的概率根据证据的概率P(E);P(E);.利用规则的（利用规则的（LSLS，LNLN）；）；LSLS：E E 的出现对的出现对 H H 的支的支持程度，持程度，LNLN：E E 的出现对的出现对 H H 的不支持程度。的不支持程度。.把结论把结论 H H 的先验概率更新为后验概率的先验概率更新为后验概率 P(H|E)P(H|E)；.循环循环(3)(3)证据理论法证据理论法 由由DempsterDempster和和shafenshafen提出并发展，其基于一系列理提出并发展，其基于一系列理论和描述，它能处理由不知道产生的不确定性，它有比论和描述，它能处理由不知道产生的不确定性，它有比概率论更弱的公理系统，概率论为其特例。概率论更弱的公理系统，概率论为其特例。(4)(4)模糊理论法模糊理论法 基于基于ZedehZedeh的模糊集合理论的模糊集合理论,主要针对知识的模糊主要针对知识的模糊性。性。3.可信度方法可信度方法 (1)可信度可信度 根据经验对一个事物或现象为真的相信程度。根据经验对一个事物或现象为真的相信程度。(2)C-F模型模型 C-F 模型是基于可信度表示的不确定性推理的基本方法。模型是基于可信度表示的不确定性推理的基本方法。.知识不确定性的表示知识不确定性的表示 在在C-F模型中，知识是用产生式规则表示的，其一般模型中，知识是用产生式规则表示的，其一般形式是：形式是：if E then H (CF(H,E)其中，其中，E：是知识的前提条件，它既可以是一个单个条件，是知识的前提条件，它既可以是一个单个条件，也可以是用也可以是用 and 及及 or 连接起来的复合条件；连接起来的复合条件；H：是结论，它可以是一个单一结论，也可以是多是结论，它可以是一个单一结论，也可以是多个结论。个结论。CF(H,E)：是该条知识的可信度，称为可信度因子或是该条知识的可信度，称为可信度因子或规则强度，静态强度。规则强度，静态强度。CH(H,E)在在-1，1上取值，它指出当前提条件上取值，它指出当前提条件 E 所所对应的证据为真时，它对结论为真的支持程度。对应的证据为真时，它对结论为真的支持程度。例如：例如：if 头痛头痛 and 流涕流涕 then 感冒（感冒（0.7）表示当病人确有表示当病人确有“头痛头痛”及及“流涕流涕”症状时，则有症状时，则有7成的把握认为成的把握认为 他患了感冒。他患了感冒。在在 C-F 模型中，把模型中，把CF(H,E)定义为：定义为：CF(H,E)=MB(H,E)MD(H,E)MB：称为称为信任增长度信任增长度，它表示因与前提条件，它表示因与前提条件 E 匹匹配的证据的出现，使结论配的证据的出现，使结论H为真的信任增长度。为真的信任增长度。MB定义为：定义为：MB(H,E)=1 若若P(H)=1MaxP(H/E),P(H)P(H)1 P(H)否则否则 MD：称为称为不信任增长度不信任增长度，它表示因与前提条件，它表示因与前提条件E匹匹配的证据的出现，使结论配的证据的出现，使结论H为真的不信任增长度。为真的不信任增长度。MD定义为：定义为：MD(H,E)=P(H)表示表示H的先验概率；的先验概率；P(H/E)表示在前提条件表示在前提条件E对应的证据出现的情况下，对应的证据出现的情况下，结论结论H的条件概率。的条件概率。1 若若P(H)=0MinP(H/E),P(H)P(H)P(H)否则否则 因为一个证据不可能既增加对因为一个证据不可能既增加对H 的信任程度，又增加的信任程度，又增加对对H的不信任程度，因此的不信任程度，因此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)的计算公式：的计算公式：MB(H,E)0 =若若P(H/E)P(H)CF(H,E)=0 若若P(H/E)=P(H)0 MD(H,E)=若若P(H/E)0，证据的出现越是支持证据的出现越是支持 H 为真，就使为真，就使CF(H,E)的值越大；反之，使的值越大；反之，使CF(H,E)0，证据的出现越是支持证据的出现越是支持 H 为假为假，就使就使CF(H,E)的值越小；若证据的出现与否与的值越小；若证据的出现与否与 H 无无关，则使关，则使 CF(H,E)=0。.证据不确定的表示证据不确定的表示 在该模型中，证据的不确定性也用可信度因子表示。如：在该模型中，证据的不确定性也用可信度因子表示。如：CF(E)=0.6 表示证据表示证据 E 的可信度为的可信度为 0.6。证据可信度值的来源分为两种情况：证据可信度值的来源分为两种情况：对于初始证据，其可信度的值由提供证据的用户给出；对于初始证据，其可信度的值由提供证据的用户给出；对于用先前推出的结论作为当前推理的证据，其可信对于用先前推出的结论作为当前推理的证据，其可信度值在推出该结论时通过不确定性传递算法计算得到。度值在推出该结论时通过不确定性传递算法计算得到。证据证据 E 的可信度的可信度 CF(E)也是在也是在-1，1之间取值。之间取值。.组合证据不确定性的算法组合证据不确定性的算法 当组合证据是多个单一证据的合取时，即：当组合证据是多个单一证据的合取时，即：E=E1 and E2 and and En 若已知若已知 CF(E1)，CF(E2)，CF(En)，则则 CF(E)=min CF(E1)，CF(E2)，CF(En)当组合证据是多个单一证据的析取时，即：当组合证据是多个单一证据的析取时，即：E=E1 or E2 or or En 若已知若已知 CF(E1)，CF(E2)，CF(En)，则则 CF(E)=max CF(E1)，CF(E2)，CF(En).不确定性的传递算法不确定性的传递算法 C-F 模型中的不确定性推理是从不确定的初始证据模型中的不确定性推理是从不确定的初始证据出发，通过运用相关的不确定性知识，最终推出结论并出发，通过运用相关的不确定性知识，最终推出结论并求出结论的可信度值。求出结论的可信度值。结论结论 H 的可信度由下式计算：的可信度由下式计算：CF(H)=CF(H,E)max 0,CF(E).结论不确定性的合成算法结论不确定性的合成算法 若由多条不同知识推出了相同的结论，但可信度不若由多条不同知识推出了相同的结论，但可信度不同，则可用合成算法求出同，则可用合成算法求出综合可信度综合可信度。设有如下知识：设有如下知识：if E1 then H (CF(H,E1)if E2 then H (CF(H,E2)则结论则结论 H 的综合可信度可分如下两步算出：的综合可信度可分如下两步算出：首先分别对每一条知识求出首先分别对每一条知识求出 CF(H)：CF1(H)=CF(H,E1)max 0,CF(E1)CF2(H)=CF(H,E2)max 0,CF(E2)然后用下述公式求出然后用下述公式求出 E1 与与 E2 对对 H 的综合影响所形成的可信度：的综合影响所形成的可信度：CF1(H)+CF2(H)CF1(H)CF2(H)若若 CF1(H)0,CF2(H)0 CF1(H)+CF2(H)+CF1(H)CF2(H)若若 CF1(H)0,CF2(H)0 CF1(H)+CF2(H)1 min|CF1(H)|,|CF2(H)|若若 CF1(H)与与 CF2(H)异号异号 CF1，2(H)=例：有下列一组知识：例：有下列一组知识：r1：if E1 then H (0.8)r2：if E2 then H (0.6)r3：if E3 then H (-0.5)r4：if E4 and (E5 or E6)then E1 (0.7)r5：if E7 and E8 then E3 (0.8)已知：已知：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)=?解：由已知知识得到推理网络：解：由已知知识得到推理网络：HE2E3E7E8E1E4E5E6由由 r4 得到：得到：CF(E1)=0.7 max 0,CF E4 and (E5 or E6)=0.7 max 0,min CF(E4),CF(E5 or E6)=0.7 max 0,min CF(E4),max CF(E5),CF(E6)=0.7 max 0,min 0.5,max 0.6,0.7 =0.7 0.5 =0.35 由由 r5 得到：得到：CF(E3)=0.8 max 0,CF(E7 and E8)=0.8 0.6 =0.48 由由 r1 得到：得到：CF1(H)=0.8 max 0,CF(E1)=0.8 0.35 =0.28 由由 r2 得到：得到：CF2(H)=0.6 max 0,CF(E2)=0.6 0.8 =0.48 由由 r3 得到：得到：CF3(H)=-0.5 max 0,CF(E3)=-0.5 0.48 =-0.24 结论不确定性的合成结论不确定性的合成 CF1，2(H)=CF1(H)+CF2(H)CF1(H)CF2(H)=0.28+0.48 0.28 0.48 =0.63 CF1,2,3(H)=0.49 即：即：CF(H)=0.49 CF1,2(H)+CF3(H)1 min|CF1,2(H)|,|CF3(H)|7.5证据理论7.5.1基本概念1.识别框架2.基本概念分配函数(p161)3.信任函数(P162)4.似真函数(P162)5.信任区间(P162)6.Dempster组合规则(P163)1)基本的组合规则2)含冲突修正的组合规则7.5.2基于证据理论的不确定性推理1.建立问题的识别框架2.给幂集2 定义基本概率分配函数3.计算所关心的子集A 2 的信任函数值Bel(A),似真函数值PL(A);4.由Bel(A),PL(A)得出结论7.6模糊推理7.6.1语言变量，语言值7.6.2用模糊（关系）集合表示模糊规则7.6.3模糊关系合成7.6.4基于关系合成的模糊推理