研究生人工智能引论课件

浙江大学研究生《人工智能引论》课件徐从富(CongfuXu)

PhD,AssociateProfessorEmail:xucongfu@InstituteofArtificialIntelligence,CollegeofComputerScience,ZhejiangUniversity,Hangzhou310027,P.R.ChinaMarch10,2002第一稿April18,2007第四次修改稿第四讲不确定性推理概述

(Chapter4UncertaintyReasoning)浙江大学研究生《人工智能引论》课件徐从富(CongfuXu1Outline本章的主要参考文献基本概念基本问题不确定性推理方法的分类不确定性度量的测度理论不确定性的其它度量方法Shannon信息熵及在决策树中的应用模糊推理Outline本章的主要参考文献2[1]王永庆.人工智能原理与方法.西安交通大学出版社,1998.pp156-252.(偏重基本概念)[2]张文修,梁怡.不确定性推理原理.西安交通大学出版社,1996.（偏重数学原理）[3]陆汝钤.人工智能(下册).

科学出版社,2000.pp1133-1170.（偏重Bayes概率推理、可信度、模糊推理）[4]史忠植.知识发现.清华大学出版社,2002.pp24-26,pp141-202.（偏重Roughset和贝叶斯网络）本章的主要参考文献[1]王永庆.人工智能原理与方法.西安交通大学出版社3[5]Mitchell,T.M.著,曾华军等译.机器学习.机械工业出版社,2003.pp112-143.（偏重贝叶斯学习）[6]Russell,S.,Norvig,P.ArtificialIntelligence:AModernApproach.人民邮电出版社,2002.pp413-522.（偏重贝叶斯网络及其应用）本章的主要参考文献（续）“BlessedisthenationwhoseGodistheLORD,thepeoplehechoseforhisinheritance.”

FromPSALMS33:12NIV

[5]Mitchell,T.M.著,曾华军等译.44.1.1精确推理的局限性推理依据已知事实（证据）、相关知识（规则）证明某个假设成立or不成立

精确推理及其不足将原本为不确定性的关系“硬性”转化为精确关系将原本不存在明确界限的事物“人为”划定界限歪曲了现实情况的本来面目舍弃了事物的某些重要属性失去了真实性4.1基本概念4.1.1精确推理的局限性4.1基本概念54.1.2不确定性推理的定义及意义1.定义也称“不精确性推理”从不确定性的初始证据（即已知事实）出发运用不确定性的知识（或规则）推出具有一定程度的不确定性但却是合理或近乎合理的结论2.意义使计算机对人类思维的模拟更接近于人类的真实思维过程4.1.2不确定性推理的定义及意义1.定义64.2不确定性推理中的基本问题不确定性的表示与度量不确定性匹配不确定性的传递算法不确定性的合成4.2不确定性推理中的基本问题不确定性的表示与度量74.2.1不确定性的表示与度量1.不确定性的表示选择不确定性表示方法时应考虑的因素充分考虑领域问题的特征恰当地描述具体问题的不确定性满足问题求解的实际需求便于推理过程中对不确定性的推算4.2.1不确定性的表示与度量1.不确定性的表示8不确定性的表示与度量（续1）2.不确定性的度量针对不同的领域问题采用不同的度量方法用不同的数值刻画不同的不确定性程度事先规定不确定性程度的取值范围3.常用的度量方法测度理论（基于概率统计的度量方法）Shannon信息熵其它度量方法……不确定性的表示与度量（续1）2.不确定性的度量9不确定性的表示与度量（续2）在选择不确定性度量方法时应考虑的因素：充分表达相应知识及证据不确定性的程度度量范围便于领域专家及用户估计不确定性便于计算过程中的不确定性传递，结论的不确定性度量不超出规定的范围度量的确定应直观，且有相应的理论依据不确定性的表示与度量（续2）在选择不确定性度量方法时应考虑的104.2.2不确定性匹配解决不确定性匹配的常用方法设计一个匹配算法用以计算相似度指定一个相似度的“限定”（即阈值）“TodowhatisrightandjustismoreacceptabletotheLORDthansacrifice.”

FromPROVERBS21:3NIV

4.2.2不确定性匹配“Todowhatisri114.2.3证据不确定性的组合单一证据&

组合证据单一证据：前提条件仅为一个简单条件组合证据：一个复合条件对应于一组证据前提条件用AND（与）或OR（或）把多个简单条件连接起来构成复合条件4.2.3证据不确定性的组合12（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为真的程度，如可信度、概率等。每组公式都有相应的适用范围和使用条件。常用的组合证据不确定性计算方法（1）最大最小法常用的组合证据不确定性计算方法134.2.4不确定性的传递包含两个子问题在每一步推理中，如何把证据及知识的不确定性传递给给结论在多步推理中，如何把初始证据的不确定性传递给最终结论4.2.4不确定性的传递144.2.5结论不确定性的合成用不同知识进行推理得到相同的结论同个结论的不确定性程度却不相同需要用合适的算法对它们进行合成4.2.5结论不确定性的合成154.3不确定性推理方法的分类4.3.1不确定性推理的两条研究路线模型方法在推理一级上扩展确定性推理不确定证据和知识与某种度量标准对应给出更新结论不确定性的算法构成相应的不确定性推理模型控制方法在控制策略一级上处理不确定性无统一的不确定性处理模型，其效果依赖于控制策略4.3不确定性推理方法的分类4.3.1不确定性推理164.3.2不确定性推理方法的分类不确定性推理模型方法控制方法数值方法非数值方法概率统计方法模糊推理方法粗糙集方法绝对概率方法贝叶斯方法证据理论方法HMM方法发生率计算相关性制导回溯、机缘控制、启发式搜索等可信度方法4.3.2不确定性推理方法的分类不确定性推理模型控制数值非174.3.3关于不确定性推理方法的说明数值方法对不确定性的一种定量表示和处理方法其研究及应用较多，已形成多种应用模型非数值方法除数值方法外的其它处理不确定性的模型方法典型代表：“发生率计算方法”，它采用集合来描述和处理不确定性，且满足概率推理的性质4.3.3关于不确定性推理方法的说明18关于不确定性推理方法的说明（续1）概率统计方法有完整、严密的数学理论为不确定性的合成与传递提供了现成的数学公式最早、最广泛地用于不确定性知识的表示与处理已成为不确定性推理的重要手段证据理论方法1967年Dempster首次提出，1976年Shafer完善可表示并处理“不知道”等不确定性信息关于不确定性推理方法的说明（续1）19关于不确定性推理方法的说明（续2）模糊推理方法可表示并处理由模糊性引起的不确定性已广泛应用于不确定性推理粗糙集理论方法1981年Z.Pawlak首次提出一种新的可表示并处理“含糊”等不确定性的数学方法可用于不确定性推理、数据挖掘等领域关于不确定性推理方法的说明（续2）204.4描述不确定性信息的测度理论4.4.1测度及其分类

设(X)是有限集合X上的子集合的全体，测度的定义如下：定义6.1（测度）若g:(X)[0,1]满足条件： (1)g(X)=1; (2)当AB=时，有 g(AB)=g(A)+g(B)+g(A)g(B)称为g测度。【注】：关于测度理论的详细论述请参见夏道行编著的《实变函数与泛函分析》，复旦大学出版社。4.4描述不确定性信息的测度理论21定义4.2（模糊测度）模糊测度被定义为一个映射M:(X)[0,1]具有如下性质：(1)有界性：M()=0,M(X)=1;(2)单调性：对任意A,B(X),AB时，有M(A)M(B)由模糊测度定义可知：

（1）有界性表示：一个非空元素不可能属于，它必然属于全集；（2）单调性表示：一个元素隶属于一个集合的确定度不大于它隶属于更大的一个集合的确定度。定义4.2（模糊测度）模糊测度被定义为一个映射22定理4.1当>-1时，测度g是模糊测度。定理4.2当>-1时，测度g具有如下性质：模糊测度及其性质定理4.1当>-1时，测度g是模糊测度。模糊测度23定义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上的概率测度，EX，且P(E)>0，称为给定条件E下，事件A发生的条件概率。定义4.3（概率测度）称P：(X）→[0，1]为24

对于条件概率有如下联合概率公式：

若A1,A2,...,An为X中的n个事件，可得

若A,B两个事件满足P(A|B)=P(A)，即A发生的可能性与B无关，称A,B是相互独立的。这时有

若n个事件A1,A2,...,An相互独立，则对于条件概率有如下联合概率公式：若A1,25Markov条件独立性定义4.5(马氏条件独立性)若A1,A2,...,An是按时间顺序发生的一系列事件，而且具有如下特性：未来某一事件Ak+1发生的可能性只依赖于当前时刻的事件Ak，而与过去发生的事件无关，即这时称n个事件具有马氏（Markov）独立性。对n个满足马氏独立性条件的事件满足Markov条件独立性定义4.5(马氏条件独立性)26定义4.6（全概率公式）设Hi(i<=m)是X上的分划，HiHj(ij)，且H1H2…

Hm=X。由概率可加性，对于任意事件A，有

对于条件概率有如下全概率公式：

定义4.7

(后验概率公式）

：Bayes公式定义4.6（全概率公式）设Hi(i<=m)是X上的分27Bayes公式与全概率公式的区别全概率公式由原因到结果的计算公式不如Bayes公式使用广泛Bayes公式后验概率公式已知某结果发生，寻求这个结果发生的原因在实际问题中有着十分重要的应用Bayes公式与全概率公式的区别28定义4.8（信任测度）设X是有限集，称B：(X)[0,1]为信任测度，若满足：(1)B()=0,B(X)=1;(2)对于X中任意子集A1，A2，…，An有如果仅仅满足，对于X中任意两个子集A1及A2有称为弱信任测度。【注】：可证明信任测度与弱信任测度都是模糊测度。信任测度是证据理论的最基础概念。定义4.8（信任测度）设X是有限集，称B：(X)29定义4.9（似然测度）设X是有限集，称L：(X)[0,1]为似然测度，若满足：(1)L()=0,L(X)=1;(2)对于X中任意子集A1，A2，…，An有如果仅仅满足，对于X中任意两个子集A1及A2有称为弱似然测度。【注】：可证明似然测度与弱似然测度都是模糊测度。似然测度是证据理论的最基础概念。定义4.9（似然测度）设X是有限集，称L：(X)30定义4.10（mass函数）称m：(X)→[0，1]是mass函数，若满足：（1）m(Ф)=0（2）mass函数是专家的一种评价或确认程度。比如X={x1,x2,…,xn}是n中疾病，某专家认为某人得疾病x1的可能性为0.7，于是得到一个mass函数：在证据理论中，mass函数对构造信任测度与似然测度中有着重要的作用。定义4.10（mass函数）称m：(X)→[0，1]是m31定义4.11（必然性测度）设X是有限集，称N：(X)[0,1]为必然性测度，若满足：(1)N()=0,N(X)=1;(2)N(AB)=N(A)N(B)定义4.12（可能性测度）设X是有限集，称：(X)[0,1]为可能性测度，若满足：(1)()=0,(X)=1;(2)(AB)=(A)(B)【注】：可证明必然测度与可能性测度都是模糊测度。它们是Zadel提出的可能性理论的最基础概念。定义4.11（必然性测度）设X是有限集，称N：(X)32概率测度必然测度可能测度信任测度似然测度模糊测度各种模糊测度之间的关系示意图4.4.2模糊测度各类之间的关系概率测度必然测度可能测度信任测度似然测度模糊测度各种模糊测度33模糊测度各类之间的关系（续）模糊测度是一大类测度，它除了有界性条件外，只要求测度满足单调性，即当AB时，有M(A)M(B)。上述各类模糊测度之间的关系如下：必然性测度一定是信任测度可能性测度一定是似然测度概率测度是信任测度与似然测度的交集……模糊测度各类之间的关系（续）模糊测度是一大类测度，344.5不确定性的其它度量方法1、不协调度定义4.17(不协调度)设m是X上的mass函数，L为由m生成的似然测度，即称为[X,m]的不协调度。4.5不确定性的其它度量方法称为[X,m]的不协调度。35若m是X上的概率分布，即这时信任测度与似然测度均为概率测度，于是显然，这时的不协调度与香农信息量（即信息熵）一致。此时的不协调度就是不确定度。不协调度（续）若m是X上的概率分布，即这时信任测度与似然测度均为概率测度，362、混淆度

定义4.18(混淆度)设m是X上的mass函数，B为由m生成的信任测度，即称为[X,m]的混淆度。其中，={A|m(A)>0}。【注】：与不协调度相似，当m是概率分布时，混淆度即为不确定度（香农信息熵）。2、混淆度称为[X,m]的混淆度。其中，={A|373、信息量

一个概念是内涵与外延的统一体。内涵的多少表示了信息量的大小，但是内涵一般是无法度量的。由于内涵与外延是某种相反关系，我们可用外延补集作为信息，用外延补集的测度作为信息量。于是就得到如下信息量的概念。定义4.19(信息量)设X是有限集，包含n个元素。P是X上的概率分布，称是[X,P]的信息量。其中，3、信息量是[X,P]的信息量。其中，38

在不确定性推理过程中，经常遇到两类问题：(1)匹配（检索）问题，需要相似度的概念；(2)推理规则的条件与结论之间的蕴涵关系，就需要蕴涵度的概念。经专家研究发现，相似度与蕴涵度的共性即为包含度。【注】：本课件只简要介绍上述三个概念的定义，有关包含度理论的详细论述请参见文献：张文修、梁怡《不确定性推理原理》，西安交通大学出版社，1996。补充说明：在不确定性推理过程中，经常遇到两类问题：补充说明394、包含度

设X是一个普通集合，(X)表示X中所有子集的全体，(X)表示X中模糊集合的全体。定义4.19(包含度)：设0(X)(X)，对A,B0(X)有数D(B/A)对应，且满足：

(1)0<=D(B/A)<=1

(2)对A,B0(X),A

B时，有D(B/A)=1

(3)对A,B,C0(X),A

B

C时，有 D(A/C)D(A/B)称D为0(X)上的包含度。【注】：关于包含度的数学原理请详见张文修《不确定性推理原理》。BACX4、包含度BACX404.6.1Shannon信息论信息论的创立1948年Shannon首次提出以数学方法度量并研究通信信号

信息论对不确定性推理的作用为不确定性知识的度量提供理论依据用信息熵来衡量不确定性程度的高低在决策树等方法中发挥重要作用4.6信息论及其在决策树中的应用4.6.1Shannon信息论4.6信息论及其在决策414.6.2信息论中的基本概念定义4.13（自信息量）在收到ai之前，收信者对信源发出ai的不确定性定义为信息符号ai的自信息量I(ai)。即其中，p(ai)为信源发出ai的概率，为表达简便起见，本课件的对数lg均以2为底。

【说明】:（1）自信息量只能反映符号的不确定性。（2）有的文献采用以10或e为底的对数，但是在某个具体的信息系统中，一旦确定并保持某个底数，对不确定性信息的度量和计算不会有任何影响。4.6.2信息论中的基本概念其中，p(ai)为信源发出a42定义4.14（信息熵）设r为信源X所有可能的符号数，p(ai)为信源发出ai的概率，则信源每发一个符号所提供的平均自信息量即为信息熵。【说明】：（1）信息熵也称香农信息量，或称不确定度。（2）信息熵可用来度量整个信源X整体的不确定性。Shannon信息熵定义4.14（信息熵）设r为信源X所有可能的符号数，43定义4.15（条件熵）如果信源X与随机变量Y不是相互独立的，那么用条件熵H(X|Y)来度量收信者在收到随机变量Y之后，对随机变量X仍然存在的不确定性。设X对应信源符号ai，Y对应信源符号bj，p(ai|bj)为当Y为bj时X为ai的概率，则有可得由于定义4.15（条件熵）如果信源X与随机变量Y不是相互44定义4.16（平均互信息量，也称信息论测度值）表示信号Y所能提供的关于X的信息量的大小，用I(X,Y)表示【说明】：信息论在决策树学习中具有非常重要的意义。在决策树学习方法中，最关键的问题就是如何根据每个属性提供的信息量构造出一棵决策树，以此对整个实例空间进行合理的分类（划分）。平均互信息量定义4.16（平均互信息量，也称信息论测度值）表示信454.6.3信息论在决策树中的应用

设训练实例集为X，目的是将训练实例分为n类。设属于第i类的训练实例个数是Ci，X中总的训练实例个数为|X|，若记一个实例属于第i类的概率为P(Ci)，则此时，决策树对划分C的不确定程度为：【注意】：在无混淆的情况下，习惯将H(X,C)简记为H(X)。4.6.3信息论在决策树中的应用此时，决策树对划分C的不46

决策树学习过程就是使得决策树对划分的不确定程度逐渐减小的过程。大致过程如下：

（1）选择测试属性a进行测试，在得知a=aj的情况下，属于第i类的实例个数为Cij个。记p(Ci;a=aj)=Cij/|X|p(Ci;a=aj)为在测试属性a的取值为aj时它属于第i类的概率。此时决策树对分类的不确定程度就是训练实例集对属性X的条件熵。决策树的学习过程决策树学习过程就是使得决策树对划分的不确定程度47训练实例集对属性X的条件熵的计算公式即训练实例集对属性X的条件熵的计算公式即48可知属性a对于分类提供的信息量I(X;a)为：（2）信息量I(X;a)的值越大，说明选择测试属性a对于分类提供的信息量越大，选择属性a之后对分类的不确定程度越小。（3）依次类推，不断地计算剩余样本的条件熵及信息量，直至构造出完整的决策树。决策树的学习过程（续）可知属性a对于分类提供的信息量I(X;a)为：（2）494.6.4信息熵在决策树中的应用实例—ID3算法属性Outlook TemperatureHumidity Windy类

Overcast Hot HighNotN

Overcast Hot HighVeryN

OvercastHot High MediumNSunny Hot HighNotPSunny Hot High MediumPRain Mild High NotNRain Mild High MediumNRain Hot NormalNotPRain Cool NormalMediumNRain Hot NormalVeryNSunny Cool NormalVeryPSunny Cool NormalMediumP4.6.4信息熵在决策树中的应用实例—ID3算法属性5013 Overcast Mild High Not N14Overcast Mild High MediumN15

Overcast Cool NormalNotP16 Overcast Cool NormalMediumP17Rain Mild NormalNotN18Rain Mild NormalMediumN19Overcast Mild NormalMediumP20Overcast Mild NormalVeryP21Sunny Mild High Veryp22Sunny Mild High MediumP23Sunny Hot NormalNotP24Rain Mild High VeryN属性Outlook TemperatureHumidityWindy类（续上表）13 Overcast Mild Hig51在决策树方法中，所要做的工作就是构造决策树将数据进行分类。因初始时属于P类和N类的实例个数均为12，故初始熵值为：(1)若选择Outlook作为测试属性，其条件熵为：本实例中的条件熵计算过程在决策树方法中，所要做的工作就是构造决策树将数据进行52(2)若选择Temp作为测试属性，其条件熵为：(3)若选择Humidity作为测试属性，其条件熵为：(2)若选择Temp作为测试属性，其条件熵为：(3)若选53(4)若选择Windy作为测试属性，其条件熵为：

由上述计算结果可知：

（1）H(X|Outlook)最小，即有关Outlook的信息对于分类有最大的帮助，提供最大的信息量，故应选择Outlook属性作为测试属性。（2）H(X)=H(X|Windy),即I(X;Windy)=0，说明有关Windy的信息不能提供任何分类信息。（3）选择Outlook作为测试属性之后，将训练实例集分为三个子集，即生成三个节点，分别对每个节点依次利用上述过程，即可生成决策树：(4)若选择Windy作为测试属性，其条件熵为：54HumidityPOutlookWindyNPTempNNNNNSunnyOvercastRainHighNormalNotMediumVeryCoolMildHot依据信息熵对上述实例集进行训练所生成的决策树HumidityPOutlookWindyNPTempNNN55【补充说明】：

（1）有关“决策树”（Decisiontree）的详细内容，请参见史忠植《知识发现》（清华大学出版社，2002年）中的“第2章决策树”（pp21-56）和《高级人工智能》中的“决策树学习”pp116-121。（2）决策树方法的几个有代表性的研究成果分别是：

a)1966年Hunt等人提出的早期决策树学习算法——CLS学习算法；

b)1979年Quinlan提出的以信息熵的下降速度作为选取测试属性的标准的ID3算法。

c)1986年Schlimmer等人构造了ID4算法，该算法允许递增式构造决策树。d)1986年Utgoff提出ID5算法，它允许通过修改决策树来增加新的训练实例，而无需重建决策树。【补充说明】：56[1]QuinlanJ.R.Discoveringrulesfromlargecollectionsofexamples:acasestudy.In:MichieD.ed.ExpertSystemsintheMicroElectronicAge,EdinburghUniversityPress,1979.[2]QuinlanJ.R.Learningefficientclassificationproceduresandtheirapplicationtochessandgames.In:Michalski,R.S.etc,eds.MachineLearning:AnArtificialIntelligenceApproach,Tioga,1983.[3]QuinlanJ.R.Inductionofdecisiontrees.MachineLearning,1986,1(1):81.与决策树相关的经典文献[1]QuinlanJ.R.Discovering57[4]Schlimmer,J.C.,Fisher,D.Acasestudyofincrementalconceptinduction.in:ProceedingsofAAAI-86,1986.[5]Schlimmer,J.C.,Grander,R.H.Incrementallearningfromnoisydata.MachineLearning,1987,1(3):318.[6]Utgoff,P.E.ID5:AnincrementalID3.in:ProceedingsofICML-88,SanMateo,CA,1988.[7]Utgoff,P.E.Perceptrontrees:Acasestudyinhybridconceptrepresentations.in:ProceedingsofAAAI-88,SaintPaul,Minnesota,1988.与决策树相关的经典文献（续）[4]Schlimmer,J.C.,Fisher,584.7

