人工智能复习幻灯片ppt课件.ppt

《人工智能复习幻灯片ppt课件.ppt》由会员分享，可在线阅读，更多相关《人工智能复习幻灯片ppt课件.ppt（138页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、复习复习第第0章章 绪论绪论 第第1章章搜索搜索问题问题第第2章章 与或图搜索与或图搜索问题问题第第3章章 谓词逻辑与归结原理谓词逻辑与归结原理第第4章章 知识表示知识表示方法方法 第第5章章 不确定性不确定性推理推理 第第6章章 机器学习机器学习 第第7章章 高级高级搜索搜索1 第第0章章 绪论绪论主要知识点：人工智能的定义人工智能的研究目标人工智能的三个主要学派人工智能的主要研究应用领域。2 第第0章章 绪论绪论 人工智能的定义 研究怎样使计算机模仿人脑所从事的感知、推理、学习、思考、规划等思维活动，来解决需要用人类智能才能解决的问题。3 第第0章章 绪论绪论人工智能的研究目标近期目标建造

2、智能计算机代替人类的部分智力劳动 远期目标用自动机模仿人类的思维过程和智能行为4 第第0章章 绪论绪论 符号主义符号主义（Symbolists),又称逻辑主义(Logics),心理学派(Psychlogism),计算机学派(Computerism). 原理主要为物理符号系统(符号操作系统），认为人工智能源于数理逻辑，人的认知基元是符号,认知过程就是符号操作过程，人和计算机系统都是一个物理符号系统. 其方法: 以功能模拟人的智能 5 第第0章章 绪论绪论 联结主义联结主义(Connectionism),又称仿生学派(Bionicisism),生理学派(Physiologism). 主要原理为神经

3、网络及神经网络间的连接机制与学习算法，认为人工智能源于仿生学.特别是人脑模型的研究，认为人的认知思维基元是神经元,用大脑工作模式代替电脑工作模式。 其方法:以结构模拟人的智能6 第第0章章 绪论绪论 联结主义联结主义(Connectionism),又称仿生学派(Bionicisism),生理学派(Physiologism). 主要原理为神经网络及神经网络间的连接机制与学习算法，认为人工智能源于仿生学.特别是人脑模型的研究，认为人的认知思维基元是神经元,用大脑工作模式代替电脑工作模式。 其方法:以结构模拟人的智能7 8第第0章章 绪论绪论人工智能研究论域 自然语言理解与机器翻译 数据库的智能检索

4、 专家咨询系统 定理证明 博弈 机器人学 自动程序设计 组合调度问题 感知问题 第第1章章 搜索问题搜索问题 主要知识点： 状态空间表示法 盲目搜索和启发式搜索的特点 宽度优先搜索、深度优先搜索、分支界限法、最佳优先搜索法、A算法、A*算法9 问题的状态空间问题的状态空间(state space)是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、算符集合F以及目标状态集合G。因此，可把状态空间记为三元状态(S，F，G)。 图搜索的定义一种计算机在状态图中寻找路径的方法。第第1章章 搜索问题搜索问题10 深度优先搜索 首先扩展最新产生的(即最深的)节

5、点。深度相等的节点可以任意排列。这种盲目(无信息)搜索叫做深度优先搜索或纵向搜索。 深度优先搜索算法是一种“后进先出”的算法。第第1章章 搜索问题搜索问题11 八数码魔方的八数码魔方的深度优先深度优先搜索树搜索树第第1章章 搜索问题搜索问题12 宽度优先搜索 以接近起始节点的程度逐层扩展节点的搜索方法(breadth-first search)，这种盲目(无信息)搜索叫做宽度优先搜索或横向搜索。 宽度优先搜索算法是一种“先进先出”的算法。第第1章章 搜索问题搜索问题13 1238456712384123845674123856712 384123845671238456712384567678

6、910111213123845675675671123845671238456712384567123845672345八数码魔方的八数码魔方的宽度优先搜索宽度优先搜索树树13456123845671238456712384567123845671 238456723242526271236782212384567123845671 238456712 38456712384567123845671238456714151617181920211238456742829303112 38456712 38456712384567123845673213456123678381238456739

7、扩展26个节点，共生成46个节点之后，才得到目标14 分支界限法 分支界限法是优先扩展当前具有最小代价的分支路径的节点，其评价函数为f(n)=g(n)，直到生成目标节点为止。第第1章章 搜索问题搜索问题15 A算法 定义每个节点n的估价函数f(n)=g(n)+h(n) 从起始节点到节点n的代价g(n)以及从节点n到达目标节点代价的估算值h(n)，找出一个最有希望的节点来扩展。 第第1章章 搜索问题搜索问题16 A*算法 在A算法中，如果满足条件：h(n)h*(n)则A算法称为A*算法。 在A算法中，如果对所有的x存在h(x)h*(x),则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。

8、第第1章章 搜索问题搜索问题17 8数码问题 h1(n) = “不在位”的将牌数 h2(n) = 将牌“不在位”的距离和2 8 31 6 47 51 2 3457 6 8将牌1：1将牌2：1将牌6：1将牌8：2八数码魔方（8-puzzle problem）12384567（目标状态）12384567（初始状态）18 57123845671238456712384567(1+4=5)(1+6=7)(1+6=7)123845671238456712384567(2+5=7)(2+5=7)(2+3=5)1238456712 384567(3+2=5)(3+4=7)12384567(4+1=5)813

9、245671 2384567(5+0=5)(5+2=7)123846(0+5=5)7八数码魔方的八数码魔方的A A* *算法搜索树算法搜索树19 57123845671238456712384567(1+4=5)(1+6=7)(1+6=7)123845671238456712384567(2+5=7)(2+5=7)(2+3=5)1238456712 384567(3+2=5)(3+4=7)12384567(4+1=5)813245671 2384567(5+0=5)(5+2=7)123846(0+5=5)7八数码魔方的八数码魔方的A A* *算法搜索树算法搜索树20 第三章第三章 与或图搜索问

10、题与或图搜索问题 主要知识点： 与或图的启发式搜索算法AO* 博弈搜索的极大极小法 -剪枝法。21 第三章第三章 与或图搜索问题与或图搜索问题 启发式搜索算法AO* 过程： 图生成过程，即扩展节点图生成过程，即扩展节点 从最优的局部途中选择一个节点扩展从最优的局部途中选择一个节点扩展 计算耗散值的过程计算耗散值的过程 对当前的局部图重新新计算耗散值对当前的局部图重新新计算耗散值22 第三章第三章 与或图搜索问题与或图搜索问题AO*算法可划分成两个操作阶段：算法可划分成两个操作阶段： 第一阶段是完成第一阶段是完成自顶向下自顶向下的图生成操作的图生成操作,先先通过有标记的连接符，找到目前为止最好通

11、过有标记的连接符，找到目前为止最好的一个局部解图，然后对其中一个非终结的一个局部解图，然后对其中一个非终结点进行扩展，并对其后继结点赋估计耗散点进行扩展，并对其后继结点赋估计耗散值和加能解标记。值和加能解标记。23 第三章第三章 与或图搜索问题与或图搜索问题第二阶段是完成第二阶段是完成自下向上自下向上的耗散值修正计算、的耗散值修正计算、连接符连接符(即指针即指针)的标记以及结点的能解标记。的标记以及结点的能解标记。 耗散值的修正从刚被扩展的结点耗散值的修正从刚被扩展的结点n开始，其开始，其修正耗散值修正耗散值q(n)取估计取估计h(n)的所有值中最小的所有值中最小的一个，然后根据耗散值递归计算

12、公式逐的一个，然后根据耗散值递归计算公式逐级向上修正其先辈结点的耗散值，只有下级向上修正其先辈结点的耗散值，只有下层耗散值修正后，才可能影响上一层结点层耗散值修正后，才可能影响上一层结点的耗散值，因此必须自底向上一直修正到的耗散值，因此必须自底向上一直修正到初始结点。这由算法中的内循环过程完成。初始结点。这由算法中的内循环过程完成。24 25AO*算法举例其中：其中： h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0设：设：K连接符连接符的耗散值为的耗散值为K目标目标目标目标初始节点初始节点n0n1n

13、2n3n4n5n6n7n8 26目标目标目标目标初始节点初始节点n0n1n2n3n4n5n6n7n8n4(1)红色：红色：4黄色：黄色：3初始节点初始节点n0n1(2)n5(1) 27目标目标目标目标初始节点初始节点n0n1n2n3n4n5n6n7n8红色：红色：4黄色：黄色：6n3(4)初始节点初始节点n0n4(1)n5(1)n1n2(4)5 28目标目标目标目标初始节点初始节点n0n1n2n3n4n5n6n7n8红色：红色：5黄色：黄色：6初始节点初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2 29目标目标目标目标初始节点初始节点n0n1n2n3

14、n4n5n6n7n8红色：红色：5黄色：黄色：6初始节点初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)21 第三章第三章 与或图搜索问题与或图搜索问题 对各个局面进行评估对各个局面进行评估 评估的目的：对后面的状态提前进行考虑，并评估的目的：对后面的状态提前进行考虑，并且以各种状态的评估值为基础作出最好的走棋且以各种状态的评估值为基础作出最好的走棋选择。选择。 评估的方法：用评价函数对棋局进行评估。赢评估的方法：用评价函数对棋局进行评估。赢的评估值设为的评估值设为+，输的评估值设为，输的评估值设为-，平局，平局的评估值设为的评估值设为0。 评估的标准：

