《史忠植高级人工智能》由会员分享，可在线阅读，更多相关《史忠植高级人工智能（43页珍藏版）》请在金锄头文库上搜索。
1、2017/8/5,史忠植 高级人工智能,1,第六章 归纳学习,史忠植 中科院计算所,2017/8/5,史忠植 高级人工智能,2,内容提要,6.1 归纳学习的逻辑基础6.2 偏置变换6.3 变型空间方法6.4 AQ归纳学习算法6.5 产生与测试方法6.6 决策树学习6.7 归纳学习的计算理论6.8 支持下向量机,2017/8/5,史忠植 高级人工智能,3,概述,给定关于某个概念的一系列已知的正例和反例，其任务是从中归纳出一个一般的概念描述。归纳学习能够获得新的概念，创立新的规则，发现新的理论。 泛化(generalization)用来扩展一假设的语义信息，以使其能够包含更多的正例，应用于更多的情
2、况。 特化(specialization)是泛化的相反的操作，用于限制概念描述的应用范围。,2017/8/5,史忠植 高级人工智能,4,归纳学习的一般模式,给定: 观察语句集(事实)F：这是有关某类对象中个别具体对象的知识或某一对象的部分特征的知识。 假定的初始归纳断言(可空)：是关于目标的泛化项或泛化描述。 背景知识：背景知识定义了在观察语句和所产生的候选归纳断言上的假定和限制，以及任何有关问题领域知识。有关问题领域知识包括特化所找归纳断言的期望性质的择优标准。寻找: 归纳断言H(hypothesis), H 重言或弱蕴涵观察语句并满足背景知识。,2017/8/5,史忠植 高级人工智能,5,
3、概述,2017/8/5,史忠植 高级人工智能,6,概述,变型空间AQ11算法决策树方法ID3,2017/8/5,史忠植 高级人工智能,7,基本符号表, 非 &合取（逻辑乘） 析取（逻辑加） 蕴涵 逻辑等价 项重写 异或 F事实集 H 假设 | 特化 | 将概念描述与概念名连接的蕴涵 ei 一个事件（对一种情况的描述）Ei 仅对概念ki的事件为真的谓词Xi 属性 LEF 评价函数 DOM(P) 描述符P的定义域,2017/8/5,史忠植 高级人工智能,9,概念获取,概念获取的一类特殊情况，它的观察语句集F是一个蕴涵的集合, 其形式如下：F: eik : Ki i I 其中，eik(Ki的训练事件
4、)是概念Ki的第k个例子的符号描述。概念的谓词Ki, I是Ki的下标集合。 eik : Ki的含义是“凡符合描述eik的事件均可被断言为概念Ki的例子。,2017/8/5,史忠植 高级人工智能,10,概念获取,学习程序要寻求的归纳断言H可以用概念识别规则集来刻画, 形式如下： H:Di : Ki i I 其中Di是概念Ki的描述，即表达式Di是事件的逻辑推论，该事件可被断言为概念Ki的一个例子。,2017/8/5,史忠植 高级人工智能,11,完整性条件, i I (Ei Di),2017/8/5,史忠植 高级人工智能,12,一致性条件, i,j I (Di Ej), 若 i j,2017/8/
5、5,史忠植 高级人工智能,13,描述符类型,(1) 名称性描述符。这种描述符的定义域由独立的符号或名字组成，即值集中值之间没有结构关系。例如水果、人名等。 (2) 线性描述符。该类描述符值集中的元素是一个全序集。例如，资金、温度、重量、产量等都是线性描述符。表示序数、区间、比率和绝对标度的变量都是线性描述符的特例。将一个集合映射成一个完全有序集的函数也是线性描述符。,2017/8/5,史忠植 高级人工智能,14,描述符类型,(3) 结构描述符。其值集是一个树形的图结构，反映值之间的生成层次。 在这样的结构中，父节点表示比子节点更一般的概念。例如，在“地名”的值集中，“中国”是节点“北京”、“上
6、海”、“江苏”、“广东”等的父节点。 结构描述符的定义域是通过问题背景知识说明的一组推理规则来定义的。结构描述符也能进一步细分为有序和无序的结构描述符。描述符的类型对确定应用描述符的操作是很重要的。,2017/8/5,史忠植 高级人工智能,15,选择型泛化规则,(1) 消除条件规则 CTX & S : K | K 其中S是任意的谓词或逻辑表达式。 (2) 增加选择项规则 CTX1 : K | K通过增加选择项将概念描述泛化,2017/8/5,史忠植 高级人工智能,16,选择型泛化规则,(3) 扩大引用范围规则CTX & L = R1 : K | K其中R1 R2 DOM(L), DOM(L)
7、为L的域，L是一个项，Ri是L取值的一个集合。 (4) 闭区间规则 CTX & L = a : K CTX & L = b : K | K,2017/8/5,史忠植 高级人工智能,17,选择型泛化规则,(5) 爬山泛化树规则 CTX & L = a : K CTX & L = b : K CTX & L = i : K | K 其中L是结构描述符，在L的泛化树域中，S表示后继为a,b, i的最低的父节点。,2017/8/5,史忠植 高级人工智能,18,选择型泛化规则,(6) 将常量转换为变量规则 Fa Fb Fi | K | K 其中F1,F2为任意描述。,2017/8/5,史忠植 高级人工智
8、能,20,选择型泛化规则,(8) 扩充量词范围规则 x,Fx : k | k (I1)x,Fx : K | K其中I1,I2是量词的域（整数集合），且I1 I2,2017/8/5,史忠植 高级人工智能,21,选择型泛化规则,(9) 泛化分解规则 用于概念获取 P & F1 : K P & F2 : K | K 用于描述泛化 P & F1 P & F2 | K CTX2 & L = R2 : K | K 其中R1,R2是析取式。,2017/8/5,史忠植 高级人工智能,23,构造型泛化规则,构造性泛化规则能生成一些归纳断言，这些归纳断言使用的描述符不出现在初始的观察陈述中，也就是说，这些规则对初
9、始表示空间进行了变换。(1) 通用构造型规则 CTX & F1 : K F1 F2 | K 该规则表示，若一个概念描述含有一部分F1, 已知F1蕴涵另一概念F2,则通过用F2替代F1可得到一个更一般的描述。,2017/8/5,史忠植 高级人工智能,24,构造型泛化规则,(2) 计算变量规则。计算量词变量CQ规则: V1,V2, ,Vk FV1,V2, ,VkCQ规则将产生一个新的描述符“#v-COND”, 表示满足某条件COND的vi的个数。,2017/8/5,史忠植 高级人工智能,25,构造型泛化规则,(3) 产生链属性规则。概念描述中，若一个概念描述中传递关系不同出现的变量形成一条链,该规
10、则能生成刻画链中某些特定对象的特征的描述符。这种对象可能是：LST-对象： “最小的对象”，或链的开始对象。MST-对象： 链的结束对象。MID-对象： 链中间的对象。Nth-对象： 链中第N个位置上的对象。(4) 检测描述符之间的相互依靠关系规则。,2017/8/5,史忠植 高级人工智能,26,偏置变换,偏置在概念学习中具有重要作用。所谓偏置，是指概念学习中除了正、反例子外，影响假设选择的所有因素。这些因素包括： 描述假设的语言。 程序考虑假设的空间。 按什么顺序假设的过程。 承认定义的准则，即研究过程带有已知假设可以终止还是应该继续挑选一个更好的假设。采用偏置方法，学习部分选择不同的假设，
11、会导致不同的归纳跳跃。,2017/8/5,史忠植 高级人工智能,27,偏置变换,偏置有两个特点： (1) 强偏置是把概念学习集中于相对少量的假设；反之，弱偏置允许概念学习考虑相对大量的假设。 (2) 正确偏置允许概念学习选择目标概念，不正确偏置就不能选择目标概念。,2017/8/5,史忠植 高级人工智能,28,偏置变换,程序,训练集,搜索程序,知识,偏置,训练例,假设,2017/8/5,史忠植 高级人工智能,29,变型空间,变型空间(Version Space)方法以整个规则空间为初始的假设规则集合H。依据训练例子中的信息，它对集合 H进行泛化或特化处理，逐步缩小集合 H。最后使 H收敛为只含
12、有要求的规则。由于被搜索的空间 H逐步缩小，故称为变型空间。,2017/8/5,史忠植 高级人工智能,30,变型空间,变型空间方法的初始 G集是最上面的一个点（最一般的概念），初始 S集是最下面的直线上的点（训练正例），初始 H集是整个规则空间。在搜索过程中，G 集逐步下移（进行特化），S 集逐步上移（进行泛化），H 逐步缩小。最后 H收敛为只含一个要求的概念。,2017/8/5,史忠植 高级人工智能,31,初始变型空间,2017/8/5,史忠植 高级人工智能,32,第一个训练实例(sm cir),2017/8/5,史忠植 高级人工智能,33,第二个训练实例(lg,tri),2017/8/5,
13、史忠植 高级人工智能,34,第三个训练实例(lg cir),2017/8/5,史忠植 高级人工智能,35,消除候选元素算法,(1) 正规的初始 H集是整个规则空间，这时 S包含所有可能的训练正例（最特殊的概念）。这时 S集规模太大。实际算法的初始 S集只包含第一个训练正例, 这种 H就不是全空间了。 (2) 接收一个新的训练例子。如果是正例，则首先由 G中去掉不覆盖新正例的概念，然后修改 S为由新正例和 S原有元素共同归纳出的最特殊的结果（这就是尽量少修改 S，但要求 S覆盖新正例）。如果这是反例，则首先由 S中去掉覆盖该反例的概念，然后修改 G为由新反例和 G原有元素共同作特殊化的最一般的结果（这就是尽量少修改 G，但要求 G不覆盖新反例）。,