模糊推理主要参考文献模糊推理的发展简况模糊集合及其运算模糊逻辑模糊推理模糊推理的神经网络算法4.7模糊推理主要参考文献594.7.1主要参考文献高济.基于知识的软件智能化技术.浙江大学出版社,2000.pp.201-213张文修,梁怡.不确定性推理原理.西安交通大学出版社,1996.pp.207-2544.7.1主要参考文献高济.基于知识的软件智能化技术.604.7.2模糊推理的发展简况1965，L.A.Zadeh发表“FuzzySets”论文，提出模糊集理论1966，Marinos首先提出“模糊逻辑”的概念1969，Guguen研究不精确概念的逻辑问题后来，Zadeh又提出可能度理论随后，Dubois&Prade发展了基于可能度的模糊推理1974，E.H.Mamdani提出了模糊控制，并给出著名的Mamdani算法4.7.2模糊推理的发展简况1965，L.A.Zad614.7.3模糊集合及其运算基本思想把传统集合论中由特征函数决定的绝对隶属关系模糊化元素x对子集A的隶属度可[0,1]上的任何值，以指示元素x隶属于子集A的模糊程度定义在论域U上定义一个模糊集A，其对U的任意元素x均指定一个值uA(x)∈[0,1]，以表示它对A的隶属程度