15、由于下棋的双方是对立的，只能评估的标准：由于下棋的双方是对立的，只能选择其中一方为评估的标准方。选择其中一方为评估的标准方。30 第三章第三章 与或图搜索问题与或图搜索问题 正方（正方（MAX节点）从所有子节点中，选取节点）从所有子节点中，选取具有最大评估值的节点。具有最大评估值的节点。 反方（反方（MIN节点）从其所有子节点中，选取节点）从其所有子节点中，选取具有最小评估值的节点。具有最小评估值的节点。 反复进行这种选取，就可以得到双方各个反复进行这种选取，就可以得到双方各个节点的评估值。这种确定棋步的方法，称节点的评估值。这种确定棋步的方法，称为为极小极大搜索法极小极大搜索法。 31 第三

16、章第三章 与或图搜索问题与或图搜索问题 在九宫格棋盘上，两位选手轮流在棋盘上在九宫格棋盘上，两位选手轮流在棋盘上摆各自的棋子摆各自的棋子( (每次一枚每次一枚) )，谁先取得三线，谁先取得三线的结果就取胜。的结果就取胜。 设程序方设程序方MAXMAX的棋子用的棋子用( () )表示，表示， MAXMAX先先走。对手走。对手MINMIN的棋子用的棋子用( (o o) )表示。表示。32 第三章第三章 与或图搜索问题与或图搜索问题估计函数估计函数 f(p)=(f(p)=(所有空格都放上所有空格都放上MAXMAX的棋子的棋子之后，之后，MAXMAX的三子成线数的三子成线数) )( (所有空格都放所有

17、空格都放上上MINMIN的棋子之后，的棋子之后，MINMIN的三子成线的总数的三子成线的总数) ) 若若P P是是MAXMAX获胜的格局，则获胜的格局，则f(p)=+ f(p)=+ ； 若若P P是是MINMIN获胜的格局，则获胜的格局，则f(p)f(p)- - 。33 估计函数值估计函数值 f(p)=6-4=2估计函数估计函数 f(p)=(f(p)=(所有空格都放上所有空格都放上MAXMAX的棋子之后，的棋子之后，MAXMAX的三子的三子成线成线( (行、列、对角行、列、对角) )数数) )( (所有空格都放上所有空格都放上MINMIN的棋子之后，的棋子之后，MINMIN的三子成线的三子成线

18、( (行、列、对角行、列、对角) )的总数的总数) )当前棋局当前棋局f(p)=2第三章第三章 与或图搜索问题与或图搜索问题34 第三章第三章 与或图搜索问题与或图搜索问题35 - - 剪支法的剪支法的引入引入 在极小极大法中，必须求出所有终端节点在极小极大法中，必须求出所有终端节点的评估值，当预先考虑的棋步比较多时，计的评估值，当预先考虑的棋步比较多时，计算量会大大增加。为了提高搜索的效率，引算量会大大增加。为了提高搜索的效率，引入了通过对评估值的上下限进行估计，从而入了通过对评估值的上下限进行估计，从而减少需进行评估的节点范围的减少需进行评估的节点范围的 - 剪支法。剪支法。第三章第三章

