人工智能第二章2015

1、9/16/2020,1,知识表示,知识是一切智能行为的基础，也是软件智能化的重要研究对象。要使软件具有智能，就必须使它具有知识，而要使软件具有知识，首先必须解决知识的表示问题。 所谓知识表示实际上就是对知识的一种描述，即用一些约定的符号把知识编码成一组计算机可以接受的数据结构。所谓知识表示过程就是把知识编码成某种数据结构的过程。 一般来说，同一知识可以有多种不同的表示形式，而不同表示形式所产生的效果又可能不一样。,9/16/2020,2,常用的知识表示方法,非结构化方法 逻辑表示法 QA3,STRIPS,DART,MOMO 产生式系统 DENDRAL，MYCIN 结构化方法 框架 语义网络 过

2、程式知识表示法,9/16/2020,3,第二章 产生式系统,2.1 产生式系统概述 一、产生式系统的定义 产生式系统是人工智能系统中常用的一种程序结构，是一种知识表示系统。 通常由以下三部分组成： 综合数据库 产生式规则集 控制系统,9/16/2020,4,综合数据库：存放问题的状态描述的数据结构。 Note: 综合数据库不是常规意义的数据库，是一种数据结构。一般数据库所存数据的结构很简单，通常只有数值与字符串；综合数据库的数据可以很复杂，其中状态描述可以为常规的各种数据结构，如表、数组、字符串、集合、矩阵、 树、图等等。 综合数据库是动态变化的。,一、产生式系统的定义,9/16/2020,5

3、,产生式规则形式： IF前提条件 THEN操作 当规则的前提条件被某一状态描述满足时，就对该状态施行规则所指出的操作。,一、产生式系统的定义,9/16/2020,6,控制系统： （1）选择规则： 对同一个状态的多个可用规则排序。 （2）检验状态描述是否满足终止条件。 如果满足终止条件，则终止产生式系统的运行， 并用使用过的规则序列构造出问题的解。,一、产生式系统的定义,9/16/2020,7,二、产生式系统的例,八数码难题 由8个标有18的棋子和一个33的棋盘组成。把8个棋子放在棋盘里，形成一个初始状态，然后移动棋子，想办法达到规定的目标状态。在移动棋子时，只能把棋子移进相邻的空格中。 图2.

4、1 八数码难题的初始状态与目标状态,9/16/2020,8,八数码难题的产生式系统表示,综合数据库：以状态为节点的有向图。 状态描述： 33矩阵 产生式规则： IFThen； IFThen ； IFThen ； IFThen 。 控制系统： 选择规则:按左、上、右、下的顺序移动空格。 终止条件：匹配成功。,9/16/2020,9,三、产生式系统的基本过程,Procedure PRODUCTION DATA初始状态描述 until DATA 满足终止条件，do： begin 在规则集合中，选出一条可用于DATA的规则R DATA把R应用于DATA所得的结果 End,9/16/2020,10,步骤

5、4是不确定的，只要求选出一条可用的规则 R，至于这条规则如何选取，却没有具体说明。 选取规则所依据的原则称为控制策略。 多数人工智能系统控制策略的信息并不足以在 第4步选出最合用的规则，因此，控制策略便成了一 个搜索过程。 高效的系统需要被求解问题足够的知识，以便在 步骤4选出一条最合用的规则。第三章，第四章,三、产生式系统的基本过程,9/16/2020,11,产生式系统的特点,一、模块性强。综合数据库、规则集和控制系统相 对独立，程序的修改更加容易。 二、各产生式规则相互独立，不能互相调用，增加 一些或删去一些产生式规则都十分方便。 三、产生式规则的形式与人们推理所用的逻辑形式 十分接近，人

