人工智能 第二章 知识表示方法.ppt

《人工智能 第二章 知识表示方法.ppt》由会员分享，可在线阅读，更多相关《人工智能 第二章 知识表示方法.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章 知识表示方法2.1 状态空间法2.2 问题归约法2.3 谓词逻辑法2.4 语义网络法2.5 其他方法2.6 小结CSUCSUCSUCSUCSUCSUCSUCSUCSU2.1状态空间法v先看下面的例子v农夫渡河问题v有一农夫带一条狼,一只羊和一筐菜欲从河的东岸渡到河的西岸,但受下列条件限制:v(1)船太小,农夫每次只能带一样东西过河;v(2)如果没有农夫看管,则狼要吃羊,羊要吃菜.v请设计一个过河方案,使得农夫,狼,羊,菜能不受损失地过河.2CSUCSUCSUCSUCSUCSUCSUCSUCSUv先要将问题表示出来,表示成计算机能够处理的数据结构.v该问题可以较好地用状态空间的方法表示.

2、v状态空间的方法:(1)状态集;(2)初始状态,目标状态;(3)规则集合.3CSUCSUCSUCSUCSUCSUCSUCSUCSU用状态空间法表示v用一个四元组(m,n,x,y)表示东岸的状态,其中:vm=0 or 1,n=0 or 1,x=0 or 1,y=0 or 1.vm=1表示人在东岸,m=0表示人不在东岸;vn=1表示狼在东岸,n=0表示狼不在东岸;vx=1表示羊在东岸,x=0表示羊不在东岸;vy=1表示菜在东岸,y=0表示菜不在东岸.4CSUCSUCSUCSUCSUCSUCSUCSUCSU状态集为:v(1,1,1,1),(1,1,1,0),(1,1,0,1),(1,1,0,0)(不

3、合法)v(1,0,1,1),(1,0,1,0),v(1,0,0,1)(不合法),(1,0,0,0)(不合法)v(0,1,1,1)(不合法),(0,1,1,0)(不合法),(0,1,0,1),(0,1,0,0),(0,0,1,1)(不合法),(0,0,1,0),(0,0,0,1),(0,0,0,0),v状态集S为10种状态.5CSUCSUCSUCSUCSUCSUCSUCSUCSU初始状态和目标状态v初始状态为(1,1,1,1);v目标状态为(0,0,0,0).6CSUCSUCSUCSUCSUCSUCSUCSUCSU规则vF0,F1,F2,F3是过河的动作,其中:vF0表示人单独过河;vF1表示人

4、带狼过河;vF2表示人带养过河;vF3表示人带菜过河.7CSUCSUCSUCSUCSUCSUCSUCSUCSU规则vIf(1,n,x,y)S and(0,n,x,y)S then F0;vIf(1,1,x,y)S and(0,0,x,y)S then F1;vIf(1,n,1,y)S and(0,n,0,y)S then F2;vIf(1,n,x,1)S and(0,n,x,1)S then F3.8CSUCSUCSUCSUCSUCSUCSUCSUCSU控制策略vIf m n x y=1 then F2;vIf m x=0 and n y=1 then F0;vIf m n x y=1 the

5、n F1;vIf m n x y=0 then F2;vIf m n x y=1 then F3;vIf m n x y=0 then F0;vIf n y=0 and m x=1 then F2.9CSUCSUCSUCSUCSUCSUCSUCSUCSU解答v(1,1,1,1)F2 (0,1,0,1)v F0 (1,1,0,1)v F1 (0,0,0,1)v F2 (1,0,1,1)v F3 (0,0,1,0)v F0 (1,0,1,0)v F2 (0,0,0,0)10CSUCSUCSUCSUCSUCSUCSUCSUCSU2.1状态空间法v野人渡河问题v设有三个传教士和三个野人来到河边,打算乘

6、一只船从右岸渡到左岸去.该船的负载能力为两人.在任何时候,如果野人人数超过传教士人数,那么野人就会把传教士吃掉.他们怎样才能用这条船安全地把所有人都渡过河去?11CSUCSUCSUCSUCSUCSUCSUCSUCSU状态表示v(3,3,1)(3,1,0)(3,2,1)v (3,0,0)(3,1,1)v (1,1,0)(2,2,1)v (0,2,0)(0,3,1)v (0,1,0)(0,2,1)v (0,0,0)12CSUCSUCSUCSUCSUCSUCSUCSUCSU2.1状态空间法（State Space Representation）v问题求解技术主要是两个方面：v问题的表示v求解的方法v

7、状态空间法v状态（state）v算符（operator）13CSUCSUCSUCSUCSUCSUCSUCSUCSU2.1.1 问题状态描述v定义v状态：描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合。v算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。v问题的状态空间：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。2.1 状态空间法14CSUCSUCSUCSUCSUCSUCSUCSUCSU2.状态空间表示概念详释v例如下棋、迷宫及各种游戏。2.1 状态空间法15CSUCSUCSUCSUCSUCSUCSUCSUCSU

