证据理论方法-浙江大学计算机学院课件.ppt

1、浙江大学研究生浙江大学研究生人工智能引论人工智能引论课件课件徐从富徐从富(Congfu Xu) PhD, Associate Professor Email: Institute of Artificial Intelligence, College of Computer Science, Zhejiang University, Hangzhou 310027, P.R. ChinaMarch 10, 2002第一稿第一稿April 18, 2007第四次修改稿第四次修改稿第四讲 不确定性推理概述(Chapter4 Uncertainty Reasoning )Outlinen本章的主要参

2、考文献n基本概念n基本问题n不确定性推理方法的分类n不确定性度量的测度理论n不确定性的其它度量方法nShannon信息熵及在决策树中的应用信息熵及在决策树中的应用n模糊推理模糊推理1 王永庆. 人工智能原理与方法人工智能原理与方法. 西安交通大学出版社, 1998. pp156-252. (偏重基本概念)2 张文修, 梁怡. 不确定性推理原理不确定性推理原理. 西安交通大学出版社, 1996. （偏重数学原理）3 陆汝钤. 人工智能人工智能(下册下册). 科学出版社, 2000. pp1133-1170. （偏重Bayes概率推理、可信度、模糊推理）4 史忠植. 知识发现知识发现. 清华大学出

3、版社, 2002. pp24-26, pp141-202. （偏重Rough set和贝叶斯网络）本章的主要参考文献本章的主要参考文献5 Mitchell, T. M.著, 曾华军等译. 机器学习机器学习. 机械工业出版社, 2003. pp112-143. （偏重贝叶斯学习）6 Russell, S., Norvig, P. Artificial Intelligence: A Modern Approach. 人民邮电出版社, 2002. pp413-522. （偏重贝叶斯网络及其应用）本章的主要参考文献（续）本章的主要参考文献（续）“Blessed is the nation whose

4、 God is the LORD, the people he chose for his inheritance.” From PSALMS 33:12 NIV 4.1.1 精确推理的局限性精确推理的局限性 推理推理n依据已知事实（证据）、相关知识（规则）n证明某个假设成立 or 不成立 精确推理及其不足精确推理及其不足n将原本为不确定性的关系“硬性”转化为精确关系n将原本不存在明确界限的事物“人为”划定界限n歪曲了现实情况的本来面目n舍弃了事物的某些重要属性n失去了真实性4.1 基本概念4.1.2 不确定性推理的定义及意义不确定性推理的定义及意义1. 定义定义n也称“不精确性推理”n从不确

5、定性的初始证据（即已知事实）出发n运用不确定性的知识（或规则）n推出具有一定程度的不确定性但却是合理或近乎合理的结论2. 意义意义n使计算机对人类思维的模拟更接近于人类的真实思维过程4. 2 不确定性推理中的基本问题不确定性推理中的基本问题n不确定性的表示与度量不确定性的表示与度量n不确定性匹配不确定性匹配n不确定性的传递算法不确定性的传递算法n不确定性的合成不确定性的合成4.2.1 不确定性的表示与度量不确定性的表示与度量1. 不确定性的表示不确定性的表示n选择不确定性表示方法时应考虑的因素选择不确定性表示方法时应考虑的因素n充分考虑领域问题的特征n恰当地描述具体问题的不确定性n满足问题求解

6、的实际需求n便于推理过程中对不确定性的推算不确定性的表示与度量（续不确定性的表示与度量（续1）2. 不确定性的度量不确定性的度量n针对不同的领域问题采用不同的度量方法针对不同的领域问题采用不同的度量方法n用不同的数值刻画不同的不确定性程度n事先规定不确定性程度的取值范围3. 常用的度量方法常用的度量方法n测度理论（基于概率统计的度量方法）nShannon信息熵n其它度量方法n不确定性的表示与度量（续不确定性的表示与度量（续2）在选择不确定性度量方法时应考虑的因素：在选择不确定性度量方法时应考虑的因素：n充分表达相应知识及证据不确定性的程度n度量范围便于领域专家及用户估计不确定性n便于计算过程中

7、的不确定性传递，结论的不确定性度量不超出规定的范围n度量的确定应直观，且有相应的理论依据4.2.2 不确定性匹配不确定性匹配n解决不确定性匹配的常用方法解决不确定性匹配的常用方法n设计一个匹配算法匹配算法用以计算相似度n指定一个相似度的“限定”（即阈值阈值）“To do what is right and just is more acceptable to the LORD than sacrifice.” From PROVERBS 21:3 NIV 4.2.3 证据不确定性的组合证据不确定性的组合n单一证据单一证据 & 组合证据组合证据n单一证据单一证据：前提条件仅为一个简单条件n组合证

