人工智能第二章

《人工智能第二章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

知识表示知识是一切智能行为的基础，也是软件智能化的重要研究对象。要使软件具有智能，就必须使它具有知识，而要使软件具有知识，首先必须解决知识的表示问题。所谓知识表示实际上就是对知识的一种描述，即用一些约定的符号把知识编码成一组计算机可以接受的数据结构。所谓知识表示过程就是把知识编码成某种数据结构的过程。一般来说，同一知识可以有多种不同的表示形式，而不同表示形式所产生的效果又可能不一样。4/16/20231 常用的知识表示方法非结构化方法逻辑表示法QA3,STRIPS,DART,MOMO产生式系统DENDRAL，MYCIN结构化方法框架语义网络过程式知识表示法4/16/20232 第二章产生式系统2.1产生式系统概述一、产生式系统的定义产生式系统是人工智能系统中常用的一种程序结构，是一种知识表示系统。通常由以下三部分组成：综合数据库产生式规则集控制系统4/16/20233 综合数据库：存放问题的状态描述的数据结构。Note:综合数据库不是常规意义的数据库，是一种数据结构。一般数据库所存数据的结构很简单，通常只有数值与字符串；综合数据库的数据可以很复杂，其中状态描述可以为常规的各种数据结构，如表、数组、字符串、集合、矩阵、树、图等等。综合数据库是动态变化的。一、产生式系统的定义4/16/20234 产生式规则形式：IF前提条件THEN操作当规则的前提条件被某一状态描述满足时，就对该状态施行规则所指出的操作。一、产生式系统的定义4/16/20235 控制系统：（1）选择规则：对同一个状态的多个可用规则排序。（2）检验状态描述是否满足终止条件。如果满足终止条件，则终止产生式系统的运行，并用使用过的规则序列构造出问题的解。一、产生式系统的定义4/16/20236 二、产生式系统的例八数码难题由8个标有1－8的棋子和一个3×3的棋盘组成。把8个棋子放在棋盘里，形成一个初始状态，然后移动棋子，想办法达到规定的目标状态。在移动棋子时，只能把棋子移进相邻的空格中。图2.1八数码难题的初始状态与目标状态28316475123847654/16/20237 八数码难题的产生式系统表示综合数据库：以状态为节点的有向图。状态描述：3×3矩阵产生式规则：IF<空格不在最左边>Then<左移空格>；IF<空格不在最上边>Then<上移空格>；IF<空格不在最右边>Then<右移空格>；IF<空格不在最下边>Then<下移空格>。控制系统：选择规则:按左、上、右、下的顺序移动空格。终止条件：匹配成功。4/16/20238 三、产生式系统的基本过程ProcedurePRODUCTIONDATA←初始状态描述untilDATA满足终止条件，do：begin在规则集合中，选出一条可用于DATA的规则RDATA←把R应用于DATA所得的结果End4/16/20239 步骤4是不确定的，只要求选出一条可用的规则R，至于这条规则如何选取，却没有具体说明。选取规则所依据的原则称为控制策略。多数人工智能系统控制策略的信息并不足以在第4步选出最合用的规则，因此，控制策略便成了一个搜索过程。高效的系统需要被求解问题足够的知识，以便在步骤4选出一条最合用的规则。第三章，第四章三、产生式系统的基本过程4/16/202310 产生式系统的特点一、模块性强。综合数据库、规则集和控制系统相对独立，程序的修改更加容易。二、各产生式规则相互独立，不能互相调用，增加一些或删去一些产生式规则都十分方便。三、产生式规则的形式与人们推理所用的逻辑形式十分接近，人们具有的知识转换成产生式规则很容易，产生式规则也容易被人们读懂。DENDRAL和MYCIN都采用了产生式系统的结构。4/16/202311 2.2控制策略产生式系统的控制策略分为两类：不可撤回的控制策略试探性控制策略：回溯方式和图搜索方式4/16/202312 一、不可撤回的控制策略（瞎子爬山法）基本思想采用不可撤回控制方式的解题过程类似于盲人爬山过程，是利用关于每一个状态的局部知识构造全局性解的过程。在盲人爬山过程中，无论爬到哪一点，他总沿着坡度最陡的方向向上爬，这是局部性的知识，尽管他事先对爬山路线并不了解，但只要按照这个原则向上爬，就一定能爬到某一山顶，于是确定了一条从山脚到山顶的爬山路线，也可以说构造出一个具有某种意义下全局性的解。4/16/202313 一、不可撤回的控制策略爬山函数：定义在整个综合数据库上的实数值函数，目标状态有最大的函数值。目标：爬到山顶。控制策略：应用爬山函数选一规则，使得所选下一状态的爬山函数值不减少且最大（有两个相同的最大值时任选一个；若无这样的规则，则终止爬山过程）。4/16/202314 设爬山函数CF(S)：不在目标位的数码个数的负值。初始状态S0目标状态SgCF(S0)＝-4CF(Sg)＝0状态描述S：3阶方阵4条产生式规则使用顺序：空格左、上、右、下移。2831647512384765例：八数码难题，不可撤回式控制4/16/202315 控制策略：处于任一状态S，系统根据爬山函数选择一条规则使得这条规则作用于S时，获得的下一状态爬山函数不减少且最大（亦即距离目标状态最少）。例：八数码难题，不可撤回式控制4/16/202316 283164752831476523184765231847651238476512384765例：八数码难题不可撤回式控制-4-3-3-1-204/16/202317 不可撤回控制策略的优点1.只记录当前一个节点，空间复杂性很低。2.若能找到解，则速度很快。4/16/202318 不可撤回控制策略的局限性多数情况下找不到解。原因：(a)爬山函数有多个局部极大值例如：目标0初始-2(b)爬山函数具有“平顶值”解决方法：设计更好的爬山函数；选多余规则12374865125748634/16/202319 二、回溯控制策略回溯方式是一种试探性的控制策略。（类似深度优先）基本思想控制系统先选用一条规则，如果发现这条规则的选用不能导致产生解，则系统“忘掉”选用规则所涉及的步骤和产生的状态，然后选用另外一条规则，重新进行试探。4/16/202320 回溯方法特点1.只存储初始节点到当前节点的路径，占用空间较小。2.总的时间复杂性无法定论:最好情况复杂性很低：当控制系统掌握较多的有关解的知识时，则回溯次数大为减少，效率高。最坏情况复杂性很高：当控制系统一点也没掌握有关解的知识时，则规则选取是任意的，回溯次数高，效率低。为了避免进入无限的境地，设置回溯深度限制强行回溯，问题：太深：效率低；太浅：可能找不到解。3.当深度限制可变时，通常能找到解，是实际用得多、应用最广的一种搜索策略。4/16/202321 四条规则使用顺序：左、上、右、下（可加入启发式信息，如使用爬山函数安排规则的顺序）深度：6控制策略：回溯式回溯条件：⑴产生了一个上溯到初始状态的路径上出现过的状态时（产生了祖先节点）。⑵无可用的规则。⑶达深度未得解。2831647512384765八数码难题的初始状态与目标状态例：八数码难题回溯式4/16/202322 28316475832641758326417528316475832641758342617583264175863241752836417583264175863241758326417583264175八数码问题回溯控制83264175（1）（5）（6）（5）（2）（6）（7）（6）（3）（7）（7）（4）（5）（6）4/16/202323 三、图搜索控制策略基本思想：从初始状态开始，使用全部可用规则序列。对所有的下一步状态每一个再用全部可用的规则，直到目标状态为止。（类似广度优先搜索策略）搜索树：记录规则的应用和所产生的状态的树结构。树根：初始状态有向弧：规则的使用除根以外的其它各节点：规则应用的结果图搜索控制方式不断地扩展搜索树，直到它包括了满足终止条件的节点为止。4/16/202324 图搜索控制策略的特点1.不再选择规则，而是使用所有可用的规则，下一步选择节点来扩展。2.存储所有产生的节点，占用空间大。3.有解一定能找到（相当于穷举）。4.平均时间复杂性高，系统效率低。4/16/202325 例：八数码难题图搜索式2831647512384765八数码难题的初始状态与目标状态书中图：按照深度小的排在前面、优先选择左节点。4/16/202326 四、产生式系统的工作方式1.正向产生式系统（数据驱动控制）：综合数据库：用状态描述产生式规则：F规则--状态产生新状态从初始状态出发，不断地应用F规则，直到产生目标状态为止。适用条件：初始节点数≤目标节点数4/16/202327 2.反（逆）向产生式系统（目标驱动控制）：综合数据库：用目标描述产生式规则：B规则目标产生子目标从目标状态出发，利用反向的产生式规则（B规则）不断地产生子目标，直到产生出与初始状态相同的子目标为止。适用条件：初始节点数≥目标节点数4/16/202328 3.双向产生式系统：正向产生式系统和反向产生式系统结合.综合数据库：既有初始状态描述，又有目标状态描述。产生式规则集：既有F规则，又有B规则。正向产生式规则用在初始方向的状态描述上，反向产生式规则用在目标描述上。控制系统:判断选F规则还是B规则；判断已经产生的状态和目标是否能以某种方式匹配，从而满足结束条件。结束条件：中间汇合时的状态。适用条件：初始节点数与目标节点数都很多。特点：效率高；复杂。4/16/202329 2.3特殊的产生式系统一、可交换产生式系统在某些产生式系统中。规则应用的次序对产生的状态无影响，即从初始状态到目标状态不依赖规则次序，因此可应用不可撤回式控制策略，从而提高了产生式系统的效率，这类产生式系统就是可交换的产生式系统。例：基于归结方法的产生式系统4/16/202330 一个产生式系统称为可交换的，如果对任意状态描述D具有如下性质：(a)设RD是可应用于D的规则集，任取r∈RD，r作用于D得D’，设为D’=r(D)，则r对D’可用(即：设D’的可用规则集为RD’，则r∈RD’，即RDRD’)；（每一条对D可应用的规则，对于对D应用一条可应用的规则后所产生的状态描述仍是可应用的）（可应用性）可交换产生式系统定义4/16/202331 (b)设D满足目标条件，D的可用规则集为RD，任取r∈RD，用r作用到D产生状态D’，D’满足目标条件。（如果D满足目标条件，则对D应用任何一条可应用的规则所产生的状态描述也满足目标条件）（可满足性）。4/16/202332 （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的规则所构成的规则序列所产生的状态描述不因序列的次序不同而改变）(无次序性）。4/16/202333 R1R3R1S12S11S0S13S3S2SGS1R3R2R1R2R3R1R2R3R2R1R3R3R2R1R2R3R1可交换的产生式系统例R2R3R2R14/16/202334 可交换产生式系统优点：从初始状态到目标状态不依赖规则次序，不必探查等价路径，可以使用不可撤回策略。Note：产生式系统的可交换性并不意味着整个规则序列的次序可以改变。只是最初作用于给定状态的那些规则使用起来与次序无关。4/16/202335 设产生式系统P：综合数据库，一组规则，图搜索策略造另一可交换的产生式系转换P’如下：综合数据库：初始状态：P的整个搜索树目标状态：只剩解路转换可用如下方法将一产生式系转换为可交换的：4/16/202336 转换可用如下方法将一产生式系转换为可交换的：规则Ri：若综合数据库中第i层节点n不是解路P上的点，则从综合数据库中删除节点n。控制策略：不可撤回式将P转换为P’，P’是可交换的产生式系统综合数据库变复杂；规则数目少，但操作复杂（如何判断n不是解路P上的点）；控制策略简单。4/16/202337 二、可分解的产生式系统可交换产生式系统可以避免搜索多余路径，可以使用不可撤回策略。避免搜索多余路径的另一种方法是可分解的产生式系统。4/16/202338 可分解的产生式系统例:字符串重写综合数据库：串节点的有向图状态：字符串（或用表）初始状态：(C,B,Z)产生式规则：R1:IF<(*1,C,*2)>THEN<(*1,D,L,*2)>（重写规则）R2:IF<(*1,C,*2)>THEN<(*1,B,M,*2)>R3:IF<(*1,B,*2)>THEN<(*1,M,M,*2)>R4:IF<(*1,Z,*2)>THEN<(*1,B,B,M,*2)>控制系统：选择规则：用图搜索控制策略终止条件：状态描述仅有M组成的符号串。4/16/202339 重写问题的解序列（不完整）R3R3R3R3R3R4R4R3R3R3R2R1R4（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,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)R2R3(B,M,B,Z)4/16/202340 Note:按照图搜索控制方式在产生终止状态时可能会探索许多完全等价的路径,导致系统的低效。从失败路径上浪费很多工作。节点的内容之间存在着大量的符号冗余。4/16/202341 观察：该产生式系统的初始状态可以分解成C,B和Z，然后把产生式规则分解使得可应用于这些组成部分：R1:(C)→(D,L)R2:(C)→(B,M)R3:(B)→(M,M)R4:(Z)→(B,B,M)应用规则后所得的结果状态又可以进一步分裂，这样不断地分解，不断地应用规则，直到所产生的状态是M字符为止，即终止条件分解为一个M字符作成的状态。4/16/202342 重写问题的与/或树(C,B,Z)CBZ(D,L)(B,M)(M,M)(B,B,M)DLBM(M,M)MMMMBMB(M,M)(M,M)MMMMR1R2R3R4R3R3R34/16/202343 定义能够把产生式系统综合数据库的状态描述分解为若干组成部分，产生式规则可以分别用在各组成部分上，并且整个系统的终止条件可以用在各组成部分的终止条件表示出来的产生式系统，称为可分解的产生式系统。可分解的产生式系统4/16/202344 Note:对分解出的独立分量的处理方式：可并行处理也可串行处理（一般情况下）：（1）按产生的时间排序；（2）在处理过程中动态排序。4/16/202345 可分解的产生式系统的基本过程ProcedureSPLITDATA←初始状态描述{Di}←DATA的分解结果；每个Di看成是独立的状态描述until对所有的Di{Di}，Di都满足终止条件，do:begin在{Di}中选择一个不满足终止条件的D*从{Di}中删除D*从规则集合中选出一个可应用于D*的规则RD←把R应用于D*的结果{di}←D的分解结果把{di}加入{Di}中end4/16/202346 SPLIT的控制策略：在步骤5中如何选取D*，在步骤7如何选取R。Note：PRODUCTION和SPLIT是两个比较重要的算法，本课的重点之一。PRODUCTION的步骤4：控制策略可分解的产生式系统的基本过程4/16/202347 可分解产生式系统的例子－－符号积分SAINT系统，1961年Slagle提出，1963年对SAINT进行改进，达到优秀大学生水平，是一个可分解产生式系统。输入：不定积分题目；输出：积分的结果函数综合数据库：以字符串为节点的与或图状态：字符串初始状态：用字符串表示的不定积分题目（被积函数）产生式规则：分步积分规则、代数替换、三角替换等等例如：IF<∫udv>THEN控制系统：选择规则：图搜索终止条件：与系统内部保存的基本积分表中的函数具有相同的形式。如：∫udu=u2/24/16/202348 三角恒等式三角恒等式z=z=z=用分母除分子-z=4/16/202349