19、与或图搜索问题与或图搜索问题36 作为正方出现的作为正方出现的MAX节点，假设它的节点，假设它的MIN子节点子节点有有N个，那么当它的第一个个，那么当它的第一个MIN子节点的评估值为子节点的评估值为 时，则对于其它的子节点，如果有高过时，则对于其它的子节点，如果有高过 的，就取的，就取那最高的值作为该那最高的值作为该MAX节点的评估值；如果没有，节点的评估值；如果没有，则该则该MAX节点的评估值为节点的评估值为 。 总之，该总之，该MAX节点的评估值不会低于节点的评估值不会低于 ，这个，这个 就称为该就称为该MAX节点的评估下限值。节点的评估下限值。n MAX节点的评估下限值节点的评估下限值

20、第三章第三章 与或图搜索问题与或图搜索问题37 MIN节点的评估上限值节点的评估上限值 作为反方出现的作为反方出现的MIN节点，假设它的节点，假设它的MAX子节点有子节点有N个，那么当它的第一个个，那么当它的第一个MAX子节点的评估值为子节点的评估值为 时，时，则对于其它子节点，如果有低于则对于其它子节点，如果有低于 的，就取那个低于的，就取那个低于 的值作为该的值作为该MIN节点的评估值；如果没有，则该节点的评估值；如果没有，则该MIN节点的评估值取节点的评估值取 。 总之，该总之，该MIN节点的评估值不会高过节点的评估值不会高过 ，这个，这个 就称就称为该为该MIN节点的评估上限值。节点的

