不确定性推理方法(导论)

IntroductionofArtificialIntelligence第4章不确定性推理方法教材：王万良《人工智能导论》（第4版）高等教育出版社，2017.72第4章不确定性推理方法现实世界中由于客观上存在的随机性、模糊性，反映到知识以及由观察所得到的证据上来，就分别形成了不确定性的知识及不确定性的证据。因而还必须对不确定性知识的表示及推理进行研究。这就是本章将要讨论的不确定性推理。下面首先讨论不确定性推理中的基本问题，然后着重介绍基于概率论的有关理论发展起来的不确定性推理方法，主要介绍可信度方法、证据理论，最后介绍目前在专家系统、信息处理、自动控制等领域广泛应用的依据模糊理论发展起来的模糊推理方法。3第4章不确定性推理方法4.1不确定性推理的基本概念4.2可信度方法4.3证据理论4.4模糊推理方法4第4章不确定性推理方法4.1不确定性推理中的基本问题4.2可信度方法4.3证据理论4.4模糊推理方法54.1不确定性推理中的基本问题推理：从已知事实（证据）出发，通过运用相关知识逐步推出结论或者证明某个假设成立或不成立的思维过程。不确定性推理：从不确定性的初始证据出发，通过运用不确定性的知识，最终推出具有一定程度的不确定性但却是合理或者近乎合理的结论的思维过程。6不确定性的表示与量度不确定性匹配算法及阈值的选择组合证据不确定性的算法不确定性的传递算法结论不确定性的合成4.1不确定性推理中的基本问题74.1不确定性推理中的基本问题1.不确定性的表示与量度（1）知识不确定性的表示（2）证据不确定性的表示——证据的动态强度（3）不确定性的量度在专家系统中知识的不确定性一般是由领域专家给出的，通常是一个数值——知识的静态强度用户在求解问题时提供的初始证据。在推理中用前面推出的结论作为当前推理的证据。①能充分表达相应知识及证据不确定性的程度。②度量范围的指定便于领域专家及用户对不确定性的估计。③便于对不确定性的传递进行计算，而且对结论算出的不确定性量度不能超出量度规定的范围。④度量的确定应当是直观的，同时应有相应的理论依据。84.1不确定性推理中的基本问题2.不确定性匹配算法及阈值的选择不确定性匹配算法：用来计算匹配双方相似程度的算法。阈值：用来指出相似的“限度”。3.组合证据不确定性的算法：最大最小方法、Hamacher方法、概率方法、有界方法、Einstein方法等。94.1不确定性推理中的基本问题4.不确定性的传递算法（1）在每一步推理中，如何把证据及知识的不确定性传递给结论。（2）在多步推理中，如何把初始证据的不确定性传递给最终结论。5.结论不确定性的合成10第4章不确定性推理方法4.1不确定性推理的基本概念4.2可信度方法4.3证据理论4.4模糊推理方法111975年肖特里菲（E.H.Shortliffe）等人在确定性理论（theoryofconfirmation）的基础上，结合概率论等提出的一种不确定性推理方法。优点：直观、简单，且效果好。4.2可信度方法12可信度：根据经验对一个事物或现象为真的相信程度。可信度带有较大的主观性和经验性，其准确性难以把握。C－F模型：基于可信度表示的不确定性推理的基本方法。4.2可信度方法13产生式规则表示:：可信度因子（certaintyfactor），反映前提条件与结论的联系强度。IFTHEN((,))EHCFHE),(EHCF1.知识不确定性的表示IF头痛AND流涕THEN感冒（0.7）4.2可信度方法14CF（H，E）的取值范围:[-1,1]。若由于相应证据的出现增加结论H为真的可信度，则CF（H，E）0，证据的出现越是支持H为真，就使CF（H，E)的值越大。反之，CF（H，E）0，证据的出现越是支持H为假，CF（H，E）的值就越小。若证据的出现与否与H无关，则CF（H，E）=0。1.知识不确定性的表示4.2可信度方法15证据E的可信度取值范围：[-1，1]。对于初始证据，若所有观察S能肯定它为真，则CF(E)=1。若肯定它为假，则CF(E)=–1。若以某种程度为真，则0CF(E)1。若以某种程度为假，则－1CF(E)0。若未获得任何相关的观察，则CF(E)=0。CF(E)＝0.6：E的可信度为0.62.证据不确定性的表示4.2可信度方法162.证据不确定性的表示静态强度CF（H，E）：知识的强度，即当E所对应的证据为真时对H的影响程度。动态强度CF（E）：证据E当前的不确定性程度。4.2可信度方法17组合证据：多个单一证据的合取则组合证据：多个单一证据的析取则)}(),...,(),(min{)(n21ECFECFECFECF＝)}(,),(),(max{)(n21ECFECFECFECF＝3.组合证据不确定性的算法E=E1ANDE2AND…ANDEnE=E1ORE2OR…OREn4.2可信度方法18C－F模型中的不确定性推理：从不确定的初始证据出发，通过运用相关的不确定性知识，最终推出结论并求出结论的可信度值。结论H的可信度由下式计算：)}(,0max{),()(ECFEHCFHCF×=4.不确定性的传递算法()0()0CFECFH当时，则()1()(,)CFECFHCFHE当＝时，则4.2可信度方法19设知识：5.结论不确定性的合成算法（1）分别对每一条知识求出CF（H）：)}(,0max{),()(111ECFEHCFHCF×=)}(,0max{),()(222ECFEHCFHCF×=)),((11EHCFHEIFTHEN)),((22EHCFHEIFTHEN4.2可信度方法20（2）求出与对H的综合影响所形成的可信度：异号与若若若)()(|})(||,)(min{|1)()(0)(,0)()()()()(0≥)(,0≥)()()()()()(2121212121212121212,1HCFHCFHCFHCFHCFHCFHCFHCFHCFHCFHCFHCFHCFHCFHCFHCFHCFHCFHCF1E2E)(2,1HCF5.结论不确定性的合成算法4.2可信度方法21例4.1设有如下一组知识：)8.0(:11HTHENEIFr)6.0(:22HTHENEIFr)5.0(:33HTHENEIFr)7.0()(:16544ETHENEOREANDEIFr)9.0(:3875ETHENEANDEIFr2()0.8,CFE4()0.5,CFE5()0.6,CFE6()0.7,CFE7()0.6,CFE8()0.9.CFE已知：求：)(HCF4.2可信度方法22解：第一步：对每一条规则求出CF（H）。)(1ECF)]}([,0max{7.0654EOREANDECF)}}(),(min{,0max{7.0654EORECFECF)}}}(),(max{),(min{,0max{7.0654ECFECFECF}}}7.0,6.0max{,5.0min{,0max{7.0}5.0,0max{7.035.04:r4.2可信度方法23解：第一步：对每一条规则求出CF（H）。5:r)}(,0max{9.0)(873EANDECFECF)}}(),(min{,0max{9.087ECFECF}}9.0,6.0min{,0max{9.0}6.0,0max{9.054.0)}(,0max{8.0)(11ECFHCF}35.0,0max{8.028.01:r4.2可信度方法24解：第一步：对每一条规则求出CF（H）。2:r)}(,0max{6.0)(22ECFHCF}8.0,0max{6.048.03:r)}(,0max{5.0)(33ECFHCF}54.0,0max{5.027.04.2可信度方法25第二步：根据结论不确定性的合成算法得到：)()()()()(21212,1HCFHCFHCFHCFHCF48.028.048.028.063.0|})(||,)(min{|1)()()(32,132,13,2,1HCFHCFHCFHCFHCF}27.0,63.0min{127.063.073.036.049.0综合可信度：()0.49CFH4.2可信度方法26第4章不确定性推理方法4.1不确定性推理的基本概念4.2可信度方法4.3证据理论4.4模糊推理方法27证据理论(theoryofevidence)：又称D－S理论，是德普斯特（A.P.Dempster）首先提出，沙佛（G.Shafer）进一步发展起来的一种处理不确定性的理论。1981年巴纳特（J.A.Barnett）把该理论引入专家系统中，同年卡威（J.Garvey）等人用它实现了不确定性推理。目前，在证据理论的基础上已经发展了多种不确定性推理模型。4.3证据理论284.3证据理论4.3.1概率分配函数4.3.2信任函数4.3.3似然函数4.3.4概率分配函数的正交和（证据的组合）4.3.5基于证据理论的不确定性推理294.3.1概率分配函数设D是变量x所有可能取值的集合，且D中的元素是互斥的，在任一时刻x都取且只能取D中的某一个元素为值，则称D为x的样本空间。在证据理论中，D的任何一个子集A都对应于一个关于x的命题，称该命题为“x的值是在A中”。设x：所看到的颜色，D={红，黄，蓝}，则A={红}：“x是红色”；A={红，蓝}：“x或者是红色，或者是蓝色”。304.3.1概率分配函数设D为样本空间，领域内的命题都用D的子集表示，则概率分配函数（basicprobabilityassignmentfunction）定义如下：定义4.1设函数M：（对任何一个属于D的子集A，命它对应一个数M[0，1]）且满足则M:上的基本概率分配函数，M（A）:A的基本概率数。],1,0[→2D0)(M∑⊆1)(DAAMD231几点说明：（1）设样本空间D中有n个元素，则D中子集的个数为个。：D的所有子集。（2）概率分配函数：把D的任意一个子集A都映射为[0，1]上的一个数M（A）。，时，M（A）：对相应命题A的精确信任度。（3）概率分配函数与概率不同。n2D2D⊂AD≠A4.5.1概率分配函数例如，设A={红}，M（A）=0.3：命题“x是红色”的信任度是0.3。4.3.1概率分配函数设D={红，黄，蓝}M（{红}）=0.3，M（{黄}）=0，M（{蓝}）=0.1，M（{红，黄}）=0.2，M（{红，蓝}）=0.2，M（{黄，蓝}）=0.1，M（{红，黄，蓝}）=0.1，M（Φ）=0但：M（{红}）+M（{黄}）+M（{蓝}）=0.4设D={红，黄，蓝}则其子集个数23＝8，具体为：A={红}，A={黄}，A={蓝}，A={红，黄}，A={红，蓝}，A={黄，蓝}，A={红，黄，蓝}，A={}32定义4.2命题的信任函数（belieffunction）且：对命题A为真的总的信任程度。：Bel]1,0[→2D∑⊆)()(ABBMABel=DA⊆∀4.3.2信任函数)(ABel由信任函数及概率分配函数的定义推出：0)()(MBelDBBMDBel1)()(设D={红，黄，蓝}M（{红}）=0.3，M（{黄}）=0，M（{红，黄}）=0.2，}),({})({})({}),({黄红黄红黄红MMMBel2.03.05.033似然函数（plansibilityfunction）：不可驳斥函数或上限函数。定义4.3似然函数且对所有的]1,0[→2DPl：)(1)(ABelAPlDA⊆4.3.3似然函数设D={红，黄，蓝}M（{红}）=0.3，M（{黄}）=0，M（{红，黄}）=0.2，}),({})({})({}),({黄红黄红黄红MMMBel2.03.05.0({})1({})1({})10.50.5PlBelBe