2013第一章产生式系统.ppt

1、第2次课：2013年09月05日,上次课程回顾,人工智能？人工智能的本质？ 是一门研究如何制造出人造的智能机器或者智能系统,来模拟人类智能活动的能力,以延伸人们智能的科学 人工智能的研究目标 人工智能的发展 研究领域和方法 课程内容： 产生式系统 搜索技术（盲目搜索方法，启发式搜索方法，与或图搜索方法，博弈树搜索方法） AI中的谓词演算及应用 高级搜索,第一章 产生式系统,PRODUCTION SYSTEM,主要内容,产生式系统概述 问题的表示 控制策略 产生式系统的推理 产生式系统的特点,产生式系统是一种通用的计算模型，可以通过编程用它来完成在计算机上可以做的任何事情。然而，它的真正强大之处

2、是为基于知识的系统提供了一种重要的架构。 这种基于产生式的计算设计思想起源于Post的著作（1943）。 Post最早把产生式规则模型作为正式的计算理论提出。它的威力可以与图灵机相提并论。,产生式系统的一个有趣的应用是用它对人类认知建模，在20世纪60和70年代，Newell 和Simon进行了此项研究。 很大程度上，他们开发的程序（如通用问题求解器 GeneralProblem solver）奠定了产生系统在AI中的重要地位。 在此项研究中，他们观察并记录了人类在求解各种问题时的行为（如国际象棋这样的博弈问题）。,产生式系统所具有的对人类求解问题建模的能力，使它成为设计和建立专家系统的理想工

3、具。 60年代开始成为专家系统最基本的结构 形式简单，在一定意义上模仿人类思考过程 产生式容易描述事实，规则以及它们的不确定度量,什么是产生式？,-如果下雨，就要打伞 -天气冷，就要加衣服。 -善有善报，恶有恶报。 在自然界的各种知识单元之间存在着大量的因果关系。这是前提和结论之间的关系，可用产生式（或称规则）来表示。产生式也称作规则，或产生式规则。,产生式的一般形式,产生式（规则）：用于表示事物间的因果关系。 一般形式为： IF THEN IF THEN 或者简写为： ,前提或条件部分可以是一些事实的合取或析取，结论是某一事实。 产生式规则的含义是：如果前件满足，则可以得到后件的结论或者执行

4、后件的相应的行动，即后件由前件来触发。 一个产生式生成的结论可以作为另一个产生式的前提。 举例：1）水被电解生成氧气和氢气 2）小明很聪明小明很努力 小明学习成绩好 3）小明学习成绩好妈妈表扬小明,什么是产生式系统？,大多数专家系统都是以产生式表示知识，把一组产生式放在一起，让它们相互配合，协同的工作，一个产生式生成的结论可以供另一个产生式作为前提使用，以这种方式求得问题的解的系统叫做产生式系统。,产生式系统的结构,组成三要素： 一个综合数据库存放信息 一组产生式规则（规则库）知识 与求解有关的所有产生式规则的集合，包括了将问题从初始状态转换成目标状态所需的所有变换规则 一个控制系统（推理机）

5、规则的解释或执行程序 （控制策略） 推理机控制协同规则库与数据库，负责整个产生式系统的运行，决定问题求解过程的推理路线，实现对问题的求解。,一个简单的例子,问题：设字符转换规则 ABC ACD BCG BEF DE 已知：A，B 求：F,综合数据库,规则库,推理机：,一个简单的例子,问题：设字符转换规则 ABC ACD BCG BEF DE 已知：A，B 求：F,一、综合数据库 x，其中x为字符 二、规则集,1，IF AB THEN C 2，IF AC THEN D 3，IF BC THEN G 4，IF BE THEN F 5，IF D THEN E,三、控制策略：顺序排队,知识库,数据库,

6、规则库,推理机,存放构成产生式系统的基本元素（系统设计时输入的事实，外部数据库输入的事实以及中间结果和最后的结果）； 推理中，当规则库中某条规则的前提可以和数据库中的已知事实相匹配时，该规则被激活，由它推出的结论将作为新的事实放入数据库，成为后面推理的已知事实。,是一个解释程序，控制协同规则库与数据库，负责整个产生式系统的运行，决定问题求解的推理线路，实现对问题的求解。,存放与求解有关的所有产生式规则的集合，包括了将问题从初始状态转换成目标状态所需的所有变换规则,产生式系统的结构图,推理机,推理机包括以下工作内容 按照一定策略从规则库中选择规则与数据库的已知事实进行匹配。在匹配中，出现下面三种