21、评估上限值。第三章第三章 与或图搜索问题与或图搜索问题38 剪支法剪支法 MAX节点节点MIN节点节点 = 剪支剪支ABCD 设MAX节点的下限为，则其所有的MIN子节点中，其评估值的上限小于等于的节点，其以下部分的搜索都可以停止了，即对这部分节点进行了剪支。第三章第三章 与或图搜索问题与或图搜索问题39 设设MINMIN节点的上限为节点的上限为 ，则其，则其所有的所有的MAXMAX子节点中，其评估值子节点中，其评估值的的 下限大于等于下限大于等于 的节点，其以下部分的搜索都可以停止了，的节点，其以下部分的搜索都可以停止了，即对这部分节点进行了即对这部分节点进行了 剪支。剪支。MAX节点节点M

22、IN节点节点 = 剪支剪支ABCDn 剪支法剪支法 第三章第三章 与或图搜索问题与或图搜索问题40 MAX节点节点(5, )35652164(6, )(2, )(- ,5,5)(- ,2,2)(5, )MIN节点节点终端节点终端节点 剪支剪支 剪支剪支A B CDEFG H I J K L N O MMAX节点节点第三章第三章 与或图搜索问题与或图搜索问题41 第四章第四章 谓词逻辑与归结原理谓词逻辑与归结原理 主要知识点： 谓词逻辑表示的语言与方法 谓词归结子句形 谓词逻辑归结原理 Herbrand定理42 例：将下式化为Skolem标准形： ( x)( y)P(a, x, y) ( x)(

23、 y)Q(y, b)R(x) 解：第一步，消去解：第一步，消去号，得：号，得： ( x)( y)P(a, x, y) ( x) ( y)Q(y, b)R(x) 第二步，深入到量词内部，得：第二步，深入到量词内部，得： ( x)( y)P(a, x, y) ( x)x) ( y)Q(y, b)R(x) 第三步，变元易名，得第三步，变元易名，得( x)( y)P(a, x, y) ( u) ( v)(Q(v, b) R(u) 第四步，存在量词左移，直至所有的量词移到前面，第四步，存在量词左移，直至所有的量词移到前面，( x) ( y) ( u) ( v) (P(a, x, y) (Q(v, b)

24、R(u)由此得到前述范式由此得到前述范式43 第五步，消去第五步，消去“ ”（存在量词），略去（存在量词），略去“ ”全全称量词称量词 消去消去( y)，因为它左边只有，因为它左边只有( x)，所以使用，所以使用x的函的函数数f(x)代替之，这样得到：代替之，这样得到：( x)( u)( v) (P(a, x, f(x) Q(v, b)R(u) 消去消去( u)，同理使用，同理使用g(x)代替之，这样得到：代替之，这样得到：( x) ( v) ( P(a, x, f(x) Q(v, b) R(g(x) 则，略去全称变量，原式的则，略去全称变量，原式的Skolem标准形为：标准形为： P(a,

25、x, f(x) Q(v, b) R(g(x) 44 例题例题“快乐学生快乐学生”问题问题 假设假设任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有的考试，张不肯学习但他是幸运的，任何幸运的的人都可以通过所有的考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的人都能获奖。求证：张是快乐的。 证明：证明：先将问题用谓词表示如下先将问题用谓词表示如下：R1:“任何通过计算机考试并获奖的人都是快乐的任何通过计算机考试并获奖的人都是快乐的”( x)(Pass(x, computer)Win(x, priz

26、e)Happy(x)R2:“任何肯学习或幸运的人都可以通过所有考试任何肯学习或幸运的人都可以通过所有考试”( x)( y)(Study(x)Lucky(x)Pass(x, y)R3:“张不肯学习但他是幸运的张不肯学习但他是幸运的”Study(zhang)Lucky(zhang)R4:“任何幸运的人都能获奖任何幸运的人都能获奖”( x)(Luck(x)Win(x,prize)结论：结论：“张是快乐的张是快乐的”的否定的否定Happy(zhang)45 由由R1及逻辑转换公式及逻辑转换公式:PWH = （PW） H ，可得，可得 (1)Pass(x, computer)Win(x, prize)H

27、appy(x)由由R2： (2)Study(y)Pass(y,z) (3)Lucky(u)Pass(u,v)由由R3： (4)Study(zhang) (5)Lucky(zhang)由由R4： (6)Lucky(w)Win(w，prize)由结论：由结论：(7)Happy(zhang)（结论的否定）（结论的否定）(8)Pass(w, computer)Happy(w)Luck(w) (1)(6)，w/x(9)Pass(zhang, computer)Lucky(zhang) (8)(7)，zhang/w(10) Pass(zhang, computer) (9)(5)(11) Lucky(zh

28、ang) (10)(3)，zhang/u, computer/v(12) (11)(5) 46 例例 设已知：设已知： (1)(1)能阅读者是识字的；能阅读者是识字的； (2)(2)海豚不识字；海豚不识字； (3)(3)有些海豚是很聪明的。有些海豚是很聪明的。试证明：有些聪明者并不能阅读。试证明：有些聪明者并不能阅读。 证证 首先，定义如下谓词：首先，定义如下谓词： R R( (x x) )：x x能阅读。能阅读。 L L( (x x) )：x x识字。识字。 I I( (x x) )：x x是聪明的。是聪明的。 D D( (x x) )：x x是海豚。是海豚。 47 然后把上述各语句翻译为谓

29、词公式：然后把上述各语句翻译为谓词公式：(1) x(R(x)L(x)(1) x(R(x)L(x)(2) x(D(x) (2) x(D(x) L(x) L(x) 已知条件已知条件(3) x(D(x)I(x)(3) x(D(x)I(x)(4) x(I(x)(4) x(I(x)R(x) R(x) 需证结论需证结论 48 求题设与结论否定的子句集，得求题设与结论否定的子句集，得(1)(1) R(x)L(x) R(x)L(x)(2)(2) D(y) D(y) L(y) L(y)(3)D(a)(3)D(a)(4)I(a)(4)I(a)(5)(5) I(z)R(z) I(z)R(z)49 第五章第五章 知识

30、表示知识表示 主要知识点主要知识点：产生式规则表示法语义网络表示法框架表示法50 表示方法产生式规则表示法 产生式系统基本结构推理机数据库规则库知识库产生式系统结构图 51 表示方法产生式规则表示法 正向推理方法：从已知事实出发，逐步推导出最后结论。 其推理过程大致是： 用工作存储器中的事实与产生式规则的前提条件进行匹配。 按冲突消解策略从匹配的规则中选择一条规则。 执行选中规则的动作（依次）。修改工作存储器。 用更新后的工作存储器，重复上述工作，直到得出结论或工作存储器不再发生变化为止。52 表示方法产生式规则表示法 反向推理方法：首先提出假设，然后验证这些假设的真假性，找到假设成立的所有证

31、据或事实。 其推理过程大致是： 看假设是否存在于工作存储器中，若在，则假设成立，推理结束。 找出结论与此假设匹配的规则。 按冲突消解策略从匹配的规则实例中选择一条规则。 将选中的规则的前提条件作为新的假设，重复上述工作，直到假设的真假性被验证或不存在激活的规则。53 表示方法产生式规则表示法 优点 模块性。规则与规则之间相互独立 灵活性。知识库易于增加、修改、删除 自然性。方便地表示专家的启发性知识与经验 透明性。易于保留动作所产生的变化、轨迹54 表示方法产生式规则表示法 缺点： 知识库维护难。 效率低。为了模块一致性。 理解难。由于规则一致性彼此之间不能调用。55 表示方法语义网络表示法

32、表示形式 每一个要表达的事实用一个“结点”表示，而事实之间的关系用“弧线”表示。即，有向图表示的三元组，（结点1， 弧，结点2）连接而成。56 张三职员李四四肢手动物人类老板办公用品桌子isaakoakomanage-ofisaownsakohas-partakoako57 表示方法语义网络表示法推理方法 网络匹配：结构上的匹配，包括结点和弧的匹配 继承推理：利用如：成员联系、特征联系、相互作用联系、集合联系、合成联系、因果联系、活动方式联式、活动目标联系、蕴含联系等具有继承性质的语义联系建立一些并不一定显示存在于网络知识库中的网络结构。 语义网络上的推理：网络上的搜索过程，正向、逆向、双向。

33、58 表示方法语义网络表示法 特点：语义网络图的好处是直观、清晰缺点是表达范围有限。如，一旦有十个结点，而且各结点之间又有联系，则这个网络就很难辨请了。 59 表示方法框架表示法 定义 框架是由若干个结点和关系（统称为槽）构成的网络。是语义网络的一般化形式的一种结构。同语义网络没有本质的区别。如书上的所示如将语音网络结点间弧上的标注也放到槽内就成了框架表示形式。 表示形式： 由框架名、槽名、侧面、值组成 推理方法： 没有固定的推理机理。但和语义网络一样遵循匹配和继承的原理。 60 表示方法框架表示法简单框架的例子：MichealGender：manProfession:singerHeight

34、:185cmWeight: 79kgAge:2761 表示方法框架表示法 框架之间的关系框架也分为类框架和实例框架。通过引入类-超类（AKO）及实例-类（ISA）关系来表示框架之间的包含关系和属于关系。框架理论将知识看成相互关系的成块组织。 推理方法： 匹配：和语义网络一样遵循匹配原理。 槽计算：继承（属性值、属性、限制）， 附加过程，即附加在数据结构上，启动时 计算槽值。62 表示方法混合型知识表示法 上述的知识表示虽各有特点，而且适用的领域也不同。如： 谓词逻辑方法只适用于确定性、陈述性、静态性知识，而对动态的、变化性、模糊性知识则很难表示。 产生式规则方法推理方法太单一，如果前提条件太多

35、，或规则条数太多，则推理的速度将慢得惊人。 语义网络方法表达的知识面比较窄。 框架方法表示的知识横向关系不太明确。（纵向从属继承关系很明确） 对于复杂的、深层次的知识，就很难用一种知识表示来解决问题。63 第第6章章 机器学习机器学习 主要知识点：主要知识点：实例学习实例学习基于解释的学习基于解释的学习决策树学习决策树学习神经网络学习神经网络学习64 机器学习 概述 机器学习模型 学习是建立理论、形成假设和进行归纳推理的过程。 整个过程包括：信息的存储、知识的处理两部分 环境学习环节知识库 执行环节65 实例学习 50年代兴起的实例学习是归纳学习的一种。目前实例学习在某些系统中的应用已成为机器

36、学习走向实践的先导。 环境提供给系统一些特殊的实例，这些实例事先由施教者划分为正例和反例。实例学习系统由此进行归纳推理得到一般规则。 环境提供给学习环节的正例和反例是低水平的信息，这是特殊情况下执行环节的行为。学习环节归纳出的规则是高水平的信息，可以在一般情况下用这些规则指导执行环节的工作。66 实例学习 解释例子 解释例子的目的是从例子中提出用于搜索空间的信息。把示教例子变换成易于进行符号归纳的形式。 例如：Winston的积木世界中的“拱”的概念。BCA67 温斯顿拱概念的学习中，示例分为两种：温斯顿拱概念的学习中，示例分为两种： 一是适合于拱概念的例子，称为正例；一是适合于拱概念的例子，

37、称为正例； 另一种是相反的例子，称为反例。另一种是相反的例子，称为反例。正例正例反例反例68 2. 2. 根据逐次展开的示例生成归纳模型根据逐次展开的示例生成归纳模型从第一个正例，从第一个正例，可学习到原始拱可学习到原始拱的初始模型，至的初始模型，至于哪个节点或连于哪个节点或连线具有本质意义线具有本质意义呢，从第一个例呢，从第一个例子中还看不出来。子中还看不出来。第一个正例第一个正例支撑支撑支撑支撑在左面在左面学到的模型学到的模型69 学完第二个负学完第二个负例后，再对第例后，再对第一个正例建立一个正例建立的模型进行增的模型进行增强，得到强，得到一定要一定要支撑支撑一定要一定要支撑支撑在左面在

38、左面增强的模型增强的模型70 第三个负例及其语义网络第三个负例及其语义网络第三个负例第三个负例支撑支撑支撑支撑在左面在左面接触接触语义网络表示语义网络表示71 第三个负例学完第三个负例学完后，对正例模型后，对正例模型再进行增强，得再进行增强，得到到一定要一定要支撑支撑一定要一定要支撑支撑在左面在左面一定不要接触一定不要接触72 最后，再对第四个正例进行学习最后，再对第四个正例进行学习第四个正例第四个正例支撑支撑支撑支撑在左面在左面语义网络表示语义网络表示73 得到增强得到增强的模型的模型一定要一定要支撑支撑一定要一定要支撑支撑在左面在左面一定不要接触一定不要接触表示不限定积木的形状表示不限定积

39、木的形状四个例子学完后的模型四个例子学完后的模型74 对上述四个例子的学习总结，可得到对上述四个例子的学习总结，可得到如果现有模型中存在的连线在反例中不存如果现有模型中存在的连线在反例中不存在，如在，如“支撑支撑”连线在第二个反例中不存连线在第二个反例中不存在，那么需要将该连线增强为在，那么需要将该连线增强为“一定要支一定要支撑撑”。如果现有模型中不存在的连线在反例中出如果现有模型中不存在的连线在反例中出现了，则该连线应增强为现了，则该连线应增强为“一定不要出一定不要出现现”。如第三个反例中的。如第三个反例中的“接触接触”连线，连线，在正模型中则变为在正模型中则变为“一定不要接触一定不要接触”

40、。75 现有模型与新的正例的对应节点不属于同一现有模型与新的正例的对应节点不属于同一种物体时，则找出它们共同的上层节点，来种物体时，则找出它们共同的上层节点，来替换原有模型的对应节点。替换原有模型的对应节点。 如果它们没有共同的上层节点，则新设一个如果它们没有共同的上层节点，则新设一个类别来表示这两个节点的属类别之和。类别来表示这两个节点的属类别之和。 现有模型中的连线在新的正例中不存在，则现有模型中的连线在新的正例中不存在，则将其删除。将其删除。76 基于解释的学习(简介)解释空间的描述 概念空间：某个学习程序能描述的所有概念的集合，其中每一点对应例子空间的唯一的一个子集合。例：C1对应I1

41、，I2，I3。但概念空间的一个点可以对应概念描述空间的多个点。例：C1对应不可操作的D1和可操作的D2。对应同一概念的两个描述称为同义词。 解释学习的任务：把不可操作的描述转化为可操作的描述。例：D1是搜索的开始结点，D2是解结点，解释是空间的变换，而可操作性是搜索结束的标准。从D1到D2的过程称作概念可操作。77 EXL概念描述概念描述的转换的转换KBPS结果是否结果是否 可操作可操作D1D2NY解释学习的框架78 基于解释的学习(简介)解释学习的模型 执行系统：PS 学习系统：EXL 领域知识库：KB(不同描述间转换的集合)系统工作过程 EXL输入概念C1的描述D1（一般是不可操作的） 根

42、据KB中的知识，对其进行不同的转换（搜索） PS对每个转换结果进行测试，直至转换结果是PS可以接受的描述D2（可操作的）时，学习结束，输出D279 基于解释的学习(简介) 一般框架： 给定：领域知识、目标概念、训练实例和操作性准则。 领域知识：描述领域的事实和规则，背景知识，用来证明训练实例为什么可作为目标概念的实例。 训练实例：为了解释学习提供的一个例子，解释学习正是从该例出发，通过运用领域知识进行证明，最终推广出目标概念的描述。 操作性准则：用于指明哪些测试在运行时容易判定，指导系统对描述目标的概念进行取舍。 找出：满足操作性准则的关于概念的充分条件80 决策树的学习决策树的学习 如果学习

43、的任务是对一个大的例子集作分如果学习的任务是对一个大的例子集作分类概念的归纳定义，而这些例子又都是用类概念的归纳定义，而这些例子又都是用一些无结构的属性值对来表示，则可以采一些无结构的属性值对来表示，则可以采用示例学习方法的一个变种用示例学习方法的一个变种决策树学习，决策树学习，其代表性的算法是昆兰（其代表性的算法是昆兰（J.R.Quinlan，1986）提出的）提出的ID3。81 决策树(Decision Tree) 一种描述概念空间的有效的归纳推理办法。基于决策树的学习方法可以进行不相关的多概念学习，具有简单快捷的优势，已经在各个领域取得广泛应用。82 基于决策树的概念表示基于决策树的概念

44、表示决策树是一种树型结构，其中每个决策树是一种树型结构，其中每个内部结点表示在一个属性上的测试，内部结点表示在一个属性上的测试，每个分支代表一个测试输出，每个每个分支代表一个测试输出，每个叶结点代表一种类别。叶结点代表一种类别。83 如，白化体动物的如，白化体动物的8个样本集合：个样本集合：事例事例动物种类动物种类身体颜色身体颜色眼睛颜色眼睛颜色白化体白化体1兔兔棕棕黑黑负负2兔兔白白红红正正3兔兔灰灰红红负负4兔兔白白红红正正5象象白白黑黑负负6象象白白红红正正7象象灰灰红红负负8象象灰灰黑黑负负84 CLSCLS算法得出的决策树为：算法得出的决策树为：动物种类动物种类兔兔象象身体的颜色身体

45、的颜色眼睛的颜色眼睛的颜色 棕棕 灰灰白白+ 红红黑黑身体的颜色身体的颜色眼睛的颜色眼睛的颜色 棕棕 灰灰白白+ 红红黑黑85 根据信息量标准选择分类属性根据信息量标准选择分类属性 ID3对对CLS的改进主要体现在两方面：的改进主要体现在两方面：增加了窗口技术；增加了窗口技术；使用信息增量的方法来选择节点上的测试属性。使用信息增量的方法来选择节点上的测试属性。 采用训练实例的子集采用训练实例的子集(即，可选择窗口即，可选择窗口)，通，通过属性，使用熵概念，来形成决策树。实过属性，使用熵概念，来形成决策树。实质是构造一株熵值下降平均最快的判定树。质是构造一株熵值下降平均最快的判定树。86 信息熵

46、的定义信息熵的定义 香农定义信息熵为，表征了信源整体的统香农定义信息熵为，表征了信源整体的统计特征的一个量。即总体的平均不确定性计特征的一个量。即总体的平均不确定性的量度。对某一特定的信源，其信息熵只的量度。对某一特定的信源，其信息熵只有一个，因统计特性不同，其熵也不同。有一个，因统计特性不同，其熵也不同。 信息熵表征了变量信息熵表征了变量X的随机性。如信息熵大，的随机性。如信息熵大，表明表明X随机性大；而信息熵小，变量随机性大；而信息熵小，变量X的随的随机性就小。因此，熵反映了变量的随机性，机性就小。因此，熵反映了变量的随机性，也是表征随机变量统计特性的一个特征参也是表征随机变量统计特性的一

47、个特征参数。数。 87 样本集的信息熵样本集的信息熵 设样本数据集为：设样本数据集为： X=x1,x2,xn 记记X的两个训练子集的两个训练子集P+X和和P-X分别为正例集和分别为正例集和反例集，其中反例集，其中P+和和P-分别为两个集合的概率，则分别为两个集合的概率，则样本空间的信息熵为：样本空间的信息熵为： PPPPH220loglog88 样本集属性样本集属性F的信息熵的信息熵 假设样本集假设样本集X有属性有属性F，其属性值集合为，其属性值集合为v1,v2,vn，它将，它将X划分为划分为n个子集。假设第个子集。假设第i个个子集中包含子集中包含Ni+个正例，个正例，Ni-个反例，则该子集的

48、个反例，则该子集的信息熵为：信息熵为： iiiiiivFNNNNNNHi2logiiiiiiNNNNNN2log89 样本集属性样本集属性F的信息熵的信息熵 因此，针对样本集的属性因此，针对样本集的属性F，其各个取值的信息，其各个取值的信息熵为熵为(其其pi为为F=vi的概率，的概率，N为样本总数为样本总数)： ivFniiFHpH1niiiiiiiiiNNNNNNNNN122loglog1iiiiiiniiiNNNNNNNNN21logiiiiiiNNNNNN2log90 因此，以属性因此，以属性F为根节点的样本集合信息增量是：为根节点的样本集合信息增量是： 由于样本集的信息熵由于样本集的信

49、息熵H0是不可改变的，所以当属是不可改变的，所以当属性性F的信息熵取的信息熵取HF最小时，获得的信息增量最大。最小时，获得的信息增量最大。即选择使即选择使HF最小的属性最小的属性F，做为决策树的分叉节，做为决策树的分叉节点。点。 FFHHgain0决策树分类节点的选取决策树分类节点的选取91 例如，白化体样本集的分类例如，白化体样本集的分类 根据具体的样本集合，计算其在各属性下根据具体的样本集合，计算其在各属性下的信息熵：的信息熵： 象种兔种种HHH848443log341log142log242log2812222906. 092 灰体白体棕体体HHHH83848130log033log34

50、1log143log310log011log181222222406. 093 红眼黑眼眼HHH858352log253log330log033log3812222607. 094 从上述计算中发现，从上述计算中发现， 因此选身体的颜色这个属性来进行分类，其信息增因此选身体的颜色这个属性来进行分类，其信息增量为最大。量为最大。 由于身体颜色这个属性中，仍有分枝存在正负例混由于身体颜色这个属性中，仍有分枝存在正负例混杂的情况，需要对其继续进行分类。杂的情况，需要对其继续进行分类。种眼体HHH95 分别计算四个身体颜色为白的分枝下，种分别计算四个身体颜色为白的分枝下，种类和眼睛颜色属性的信息熵：类