人工智能课件3-推理.ppt

1、第7章 高级知识推理高级知识推理n经典逻辑n确定性推理 单调性推理 n归约推理 肖解演绎推理 规则演绎推理n非经典逻辑n不确定性推理 非单调性推理 n时序推理 概率推理 经典逻辑与非经典逻辑的不同n 经典经典 非经典非经典n推理方法 演绎逻辑 归纳逻辑n辖域取值 二值 多值 模糊n运算法则 有些不成立n逻辑算符 逻辑算符 引入模态算符n单调性 单调 非单调单调推理和非单调推理n单调推理n基于谓词逻辑的推理系统是单调的n系统中已知为真的命题随着推理的进行而增加,结论越来越多n非单调推理n推理系统的定理集合不随推理过程的进行而单调增大n新推理出的定理可能修正以至否定原有的一些定理,使得原来能够解释

2、的一些现象变得不可解释. 非单调推理n非单调推理用来处理那些不适合用谓词逻辑表示的知识。n它能够较好地处理不完全信息、不断变化的情况以及求解复杂问题过程中生成的假设，具有较为有效的求解效率。缺省推理n在没有证据能够证明某命题不成立时,就承认该命题成立.n不具备命题的全部知识,也能够进行合理的推理并给出正确的结论n定义n如果X不知道，那么得结论Y。n如果X不能被证明，那么得结论Y。n如果X不能在某个给定的时间内被证明，那么得结论Y。不确定性推理不确定性推理精确推理的局限性精确推理的局限性n推理推理n依据已知事实（证据）、相关知识（规则）n证明某个假设成立 or 不成立n精确推理及其不足精确推理及

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

4、n不确定性的传递算法不确定性的传递算法n不确定性的合成不确定性的合成不确定性的表示与度量不确定性的表示与度量1. 不确定性的表示不确定性的表示n选择不确定性表示方法时应考虑的因素选择不确定性表示方法时应考虑的因素n充分考虑领域问题的特征n恰当地描述具体问题的不确定性n满足问题求解的实际需求n便于推理过程中对不确定性的推算不确定性的表示与度量（续不确定性的表示与度量（续1）2. 不确定性的度量不确定性的度量n针对不同的领域问题采用不同的度量方法针对不同的领域问题采用不同的度量方法n用不同的数值刻画不同的不确定性程度n事先规定不确定性程度的取值范围3. 常用的度量方法常用的度量方法n测度理论（基于

5、概率统计的度量方法）nShannon信息熵n其它度量方法n不确定性的表示与度量（续不确定性的表示与度量（续2）在选择不确定性度量方法时应考虑的因素：在选择不确定性度量方法时应考虑的因素：n充分表达相应知识及证据不确定性的程度n度量范围便于领域专家及用户估计不确定性n便于计算过程中的不确定性传递，结论的不确定性度量不超出规定的范围n度量的确定应直观，且有相应的理论依据不确定性匹配不确定性匹配n解决不确定性匹配的常用方法解决不确定性匹配的常用方法n设计一个匹配算法匹配算法用以计算相似度n指定一个相似度的“限定”（即阈值阈值）证据不确定性的组合证据不确定性的组合n单一证据单一证据 & 组合证据组合证

6、据n单一证据单一证据：前提条件仅为一个简单条件n组合证据组合证据：一个复合条件对应于一组证据n前提条件用AND（与）或OR（或）把多个简单条件连接起来构成复合条件不确定性的传递不确定性的传递n包含两个子问题包含两个子问题n在每一步推理每一步推理中，如何把证据及知识的不确定性传递给结论n在多步推理多步推理中，如何把初始证据的不确定性传递给最终结论结论不确定性的合成结论不确定性的合成n用不同知识进行推理得到相同的结论n相同结论的不确定性程度却不相同n需要用合适的算法对它们进行合成不确定性推理方法的分类不确定性推理方法的分类不确定性推理的两条研究路线不确定性推理的两条研究路线n模型方法模型方法n在推

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

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

9、引起的不确定性n已广泛应用于不确定性推理n粗糙集理论方法粗糙集理论方法n1981年Z. Pawlak首次提出n一种新的可表示并处理“含糊”等不确定性的数学方法n可用于不确定性推理、数据挖掘等领域概率推理概率推理n概率论是研究随机现象中数量规律的科学。n所谓随机现象是指在相同的条件下重复进行某种实验时，所得实验结果不一定完全相同且不可预知的现象n 掷硬币实验n人工智能所讨论的不确定性现象，虽然不完全是随机的过程，但是实践证明，采用概率论的思想方法考虑能够得到较好的结果。 概率论基础（概率定义 ）n定义：定义：设为一个随机实验的样本空间，对上的任意事件A，规定一个实数与之对应，记为P(A)，满足以