7、情况 匹配成功，则此规则将列入被激活侯选集（冲突集） 匹配失败，即输入条件与已知条件矛盾，则此条规则被完全放弃，今后不予考虑。 匹配无结果，即规则前件与输入事实无关，该规则被放入待测试规则集。,2 当匹配成功的规则多于一条时，需要从匹配成功的规则中选出一个加以执行，即根据一定的策略解消冲突（例如选择编号最小的）。 解释执行规则后件的动作。如果该规则的后件不是问题的目标，将其加入数据库中。如果这些后件是一个或者多个操作时，根据一定的策略，有选择有顺序的执行。 掌握结束产生式系统运行的时机。对要执行的规则，如果该规则的后件满足问题的结束条件，则停止推理。,产生式系统的基本过程,过程PRODUCTI

8、ON 1，DATA初始数据库 2，until DATA满足结束条件，do 3， 4，在规则集中选择一条可应用于DATA 的规则R 5，DATA R应用到DATA得到的结果 6，,一个简单的例子,问题：设字符转换规则 ABC ACD BCG BEF DE 已知：A，B 求：F,一、综合数据库 x，其中x为字符 二、规则集,1，IF AB THEN C 2，IF AC THEN D 3，IF BC THEN G 4，IF BE THEN F 5，IF D THEN E,三、控制策略 顺序排队 四、初始条件 A，B 五、结束条件 Fx,求解过程,数据库可触发规则被触发规则,A，B,（1）,（1）,A

9、，B，C,（2）（3）,（2）,A，B，C，D,（3）（5）,（3）,A，B，C，D，G,（5）,（5）,A，B，C，D，G，E,（4）,（4）,A，B，C，D，G，E，F,1，IF AB THEN C 2，IF AC THEN D 3，IF BC THEN G 4，IF BE THEN F 5，IF D THEN E,1 .3 问题表示举例,例: 传教士与野人问题（Missionaries-Cannibals问题) 问题：N个传教士和N个野人在河边准备渡河，河岸有一条船，可同时乘坐k个人，要求在任何时刻，在河的两岸以及船上，传教士人数不能少于野人的人数。 问：如何过河。 以N=3，k=2，传

10、教士和野人从左岸向右岸过河为例求解。,M-C问题（续1）,传教士人数,野人数,B=1：船在左岸 B=0：船在右岸,M-C问题（续2）,1，综合数据库 （m, c, b)， 其中：0m, c3, b 0, 1 2，初始状态 （3，3，1） 3，目标状态（结束状态） （0，0，0）,M-C问题（续3）,4，规则集 IF (m, c, 1) THEN (m-1, c, 0) IF (m, c, 1) THEN (m, c-1, 0) IF (m, c, 1) THEN (m-1, c-1, 0) IF (m, c, 1) THEN (m-2, c, 0) IF (m, c, 1) THEN (m,

11、c-2, 0),M-C问题（续4）,IF (m, c, 0) THEN (m+1, c, 1) IF (m, c, 0) THEN (m, c+1, 1) IF (m, c, 0) THEN (m+1, c+1, 1) IF (m, c, 0) THEN (m+2, c, 1) IF (m, c, 0) THEN (m, c+2, 1) 5，控制策略：（略）,M-C问题,4，规则集 IF (m, c, 1) THEN (m-1, c, 0) IF (m, c, 1) THEN (m, c-1, 0) IF (m, c, 1) THEN (m-1, c-1, 0) IF (m, c, 1) TH

12、EN (m-2, c, 0) IF (m, c, 1) THEN (m, c-2, 0),IF (m, c, 1) AND 1 i+j2 THEN (m-i, c-j, 0),M-C问题,4，规则集 IF (m, c, 0) THEN (m+1, c, 1) IF (m, c, 0) THEN (m, c+1, 1) IF (m, c, 0) THEN (m+1, c+1, 1) IF (m, c, 0) THEN (m+2, c, 1) IF (m, c, 0) THEN (m, c+2, 1),IF (m, c, 0) AND 1 i+j2 THEN (m+i, c+j, 1),M-C问题

