AI_05_6不确定性推理概述人工智能课程浙江大学研究生

第六章不确定性推理概述徐从富浙江大学人工智能研究所2002年8月第一稿2005年9月修改主要参考文献：[1]王永庆.《人工智能原理与方法》.西安交通大学出版社,1998.pp156-252.(偏重基本概念)[2]张文修,梁怡.《不确定性推理原理》.西安交通大学出版社,1996.（偏重数学原理）[3]陆汝钤.《人工智能》（下册）.科学出版社,2000.pp1133-1170.（偏重Bayes概率推理、可信度、模糊推理）[4]史忠植.《知识发现》.清华大学出版社,2002.pp24-26,pp141-202.（偏重Roughset和贝叶斯网络）[5]Mitchell,T.M.著,曾华军等译.《机器学习》.机械工业出版社,2003.pp112-143.（偏重贝叶斯学习）[6]Russell,S.,Norvig,P.ArtificialIntelligence:AModernApproach.人民邮电出版社,2002.pp413-522.（偏重贝叶斯网络及其应用）6.1造成知识不精确性的主要原因在人类的知识和思维行为中，精确性只是相对的，不精确性才是绝对的。这是客观现实的必然要求，主要原因有：（1）很多原因导致同一结果。如医学上导致低烧的病因就很多，医生只能作出猜测性判断。（2）信息的不完备性。如战场态势估计、股市波动预测等。（3）背景知识的不充分性。如人类目前对癌症机理还不了解。（4）信息描述的模糊性。如报警者说：“凶手是高个子青年，三角眼、鹰钩鼻、山羊胡。”征婚广告：“觅年青貌美、温柔体贴、家境富裕者”。（5）信息中含有噪声。如为了逃税，有些公司做假帐。军事上的雷达、无线通信、声纳等都会掺进噪声。（6）推理规则的模糊性。如“若物价上涨过快，就要紧缩信贷”等模糊规则。（7）推理能力的局限性。如天气预报，气象专家只能满足于时间不太长、精度尽可能好的预测算法。（8）解题方案的不唯一性。无论是政治、经济、文化，还是军事领域中的很多问题，一般都有多种可选方案，在无法绝对地判断各方案优劣的情况下，只好选择主观上认为相对较优的方案，这又是一种不精确推理。6.2不确定性推理的基本概念1、推理：就是从已知事实出发，通过运用相关知识逐步推出结论，或证明某个假设成立或不成立的思维过程。2、推理的两个基本要素（1）已知事实（又称证据）：用以指出推理的出发点及推理时应该使用的知识。（2）知识：是推理得以向前推进，并逐步达到最终目标的依据。3、精确性推理的局限性若用精确性推理方法（即经典逻辑）处理不确定性知识，则势必产生如下问题：把客观事物原本具有的不确定性及事物之间客观存在的不确定性关系化归为确定性的，在本来不存在明确类属界限的事物间人为地划定界限，这无疑会舍弃事物的某些重要属性，从而失去了真实性。因此，对不确定性知识的表示及其推理方法的研究，将使计算机对人类思维的模拟更接近于人类的真实思维过程。4、不确定性推理的定义不确定性推理（也称不精确性推理），就是从不确定性的初始证据（即已知事实）出发，通过运用不确定性的知识，最终推出具有一定程度的不确定性但却是合理或近乎合理的结论的思维过程。5、不确定性推理的根本目的根据用户提供的初始证据，通过运用不确定性知识，最终推出不确定性的结论，并推算出结论的不确定性程度。6.3不确定性推理中的基本问题除了必须解决经典推理方法中同样存在的推理方向、推理方法、控制策略等基本问题外，一般还需要着重解决不确定性的表示与度量、不确定性匹配、不确定性的传递算法，以及不确定性的合成等问题。1、不确定性的表示与度量不确定性推理中的“不确定性”的分类：（1）知识的不确定性（2）证据的不确定性选择不确定性表示方法时应考虑的因素：（1）根据领域问题的特征将其不确定性比较准确地描述出来，以满足问题求解的需要；（2）便于推理过程中对不确定性的推算。静态强度：表示相应知识的不确定性程度的某个数值。它可以是相应知识在应用中成功的概率，也可以是该条知识的可信程度等，其值范围因其意义与使用方法的不同而不同。动态强度：表示相应证据的不确定性程度的数值。初始证据的动态强度由用户给出；推理过程中所得到的中间结论（或中间结果）的动态强度由不确定性传递算法计算得到。不确定性的度量：对于不同的知识及不同的证据，其不确定性的程度一般是不相同的，需要用不同的数据表示其不确定性程度，还需事先规定其取值范围，只有这样每个数据才会有确定的意义。例如，在专家系统MYCIN中，（1）可信度：表示知识及证据的不确定性；（2）取值范围：[-1,1]；（3）当可信度0时，其值越大表示相应的知识或证据越接近于“真”；（4）当可信度0时，其值越小表示相应的知识或证据越接近于“假”。在确定一种度量方法及其范围时，应注意：（1）度量要能充分表达相应知识及证据不确定性的程度；（2）度量范围的指定应便于领域专家及用户对不确定性的估计；（3）度量要便于对不确定性的传递进行计算，而且对结论算出不确定性度量不能超出度量规定的范围；（4）度量的确定应当是直观的，同时应有相应的理论依据。2、不确定性匹配算法及阈值的选择对于不确定性推理，由于知识和证据都具有不确定性，而且知识所要求的不确定性程度与证据实际具有的不确定性程度不一定相同，因而就出现了“怎样才算匹配成功？”的问题。常用的解决办法：（1）设计一个算法用以计算匹配双方的相似程度（简称相似度）；（2）此外，再指定一个相似的“限定”（即阈值），用以衡量匹配双方的相似度是否落在指定的限度内。若相似度在阈值范围内，则表明是匹配的，相应知识可被应用；否则，反之。3、组合证据不确定性的算法在基于产生式规则的系统中，根据知识的前提条件是简单条件还是复合条件，可分为：单一证据：是指知识的前提条件仅为一个简单条件的情况；复合证据：是指知识的前提条件用AND（与）或OR（或）把多个简单条件连接起来构成复合条件的情况，即一个复合条件对应于一组证据。在不确定性推理中，由于结论的不确定性通常是通过对证据及知识的不确定性进行某种运算得到的，因而需要有合适的算法来计算组合证据的不确定性。常用的组合证据不确定性的计算方法有：（1）最大最小法T(E1ANDE2)=min{T(E1),T(E2)}T(E1ORE2)=max{T(E1),T(E2)}（2）概率方法（要求事件之间完全独立）T(E1ANDE2)=T(E1)×T(E2)T(E1ORE2)=T(E1)+T(E2)-T(E1)×T(E2)（3）有界方法T(E1ANDE2)=max{0,T(E1)+T(E2)-1}T(E1ORE2)=min{1,T(E1)+T(E2)}【注】：上述T(E)表示证据E为真的程度，如可信度、概率等。每组公式都有相应的适用范围和使用条件。4、不确定性的传递算法包括两个子问题：（1）在每一步推理中，如何把证据及知识的不确定性传递给给结论；（2）在多步推理中，如何把初始证据的不确定性传递给最终结论。5、结论不确定性的合成在不确定性推理中有时会出现如下情况：用不同知识进行推理得到了相同结论，但不确定性的程度却不相同，此时，需要用合适的算法对它们进行合成。而且在不同的不确定性推理方法中，所采用的合成方法也就各不相同。6.4不确定性推理方法的分类1、不确定性推理方法的两条研究路线（1）模型方法：即在推理一级上扩展确定性推理，其特点是把不确定的证据和知识分别与某种度量标准对应起来，并且给出更新结论不确定性的算法，从而构成相应的不确定性推理的模型。一般地，该方法与控制策略无关。（2）控制方法：即在控制策略一级上处理不确定性，其特点是通过识别领域中引起不确定性的某些特征，并采取相应的控制策略来限制或减少不确定性对系统产生的影响。这类方法没有处理不确定性的统一模型，其效果极大地依赖于控制策略。目前主要有：相关性制导回溯、机缘控制、启发式搜索等。2、不确定性推理方法的分类示意图不确定性推理模型方法控制方法数值方法非数值方法概率统计方法模糊推理方法粗糙集方法绝对概率方法贝叶斯方法证据理论方法HMM方法发生率计算相关性制导回溯、机缘控制、启发式搜索等可信度方法3、关于不确定性推理方法的说明（1）数值方法：这是对不确定性的一种定量表示和处理方法，目前对它的研究及应用都比较多，形成了多种应用模型。（2）非数值方法：是指除数值方法外的其它各种处理不确定性的方法，如Bundy于1984年提出的发生率计算方法，它采用集合来描述和处理不确定性，而且满足概率推理的性质。（3）概率统计方法：是指依据概率论而发展起来的各种方法，也称为基于概率的方法。由于概率论不仅有完整的理论，而且还为不确定性的合成与传递提供了现成的公式，它已成为不确定性度量的重要手段，因而它被最早、最广泛地用于不确定性知识的表示与处理。（4）证据理论方法：这是Dempster于1967首次提出，Shafer于1976年完善而成的证据合成的方法。【注】：我们将专门详细论述该理论。（5）模糊推理方法：该方法弥补了概率统计方法无法处理知识和证据中存在的模糊性问题，对由模糊性引起的不确定性的表示及处理开辟了一种新途径，目前已经广泛应用于不确定性推理领域。（6）粗糙集（RoughSets）理论方法：粗糙集理论是波兰数学家Z.Pawlak于1981年正式提出的一套全新的处理不确定的、含糊信息的数学方法，目前已经广泛应用于不确定性推理、数据挖掘、知识发现等领域。【注】：关于粗糙集理论及其应用将专门详细论述，有关辅导材料请参见ftp://10.214.1.200/课件/AI_徐从富/RoughSet6.5描述不确定性信息的测度理论6.5.1测度及其分类设(X)是有限集合X上的子集合的全体，测度的定义如下：定义6.1（测度）若g:(X)[0,1]满足条件：(1)g(X)=1;(2)当AB=时，有g(AB)=g(A)+g(B)+g(A)g(B)称为g测度。【注】：关于测度理论的详细论述请参见夏道行编著的《实变函数与泛函分析》，复旦大学出版社。定义6.2（模糊测度）模糊测度被定义为一个映射M:(X)[0,1]具有如下性质：(1)有界性：M()=0,M(X)=1;(2)单调性：对任意A,B(X),AB时，有M(A)M(B)由模糊测度定义可知：（1）有界性表示，一个非空元素不可能属于，它必然属于全集；（2）单调性表示，一个元素隶属于一个集合的确定度不大于它隶属于更大的一个集合的确定度。定理6.1当-1时，测度g是模糊测度。定理6.2当-1时，测度g具有如下性质：1()()1()cgAgAgA()()()()()()1()gAgBgABgAgBgABgAB定义6.3（概率测度）称P：(X）→[0，1]为概率测度，若满足：（1）有界性：P(X)=1（2）可加性：A∩B=Φ时，P(A∪B)=P(A)+P(B)【注】：可证明概率测度是＝0时模糊测度。定义6.4(条件概率)如果P是X上的概率测度，EX，且P(E)0，称()(|)()PAEPAEPE为给定条件E下，事件A发生的条件概率。对于条件概率显然有如下联合概率公式：()(|)()PAEPAEPE若A1,A2,...,An为X中的n个事件，可得112131211()()(|)(|)(|)nninjijPAPAPAAPAAAPAA若A,B两个事件满足P(A|B)=P(A)，即A发生的可能性与B无关，称A,B是相互独立的。这时有()()()PABPAPB若n个事件A1,A2,...,An相互独立，则11()()nniiiiPAPA在实际问题中，独立性是一个非常重要的概念，它可以大大简化概率计算。但是独立性的条件有时显得太强，需要有某种条件独立性。定义6.5(马氏条件独立性)若A1,A2,...,An是按时间顺序发生的一系列事件，而且具有如下特性：未来某一事件Ak+1发生的可能性只依赖于当前时刻的事件Ak，而与过去发生的事件无关，即111(|)(|)kkjkkjPAAPAA这时称n个事件具有马氏（M