PPTOK :您身边最贴心好用的PPT站!

您当前所在位置:首页 > PPT课件 > 行业PPT → 人工智能及应用_ch3_3ppt

人工智能及应用_ch3_3ppt

  • 素材大小:251 KB
  • 素材授权:免费下载
  • 更新时间:2018-03-29
  • 素材类别:行业PPT
  • 素材格式:.ppt
  • 关键提要:人工智能及应用_ch3_3,人工智能
  • 素材版本:PowerPoint2003及以上版本(.ppt)
网友评分:
PPT介绍优秀PPT相关PPT精品PPT

这是人工智能及应用_ch3_3ppt,包括了归结反演求取问题的答案,归结演绎推理的策略,基于规则的演绎推理等内容,欢迎点击下载。

PPT预览

人工智能及应用_ch3_3ppt

PPT内容

经典逻辑推理
归结反演求取问题的答案
归结演绎推理的策略
基于规则的演绎推理
归结反演求取问题的答案
归结原理还可以用于求取问题答案,其思想与定理证明相似,求解步骤为;
把已知前提用谓词公式表示,并化为子句集S;
把待求解的问题用谓词公式表示,然后把它的否定与谓词ANWSER析取构成析取式,ANWSER的变元与问题谓词的变元完全一致;
把此析取式化为子句集,并添加到S中,构成新的子句集S1;
对S1使用归结原理,直到得到归结式ANWSER,则问题答案在谓词ANWSER中。
归结反演求取问题的答案-示例
例:已知王先生是小李的老师,小李与小张是同班同学,如果x与y是同班同学,则x的老师也是y的老师。求小张的老师是谁?
解:定义谓词
   T(x,y):x是y的老师;
   C(x,y):x与y是同班同学。
归结反演求取问题的答案-示例
用谓词表示已知条件
T(Wang,Li):王先生是小李的老师;
C(Li,Zhang):小李与小张是同班同学;
(∀x) (∀y) (∀z)(C(x,y)ΛT(z,x)→T(z,y)):如果x与y是同班同学,则x的老师也是y的老师。
归结反演求取问题的答案-示例
化子句集
T(Wang,Li)
C(Li,Zhang)
¬C(x,y)V¬T(z,x)VT(z,y)
表达待求解问题
 (∃u)T(u,Zhang)
  ¬ (∃u)T(u,Zhang)VANWSER(u)
归结反演求取问题的答案-示例
化子句集
  ¬(∃u)T(u,Zhang)VANWSER(u)
 ⇔ (∀u)¬T(u,Zhang)VANWSER(u) ⇔
4.¬T(u,Zhang)VANWSER(u)
进行归结
  1⊕3→5  ¬C(li,y)V¬T(Wang,y)
  4⊕ 5→ 6    ¬C(li,Zhang)VANWSER(Wang)
    2⊕ 6→           ANWSER(Wang)
归结树
归结演绎推理的策略
用产生式系统表示归结过程
综合数据库:子句集S
规则集:IF  C1和C2有归结式C12  THEN S=S∪{C12}
目标条件:NIL∈S
归结演绎推理的策略
产生式系统基本算法
初始化综合数据库,把问题的已知事实送入综合数据库。
若规则库中存在尚未使用过的规则,若有则执行3;否则转7。
检查规则库中未使用的规则前件能否与综合数据库中的事实匹配,若有从中选择一个;否则转6。
执行当前选中的规则,并标记,将结论加入综合数据库,若结论是操作,则执行操作。
检查综合数据库中是否包含了问题的解,若包含,问题解决,求解过程结束;否则转2。
当规则库有未使用的规则,但均不能与已知事实匹配,要求用户提供新的事实,若提供,则转2;否则,问题无解停止求解过程。
若规则库中不再有未使用过的规则,问题无解,停止求解过程。
归结演绎推理的策略
初始化综合数据库DB=S;
若NIL∈DB,停止问题得证;
DB中是否有可归结的子句,若有执行下一步,否则转7;
从DB中选择两个不同的可归结子句C1和C2;
求C1和C2的归结式C12;
DB=DB∪{C12},返回2;
停止,无法证明问题。
归结的一般过程
归结过程是从子句集中不断寻找可归结子句对进行归结,直到归结出空子句或没有可归结子句对为止。一般的归结过程如下:
设初始子句集S0 =S,对中的全部子句作所有可能的归结,得到第一层归结式,把这些归结式的集合记为S1。
用S0中的子句和S1 中的子句进行所有可能的归结,得到第二层归结式,把这些归结式的集合记为S2。
归结的一般过程-示例
用S0和S1中的子句与S2中的子句进行所有可能的归结,得到第三层归结式,把这些归结式的集合记为S3。
重复此过程直到得到空子句或不能继续归结为止。
一般称如上的归结策略为广度优先策略。
归结的一般过程-示例
例:设有如下子句集
     S={¬I(x)VR(x),I(a),¬R(y)VL(y),¬L(a)}
