人工智能原理及其应用优秀课件.ppt

《人工智能原理及其应用优秀课件.ppt》由会员分享，可在线阅读，更多相关《人工智能原理及其应用优秀课件.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、人工智能原理及其应用第1页，本讲稿共27页第三章确定性推理第三章确定性推理一、推理的基本概念n定义 推理：已知事实 结论 知识推理是指在计算机或智能机器中，在知识表达的基础上，利用形式化的知识模型，进行机器思维求解问题，实现状态转移的智能操作序列。策略第2页，本讲稿共27页第三章确定性推理第三章确定性推理 基本问题：推理的方法和控制的策略2.推理方法及分类1)根据知识表示方式分类 “图搜索”方法 如：状态空间法、与或图 “逻辑论证”方法 如：谓词逻辑等2)推理算法与推理步骤 算法：完备性 如宽度优先 步骤：不完备 如深度优先3)启发式与非启发式 启发性知识：即解决问题的策略、技巧、窍门等实践经

2、验和知识。例：瞎子爬山第3页，本讲稿共27页第三章确定性推理第三章确定性推理n按逻辑基础 演绎推理：一般到个别 三段论 归纳推理：个别到一般 完全归纳、不完全归纳 枚举归纳、类比归纳等 默认（缺省）推理：知识不完备n按知识的确定性 确定性推理：知识和结论都是精确的 非确定性推理第4页，本讲稿共27页第三章确定性推理第三章确定性推理6)按推理过程的单调性 单调推理 非单调推理：加入新知识会否定原来推出的结论，使推理过程回退3.控制策略及分类 推理的控制策略：指如何使用领域知识使推理过程尽快达到目标的策略。推理策略：推理方向控制策略、求解策略、限制策略、冲突消解策略 搜索策略（第五章）：推理线路、

3、推理效果、推理效率第5页，本讲稿共27页第三章确定性推理第三章确定性推理n正向推理 知识库、综合数据库、推理机 正向推理的过程（图3-1）优点：直观。适合于诊断、监控、设计、预测等领域。缺点；推理无明确目标，效率较低。2)逆向推理 逆向推理的过程（图3-2）优点：目标明确，效率较高 缺点：情况不明时，选择假设目标的盲目性比较大，可能多次提出假设，降低系统效率第6页，本讲稿共27页第三章确定性推理第三章确定性推理n混合推理n方法n先正后逆（图3-3）n先逆后正（图3-4）n双向（图3-5）n适用场合n事实不够充分n正向推理推出的结论可性度不高n希望得到更多结论第7页，本讲稿共27页第三章确定性推

4、理第三章确定性推理n冲突消解策略 基本思想：对可用知识排序n特殊知识优先n新鲜知识优先n差异性大的知识优先n领域特点优先n上下文关系优先n前提条件少者优先第8页，本讲稿共27页第三章确定性推理第三章确定性推理二、推理的逻辑基础n基本概念n谓词公式的解释 对所包含的常量、函数、谓词赋值2)谓词公式的永真性与可满足性 非空个体域上的任一解释（在D上永真）；任何非空个体域（永真）3)谓词公式的等价性与永真蕴含性 在D上等价与等价PQ,永真蕴含PQ 常用的等价式、永真蕴含式（牢记）第9页，本讲稿共27页第三章确定性推理第三章确定性推理1.谓词公式的范式 前束范式：前缀 母式1.置换与合一 已知：W1(

5、A),(x)(W1(x)W2(x)结论：W2(A)1)置换：在表达式中用置换项置换变量。t1/x1,t2/x2,tn/xn,量词串无量词公式第10页，本讲稿共27页第三章确定性推理第三章确定性推理 置换的例 置换的合成 (Ls1)s2=L(s1s2)置换一般不可交换 s1s2s2s1 例：表达式P(x,g(y),c)置换 s1=f(y)/x,z/y s2=a/x,b/y,y/z Ps1=P(f(z),g(z),c)Ps2=P(a,g(b),c)Ps1s2=P(f(b),g(b),c)s1s2=f(b)/x,b/y,y/z Ps2s1=P(a,g(b),c)s2s1=a/x,b/y 第11页，本

