人工智能课件3-推理

第7章高级知识推理高级知识推理经典逻辑确定性推理单调性推理归约推理肖解演绎推理规则演绎推理非经典逻辑不确定性推理非单调性推理时序推理概率推理经典逻辑与非经典逻辑的不同

经典非经典推理方法演绎逻辑归纳逻辑辖域取值二值多值模糊运算法则有些不成立逻辑算符逻辑算符引入模态算符单调性单调非单调单调推理和非单调推理单调推理基于谓词逻辑的推理系统是单调的系统中已知为真的命题随着推理的进行而增加,结论越来越多非单调推理推理系统的定理集合不随推理过程的进行而单调增大新推理出的定理可能修正以至否定原有的一些定理,使得原来能够解释的一些现象变得不可解释.

非单调推理非单调推理用来处理那些不适合用谓词逻辑表示的知识。它能够较好地处理不完全信息、不断变化的情况以及求解复杂问题过程中生成的假设，具有较为有效的求解效率。缺省推理在没有证据能够证明某命题不成立时,就承认该命题成立.不具备命题的全部知识,也能够进行合理的推理并给出正确的结论定义如果X不知道，那么得结论Y。如果X不能被证明，那么得结论Y。如果X不能在某个给定的时间内被证明，那么得结论Y。不确定性推理精确推理的局限性推理依据已知事实（证据）、相关知识（规则）证明某个假设成立or不成立精确推理及其不足将原本为不确定性的关系“硬性”转化为精确关系将原本不存在明确界限的事物“人为”划定界限歪曲了现实情况的本来面目舍弃了事物的某些重要属性失去了真实性不确定性推理的定义及意义1.定义也称“不精确性推理”从不确定性的初始证据（即已知事实）出发运用不确定性的知识（或规则）推出具有一定程度的不确定性但却是合理或近乎合理的结论2.意义使计算机对人类思维的模拟更接近于人类的真实思维过程不确定性推理的定义及意义不确定性推理中的基本问题不确定性的表示与度量不确定性匹配不确定性的传递算法不确定性的合成不确定性的表示与度量1.不确定性的表示选择不确定性表示方法时应考虑的因素充分考虑领域问题的特征恰当地描述具体问题的不确定性满足问题求解的实际需求便于推理过程中对不确定性的推算不确定性的表示与度量（续1）2.不确定性的度量针对不同的领域问题采用不同的度量方法用不同的数值刻画不同的不确定性程度事先规定不确定性程度的取值范围3.常用的度量方法测度理论（基于概率统计的度量方法）Shannon信息熵其它度量方法……不确定性的表示与度量（续2）在选择不确定性度量方法时应考虑的因素：充分表达相应知识及证据不确定性的程度度量范围便于领域专家及用户估计不确定性便于计算过程中的不确定性传递，结论的不确定性度量不超出规定的范围度量的确定应直观，且有相应的理论依据不确定性匹配解决不确定性匹配的常用方法设计一个匹配算法用以计算相似度指定一个相似度的“限定”（即阈值）证据不确定性的组合单一证据&

组合证据单一证据：前提条件仅为一个简单条件组合证据：一个复合条件对应于一组证据前提条件用AND（与）或OR（或）把多个简单条件连接起来构成复合条件不确定性的传递包含两个子问题在每一步推理中，如何把证据及知识的不确定性传递给结论在多步推理中，如何把初始证据的不确定性传递给最终结论结论不确定性的合成用不同知识进行推理得到相同的结论相同结论的不确定性程度却不相同需要用合适的算法对它们进行合成不确定性推理方法的分类不确定性推理的两条研究路线模型方法在推理一级上扩展确定性推理不确定证据和知识与某种度量标准对应给出更新结论不确定性的算法构成相应的不确定性推理模型控制方法在控制策略一级上处理不确定性无统一的不确定性处理模型，其效果依赖于控制策略不确定性推理方法的分类不确定性推理模型方法控制方法数值方法非数值方法概率统计方法模糊推理方法粗糙集方法绝对概率方法贝叶斯方法证据理论方法HMM方法发生率计算相关性制导回溯、机缘控制、启发式搜索等可信度方法关于不确定性推理方法的说明数值方法对不确定性的一种定量表示和处理方法其研究及应用较多，已形成多种应用模型非数值方法除数值方法外的其它处理不确定性的模型方法典型代表：“发生率计算方法”，它采用集合来描述和处理不确定性，且满足概率推理的性质关于不确定性推理方法的说明（续1）概率统计方法有完整、严密的数学理论为不确定性的合成与传递提供了现成的数学公式最早、最广泛地用于不确定性知识的表示与处理已成为不确定性推理的重要手段证据理论方法1967年Dempster首次提出，1976年Shafer完善可表示并处理“不知道”等不确定性信息关于不确定性推理方法的说明（续2）模糊推理方法可表示并处理由模糊性引起的不确定性已广泛应用于不确定性推理粗糙集理论方法1981年Z.Pawlak首次提出一种新的可表示并处理“含糊”等不确定性的数学方法可用于不确定性推理、数据挖掘等领域概率推理概率论是研究随机现象中数量规律的科学。所谓随机现象是指在相同的条件下重复进行某种实验时，所得实验结果不一定完全相同且不可预知的现象掷硬币实验人工智能所讨论的不确定性现象，虽然不完全是随机的过程，但是实践证明，采用概率论的思想方法考虑能够得到较好的结果。概率论基础（概率定义）定义：设Ω为一个随机实验的样本空间，对Ω上的任意事件A，规定一个实数与之对应，记为P(A)，满足以下三条基本性质，称为事件A发生的概率：若二事件A、B互斥，即，则以上三条基本规定是符合常识的。概率论基础（条件概率）定义：设A，B为事件且P(A)>0，称