10、下三条基本性质，称为事件A发生的概率：n若二事件A、B互斥，即，则1)(0AP1)(P0)(P)()()(BPAPBAP以上三条基本规定是符合常识的。概率论基础（条件概率 ）n定义定义：设A，B为事件且P(A)0，称nP(B|A)为事件A已发生的条件下，事件B的条件概率条件概率，P(A)在概率推理中称为边缘概率边缘概率。n简称P(B|A)为给定A时B发生的概率。P(AB)称为A与B的联合概率。有联合概率公式：)()()|(APABPABP)()|()(APABPABP概率论基础（条件概率性质 ）n n ，n 乘法公式：n全概率公式：设A1，A2，An互不相交， ， 且 ，则对于任意事件A有1)

11、|(0ABP1)|( AP0)|(AP)|()()(ABPAPABP).|().|()|()().(12121312121nnnAAAAPAAAPAAPAPAAAPiiAniAPi,.,2 , 1, 0)(iiiAAPAPAP)|()()(概率论基础（贝叶斯定理 ）n设A，B1，B2，Bn为一些事件，P(A)0，B1，B2，Bn互不相交，P(Bi)0, i=1, 2, n，且 ， 则对于k=1, 2, , n，n贝叶斯公式容易由条件概率的定义，乘法公式和全概率公式得到。在贝叶斯公式中，P(Bi), i=1, 2, , n称为先验概率先验概率，而P(Bi|A) i=1, 2, , n称为后验概率

12、后验概率也是条条件概率件概率。 1)(iiBPiiikkkBAPBPBAPBPABP)|()()|()()|(独立性独立性n和是独立的n在给定时，和是条件独立的概率推理概率推理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)解: 43. 0)|( 26. 0)|(32. 02 . 012. 015. 015. 0)|()()|()()|()()|()()()|()()|(32332211111

13、11EHPEHPHEPHPHEPHPHEPHPHEPHPEPHEPHPEHP贝叶斯网络n二十世纪八十年代贝叶斯网络（Bayes Network）成功地应用于专家系统，成为表示不确定性专家知识和推理的一种流行的方法。n基于贝叶斯方法的贝叶斯网络是一种适应性很广的手段和工具，具有坚实的数学理论基础。n在综合先验信息（领域知识）和数据样本信息的前提下，还可避免只使用先验信息可能带来的主观偏见。n虽然很多贝叶斯网络涉及的学习问题是NP难解的。但是，由于已经有了一些成熟的近似解法，加上一些限制后计算可大为简化，很多问题可以利用近似解法求解。贝叶斯网络n贝叶斯网络方法的不确定性表示基本上是保持了概率的表示

14、方式，可信度计算也是概率计算方法，只是在实现时，各具体系统根据应用背景的需要采用各种各样的近似计算方法。n推理过程称为概率推理。n贝叶斯网络没有其它确定性推理方法拥有的确定性表示、计算、语义解释等问题。 贝叶斯网络的由来贝叶斯网络的由来n全联合概率计算复杂性十分巨大n朴素贝叶斯太过简单n现实需要一种自然、有效的方式来捕捉和推理不确定性知识n变量之间的独立性和条件独立性可大大减少为了定义全联合概率分布所需的概率数目贝叶斯网络（基本概念）贝叶斯网络：n一系列变量的联合概率分布的图形表示。n一个表示变量之间的相互依赖关系的数据结构；图论与概率论的结合。贝叶斯网络的定义贝叶斯网络的定义 n是一个有向无

15、环图(DAG)n随机变量集组成网络节点，变量可离散或连续n连接节点对的有向边组成边集合n每 节 点 Xi都 有 一 个 条 件 概 率 分 布 表 ：P(Xi|Parents(Xi)，量化其父节点对该节点的影响独立和条件独立独立和条件独立WeatherCavityCatchToothachen Weather和其它3个变量相互独立贝叶斯网络示例贝叶斯网络示例BurglaryEarthquakeMaryCallsJohnCallsAlarm B EP(A) t t t f f t f f0.950.940.290.001 AP(J) t f0.900.05 AP(M) t f0.700.01P(

16、B) 0.001P(E) 0.002 贝叶斯网络的语义贝叶斯网络的语义贝叶斯网就是一个在弧的连接关系上加入连接强度的因果关系网络 。n贝叶斯网络的语义贝叶斯网络的语义P(x1,., xn) = P(x1|parent(x1) . P(xn|parent(xn)贝叶斯网络的语义公式计算示例：贝叶斯网络的语义公式计算示例： n试计算：报警器响了，但既没有盗贼闯入，也没有发生地震，同时John和Mary都给你打电话的概率。n解： 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 =

17、0.062%贝叶斯网络的推理贝叶斯网络的推理n计算贝叶斯网络中的条件独立关系贝叶斯网络中的条件独立关系： n给定父节点，一个节点与它的非后代节点非后代节点是条件独立的n给定一个节点的父节点、子节点以及子节点的父节点马尔可夫覆盖马尔可夫覆盖(Markov blanket)，这个节点和网络中的所有其它节点是条件独立的主观Bayes方法n用产生式规则表示知识: IF E THEN (LS,LN) H式中, (LS,LN)表示知识的静态强度 LS:充分性因子 LN:必要性因子n充分性度量 它表示E 对H 的支持程度，取值于0, ,由专家给出。n 必要性度量它表示E 对的支持程度，即E 对H 为真的必要

18、性程度，取值范围为0,+，也是由专家凭经验给出。主观Bayes方法 n几率函数 表示x的出现概率与不出现概率之比 当P(x)=0时，有 O(x) 0 当P(x)=1时，有 O(x) 把取值为0,1的P(X)放大为取值0,+ 的O(X).知识不确定性的表示n由Bayes公式，n由以上两式可得， n即有，n同理可得: 以上两式是修改的Bayes公式当E为真时,利用LS将H的先验几率O(H)更新为后验几率O(H|E)当E为假时,利用LN将H的先验几率O(H)更新为后验几率O(H|E)知识不确定性的表示nLS时,O(H|E) ,P(H|E) 1, E的存在导致H为真. 因此称E对H是充分的, LS为充

19、分性因子nLN0时,O(H|E) 0,P(H|E) 0, E的不存在导致H为假. 因此称E对H是必要的, LN为必要性因子证据的不确定性描述 n根据观察S直接求出P(E|S)非常困难， 引进了可信度C(E|S) ，用户可根据实际情况在-5,5中选取一个整数作为初始证据的可信度。n可信度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下的可信度

20、C(E|S)，系统即可求出相应的P(E|S)。 组合证据的不确定性描述对于组合证据 EE1 AND E2 AND AND En 则 P(E|S)minP(E1|S),P(E2|S), ,P(En|S) 对于组合证据 EE1 OR E2 OR OR En 则 P(E|S)maxP(E1|S),P(E2|S),P (En|S) 基于主观Bayes方法的不确定性推理 n在主观Bayes方法中，知识是用产生式规则表示的，具体形式为： IF E THEN(LS,LN) H (P(H) LS,LN是充分性和必要性度量，P(H)是专家给出的先验概率。n推理就由P(H)，P(E)，LS和LN求出 的过程。证据

21、E确定必出现 nP(E)=P(E/S)=1，由Bayes公式，n由以上两式可得， n即有，n若需要以概率的形式表示，再由公式n 计算出n这就是把先验概率P(H)更新为后验概率P(H|E)的计算公式。 证据E 确定必不出现 nP(E)=P(E|S) = 0 n所以 从而 这就是把先验概率P(H)更新为后验概率 的计算公式。 证据E 不确定 n不能用上面的公式计算后验概率，可用Duda于1976年给出的公式 来计算出后验概率。这分为以下情况：n证据肯定存在 n证据肯定不存在n与无关 n当P（E|S） 为其它值时 证据E 不确定(续)n当 故 这就是证据肯定存在的情况。n当 故有这就是证据肯定不存在

22、的情况。证据E 不确定(续)n当 P(E|S)=P(E) 时，与无关，利用全概率公式有 n当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(

23、H|S). 结论不确定性的合成算法 若有n条规则都支持相同的结论，而且每条规则的前提条件所对应的证据i（i = 1,2,n）都有相应的观察Si与之对应，此时只要先对每条规则分别求出H的后验几率O(H|Si),然后按下列公式求出所有观察下H的后验几率.证据理论Dempster-Shafer理论n诞生诞生：源于20世纪60年代美国哈佛大学数学家A. P. Dempster在利用上、下限概率来解决多值映射问题利用上、下限概率来解决多值映射问题方面的研究工作。自1967年起连续发表了一系列论文，标志着证据理论的正式诞生。n形成形成：Dempster的学生G. Shafer对证据理论做了进一步的发展，引

24、入信任函数信任函数概念，形成了一套基于“证据”和“组合”来处理不确定性推理问题的数学方法，并于1976年出版了证据的数学理论(A Mathematical Theory of Evidence)，这标志着证据理论正式成为一种处理不确定性问题的完整理论。证据理论的核心、优点及适用领域n核心核心：Dempster合成规则合成规则，这是Dempster在研究统计问题时首先提出的，随后Shafer把它推广到更为一般的情形。n优点优点：由于在证据理论中需要的先验数据比概率推理理论中的更为直观、更容易获得，再加上Dempster合成公式可以综合不同专家或数据源的知识或数据，这使得证据理论在专家系统、专家系

25、统、信息融合信息融合等领域中得到了广泛应用。n适用领域适用领域：信息融合、专家系统、情报分析、法律案件分析、多属性决策分析，等等。证据理论的局限性n要求证据必须是独立的证据必须是独立的，而这有时不易满足n证据合成规则没有非常坚固的理论支持，其合合理性和有效性还存在较大的争议理性和有效性还存在较大的争议n计算上存在着潜在的指数爆炸问题指数爆炸问题证据理论的主要特点n满足比Bayes概率理论更弱的条件，即不必满不必满足概率可加性足概率可加性。n具有直接表达直接表达“不确定不确定”和和“不知道不知道”的能力 。n 证据理论不但允许人们将信度赋予假设空间的单个元素，而且还能赋予它的子集，这很象人很象人类在各级抽象层次上的证据收集过程类在各级抽象层次上的证据收集过程。其他推理方法n非单调推理n时序推理n缺省推理n模糊逻辑n