6、讲稿共27页第三章确定性推理第三章确定性推理2)合一：寻找项对变量的置换，以使表达式一致。Pg(x),f(y),B,Ph(x),f(B),B不可合一 尽管s=A/x,B/y是Px,f(y),B,Px,f(B),B的一个合一者，但是最简单的合一者是g=B/y 最一般(通用)合一者(mgu)：置换最少的变量以使表达式一致。分歧集：例：F=P(x,y,z),P(x,f(a),h(b)的分歧集 D1=y,f(a)D2=z,h(b)第12页，本讲稿共27页第三章确定性推理第三章确定性推理 合一算法(p89)例：F=P(a,x,f(g(y),P(z,h(z,u),f(u)第13页，本讲稿共27页第三章确定

7、性推理第三章确定性推理三、自然演绎推理 已知事实 结论 注意肯定前件、否定后件的错误 例3.8：定义谓词：Prog(x)Like(x,y)Lang(x)事实：Prog(x)Like(Wang,x)(x)(Lang(x)Prog(x)Lang(C)结论：Like(Wang,C)经典逻辑推理规则第14页，本讲稿共27页第三章确定性推理第三章确定性推理四、归结演绎推理（Robinson消解原理）对前提P，结论Q，证明P Q永真 P Q与PQ等价 只需证明（PQ）即P Q不可满足。第15页，本讲稿共27页第三章确定性推理第三章确定性推理n子句集n概念 文字：原子谓词公式及其否定 子句：任何文字的析取式

8、 空子句NIL：永假、不可满足2)化为子句集n消去蕴涵和等价符号n减少否定符号的辖域n对变量标准化，保证每个量词有其唯一的哑元n消去存在量词 skolem函数第16页，本讲稿共27页第三章确定性推理第三章确定性推理e)化为前束形 前缀（全称量词串）母式（元量词公式）f)把母式化为合取范式g)消去全称量词h)消去连词符号i)更换变量名称第17页，本讲稿共27页第三章确定性推理第三章确定性推理例（x）P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)第18页，本讲稿共27页第三章确定性推理第三章确定性推理二、p9398:只要求记住两条有用的结论：q原谓词公式不可满足，其标准子句集则一

9、定不可满足。qHerbrand(海伯伦)定理：子句集S不可满足的充要条件是存在一个有限的不可满足的基子句集S。第19页，本讲稿共27页第三章确定性推理第三章确定性推理三、鲁宾逊（Robinson）归结原理n基本思想 否定结论，加入前提子句集，应用归结原理，是否能导出空子句，若存在，证明否定结论错误，即原结论得证。（反证法）实际上归结原理不仅应用在定理证明，还可应用于问题求解过程。2.归结原理 互补文字：P、P 归结式：分为命题逻辑归结和谓词逻辑归结.第20页，本讲稿共27页第三章确定性推理第三章确定性推理n 命题逻辑归结n定义：L1、L2分别是子句C1、C2中的文字，并且L1、L2 互补，即L

10、1 L2，将它们从C1、C2中消去，并将两子句余下部分按析取关系组成新子句C12，即归结式。C1、C2叫做亲本子句。例：p99 3.15、3.16、3.17第21页，本讲稿共27页第三章确定性推理第三章确定性推理n定理：归结式C12是亲本子句C1和C2的逻辑结论。定理：子句集S是不可满足的，当且仅当存在一个从S到空子句的归结过程。第22页，本讲稿共27页第三章确定性推理第三章确定性推理n归结反演定理证明过程：公式集S，目标公式GI.否定G，得到 GII.把 G添加到S中去III.新产生 G，S化为子句集IV.应用归结原理，力图推导出一个矛盾空子句 例：p101 3.18第23页，本讲稿共27页

11、第三章确定性推理第三章确定性推理2)谓词逻辑归结a)定义：对含有变元的子句C1、C2中文字L1、L2，如果L1、L2存在最一般合一者，则有归结式 C12C1L1 C2-L2 二元归结式不作要求 例：p102b)谓词逻辑归结反演定理证明 例：p103105第24页，本讲稿共27页第三章确定性推理第三章确定性推理c)谓词逻辑归结反演问题求解 答案求取涉及到把一棵根部有空子句的反演树变换为在根部带有可用作答案的某个语句的一棵证明树I.把由目标公式的否定产生的每个子句添加到目标公式否定的否定的子句中去II.按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。III.用根部的子句作为一个回答语句 例：p110第25页，本讲稿共27页第三章确定性推理第三章确定性推理n归结演绎推理的归结策略 广度优先策略n删除策略：缩小归结范围n纯文字删除法n重言式删除法n包孕删除法2)限制策略：加入启发信息，减少盲目性n支持集策略n单文字子句策略n线性输入策略n祖先过滤策略第26页，本讲稿共27页第三章第三章 作业作业qP119:3-1、3-5、3-9、3-10、3-13(1)(3)(5)、3-15、3-18、3-19第27页，本讲稿共27页