P(B|A)为事件A已发生的条件下，事件B的条件概率，P(A)在概率推理中称为边缘概率。简称P(B|A)为给定A时B发生的概率。P(AB)称为A与B的联合概率。有联合概率公式：概率论基础（条件概率性质）

，

乘法公式：

全概率公式：设A1，A2，…An互不相交，，且，则对于任意事件A有概率论基础（贝叶斯定理）设A，B1，B2，…，Bn为一些事件，P(A)>0，B1，B2，…，Bn互不相交，P(Bi)>0,i=1,2,…,n，且，则对于k=1,2,…,n，

贝叶斯公式容易由条件概率的定义，乘法公式和全概率公式得到。在贝叶斯公式中，P(Bi),i=1,2,…,n称为先验概率，而P(Bi|A)i=1,2,…,n称为后验概率也是条件概率。独立性Ａ和Ｂ是独立的在给定Ｃ时，Ａ和Ｂ是条件独立的概率推理

设H1,H2,H3为三个结论,E是支持这些结论的证据,且已知:P(H1)=0.3,P(H2)=0.4,P(H3)=0.5

P(E|H1)=0.5,P(E|H2)=0.3,P(E|H3)=0.4求:P(H1|E),P(H2|E),P(H3|E)解:贝叶斯网络二十世纪八十年代贝叶斯网络（BayesNetwork）成功地应用于专家系统，成为表示不确定性专家知识和推理的一种流行的方法。基于贝叶斯方法的贝叶斯网络是一种适应性很广的手段和工具，具有坚实的数学理论基础。在综合先验信息（领域知识）和数据样本信息的前提下，还可避免只使用先验信息可能带来的主观偏见。虽然很多贝叶斯网络涉及的学习问题是NP难解的。但是，由于已经有了一些成熟的近似解法，加上一些限制后计算可大为简化，很多问题可以利用近似解法求解。贝叶斯网络贝叶斯网络方法的不确定性表示基本上是保持了概率的表示方式，可信度计算也是概率计算方法，只是在实现时，各具体系统根据应用背景的需要采用各种各样的近似计算方法。推理过程称为概率推理。贝叶斯网络没有其它确定性推理方法拥有的确定性表示、计算、语义解释等问题。贝叶斯网络的由来全联合概率计算复杂性十分巨大朴素贝叶斯太过简单现实需要一种自然、有效的方式来捕捉和推理——不确定性知识变量之间的独立性和条件独立性可大大减少为了定义全联合概率分布所需的概率数目贝叶斯网络（基本概念）贝叶斯网络：一系列变量的联合概率分布的图形表示。一个表示变量之间的相互依赖关系的数据结构；图论与概率论的结合。贝叶斯网络的定义

是一个有向无环图(DAG)随机变量集组成网络节点，变量可离散或连续连接节点对的有向边组成边集合每节点Xi都有一个条件概率分布表：P(Xi|Parents(Xi))，量化其父节点对该节点的影响独立和条件独立WeatherCavityCatchToothacheWeather和其它3个变量相互独立贝叶斯网络示例BurglaryEarthquakeMaryCallsJohnCallsAlarmBEP(A)tttfftff0.950.940.290.001AP(J)tf0.900.05AP(M)tf0.700.01P(B)0.001P(E)0.002

贝叶斯网络的语义贝叶斯网就是一个在弧的连接关系上加入连接强度的因果关系网络。贝叶斯网络的语义P(x1,...,xn)=P(x1|parent(x1))...P(xn|parent(xn))贝叶斯网络的语义公式计算示例：

试计算：报警器响了，但既没有盗贼闯入，也没有发生地震，同时John和Mary都给你打电话的概率。解：