8、据组合证据：一个复合条件对应于一组证据n前提条件用AND（与）或OR（或）把多个简单条件连接起来构成复合条件（1 1）最大最小法）最大最小法T(E1 AND E2) = min T(E1), T(E2)T(E1 OR E2) = max T(E1), T(E2)（2 2）概率方法）概率方法 （要求事件之间完全独立）（要求事件之间完全独立） T(E1 AND E2) = T(E1) T(E2) T(E1 OR E2) = T(E1) + T(E2) - T(E1) T(E2)（3 3）有界方法）有界方法T(E1 AND E2) = max 0, T(E1) + T(E2) -1T(E1 OR E

9、2) = min 1, T(E1) + T(E2)【注】：上述T(E)表示证据E为真的程度，如可信度、概率等。每组公式都有相应的适用范围和使用条件。常用的组合证据不确定性计算方法常用的组合证据不确定性计算方法4.2.4 不确定性的传递不确定性的传递n包含两个子问题包含两个子问题n在每一步推理每一步推理中，如何把证据及知识的不确定性传递给给结论n在多步推理多步推理中，如何把初始证据的不确定性传递给最终结论4.2.5 结论不确定性的合成结论不确定性的合成n用不同知识进行推理得到相同的结论n同个结论的不确定性程度却不相同n需要用合适的算法对它们进行合成4. 3 不确定性推理方法的分类不确定性推理方法

10、的分类4.3.1 不确定性推理的两条研究路线不确定性推理的两条研究路线n模型方法模型方法n在推理一级上扩展确定性推理n不确定证据和知识与某种度量标准对应n给出更新结论不确定性的算法n构成相应的不确定性推理模型n控制方法控制方法n在控制策略一级上处理不确定性n无统一的不确定性处理模型，其效果依赖于控制策略4.3.2 4.3.2 不确定性推理方法的分类不确定性推理方法的分类不确定性推理模型方法控制方法数值方法非数值方法概率统计方法模糊推理方法粗糙集方法绝对概率方法贝叶斯方法证据理论方法HMM方法发生率计算相关性制导回溯、机缘控制、启发式搜索等可信度方法4.3.3 关于不确定性推理方法的说明关于不确

11、定性推理方法的说明n数值方法数值方法n对不确定性的一种定量表示和处理方法n其研究及应用较多，已形成多种应用模型n非数值方法非数值方法n除数值方法外的其它处理不确定性的模型方法n典型代表：“发生率计算方法”，它采用集合来描述和处理不确定性，且满足概率推理的性质关于不确定性推理方法的说明（续关于不确定性推理方法的说明（续1）n概率统计方法概率统计方法n有完整、严密的数学理论n为不确定性的合成与传递提供了现成的数学公式n最早、最广泛地用于不确定性知识的表示与处理n已成为不确定性推理的重要手段n证据理论方法证据理论方法n1967年Dempster首次提出，1976年Shafer完善n可表示并处理“不知

12、道”等不确定性信息关于不确定性推理方法的说明（续关于不确定性推理方法的说明（续2）n模糊推理方法模糊推理方法n可表示并处理由模糊性引起的不确定性n已广泛应用于不确定性推理n粗糙集理论方法粗糙集理论方法n1981年Z. Pawlak首次提出n一种新的可表示并处理“含糊”等不确定性的数学方法n可用于不确定性推理、数据挖掘等领域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) +

13、 g(A) g(B)称为g 测度测度。【注】：关于测度理论的详细论述请参见夏道行编著的实变函数与泛函分析，复旦大学出版社。定义4.2（模糊测度模糊测度） 模糊测度被定义为一个映射M: (X) 0, 1具有如下性质： (1) 有界性有界性： M() = 0, M(X) = 1; (2) 单调性单调性： 对任意A, B(X), AB时，有M(A) M(B) 由模糊测度定义可知： （1）有界性表示：一个非空元素不可能属于，它必然属于全集； （2）单调性表示：一个元素隶属于一个集合的确定度不大于它隶属于更大的一个集合的确定度。定理4.1 当-1时， 测度g是模糊测度。定理4.2 当-1时， 测度g具有

