AAI06归纳学习----高级人工智能-史忠植课件

第六章 归纳学习 中科院计算所5/4/20241史忠植 高级人工智能内容提要6.1 归纳学习的逻辑基础6.2 偏置变换6.3 变型空间方法6.4 AQ归纳学习算法6.5 产生与测试方法6.6 决策树学习6.7 归纳学习的计算理论6.8 支持下向量机5/4/20242史忠植 高级人工智能 概述概述 给定关于某个概念的一系列已知的正例和反例，其任务是从中归纳出一个一般的概念描述。归纳学习能够获得新的概念，创立新的规则，发现新的理论。泛化(generalization)用来扩展一假设的语义信息，以使其能够包含更多的正例，应用于更多的情况。特化(specialization)是泛化的相反的操作，用于限制概念描述的应用范围。5/4/20243史忠植 高级人工智能归纳学习的一般模式给定:观察语句集(事实)F：这是有关某类对象中个别具体对象的知识或某一对象的部分特征的知识。假定的初始归纳断言(可空)：是关于目标的泛化项或泛化描述。背景知识：背景知识定义了在观察语句和所产生的候选归纳断言上的假定和限制，以及任何有关问题领域知识。有关问题领域知识包括特化所找归纳断言的期望性质的择优标准。寻找:归纳断言H(hypothesis),H 重言或弱蕴涵观察语句并满足背景知识。5/4/20244史忠植 高级人工智能概述概述5/4/20245史忠植 高级人工智能 概述概述变型空间变型空间AQ11AQ11算法算法决策树方法决策树方法ID3ID35/4/20246史忠植 高级人工智能基本符号表基本符号表 非&合取（逻辑乘）析取（逻辑加）蕴涵 逻辑等价 项重写 异或 F事实集 H 假设|特化|将概念描述与概念名连接的蕴涵 ei 一个事件（对一种情况的描述）Ei 仅对概念ki的事件为真的谓词Xi 属性 LEF 评价函数 DOM(P)描述符P的定义域5/4/20248史忠植 高级人工智能概念获取概念获取概念获取的一类特殊情况，它的观察语句集F是一个蕴涵的集合,其形式如下：F:eik:Ki i I 其中，eik(Ki的训练事件)是概念Ki的第k个例子的符号描述。概念的谓词Ki,I是Ki的下标集合。eik:Ki的含义是“凡符合描述eik的事件均可被断言为概念Ki的例子。5/4/20249史忠植 高级人工智能概念获取概念获取学习程序要寻求的归纳断言H可以用概念识别规则集来刻画,形式如下：H:Di:Ki i I 其中Di是概念Ki的描述，即表达式Di是事件的逻辑推论，该事件可被断言为概念Ki的一个例子。5/4/202410史忠植 高级人工智能完整性条件完整性条件 i I (Ei Di)5/4/202411史忠植 高级人工智能一致性条件一致性条件 i,j I (Di Ej),若 i j5/4/202412史忠植 高级人工智能描述符类型描述符类型(1)名称性描述符。这种描述符的定义域由独立的符号或名字组成，即值集中值之间没有结构关系。例如水果、人名等。(2)线性描述符。该类描述符值集中的元素是一个全序集。例如，资金、温度、重量、产量等都是线性描述符。表示序数、区间、比率和绝对标度的变量都是线性描述符的特例。将一个集合映射成一个完全有序集的函数也是线性描述符。5/4/202413史忠植 高级人工智能描述符类型描述符类型 (3)结构描述符。其值集是一个树形的图结构，反映值之间的生成层次。在这样的结构中，父节点表示比子节点更一般的概念。例如，在“地名”的值集中，“中国”是节点“北京”、“上海”、“江苏”、“广东”等的父节点。结构描述符的定义域是通过问题背景知识说明的一组推理规则来定义的。结构描述符也能进一步细分为有序和无序的结构描述符。描述符的类型对确定应用描述符的操作是很重要的。5/4/202414史忠植 高级人工智能选择型泛化规则选择型泛化规则 (1)消除条件规则 CTX&S:K|K 其中S是任意的谓词或逻辑表达式。(2)增加选择项规则 CTX1:K|K通过增加选择项将概念描述泛化5/4/202415史忠植 高级人工智能选择型泛化规则选择型泛化规则 (3)扩大引用范围规则CTX&L=R1 :K|K其中R1 R2 DOM(L),DOM(L)为L的域，L是一个项，Ri是L取值的一个集合。(4)闭区间规则 CTX&L=a:K CTX&L=b:K|K5/4/202416史忠植 高级人工智能选择型泛化规则选择型泛化规则 (5)爬山泛化树规则 CTX&L=a:K CTX&L=b:K CTX&L=i:K|K 其中L是结构描述符，在L的泛化树域中，S表示后继为a,b,i的最低的父节点。5/4/202417史忠植 高级人工智能选择型泛化规则选择型泛化规则 (6)将常量转换为变量规则 Fa Fb Fi|K|K 其中F1,F2为任意描述。5/4/202419史忠植 高级人工智能选择型泛化规则选择型泛化规则 (8)扩充量词范围规则 x,Fx:k|k (I1)x,Fx:K|K其中I1,I2是量词的域（整数集合），且I1 I25/4/202420史忠植 高级人工智能选择型泛化规则选择型泛化规则 (9)泛化分解规则 用于概念获取 P&F1:K P&F2:K|K 用于描述泛化 P&F1 P&F2|K CTX2&L=R2:K|K 其中R1,R2是析取式。5/4/202422史忠植 高级人工智能构造型泛化规则构造型泛化规则构造性泛化规则能生成一些归纳断言，这些归纳断言使用的描述符不出现在初始的观察陈述中，也就是说，这些规则对初始表示空间进行了变换。(1)通用构造型规则 CTX&F1:K F1 F2|K 该规则表示，若一个概念描述含有一部分F1,已知F1蕴涵另一概念F2,则通过用F2替代F1可得到一个更一般的描述。5/4/202423史忠植 高级人工智能构造型泛化规则构造型泛化规则(2)计算变量规则。计算量词变量CQ规则:V1,V2,Vk FV1,V2,VkCQ规则将产生一个新的描述符“#v-COND”,表示满足某条件COND的vi的个数。5/4/202424史忠植 高级人工智能构造型泛化规则构造型泛化规则(3)产生链属性规则。概念描述中，若一个概念描述中传递关系不同出现的变量形成一条链,该规则能生成刻画链中某些特定对象的特征的描述符。这种对象可能是：LST-对象：“最小的对象”，或链的开始对象。MST-对象：链的结束对象。MID-对象：链中间的对象。Nth-对象：链中第N个位置上的对象。(4)检测描述符之间的相互依靠关系规则。5/4/202425史忠植 高级人工智能偏置变换偏置变换偏置在概念学习中具有重要作用。所谓偏置，是指概念学习中除了正、反例子外，影响假设选择的所有因素。这些因素包括：描述假设的语言。程序考虑假设的空间。按什么顺序假设的过程。承认定义的准则，即研究过程带有已知假设可以终止还是应该继续挑选一个更好的假设。采用偏置方法，学习部分选择不同的假设，会导致不同的归纳跳跃。5/4/202426史忠植 高级人工智能偏置变换偏置变换偏置有两个特点：(1)强偏置是把概念学习集中于相对少量的假设；反之，弱偏置允许概念学习考虑相对大量的假设。(2)正确偏置允许概念学习选择目标概念，不正确偏置就不能选择目标概念。5/4/202427史忠植 高级人工智能偏置变换偏置变换程序训练集搜索程序知识偏置训练例假设5/4/202428史忠植 高级人工智能变型空间变型空间变型空间(Version Space)方法以整个规则空间为初始的假设规则集合H。依据训练例子中的信息，它对集合 H进行泛化或特化处理，逐步缩小集合 H。最后使 H收敛为只含有要求的规则。由于被搜索的空间 H逐步缩小，故称为变型空间。5/4/202429史忠植 高级人工智能变型空间变型空间没有描述训练例子GS更特殊更一般变型空间方法的初始 G集是最上面的一个点（最一般的概念），初始 S集是最下面的直线上的点（训练正例），初始 H集是整个规则空间。在搜索过程中，G 集逐步下移（进行特化），S 集逐步上移（进行泛化），H 逐步缩小。最后 H收敛为只含一个要求的概念。5/4/202430史忠植 高级人工智能初始变型空间初始变型空间5/4/202431史忠植 高级人工智能第一个训练实例第一个训练实例(sm cir)(sm cir)5/4/202432史忠植 高级人工智能第二个训练实例第二个训练实例(lg,tri)(lg,tri)5/4/202433史忠植 高级人工智能第三个训练实例第三个训练实例(lg cir)(lg cir)5/4/202434史忠植 高级人工智能消除候选元素算法消除候选元素算法 (1)正规的初始 H集是整个规则空间，这时 S包含所有可能的训练正例（最特殊的概念）。这时 S集规模太大。实际算法的初始 S集只包含第一个训练正例,这种 H就不是全空间了。(2)接收一个新的训练例子。如果是正例，则首先由 G中去掉不覆盖新正例的概念，然后修改 S为由新正例和 S原有元素共同归纳出的最特殊的结果（这就是尽量少修改 S，但要求 S覆盖新正例）。如果这是反例，则首先由 S中去掉覆盖该反例的概念，然后修改 G为由新反例和 G原有元素共同作特殊化的最一般的结果（这就是尽量少修改 G，但要求 G不覆盖新反例）。5/4/202435史忠植 高级人工智能消除候选元素算法消除候选元素算法 (3)若 G=S且是单元素集，则转(4)，否则转(2)。(4)输出 H中的概念（即 G和 S）。5/4/202436史忠植 高级人工智能改进算法改进算法冲突匹配算法(Hayes-Roth和 McDormott)它用于学习“参数化结构表示”所表达的概念。在上述的修改 S过程中，总是对 S作尽量少的泛化，以便覆盖新的正例。如果描述形式为谓词表达式，则这个过程相当于寻找最大的公共子表达式，这只需要去掉最少的合取条件。最大的合一泛化这个算法用于寻找谓词表达式的最大的合一泛化。它类似于冲突匹配算法，但是它使用的表示语言允许在匹配中多对一的参数联系。5/4/202437史忠植 高级人工智能变型空间缺点变型空间缺点(1)抗干扰能力差(2)不能学习析取概念5/4/202438史忠植 高级人工智能AQAQ归纳学习算法归纳学习算法1969年,Michalski提出了AQ学习算法,这是一种基于实例的学习方法。AQ算法生成的选择假设的析取,覆盖全部正例,而不覆盖任何反例。1978年提出了AQ11 AQ18 AQ195/4/202439史忠植 高级人工智能简单的简单的AQAQ学习算法学习算法它是利用覆盖所有正例，排斥所有反例的思想来寻找规则。比较典型的有Michalski的AQ11方法洪家荣改进的AQ15方法洪家荣的AE5方法5/4/202440史忠植 高级人工智能简单的简单的AQAQ学习算法学习算法(1)集中注意一个实例(作为种子);(2)生成该实例的一致性泛化式(称作star);(3)根据偏好标准,从star选择最优的泛化式(假设)。如果需要,特化该假设;(4)如果该假设覆盖了全部实例,则停止;否则选择一个未被假设覆盖的实例,转到(2)。5/4/202441史忠植 高级人工智能简单的简单的AQAQ学习算法学习算法AE方法AE系列方法是在扩张矩阵中寻找覆盖正例排斥反例的字段值的规则 5/4/202442史忠植 高级人工智能写在最后写在最后成功的基成功的基础在于好的学在于好的学习习惯The foundation of success lies in good habits43谢谢聆听 学习就是为了达到一定目的而努力去干,是为一个目标去战胜各种困难的过程,这个过程会充满压力、痛苦和挫折Learning Is To Achieve A Certain Goal And Work Hard,Is A Process To Overcome Various Difficulties For A Goal