浙江大学研究生《人工智能引论》

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 )1Outline本章的主要参考文献基本概念基本问题不确定性推理方法的分类不确定性度量的测度理论不确定性

2、的其它度量方法Shannon信息熵及在决策树中的应用模糊推理21 王永庆. 人工智能原理与方法. 西安交通大学出版社, 1998. pp156-252. (偏重基本概念)2 张文修, 梁怡. 不确定性推理原理. 西安交通大学出版社, 1996. （偏重数学原理）3 陆汝钤. 人工智能(下册). 科学出版社, 2000. pp1133-1170. （偏重Bayes概率推理、可信度、模糊推理）4 史忠植. 知识发现. 清华大学出版社, 2002. pp24-26, pp141-202. （偏重Rough set和贝叶斯网络）本章的主要参考文献35 Mitchell, T. M.著, 曾华军等译.

3、机器学习. 机械工业出版社, 2003. pp112-143. （偏重贝叶斯学习）6 Russell, S., Norvig, P. Artificial Intelligence: A Modern Approach. 人民邮电出版社, 2002. pp413-522. （偏重贝叶斯网络及其应用）本章的主要参考文献（续）“Blessed is the nation whose God is the LORD, the people he chose for his inheritance.” From PSALMS 33:12 NIV 44.1.1 精确推理的局限性 推理依据已知事实（证据）

4、、相关知识（规则）证明某个假设成立 or 不成立 精确推理及其不足将原本为不确定性的关系“硬性”转化为精确关系将原本不存在明确界限的事物“人为”划定界限歪曲了现实情况的本来面目舍弃了事物的某些重要属性失去了真实性4.1 基本概念54.1.2 不确定性推理的定义及意义1. 定义也称“不精确性推理”从不确定性的初始证据（即已知事实）出发运用不确定性的知识（或规则）推出具有一定程度的不确定性但却是合理或近乎合理的结论2. 意义使计算机对人类思维的模拟更接近于人类的真实思维过程64. 2 不确定性推理中的基本问题不确定性的表示与度量不确定性匹配不确定性的传递算法不确定性的合成74.2.1 不确定性的表

5、示与度量1. 不确定性的表示选择不确定性表示方法时应考虑的因素充分考虑领域问题的特征恰当地描述具体问题的不确定性满足问题求解的实际需求便于推理过程中对不确定性的推算8不确定性的表示与度量（续1）2. 不确定性的度量针对不同的领域问题采用不同的度量方法用不同的数值刻画不同的不确定性程度事先规定不确定性程度的取值范围3. 常用的度量方法测度理论（基于概率统计的度量方法）Shannon信息熵其它度量方法9不确定性的表示与度量（续2）在选择不确定性度量方法时应考虑的因素：充分表达相应知识及证据不确定性的程度度量范围便于领域专家及用户估计不确定性便于计算过程中的不确定性传递，结论的不确定性度量不超出规定

6、的范围度量的确定应直观，且有相应的理论依据104.2.2 不确定性匹配解决不确定性匹配的常用方法设计一个匹配算法用以计算相似度指定一个相似度的“限定”（即阈值）“To do what is right and just is more acceptable to the LORD than sacrifice.” From PROVERBS 21:3 NIV 114.2.3 证据不确定性的组合单一证据 & 组合证据单一证据：前提条件仅为一个简单条件组合证据：一个复合条件对应于一组证据前提条件用AND（与）或OR（或）把多个简单条件连接起来构成复合条件12（1）最大最小法T(E1 AND E2)

7、 = min T(E1), T(E2)T(E1 OR E2) = max T(E1), T(E2)（2）概率方法 （要求事件之间完全独立） T(E1 AND E2) = T(E1) T(E2) T(E1 OR E2) = T(E1) + T(E2) - T(E1) T(E2)（3）有界方法T(E1 AND E2) = max 0, T(E1) + T(E2) -1T(E1 OR E2) = min 1, T(E1) + T(E2)【注】：上述T(E)表示证据E为真的程度，如可信度、概率等。每组公式都有相应的适用范围和使用条件。常用的组合证据不确定性计算方法134.2.4 不确定性的传递包含两个

8、子问题在每一步推理中，如何把证据及知识的不确定性传递给给结论在多步推理中，如何把初始证据的不确定性传递给最终结论144.2.5 结论不确定性的合成用不同知识进行推理得到相同的结论同个结论的不确定性程度却不相同需要用合适的算法对它们进行合成154. 3 不确定性推理方法的分类4.3.1 不确定性推理的两条研究路线模型方法在推理一级上扩展确定性推理不确定证据和知识与某种度量标准对应给出更新结论不确定性的算法构成相应的不确定性推理模型控制方法在控制策略一级上处理不确定性无统一的不确定性处理模型，其效果依赖于控制策略164.3.2 不确定性推理方法的分类不确定性推理模型方法控制方法数值方法非数值方法概

