人工智能及应用_ch2_2

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,知识表示,产生式表示法,框架表示法,1,产生式表示法,产生式表示的基本方法。,产生式系统的基本结构。,产生式系统的分类。,产生式表示法的特点。,2,产生式表示的基本方法,事实表示：把事实看作是断言一个语言变量的值或多个语言变量间的关系的陈述句。,例如：,雪,是,白的,。,王蜂,热爱,祖国。,对确定性知识的表示为一个三元组：,（对象，属性，值）或,（关系，对象1，对象2）,3,产生式表示的基本方法,不确定知识表示为一个四元组：,（对象，属性，值，可信度因子）,其中可信度因子是0到1的数值。,（雪，颜色，白）,（热爱，王蜂，祖国）,4,产生式表示的基本方法,规则的表示：规则一般描述事物间的因果关系，规则的产生式表示形式称为产生式规则，简称为产生式。,P,Q 或,IF,P,THEN Q 置信度,P是产生式的前提或前件，一般由事实的逻辑组合构成。Q是产生式的后件或结论，一般是结论或操作。,5,产生式表示的基本方法,产生式的含义：如果前件P满足，则可推出结论Q，或执行Q所规定的操作。,例如：r14：IF 该动物是鸟 AND 会游泳 AND 不会飞 AND 有黑白二色 THEN 该动物是企鹅。,6,产生式与蕴含式的区别,蕴含式只能表示精确性知识，产生式不仅可以表示精确知识，也可表示不精确性知识。,使用过程中对前件的匹配，蕴含式要精确匹配，而产生式可以相似匹配。,7,产生式表示的示例,八数码游戏：在3X3的九宫格棋盘上，摆有八个将牌，每个将牌刻有18中的某个数码。棋盘上有一个空格，允许将牌向空格移动。给定初始布局和目标布局，如何移动将牌实现从初始布局到目标布局,的转变。,8,产生式表示的示例,初始布局,目标布局,9,产生式表示的示例,问题的表示：,综合数据库：Sij 1,i,j,3 Sij,1,2,8,规则库:,IF j-1,1 THEN Sij=Sij-1,Sij-1=0,IF i-1,1 THEN Sij=Si-1j,Si-1j=0,IF j+1,3 THEN Sij=Sij+1,Sij+1=0,IF i+1,3 THEN Sij=Si+1j,Si+1j=0,10,产生式系统的基本结构,通常将使用产生式表示方法构造的系统称为产生式系统，产生式系统的基本结构如下图：,规则库或知识库,综合数据库,控制系统,11,规则库,用于存放系统相关领域的所有知识的产生式。,有效地表达领域内的过程性知识。,建立那些产生式规则；,对不确定性知识如何表示；,规则库中的知识是否具有一定的完备性。,对知识进行合理的组织与管理，如将规则分成无关联的子集。,12,综合数据库,又称为事实库，用来存放问题求解过程中信息的数据结构。包含；初始状态、原始证据、推理得到的中间结论以及最终结论。,13,控制系统,由一组程序组成的推理机，主要任务：,按一定的策略从规则库中选择规则，与综合数据库中的已知事实进行匹配，若匹配成功则启用规则，否则不使用此规则。,当匹配成功的规则多于一条时，使用冲突消解机制，选出一条规则执行。,执行规则后，将结果添加到综合数据库中，若后件是操作时执行操作。,确定系统执行停止的条件是否满足。,14,产生式系统的示例,用于识别老虎、金钱豹、长颈鹿、企鹅、信天翁和鸵鸟等动物的产生式系统，其包含15条规则：,r1: IF 该动物有毛发 THEN 该动物是哺乳动物。,r2: IF 该动物有奶 THEN 该动物是哺乳动物。,r3: IF 该动物有羽毛 THEN 该动物是鸟。,r4: IF 该动物会飞 AND 会下蛋 THEN 该动物是鸟。,r5: IF 该动物吃肉 THEN 该动物是肉食动物。,r6: IF 该动物有犬齿 AND 有爪 AND 眼盯前方 THEN 该动物是肉食动物。,15,产生式系统的示例,r7: IF 该动物是哺乳动物 AND 有蹄 THEN 该动物是有蹄类动物。,r8: IF 该动物是哺乳动物 AND 是嚼反刍 THEN 该动物是有蹄类动物。,r9: IF 该动物是哺乳动物 AND 是肉食动物 AND 黄褐色AND 有暗斑点 THEN 该动物是金钱豹。,r10: IF 该动物是哺乳动物 AND是肉食动物 AND 黄褐色AND 有黑色条纹 THEN 该动物是老虎。,r11: IF 该动物是有蹄类动物 AND 长脖子 AND 长腿 AND 有暗斑点 THEN 该动物是长颈鹿。,16,产生式系统的示例,r12: IF 该动物是有蹄类动物 AND 黑色条纹 THEN 该动物是斑马。,r13: IF 该动物是鸟 AND 长脖子 AND 长腿 AND 不会飞 THEN 该动物是鸵鸟。,r14：IF 该动物是鸟 AND 会游泳 AND 不会飞 AND 有黑白二色 THEN 该动物是企鹅。,r15: IF 该动物是鸟 AND 善飞 THEN 该动物是信天翁。,17,产生式系统的示例,根据规则可以绘出推理链。,虎,黄褐色,肉食动物,有齿,有爪,吃肉,眼盯前方,金钱豹,哺乳动物,有毛,有奶,有暗斑点,有黑色条纹,18,产生式系统的示例,推理过程,确定推理终止条件：目标集（7类动物）或所有规则使用完毕。,已知事实：有暗斑点、有长脖子、有奶、有长腿、有蹄，将其加入综合数据库。,搜索过程：,从规则库取出r1，将前提与已知事实匹配，不成功。,从规则库取出r2，将前提与已知事实匹配，成功。执行r2得到结论是哺乳动物，将其加入综合数据库。此时综合数据库有暗斑点、有长脖子、有奶、有长腿、有蹄、哺乳动物,19,产生式系统的示例,用r3,r4,r5,r6进行匹配均不成功,。,从规则库取出r7，将前提与已知事实匹配，成功。执行r2得到结论是有蹄动物，将其加入综合数据库。此时综合数据库有暗斑点、有长脖子、有奶、有长腿、有蹄、哺乳动物、有蹄动物。,用r8,r9,r10进行匹配均不成功。,R11与综合数据库匹配成功，得出结论该动物是长颈鹿，结论再目标集中停止搜索。,20,产生式系统的基本过程,初始化综合数据库，把问题的已知事实送入综合数据库。,若规则库中存在尚未使用过的规则，若有则执行,3,；否则转,7,。,检查规则库中未使用的规则前件能否与综合数据库中的事实匹配，若有从中选择一个；否则转,6,。,执行当前选中的规则，并标记，将结论加入综合数据库，若结论是操作，则执行操作。,21,产生式系统的基本过程,5. 检查综合数据库中是否包含了问题的解，若包含，问题解决，求解过程结束；否则转2。,6. 当规则库有未使用的规则，但均不能与已知事实匹配，要求用户提供新的事实，若提供，则转2；否则，问题无解停止求解过程。,7. 若规则库中不再有未使用过的规则，问题无解，停止求解过程。,22,产生式系统的控制策略,不可撤回方式：利用问题的局部信息决定选用规则作用于综合数据库，在根据新的状态继续选取规则。,试探性方式：问题求解时试探某条规则，若不行则退回原状态。,回溯方式,图搜索方式,23,产生式系统的类型,按推理方向,正向推理产生式系统；,逆向推理产生式系统；,双向推理产生式系统。,24,产生式系统的类型,按规则库和综合数据库的性质和结构,可交换的产生式系统；,可分解的产生式系统；,可恢复的产生式系统。,25,可交换的产生式系统,一个产生式系统对规则的使用次序无关称为可交换的产生式系统。,设：,DB：综合数据库。,RB：规则库。,DBi：是第i次使用规则后得到的综合数据库。,RS,RB：是DBi可用的规则集合。,26,可交换的产生式系统,产生式系统是可交换的如果RS和DB满足：,使用,RS,中任意一条规则,R,使,DB,改变后，,RS,仍是新的,R,（,DB,）的,可用的规则集合。,如果,DBi,满足目标条件，则,R,（,DB,）也满足目标条件。,对,DBi,使用一系列规则,R1,，,R2,，。，,Rk,得到一个新的综合数据库,DBi+k,，改变规则序列的使用次序得到的综合数据库依然是,DBi+k,。,27,可交换的产生式系统,例：设给定整数集a,b,c，通过把集合中任意一对元素的乘积作为新元素添加到集合中的办法扩大整数集， 要求经过若干次操作后生成整数集a,b,c,ab,bc,ca。,初始状态：a,b,c,目标状态：a,b,c,ab,bc,ca,28,可交换的产生式系统,规则集：,r1: IF a,b,c THEN a,b,c,ab,r2: IF a,b,c THEN a,b,c,bc,r3: IF a,b,c THEN a,b,c,ca,29,可分解的产生式系统,把一个整体问题分解为若干个子问题，然后通过子问题的求解得到整体问题的解的一种产生式系统。,产生式系统可分解的条件：可以将系统的综合数据库DB以及终止条件都分解为若干个独立的部分,30,可分解的产生式系统_示例,综合数据库的初始内容是C，B，Z，系统的规则集：,r1: IF C THEN D,L,r2: IF C THEN B,M,r3: IF B THEN M,M,r4: IF Z THEN B,B,M,终止条件是生成只包含M的综合数据库。,31,可分解的产生式系统,C，B，Z,C,B,Z,B，M,D，L,B,M,M，M,M，M,B，B，M,M,B,B,M，M,M，M,32,产生式表示法的特点,优点：,自然性：与人类表达因果关系的形式一样，自然，直观，而且便于推理。,模块性：规则库、综合数据库与推理机分离。,有效性：即可以表达确定性知识，又可以表达不确定性知识。,清晰性：固定的知识格式。,33,产生式表示法的特点,缺点,效率不高,不适合表达结构性知识,34,框架表示法,框架表示的基本概念,框架系统,框架系统求解的基本过程,框架表示法的特点,35,框架表示的基本概念,1975年明斯基提出框架理论，并应用于理解视觉和自然语言对话等方面的研究。,框架的基本思路：当一个人遇到新的情况（或看待问题的观点发生实质变化）时，他会从记忆中选择一种结构，即“框架”。这是一种记忆下来的轮廓，按照需要改变其细节就可以用其拟和真实情况(Minsky 1975),36,框架表示的基本概念,框架实质上是一种数据结构一般表示为：,框架名,槽1侧面11值111。,侧面12值121。 。,槽2侧面21值211。,侧面22值221。,。,37,框架表示的基本概念,例如表示一个人可以用职业、身高、体重等项来描述。,框架名,JOHN,isa : PERSON,profession: PROGRAMMER,height : 1.8m,weight : 79kg,38,框架表示的基本概念,框架的槽值和侧面值即可以是数字、字符串、布尔值，也可以是满足给定条件的操作或过程，还可以是另外一个框架名。,框架与实例框架：对一个具体问题可以根据问题设计好适合该问题描述的框架。当把具体信息添入框架的槽和侧面后就得到一个该框架的实例框架。,39,框架表示的基本概念,例如：框架名硕士生,姓名：单位（姓，名）,性别：范围（男，女）,默认：男,年龄：单位（岁）、条件：岁16,学籍：硕学籍,40,框架表示的基本概念,框架名硕士生-1,姓名：杨叶,性别：女,年龄：23岁,学籍：硕学籍-1,41,框架系统,单个框架只能表示简单的知识，当知识比较复杂时往往需要把多个相互联系的框架组织起来进行表示，这些相互联系的框架就形成了一个框架系统。,42,框架系统的结构,横向联系：框架的槽值可以是框架这建立了框架间的横向联系。,硕士生-1,姓名：杨叶,性别：女,年龄：23,学籍：硕学籍-1,硕学籍-1,入学日期：04-09,第一学年：注册,第二学年：,成绩：成绩1,43,框架系统的结构,纵向联系,：,描述一些事物时，它们会有一定的共同属性，将共同属性抽出，构成上层框架，然后再对不同的事物的独有的属性分别构成下层框架。为了指明上下层框架间的关系，在下层框架中设立一个专用槽-继承槽，指明框架的上层槽是那一个。如此建立的框架间的联系称为纵向联系。,纵向联系的下层框架自动继承上层框架的属性。,44,框架系统的结构,例如：,教职员工框架,教员框架,职工框架,教员1,教员2,员工2,员工2,45,框架系统的结构,框架名教职员工,姓名：单位（姓，名）,年龄：单位（岁）,性别：范围（男，女），默认：男,住址：住址框架,开始工作时间：单位（年，月）,截止工作时间：单位（年，月），默认：现在,46,框架系统的结构,框架名教员,继承：教职员工,部门：单位（学院，系）,职称：范围（教授，副教授，讲师，助教）,语种：范围（英语，日语，法语，德语，俄语） 默认：英语,47,框架系统中的预定义槽,用框架表示复杂问题时，框架间除了横向和纵向关系外，还有其他形式的联系。,表达框架间的关系是通过在槽中添入框架名实现的。为了实现框架间其他关系的描述，框架系统预定义一些常用的槽。,48,框架系统中的预定义槽,常用的预定义槽有以下几种：,isa槽：描述具体事物与其抽象概念间的类属关系。直观含义是“是一个”，表示一个事物是另一个事物的特例。,人-杨叶,AKO槽：用来指出事物间在抽象概念上的类属关系。其直观含义是“是一种”，表示一个事物是另一个事物的一种类型。,运动员-棋手,49,框架系统中的预定义槽,part-of槽：指出部分与全体的关系。,汽车-轮胎,infer槽：用于指出两个框架所描述事物间的推理关系。,框架名诊断规则,症状1：咳,症状2：发烧,症状3：打喷嚏,infer: ,可信度：0。8,框架名结论,病名：感冒,用药：口服感冒清,用法：一日三次，一次2粒,50,框架系统求解的基本过程,将问题用一个框架表示出来。,通过与知识库中以有的框架进行匹配，找到一个或几个可匹配的预选框架。,进一步收集信息，评价预选框架，决定是否接受它。,说明：,匹配：如果两个框架的各个对应槽没有矛盾，或满足预先给定的条件，即可以认为两个框架匹配。,51,框架表示法的特点,优点,结构性：善于表示结构性知识。,深层性：框架表示不仅可以从多个方面、多重属性表示知识，而且可以通过预定义槽表示知识的结构层次和因果关系，因此能表达事物间复杂深层联系。,继承性：下层框架可以继承上层框架的槽值。,自然性：模拟人类对实体的多方面、多层次的存储结构，直观自然，易于理解。,52,框架表示法的特点,缺点,缺乏框架的形式理论,缺乏过程性知识表示,53,