人工智能chapter2Part1V7Student

1第二章知识表达技术2课程的基本内容与要求知识的概念与含义，知识类型和知识模型的变换；重点介绍几种常用的知识表达法——状态空间表示法、与/或图表示法、产生式系统、知识的逻辑表达方法、语义网络、框架表达法、特征表表达法和面向对象的表达法。掌握知识表达的基本概念，学会划分知识的类型和理解知识模型变换在解决人工智能问题的过程中的作用与意义；学会如何将一个具体的问题，用所介绍的知识表达方法来表示；初步体会在各种知识表达方法中，其知识机构是如何随知识的运用而变化的。知识的概念与含义知识表达技术概述状态空间表达与或图表达法产生式系统知识的逻辑表达方法语义网络框架表达法特征表表达法3知识的概念与含义知识表达技术概述状态空间表达与或图表达法产生式系统知识的逻辑表达方法语义网络框架表达法特征表表达法452.1知识的概念与含义智能行为——知识——对知识的获取、表达、搜索、分析、解答等智能能力人的智能的核心也在于“知识”感性知识与理性知识，经验知识与理论知识智能表现在：知识的获取能力知识的处理能力知识的运用能力知识是什么？知识：是人们对自然现象的认识和从中总结出来的规律、经验6知识模式K=F+R+CK表示知识项(Knowledgeitems)F表示事实(Facts)——人类对客观世界、客观事物的状态、属性、特征的描述，以及对事物之间关系的描述R表示规则(Rules)——能表达在前提与结论之间的因果关系的一种形式C表示概念(Concepts)——事实的含义规则语义说明等2.1知识的概念与含义知识的概念与含义知识表达技术概述状态空间表达与或图表达法产生式系统知识的逻辑表达方法语义网络框架表达法特征表表达法面向对象的表示782.2知识表达技术知识类型按知识的适用范围常识性知识：通用通识的、普遍知道的、适应所有领域的知识。领域性知识：面向某个具体专业领域的知识。如：专家经验。92.2知识表达技术知识类型按知识的确定性确定性知识：可以给出其“真”、“假”的知识。不确定性知识：具有不确定特性（不精确、模糊、不完备）的知识。102.2知识表达技术知识类型在人工智能研究中，通常把问题求解所需知识分为3类：叙述型知识——有关系统状态、环境和条件，问题的概念、定义和事实的知识。回答“是什么？”、“为什么？”过程型知识——有关系统状态变化、问题求解过程的操作、演算和行动的知识。即如何使用事实性知识的知识。回答“怎么做？”控制型知识——有关如何选择相应的操作、演算和行动的比较、判断、管理和决策的知识。是关于如何使用过程性知识的知识，如：推理策略、搜索策略、不确定性的传播策略。例：对于从北京到上海，是乘飞机还是坐火车的问题。叙述型知识：北京、上海、飞机、火车、时间、费用。过程型知识：乘飞机、坐火车。控制型知识：乘飞机较快、较贵；坐火车较慢、较便宜。11知识表示的解释知识表示是对知识的描述，即用一组符号把知识编码成计算机可以接受的某种结构。其表示方法不唯一。知识表示的要求表示能力：是指能否正确、有效地将问题求解所需要的知识表示出来。可利用性：是指表示方法应有利于进行有效的知识推理。包括：对推理的适应性，对高效算法的支持程度可组织性与可维护性：可组织性是指可以按某种方式把知识组织成某种知识结构。可维护性是指要便于对知识的增、删、改等操作可理解性与可实现性：可理解性是指知识应易读、易懂、易获取等可实现性是指知识的表示要便于计算机上实现2.2知识表达技术12知识表示的基本方法状态空间表达与或图表达法产生式系统知识的逻辑表达方法语义网络框架表达法特征表表达法面向对象的表示2.2知识表达技术13对于不同的知识表达方法，有不同的形式化知识模型。知识模型变换同构：问题的解答等价于原始问题的解答同态：可使问题更加简化，易于求解同构/同态变换同构变换(明确)同态变换(简化)难求解便于求解等价易求解蕴含原始问题同构问题同态问题原始解答同构解答同态解答2.2知识表达技术14【例2．1】方格棋盘分割问题原始问题:2n×2n方格盘，去掉对顶角上两方格，问能否将它分割为若干1×2长方块？直接求解:考察(2^(2n)^2)种可能分割方案，且随着n增大，会“组合爆炸”2.2知识表达技术15【例2．1】方格棋盘分割问题同构问题:方格相间着色,无论n为何值，对顶角上两方格同色，去掉后白格与黑格的数目间差值为2——最后剩的必是同色两方格——因同构问题无解，等价的原始问题无解。2.2知识表达技术16【例2．1】方格棋盘分割问题同态问题：同态变换——序对小黑格数，小白格数。初始状态：2n2,2n2-2，目标状态：0,0。分割操作：每操作，分割出一长方块，割去一白格和一黑格，使状态变量都减去1。经过2n2-2次操作后，状态变为2,0，不可能达到0,0——因同态问题无解，蕴含着其原始问题也无解2.2知识表达技术知识的概念与含义知识表达技术概述状态空间表达与或图表达法产生式系统知识的逻辑表达方法语义网络框架表达法特征表表达法面向对象的表示17182.3状态空间表达2.3.1状态空间表达法的概念状态用来表示系统状态,事实等叙述型知识的一组变量或数组Q=[q1,q2,…,qn]t操作是用来表示引起状态变化的过程型知识的一组关系或函数F:{f1,f2,…,fm}状态空间(StateSpace)是利用状态变量和操作符号，表示系统或问题的有关知识的符号体系，状态空间是一个四元组（S，O，S0，G）：S—状态集合;O—操作算子集合;S0—初始状态,S0S;G—目的状态,GS,(G可以是若干具体状态，也可以是满足某些性质的路径信息描述)从S0结点到G结点的路径被称为求解路径。状态空间的一个解是一有限操作算子序列，它使初始状态转换为目标状态：O1O2O3OkS0S1S2……G其中O1，…，Ok即为状态空间的一个解(解往往不是唯一的)192.3.2状态空间表达法的例子【例2．2】八数码问题的状态空间在一3×3方格盘，放1到8八个数码，另一格为空。空格四周上下左右数码可移到空格。一布局：23158467八数码任何一种摆法就是一个状态，所有的摆法为状态集S，构成了一个状态空间，其大小为9！相应操作算子是数码移动，其操作算子共有4（方向）×8（数码）=32个。可简化为4个：Up，Left，Down，Right2.3状态空间表达202.3.2与/或表达法的例子【例2．3】猴子和香蕉问题设机器人“猴子”位于a处，目的物“香蕉”挂在c处上方，猴子想吃香蕉，但高度不够，拿不着。在b处有可移动的台子，若猴子站在台子上，就可以拿到香蕉。问题是制定机器人的行动计划，使猴子能拿到香蕉。2.3状态空间表达21【例2．3】猴子和香蕉问题状态空间法:四元数组描述：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为目标状态2.3状态空间表达22【例2．3】猴子和香蕉问题允许的操作集为：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)2．4与/或图表达法•已知3个柱子l、2、3和两个盘子A、B(A比B小)。•初始状态下，A、B依次放在柱子1上；目标状态是A、B依次放在柱子3上。•条件是每次可移动一个盘子，盘子上方是空顶方可移动，而且任何时候都不允许大盘在小盘之上。课堂练习：二阶Hanoi塔问题用状态空间法表示该问题23①定义问题状态的描述形式设用Sk=(SkA，SkB)表示问题的状态，SkA表示盘子A所在的柱号，SkB表示盘子B所在的柱号。②用状态描述形式把问题的所有可能的状态都表示出来。S0=(1，1)，S1=(1，2)，S2=(1，3)，S3=(2，1)，S4=(2，2)，S5=(2，3)S6=(3，1)，S7=(3，2)，S8=(3，3)；问题的初始状态集合为{S0}，目标状态集合为{S8}。24③定义一组算符F1233:,,),:,,:()(()(),()()(,,,:,),(),FxxyxxyFxyyyxyFxyyxyzFxyzxyzzxSk=(SkA，SkB)25知识的概念与含义知识表达技术概述状态空间表达与或图表达法产生式系统知识的逻辑表达方法语义网络框架表达法特征表表达法面向对象的表示262.3.2与/或表达法的概念1.与树：当把一个复杂问题分解为若干个子问题时，可用一个“与树”来表示这种分解。2.或树：当把一个复杂问题变换为若干个与之等价的新问题时，可用一个“或树”来表示这种变换。2．4与/或图表达法273.与／或树：如果一个问题既需要通过分解，又需要通过变换才能得到其本原问题，则其求解过程可用一个“与／或树”来表示。2．4与/或图表达法28知识的概念与含义知识表达技术概述状态空间表达与或图表达法产生式系统知识的逻辑表达方法语义网络框架表达法特征表表达法面向对象的表示29302.5产生式系统产生式系统(productionsystem)描述若干不同的以一个基本概念为基础的系统。这个基本概念就是产生式规则或产生式条件和操作对的概念论域知识分为两部分：1.事实表示静态知识，如事物、事件和它们之间的关系2.产生式规则表示推理过程和行为，如动作，算子，变换等这类系统的知识库主要用于存储规则，因此又把此类系统称为基于规则的系统(rule-basedsystem)31产生式系统的基本结构一个产生式系统包含事实库、规则集和规则解释（控制器）三部分控制器匹配排序冲突裁决规则集激发树元规则事实库知识匹配相关检索匹配检索2.5产生式系统32事实库——当前已知的知识信息数据，包括推理过程中形成的中间结论知识，换句话说，它用于存储有关问题的状态、性质等事实的叙述型知识，也称为综合数据库或工作存储器。数据是广义的例如：“雪是白的”2.5产生式系统控制器匹配排序冲突裁决规则集激发树元规则事实库知识匹配相关检索匹配检索33规则集——存储有关问题的状态转移、性质变化等规则的过程型知识，或称“规则库”规则的作用•描述事物之间的因果关系。•规则的产生式表示形式常称为产生式规则，简称为产生式或规则。2.5产生式系统控制器匹配排序冲突裁决规则集激发树元规则事实库知识匹配相关检索匹配检索34产生式的基本形式P→Q或者IFPTHENQP是产生式的前提，也称为前件，它给出了该产生式可否使用的先决条件，由事实的逻辑组合来构成；Q是一组结论或操作，也称为产生式的后件，它指出当前题P满足时，应该推出的结论或应该执行的动作。产生式的含义如果前提P满足，则可推出结论Q或执行Q所规定的操作2.5产生式系统35产生式规则的例子r6:IF动物有犬齿AND有爪AND眼盯前方THEN该动物是食肉动物其中，r6是该产生式的编号；“动物有犬齿AND有爪AND眼盯前方”是产生式的前提P；“该动物是食肉动物”是产生式的结论Q。2.5产生式系统36产生式规则的形式与传统程序设计语言中条件语句非常相似，但实际上两者之间存在根本的区别：产生式规则左部表达的是一组复杂模式，而不仅仅是一个布尔表达式规则之间控制流不象传统语言中从一条语句向其下一条语句传递，而且满足条件的规则被激活但不一定立即执行，这将取决于产生式系统的冲突消解策略，这也是区分传统程序与产生式系统行为特征的关键逻辑程序中的语句可以视作产生式规则的一种特殊形式在产生式系统中，一条规则仅描述前提条件与行为之间的静态关系，因此，规则的正确性应当独立地得到保证。这就是规则的自含性，正是由于产生式规则的自含性特点，才使得知识的表示与控