P(J,M,A,~B,~E)=P(J|A)P(M|A)P(A|~B,~E)P(~B)P(~E)=0.9x0.7x0.001x0.999x0.998=0.00062=0.062%贝叶斯网络的推理计算贝叶斯网络中的条件独立关系：

给定父节点，一个节点与它的非后代节点是条件独立的给定一个节点的父节点、子节点以及子节点的父节点——马尔可夫覆盖(Markovblanket)，这个节点和网络中的所有其它节点是条件独立的主观Bayes方法用产生式规则表示知识:

IFETHEN(LS,LN)H式中,(LS,LN)表示知识的静态强度LS:充分性因子LN:必要性因子充分性度量它表示E对H的支持程度，取值于[0,∞],由专家给出。必要性度量它表示~E对Ｈ的支持程度，即E对H为真的必要性程度，取值范围为[0,+∞]，也是由专家凭经验给出。主观Bayes方法

几率函数表示x的出现概率与不出现概率之比当P(x)=0时，有O(x)＝0当P(x)=1时，有O(x)＝∞把取值为[0,1]的P(X)放大为取值[0,+∞]的O(X).知识不确定性的表示由Bayes公式，由以上两式可得，

即有，

同理可得:以上两式是修改的Bayes公式当E为真时,利用LS将H的先验几率O(H)更新为后验几率O(H|E)当E为假时,利用LN将H的先验几率O(H)更新为后验几率O(H|~E)知识不确定性的表示LS→∞时,O(H|E)→∞,P(H|E)→1,E的存在导致H为真.因此称E对H是充分的,LS为充分性因子LN→0时,O(H|~E)→0,P(H|~E)→0,E的不存在导致H为假.因此称E对H是必要的,LN为必要性因子证据的不确定性描述根据观察S直接求出P(E|S)非常困难，引进了可信度C(E|S)，用户可根据实际情况在[-5,5]中选取一个整数作为初始证据的可信度。可信度C(E|S)与概率P(E|S)的对应关系可用下式表示：

C(E|S)=-5，表示在观察S下证据E肯定不存在，即P(E|S)=0；

C(E|S)=0，表示在观察S与证据E无关，即P(E|S)=P(E)；

C(E|S)=5，表示在观察S下证据E肯定存在，即P(E|S)=1。

这样，用户只要对证据E给出在观察S下的可信度C(E|S)，系统即可求出相应的P(E|S)。组合证据的不确定性描述对于组合证据E＝E1ANDE2AND…ANDEn

则P(E|S)＝min{P(E1|S),P(E2|S),…,P(En|S)}

对于组合证据E＝E1ORE2OR…OREn

则P(E|S)＝max{P(E1|S),P(E2|S),…,P(En|S)}基于主观Bayes方法的不确定性推理

在主观Bayes方法中，知识是用产生式规则表示的，具体形式为：

IFETHEN(LS,LN)H(P(H))LS,LN是充分性和必要性度量，P(H)是专家给出的先验概率。推理就由P(H)，P(E)，LS和LN求出的过程。证据E确定必出现P(E)=P(E/S)=1，由Bayes公式，由以上两式可得，

即有，

若需要以概率的形式表示，再由公式

计算出

这就是把先验概率P(H)更新为后验概率P(H|E)的计算公式。

证据E

确定必不出现P(E)=P(E|S)=0所以

从而这就是把先验概率P(H)更新为后验概率

的计算公式。证据E

不确定不能用上面的公式计算后验概率，可用Duda于1976年给出的公式

来计算出后验概率。这分为以下情况：证据肯定存在证据肯定不存在Ｅ与Ｓ无关当P（E|S）为其它值时

证据E

不确定(续)当

故

这就是证据肯定存在的情况。当

故有

这就是证据肯定不存在的情况。证据E

不确定(续)当P(E|S)=P(E)时，Ｅ与Ｓ无关，利用全概率公式有

当P(E|S)为其它值时，通过分段线性插值的方法，就可以得到计算P(H|S)的公式，即

该公式称为EH公式。

P(E)(E|S)1

对于初始证据，由于其不确定性是用可信度C(E|S)给出，此时只要把P(E|S)与C(E|S)的对应关系转换公式代入EH公式，就可以得到用可信度C(E|S)计算P(H|S)的公式：

该公式称为CP公式。

这样，当用初始证据进行推理时，根据用户告知的C(E|S)

通过运用CP公式就可以求出P(H|S).当用推理过程中得到的中间结论作为证据进行推理时，通过运用EH公式就可求出P(H|S).

结论不确定性的合成算法若有n条规则都支持相同的结论，而且每条规则的前提条件所对应的证据Ｅi（i=1,2,…,n）都有相应的观察Si与之对应，此时只要先对每条规则分别求出H的后验几率O(H|Si),然后按下列公式求出所