欢迎来到工友文库! | 帮助中心 工友共享,造福你我!
工友文库
全部分类
  • 行业文库 >
    行业文库
    行业标准 农林牧渔 能源矿业 电力热力 水利环境 材料技术 地理测绘 建筑工程 机械工程 制造加工 交通物流 网络计算 电气机电 信息通讯 汽车行业 航空航天 船舶工程 光电工程 住宿餐饮 财会金融 房地产业 城建规划 装饰装修 家电维修 电商行业 租赁商务 批发零售 居民服务 教育服务 医药卫生 体育行业 公共管理 图书管理 外语翻译 休闲旅游 文艺传媒 其他行业
  • 商业文档 >
    商业文档
    企业计划 工程管理 广告经营 财务报表 物业管理 质控管理 企业文化 绩效管理 商务礼仪 创业孵化 市场营销 经营企划 销售管理 营销创新 资本运营 招商加盟 合同协议 信息管理 励志材料 人事档案 员工关系 薪酬管理 招聘面试 其它文档
  • 办公文书 >
    办公文书
    统计图表 总结报告 演讲致辞 心得体会 述职报告 工作计划 解决方案 调研报告 事务文书 经验事迹 往来文书 规章制度 申请范文 求职简历 活动策划 会议纪要 党建材料 软件教程 其他文书
  • PPT模板库 >
    PPT模板库
    扁平风格 创意新颖 动画效果 动态模板 简约风格 静态模板 环保绿色 卡通风格 立体风格 欧洲风格 手绘风格 创意黑板 相册风格 星空风格 炫酷科技 中国风格 医疗风格 高端商务 工作常用 总结报告 毕业答辩 节日庆典 公益风格 化妆美容 婚礼策划 餐饮美食 培训课件 融资路演 商业策划 英文模板 党政机关 述职竞聘
  • 小学初中 >
    小学初中
    幼儿教育 小学语文 小学数学 小学英语 初中语文 初中数学 初中英语 初中物理 初中化学 初中地理 初中生物 初中政治 初中历史 思想品德 小学竞赛 初中竞赛 其他学科
  • 高中教育 >
    高中教育
    高中语文 高中数学 高中英语 高中物理 高中化学 高中生物 高中地理 高中政治 高中历史 高考资料 高中竞赛 其他学科
  • 高等教育 >
    高等教育
    基础课 艺术类 哲学类 体育类 水利类 测绘类 法学类 历史学 社会学 心理学 教育学 政治学 统计学 房地产 语言文化 生物科学 医药卫生 天文气象 地理科学 环境科学 系统科学 材料科学 机械仪表 图书档案 土建工程 海洋工程 轻工纺织 工程力学 能源动力 光电工程 电力技术 市政工程 财会金融 工商管理 语言文学 广播影视 公安司法 汽车汽修 交通运输 水产加工 植物生产 森林资源 动物科学 食品加工 餐饮旅游 公共事业 新闻传播学 农林业工程 城镇规划管理 水文与水资源 地矿及资源勘查 航空航天与武器 管理科学与工程 农林业经济管理 机电设备及自动化 计算机与信息科学 大学生竞赛资料
  • 执业资格考试 >
    执业资格考试
    财会类考试 建筑类考试 外贸类考试 外语类考试 医药类考试 管理类考试 公务员类考试 司法法律考试 教师资格考试 计算机类考试 公共服务类考试 其他资格证考试
  • 一线采风 >
    一线采风
    一线新闻 事迹宣传 工友作品
  • 教育视频 >
    教育视频
    幼儿教育视频 小学教育视频 初中教育视频 高中教育视频 大学教育视频 C#自学视频教程 软件视频教程 英语视频教学 其他教学视频
  • 换一换
    首页 工友文库 > 资源分类 > PPTX文档下载
     

    人工智能第二章教学课件.pptx

    • 资源ID:20110       资源大小:242.16KB        全文页数:49页
    • 资源格式: PPTX        下载权限:注册会员/VIP会员    下载费用:0金币 【人民币0元】
    下载资源需要0金币 【人民币0元】
    已注册用户请登录:
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,既可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰   

    人工智能第二章教学课件.pptx

    8/17/2019,1,知识表示,知识是一切智能行为的基础,也是软件智能化的重要研究对象。要使软件具有智能,就必须使它具有知识,而要使软件具有知识,首先必须解决知识的表示问题。 所谓知识表示实际上就是对知识的一种描述,即用一些约定的符号把知识编码成一组计算机可以接受的数据结构。所谓知识表示过程就是把知识编码成某种数据结构的过程。 一般来说,同一知识可以有多种不同的表示形式,而不同表示形式所产生的效果又可能不一样。,8/17/2019,2,常用的知识表示方法,非结构化方法 逻辑表示法 QA3,STRIPS,DART,MOMO 产生式系统 DENDRAL,MYCIN 结构化方法 框架 语义网络 过程式知识表示法,8/17/2019,3,第二章 产生式系统,2.1 产生式系统概述 一、产生式系统的定义 产生式系统是人工智能系统中常用的一种程序结构,是一种知识表示系统。 通常由以下三部分组成 综合数据库 产生式规则集 控制系统,8/17/2019,4,综合数据库存放问题的状态描述的数据结构。 Note 综合数据库不是常规意义的数据库,是一种数据结构。一般数据库所存数据的结构很简单,通常只有数值与字符串;综合数据库的数据可以很复杂,其中状态描述可以为常规的各种数据结构,如表、数组、字符串、集合、矩阵、 树、图等等。 综合数据库是动态变化的。,一、产生式系统的定义,8/17/2019,5,产生式规则形式 IF前提条件 THEN操作 当规则的前提条件被某一状态描述满足时,就对该状态施行规则所指出的操作。,一、产生式系统的定义,8/17/2019,6,控制系统 (1)选择规则 对同一个状态的多个可用规则排序。 (2)检验状态描述是否满足终止条件。 如果满足终止条件,则终止产生式系统的运行, 并用使用过的规则序列构造出问题的解。,一、产生式系统的定义,8/17/2019,7,二、产生式系统的例,八数码难题 由8个标有1-8的棋子和一个33的棋盘组成。把8个棋子放在棋盘里,形成一个初始状态,然后移动棋子,想办法达到规定的目标状态。在移动棋子时,只能把棋子移进相邻的空格中。 图2.1 八数码难题的初始状态与目标状态,8/17/2019,8,八数码难题的产生式系统表示,综合数据库以状态为节点的有向图。 状态描述 33矩阵 产生式规则 IFThen; IFThen ; IFThen ; IFThen 。 控制系统 选择规则按左、上、右、下的顺序移动空格。 终止条件匹配成功。,8/17/2019,9,三、产生式系统的基本过程,Procedure PRODUCTION DATA←初始状态描述 until DATA 满足终止条件,do begin 在规则集合中,选出一条可用于DATA的规则R DATA←把R应用于DATA所得的结果 End,8/17/2019,10,步骤4是不确定的,只要求选出一条可用的规则 R,至于这条规则如何选取,却没有具体说明。 选取规则所依据的原则称为控制策略。 多数人工智能系统控制策略的信息并不足以在 第4步选出最合用的规则,因此,控制策略便成了一 个搜索过程。 高效的系统需要被求解问题足够的知识,以便在 步骤4选出一条最合用的规则。第三章,第四章,三、产生式系统的基本过程,8/17/2019,11,产生式系统的特点,一、模块性强。综合数据库、规则集和控制系统相 对独立,程序的修改更加容易。 二、各产生式规则相互独立,不能互相调用,增加 一些或删去一些产生式规则都十分方便。 三、产生式规则的形式与人们推理所用的逻辑形式 十分接近,人们具有的知识转换成产生式规则 很容易,产生式规则也容易被人们读懂。 DENDRAL和MYCIN都采用了产生式系统的结构。,8/17/2019,12,2.2 控制策略,产生式系统的控制策略分为两类 不可撤回的控制策略 试探性控制策略回溯方式和图搜索方式,8/17/2019,13,一、不可撤回的控制策略(瞎子爬山法),基本思想 采用不可撤回控制方式的解题过程类似于盲人爬山过程,是利用关于每一个状态的局部知识构造全局性解的过程。在盲人爬山过程中,无论爬到哪一点,他总沿着坡度最陡的方向向上爬,这是局部性的知识,尽管他事先对爬山路线并不了解,但只要按照这个原则向上爬,就一定能爬到某一山顶,于是确定了一条从山脚到山顶的爬山路线,也可以说构造出一个具有某种意义下全局性的解。,8/17/2019,14,一、不可撤回的控制策略,爬山函数定义在整个综合数据库上的实数值函数, 目标状态有最大的函数值。 目 标爬到山顶。 控制策略应用爬山函数选一规则,使得所选下一状态的爬山函数值不减少且最大(有两个相同的最大值时任选一个;若无这样的规则,则终止爬山过程)。,8/17/2019,15,设爬山函数CFS 不在目标位的数码个数的负值。 初始状态S0 目标状态Sg CFS0= - 4 CFSg= 0 状态描述S3阶方阵 4条产生式规则使用顺序空格左、上、右、下移。,例八数码难题,不可撤回式控制,8/17/2019,16,控制策略处于任一状态S,系统根据爬山函数选择一条规则使得这条规则作用于 S 时,获得的下一状态爬山函数不减少且最大(亦即距离目标状态最少)。,例八数码难题,不可撤回式控制,8/17/2019,17,,,,,,,例八数码难题 不可撤回式控制,-4,-3,-3,-1,-2,0,8/17/2019,18,不可撤回控制策略的优点,1. 只记录当前一个节点,空间复杂性很低。 2. 若能找到解,则速度很快。,8/17/2019,19,不可撤回控制策略的局限性,多数情况下找不到解。原因 a 爬山函数有多个局部极大值 例如 目标 0 初始 -2 b 爬山函数具有“平顶值” 解决方法设计更好的爬山函数;选多余规则,8/17/2019,20,二、回溯控制策略,回溯方式是一种试探性的控制策略。(类似深度优先) 基本思想 控制系统先选用一条规则,如果发现这条规则的选用不能导致产生解,则系统“忘掉”选用规则所涉及的步骤和产生的状态,然后选用另外一条规则,重新进行试探。,8/17/2019,21,回溯方法特点,1.只存储初始节点到当前节点的路径,占用空间较小。 2. 总的时间复杂性无法定论 最好情况复杂性很低当控制系统掌握较多的有关解的知识时,则回溯次数大为减少,效率高。 最坏情况复杂性很高当控制系统一点也没掌握有关解的知识时,则规则选取是任意的,回溯次数高,效率低。 为了避免进入无限的境地,设置回溯深度限制强行回溯,问题太深效率低;太浅可能找不到解。 3. 当深度限制可变时,通常能找到解,是实际用得多、应用最广的一种搜索策略。,8/17/2019,22,四条规则使用顺序左、上、右、下(可加入启发式信息,如使用爬山函数安排规则的顺序) 深度6 控制策略回溯式 回溯条件 ⑴ 产生了一个上溯到初始状态的路径上出现过的状态时(产生了祖先节点)。 ⑵ 无可用的规则。 ⑶ 达深度未得解。,八数码难题的初始状态与目标状态,例八数码难题 回溯式,8/17/2019,23,2 8 3 1 6 4 7 5,8 3 2 6 4 1 7 5,8 3 2 6 4 1 7 5,2 8 3 1 6 4 7 5,8 3 2 6 4 1 7 5,8 3 4 2 6 1 7 5,,8 3 2 6 4 1 7 5,8 6 3 2 4 1 7 5,2 8 3 6 4 1 7 5,8 3 2 6 4 1 7 5,8 6 3 2 4 1 7 5,8 3 2 6 4 1 7 5,8 3 2 6 4 1 7 5,,,,,,,,,八数码问题回溯控制,8 3 2 6 4 1 7 5,,,(1) (5) (6) (5) (2) (6) (7) (6) (3) (7) (7) (4) (5) (6),8/17/2019,24,三、图搜索控制策略,基本思想从初始状态开始,使用全部可用规则序列。对所有的下一步状态每一个再用全部可用的规则,直到目标状态为止。(类似广度优先搜索策略) 搜索树记录规则的应用和所产生的状态的树结构。 树根初始状态 有向弧规则的使用 除根以外的其它各节点规则应用的结果 图搜索控制方式不断地扩展搜索树,直到它包括了满足终止条件的节点为止。,8/17/2019,25,图搜索控制策略的特点,1.不再选择规则,而是使用所有可用的规则,下一步选择节点来扩展。 2.存储所有产生的节点,占用空间大。 3.有解一定能找到(相当于穷举)。 4.平均时间复杂性高,系统效率低。,8/17/2019,26,,,例八数码难题 图搜索式,八数码难题的初始状态与目标状态,书中图按照深度小的排在前面、优先选择左节点。,8/17/2019,27,四、产生式系统的工作方式,1.正向产生式系统(数据驱动控制) 综合数据库用状态描述 产生式规则F规则--状态产生新状态 从初始状态出发,不断地应用F规则,直到产生目标状态为止。 适用条件初始节点数≤目标节点数,8/17/2019,28,,2. 反(逆)向产生式系统(目标驱动控制) 综合数据库用目标描述 产生式规则B规则 目标产生子目标 从目标状态出发,利用反向的产生式规则( B规则 )不断地产生子目标,直到产生出与初始状态相同的子目标为止。 适用条件初始节点数≥目标节点数,8/17/2019,29,,3. 双向产生式系统正向产生式系统和反向产生式系统结合. 综合数据库既有初始状态描述,又有目标状态描述。 产生式规则集既有F规则,又有B规则。 正向产生式规则用在初始方向的状态描述上,反向产生式规则用在目标描述上。 控制系统判断选F规则还是B规则; 判断已经产生的状态和目标是否能以某种方式匹配, 从而满足结束条件。 结束条件中间汇合时的状态。 适用条件初始节点数与目标节点数都很多。 特点效率高;复杂。,8/17/2019,30,2.3 特殊的产生式系统,一、可交换产生式系统 在某些产生式系统中。规则应用的次序对产生的状态无影响,即从初始状态到目标状态不依赖规则次序,因此可应用不可撤回式控制策略,从而提高了产生式系统的效率,这类产生式系统就是可交换的产生式系统。 例基于归结方法的产生式系统,8/17/2019,31,一个产生式系统称为可交换的,如果对任意状态描述D具有如下性质 a 设RD是可应用于D的规则集,任取r ∈RD, r作用于D得 D’,设为D’ r D,则r对D’ 可用即设D’的可用规则集为RD’,则r∈ RD’ ,即RD RD’ ;(每一条对D可应用的规则,对于对D应用一条可应用的规则后所产生的状态描述仍是可应用的)(可应用性),可交换产生式系统定义,8/17/2019,32,,b设D满足目标条件,D的可用规则集为RD,任取 r∈ RD ,用r作用到D产生状态D’ ,D’满足目标条件。(如果D满足目标条件,则对D应用任何一条可应用的规则所产生的状态描述也满足目标条件) (可满足性)。,8/17/2019,33,,(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的规则所构成的规则序列所产生的状态描述不因序列的次序不同而改变)无次序性)。,8/17/2019,34,R1,R3,R1,S12,S11,S0,S13,S3,S2,SG,S1,R3,R2,R1,R2,R3,R1,R2,R3,R2,R1,R3,R3,R2,R1,R2,R3,R1,可交换的产生式系统例,R2,R3,R2,R1,8/17/2019,35,可交换产生式系统优点从初始状态到目标状态不依赖规则次序,不必探查等价路径,可以使用不可撤回策略。 Note产生式系统的可交换性并不意味着整个规则序列的次序可以改变。只是最初作用于给定状态的那些规则使用起来与次序无关。,8/17/2019,36,设产生式系统P综合数据库,一组规则,图搜索策略 造另一可交换的产生式系转换P’如下 综合数据库 初始状态P的整个搜索树 目标状态只剩解路,转换 可用如下方法将一产生式系转换为可交换的,8/17/2019,37,转换 可用如下方法将一产生式系转换为可交换的,规则Ri若综合数据库中第i层节点n不是解路P上的点,则从综合数据库中删除节点n。 控制策略不可撤回式 将P转换为P’, P’是可交换的产生式系统 综合数据库变复杂;规则数目少,但操作复杂(如何判断n不是解路P上的点);控制策略简单。,8/17/2019,38,二、可分解的产生式系统,可交换产生式系统可以避免搜索多余路径,可 以使用不可撤回策略。避免搜索多余路径的另一 种方法是可分解的产生式系统。,8/17/2019,39,可分解的产生式系统例字符串重写,综合数据库串节点的有向图 状态字符串(或用表) 初始状态 C, B, Z 产生式规则 R1 IFTHEN (重写规则) R2 IFTHEN R3 IFTHEN R4 IFTHEN 控制系统 选择规则用图搜索控制策略 终止条件状态描述仅有M组成的符号串。,8/17/2019,40,重写问题的解序列(不完整),R3,R3,R3,R3,R3,R4,R4,R3,R3,R3,R2,R1,R4,(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,,,,,,,,,,,,,,,,,R2,R3,B,M,B,Z,8/17/2019,41,,Note 按照图搜索控制方式在产生终止状态时可能会探索许多完全等价的路径,导致系统的低效。 从失败路径上浪费很多工作。 节点的内容之间存在着大量的符号冗余。,8/17/2019,42,,观察 该产生式系统的初始状态可以分解成 C, B和Z, 然后把产生式规则分解使得可应用于这些组成部分 R1 C → D, L R2 C → B, M R3 B → M, M R4 Z → B, B, M 应用规则后所得的结果状态又可以进一步分裂,这样不断地分解,不断地应用规则,直到所产生的状态是M字符为止,即终止条件分解为一个M字符作成的状态。,8/17/2019,43,重写问题的与/或树,R1 R2 R3 R4 R3 R3 R3,8/17/2019,44,定义 能够把产生式系统综合数据库的状态描述分解为若干组成部分,产生式规则可以分别用在各组成部分上,并且整个系统的终止条件可以用在各组成部分的终止条件表示出来的产生式系统,称为可分解的产生式系统。,可分解的产生式系统,8/17/2019,45,,Note 对分解出的独立分量的处理方式 可并行处理 也可串行处理(一般情况下) (1)按产生的时间排序; (2)在处理过程中动态排序。,8/17/2019,46,可分解的产生式系统的基本过程,Procedure SPLIT DATA ← 初始状态描述 {Di} ← DATA的分解结果;每个Di看成是独立的状态描述 until 对所有的Di {Di}, Di都满足终止条件,do begin 在{Di}中选择一个不满足终止条件的D* 从{Di}中删除D* 从规则集合中选出一个可应用于D*的规则R D ← 把R应用于D*的结果 {di} ← D的分解结果 把{di}加入{Di}中 end,8/17/2019,47,SPLIT的控制策略在步骤5中如何选取D*,在步骤7如何选取R。 NotePRODUCTION和SPLIT是两个比较重要的算法, 本课的重点之一。 PRODUCTION的步骤4 控制策略,可分解的产生式系统的基本过程,8/17/2019,48,可分解产生式系统的例子 --符号积分,SAINT系统,1961年Slagle提出,1963年对SAINT进行改 进,达到优秀大学生水平,是一个可分解产生式系统。 输入不定积分题目;输出积分的结果函数 综合数据库以字符串为节点的与或图 状态字符串 初始状态用字符串表示的不定积分题目(被积函数) 产生式规则分步积分规则、代数替换、三角替换等等 例如IFTHEN 控制系统 选择规则图搜索 终止条件与系统内部保存的基本积分表中的函数具有相同的形式 。 如∫uduu2/2,8/17/2019,49,,,,

    注意事项

    本文(人工智能第二章教学课件.pptx)为本站会员(小旋风)主动上传,工友文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知工友文库(发送邮件至gydoc@qq.com或直接QQ联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    copyright@ 2019-2022 工友文库网站版权所有
    经营许可证编号:鲁ICP备19032292号-1


    1
    收起
    展开