2013第一章产生式系统-王洁

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