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

第六章归纳学习史忠植中科院计算所3/7/20251史忠植高级人工智能内容提要6.1归纳学习的逻辑基础6.2偏置变换6.3变型空间方法6.4AQ归纳学习算法6.5产生与测试方法6.6决策树学习6.7归纳学习的计算理论6.8支持下向量机3/7/20252史忠植高级人工智能

概述给定关于某个概念的一系列已知的正例和反例，其任务是从中归纳出一个一般的概念描述。归纳学习能够获得新的概念，创立新的规则，发现新的理论。泛化(generalization)用来扩展一假设的语义信息，以使其能够包含更多的正例，应用于更多的情况。特化(specialization)是泛化的相反的操作，用于限制概念描述的应用范围。3/7/20253史忠植高级人工智能归纳学习的一般模式给定:①观察语句集(事实)F：这是有关某类对象中个别具体对象的知识或某一对象的部分特征的知识。②假定的初始归纳断言(可空)：是关于目标的泛化项或泛化描述。③背景知识：背景知识定义了在观察语句和所产生的候选归纳断言上的假定和限制，以及任何有关问题领域知识。有关问题领域知识包括特化所找归纳断言的期望性质的择优标准。寻找:归纳断言H(hypothesis),H重言或弱蕴涵观察语句并满足背景知识。3/7/20254史忠植高级人工智能概述3/7/20255史忠植高级人工智能

概述变型空间AQ11算法决策树方法ID33/7/20256史忠植高级人工智能基本符号表~非&合取（逻辑乘）

析取（逻辑加）

蕴涵

逻辑等价

项重写

异或F事实集H假设|>特化|<泛化3/7/20257史忠植高级人工智能基本符号表|=重新形式化

vi存在量词约束变项vi

Ivi

数值存在量词约束变项vivi

全称量词约束变项viDi

概念描述Ki判断一个概念的名字的谓词::>将概念描述与概念名连接的蕴涵ei

一个事件（对一种情况的描述）Ei

仅对概念ki的事件为真的谓词Xi

属性LEF评价函数DOM(P)描述符P的定义域3/7/20258史忠植高级人工智能概念获取概念获取的一类特殊情况，它的观察语句集F是一个蕴涵的集合,其形式如下：F:{eik::>Ki}i

I其中，eik(Ki的训练事件)是概念Ki的第k个例子的符号描述。概念的谓词Ki,I是Ki的下标集合。

eik::>Ki的含义是“凡符合描述eik的事件均可被断言为概念Ki的例子。3/7/20259史忠植高级人工智能概念获取学习程序要寻求的归纳断言H可以用概念识别规则集来刻画,形式如下：

H:{Di::>Ki}i

I其中Di是概念Ki的描述，即表达式Di是事件的逻辑推论，该事件可被断言为概念Ki的一个例子。3/7/202510史忠植高级人工智能完整性条件

i

I(Ei

Di)3/7/202511史忠植高级人工智能一致性条件

i,j

I(Di

~

Ej),

若i

j3/7/202512史忠植高级人工智能描述符类型(1)名称性描述符。这种描述符的定义域由独立的符号或名字组成，即值集中值之间没有结构关系。例如水果、人名等。(2)线性描述符。该类描述符值集中的元素是一个全序集。例如，资金、温度、重量、产量等都是线性描述符。表示序数、区间、比率和绝对标度的变量都是线性描述符的特例。将一个集合映射成一个完全有序集的函数也是线性描述符。

3/7/202513史忠植高级人工智能描述符类型

(3)结构描述符。其值集是一个树形的图结构，反映值之间的生成层次。在这样的结构中，父节点表示比子节点更一般的概念。例如，在“地名”的值集中，“中国”是节点“北京”、“上海”、“江苏”、“广东”等的父节点。结构描述符的定义域是通过问题背景知识说明的一组推理规则来定义的。结构描述符也能进一步细分为有序和无序的结构描述符。描述符的类型对确定应用描述符的操作是很重要的。3/7/202514史忠植高级人工智能选择型泛化规则

(1)消除条件规则

CTX&S::>K|<CTX::>K其中S是任意的谓词或逻辑表达式。(2)增加选择项规则

CTX1::>K|<CTX1

CTX2::>K通过增加选择项将概念描述泛化3/7/202515史忠植高级人工智能选择型泛化规则

(3)扩大引用范围规则CTX&[L=R1]::>K|<CTX\&[L=R_2]::>K其中R1

R2

DOM(L),DOM(L)为L的域，L是一个项，Ri是L取值的一个集合。(4)闭区间规则

CTX&[L=a]::>KCTX&[L=b]::>K|<CTX&[L=a..b]::>K3/7/202516史忠植高级人工智能选择型泛化规则

(5)爬山泛化树规则

CTX&[L=a]::>KCTX&[L=b]::>K…CTX&[L=i]::>K

|<CTX&[L=S]::>K其中L是结构描述符，在L的泛化树域中，S表示后继为a,b,…,i的最低的父节点。3/7/202517史忠植高级人工智能选择型泛化规则

(6)将常量转换为变量规则

F[a]F[b]…F[i]|<

x,F[x]其中F[x]是依赖于变量x的描述符，a,b,…,i是常量。对于描述F[x],若x的某些值(a,b,…,i)使F[x]成立，则可得到假设：对于x的所有值，F[x]成立。3/7/202518史忠植高级人工智能选择型泛化规则

(7)将合取转换为析取规则

F1&F2::>K|<F1

F2::>K其中F1,F2为任意描述。3/7/202519史忠植高级人工智能选择型泛化规则

