我要投搞

标签云

收藏小站

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

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

人工智能第3章推理技术1解读ppt

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

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  * 《人工智能》 * 3 消解的一般过程: 设子句集S={C1,C2,…Cn},则消解的一般过程是: S内任意子句两两逐一进行归结,得到一组归结式,称为第一级归结式,记为S1。 把S与S1内的任意子句两两逐一进行归结,得到一组归结式,称为第二级归结式,记为S2。 S和S1内的子句与S2内的任意子句两两逐一进行归结,得到一组归结式,称为第三级归结式,记为S3。 如此继续,直到出现了空子句或者不能再继续归结为止。 * 《人工智能》 * 目的:为了提高消解推理的效率,删除某些无用的子句来缩小归结的范围。下述删除策略是完备的(即如果子句集S不可满足,则采用该策略一定可以推出空子句)。 纯文字删除法 如果某文字L在子句集中不存在可与之互补的文字?L,则称该文字为纯文字。包含纯文字的子句可以删除。 重言式删除法 如果一个子句中同时包含互补文字对,则该字句称为重言式。重言式是永远为真的子句,可以删除。 包孕删除法 设有子句C1和C2,如果存在一个代换σ,使得: C1σ?C2 ,则称C1包孕于C2,可删除C2。 4 删除策略 * 《人工智能》 * 目的:通过对参加归结的子句进行限制,尽可能减小归结的盲目性,使其尽快地归结出空子句。 支持集策略 限制:每一次归结时,亲本子句中至少有一个是由目标公式的否定所得到的子句,或者是它们的后裔。支持集策略是完备的(即如果子句集S不可满足,采用该策略一定可以推出空子句)。 线性输入策略 限制:参加归结的两个子句中必须至少有一个是初始子句集中的子句。线性输入策略是不完备的。 祖先过滤策略 限制:参加归结的子句满足:(1)C1和C2中至少有一个是初始子句集中的子句;或(2)C1和C2中一个是另外一个的祖先子句。祖先过滤策略是完备的。 5 限制策略 * 《人工智能》 * 3.2 规则演绎系统 对于许多公式来说,子句形是一种低效率的表达式,因为一些重要信息可能在求取子句形过程中丢失。本节将研究采用易于叙述的if-then(如果-那么)规则来求解问题。 在所有基于规则系统中,每个if可能与某断言集中的一个或多个断言匹配。有时把该断言集称为工作内存。在许多基于规则系统中,then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统(rule based deduction system)。在这种系统中,通常称每个if部分为前项,称每个then部分为后项。 基于规则的演绎系统和产生式系统,均有正向推理和逆向推理两种推理方式。 * 《人工智能》 * 3.3 产生式系统 一个产生式系统一般由三部分组成:规则库、综合数据库、控制系统。 综合数据库 产生式规则库 控制系统 * 《人工智能》 * 规则库 用于描述相应领域内知识的产生式的集合。 一个规则库的例子: R1:动物有毛 → 哺乳类 R2:动物产奶 → 哺乳类 R3:哺乳类 ∧ 吃肉 → 食肉类 R4:哺乳类 ∧ 吃草 → 有蹄类 R5:食肉类 ∧ 黄褐色 ∧ 有斑点→ 金钱豹 R6:食肉类 ∧ 黄褐色 ∧ 黑条纹→ 虎 R7:有蹄类 ∧ 长脖 → 长颈鹿 R8:有蹄类 ∧ 黑条纹 → 斑马 * 《人工智能》 * 综合数据库 又称为事实库、上下文、黑板等等。 存放已知的事实和推导出的事实。 * 《人工智能》 * 控制机制 又称为推理机构,负责整个产生式系统的运行。 控制机制完成的工作有: 按照一定的策略,匹配规则的条件部分; 当多于一条的规则匹配成功时(称为冲突),选择其中一条规则加以执行(冲突消解); 将匹配规则的结论部分放入综合数据库; 计算结论的不确定性; 决定系统何时终止运行; * 《人工智能》 * 一个动物识别的例子 已知事实:一动物{有毛,吃草,黑条纹} R1:动物有毛 → 哺乳类 R2:动物产奶 → 哺乳类 R3:哺乳类 ∧ 吃肉 → 食肉类 R4:哺乳类 ∧ 吃草 → 有蹄类 R5:食肉类 ∧ 黄褐色 ∧ 有斑点→ 猎狗 R6:食肉类 ∧ 黄褐色 ∧ 黑条纹→ 虎 R7:有蹄类 ∧ 长脖 → 长颈鹿 R8:有蹄类 ∧ 黑条纹 → 斑马 * 《人工智能》 * 产生式系统求解问题的一般步骤 初始化事实库; 若规则库中存在尚未使用过的规则,且可匹配成功,则转第3步。否则转第5步; 执行当前选中的规则,并把结论送入事实库; 检查事实库中是否已经包含了解。若有则终止推理。若无则转第2步; 要求用户增添事实。若有则转第2步。若无则终止推理。 * 欢迎辞 《人工智能》 《人工智能》 第3章 推理技术 * 《人工智能》 * 3.1 消解原理 3.2 规则演绎系统 3.3 产生式系统 3.4 基于概率的推理 3.5 可信度方法 3.6 证据理论 3.7 模糊推理(cut) 3.8 非单调推理 本章主要内容: * 《人工智能》 * 推理方式及其分类 1. 演绎推理、归纳推理、默认推理 演绎推理:从一般到特殊。例如三段论。 归纳推理:从个体到一般。 默认推理:缺省推理,在知识不完全的情况下假设某些条件已经具备所进行的推理。 2. 确定性、不确定性推理 3. 单调性、非单调推理 推出的结论是否单调增加。 4. 基于知识的推理、统计推理、直觉推理 * 《人工智能》 * 谓词逻辑基本概念 1. 一个谓词分为谓词名与个体两个部分。 谓词名刻画个体的性质、状态或个体间的关系。 个体表示独立存在的事物或者概念。 例如: Teacher(zhang),Greater(5,3) 谓词的一般形式 P (x1, x2,…,xn) 其中,P是谓词名,x1, x2,…,xn是个体。谓词名通常用大写的英文字母表示,个体通常用小写的英文字母表示。该谓词是一个原子谓词公式。 * 《人工智能》 * 2. 个体可以是常量、变元或者函数。 例如: Less(x,5),x是一个变元。 Teacher(father(wang)),其中father(wang)是一个函数。 3.谓词的语义由人指定。 例如: S(x)可以表示x是一个人;也可以表示x是一朵花 * 《人工智能》 * 4. 连接词 非:?;析取:∨;合取:∧;蕴含:→; 双向蕴含: 谓词逻辑真值表 P Q ?P P∨Q P∧Q P→Q P Q T T F T T T T T F F T F F F F T T T F T F F F T F F T T * 《人工智能》 * 5. 谓词公式 (well formed formulas) 定义: 按下述规则得到的合式公式: (1) 单个谓词是合式公式,称为原子公式; (2) 若A是合式公式,则 也是合式公式; (3) 若A,B是合式公式,则 都是合式公式; (4) 若A是合式公式,x是任一个体变元,则 都是合式公式; (5) 运用有限步上述规则得到的公式是合式公式。 * 《人工智能》 * 6.一些重要的等价式 * 《人工智能》 * 7.一些重要的永真蕴含式 * 《人工智能》 * 所谓模式匹配是指对两个知识模式(例如两个谓词公式)进行比较,以检查这两个知识模式是否完全一致或者近似一致。 模式匹配可分为确定性匹配与不确定性匹配。 确定性匹配是指两个知识模式完全一致,或者经过变量代换后变得完全一致。例如: 规则: IF father(x,y) and man(y) THEN son(y,x) 事实: father(李四,李小四) and man(李小四) 代换:θ= {李四/X,李小四/Y} 结论:son(李小四,李四) 不确定性匹配是指两个知识模式不完全一致,但是它们的相似程度又在规定的限度内。 模式匹配 * 《人工智能》 * 变量代换 定义 代换是一个有限集合 {t1/x1,t2/x2,…,tn/xn} 其中t1,t2,…,tn是项,项可以是常量、变量、函数; x1,x2,…,xn是互不相同的变元; ti/xi表示用ti代换xi ; 一个合法的代换不允许ti与xi相同,也不允许变元xi循环地出现在另一个tj中。例如: {a/x,f(b)/y,w/z}是一个代换 {g(y)/x,f(x)/y}不是代换 * 《人工智能》 * 令θ= {t1/x1,t2/x2,…,tn/xn}为一个代换,F为表达 式,则Fθ表示对F用ti代换xi后得到的表达式。 Fθ称为F的特例。 规则: IF father(x,y) and man(y) THEN son(y,x) 事实: father(李四,李小四) and man(李小四) F=father(x,y) ∧ man(y) θ= {李四/X,李小四/Y} Fθ= father(李四,李小四) ∧ man(李小四) 结论: son(李小四,李四) * 《人工智能》 * 代换的复合 定义 设 θ= {t1/x1,t2/x2,…,tn/xn} λ= {u1/y1,u2/y2,…,um/ym} 是两个代换,则这两个代换的复合也是一个代换,它是从 {t1λ/x1,t2λ/x2,…,tnλ/xn,u1/y1,u2/y2,…,um/ym} 中删去如下两种元素: tiλ/xi 当tiλ=xi ui/yi 当yi∈{x1,x2,…,xn} 后剩下的元素所构成的集合,记为θ°λ 。 tiλ表示对ti运用λ进行代换。 θ°λ就是对一个公式F先运用θ进行代换,然后再运用λ进行代换:F( θ°λ )=(F θ)λ * 《人工智能》 * 代换复合的例子 设有代换 θ= {f(y)/x,z/y} λ= {a/x,b/y,y/z} 则 θ°λ={f(y)λ/x, zλ/y, a/x, b/y, y/z} ={f(b)/x, y/y, a/x, b/y, y/z} ={f(b)/x,y/z} * 《人工智能》 * 公式集的合一 定义 设有公式集F={F1,F2,…,Fn},若存在一个代换λ使得 F1λ=F2λ=…=Fnλ 则称λ为公式集F的一个合一,且称F1,F2,…,Fn是可合一的。 设有公式集 F={P(x,y,f(y)),P(a,g(x),z)} 则下式是它的一个合一: λ={a/x,g(a)/y,f(g(a))/z} 一个公式集的合一一般不唯一。 * 《人工智能》 * 最一般的合一 定义 设σ是公式集F的一个合一,如果对任一个合一θ都 存在一个代换λ,使得θ=σ°λ,则称σ是一个最一般的 合一。 代换过程是一个用项(常数,函数,变量)代替变元 的过程,因此是一个从一般到特殊的过程。 F= P(x,y) ∧ Q(y) θ= {a/x,f(z)/y} Fθ=P(a,f(z)) ∧ Q(f(z)) 最一般合一是唯一的。 * 《人工智能》 * 求取最一般合一 差异集:两个公式中相同位置处不同符号的集合。 例如:F1:P(x,y,z), F2:P(x,f(a),h(b)) 则D1={y,f(a)}, D2={z,h(b)} 求取最一般合一的算法: 令k=0,Fk=F, σk=ε。 ε是空代换。 若Fk只含一个表达式,则算法停止,σk就是最一般合一。 找出Fk的差异集Dk。 若Dk中存在元素xk和tk,其中xk是变元,tk是项,且xk不在tk中出现,则置: Fk+1=Fk{tk/xk} σK+1=σk°{tk/xk} k=k+1 然后转(2)。若不存在这样的xk和tk则算法停止。 算法终止,F的最一般合一不存在。 * 《人工智能》 * 求取最一般合一的例子 例如,设 F={P(a,x,f(g(y))),P(z,f(z),f(u))} 求其最一般合一。 令F0=F, σ0=ε。F0中有两个表达式,所以σ0不是最一般合一。 差异集:D0={a,z}。代换: {a/z} F1= F0 {a/z}={P(a,x,f(g(y))),P(a,f(a),f(u))} 。 σ1=σ0°{a/z}={a/z} 差异集: D1={x,f(a)} 。代换: {f(a)/x} F2=F1{f(a)/x}={P(a,f(a),f(g(y))),P(a,f(a),f(u))} 。 σ2=σ1°{f(a)/x}={a/z,f(a)/x} 差异集: D2={g(y),u} 。代换: {g(y)/u} F3=F2{g(y)/u}={P(a,f(a),f(g(y))),P(a,f(a),f(g(y)))} 。 σ3=σ2°{g(y)/u}={a/z,f(a)/x,g(y)/u} F3=Fσ3 * 《人工智能》 * 3.1 消解原理 消解原理也叫做归结原理。主要内容包括子句集的求取、消解推理的规则和消解反演问题求解方法。 消解原理的基础知识: 在谓词逻辑中,把原子谓词公式及其否定统称为文字。 例如: P(x), ?P(x,f(x)) 任何文字的析取式称为子句(clause)。 例如: P(x)∨Q(x), ?P(x,f(x))∨Q(x,g(x)) 不包含任何文字的子句称为空子句。 合取范式:若干子句的合取(and) 例如: C1 ∧C2 ∧C3… ∧Cn 子句集: S= {C1 ,C2 ,C3… ,Cn} * 《人工智能》 * 3.1.1 化为子句集 (1)消去蕴涵符号: 例如: (2)减少否定符号的辖域:每个否定符号“?”最多只用到一个谓词符号上,即利用等价关系把“?”移到紧靠谓词的位置上。上式经等价变换后 在进行消解过程之前, 首先需要将谓词演算公式化为一个子句集。其变换过程由下列几个步骤组成: * 《人工智能》 * (3)对变量标准化 :使不同量词约束的变元有不同的名字,通过变量更名来完成。例如,上式经变换后 (4)消去存在量词:分两种情况 a)存在量词不出现在全称量词的辖域内,则只要用一个新的个体常量替换受该量词约束的变元。 b)存在量词位于一个或者多个全称量词的辖域内,此时要用Skolem函数f(x1,x2,…,xn)替换受该存在量词约束的变元。上式中存在量词(?y)及(?z)都位于(?x)的辖域内,所以需要用Skolem函数替换,设替换y和z的Skolem函数分别是f(x)和g(x),则替换后得到 3.1.1 化为子句集(2) * 《人工智能》 * (5)化为前束形 :把所有全称量词移到公式的左边,并使每个量词的辖域包括这个量词后面公式的整个部分。所得公式称为前束形。 3.1.1 化为子句集(3) (6)化为合取范式 (7) 消去全称量词 :到了这一步,所有余下的量词均被全称量词量化了。同时全称量词的次序也不重要了。因此,我们可以消去全称量词。 * 《人工智能》 * (8)获取子句集: 3.1.1 化为子句集(4) (9)更换变量名称:使一个变量符号不出现在一个以上的子句中。上式在更改变量名后,可以得到子句集: * 《人工智能》 * 子句集S的不可满足性:对于任意论域中的任意 一个解释,S中的子句不能同时取得真值T。 谓词公式F的不可满足性:对于任意论域中的任意一个解释,F都不能取得真值T,即F是永假的。 定理 设有谓词公式F,其子句集为S,则F不可满足的充要条件是S不可满足。 * 《人工智能》 * 定义:设L1为任一原子公式,L2为另一原子公式,且具有相同的谓词名,但一般具有不同的变量。已知两子句L1∨α和?L2∨β,如果L1和L2具有最一般合一σ,那么通过消解可以从这两个子句推导出一个新子句ασ∨βσ。这个新子句叫做消解式(归结式)。 3.1.2 消解推理规则 ? * 《人工智能》 * C1=P(x)∨Q(x), C2= ?P(a)∨R(y) 最一般合一:σ={a/x} C1σ = P(a)∨Q(a) C2σ = ?P(a)∨R(y) 对它们进行归结,得到归结式:Q(a)∨R(y) 若某个子句C含有可合一的文字,则在进行归结之前应先对这些文字进行合一。 C1=P(x) ∨ P(f(a)) ∨ Q(x), C2= ?P(y) ∨ R(b) σ={ f(a)/x } C1σ=P(f(a)) ∨ Q(f(a)) C12 = Q(f(a)) ∨ R(b) * 《人工智能》 * 推论1 设C1与C2是子句集S中的两个子句,C12是它们的消解式。若用C12代替C1和C2后得到新子句集S1,则由S1的不可满足性可推出原子句集S的不可满足性,即 S1的不可满足性=S的不可满足性 推论2 设C1与C2是子句集S中的两个子句,C12是它们的消解式。若把C12加入S中得到新子句集S2,则S与S2在不可满足的意义上是等价的,即 S2的不可满足性=S的不可满足性 定理 若C12是子句C1与C2的消解式,则C12是C1与C2逻辑结论。 * 《人工智能》 * 3.1.3 消解反演求解过程 1 基本思想: 如欲证明Q为P1,P2,…,Pn的逻辑结论,即证明 (P1∧P2∧…∧Pn) → Q永线∧…∧Pn)∧?Q 是不可满足的,即证明其子句集S是不可满足的。为此,检查子句集S中是否包含空子句。若不包含,就在子句集中选择合适的子句进行归结,一旦通过归结能推出空子句,就说明子句集S是不可满足的,原定理得证。消解反演是完备的,即如果子句集不可满足,则一定可以得到空子句。 * 《人工智能》 * 2 消解反演: 设F为已知前提的公式集,Q为目标公式(结论),用归结反演证明Q为真的步骤是: 否定Q,得到?Q; F={P1,P2,…,Pn} 把?Q并入到公式集F中,得到{F, ?Q}; {P1,P2,…,Pn, ?Q} 把公式集{F, ?Q}化为子句集S; (P1∧P2∧…∧Pn)∧?Q 应用归结原理对子句集S中的子句进行归结,并把每次归结得到的归结式都并入S中。如此反复进行,若出现了空子句,则停止归结,此时就证明了Q为真。 * 《人工智能》 * 例: 已知 求证:G是F的逻辑结论。 证明:首先把F和?G化为子句集: 然后进行归结: (6)?A(x,y)∨?B(y) 由(1)与(3)归结,{f(x)/z} (7)?B(b) 由(4)与(6)归结,{a/x,b/y} (8)NIL 由(5)与(7)归结 所以G是F的逻辑结论。 上述归结过程如右图归结树所示。 ?A(x,y)∨?B(y)∨C(f(x)) ?A(x,y)∨?B(y) ?B(b) NIL ?C(z) A(a,b) B(b) 《人工智能》 《人工智能》 * 欢迎辞

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