6、们具有的知识转换成产生式规则 很容易，产生式规则也容易被人们读懂。 DENDRAL和MYCIN都采用了产生式系统的结构。,9/16/2020,12,2.2 控制策略,产生式系统的控制策略分为两类： 不可撤回的控制策略 试探性控制策略：回溯方式和图搜索方式,9/16/2020,13,一、不可撤回的控制策略（瞎子爬山法）,基本思想 采用不可撤回控制方式的解题过程类似于盲人爬山过程，是利用关于每一个状态的局部知识构造全局性解的过程。在盲人爬山过程中，无论爬到哪一点，他总沿着坡度最陡的方向向上爬，这是局部性的知识，尽管他事先对爬山路线并不了解，但只要按照这个原则向上爬，就一定能爬到某一山顶，于是确定了

7、一条从山脚到山顶的爬山路线，也可以说构造出一个具有某种意义下全局性的解。,9/16/2020,14,一、不可撤回的控制策略,爬山函数：定义在整个综合数据库上的实数值函数， 目标状态有最大的函数值。 目 标：爬到山顶。 控制策略：应用爬山函数选一规则，使得所选下一状态的爬山函数值不减少且最大（有两个相同的最大值时任选一个；若无这样的规则，则终止爬山过程）。,9/16/2020,15,设爬山函数CF(S) ：不在目标位的数码个数的负值。 初始状态S0 目标状态Sg CF(S0) - 4 CF(Sg) 0 状态描述S：3阶方阵 4条产生式规则使用顺序：空格左、上、右、下移。,例：八数码难题，不可撤回

8、式控制,9/16/2020,16,控制策略：处于任一状态S，系统根据爬山函数选择一条规则使得这条规则作用于 S 时，获得的下一状态爬山函数不减少且最大（亦即距离目标状态最少）。,例：八数码难题，不可撤回式控制,9/16/2020,17,例：八数码难题 不可撤回式控制,-4,-3,-3,-1,-2,0,9/16/2020,18,不可撤回控制策略的优点,1. 只记录当前一个节点，空间复杂性很低。 2. 若能找到解，则速度很快。,9/16/2020,19,不可撤回控制策略的局限性,多数情况下找不到解。原因： (a) 爬山函数有多个局部极大值 例如： 目标 0 初始 -2 (b) 爬山函数具有“平顶值

9、” 解决方法：设计更好的爬山函数；选多余规则,9/16/2020,20,二、回溯控制策略,回溯方式是一种试探性的控制策略。（类似深度优先） 基本思想 控制系统先选用一条规则，如果发现这条规则的选用不能导致产生解，则系统“忘掉”选用规则所涉及的步骤和产生的状态，然后选用另外一条规则，重新进行试探。,9/16/2020,21,回溯方法特点,1.只存储初始节点到当前节点的路径，占用空间较小。 2. 总的时间复杂性无法定论: 最好情况复杂性很低：当控制系统掌握较多的有关解的知识时，则回溯次数大为减少，效率高。 最坏情况复杂性很高：当控制系统一点也没掌握有关解的知识时，则规则选取是任意的，回溯次数高，效

10、率低。 为了避免进入无限的境地，设置回溯深度限制强行回溯，问题：太深：效率低；太浅：可能找不到解。 3. 当深度限制可变时，通常能找到解，是实际用得多、应用最广的一种搜索策略。,9/16/2020,22,四条规则使用顺序：左、上、右、下（可加入启发式信息，如使用爬山函数安排规则的顺序）深度：6控制策略：回溯式回溯条件： 产生了一个上溯到初始状态的路径上出现过的状态时（产生了祖先节点）。 无可用的规则。 达深度未得解。,八数码难题的初始状态与目标状态,例：八数码难题 回溯式,9/16/2020,23,2 8 3 1 6 4 7 5,8 3 2 6 4 1 7 5,8 3 2 6 4 1 7 5,

