人工智能第二章知识表达技术(王士同人工智能教程第二版)82

2012/10/161人工智能(2)2012/10/162人工智能问题的求解是以知识为基础的.如何将已获得的知识以计算机内部代码形式加以合理的描述、存储，以便有效地利用这些知识便是知识的表示。知识表示方法的提出，常模仿人脑的知识存储结构。这一章将介绍产生式的、逻辑的、语义网络和框架的知识表示方法。第二章知识表达技术2012/10/163第二章知识表达技术课程的基本内容与要求知识的概念与含义，知识类型和知识模型的变换；重点介绍几种常用的知识表达法——状态空间表示法、与/或图表示法、产生式系统、知识的逻辑表达方法、语义网络、框架表达法、特征表表达法和面向对象的表达法。掌握知识表达的基本概念，学会划分知识的类型和理解知识模型变换在解决人工智能问题的过程中的作用与意义；学会如何将一个具体的问题，用所介绍的知识表达方法来表示；初步体会在各种知识表达方法中，其知识机构是如何随知识的运用而变化的。2012/10/164第二章知识表达技术2．1知识的概念与含义智能行为——拥有知识——拥有对知识的获取、表达、搜索、分析、解答等智能能力人的智能的核心也在于人的智能的核心也在于““知识知识””感性知识与理性知识，经验知识与理论知识智能表现在：•知识的获取能力•知识的处理能力•知识的运用能力知识：是人们对自然现象的认识和从中总结出来的规律、经验2012/10/165第二章知识表达技术2．1知识的概念与含义知识模式知识模式K=F+R+CK表示知识项(Knowledgeitems)F表示事实(Facts)——人类对客观世界、客观事物的状态、属性、特征的描述，以及对事物之间关系的描述R表示规则(Rules)——能表达在前提与结论之间的因果关系的一种形式C表示概念(Concepts)——事实的含义规则语义说明等2012/10/166第二章知识表达技术2．2知识表达技术知识类型知识类型叙述型知识——有关系统状态、环境和条件，问题的概念、定义和事实的知识。过程型知识——有关系统状态变化、问题求解过程的操作、演算和行动的知识。控制型知识——有关如何选择相应的操作、演算和行动的比较、判断、管理和决策的知识。例：对于从北京到上海，是乘飞机还是坐火车的问题。•叙述型知识：北京、上海、飞机、火车、时间、费用。•过程型知识：乘飞机、坐火车。•控制型知识：乘飞机较快、较贵；坐火车较慢、较便宜。2012/10/167第二章知识表达技术2．2知识表达技术知识模型变换同构：问题的解答等价于原始问题的解答同态：可使问题更加简化，易于求解同构/同态变换同构变换(明确)同态变换(简化)难求解便于求解等价易求解蕴含原始问题同构问题同态问题原始解答同构解答同态解答原始问题有解，则同态问题有解；同态问题无解，则原始问题无解2012/10/168第二章知识表达技术2．2知识表达技术【例2．1】方格棋盘分割问题原始问题:2n×2n方格盘，去掉对顶角上两方格，问能否将它分割为若干1×2长方块？(a)原始问题2n2n(b)同构问题(c)同态问题初始状态第一次分割2，00，0各种知识模型都是真实问题的有关知识的同构或同态模型。2012/10/169第二章知识表达技术2．2知识表达技术【例2．1】方格棋盘分割问题原始问题:2n×2n方格盘，去掉对顶角上两方格，问能否将它分割为若干1×2长方块？直接求解:考察(2**(2n))**2种可能分割方案，且随着n增大，会“组合爆炸”同构问题:方格相间着色,无论n为何值，对顶角上两方格同色，去掉后白格与黑格的数目间差值为2——最后剩的必是同色两方格——因同构问题无解，所以等价的原始问题无解。同态问题：同态变换——序对小黑格数，小白格数。初始状态：2n2,2n2-2，目标状态：0,0。分割操作：每操作，分割出一长方块，割去一白格和一黑格，使状态变量都减去1。经过2n2-2次操作后，状态变为2,0，不可能达到0,0——因同态问题无解，蕴含着其原始问题也无解2012/10/1610第二章知识表达技术2．3状态空间表达状态用来表示系统状态,事实等叙述型知识的一组变量或数组Q=[q1,q2,…qn]t操作是用来表示引起状态变化的过程型知识的一组关系或函数F:{f1,f2,…fm}状态空间(StateSpace)是利用状态变量和操作符号，表示系统或问题的有关知识的符号体系，状态空间是一个四元组（S，O，S0，G）：S—状态集合;O—操作算子集合;S0—初始状态,S0⊂S;G—目的状态,G⊂S,(G可若干具体状态，也可满足某些性质的路径信息描述)从从SS00结点到结点到GG结点的路径被称为结点的路径被称为求解路径求解路径。状态空间一解是一有限操作算子序列，它使初始状态转换为目标状态：O1O2O3OkS0⎯⎯⎯→S1⎯⎯⎯→S2⎯⎯⎯→……⎯⎯⎯→G其中O1，…，Ok即为状态空间的一个解(解往往不是唯一的)2012/10/1611第二章知识表达技术2．3状态空间表达【例2．2】八数码问题的状态空间在一3×3方格盘，放1到8八个数码，另一格为空。空格四周上下左右数码可移到空格。一布局：23158467八数码任何一种摆法就是一个状态，所有的摆法为状态集S，构成了一个状态空间，其大小为9！相应操作算子是数码移动，其操作算子共有4（方向）×8（数码）=32个。可简化为4个：Up，Left，Down，Right2012/10/1612第二章知识表达技术2．4与/或图表达法超图树图与/或树在求解问题时的两种思维方法：分解：将复杂大问题分解为一组简单小问题若所有子问题都解决了，则总问题也解决了，这是“与”的逻辑关系——“与”树变换：将较难问题变换为较易等价/等效问题若一难问题可以等价变换为几个容易问题，则任何一个容易问题解决了，也就解决了原有难问题，这是“或”的逻辑关系——“或”树兼用兼用““分解分解””和和““变换变换””方法方法————““与与//或或””树树（见（见p20p20图图2.42.4、图、图2.52.5））2012/10/1613第二章知识表达技术2．4与/或图表达法【【例例22．．33】】猴子和香蕉问题猴子和香蕉问题设机器人“猴子”位于a处，目的物“香蕉”挂在c处上方，猴子想吃香蕉，但高度不够，拿不着。在b处有可移动的台子，若猴子站在台子上，就可以拿到香蕉。问题是制定机器人的行动计划，使猴子能拿到香蕉。2012/10/1614第二章知识表达技术2．4与/或图表达法【【例例22．．33】】猴子和香蕉问题猴子和香蕉问题状态空间法:四元数组描述：S=(w,x,y,z)其中：w：猴子所处水平位置x：台子所在水平位置y：猴子是否在台子上（y=1:在;y=0:不在）z：猴子是否能拿到香蕉（z=1:拿到;z=0:没拿到）可能出现的状态如下：S0=(a,b,0,0)S1=(b,b,0,0)S2=(c,c,0,0)S3=(c,c,1,0)S4=(c,c,1,1)其中S0为初始状态，S4为目标状态2012/10/1615第二章知识表达技术2．4与/或图表达法【【例例22．．33】】猴子和香蕉问题猴子和香蕉问题允许的操作集为：F={f1,f2,f3,f4}其中：f1(u)为猴子走到u处(w,x,0,z)→(u,x,0,z)f2(v)为猴子推台子到v处(x,x,0,0)→(v,v,0,0)f3为猴子爬上台子(x,x,0,z)→(x,x,1,z)f4为猴子拿到香蕉(c,c,1,0)→(c,c,1,1)比较目标状态（S4）与初始状态（S0）的差异，来选择主操作。由于S0与S4中的四个状态量都有差异，相应的操作为f1,f2,f3和f4，都可选为主操作。因此，可将原问题变换为四个新问题，而新问题又可分为几个子问题及子子问题。这一过程——与/或树图2012/10/1616第二章知识表达技术2．4与/或图表达法【【例例22．．33】】猴子和香蕉问题猴子和香蕉问题与/或树图P31(f1,f2)P32(f3)P33(f4)P311(f1)P312(f2)S0-S4P1:主操作f1P2:主操作f2P3:主操作f3P4:主操作f4S2-S3S0-S2S3-S4S0-S1S1-S22012/10/1617第二章知识表达技术2．5产生式系统产生式系统产生式系统(productionsystem)(productionsystem)描述若干个不同的以一个基本概念为基础的系统。这个基本概念就是产生式规则或产生式条件和操作对的概念论域知识分为两部分：论域知识分为两部分：1.事实表示静态知识，如事物、事件和它们之间的关系2.产生式规则表示推理过程和行为，如动作，算子，变换等这类系统的知识库主要用于存储规则，因此又把此类系这类系统的知识库主要用于存储规则，因此又把此类系统称为统称为基于规则的系统基于规则的系统(rule(rule--basedsystem)basedsystem)2012/10/1618第二章知识表达技术2．5产生式系统产生式系统的基本结构产生式系统的基本结构一个产生式系统包含事实库、规则集和规则解释（控制器）三部分控制器匹配排序冲突裁决规则集激发树元规则事实库知识匹配相关检索匹配检索2012/10/1619第二章知识表达技术2．5产生式系统事实库事实库——当前已知的知识信息数据，包括推理过程中形成的中间结论知识，换句话说，它用于存储有关问题的状态、性质等事实的叙述型知识，也称为综合数据库或工作存储器。数据是广义的，基本含义是指一个事实或一个断言。在事实库中的数据由规则解释（控制器），用来激活相在事实库中的数据由规则解释（控制器），用来激活相应的规则。应的规则。规则集库规则集库——存储有关问题的状态转移、性质变化等规则的过程型知识，或称“规则库”。2012/10/1620规则集库规则集库产生式规则的一般形式可以表述为：P1,P2,…,PmÆC1,C2,…,Cn每条产生式规则分为左部和右部两个部分，左部表示激活该产生式规则的前提条件/规则前件，右部表示调用该产生式规则后所做的行为部分/规则后件/结论。可简述成“条件-动作”对的形式。对事实库的修改在产生式系统中扮演着推理的角色，正是由于事实库内容的不断改变，才构成了由原始数据到结论的变换过程。第二章知识表达技术2．5产生式系统2012/10/1621第二章知识表达技术2．5产生式系统产生式规则的形式与传统程序设计语言中条件语句非常相似，但实际上两者之间存在根本的区别：区别：产生式规则左部表达的是一组复杂模式，而不仅仅是一个布尔表达式规则之间控制流不象传统语言中从一条语句向其下一条语句传递，而且满足条件的规则被激活但不一定立即执行，这将取决于产生式系统的冲突消解策略，这也是区分传统程序与产生式系统行为特征的关键关键逻辑程序中的语句可以视作产生式规则的一种特殊形式在产生式系统中，一条规则仅描述前提条件与行为之间的静态关系，因此，规则的正确性应当独立地得到保证。这就是规则的自含自含性性，正是由于产生式规则的自含性特点，才使得知识的表示与控制的分离分离成为可能。2012/10/1622第二章知识表达技术2．5产生式系统规则解释（控制器）——根据有关问题的控制型知识，选择控制策略，将规则与事实进行匹配，控制并利用知识进行推理并求解问题通常从选择规则到执行操作分3步：匹配、冲突消解和操作——由匹配器负责判断规则条件是否成立，冲突消解器负责选择可调用的规则，解释器负责执行规则的动作，并在满足结束条件时终止产生式系统的运行。2012/10/16232012/10/1623第二章知识表达技术2．5产生式系统规则解释（控制器）1.1.匹配匹配——当前事实库内容与规则条件部分匹配。如果两者完全匹配，则把这条规则称为触发规则。当按规则的操作部分去执行时，称这条规则为启用规则。被触发的规则不一定总是启用规则，因为可能同时有几条规则的条件部分被满足，需解决冲突步骤中来解决。在复杂的情况下，在事实库和规则的条件部分之间可能要进行近似匹配2.2.冲突解决冲突解决——当有一条以上规则的条件部分和当前事实库相匹配时，就需要决定首先使用哪一条规则，这称为