9、率统计方法模糊推理方法粗糙集方法绝对概率方法贝叶斯方法证据理论方法HMM方法发生率计算相关性制导回溯、机缘控制、启发式搜索等可信度方法174.3.3 关于不确定性推理方法的说明数值方法对不确定性的一种定量表示和处理方法其研究及应用较多，已形成多种应用模型非数值方法除数值方法外的其它处理不确定性的模型方法典型代表：“发生率计算方法”，它采用集合来描述和处理不确定性，且满足概率推理的性质18关于不确定性推理方法的说明（续1）概率统计方法有完整、严密的数学理论为不确定性的合成与传递提供了现成的数学公式最早、最广泛地用于不确定性知识的表示与处理已成为不确定性推理的重要手段证据理论方法1967年Demp

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

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

12、性质23定义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，称为给定条件E下，事件A发生的条件概率。24 对于条件概率有如下联合概率公式： 若A1, A2, ., An为X中的n个事件，可得 若A, B两个事件满足P(A|B) = P(A)，即A发生的可能性与B无关，称A, B是相互独立的。这时有 若n个事件A1, A2, ., An相互独立，则25Markov条件独立性定义4.5

13、 (马氏条件独立性) 若A1, A2, ., An是按时间顺序发生的一系列事件，而且具有如下特性：未来某一事件Ak+1发生的可能性只依赖于当前时刻的事件Ak ，而与过去发生的事件无关，即这时称n个事件具有马氏（Markov）独立性。 对n个满足马氏独立性条件的事件满足26定义4.6（全概率公式） 设Hi (i 0 。【注】：与不协调度相似，当m是概率分布时，混淆度即为不确定度（香农信息熵）。37 3、信息量 一个概念是内涵与外延的统一体。内涵的多少表示了信息量的大小，但是内涵一般是无法度量的。由于内涵与外延是某种相反关系，我们可用外延补集作为信息，用外延补集的测度作为信息量。于是就得到如下信息

14、量的概念。定义4.19 (信息量) 设X是有限集，包含n个元素。P是X上的概率分布，称是X, P的信息量。其中，38 在不确定性推理过程中，经常遇到两类问题： (1) 匹配（检索）问题，需要相似度的概念； (2) 推理规则的条件与结论之间的蕴涵关系，就需要蕴涵度的概念。 经专家研究发现，相似度与蕴涵度的共性即为包含度。 【注】：本课件只简要介绍上述三个概念的定义，有关包含度理论的详细论述请参见文献： 张文修、梁怡不确定性推理原理，西安交通大学出版社，1996。补充说明：39 4、包含度 设X是一个普通集合，(X)表示X中所有子集的全体，(X)表示X中模糊集合的全体。 定义4.19 (包含度)：

15、设0(X)(X) ，对A, B 0(X) 有数D(B/A)对应，且满足： (1) 0 = D(B/A) H，令R(P; H)为从P推出 H的模糊关系R(P; H) = APAH = (xP, xH) / uR(xP, xH)uR(xP, xH) = uAp(xP) uAH(xH) 阶段二：推理合成规则（max-min复合运算）当实际的输入信息为模糊命题P时，则模糊推理的输出HAH = AP R(P; H) 可得69基于模糊关系的推理举例请参见高济教授编著的教材基于知识的软件智能化技术pp206-208有兴趣的同学可进一步参考张文修、梁怡编著的不确定性推理原理pp228-235中的“5-4 Ma

16、mdani模糊推理”基本要求：能熟练解答与高济教授教材中类似的模糊推理习题704.7.6 模糊推理的神经网络算法特别声明这一节属于补充材料，考试时不做要求 感兴趣的同学可参见张文修、梁怡编著的不确定性推理原理pp244-248中的“5-7 模糊推理的神经网络算法”模糊推理的神经网络算法思想将“Ai = Bi”规则作为第i个输入，则形成一个神经网络可通过神经网络的学习算法得到权重wi71模糊推理的神经网络算法学习过程当Y是单点集y时，训练模型为(A, B)，学习算法的过程如下：步1：给出初始权重w1和训练样本H=(A, B)步2：利用如下公式计算步3：若B(y) = B(y) ，则终止；否则，修正w1;步4：若上述过程进行到第k步，得到Wk=(wk1,wk2,wkn)，使得 则终止，其中，gk为形成的模糊测度，即 gk(i)= wki；否则，修正权重wki。【注】：权重修正方法详见张文修、梁怡编著的不确定性推理原理pp24672THANKS FOR Y