用广度优先策略证明S不可满足。
证明:从S出发,依次构造S1 ,S2 ,S3 ,。。。直到出现空子句为止。
示例的归结图
归结演绎中的策略
盲目全面进行归结,产生许多无用归结式,更严重的是产生组合爆炸问题。
常用的归结策略分为两大类:
删除策略:通过删除某些无用的子句缩小归结的范围。
限制策略:通过对参加归结的子句进行某些限制减少归结的盲目性。
删除策略-纯文字删除
如果某个文字L在子句集中不存在与其互补的文字¬L,称此文字为纯文字。
纯文字删除法是删除子句集中包含纯文字的子句。
例:设子句集 S={PVQVR,¬QVR,Q,¬R}
   P为纯文字,删除子句PVQVR,然后对{¬QVR,Q,¬R}进行归结。
删除策略-重言式删除
如果一个子句中包含有互补文字,称该子句为重言式。
子句PV¬PVQ是一个重言式,显然这个子句的真值是真,在子句集中删除此子句,不影响子句集的不可满足性。
重言式删除法是将子句集中的重言式删除。
删除策略-包孕删除
设子句C1和C2 ,如果存在一个置换σ,使得C1σ⊆C2,则称C1包孕于C2。
例:P(x) 包孕于 P(y)VQ(z)  σ={y/x}
对子句集来说把包孕子句删除,不影响子句集的不可满足性。
包孕删除法:从子句集中删除包孕子句。
删除策略的完备性
以上的几种删除策略是否为完备的归结策略?
限制策略-支持集策略
支持集策略是沃斯等人在1965年提出的一种归结策略。它要求参加归结的两个亲本子句中至少有一个是由目标公式的否定所得到的子句或是它们的后裔。
可以证明支持集策略是完备的,即子句集不可满足时,使用支持集策略一定可以归结出空子句。
支持集策略-示例
限制策略-单文字子句策略
如果一个子句只包含一个文字,则称此子句是一个单文字子句。
单文字子句策略:要求参加归结的两个亲本子句中至少有一个子句是单文字子句。
单文字子句策略是不完备的。
单文字子句策略-示例
限制策略-线性输入策略
这种策略要求每次参加归结的两个亲本子句中,至少有一个是初始子句集中的子句。
线性输入策略是一种不完备的归结策略。例如S={Q(u)VP(u),¬Q(x)VP(x), ¬Q(y)V¬P(y), ¬Q(w)V ¬P(w)} 是不可满足的,但使用线性输入策略无法得到空子句。
线性输入策略-示例
限制策略-祖先过滤策略
要求参加归结的两个亲本子句满足以下两个条件中的任意一个:
参加归结的两个亲本子句中,至少有一个是初始子句集中的子句。
如果两个亲本子句都不是初始子句集的子句,则一个应是另一个的先辈子句。
可以证明,祖先过滤策略是完备的。
祖先过滤策略-示例
基于规则的演绎推理
归结演绎方便了机器推理,但在化子句集时损失了一些控制信息。例如:如下的子句
                     PVQVR
   其可由下面的几个公式等价得到。
   ¬PΛ¬Q→R、 ¬RΛ¬Q→P、 ¬PΛ¬R→Q、  。。。
基于规则的正向演绎推理
定理证明问题:已知一组事实,以及相关的领域知识,证明目标。一般情况下,已知事实和目标是用谓词公式表达,而相关领域的知识是由一组蕴含式表达,我们将这组蕴含式称为规则。
从事实出发,正向使用规则(F规则),直接进行演绎,直至达到目标为止的一种证明方法。
基于规则的正向演绎推理
为了实现正向推理,需要对定理证明问题的已知事实、规则和证明目标按一定的形式表示出来。下面讨论表示形式的转换。
基于规则的正向演绎推理
事实表达式的与/或形变换:基于规则的正向演绎推理通常将已知事实化为与/或形,化与/或形的基本步骤如下:
利用规则P→Q⇔¬PVQ消去蕴含符号。
利用狄。摩根定律及量词转换律把¬移到紧靠谓词,使否定连接词的辖域只含一个谓词。
化为前束范式。
变元标准化。
消去全称量词。
基于规则的正向演绎推理
例:将公式化为与/或形 (∃x)(∀y)(Q(y,x)Λ¬((R(y)VP(y))ΛS(x,y)))
解: (∃x)(∀y)(Q(y,x)Λ¬((R(y)VP(y))ΛS(x,y)))⇔ (∃x)(∀y)(Q(y,x)Λ(¬(R(y)VP(y))V¬S(x,y)))   ⇔
 (∃x)(∀y)(Q(y,x)Λ((¬R(y)Λ¬P(y))V¬S(x,y))) ⇔ (∃x)(∀y)(Q(y,x)Λ((¬R(y)Λ¬P(y))V¬S(x,y))) ⇔
   (∀y)(Q(y,a)Λ((¬R(y)Λ¬P(y))V¬S(a,y)))        ⇔
   Q(y,a)Λ((¬R(y)Λ¬P(y))V¬S(a,y))