11、2 8 3 1 6 4 7 5,8 3 2 6 4 1 7 5,8 3 4 2 6 1 7 5,8 3 2 6 4 1 7 5,8 6 3 2 4 1 7 5,2 8 3 6 4 1 7 5,8 3 2 6 4 1 7 5,8 6 3 2 4 1 7 5,8 3 2 6 4 1 7 5,8 3 2 6 4 1 7 5,八数码问题回溯控制,8 3 2 6 4 1 7 5,（1） （5） （6） （5） （2） （6） （7） （6） （3） （7） （7） （4） （5） （6）,9/16/2020,24,三、图搜索控制策略,基本思想：从初始状态开始，使用全部可用规则序列。对所有的下一步状态每一

12、个再用全部可用的规则，直到目标状态为止。（类似广度优先搜索策略） 搜索树：记录规则的应用和所产生的状态的树结构。 树根：初始状态 有向弧：规则的使用 除根以外的其它各节点：规则应用的结果 图搜索控制方式不断地扩展搜索树，直到它包括了满足终止条件的节点为止。,9/16/2020,25,图搜索控制策略的特点,1.不再选择规则，而是使用所有可用的规则，下一步选择节点来扩展。 2.存储所有产生的节点，占用空间大。 3.有解一定能找到（相当于穷举）。 4.平均时间复杂性高，系统效率低。,9/16/2020,26,例：八数码难题 图搜索式,八数码难题的初始状态与目标状态,书中图：按照深度小的排在前面、优先

13、选择左节点。,9/16/2020,27,四、产生式系统的工作方式,1.正向产生式系统（数据驱动控制） ： 综合数据库：用状态描述 产生式规则：F规则-状态产生新状态 从初始状态出发，不断地应用F规则，直到产生目标状态为止。 适用条件：初始节点数目标节点数,9/16/2020,28,2. 反（逆）向产生式系统（目标驱动控制） ： 综合数据库：用目标描述 产生式规则：B规则 目标产生子目标 从目标状态出发，利用反向的产生式规则（ B规则 ）不断地产生子目标，直到产生出与初始状态相同的子目标为止。 适用条件：初始节点数目标节点数,9/16/2020,29,3. 双向产生式系统：正向产生式系统和反向产

14、生式系统结合. 综合数据库：既有初始状态描述，又有目标状态描述。 产生式规则集：既有F规则，又有B规则。 正向产生式规则用在初始方向的状态描述上，反向产生式规则用在目标描述上。 控制系统:判断选F规则还是B规则； 判断已经产生的状态和目标是否能以某种方式匹配， 从而满足结束条件。 结束条件：中间汇合时的状态。 适用条件：初始节点数与目标节点数都很多。 特点：效率高；复杂。,9/16/2020,30,2.3 特殊的产生式系统,一、可交换产生式系统 在某些产生式系统中。规则应用的次序对产生的状态无影响，即从初始状态到目标状态不依赖规则次序，因此可应用不可撤回式控制策略，从而提高了产生式系统的效率，

15、这类产生式系统就是可交换的产生式系统。 例：基于归结方法的产生式系统,9/16/2020,31,一个产生式系统称为可交换的，如果对任意状态描述D具有如下性质： (a) 设RD是可应用于D的规则集，任取r RD， r作用于D得 D，设为D= r (D)，则r对D 可用(即：设D的可用规则集为RD，则r RD ，即RD RD )；（每一条对D可应用的规则，对于对D应用一条可应用的规则后所产生的状态描述仍是可应用的）（可应用性）,可交换产生式系统定义,9/16/2020,32,(b)设D满足目标条件，D的可用规则集为RD，任取 r RD ，用r作用到D产生状态D ，D满足目标条件。（如果D满足目标条