14、如下性质：1()()1()cgAgAgA( )( )()( )( )()1()gAgBgABgA gBgABgAB模糊测度及其性质模糊测度及其性质定义4.3（概率测度概率测度） 称P： (X） 0，1为概率测度，若满足：（1）有界性：P(X) = 1（2）可加性：AB=时，P(AB) = P(A) + P(B)【注】：可证明概率测度概率测度是0时模糊测度。 定义4.4 (条件概率条件概率) 如果P是X上的概率测度，EX，且P(E)0，称()(|)()P AEP A EP E为给定条件E下，事件A发生的条件概率。 对于条件概率有如下联合概率公式：联合概率公式：()(|)()P AEP A E P

15、 E 若A1, A2, ., An为X中的n个事件，可得112131211()() (|) (|)(|)nninjijPAP A P AA P AAAP AA 若A, B两个事件满足P(A|B) = P(A)，即A发生的可能性与B无关，称A, B是相互独立相互独立的。这时有()( )( )P ABP A P B 若n个事件A1, A2, ., An相互独立，则11()()nniiiiPAP AMarkov条件独立性条件独立性定义定义4.5 (马氏条件独立性马氏条件独立性) 若A1, A2, ., An是按时间顺序发生的一系列事件，而且具有如下特性：未来某一事件Ak+1发生的可能性只依赖于当前时

16、刻的事件Ak ，而与过去发生的事件无关，即111(|)(|)kkjkkjP AAP AA这时称n个事件具有马氏（马氏（Markov）独立性独立性。 对n个满足马氏独立性条件的事件满足1213211()() (|) (|)(|)ninniPAP A P AA P AAP AA定义4.6（全概率公式全概率公式） 设Hi (i 0 。【注】：与不协调度相似，当m是概率分布时，混淆度即为不确定度（香农信息熵）。 3、信息量、信息量 一个概念是内涵与外延的统一体。内涵的多少表示了信息量的大小，但是内涵一般是无法度量的。由于内涵与外延是某种相反关系，我们可用外延补集作为信息，可用外延补集作为信息，用外延补

17、集的测度作为信息量用外延补集的测度作为信息量。于是就得到如下信息量的概念。定义4.19 (信息量信息量) 设X是有限集，包含n个元素。P是X上的概率分布，称2()( ) ( )( )(1( )1( )xxxI XP x P xP xP xPx 是X, P的信息量。其中， |xXxy yx 在不确定性推理过程中，经常遇到两类问题： (1) 匹配（检索）问题，需要相似度相似度的概念； (2) 推理规则的条件与结论之间的蕴涵关系，就需要蕴蕴涵度涵度的概念。 经专家研究发现，相似度与蕴涵度的共性即为包含度包含度。 【注】：本课件只简要介绍上述三个概念的定义，有关包含度理论的详细论述请参见文献： 张文修

18、、梁怡不确定性推理原理，西安交通大学出版社，1996。补充说明：补充说明： 4、包含度、包含度 设X是一个普通集合，(X)表示X中所有子集的全体，(X)表示X中模糊集合的全体。 定义4.19 (包含度包含度)：设0(X)(X) ，对A, B 0(X) 有数D(B/A)对应，且满足： (1) 0 = D(B/A) H，令R(P; H)为从P推出 H的模糊关系nR(P; H) = APAH = (xP, xH) / uR(xP, xH)nuR(xP, xH) = uAp(xP) uAH(xH) n阶段二：推理合成规则（max-min复合运算）n当实际的输入信息为模糊命题P时，则模糊推理的输出HnA

19、H = AP R(P; H) n可得()()(,)HPPPAHAPRPHxUxxx x基于模糊关系的推理举例n请参见高济教授编著的教材基于知识的软件智能化技术pp206-208n有兴趣的同学可进一步参考张文修、梁怡编著的不确定性推理原理pp228-235中的“5-4 Mamdani模糊推理”n基本要求：能熟练解答与高济教授教材中类似的模糊推理习题4.7.6 模糊推理的神经网络算法n特别声明特别声明n这一节属于补充材料，考试时不做要求 n感兴趣的同学可参见张文修、梁怡编著的不确定性推理原理pp244-248中的“5-7 模糊推理的神经网络算法”n模糊推理的神经网络算法思想n将“Ai = Bi”规

20、则作为第i个输入，则形成一个神经网络n可通过神经网络的学习算法得到权重wi模糊推理的神经网络算法学习过程n当Y是单点集y时，训练模型为(A, B)，学习算法的过程如下：n步1：给出初始权重w1和训练样本H=(A, B)n步2：利用如下公式计算n步3：若B(y) = B(y) ，则终止；否则，修正w1;n步4：若上述过程进行到第k步，得到Wk=(wk1,wk2,wkn)，使得 则终止，其中，gk为形成的模糊测度，即 gk(i)= wki；否则，修正权重wki。【注】：权重修正方法详见张文修、梁怡编著的不确定性推理原理pp246( )()( )ZRiZByg ZiiBy ( )( )( )( )ZRi ZB yg ZB yiiB y THANKS FOR YOUR PRESENCE!“But seek first his kingdom and his righteousness, and all these things will be given to you as well. Therefore do not worry about tomorrow, for tomorrow will worry about itself. Each day has enough trouble of its own.” from MATTHEW 6:33-34 NIV