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

第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)解:,贝叶斯网络,二十世纪八十年代贝叶斯网络（Bayes Network）成功地应用于专家系统，成为表示不确定性专家知识和推理的一种流行的方法。基于贝叶斯方法的贝叶斯网络是一种适应性很广的手段和工具，具有坚实的数学理论基础。在综合先验信息（领域知识）和数据样本信息的前提下，还可避免只使用先验信息可能带来的主观偏见。虽然很多贝叶斯网络涉及的学习问题是NP难解的。但是，由于已经有了一些成熟的近似解法，加上一些限制后计算可大为简化，很多问题可以利用近似解法求解。,贝叶斯网络,贝叶斯网络方法的不确定性表示基本上是保持了概率的表示方式，可信度计算也是概率计算方法，只是在实现时，各具体系统根据应用背景的需要采用各种各样的近似计算方法。推理过程称为概率推理。贝叶斯网络没有其它确定性推理方法拥有的确定性表示、计算、语义解释等问题。,贝叶斯网络的由来,全联合概率计算复杂性十分巨大朴素贝叶斯太过简单现实需要一种自然、有效的方式来捕捉和推理不确定性知识变量之间的独立性和条件独立性可大大减少为了定义全联合概率分布所需的概率数目,贝叶斯网络（基本概念）,贝叶斯网络：一系列变量的联合概率分布的图形表示。一个表示变量之间的相互依赖关系的数据结构；图论与概率论的结合。,贝叶斯网络的定义,是一个有向无环图(DAG)随机变量集组成网络节点，变量可离散或连续连接节点对的有向边组成边集合每节点Xi都有一个条件概率分布表：P(Xi|Parents(Xi)，量化其父节点对该节点的影响,独立和条件独立,Weather,Weather和其它3个变量相互独立,贝叶斯网络示例,Burglary,Earthquake,MaryCalls,JohnCalls,Alarm,贝叶斯网络的语义,贝叶斯网就是一个在弧的连接关系上加入连接强度的因果关系网络 。贝叶斯网络的语义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%,贝叶斯网络的推理,计算,贝叶斯网络中的条件独立关系：,给定父节点，一个节点与它的非后代节点是条件独立的给定一个节点的父节点、子节点以及子节点的父节点马尔可夫覆盖(Markov blanket)，这个节点和网络中的所有其它节点是条件独立的,主观Bayes方法,用产生式规则表示知识: IF E THEN (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为充分性因子LN0时,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)。,组合证据的不确定性描述,对于组合证据 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方法的不确定性推理,在主观Bayes方法中，知识是用产生式规则表示的，具体形式为： IF E THEN(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),然后按下列公式求出所有观察下H的后验几率.,证据理论,Dempster-Shafer理论诞生：源于20世纪60年代美国哈佛大学数学家A. P. Dempster在利用上、下限概率来解决多值映射问题方面的研究工作。自1967年起连续发表了一系列论文，标志着证据理论的正式诞生。形成：Dempster的学生G. Shafer对证据理论做了进一步的发展，引入信任函数概念，形成了一套基于“证据”和“组合”来处理不确定性推理问题的数学方法，并于1976年出版了证据的数学理论(A Mathematical Theory of Evidence)，这标志着证据理论正式成为一种处理不确定性问题的完整理论。,证据理论的核心、优点及适用领域,核心：Dempster合成规则，这是Dempster在研究统计问题时首先提出的，随后Shafer把它推广到更为一般的情形。优点：由于在证据理论中需要的先验数据比概率推理理论中的更为直观、更容易获得，再加上Dempster合成公式可以综合不同专家或数据源的知识或数据，这使得证据理论在专家系统、信息融合等领域中得到了广泛应用。适用领域：信息融合、专家系统、情报分析、法律案件分析、多属性决策分析，等等。,证据理论的局限性,要求证据必须是独立的，而这有时不易满足证据合成规则没有非常坚固的理论支持，其合理性和有效性还存在较大的争议计算上存在着潜在的指数爆炸问题,证据理论的主要特点,满足比Bayes概率理论更弱的条件，即不必满足概率可加性。具有直接表达“不确定”和“不知道”的能力 。 证据理论不但允许人们将信度赋予假设空间的单个元素，而且还能赋予它的子集，这很象人类在各级抽象层次上的证据收集过程。,其他推理方法,非单调推理时序推理缺省推理模糊逻辑,