我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:管家婆六肖中特 > 非单调推理 >

人工智能课件3 高级知识推理

归档日期:05-05       文本归类:非单调推理      文章编辑:爱尚语录

  第3章 高级知识推理 陈琼School of Computer Science and Engineering, South China University of Technology, Guangzhou, P.R. China 2008.9 高级知识推理 经典逻辑 确定性推理 单调性推理 归约推理 肖解演绎推理 规则演绎推理 非经典逻辑 不确定性推理 非单调性推理 时序推理 概率推理 经典逻辑与非经典逻辑的不同 推理方法 辖域取值 运算法则 逻辑算符 单调性 经典 演绎逻辑 二值 非经典 归纳逻辑 多值 模糊 有些不成立 逻辑算符 引入模态算符 单调 非单调 单调推理和非单调推理 单调推理 基于谓词逻辑的推理系统是单调的 系统中已知为真的命题随着推理的进行而增加,结论 越来越多 非单调推理 推理系统的定理集合不随推理过程的进行而单调增 大 新推理出的定理可能修正以至否定原有的一些定理, 使得原来能够解释的一些现象变得不可解释. 非单调推理 非单调推理用来处理那些不适合用谓词逻辑表 示的知识。 它能够较好地处理不完全信息、不断变化的情 况以及求解复杂问题过程中生成的假设,具有 较为有效的求解效率。 缺省推理 在没有证据能够证明某命题不成立时,就承认该 命题成立. 不具备命题的全部知识,也能够进行合理的推理 , 并给出正确的结论 定义 如果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发生的概率: 0 ≤ P ( A) ≤ 1 P (? ) = 1 P (φ ) = 0 若二事件A、B互斥,即,则 P ( A U B ) = P ( A) + P ( B ) 以上三条基本规定是符合常识的。 概率论基础(条件概率 ) 定义:设A,B为事件且P(A)0,称 定义 P( AB) P( B A) = P( A) P(BA)为事件A已发生的条件下,事件B的条件概率 条件概率, 条件概率 P(A)在概率推理中称为边缘概率 边缘概率。 边缘概率 简称P(BA)为给定A时B发生的概率。P(AB)称为A与B 的联合概率。有联合概率公式: P ( AB ) = P ( B A) P ( A) 概率论基础(条件概率性质 ) 0 ≤ P ( B A) ≤ 1 P (? A) = 1 , P (φ A) = 0 乘法公式: P ( AB ) = P ( A) P ( B A) P ( A1 A2 ... An ) = P ( A1 ) P ( A2 A1 ) P ( A3 A1 A2 )...P ( An A1 A2 ... An ?1 ) 全 概 率 公 式 : 设 A1 , A2 , …An 互 不 相 交 , , Ai =? 且 ∑ P( Ai ) 0, i = 1,2,..., n , i 则对于任意事件A有 P( A) = ∑ P( Ai ) P( A Ai ) i 概率论基础(贝叶斯定理 ) 设A,B1 ,B2 ,…,Bn 为一些事件,P(A)0,B1 ,B2 , … , Bn 互 不 相 交 , P(Bi)0, i=1, 2,…, n , 且 , ∑ P( Bi ) =1 则对于k=1, 2, …, n, i P ( B k ) P ( A Bk ) P ( Bk A) = ∑ P( Bi ) P( A Bi ) i 贝叶斯公式容易由条件概率的定义,乘法公式和全概 率公式得到。在贝叶斯公式中,P(Bi), i=1, 2, …, n称为 先验概率,而P(BiA) i=1, 2, …, n称为后验概率 后验概率也是条 先验概率 后验概率 条 件概率。 件概率 独立性 A和B是独立的 在给定C时,A和B是条件独立的 概率推理 设H1,H2,H3为三个结论,E是支持这些结论的证据,且已 知:P(H1)=0.3,P(H2)=0.4,P(H3)=0.5 P(EH1)=0.5,P(EH2)=0.3,P(EH3)=0.4 求: P(H1E), P(H2E), P(H3E) 解: P( H1 ) × P( E H1 ) P( E ) P ( H1 ) × P ( E H1 ) = P ( H1 ) × P( E H1 ) + P( H 2 ) × P ( E H 2 ) + P ( H 3 ) × P ( E H 3 ) P( H1 E ) = = 0.15 = 0.32 0.15 + 0.12 + 0.2 P( H 2 E ) = 0.26 P( H 3 E ) = 0.43 贝叶斯网络 二十世纪八十年代贝叶斯网络(Bayes Network)成功地应 用于专家系统,成为表示不确定性专家知识和推理的一种 流行的方法。 基于贝叶斯方法的贝叶斯网络是一种适应性很广的手段和 工具,具有坚实的数学理论基础。 在综合先验信息(领域知识)和数据样本信息的前提下, 还可避免只使用先验信息可能带来的主观偏见。 虽然很多贝叶斯网络涉及的学习问题是NP难解的。但是, 由于已经有了一些成熟的近似解法,加上一些限制后计算 可大为简化,很多问题可以利用近似解法求解。 贝叶斯网络 贝叶斯网络方法的不确定性表示基本上是保持了概 率的表示方式,可信度计算也是概率计算方法,只 是在实现时,各具体系统根据应用背景的需要采用 各种各样的近似计算方法。 推理过程称为概率推理。 贝叶斯网络没有其它确定性推理方法拥有的确定性 表示、计算、语义解释等问题。 贝叶斯网络的由来 全联合概率计算复杂性十分巨大 朴素贝叶斯太过简单 现实需要一种自然、有效的方式来捕捉 和推理——不确定性知识 变量之间的独立性和条件独立性可大大 减少为了定义全联合概率分布所需的概 率数目 贝叶斯网络(基本概念) 贝叶斯网络: 一系列变量的联合概率分布的图形表示。 一个表示变量之间的相互依赖关系的数据 结构;图论与概率论的结合。 贝叶斯网络的定义 是一个有向无环图(DAG) 随机变量集组成网络节点,变量可离散或连续 连接节点对的有向边组成边集合 每 节 点 Xi 都 有 一 个 条 件 概 率 分 布 表 : P(XiParents(Xi)),量化其父节点对该节点的影 响 独立和条件独立 Cavity Weather Toothache Catch Weather和其它3个变量相互独立 贝叶斯网络示例 P(B) P(E) Burglary 0.001 Earthquake B E t f t f P(A) 0.95 0.94 0.29 0.001 0.002 Alarm t t f f JohnCalls A t f P(J) 0.90 0.05 A P(M) 0.70 0.01 MaryCalls t f 贝叶斯网络的语义 贝叶斯网就是一个在弧的连接关系上加入连接强度的 因果关系网络 。 贝叶斯网络的语义 P(x1,..., xn) = P(x1parent(x1)) ... P(xnparent(xn)) 贝叶斯网络的语义公式计算示例: 贝叶斯网络的语义公式计算示例: 试计算:报警器响了,但既没有盗贼闯入,也没有 发生地震,同时John和Mary都给你打电话的概率。 解: P(J,M,A,~B,~E) = P(JA)P(MA)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 对H的支持程度,即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(HE) 当E为假时,利用LN将H的先验几率O(H)更新为后验几率O(H~E) 知识不确定性的表示 LS→∞时,O(HE) →∞,P(HE) →1, E的存在导致H为真. 因此称E对H是充分的, LS为充分性因子 LN→0时,O(H~E) →0,P(H~E) →0, E的不存在导致H为 假. 因此称E对H是必要的, LN为必要性因子 证据的不确定性描述 根据观察S直接求出P(ES)非常困难, 引进了可信度C(ES) ,用户可根据 实际情况在[-5,5]中选取一个整数作为初始证据的可信度。 可信度C(ES)与概率P(ES)的对应关系可用下式表示: C(ES)=-5,表示在观察S下证据E肯定不存在,即P(ES)=0; C(ES)=0 ,表示在观察S与证据E无关,即P(ES)=P(E); C(ES)=5 ,表示在观察S下证据E肯定存在,即P(ES)=1。 这样,用户只要对证据E给出在观察S下的可信度C(ES),系统即可求出 相应的P(ES)。 组合证据的不确定性描述 ?对于组合证据 E=E1 AND E2 AND …AND En 则 P(ES)=min{P(E1S),P(E2S), …,P(EnS)} ?对于组合证据 E=E1 OR E2 OR … OR En 则 P(ES)=max{P(E1S),P(E2S),…,P (EnS)} 基于主观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(HE)的计算公式。 证据E 确定必不出现 P(E)=P(ES) = 0 所以 从而 这就是把先验概率P(H)更新为后验概率 的计算公式。 证据E 不确定 不能用上面的公式计算后验概率,可用Duda于1976年 给出的公式 来计算出后验概率。这分为以下情况: 证据肯定存在 证据肯定不存在 E与S无关 当P(ES) 为其它值时 证据E 不确定(续) 当 故 这就是证据肯定存在的情况。 当 故有 这就是证据肯定不存在的情况。 证据E 不确定(续) 当 P(ES)=P(E) 时,E与S无关,利用全概率公式有 当P(ES)为其它值时,通过分段线性插值的方法,就 可以得到计算P(HS)的公式, 即 P(E)≤(ES) ≤ 1 该公式称为EH公式。 对于初始证据,由于其不确定性是用可信度C(ES) 给 出,此时只要把P(ES)与C(ES)的对应关系转换公式代入 EH公式,就可以得到用可信度C(ES) 计算P(HS) 的公式: 该公式称为CP公式。 这样,当用初始证据进行推理时,根据用户告知的 C(ES) 通过运用CP公式就可以求出P(HS).当用推理过程中 得到的中间结论作为证据进行推理时,通过运用EH公式就可 求出P(HS). 结论不确定性的合成算法 ? 若有n条规则都支持相同的结论,而且每条规则的前提 条件所对应的证据Ei(i = 1,2,…,n)都有相应的观察Si 与之对应,此时只要先对每条规则分别求出H的后验几 率O(HSi),然后按下列公式求出所有观察下H的后验几 率. 证据理论 Dempster-Shafer理论 诞生:源于20世纪60年代美国哈佛大学数学家A. P. 诞生 Dempster在利用上、下限概率来解决多值映射问题 利用上、 利用上 下限概率来解决多值映射问题方 面的研究工作。自1967年起连续发表了一系列论文, 标志着证据理论的正式诞生。 形成:Dempster的学生G. Shafer对证据理论做了进一 形成 步的发展,引入信任函数 信任函数概念,形成了一套基于“证 信任函数 据”和“组合”来处理不确定性推理问题的数学方法, 并于1976年出版了《证据的数学理论》(A Mathematical Theory of Evidence),这标志着证据理 论正式成为一种处理不确定性问题的完整理论。 证据理论的核心、优点及适用领域 核心:Dempster合成规则 合成规则,这是Dempster在 核心 合成规则 研究统计问题时首先提出的,随后Shafer把它 推广到更为一般的情形。 优点:由于在证据理论中需要的先验数据比概 优点 率推理理论中的更为直观、更容易获得,再加 上Dempster合成公式可以综合不同专家或数据 源的知识或数据,这使得证据理论在专家系统、 专家系统、 专家系统 信息融合等领域中得到了广泛应用。 信息融合 适用领域:信息融合、专家系统、情报分析、 适用领域 法律案件分析、多属性决策分析,等等。 证据理论的局限性 要求证据必须是独立的 证据必须是独立的,而这有时不易满足 证据必须是独立的 证据合成规则没有非常坚固的理论支持,其合 合 理性和有效性还存在较大的争议 计算上存在着潜在的指数爆炸问题 指数爆炸问题 证据理论的主要特点 满足比Bayes概率理论更弱的条件,即不必满 不必满 足概率可加性。 足概率可加性 具有直接表达“不确定”和“不知道”的能 直接表达“ 不知道” 直接表达 不确定” 力。 证据理论不但允许人们将信度赋予假设空间的 单个元素,而且还能赋予它的子集,这很象人 很象人 类在各级抽象层次上的证据收集过程。 类在各级抽象层次上的证据收集过程 其他推理方法 非单调推理 时序推理 缺省推理 模糊逻辑 ……

本文链接:http://meghanmbiro.com/feidandiaotuili/333.html