《2013第一章产生式系统》由会员分享，可在线阅读，更多相关《2013第一章产生式系统（49页珍藏版）》请在金锄头文库上搜索。
1、第2次课：2013年09月05日,上次课程回顾,人工智能？人工智能的本质？ 是一门研究如何制造出人造的智能机器或者智能系统,来模拟人类智能活动的能力,以延伸人们智能的科学人工智能的研究目标人工智能的发展研究领域和方法 课程内容： 产生式系统搜索技术（盲目搜索方法，启发式搜索方法，与或图搜索方法，博弈树搜索方法）AI中的谓词演算及应用高级搜索,第一章 产生式系统,PRODUCTION SYSTEM,主要内容,产生式系统概述 问题的表示 控制策略 产生式系统的推理 产生式系统的特点,产生式系统是一种通用的计算模型，可以通过编程用它来完成在计算机上可以做的任何事情。然而，它的真正强大之处是为基于知识
2、的系统提供了一种重要的架构。这种基于产生式的计算设计思想起源于Post的著作（1943）。Post最早把产生式规则模型作为正式的计算理论提出。它的威力可以与图灵机相提并论。,产生式系统的一个有趣的应用是用它对人类认知建模，在20世纪60和70年代，Newell 和Simon进行了此项研究。很大程度上，他们开发的程序（如通用问题求解器 GeneralProblem solver）奠定了产生系统在AI中的重要地位。在此项研究中，他们观察并记录了人类在求解各种问题时的行为（如国际象棋这样的博弈问题）。,产生式系统所具有的对人类求解问题建模的能力，使它成为设计和建立专家系统的理想工具。60年代开始成为
3、专家系统最基本的结构形式简单，在一定意义上模仿人类思考过程产生式容易描述事实，规则以及它们的不确定度量,什么是产生式？,-如果下雨，就要打伞 -天气冷，就要加衣服。 -善有善报，恶有恶报。在自然界的各种知识单元之间存在着大量的因果关系。这是前提和结论之间的关系，可用产生式（或称规则）来表示。产生式也称作规则，或产生式规则。,产生式的一般形式,产生式（规则）：用于表示事物间的因果关系。一般形式为： IF THEN IF THEN 或者简写为： ,前提或条件部分可以是一些事实的合取或析取，结论是某一事实。 产生式规则的含义是：如果前件满足，则可以得到后件的结论或者执行后件的相应的行动，即后件由前件
4、来触发。一个产生式生成的结论可以作为另一个产生式的前提。举例：1）水被电解生成氧气和氢气 2）小明很聪明小明很努力 小明学习成绩好 3）小明学习成绩好妈妈表扬小明,什么是产生式系统？,大多数专家系统都是以产生式表示知识，把一组产生式放在一起，让它们相互配合，协同的工作，一个产生式生成的结论可以供另一个产生式作为前提使用，以这种方式求得问题的解的系统叫做产生式系统。,产生式系统的结构,组成三要素：一个综合数据库存放信息 一组产生式规则（规则库）知识 与求解有关的所有产生式规则的集合，包括了将问题从初始状态转换成目标状态所需的所有变换规则一个控制系统（推理机）规则的解释或执行程序 （控制策略） 推
5、理机控制协同规则库与数据库，负责整个产生式系统的运行，决定问题求解过程的推理路线，实现对问题的求解。,一个简单的例子,问题：设字符转换规则ABCACDBCGBEFDE已知：A，B求：F,综合数据库,规则库,推理机：,一个简单的例子,问题：设字符转换规则ABCACDBCGBEFDE已知：A，B求：F,一、综合数据库x，其中x为字符二、规则集,1，IF AB THEN C2，IF AC THEN D3，IF BC THEN G4，IF BE THEN F5，IF D THEN E,三、控制策略：顺序排队,知识库,数据库,规则库,推理机,存放构成产生式系统的基本元素（系统设计时输入的事实，外部数据库
6、输入的事实以及中间结果和最后的结果）；推理中，当规则库中某条规则的前提可以和数据库中的已知事实相匹配时，该规则被激活，由它推出的结论将作为新的事实放入数据库，成为后面推理的已知事实。,是一个解释程序，控制协同规则库与数据库，负责整个产生式系统的运行，决定问题求解的推理线路，实现对问题的求解。,存放与求解有关的所有产生式规则的集合，包括了将问题从初始状态转换成目标状态所需的所有变换规则,产生式系统的结构图,推理机,推理机包括以下工作内容按照一定策略从规则库中选择规则与数据库的已知事实进行匹配。在匹配中，出现下面三种情况匹配成功，则此规则将列入被激活侯选集（冲突集）匹配失败，即输入条件与已知条件矛
7、盾，则此条规则被完全放弃，今后不予考虑。匹配无结果，即规则前件与输入事实无关，该规则被放入待测试规则集。,2 当匹配成功的规则多于一条时，需要从匹配成功的规则中选出一个加以执行，即根据一定的策略解消冲突（例如选择编号最小的）。解释执行规则后件的动作。如果该规则的后件不是问题的目标，将其加入数据库中。如果这些后件是一个或者多个操作时，根据一定的策略，有选择有顺序的执行。掌握结束产生式系统运行的时机。对要执行的规则，如果该规则的后件满足问题的结束条件，则停止推理。,产生式系统的基本过程,过程PRODUCTION1，DATA初始数据库2，until DATA满足结束条件，do3，4，在规则集中选择一
8、条可应用于DATA 的规则R5，DATA R应用到DATA得到的结果6，,一个简单的例子,问题：设字符转换规则ABCACDBCGBEFDE已知：A，B求：F,一、综合数据库x，其中x为字符二、规则集,1，IF AB THEN C2，IF AC THEN D3，IF BC THEN G4，IF BE THEN F5，IF D THEN E,三、控制策略顺序排队四、初始条件A，B五、结束条件Fx,求解过程,数据库可触发规则被触发规则,A，B,（1）,（1）,A，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）,（
9、4）,A，B，C，D，G，E，F,1，IF AB THEN C 2，IF AC THEN D3，IF BC THEN G 4，IF BE THEN F5，IF D THEN E,1 .3 问题表示举例,例: 传教士与野人问题（Missionaries-Cannibals问题) 问题：N个传教士和N个野人在河边准备渡河，河岸有一条船，可同时乘坐k个人，要求在任何时刻，在河的两岸以及船上，传教士人数不能少于野人的人数。问：如何过河。以N=3，k=2，传教士和野人从左岸向右岸过河为例求解。,M-C问题（续1）,传教士人数,野人数,B=1：船在左岸B=0：船在右岸,M-C问题（续2）,1，综合数据库
10、（m, c, b)，其中：0m, c3, b 0, 12，初始状态 （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, 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
11、, 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) THEN (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
12、-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问题（另一种表示）,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
13、, c+j, 1),产生式系统的推理方式,正向推理 从已知事实出发，通过规则库求得结论，也称为自底向上（bottom-up），或称为数据驱动方式。 已知事实A，规则库中规则A B，B C，C D，则正向推理过程表示为： A B C D 反向推理 从目标出发，反向使用规则，求得已知事实，也称为自顶向下（top-down）推理方式，或称目标驱动方式。 双向推理（正反向推理） 是既自顶向下（top-down）又自底向上（bottom-up），直到达到某一个中间环节两个方向的结果相符便成功结束的推理方式。,正向推理步骤,1、正向推理步骤读入初始数据（事实）集到工作存储器,待测试规则表清空寻找与初始事实
14、相匹配的规则。取出规则，将规则的全部前件与工作器中所有的事实比较。如匹配成功，将规则加入冲突集；如冲突集为空，转向（3）；否则冲突消解；将所选择的规则的结论加入工作存储器；如达到目标结点转向（3）；否则返回（2）。结束,举例说明,以植物分类系统为例，对各种植物构造一条识别规则，规则左部为该植物的特征，右部为识别出的植物名。,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他是李R9：IF 它的果实为扁圆形AND它的果实外有纵沟 THEN 它是桃R10：IF它是苹果亚科植物AND它的果实里无石细胞 THEN它是苹果R11：IF它是苹果亚科植物AND它的果实里有石细胞 THEN它是梨R12：IF它的果肉为乳黄色AND它的果肉质脆 THEN它是苹果,