13、（另一种表示）,4，规则集： IF (m, c, 1) AND 1 i+j2 THEN (m-i, c-j, 0) IF (m, c, 0) AND 1 i+j2 THEN (m+i, c+j, 1),产生式系统的推理方式,正向推理 从已知事实出发，通过规则库求得结论，也称为自底向上（bottom-up），或称为数据驱动方式。 已知事实A，规则库中规则A B，B C，C D，则正向推理过程表示为： A B C D 反向推理 从目标出发，反向使用规则，求得已知事实，也称为自顶向下（top-down）推理方式，或称目标驱动方式。 双向推理（正反向推理） 是既自顶向下（top-down）又自底向上（

14、bottom-up），直到达到某一个中间环节两个方向的结果相符便成功结束的推理方式。,正向推理步骤,1、正向推理步骤 读入初始数据（事实）集到工作存储器,待测试规则表清空 寻找与初始事实相匹配的规则。取出规则，将规则的全部前件与工作器中所有的事实比较。如匹配成功，将规则加入冲突集；如冲突集为空，转向（3）；否则冲突消解；将所选择的规则的结论加入工作存储器；如达到目标结点转向（3）；否则返回（2）。 结束,举例说明,以植物分类系统为例，对各种植物构造一条识别规则，规则左部为该植物的特征，右部为识别出的植物名。,R1：IF 它种子的胚有两个叶子OR 它的叶脉为网状 THEN 它为双子叶植物 R2：

15、IF 它种子的胚有一个子叶，THEN 它为单子叶植物 R3：IF 它的叶脉平行，THEN 它为单子叶植物 R4：IF它是双子叶植物AND 它的花托呈杯形OR 它是双子叶植物AND 它的花为两性AND它的花瓣有5枚 THEN它为蔷薇科植物 R5：IF 它为蔷薇科植物AND 它的果实为核果 THEN它为李亚科植物 R6：IF 它为蔷薇科植物AND 它的果实为梨果 THEN它为苹果亚科植物 R7：IF 它为李亚科植物AND它的果实上有毛 THEN他是桃 R8：IF 它为李亚科植物AND它的果皮光滑 THEN他是李 R9：IF 它的果实为扁圆形AND它的果实外有纵沟 THEN 它是桃 R10：IF它是

16、苹果亚科植物AND它的果实里无石细胞 THEN它是苹果 R11：IF它是苹果亚科植物AND它的果实里有石细胞 THEN它是梨 R12：IF它的果肉为乳黄色AND它的果肉质脆 THEN它是苹果,R1：IF 它种子的胚有两个叶子OR 它的叶脉为网状 THEN 它为双子叶植物 R2：IF 它种子的胚有一个子叶，THEN 它为单子叶植物 R3：IF 它的叶脉平行，THEN 它为单子叶植物 R4：IF它是双子叶植物AND 它的花托呈杯形OR 它是双子叶植物AND 它的花为两性AND它的花瓣有5枚 THEN它为蔷薇科植物 R5：IF 它为蔷薇科植物AND 它的果实为核果 THEN它为李亚科植物 R6：IF

17、 它为蔷薇科植物AND 它的果实为梨果 THEN它为苹果亚科植物,R7：IF 它为李亚科植物AND它的果实上有毛 THEN他是桃 R8：IF 它为李亚科植物AND它的果皮光滑 THEN他是李 R9：IF 它的果实为扁圆形AND它的果实外有纵沟 THEN 它是桃 R10：IF它是苹果亚科植物AND它的果实里无石细胞 THEN它是苹果 R11：IF它是苹果亚科植物AND它的果实里有石细胞 THEN它是梨 R12：IF它的果肉为乳黄色AND它的果肉质脆 THEN它是苹果,假设事实是： 它的果肉为乳黄色； 它的果实里无石细胞； 它的果实为梨果； 它的果实无毛 它的花托为杯形状； 它种子的胚有两个子叶,