(8)扩充量词范围规则

x,F[x]::>k|<

x,F[x]::>k

(I1)x,F[x]::>K|<

(I2)x,F[x]::>K

其中I1,I2是量词的域（整数集合），且I1

I23/7/202520史忠植高级人工智能选择型泛化规则

(9)泛化分解规则用于概念获取

P&F1::>K~P&F2::>K|<F1

F2::>K用于描述泛化

P&F1~P&F2|<F1&F2这里P均为谓词。3/7/202521史忠植高级人工智能选择型泛化规则

(10)反扩充规则

CTX1&[L=R1]::>KCTX2&[L=R2]::>~K|<[L

R2]::>K

其中R1,R2是析取式。3/7/202522史忠植高级人工智能构造型泛化规则构造性泛化规则能生成一些归纳断言，这些归纳断言使用的描述符不出现在初始的观察陈述中，也就是说，这些规则对初始表示空间进行了变换。(1)通用构造型规则

CTX&F1::>KF1

F2|<CTX&F2::>K该规则表示，若一个概念描述含有一部分F1,已知F1蕴涵另一概念F2,则通过用F2替代F1可得到一个更一般的描述。3/7/202523史忠植高级人工智能构造型泛化规则(2)计算变量规则。计算量词变量CQ规则:

V1,V2,…,VkF[V1,V2,…,Vk]CQ规则将产生一个新的描述符“#v-COND”,表示满足某条件COND的vi的个数。3/7/202524史忠植高级人工智能构造型泛化规则(3)产生链属性规则。概念描述中，若一个概念描述中传递关系不同出现的变量形成一条链,该规则能生成刻画链中某些特定对象的特征的描述符。这种对象可能是：LST-对象：“最小的对象”，或链的开始对象。MST-对象：链的结束对象。MID-对象：链中间的对象。Nth-对象：链中第N个位置上的对象。(4)检测描述符之间的相互依靠关系规则。3/7/202525史忠植高级人工智能偏置变换偏置在概念学习中具有重要作用。所谓偏置，是指概念学习中除了正、反例子外，影响假设选择的所有因素。这些因素包括：①描述假设的语言。②程序考虑假设的空间。③按什么顺序假设的过程。④承认定义的准则，即研究过程带有已知假设可以终止还是应该继续挑选一个更好的假设。采用偏置方法，学习部分选择不同的假设，会导致不同的归纳跳跃。3/7/202526史忠植高级人工智能偏置变换偏置有两个特点：(1)强偏置是把概念学习集中于相对少量的假设；反之，弱偏置允许概念学习考虑相对大量的假设。(2)正确偏置允许概念学习选择目标概念，不正确偏置就不能选择目标概念。3/7/202527史忠植高级人工智能偏置变换程序训练集搜索程序知识偏置训练例假设3/7/202528史忠植高级人工智能变型空间变型空间(VersionSpace)方法以整个规则空间为初始的假设规则集合H。依据训练例子中的信息，它对集合H进行泛化或特化处理，逐步缩小集合H。最后使H收敛为只含有要求的规则。由于被搜索的空间H逐步缩小，故称为变型空间。3/7/202529史忠植高级人工智能变型空间没有描述训练例子GS更特殊更一般变型空间方法的初始G集是最上面的一个点（最一般的概念），初始S集是最下面的直线上的点（训练正例），初始H集是整个规则空间。在搜索过程中，G集逐步下移（进行特化），S集逐步上移（进行泛化），H逐步缩小。最后H收敛为只含一个要求的概念。3/7/202530史忠植高级人工智能初始变型空间3/7/202531史忠植高级人工智能第一个训练实例(smcir)3/7/202532史忠植高级人工智能第二个训练实例(lg,tri)3/7/202533史忠植高级人工智能第三个训练实例(lgcir)3/7/202534史忠植高级人工智能消除候选元素算法(1)正规的初始H集是整个规则空间，这时S包含所有可能的训练正例（最特殊的概念）。这时S集规模太大。实际算法的初始S集只包含第一个训练正例,这种H就不是全空间了。(2)接收一个新的训练例子。如果是正例，则首先由G中去掉不覆盖新正例的概念，然后修改S为由新正例和S原有元素共同归纳出的最特殊的结果（这就是尽量少修改S，但要求S覆盖新正例）。如果这是反例，则首先由S中去掉覆盖该反例的概念，然后修改G为由新反例和G原有元素共同作特殊化的最一般的结果（这就是尽量少修改G，但要求G不覆盖新反例）。3/7/202535史忠植高级人工智能消除候选元素算法(3)若G=S且是单元素集，则转(4)，否则转(2)。(4)输出H中的概念（即G和S）。3/7/202536史忠植高级人工智能改进算法冲突匹配算法(Hayes-Roth和McDormott)它用于学习“参数化结构表示”所表达的概念。在上述的修改S过程中，总是对S作尽量少的泛化，以便覆盖新的正例。如果描述形式为谓词表达式，则这个过程相当于寻找最大的公共子表达式，这只需要去掉最少的合取条件。最大的合一泛化这个算法用于寻找谓词表达式的最大的合一泛化。它类似于冲突匹配算法，但是它使用的表示语言允许在匹配中多对一的参数联系。3/7/202537史忠植高级人工智能变型空间缺点(1)抗干扰能力差(2)不能学习析取概念3/7/202538史忠植高级人工智能AQ归纳学习算法1969年,Michalski提出了AQ学习算法,这是一种基于实例的学习方法。AQ算法生成的选择假设的析取,覆盖