人工智能202知识表达(胡静演讲稿)

2019/8/301第二章知识表达技术课程的基本内容知识的概念与含义，知识类型和知识模型的变换；重点介绍几种常用的知识表达法——状态空间表示法、与/或图表示法、产生式系统、知识的逻辑表达方法、语义网络、框架表达法、特征表表达法和面向对象的表达法。课程的基本要求掌握知识表达的基本概念，学会划分知识的类型和理解知识模型变换在解决人工智能问题的过程中的作用与意义；学会如何将一个具体的问题，用所介绍的知识表达方法来表示；初步体会在各种知识表达方法中，其知识机构是如何随知识的运用而变化的。2019/8/302第二章知识表达技术2．1知识的概念与含义智能行为——即拥有知识——即对知识的获取、表达、搜索、分析、解答等智能能力人的智能的核心也在于“知识”感性知识与理性知识，经验知识与理论知识智能表现在：•知识的获取能力—通过感知器官获取感性知识•知识的处理能力—将感性知识上升为理性知识•知识的运用能力—采取行动，发挥知识的效用知识：是人们对自然现象的认识和从中总结出来的规律、经验2019/8/303第二章知识表达技术2．1知识的概念与含义知识模式K=F+R+CK表示知识项(Knowledgeitems)F表示事实(Facts)——人类对客观世界、客观事物的状态、属性、特征的描述，以及对事物之间关系的描述R表示规则(Rules)——能表达在前提与结论之间的因果关系的一种形式C表示概念(Concepts)——事实的含义规则语义说明等2019/8/304第二章知识表达技术2．2知识表达技术知识类型叙述型知识——有关系统状态、环境和条件，问题的概念、定义和事实的知识。过程型知识——有关系统状态变化、问题求解过程的操作、演算和行动的知识。控制型知识——有关如何选择相应的操作、演算和行动的比较、判断、管理和决策的知识。例：对于从北京到上海，是乘飞机还是坐火车的问题。•叙述型知识：北京、上海、飞机、火车、时间、费用。•过程型知识：乘飞机、坐火车。•控制型知识：乘飞机较快、较贵；坐火车较慢、较便宜。2019/8/305知识的表达技术2019/8/306第二章知识表达技术(一)状态空间表达状态用来表示系统状态,事实等叙述型知识的一组变量或数组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即为状态空间的一个解(解往往不是唯一的)2019/8/307第二章知识表达技术2．3状态空间表达【例2．2】八数码问题的状态空间在一3×3方格盘，放1到8八个数码，另一格为空。空格四周上下左右数码可移到空格。一布局：23158467八数码任何一种摆法就是一个状态，所有的摆法为状态集S，构成了一个状态空间，其大小为9！相应操作算子是数码移动，其操作算子共有4（方向）×8（数码）=32个。可简化为4个：Up，Left，Down，Right2019/8/308状态图这种描述问题的有向图被称为状态空间图，简称状态图；许多智力问题都可以归结为在某一状态中寻找目标或路径的问题。2019/8/309X1X2X3X８X0X4X7X6X5例3.8八数码难题的状态图表示。我们将棋局用向量A＝(X0,X1,X2,X3,X4,X5,X6,X7,X8)表示,Xi为变量,Xi的值就是方格Xi内的数字。于是,向量A就是该问题的状态空间表达式。2019/8/3010So＝(0,2,8,3,4,5,6,7,1)Sg＝(0,1,2,3,4,5,6,7,8)易见,数码的移动规则就是该问题的状态变换规则,即操作。经分析,该问题共有24条移码规则,可分为9组。2019/8/30110组规则:;0)()0(;0)()0(;0)()0(;0)()0(80804606034040220201XnXnXXrXnXnXXrXnXnXXrXnXnXXr1组规则:;0)()0(;0)()0(3232622225XnXnXXrXnXnXXr2019/8/30122组规则:;0)()0(;0)()0(;0)()0(020293232812127XnXnXXrXnXnXXrXnXnXXr8组规则:;0)()0(;0)()0(;0)()0(787824080823181822XnXnXXrXnXnXXrXnXnXXr于是,八数码问题的状态空间（状态图）可表示为({So},{r1,r2,…,r24},{Sg})2019/8/3013当然,上述24条规则也可以简化为4条:即空格上移（UP）、下移（DOWN）、左移（LEFT）、右移（RIGHT）。不过,这时状态(即棋局)就需要用矩阵来表示。可以看出,这个状态图中仅给出了初始节点和目标节点,并未给出其余节点。而其余节点需用状态转换规则来产生。类似于这样表示的状态图称为隐式状态图,或者说状态图的隐式表示。2019/8/3014状态空间表示例2走迷宫是人们熟悉的一种游戏,如图3－1就是一个迷宫。如果我们把该迷宫的每一个格子以及入口和出口都作为节点,把通道作为边,则该迷宫可以由一个有向图表示(如图3-2所示)。那么,走迷宫其实就是从该有向图的初始节点(入口)出发,寻找目标节点(出口)的问题,或者是寻找通向目标节点(出口)的路径的问题。2019/8/3015图3-1迷宫图2019/8/3016图3-2迷宫的有向图表示2019/8/3017第二章知识表达技术（二）与/或图表达法超图树图与/或树基于人们在求解问题时的两种思维方法：分解：将复杂大问题分解为一组简单小问题若所有子问题都解决了，则总问题也解决了，这是“与”的逻辑关系——“与”树变换：将较难问题变换为较易等价/等效问题若一难问题可以等价变换为几个容易问题，则任何一个容易问题解决了，也就解决了原有难问题，这是“或”的逻辑关系——“或”树兼用“分解”和“变换”方法——“与/或”树2019/8/3018与或图搜索与或图我们仍用例子引入与或图的概念。例如图所示,设有四边形ABCD和A′B′C′D′,要求证明它们全等。分析：分别连接B、D和B′、D′,则原问题可分解为两个子问题：Q1：证明△ABD≌△A′B′D′Q2：证明△BCD≌△B′C′D′2019/8/3019图3-12四边形ABCD和A’B’C’D’2019/8/3020于是,原问题的解决可归结为这两个子问题的解决。换句话说,原问题被解决当且仅当这两个子问题都被解决。进一步,问题Q1Q11：证明AB＝A′B′Q12：证明AD＝A′D′Q13：证明∠A＝∠A′Q11′：证明AB＝A′B′Q12′：证明AD＝A′D′Q13′：证明BD＝B′D′2019/8/3021问题Q2Q21：证明BC＝B′C′Q22：证明CD＝C′D′Q23：证明∠C＝∠C′Q21′：证明BC＝B′C′Q22′：证明CD＝C′D′Q23′：证明BD＝B′D′2019/8/3022现在考虑原问题与这两组子问题的关系,我们便得到图3-13。图中的弧线表示所连边为“与”关系,不带弧线的边为或关系。这个图中既有与关系又有或关系,因此被称为与或图。但这个与或图是一种特殊的与或图,称为与或树。2019/8/3023图3-13问题的分解与变换2019/8/3024第二章知识表达技术2．4状态图、与/或图表达法【例2．3】猴子和香蕉问题（两种方法都试试）设机器人“猴子”位于a处，目的物“香蕉”挂在c处上方，猴子想吃香蕉，但高度不够，拿不着。在b处有可移动的台子，若猴子站在台子上，就可以拿到香蕉。问题是制定机器人的行动计划，使猴子能拿到香蕉。香蕉a猴子cb台子2019/8/3025第二章知识表达技术1.状态空间法【例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为目标状态2019/8/3026第二章知识表达技术2．4与/或图表达法【例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)2019/8/3027第二章知识表达技术2．4与/或图表达法【例2．3】猴子和香蕉问题允许的操作集为：F={f1,f2,f3,f4}比较目标状态（S4）与初始状态（S0）的差异，来选择主操作。由于S0与S4中的四个状态量都有差异，相应的操作为f1,f2,f3和f4，都可选为主操作。因此，可将原问题变换为四个新问题，而新问题又可分为几个子问题及子子问题。这一过程——与/或树图2019/8/3028第二章知识表达技术2．4与/或图表达法【例2．3】猴子和香蕉问题与/或树图P31(f1,f2)P32(f3)P33(f4)P311(f1)P312(f2)S0-S4P1:主操作f1P2:主操作f2P3:主操作f3P4:主操作f4S2-S3S0-S2S3-S4S0-S1S1-S22019/8/3029第二章知识表达技术习题练习（一）例2.1梵塔问题（状态空间法）。设有三根宝石杆,在1号杆上穿有A、B两个金盘,A小于B，并且A位于B的上面。要求：把这两个金盘全部移到另一根杆上,而且规定每次只能移动一个盘子,任何时刻都不能使B位于A的上面（小盘永远在大盘上面）。2019/8/3030图2.1二阶梵塔的全部状态2019/8/3031第二章知识表达技术习题练习（一）例2.1梵塔问题（状态空间法）。设用二元组(SA,SB)表示问题的状态,SA表示小盘A所在的杆号,SB表示大盘B所在的杆号,这样,全部可能的状态有9种,可表示如下：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)2019/8/3032这里的操作算子就是盘子的搬动规则，分别用A(i,j)及B(i,j)表示：A(i,j)表示把A盘（小盘）从第i号杆移到第j号杆上;B(i,j)表示把B盘（大盘）从第i号杆移到第j号杆上。经分析，共有12个操作，它们分别是：A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2)B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2)2019/8/3033这样由题意,问题的初始状态为(1,1),目标状态为(3,3),则二阶梵塔问题可用状态图表示为({(1,1)},{A(1,2),…,B(3,2)},{(3,3)})从初始节点到目标节点的任何一跳通路都是一个解，其中的最短路径长度是3，它有三个算子组成：A（1，3）、B（1，2）、A（3，2）。2019/8/3034由本题可以得出结论（1）首先必须定义状态的描述形式，通过使用这种描述形式可把问题的全部状态都表示出来。（2）其次还要有一组算子，通过使用算子可把问题的一种状态转换为另一种状态。（3）状态图就是通过一组算子将问题的初始