浙江大学研究生人工智能引论课件-PowerPointP

浙江大学研究生《人工智能引论》课件徐从富(CongfuXu)PhD,AssociateProfessorEmail:[e-mail]ntelligence,CollegeofComputerScience,ZhejiangUniversity,Hangzhou310027,P.R.ChinaMarch10,2002第一稿April18,2007第四次修改稿第四讲不确定性推理概述(Chapter4UncertaintyReasoning)Outline本章的主要参考文献基本概念基本问题不确定性推理方法的分类不确定性度量的测度理论不确定性的其它度量方法Shannon信息熵及在决策树中的应用模糊推理[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.（偏重贝叶斯网络及其应用）本章的主要参考文献（续）“BlessedisthenationwhoseGodistheLORD,thepeoplehechoseforhisinheritance.”FromPSALMS33:12NIV4.1.1精确推理的局限性推理依据已知事实（证据）、相关知识（规则）证明某个假设成立or不成立精确推理及其不足将原本为不确定性的关系“硬性”转化为精确关系将原本不存在明确界限的事物“人为”划定界限歪曲了现实情况的本来面目舍弃了事物的某些重要属性失去了真实性4.1基本概念4.1.2不确定性推理的定义及意义1.定义也称“不精确性推理”从不确定性的初始证据（即已知事实）出发运用不确定性的知识（或规则）推出具有一定程度的不确定性但却是合理或近乎合理的结论2.意义使计算机对人类思维的模拟更接近于人类的真实思维过程4.2不确定性推理中的基本问题不确定性的表示与度量不确定性匹配不确定性的传递算法不确定性的合成4.2.1不确定性的表示与度量1.不确定性的表示选择不确定性表示方法时应考虑的因素充分考虑领域问题的特征恰当地描述具体问题的不确定性满足问题求解的实际需求便于推理过程中对不确定性的推算不确定性的表示与度量（续1）2.不确定性的度量针对不同的领域问题采用不同的度量方法用不同的数值刻画不同的不确定性程度事先规定不确定性程度的取值范围3.常用的度量方法测度理论（基于概率统计的度量方法）Shannon信息熵其它度量方法……不确定性的表示与度量（续2）在选择不确定性度量方法时应考虑的因素：充分表达相应知识及证据不确定性的程度度量范围便于领域专家及用户估计不确定性便于计算过程中的不确定性传递，结论的不确定性度量不超出规定的范围度量的确定应直观，且有相应的理论依据4.2.2不确定性匹配解决不确定性匹配的常用方法设计一个匹配算法用以计算相似度指定一个相似度的“限定”（即阈值）“TodowhatisrightandjustismoreacceptabletotheLORDthansacrifice.”FromPROVERBS21:3NIV4.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.2.4不确定性的传递包含两个子问题在每一步推理中，如何把证据及知识的不确定性传递给给结论在多步推理中，如何把初始证据的不确定性传递给最终结论4.2.5结论不确定性的合成用不同知识进行推理得到相同的结论同个结论的不确定性程度却不相同需要用合适的算法对它们进行合成4.3不确定性推理方法的分类4.3.1不确定性推理的两条研究路线模型方法在推理一级上扩展确定性推理不确定证据和知识与某种度量标准对应给出更新结论不确定性的算法构成相应的不确定性推理模型控制方法在控制策略一级上处理不确定性无统一的不确定性处理模型，其效果依赖于控制策略4.3.2不确定性推理方法的分类不确定性推理模型方法控制方法数值方法非数值方法概率统计方法模糊推理方法粗糙集方法绝对概率方法贝叶斯方法证据理论方法HMM方法发生率计算相关性制导回溯、机缘控制、启发式搜索等可信度方法4.3.3关于不确定性推理方法的说明数值方法对不确定性的一种定量表示和处理方法其研究及应用较多，已形成多种应用模型非数值方法除数值方法外的其它处理不确定性的模型方法典型代表：“发生率计算方法”，它采用集合来描述和处理不确定性，且满足概率推理的性质关于不确定性推理方法的说明（续1）概率统计方法有完整、严密的数学理论为不确定性的合成与传递提供了现成的数学公式最早、最广泛地用于不确定性知识的表示与处理已成为不确定性推理的重要手段证据理论方法1967年Dempster首次提出，1976年Shafer完善可表示并处理“不知道”等不确定性信息关于不确定性推理方法的说明（续2）模糊推理方法可表示并处理由模糊性引起的不确定性已广泛应用于不确定性推理粗糙集理论方法1981年Z.Pawlak首次提出一种新的可表示并处理“含糊”等不确定性的数学方法可用于不确定性推理、数据挖掘等领域4.4描述不确定性信息的测度理论4.4.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测度。【注】：关于测度理论的详细论述请参见夏道行编著的《实变函数与泛函分析》，复旦大学出版社。定义4.2（模糊测度）模糊测度被定义为一个映射M:(X)[0,1]具有如下性质：(1)有界性：M()=0,M(X)=1;(2)单调性：对任意A,B(X),AB时，有M(A)M(B)由模糊测度定义可知：（1）有界性表示：一个非空元素不可能属于，它必然属于全集；（2）单调性表示：一个元素隶属于一个集合的确定度不大于它隶属于更大的一个集合的确定度。定理4.1当-1时，测度g是模糊测度。定理4.2当-1时，测度g具有如下性质：1()()1()cgAgAgA()()()()()()1()gAgBgABgAgBgABgAB模糊测度及其性质定义4.3（概率测度）称P：(X）→[0，1]为概率测度，若满足：（1）有界性：P(X)=1（2）可加性：A∩B=Φ时，P(A∪B)=P(A)+P(B)【注】：可证明概率测度是＝0时模糊测度。定义4.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Markov条件独立性定义4.5(马氏条件独立性)若A1,A2,...,An是按时间顺序发生的一系列事件，而且具有如下特性：未来某一事件Ak+1发生的可能性只依赖于当前时刻的事件Ak，而与过去发生的事件无关，即111(|)(|)kkjkkjPAAPAA这时称n个事件具有马氏（Markov）独立性。对n个满足马氏独立性条件的事件满足1213211()()(|)(|)(|)ninniPAPAPAAPAAPAA定义4.6（全概率公式）设Hi(i=m)是X上的分划，HiHj(ij)，且H1H2…Hm=X。由概率可加性，对于任意事件A，有11()()(|)()mmiiiiiPAPAHPAHPH对于条件概率有如下全概率公式：定义4.7(后验概率公式）：Bayes公式1(|)(|)(|)miiiPAEPAHEPHE1(|)()(|)(|)()jjjmiiiPAHPHPHAPAHPHBayes公式与全概率公式的区别全概率公式由原因到结果的计算公式不如Bayes公式使用广泛Bayes公式后验概率公式已知某结果发生，寻求这个结果发生的原因在实际问题中有着十分重要的应用定义4.8（信任测度）设X是有限集，称B：(X)[0,1]为信任测度，若满足：(1)B()=0,B(X)=1;(2)对于X中任意子集A1，A2，…，An有||1{1,2,...,}1()(1)()nIiiIniiIIBABA如果仅仅满足，对于X中任意两个子集A1及A2有121212()()()()BAABABABAA称为弱信任测度。【注】：可证明信任测度与弱信任测度都是模糊测度。信任测度是证据理论的最基础概念。定义4.9（似然测度）设X是有限集，称L：(X)[0,1]为似然测度，若满足：(1)L()=0,L(X)=1;(2)对于X中任意子集A1，A2，…，An有||1{1,2,...,}1()(1)()nIiiIniiIILALA如果仅仅满足，对于X中任意两个子集A1及A2有121212()()()()LAALALALAA称为弱似然测度。【注】：可证明似然测度与弱似然测度都是模糊测度。似然测度是证据理论的最基础概念。定义4.10（mass函数）称m：(X)→[0，1]是mass函数，若满足：（1）m(Ф)=0（2）mass函数是专家的一种评价或确认程度。比如X={x1,x2,…,xn}是n中疾病，某专家认为某人得疾病x1的可能性为0.7，于是得到一个mass函数：()1AXmA在证据理论中，mass函数对构造信任测度与似然测度中有着重要的作用。110.7,{}()0.3,0,,{}AxmAAXAXx定义4.11（必然性测度）设X是有限集，称N：(X)[0,1]为必然性测度，若满足：(1)N()=0,N(X)=1;(2)N(AB)=N(A)N(B)定义4.12（可能性测度）设X是有限集，称：(X)[0,1]为可能性测度，若满足：(1)()=0,(X)=1;(2)(AB)=(A)(B)【注】：可证明必然测度与可能性测度都