基于规则的正向演绎推理
事实表达式的与/或树:为了推理过程直观将事实表达式的与/或形表示为一棵与/或树。
基于规则的正向演绎推理
与/或树中的结点表示与/或形中的一个子表达式,表达式间的关系规定如下:
表达式E为k个子表达式析取时即E=E1VE2V…V Ek,每个子表达式Ei均被表示为E的后继结点,并由一个k连接符将这些后继结点连接到父结点,即表示成与的关系。
表达式E为k个子表达式合取时即E=E1ΛE2Λ…ΛEk,每个子表达式Ei均被表示为E的后继结点,并由一个单一连接符将这些后继结点连接到父结点,即表示成或的关系。
基于规则的正向演绎推理
例:将Q(y,a)Λ((¬R(y)Λ¬P(y))V¬S(a,y))表示为与/或树。
基于规则的正向演绎推理
与/或树的特点
根结点是事实表达式的与/或形,端结点是事实表达式中的一个文字。
解树集对应着子句集。例中的三个解树对应着三个子句, Q(y,a),¬R(y)V¬S(a,y),¬P(y) V¬S(a,y)
基于规则的正向演绎推理
规则的与/或形变换:基于规则的正向演绎推理中要求规则要具有L→W的形状,其中L为单文字,W为与/或形。
规则的变换步骤:
利用规则P→Q⇔¬PVQ暂时消去蕴含符号。
利用狄。摩根定律及量词转换律把¬移到紧靠谓词,使否定连接词的辖域只含一个谓词。
引入Skolem函数,消去存在量词。
化为前束范式,消去全称量词。
恢复蕴含式表示。
基于规则的正向演绎推理
例:(∀x)(((∃y)(∀z)(P(x,y,z))→(∀u)Q(x,u))    ⇔
       (∀x)(¬((∃y)(∀z)(P(x,y,z))V(∀u)Q(x,u))   ⇔
       (∀x)((∀y)(∃z)(¬P(x,y,z))V(∀u)Q(x,u))    ⇔
       (∀x)((∀y)(¬P(x,y,f(x,y)))V(∀u)Q(x,u))    ⇔
       ¬P(x,y,f(x,y))VQ(x,u)                            ⇔
       P(x,y,f(x,y))→Q(x,u)
基于规则的正向演绎推理
若出现规则前件非单文字时,如
     L1VL2→W
  将其等价为两个规则:
          L1→W
                  L2→W
基于规则的正向演绎推理
目标公式的表示形式:基于规则的正向演绎推理要求将目标公式表达为子句集的形式。
基于规则的正向演绎推理过程
命题逻辑:设已知事实表示为如下的与/或形
           ((PVQ)ΛR)V(SΛ(TVU))
规则为 
      S→(XΛY)VZ
基于规则的正向演绎推理过程
基于规则的正向演绎推理过程
已知事实的四个子句
SVR
SVPVQ
RVTVU
PVQVTVU
规则化为子句的两个子句
¬SVXVZ
¬SVYVZ
基于规则的正向演绎推理过程
应用规则后的与/或树的子句(解图)有六个
XVZVR
YVZVR
XVZVPVQ
YVZVPVQ
RVTVU
PVQVTVU
基于规则的正向演绎推理过程
前面的四个子句是已知事实和规则表示的子句进行归结得到的所有归结式。
既有规则应用结果,就是归结式的完备集,即规则的应用演绎出所有的逻辑推论。
基于规则的正向演绎系统的演绎过程就是不断地调用匹配的规则,对与/或树进行变换,直到生成的与/或树含有目标表达式为止。
基于规则的正向演绎推理-示例
已知事实表达式:AVB
规则集:A→CΛD
               B→EΛF
目标公式:CVF
基于规则的正向演绎推理-示例
基于规则的正向演绎推理过程
谓词逻辑:与命题逻辑的推理过程的主要区别在于,已知事实、规则和目标公式的标准化时要考虑变元和Skolem函数,使用规则匹配时需要合一处理。
基于规则的正向演绎推理-示例
事实:Fido barks and bites,or Fido is not a dog.
   ¬DOG(Fido)V(BARKS(Fido)ΛBITES(Fido))
规则:ALL terriers are dogs.
       (∀x)(¬DOG(x)→¬TERRIES(x))
          Anyone who barks is noisy
            (∀y)(BARKS(y)→NOISY(y))
目标:There exists someone who is not a terrier or who is noisy.
       (∃z)(¬TERRIER(z)VNOISY(z))
基于规则的正向演绎推理-示例
基于规则的逆向演绎推理
逆向演绎系统:是从目标出发,反方向使用规则(B规则)对目标表达式的与/或树进行变换,最后得到含有事实结点的图。
逆向演绎系统对已知事实、规则和目标公式的表示形式要求与正向的形式对偶。
基于规则的逆向演绎推理
目标公式转换为与/或形。
B规则的形式为W→L,其中W为与/或形,L为单文字。
已知事实表达为文字的合取,即表达为短语。
基于规则的逆向演绎推理-示例
事实:DOG(Fido)               Fido是一只狗
           ¬BARKS(Fido)         Fido是不叫的
           WAGS-TAIL(Fido)   Fido摇尾巴  
          MEOWS(Myrtle)       猫咪的名字是Myrtle
规则:摇尾巴的狗是温顺的狗。
  WAGS-TAIL(x)Λ DOG(x)→FRIENDLY(x)
温顺不叫的东西不值得害怕。
  FRIENDLY(y)Λ¬BARKS(y)→¬AFRAID(z,y)
基于规则的逆向演绎推理-示例
    DOG(u)→ANIMAL(u)     狗是动物
    CAT(v)→ANIMAL(v)       猫是动物
    MEOWS(w)→CAT(w)     猫咪是猫
目标:存在一只猫和一只狗,这只猫不害怕这只狗。
   (∃x)(∃y)(CAT(x)ΛDOG(y)Λ¬AFRAID(x,y))
基于规则的逆向演绎推理-示例
 

相关PPT

人工智能基础03--搜索技术ppt:这是人工智能基础03--搜索技术ppt,包括了盲目搜索,启发式搜索,博弈树搜索,遗传算法,模拟退火算法,免疫算法等内容,欢迎点击下载。
人工智能基础07--自动规划系统ppt:这是人工智能基础07--自动规划系统ppt,包括了自动规划概述,基于谓词逻辑的规划,STRIPS规划系统,分层规划,基于专家系统的机器人规划,轨迹规划简介等内容,欢迎点击下载。
人工智能第二章人工智能的数学基础ppt:这是人工智能第二章人工智能的数学基础ppt,包括了命题,谓词,谓词公式,概率论,随机现象,样本空间与随机事件,事件的概率,全概率公式与Bayes公式,模糊理论,模糊性,模糊集与隶属函数,模糊集的表示方法,模糊集的运算,模糊度,模糊关系及其合成,模糊变换,模糊集的水平截集,模糊数等内容,欢迎点击下载。
《人工智能及应用_ch3_3ppt》是由用户Hatsukoi于2018-03-29上传,属于行业PPT。

精品推荐 人工智能ppt

更多 ( 380 个) >> 人工智能ppt PPTOK为广大PPT爱好者展示用户上传的《人工智能》PPT集合大全,欢迎点击下载哦。人工智能(Artificial Intelligence),英文缩写为AI。它是研究、开发用于模拟、延伸和扩展......
  • 优秀PPT

    缩略图

    • 人工智能及应用_ch3_3ppt

    下载地址

    • 人工智能及应用_ch3_3ppt

    相关PPT

    推荐

    颜色分类黑色秒速1分6合-好运3分6合橙色秒速1分6合-好运3分6合紫色秒速1分6合-好运3分6合蓝色秒速1分6合-好运3分6合黄色秒速1分6合-好运3分6合红色秒速1分6合-好运3分6合绿色秒速1分6合-好运3分6合彩色秒速1分6合-好运3分6合黑白秒速1分6合-好运3分6合

    行业分类科技秒速1分6合-好运3分6合医学秒速1分6合-好运3分6合教育秒速1分6合-好运3分6合工业秒速1分6合-好运3分6合金融秒速1分6合-好运3分6合音乐秒速1分6合-好运3分6合汽车房地产互联网培训手机

    实用必备个人简历自我介绍年终总结职业规划述职报告工作汇报工作总结岗位竞聘公司简介发布会年会论文答辩

    PPT推荐语文课件数学课件英语课件美术课件物理课件科学课件化学课件地理课件生物课件主题班会家长会绘本故事

    节日PPT新年元旦节农历春节情人节元宵节三八妇女节愚人节清明节五一劳动节母亲节六一儿童节端午节

    节日PPT 父亲节七夕情人节教师节中秋节国庆节重阳节万圣节光棍节感恩节平安夜圣诞节纪念日