16、件，则对D应用任何一条可应用的规则所产生的状态描述也满足目标条件） （可满足性）。,9/16/2020,33,（c）设D的可用规则集为RD，任取 r1, r2, , rn RD，依据（a）将r1, r2, , rn依次作用到D及产生的状态上，得状态Dn；设r1, r2, , rn 是 r1, r2, , rn的任意一个排列，用r1, r2, , rn依次作用到D及产生的状态上，得状态Dn，则Dn= Dn （对D应用一个由可应用于D的规则所构成的规则序列所产生的状态描述不因序列的次序不同而改变）(无次序性）。,9/16/2020,34,R1,R3,R1,S12,S11,S0,S13,S3,S2,

17、SG,S1,R3,R2,R1,R2,R3,R1,R2,R3,R2,R1,R3,R3,R2,R1,R2,R3,R1,可交换的产生式系统例,R2,R3,R2,R1,9/16/2020,35,可交换产生式系统优点：从初始状态到目标状态不依赖规则次序，不必探查等价路径，可以使用不可撤回策略。 Note：产生式系统的可交换性并不意味着整个规则序列的次序可以改变。只是最初作用于给定状态的那些规则使用起来与次序无关。,9/16/2020,36,设产生式系统P：综合数据库，一组规则，图搜索策略 造另一可交换的产生式系转换P如下： 综合数据库： 初始状态：P的整个搜索树 目标状态：只剩解路,转换 可用如下方法将

18、一产生式系转换为可交换的：,9/16/2020,37,转换 可用如下方法将一产生式系转换为可交换的：,规则Ri：若综合数据库中第i层节点n不是解路P上的点，则从综合数据库中删除节点n。 控制策略：不可撤回式 将P转换为P， P是可交换的产生式系统 综合数据库变复杂；规则数目少，但操作复杂（如何判断n不是解路P上的点）；控制策略简单。,9/16/2020,38,二、可分解的产生式系统,可交换产生式系统可以避免搜索多余路径，可 以使用不可撤回策略。避免搜索多余路径的另一 种方法是可分解的产生式系统。,9/16/2020,39,可分解的产生式系统例:字符串重写,综合数据库：串节点的有向图 状态：字符

19、串（或用表） 初始状态： (C, B, Z) 产生式规则： R1: IFTHEN （重写规则） R2: IFTHEN R3: IFTHEN R4: IFTHEN 控制系统： 选择规则：用图搜索控制策略 终止条件：状态描述仅有M组成的符号串。,9/16/2020,40,重写问题的解序列（不完整）,R3,R3,R3,R3,R3,R4,R4,R3,R3,R3,R2,R1,R4,（C，B，Z）,(M,M,M,B,Z),(M,M,M,M,M,Z),(M,M,M,M,M,B,B,M),(M,M,M,M,M,M,M,B,M),(M,M,M,M,M,M,M,M,M,M),(C,B,B,B,M),(B,M,B,

20、B,B,M),(M,M,M,B,B,B,M),(D,L,B,Z),(D,L,M,M,Z),(D,L,M,M,B,B,M),(D,L,M,M,M,M,B,M),(D,L,M,M,M,M,M,M,M),R2,R3,(B,M,B,Z),9/16/2020,41,Note: 按照图搜索控制方式在产生终止状态时可能会探索许多完全等价的路径,导致系统的低效。 从失败路径上浪费很多工作。 节点的内容之间存在着大量的符号冗余。,9/16/2020,42,观察： 该产生式系统的初始状态可以分解成 C, B和Z， 然后把产生式规则分解使得可应用于这些组成部分： R1: (C) (D, L) R2: (C) (B, M) R3: (B) (M, M) R4: (Z) (B, B, M) 应用规则后所得的结果状态又可以进一步分裂，这样不断地分解，不断地应用规则，直到所产生的状态是M字符为止，即终止条件分解为一个M字符作成的状态。,9/16/2020,43,重写问题的与/或树,R1 R2 R3 R4 R3 R3 R3,9/16/2020,44,定义 能够把产生式系统综合数据库的状态描述分解为若干组成部分，产生式规则可以分别用在各组成部分上，并且整个系统的终止条件可以用在各组成部分的终止条件表示出来的产生式系统，称为可分解的产生式系统。