uA：→

[0,1]

（uA—A的隶属函数）

A

={x/uA(x)}4.7.3模糊集合及其运算基本思想62模糊集合及其运算（续1）当U={x1,x2,…,xn}，模糊集A可表示为

A

=x1/uA(x1)+x2/uA(x2)+…+xn/uA(xn)uA(xi)=0的项可省略隶属度的概念是构成模糊集理论的基石模糊集运算公式uA∪B(x)=max[uA(x),uB(x)]uA∩B(x)=min[uA(x),uB(x)]u~A(x)=1-uA(x)模糊集合及其运算（续1）当U={x1,x2,…,x63模糊集合及其运算（续2）模糊集隶属函数举例论域：人的年龄以定性（模糊）术语描述年龄，值域为：年龄={青，中，老}隶属函数：uY,uM,uO图形表示01305065YMOu年龄（岁）模糊集合及其运算（续2）模糊集隶属函数举例01305065Y644.7.4模糊逻辑基本思想由定性术语构成模糊命题定性术语由隶属函数表示对模糊命题进行合取、析取、取反等逻辑操作基本公式uP∨

=max[uP1(xp1),uP2(xp2),…,uPm(xpm)](析取)uP∧

=min[uP1(xp1),uP2(xp2),…,uPm(xpm)]（合取）u~Pi(xpi)=1-uPi(xpi)（取反）4.7.4模糊逻辑基本思想654.7.5模糊推理模糊关系uR:U1×U2×…×Un→[0,1]R={(XU1,XU2,…,XUn)/uR(XU1,XU2,…,XUn)}模糊推理方法主流方法：基于max-min原则的算法直接基于模糊规则的推理基于模糊关系的推理4.7.5模糊推理模糊关系66直接基于模糊规则的推理适用条件：当模糊推理的输入信息为量化数值时推理原理阶段一：计算每条模糊规则的结论步骤1：输入量模糊化，即求出输入量相对于语言变量各定性值的隶属度步骤2：计算规则前提部分模糊命题的逻辑组合步骤3：将规则前提逻辑组合的隶属度与结论命题的隶属函数做min运算，求得结论的模糊程度。阶段二对所有规则结论的模糊程度做max运算，得到模糊推理结果。直接基于模糊规则的推理适用条件：当模糊推理的输入信息为量化数67直接基于模糊规则的推理举例请参见高济教授编著的教材《基于知识的软件智能化技术》pp205-206基本要求：能熟练解答类似的模糊推理习题直接基于模糊规则的推理举例请参见高济教授编著的教材《基于知识68基于模糊关系的推理适用条件：当模糊推理的输入信息为定性术语时Mamdani模糊推理方法阶段一：关系生成规则模糊规则为：P=>H，令R(P;H)为从P推出H的模糊关系R(P;H)=AP×AH={(xP,xH)/uR(xP,xH)}uR(xP,xH)=uAp(xP)∧uAH(xH)阶段二：推理合成规则（max-min复合运算）当实际的输入信息为模糊命题P’时，则模糊推理的输出H’AH’=AP’

·R(P;H)可得基于模糊关系的推理适用条件：当模糊推理的输入信息为定性术语时69基于模糊关系的推理举例请参见高济教授编著的教材《基于知识的软件智能化技术》pp206-208有兴趣的同学可进一步参考张文修、梁怡编著的《不确定性推理原理》pp228-235中的“5-4Mamdani模糊推理”基本要求：能熟练解答与高济教授教材中类似的模糊推理习题基于模糊关系的推理举例请参见高济教授编著的教材《基于知识的软704.7.6模糊推理的神经网络算法特别声明这一节属于补充材料，考试时不做要求感兴趣的同学可参见张文修、梁怡编著的《不确定性推理原理》pp244-248中的“5-7模糊推理的神经网络算法”模糊推理的神经网络算法思想将“Ai=>Bi”规则作为第i个输入，则形成一个神经网络可通过神经网络的学习算法得到权重wi4.7.6模糊推理的神经网络算法特别声明71模糊推理的神经网络算法学习过程当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。【注】：权重修正方法详见张文修、梁怡编著的《不确定性推理原理》pp246模糊推理的神经网络算法学习过程当Y是单点集{y}时，训练模型72THANKSFORYOURPRESENCE!“Butseekfirsthiskingdomandhisrighteousness,andallthesethingswillbegiventoyouaswell.Thereforedonotworryabouttomorrow,fortomorrowwillworryaboutitself.Eachdayhasenoughtroubleofitsown.”

fromMATTHEW6:33-34NIVTHANKSFORYOURPRESENCE!“But73浙江大学研究生《人工智能引论》课件徐从富(CongfuXu)

PhD,AssociateProfessorEmail:xucongfu@InstituteofArtificialIntelligence,CollegeofComputerScience,ZhejiangUniversity,Hangzhou310027,P.R.ChinaMarch10,2002第一稿April18,2007第四次修改稿第四讲不确定性推理概述

(Chapter4UncertaintyReasoning)浙江大学研究生《人工智能引论》课件徐从富(CongfuXu74Outline本章的主要参考文献基本概念基本问题不确定性推理方法的分类不确定性度量的测度理论不确定性的其它度量方法Shannon信息熵及在决策树中的应用模糊推理Outline本章的主要参考文献75[1]王永庆.人工智能原理与方法.西安交通大学出版社,1998.pp156-252.(偏重基本概念)[2]张文修,梁怡.不确定性推理原理.西安交通大学出版社,1996.（偏重数学原理）[3]陆汝钤.人工智能(下册).

科学出版社,2000.pp1133-1170.（偏重Bayes概率推理、可信度、模糊推理）[4]史忠植.知识发现.清华大学出版社,2002.pp24-26,pp141-202.（偏重Roughset和贝叶斯网络）本章的主要参考文献[1]王永庆.人工智能原理与方法.西安交通大学出版社76[5]Mitchell,T.M.著,曾华军等译.机器学习.机械工业出版社,2003.pp112-143.（偏重贝叶斯学习）[6]Russell,S.,Norvig,P.ArtificialIntelligence:AModernApproach.人民邮电出版社,2002.pp413-522.（偏重贝叶斯网络及其应用）本章的主要参考文献（续）“BlessedisthenationwhoseGodistheLORD,thepeoplehechoseforhisinheritance.”

FromPSALMS33:12NIV

[5]Mitchell,T.M.著,曾华军等译.774.1.1精确推理的局限性推理依据已知事实（证据）、相关知识（规则）证明某个假设成立or不成立

精确推理及其不足将原本为不确定性的关系“硬性”转化为精确关系将原本不存在明确界限的事物“人为”划定界限歪曲了现实情况的本来面目舍弃了事物的某些重要属性失去了真实性4.1基本概念4.1.1精确推理的局限性4.1基本概念784.1.2不确定性推理的定义及意义1.定义也称“不精确性推理”从不确定性的初始证据（即已知事实）出发运用不确定性的知识（或规则）推出具有一定程度的不确定性但却是合理或近乎合理的结论2.意义使计算机对人类思维的模拟更接近于人类的真实思维过程4.1.2不确定性推理的定义及意义1.定义794.2不确定性推理中的基本问题不确定性的表示与度量不确定性匹配不确定性的传递算法不确定性的合成4.2不确定性推理中的基本问题不确定性的表示与度量804.2.1不确定性的表示与度量1.不确定性的表示选择不确定性表示方法时应考虑的因素充分考虑领域问题的特征恰当地描述具体问题的不确定性满足问题求解的实际需求便于推理过程中对不确定性的推算4.2.1不确定性的表示与度量1.不确定性的表示81不确定性的表示与度量（续1）2.不确定性的度量针对不同的领域问题采用不同的度量方法用不同的数值刻画不同的不确定性程度事先规定不确定性程度的取值范围3.常用的度量方法测度理论（基于概率统计的度量方法）Shannon信息熵其它度量方法……不确定性的表示与度量（续1）2.不确定性的度量82不确定性的表示与度量（续2）在选择不确定性度量方法时应考虑的因素：充分表达相应知识及证据不确定性的程度度量范围便于领域专家及用户估计不确定性便于计算过程中的不确定性传递，结论的不确定性度量不超出规定的范围度量的确定应直观，且有相应的理论依据不确定性的表示与度量（续2）在选择不确定性度量方法时应考虑的834.2.2不确定性匹配解决不确定性匹配的常用方法设计一个匹配算法用以计算相似度指定一个相似度的“限定”（即阈值）“TodowhatisrightandjustismoreacceptabletotheLORDthansacrifice.”

FromPROVERBS21:3NIV

4.2.2不确定性匹配“Todowhatisri844.2.3证据不确定性的组合单一证据&

组合证据单一证据：前提条件仅为一个简单条件组合证据：一个复合条件对应于一组证据前提条件用AND（与）或OR（或）把多个简单条件连接起来构成复合条件4.2.3证据不确定性的组合85（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为真的程度，如可信度、概率等。每组公式都有相应的适用范围和使用条件。常用的组合证据不确定性计算方法（1）最大最小法常用的组合证据不确定性计算方法864.2.4不确定性的传递包含两个子问题在每一步推理中，如何把证据及知识的不确定性传递给给结论在多步推理中，如何把初始证据的不确定性传递给最终结论4.2.4不确定性的传递874.2.5结论不确定性的合成用不同知识进行推理得到相同的结论同个结论的不确定性程度却不相同需要用合适的算法对它们进行合成4.2.5结论不确定性的合成884.3不确定性推理方法的分类4.3.1不确定性推理的两条研究路线模型方法在推理一级上扩展确定性推理不确定证据和知识与某种度量标准对应给出更新结论不确定性的算法构成相应的不确定性推理模型控制方法在控制策略一级上处理不确定性无统一的不确定性处理模型，其效果依赖于控制策略4.3不确定性推理方法的分类4.3.1不确定性推理894.3.2不确定性推理方法的分类不确定性推理模型方法控制方法数值方法非数值方法概率统计方法模糊推理方法粗糙集方法绝对概率方法贝叶斯方法证据理论方法HMM方法发生率计算相关性制导回溯、机缘控制、启发式搜索等可信度方法4.3.2不确定性推理方法的分类不确定性推理模型控制数值非904.3.3关于不确定性推理方法的说明数值方法对不确定性的一种定量表示和处理方法其研究及应用较多，已形成多种应用模型非数值方法除数值方法外的其它处理不确定性的模型方法典型代表：“发生率计算方法”，它采用集合来描述和处理不确定性，且满足概率推理的性质4.3.3关于不确定性推理方法的说明91关于不确定性推理方法的说明（续1）概率统计方法有完整、严密的数学理论为不确定性的合成与传递提供了现成的数学公式最早、最广泛地用于不确定性知识的表示与处理已成为不确定性推理的重要手段证据理论方法1967年Dempster首次提出，1976年Shafer完善可表示并处理“不知道”等不确定性信息关于不确定性推理方法的说明（续1）92关于不确定性推理方法的说明（续2）模糊推理方法可表示并处理由模糊性引起的不确定性已广泛应用于不确定性推理粗糙集理论方法1981年Z.Pawlak首次提出一种新的可表示并处理“含糊”等不确定性的数学方法可用于不确定性推理、数据挖掘等领域关于不确定性推理方法的说明（续2）934.4描述不确定性信息的测度理论4.4.1测度及其分类

设(X)是有限集合X上的子集合的全体，测度的定义如下：定义6.1（测度）若g:(X)[0,1]满足条件： (1)g(X)=1; (2)当AB=时，有 g(AB)=g(A)+g(B)+g(A)g(B)称为g测度。【注】：关于测度理论的详细论述请参见夏道行编著的《实变函数与泛函分析》，复旦大学出版社。4.4描述不确定性信息的测度理论94定义4.2（模糊测度）模糊测度被定义为一个映射M:(X)[0,1]具有如下性质：(1)有界性：M()=0,M(X)=1;(2)单调性：对任意A,B(X),AB时，有M(A)M(B)由模糊测度定义可知：

（1）有界性表示：一个非空元素不可能属于，它必然属于全集；（2）单调性表示：一个元素隶属于一个集合的确定度不大于它隶属于更大的一个集合的确定度。定义4.2（模糊测度）模糊测度被定义为一个映射95定理4.1当>-1时，测度g是模糊测度。定理4.2当>-1时，测度g具有如下性质：模糊测度及其性质定理4.1当>-1时，测度g是模糊测度。模糊测度96定义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上的概率测度，EX，且P(E)>0，称为给定条件E下，事件A发生的条件概率。定义4.3（概率测度）称P：(X）→[0，1]为97

对于条件概率有如下联合概率公式：

若A1,A2,...,An为X中的n个事件，可得

若A,B两个事件满足P(A|B)=P(A)，即A发生的可能性与B无关，称A,B是相互独立的。这时有

若n个事件A1,A2,...,An相互独立，则对于条件概率有如下联合概率公式：若A1,98Markov条件独立性定义4.5(马氏条件独立性)若A1,A2,...,An是按时间顺序发生的一系列事件，而且具有如下特性：未来某一事件Ak+1发生的可能性只依赖于当前时刻的事件Ak，而与过去发生的事件无关，即这时称n个事件具有马氏（Markov）独立性。对n个满足马氏独立性条件的事件满足Markov条件独立性定义4.5(马氏条件独立性)99定义4.6（全概率公式）设Hi(i<=m)是X上的分划，HiHj(ij)，且H1H2…

Hm=X。由概率可加性，对于任意事件A，有

对于条件概率有如下全概率公式：

定义4.7

(后验概率公式）

：Bayes公式定义4.6（全概率公式）设Hi(i<=m)是X上的分100Bayes公式与全概率公式的区别全概率公式由原因到结果的计算公式不如Bayes公式使用广泛Bayes公式后验概率公式已知某结果发生，寻求这个结果发生的原因在实际问题中有着十分重要的应用Bayes公式与全概率公式的区别101定义4.8（信任测度）设X是有限集，称B：(X)[0,1]为信任测度，若满足：(1)B()=0,B(X)=1;(2)对于X中任意子集A1，A2，…，An有如果仅仅满足，对于X中任意两个子集A1及A2有称为弱信任测度。【注】：可证明信任测度与弱信任测度都是模糊测度。信任测度是证据理论的最基础概念。定义4.8（信任测度）设X是有限集，称B：(X)102定义4.9（似然测度）设X是有限集，称L：(X)[0,1]为似然测度，若满足：(1)L()=0,L(X)=1;(2)对于X中任意子集A1，A2，…，An有如果仅仅满足，对于X中任意两个子集A1及A2有称为弱似然测度。【注】：可证明似然测度与弱似然测度都是模糊测度。似然测度是证据理论的最基础概念。定义4.9（似然测度）设X是有限集，称L：(X)103定义4.10（mass函数）称m：(X)→[0，1]是mass函数，若满足：（1）m(Ф)=0（2）mass函数是专家的一种评价或确认程度。比如X={x1,x2,…,xn}是n中疾病，某专家认为某人得疾病x1的可能性为0.7，于是得到一个mass函数：在证据理论中，mass函数对构造信任测度与似然测度中有着重要的作用。定义4.10（mass函数）称m：(X)→[0，1]是m104定义4.11（必然性测度）设X是有限集，称N：(X)[0,1]为必然性测度，若满足：(1)N()=0,N(X)=1;(2)N(AB)=N(A)N(B)定义4.12（可能性测度）设X是有限集，称：(X)[0,1]为可能性测度，若满足：(1)()=0,(X)=1;(2)(AB)=(A)(B)【注】：可证明必然测度与可能性测度都是模糊测度。它们是Zadel提出的可能性理论的最基础概念。定义4.11（必然性测度）设X是有限集，称N：(X)105概率测度必然测度可能测度信任测度似然测度模糊测度各种模糊测度之间的关系示意图4.4.2模糊测度各类之间的关系概率测度必然测度可能测度信任测度似然测度模糊测度各种模糊测度106模糊测度各类之间的关系（续）模糊测度是一大类测度，它除了有界性条件外，只要求测度满足单调性，即当AB时，有M(A)M(B)。上述各类模糊测度之间的关系如下：必然性测度一定是信任测度可能性测度一定是似然测度概率测度是信任测度与似然测度的交集……模糊测度各类之间的关系（续）模糊测度是一大类测度，1074.5不确定性的其它度量方法1、不协调度定义4.17(不协调度)设m是X上的mass函数，L为由m生成的似然测度，即称为[X,m]的不协调度。4.5不确定性的其它度量方法称为[X,m]的不协调度。108若m是X上的概率分布，即这时信任测度与似然测度均为概率测度，于是显然，这时的不协调度与香农信息量（即信息熵）一致。此时的不协调度就是不确定度。不协调度（续）若m是X上的概率分布，即这时信任测度与似然测度均为概率测度，1092、混淆度

定义4.18(混淆度)设m是X上的mass函数，B为由m生成的信任测度，即称为[X,m]的混淆度。其中，={A|m(A)>0}。【注】：与不协调度相似，当m是概率分布时，混淆度即为不确定度（香农信息熵）。2、混淆度称为[X,m]的混淆度。其中，={A|1103、信息量

一个概念是内涵与外延的统一体。内涵的多少表示了信息量的大小，但是内涵一般是无法度量的。由于内涵与外延是某种相反关系，我们可用外延补集作为信息，用外延补集的测度作为信息量。于是就得到如下信息量的概念。定义4.19(信息量)设X是有限集，包含n个元素。P是X上的概率分布，称是[X,P]的信息量。其中，3、信息量是[X,P]的信息量。其中，111

在不确定性推理过程中，经常遇到两类问题：(1)匹配（检索）问题，需要相似度的概念；(2)推理规则的条件与结论之间的蕴涵关系，就需要蕴涵度的概念。经专家研究发现，相似度与蕴涵度的共性即为包含度。【注】：本课件只简要介绍上述三个概念的定义，有关包含度理论的详细论述请参见文献：张文修、梁怡《不确定性推理原理》，西安交通大学出版社，1996。补充说明：在不确定性推理过程中，经常遇到两类问题：补充说明1124、包含度

设X是一个普通集合，(X)表示X中所有子集的全体，(X)表示X中模糊集合的全体。定义4.19(包含度)：设0(X)(X)，对A,B0(X)有数D(B/A)对应，且满足：

(1)0<=D(B/A)<=1

(2)对A,B0(X),A

B时，有D(B/A)=1

(3)对A,B,C0(X),A

B

C时，有 D(A/C)D(A/B)称D为0(X)上的包含度。【注】：关于包含度的数学原理请详见张文修《不确定性推理原理》。BACX4、包含度BACX1134.6.1Shannon信息论信息论的创立1948年Shannon首次提出以数学方法度量并研究通信信号

信息论对不确定性推理的作用为不确定性知识的度量提供理论依据用信息熵来衡量不确定性程度的高低在决策树等方法中发挥重要作用4.6信息论及其在决策树中的应用4.6.1Shannon信息论4.6信息论及其在决策1144.6.2信息论中的基本概念定义4.13（自信息量）在收到ai之前，收信者对信源发出ai的不确定性定义为信息符号ai的自信息量I(ai)。即其中，p(ai)为信源发出ai的概率，为表达简便起见，本课件的对数lg均以2为底。

【说明】:（1）自信息量只能反映符号的不确定性。（2）有的文献采用以10或e为底的对数，但是在某个具体的信息系统中，一旦确定并保持某个底数，对不确定性信息的度量和计算不会有任何影响。4.6.2信息论中的基本概念其中，p(ai)为信源发出a115定义4.14（信息熵）设r为信源X所有可能的符号数，p(ai)为信源发出ai的概率，则信源每发一个符号所提供的平均自信息量即为信息熵。【说明】：（1）信息熵也称香农信息量，或称不确定度。（2）信息熵可用来度量整个信源X整体的不确定性。Shannon信息熵定义4.14（信息熵）设r为信源X所有可能的符号数，116定义4.15（条件熵）如果信源X与