8、例:三数码难题（3 puzzle problem）2.1 状态空间法16CSUCSUCSUCSUCSUCSUCSUCSUCSUv有向图v路径v代价v图的显示说明v图的隐示说明2.1.2 状态图示法AB2.1 状态空间法17CSUCSUCSUCSUCSUCSUCSUCSUCSU2.1.3 状态空间表示举例v产生式系统（production system）v一个总数据库：它含有与具体任务有关的信息随着应用情况的不同，这些数据库可能简单，或许复杂。v一套规则：它对数据库进行操作运算。每条规则由左部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。v一个控制策略：它确定应该采用哪一条适用规

9、则，而且当数据库的终止条件满足时，就停止计算。2.1 状态空间法18CSUCSUCSUCSUCSUCSUCSUCSUCSU 状态空间表示举例状态空间表示举例v例：猴子和香蕉问题2.1 状态空间法19CSUCSUCSUCSUCSUCSUCSUCSUCSU解题过程v 用一个四元表列（W，x，Y，z）来表示这个问题状态.v这个问题的操作（算符）如下：v goto（U）表示猴子走到水平位置Uv或者用产生式规则表示为（W，0，Y，z）goto（U）（U，0，Y，z）2.1 状态空间法20CSUCSUCSUCSUCSUCSUCSUCSUCSUvpushbox（V）猴子把箱子推到水平位置V，即有（W，0，W

10、，z）pushbox（V）（V，0，V，z）vclimbbox猴子爬上箱顶，即有（W，0，W，z）climbbox （W，1，W，z）2.1 状态空间法21CSUCSUCSUCSUCSUCSUCSUCSUCSUvgrasp猴子摘到香蕉，即有（c，1，c，0）grasp （c，1，c，1）v该初始状态变换为目标状态的操作序列为goto(b),pushbox(c),climbbox,grasp2.1 状态空间法22CSUCSUCSUCSUCSUCSUCSUCSUCSU目标状态目标状态goto（U）goto（U）U=b，climbboxgoto（U）U=bpushbox（V）猴子和香蕉问题的状态空间

11、图猴子和香蕉问题的状态空间图goto（U）U=V2.1 状态空间法23CSUCSUCSUCSUCSUCSUCSUCSUCSU2.2 问题归约法（Problem Reduction Representation）子问题子问题1子问题子问题n原始问题原始问题子问题集本本原原问问题题24CSUCSUCSUCSUCSUCSUCSUCSUCSUv 问题归约表示的组成部分：v一个初始问题描述；v一套把问题变换为子问题的操作符；v一套本原问题描述。v问题归约的实质：v从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。2.2 问题规约法25CSU

12、CSUCSUCSUCSUCSUCSUCSUCSU2.2.1 问题归约描述（Problem Reduction Description）v梵塔难题123CBA2.2 问题规约法26CSUCSUCSUCSUCSUCSUCSUCSUCSU解题过程（3个圆盘问题）1231231231321231231231232.2 问题规约法27CSUCSUCSUCSUCSUCSUCSUCSUCSU2.2.2与或图表示v1.与图、或图、与或图2.2 问题规约法ABCD与图ABC或图28CSUCSUCSUCSUCSUCSUCSUCSUCSU2.2 问题规约法BCDEFGAHMBCDEFGAN29CSUCSUCSUCS

13、UCSUCSUCSUCSUCSU2.一些关于与或图的术语2.2 问题规约法HMBCDEFGAN父节点与节点弧线或节点子节点终叶节点30CSUCSUCSUCSUCSUCSUCSUCSUCSU3.定义2.2 问题规约法与或图例子与或图例子ttttttttt（a）（b）有解节点无解节点终叶节点31CSUCSUCSUCSUCSUCSUCSUCSUCSUv不可解节点的一般定义v没有后裔的非终叶节点为不可解节点。v含有或后继节点且全部后裔为不可解的非终叶节点是不可解的。v含有与后继节点且后裔至少有一个为不可解的非终叶节点是不可解的。2.2 问题规约法32CSUCSUCSUCSUCSUCSUCSUCSUCS

14、U梵塔问题归约图（113113）（123123）（111111）（113113）（123123）（122122）（111111）（333333）（122122）（322322）（111111）（122122）（322322）（333333）（321321）（331331）（322322）（321321）（331331）（333333）2.2 问题规约法33CSUCSUCSUCSUCSUCSUCSUCSUCSU2.3 谓词逻辑法v谓词逻辑容许表达那些无法用命题逻辑表达的事情.一阶谓词演算是一种形式语言,其根本目的在于把数学中的逻辑论证符号化.如果能够采用数学演绎的方式证明一个新语句是从那些已知正

