人工智能导论-第二章-001-2014

1、第二章 知识表示方法,2.1 知识和知识表示 2.2 状态空间表示 2.3 问题归约表示 2.4 谓词逻辑表示 2.5 语义网络表示 2.6 产生式表示 2.7 框架表示 2.8 面向对象表示,2020/9/15,人工智能导论 - 刘珊,1,1个字节由8个“位”构成。 一个扇区有512个“字节”的数据。,糖是甜的。 一年有春、夏、秋、冬四个季节。,知识的概念,知识的定义 (1) Feigenbaum：知识是经过剪裁、塑造、解释、选择和转换了的信息 (2)把有关信息关联在一起所形成的信息结构。 (3)反映了客观世界中事物之间的关系，不同事物或者相同事物间的不同关系形成了不同的知识。 知识的类型

2、常识性知识 -陈述性知识 领域性知识 -过程性知识 -控制性知识,2020/9/15,人工智能导论 - 刘珊,2,2.1 知识和知识表示的概念,知识的特性,相对正确性 任何知识都是在一定的条件及环境下产生的，在这种条件及环境下才是正确的。,1+1=2 （十进制） 1+1=10 (二进制）,不确定性,随机性引起的不确定性 模糊性引起的不确定性 经验引起的不确定性 不完全性引起的不确定性,知识状态：“真”、“假” “真”与“假”之间的中间状态,“如果头痛且流涕，则有可能患了感冒”,小李很高,2.1 知识和知识表示的概念,2020/9/15,人工智能导论 - 刘珊,3,知识的特性,可表示性与可利用性

3、 知识的可表示性: 知识可以用适当形式表示出来，如用语言、文字、图形、神经网络等。 知识的可利用性：知识可以被利用。,2020/9/15,人工智能导论 - 刘珊,4,2.1 知识和知识表示的概念,知识表示的概念,知识表示 对知识的描述，即用一组符号把知识编码成可以被计算机直接识别、并便于系统使用的数据结构。 知识表示的要求 表示能力 可利用性 可组织性与可维护性 可实现性 自然性与可理解性,2020/9/15,人工智能导论 - 刘珊,5,2.1 知识和知识表示的概念,表示方法,2020/9/15,人工智能导论 - 刘珊,6,表示方法,直接表示,局部表示,分布表示,陈述性表示,过程性表示,语义网

4、络表示,产生式表示,逻辑表示,框架表示,脚本表示,替代表示,第二章 知识表示方法,2.1 知识和知识表示 2.2 状态空间表示 2.3 问题归约表示 2.4 谓词逻辑表示 2.5 语义网络表示 2.6 产生式表示 2.7 框架表示 2.8 面向对象表示,2020/9/15,人工智能导论 - 刘珊,7,2.2 状态空间表示,状态空间表示法的基本思想 将待求解的问题通过状态和算符表示出来 状态：描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合。 算符也称为操作符：将问题从一种状态变换为另一种状态的手段 状态空间：表示该问题全部可能状态及其关系，三元状态（S，F，G）或二元状态

5、（S, O）,2020/9/15,人工智能导论 - 刘珊,8,2.2 状态空间表示,9,例:三数码难题（3 puzzle problem）,初始棋局,目标棋局,2020/9/15,人工智能导论 - 刘珊,2.2 状态空间表示,10,有向图：由节点的集合构成，一对节点用有向弧线连接。 状态空间图：表示状态空间的有赋值的有向图。 路径 代价 图的显示说明：各节点及其代价的弧线由一张表明确给出。 图的隐式说明：节点的无限集合si作为起始节点已知，后续节点算符已知，由 和si 规定隐式图。,状态图示法,2020/9/15,人工智能导论 - 刘珊,2.2 状态空间表示,状态空间表示举例,例：猴子摘香蕉问

6、题,2020/9/15,人工智能导论 - 刘珊,11,2.2 状态空间表示,12,解题过程,用一个四元表列（M，p1，B，p2）来表示这个问题状态. 初始状态：（a，0，b，0） 目标状态：（c，1，c，1）,这个问题的算符如下： goto（U）表示猴子走到水平位置U 或者用产生式规则表示为 （M，0，B，0） goto（U） （U，0，B，0）,2020/9/15,人工智能导论 - 刘珊,2.2 状态空间表示,13,pushbox（V）猴子把箱子推到水平位置V，即有 （B，0，B，0） pushbox（V） （V，0，V，0）,climbbox 猴子爬上箱顶，即有 （B，0，B，0） cli

7、mbbox （B，1，B，0）,2020/9/15,人工智能导论 - 刘珊,2.2 状态空间表示,解题过程,14,grasp 猴子摘到香蕉，即有 （c，1，c，0） grasp （c，1，c，1）,初始状态变换为目标状态的操作序列为 goto(b), pushbox(c), climbbox, grasp,2020/9/15,人工智能导论 - 刘珊,2.2 状态空间表示,解题过程,15,猴子摘香蕉问题的状态空间图,2020/9/15,人工智能导论 - 刘珊,2.2 状态空间表示,第二章 知识表示方法,2.1 知识表示的概念 2.2 状态空间表示 2.3 问题归约表示 2.4 谓词逻辑表示 2.

8、5 语义网络表示 2.6 产生式表示 2.7 框架表示 2.8 面向对象表示,2020/9/15,人工智能导论 - 刘珊,16,17,2.3 问题归约表示,子问题1,子问题n,原始问题,子问题集,本 原 问 题,2020/9/15,人工智能导论 - 刘珊,2.3 问题归约表示,18,问题归约表示的组成部分： 一个初始问题描述； 一套把问题变换为子问题的操作符； 一套本原问题描述。,问题归约的实质： 从目标（要解决的问题）出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。,2020/9/15,人工智能导论 - 刘珊,2.3 问题归约表示,分解与变换,分解

9、 如果一个问题可以归约为一组子问题，并且当且仅当所有子问题都有解时原问题才有解，则称这种归约为问题的分解。 分解所得的子问题的“与”与原问题等价。 等价变换 如果一个问题可以归约为一组子问题，并且只要有一个子问题有解则原问题有解，则称这种归约为问题的等价变换，简称变换。 变换所得的子问题的“或”与原问题等价。,2020/9/15,人工智能导论 - 刘珊,19,2.3 问题归约表示,20,与、或图,与图,或图,2020/9/15,人工智能导论 - 刘珊,2.3 问题归约表示,21,2020/9/15,人工智能导论 - 刘珊,2.3 问题归约表示,与/或图,22,与或图的术语,父节点,与节点,弧线

10、,或节点,子节点,终叶节点,2020/9/15,人工智能导论 - 刘珊,2.3 问题归约表示,端节点,23,与或图的术语,t,t,t,t,t,t,t,t,t,（a）,（b）,可解节点,无解节点,终叶节点,2020/9/15,人工智能导论 - 刘珊,2.3 问题归约表示,24,不可解节点的一般定义 没有后裔的非终叶节点为不可解节点。 含有或后继节点，且全部后裔为不可解，此非终叶节点是不可解的。 含有与后继节点，后裔至少有一个为不可解，此非终叶节点是不可解的。,2020/9/15,人工智能导论 - 刘珊,2.3 问题归约表示,25,梵塔难题,2020/9/15,人工智能导论 - 刘珊,2.3 问题

11、归约表示,26,1、首先定义该问题的形式化表示方法。 设用三元组 (i, j, k) 表示问题在任一时刻的状态，用“”表示状态的转换。其中 i 代表金片A所在的钢针号 j 代表金片B所在的钢针号 k 代表金片C所在的钢针号,解题过程,2020/9/15,人工智能导论 - 刘珊,2.3 问题归约表示,27,解题过程,2020/9/15,人工智能导论 - 刘珊,2.3 问题归约表示,2、原问题可分解为三个子问题： (1, 1, 1) (2, 2, 1) (2, 2, 1) (2, 2, 3) (2, 2, 3) (3, 3, 3) 3、进一步分解,(1, 1, 1),(2, 2, 1),(2, 2

12、, 3),(3, 3, 3),2020/9/15,人工智能导论 - 刘珊,28,(1, 1, 1) (3, 3, 3),(1, 1, 1) (2, 2, 1),(2, 2, 1) (2, 2, 3),(2, 2, 3) (3, 3, 3),(1, 1, 1) (3, 1, 1),(3, 2, 1) (2, 2, 1),(3, 1, 1) (3, 2, 1),(2, 2, 3) (1, 2, 3),(1, 2, 3) (1, 3, 3),(1, 3, 3) (3, 3, 3),三阶梵塔问题的分解过程可用下图表示,2.3 问题归约表示,第二章 知识表示方法,2.1 知识表示的概念 2.2 状态空间

13、表示 2.3 问题归约表示 2.4 谓词逻辑表示 2.5 语义网络表示 2.6 产生式表示 2.7 框架表示 2.8 面向对象表示,2020/9/15,人工智能导论 - 刘珊,29,逻辑,2020/9/15,人工智能导论 - 刘珊,30,2.4 谓词逻辑表示,命题逻辑,2020/9/15,人工智能导论 - 刘珊,31,命题逻辑：研究命题及命题之间关系的符号逻辑系统。 命题逻辑表示：无法把它所描述的事物的结构及逻辑特征反映出来，也不能把不同事物间的共同特征表述出来。,命题：一个非真即假的陈述句。 若命题的意义为真，称它的真值为真，记为 T。 若命题的意义为假，称它的真值为假，记为 F。 一个命题

14、可在一种条件下为真，在另一种条件下为假。,例如：35,例如：太阳从西边升起,P：老李是小李的父亲,P：北京是中华人民共和国的首都,P：李白是诗人 Q：杜甫也是诗人,例: 1110,2.4 谓词逻辑表示,谓词,2020/9/15,人工智能导论 - 刘珊,32,2.4 谓词逻辑表示,谓词的一般形式： P (x1, x2, xn) 个体 x1, x2, xn ：某个独立存在的事物或者某个抽象的概念； 谓词名 P：刻画个体的性质、状态或个体间的关系。,“老张是一个教师”：一元谓词 Teacher (Zhang) “53” ：二元谓词 Greater (5, 3) “Smith作为一个工程师为IBM工作

15、”： 三元谓词 Works (Smith, IBM, engineer),（1）个体是常量：一个或者一组指定的个体。,谓词,2020/9/15,人工智能导论 - 刘珊,33,（2）个体是变元（变量）：没有指定的一个或者一组个体。,“小李的父亲是教师”：Teacher (father (Li) ),（3）个体是函数：一个个体到另一个个体的映射。,“x5” ：Less(x, 5),（4）个体是谓词,“Smith作为一个工程师为IBM工作”： 二阶谓词 Works (engineer (Smith), IBM),2.4 谓词逻辑表示,谓词与函数的区别,谓词是个体域D到T，F的映射，函数是D到D的映射

16、 谓词的真值是T和F，函数的值（无真值）是D中的元素 谓词可独立存在，函数只能作为谓词的个体。,2020/9/15,人工智能导论 - 刘珊,34,2.4 谓词逻辑表示,1. 连接词（连词）,（1）： “否定” 或 “非”。 （2）： “析取”或。 （3）： “合取”与。,“机器人不在2号房间”： Inroom (robot, r2),“李明打篮球或踢足球”： Plays (Liming, basketball) Plays (Liming, football),“我喜欢音乐和绘画”： Like (I, music) Like (I, painting),35,9/15/2020,人工智能导论

17、- 刘珊,2.4 谓词逻辑表示,2020/9/15,1. 连接词（连词）,（4）：“蕴含” 或 “条件”。,“如果刘华跑得最快，那么他取得冠军。” ： RUNS (Liuhua，fastest)WINS (Liuhua ，champion),（5） ：“等价” 或“双条件”。 P Q: “P当且仅当Q”。,36,9/15/2020,人工智能导论 - 刘珊,2.4 谓词逻辑表示,2020/9/15,谓词逻辑真值表,37,9/15/2020,人工智能导论 - 刘珊,2.4 谓词逻辑表示,2020/9/15,2. 量词,（1）全称量词（x）：“对个体域中的所有（或任一个）个体 x ”。,“所有的机器

18、人都是灰色的”： (x)ROBOT (x) COLOR (x，GRAY),（2）存在量词（ x）：“在个体域中存在个体 x ”。,“1号房间有个物体”： （ x）INROOM（x，r1）,38,9/15/2020,人工智能导论 - 刘珊,2.4 谓词逻辑表示,2020/9/15,全称量词和存在量词出现的次序将影响命题的意思。 例如：,(x)( y)(Employee(x) Manager(y, x) : “每个雇员都有一个经理。” ( y)(x)(Employee(x) Manager(y, x): “有一个人是所有雇员的经理。”,39,9/15/2020,人工智能导论 - 刘珊,2.4 谓词

19、逻辑表示,2020/9/15,3. 谓词公式,规则,(1)单个谓词是谓词公式，称为原子谓词公式。 (2)若A是谓词公式，则A也是谓词公式。 (3)若A，B都是谓词公式，则AB，AB，AB， A B也都是谓词公式。 若A是谓词公式，则 (x) A，( x)A也是谓词公式。 有限步应用(1)-(4)生成的公式也是谓词公式。,连接词的优先级别从高到低排列： ， ， ， ，,40,9/15/2020,人工智能导论 - 刘珊,2.4 谓词逻辑表示,2020/9/15,置换和合一,置换 假元推理、全称化推理、综合推理 在该表达式中用置换项置换变量 可结合，不可交换 合一 寻找对变量的置换，以使两表达式一致

20、,2020/9/15,人工智能导论 - 刘珊,41,W1，W1 W2 W2,(x)W(x) W(A),4量词的辖域,量词的辖域：位于量词后面的单个谓词或者用括弧括起来的谓词公式。 约束变元与自由变元：辖域内与量词中同名的变元称为约束变元，不同名的变元称为自由变元。,例如： ( x)(P(x, y) Q (x, y)R(x, y) (P(x, y) Q (x, y) ：( x)的辖域，辖域内的变元x是受（ x）约束的变元，R(x, y)中的x是自由变元。 公式中的所有y都是自由变元。,42,9/15/2020,人工智能导论 - 刘珊,2.4 谓词逻辑表示,2020/9/15,谓词逻辑表示步骤,（

21、1）根据要表示的知识定义谓词； （2）用连接词、量词连接各个谓词，形成谓词公式。,Occupant,Telephone,43,9/15/2020,人工智能导论 - 刘珊,2.4 谓词逻辑表示,2020/9/15,用一阶谓词表示： Occupant（Zhang ， 201） Occupant（Li，201） Occupant（Wang， 202） Occupant（Zhao， 203） Telephone（491，201） Telephone（492，201） Telephone（451，202） Telephone（451，203）,44,9/15/2020,人工智能导论 - 刘珊,2.4 谓

22、词逻辑表示,2020/9/15,简例,用谓词逻辑表示如下知识：王宏是计算机系的一名学生， 王宏和李明是同班同学，凡是计算机系的学生都喜欢编程序。 解：1、先定义谓词： CS(x)：表示x是计算机系的学生。 CM(x,y)：表示x和y是同班同学。 L (x,y)：表示x喜欢y。 2、然后再将知识表示为： CS(Wang hong) CM(Wanghong, Li ming) (x)(CS(x) L (x, programming),2020/9/15,人工智能导论 - 刘珊,45,2.4 谓词逻辑表示,机器人移盒子问题,假设在一个房间里，c处有一个机器人，a和b处各有一张桌子，分别称为a桌和b桌

23、，a桌上有一个盒子，要求机器人从c处出发把盒子从a桌上搬到b桌上，然后回到c处。请用谓词逻辑表示方法描述这个问题。,2020/9/15,人工智能导论 - 刘珊,46,2.4 谓词逻辑表示,机器人移盒子问题,解：1、分别定义描述状态和操作的谓词 描述状态的谓词： TABLE( x)：x是桌子 EMPTY( y )：y手中是空的 AT( y, z )：y在z处 HOLDS( y, w )：y拿着w ON(w, x)：w在x桌面上 变元的个体域：x的个体域是a, b y的个体域是robot z的个体域是a, b, c w的个体域是box,2020/9/15,人工智能导论 - 刘珊,47,2.4 谓词

24、逻辑表示,48,机器人移盒子问题,问题的初始状态： AT( robot, c ) EMPTY( robot ) ON( box, a ) TABLE( a ) TABLE( b ),问题的目标状态： AT( robot, c ) EMPTY( robot ) ON( box, b ) TABLE( a ) TABLE( b ),描述操作的谓词 条件部分：用来说明执行该操作必须具备的先决条件，用谓词公式来表示。 动作部分：给出了该操作对问题状态的改变情况，通过在执行该操作前的问题状态中删去和增加相应的谓词来实现。,描述操作的谓词：Goto( x, y )：从x处走到y处。 Pickup( x )

25、：在x处拿起盒子。 Setdown( y )：在x处放下盒子。,9/15/2020,人工智能导论 - 刘珊,2.4 谓词逻辑表示,2020/9/15,各操作的条件和动作：,Goto( x，y ) 条件：AT( robot，x) 动作：删除表：AT( robot，x )；添加表：AT( robot，y ) Pickup( x ) 条件：ON( box，x )，TABLE( x )，AT( robot，x )，EMPTY( robot ) 动作：删除表：EMPTY( robot )，ON( box，x ) 添加表：HOLDS( robot，box ) Setdown( x ) 条件：AT( rob

26、ot，x )，TABLE( x )，HOLDS( robot，box ) 动作：删除表：HOLDS( robot，box ) 添加表：EMPTY( robot )，ON( box，x ),49,9/15/2020,人工智能导论 - 刘珊,2.4 谓词逻辑表示,2020/9/15,50,求解过程,状态3 AT( robot, a ) HOLDS( robot, box ) Pickup( a ) TABLE( a ) = TABLE( b ),状态1(初始状态) AT( robot, c ) EMPTY( robot ) ON( box, a ) TABLE( a ) TABLE( b ),状态

27、2 AT( robot, a ) Goto( c, a) EMPTY( robot ) = ON( box, a ) TABLE( a ) TABLE( b ),9/15/2020,人工智能导论 - 刘珊,2.4 谓词逻辑表示,2020/9/15,51,求解过程,状态6(目标状态) AT( robot, c ) EMPTY( robot ) Goto( b, c ) ON( box, b ) = TABLE( a ) TABLE( b ),状态3 AT( robot, a ) HOLDS( robot, box ) TABLE( a ) TABLE( b ),状态4 AT( robot, b

28、) Goto( a, b ) HOLDS( robot, box ) = TABLE( a ) TABLE( b ),状态5 AT( robot, b) EMPTY( robot ) ON( box, b) TABLE( a ) TABLE( b ）,Setdown( b ),9/15/2020,人工智能导论 - 刘珊,2.4 谓词逻辑表示,2020/9/15,谓词逻辑表示的特征,优点： 自然性 明确 精确 灵活 模块化,局限性： 只能表示确定的知识 组合爆炸 效率低,52,9/15/2020,人工智能导论 - 刘珊,2.4 谓词逻辑表示,2020/9/15,第二章 知识表示方法,2.1 知识

29、表示的概念 2.2 状态空间表示 2.3 问题归约表示 2.4 谓词逻辑表示 2.5 语义网络表示 2.6 产生式表示 2.7 框架表示 2.8 面向对象表示,2020/9/15,人工智能导论 - 刘珊,53,2.5 语义网络表示,定义 一种用实体及其语义关系来表达知识的有向图。 语义基元 语义网络中最基本的语义单元，可用三元组表示为： （节点1，弧，节点2） 基本网元 一个语义基元对应的有向图，是语义网络中最基本的结构单元,54,说明：弧的方向不可随意调换。,2020/9/15,人工智能导论 - 刘珊,2.5 语义网络表示,基本的语义关系,1、实例关系： ISA 体现“具体与抽象”的概念 2

30、、分类关系： AKO 体现“子类与超类”的概念 3、成员关系： A-Member-of 体现“个体与集体”的关系 4、属性关系 指事物和其属性之间的关系。 常用的有：Have，Can,2020/9/15,人工智能导论 - 刘珊,55,主要特征： 属性的继承性,2.5 语义网络表示,基本的语义关系,5、聚类关系 指具有组织或结构特征的“部分与整体”之间的关系。 常用的： Part-of 一般不具备属性的继承性 6、时间关系 7、位置关系 8、相近关系,2020/9/15,人工智能导论 - 刘珊,56,2.5 语义网络表示,一元关系的表示,节点1表示实体，节点2表示实体的性质或属性等，弧表示语义关

31、系。 例：用语义网络表示“动物能运动、会吃” 。,2020/9/15,人工智能导论 - 刘珊,57,2.5 语义网络表示,二元关系的表示,单个二元关系直接用一个基本网元来表示。 复杂关系，可通过一些相对独立的二元或一元关系的组合来实现。,2020/9/15,人工智能导论 - 刘珊,58,例：用语义网络表示：动物能运动、会吃， 鸟是一种动物，鸟有翅膀、会飞；鱼是一种动物，鱼生活在水中、会游泳。,2.5 语义网络表示,多元关系的表示,用语义网络表示多元关系时，可把它转化为一个或多个二元关系的组合； 然后再利用合取、析取等关系的表示方法，把多元关系表示出来。,2020/9/15,人工智能导论 - 刘珊,59,2.5 语义网络表示,动作的表示,设立一个动作节点，用一些向外引出的弧来指出动作的主体与客体。 例：用于语义网络表示“常河给江涛一个优盘”,2020/9/15,人工智能导论 - 刘珊,60,2.5 语义网络表示,情况的表示,例：用语义网络表示“小燕子这只燕子从春天到秋天占有一个巢”,202