18、R1：IF 它种子的胚有两个叶子OR 它的叶脉为网状 THEN 它为双子叶植物 R2：IF 它种子的胚有一个子叶，THEN 它为单子叶植物 R3：IF 它的叶脉平行，THEN 它为单子叶植物 R4：IF它是双子叶植物AND 它的花托呈杯形OR 它是双子叶植物AND 它的花为两性AND它的花瓣有5枚 THEN它为蔷薇科植物 R5：IF 它为蔷薇科植物AND 它的果实为核果 THEN它为李亚科植物 R6：IF 它为蔷薇科植物AND 它的果实为梨果 THEN它为苹果亚科植物 R7：IF 它为李亚科植物AND它的果实上有毛 THEN他是桃 R8：IF 它为李亚科植物AND它的果皮光滑 THEN他是李

19、R9：IF 它的果实为扁圆形AND它的果实外有纵沟 THEN 它是桃 R10：IF它是苹果亚科植物AND它的果实里无石细胞 THEN它是苹果 R11：IF它是苹果亚科植物AND它的果实里有石细胞 THEN它是梨 R12：IF它的果肉为乳黄色AND它的果肉质脆 THEN它是苹果,它的果肉为乳黄色； 它的果实里无石细胞； 它的果实为梨果； 它的果实无毛 它的花托为杯形状； 它种子的胚有两个子叶,蔷薇科植物,苹果亚科植物,苹果,双子叶植物,进入第二个工作周期,第二个工作周期,取出待测试规则表的7条规则，在第一周期结束时的存储器内容基础上，对它们进行重新匹配，同时将待测试规则表再次清空。 检查本周期中

20、存储器内容是否有变化，以及待测试规则表是否为空。如果存储器内容没有变化，或待测试规则表为空，则推理结束，否则继续下一个工作周期。,总结：推理过程为： 初始数据集存入工作存储器 果肉乳黄色，无石细胞，梨果，果实无毛，花托为杯形状，双子叶胚 寻找与初始事实匹配的规则 进入第二个工作周期，取出待测试规则表的7条规则，在第一周期结束时的存储器内容基础上，对它们进行重新匹配，同时将待测试规则表再次清空。 该工作周期结束后，检查本周期中存储器内容是否有变化，以及待测试规则表是否为空。如果存储器内容没有变化，或待测试规则表为空，则推理结束，否则继续下一个工作周期。,正向推理特点,在上面的例子中，推理机给出的

21、推理结果是“苹果” 正向推理的特点： 正向推理是数据驱动，从一组事实出发推导结论。 优点是：算法简单，容易实现，允许用户一开始就把有关的事实存入数据库 缺点是：盲目搜索，可能会求解许多与总目标无关的子目标，推理效率底。,反向推理,反向推理的具体实现策略是：先假设一个可能的目标，系统试图证明它。 看此假设是否在数据存储器中，若在，则假设成立。 否则，将查看这些假设的叶子结点，找出结论部分包括此假设的规则，把它们的前提作为新的假设，并试图证明它。 这样周而复始，直到所有目标被证明，所有路径被测试。 假设一个目标：“苹果”,R1：IF 它种子的胚有两个子叶OR 它的叶脉为网状 THEN 它为双子叶植

22、物 R2：IF 它种子的胚有一个子叶，THEN 它为单子叶植物 R3：IF 它的叶脉平行，THEN 它为单子叶植物 R4：IF它是双子叶植物AND 它的花托呈杯形OR 它是双子叶植物AND 它的花为两性AND它的花瓣有5枚 THEN它为蔷薇科植物 R5：IF 它为蔷薇科植物AND 它的果实为核果 THEN它为李亚科植物 R6：IF 它为蔷薇科植物AND 它的果实为梨果 THEN它为苹果亚科植物 R7：IF 它为李亚科植物AND它的果实上有毛 THEN他是桃 R8：IF 它为李亚科植物AND它的果皮光滑 THEN他是李 R9：IF 它的果实为扁圆形AND它的果实外有纵沟 THEN 它是桃 R10：IF它是苹果亚科植物AND它的果实里无石细胞 THEN它是苹果 R11：IF它是苹果亚科植物AND它的果实里有石细胞 THEN它是梨 R12：IF它的果肉为乳黄色AND它的果肉质脆 THEN它是苹果,它的果肉为乳黄色； 它的果实里无石细胞； 它的果实为梨果； 它的果实无毛 它的花