15、确的语句导出的,那么也就能够断定这个新语句也是正确的.2.3.1 谓词演算v 1.语法和语义v谓词逻辑的基本组成部分是谓词符号、变量符号、函数符号和常量符号，并用圆括弧、方括弧、花括弧和逗号隔开，以表示论域内的关系。34CSUCSUCSUCSUCSUCSUCSUCSUCSU例1 表示机器人(ROBOT)在1号房间v用原子公式表示如下:vINROOM(ROBOT,r1)v其中:ROBOT和r1为常量符号,INROOM为谓词符号.35CSUCSUCSUCSUCSUCSUCSUCSUCSUv连词和量词(Connective&Quantifiers)v连词v与及合取（conjunction)v或及析取

16、（disjunction）v蕴涵（Implication）v非（Not）v量词v全称量词（Universal Quantifiers)v存在量词(Existential Quantifiers)2.3 谓词逻辑法36CSUCSUCSUCSUCSUCSUCSUCSUCSU2.3.2 谓词公式v原子公式的的定义：v用P(x1，x2，xn)表示一个n元谓词公式，其中P为n元谓词，x1,x2,，xn为客体变量或变元。通常把P(x1,x2,xn)叫做谓词演算的原子公式，或原子谓词公式。v分子谓词公式v可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。2.3 谓词逻辑法37CSUCSUCS

17、UCSUCSUCSUCSUCSUCSUv合适公式（WFF，well-formed formulas）v合适公式的递归定义v合适公式的性质v合适公式的真值v等价（Equivalence)2.3 谓词逻辑法38CSUCSUCSUCSUCSUCSUCSUCSUCSU2.3.3 置换与合一v置换v概念v假元推理v全称化推理v综合推理v定义v就是在该表达式中用置换项置换变量v性质v可结合的v不可交换的2.3 谓词逻辑法39CSUCSUCSUCSUCSUCSUCSUCSUCSUv合一（Unification)v合一：寻找项对变量的置换，以使两表达式一致。v可合一：如果一个置换s作用于表达式集Ei的每个元素

18、，则我们用Ei s来表示置换例的集。我们称表达式集Ei是可合一的。2.3 谓词逻辑法40CSUCSUCSUCSUCSUCSUCSUCSUCSU2.4 语义网络法 （Semantic Network Representation）v语义网络的结构v定义v组成部分v词法v结构v过程v语义41CSUCSUCSUCSUCSUCSUCSUCSUCSUv表示占有关系和其它情况v例：小燕是一只燕子，燕子是鸟；巢-1是小燕的巢，巢-1是巢中的一个。v选择语义基元v试图用一组基元来表示知识，以便简化表示，并可用简单的知识来表示更复杂的知识。2.4 语义网络法2.4.1 二元语义网络的表示42CSUCSUCSUC

19、SUCSUCSUCSUCSUCSU2.4.2 多元语义网络的表示v谓词逻辑与语义网络等效ISA（语义网络）（语义网络）（谓词逻辑）（谓词逻辑）2.4 语义网络法43CSUCSUCSUCSUCSUCSUCSUCSUCSUv多元语义网络表示的实质v把多元关系转化为一组二元关系的组合，或二元关系的合取。可转换为可转换为2.4 语义网络法44CSUCSUCSUCSUCSUCSUCSUCSUCSU2.4.3 连接词和量化的表示v合取v三元变为二元组合v析取v加注析取界限，并标记DIS，以免引起混淆。v否定v两种表示方式：或标注NEG界限。2.4 语义网络法45CSUCSUCSUCSUCSUCSUCSUC

20、SUCSUv蕴涵v在语义网络中可用标注ANTE和CONSE界限来表示蕴涵关系。ANTE和CONSE界限分别用来把与先决条件(antecedent)及与结果(consequence)相关的链联系在一起。v量化v存在量化ISA链v全称量化分割法2.4 语义网络法46CSUCSUCSUCSUCSUCSUCSUCSUCSU2.5其他方法（Others)v框架（Frame）表示v框架是一种结构化表示法，通常采用语义网络中的节点-槽-值表示结构。v剧本（Script）表示v剧本是框架的一种特殊形式，它用一组槽来描述某些事件的发生序列。v过程（Procedure）表示v过程式表示就是将有关某一问题领域的知识

21、，连同如何使用这些知识的方法，均隐式地表达为一个求解问题的过程。47CSUCSUCSUCSUCSUCSUCSUCSUCSU2.6 小结（Summary）v本章所讨论的知识表示问题是人工智能研究的核心问题之一。知识表示方法很多，本章介绍了其中的7种，有图示法和公式法，陈述式表示和过程式表示等。48CSUCSUCSUCSUCSUCSUCSUCSUCSU方法 初始问题算符目标结果 状态 空间法 归约法 谓词逻辑法 语义网络法状态状态结点结点合适公式合适公式结点结点算符算符弧弧 子句集子句集（set of clause）置换合一置换合一消解反演消解反演链链目标状态目标状态结点结点根结点根结点目标网络目标网络解答路径解答路径 （path）解答树解答树 （tree）nil语义网络语义网络知识表示方法间的关系知识表示方法间的关系49