2009-8-20 史忠植 高级人工智能 1
第六章 归纳学习史忠植中科院计算所
2009-8-20 史忠植 高级人工智能 2
内容提要
6.1 归纳学习的逻辑基础
6.2 偏置变换
6.3 变型空间方法
6.4 AQ归纳学习算法
6.5 产生与测试方法
6.6 决策树学习
6.7 归纳学习的计算理论
6.8 支持下向量机
2009-8-20 史忠植 高级人工智能 3
概述给定关于某个概念的一系列已知的正例和反例，其任务是从中归纳出一个一般的概念描述。归纳学习能够获得新的概念，创立新的规则，发现新的理论。
泛化 (generalization)用来扩展一假设的语义信息，
以使其能够包含更多的正例，应用于更多的情况。
特化 (specialization)是泛化的相反的操作，用于限制概念描述的应用范围。
2009-8-20 史忠植 高级人工智能 4
归纳学习的一般模式给定,
① 观察语句集 (事实 )F：这是有关某类对象中个别具体对象的知识或某一对象的部分特征的知识。
② 假定的初始归纳断言 (可空 )：是关于目标的泛化项或泛化描述。
③ 背景知识：背景知识定义了在观察语句和所产生的候选归纳断言上的假定和限制，以及任何有关问题领域知识。有关问题领域知识包括特化所找归纳断言的期望性质的择优标准。
寻找,
归纳断言 H(hypothesis),H 重言或弱蕴涵观察语句并满足背景知识。
2009-8-20 史忠植 高级人工智能 5
概述
2009-8-20 史忠植 高级人工智能 6
概述变型空间
AQ11算法决策树方法 ID3
2009-8-20 史忠植 高级人工智能 7
基本符号表
~ 非
&合取（逻辑乘）
析取（逻辑加）
蕴涵
逻辑等价
项重写
异或
F事实集
H 假设
|> 特化
|< 泛化
2009-8-20 史忠植 高级人工智能 8
基本符号表
|= 重新形式化
vi存在量词约束变项 vi
Ivi 数值存在量词约束变项 vi
vi 全称量词约束变项 vi
Di 概念描述
Ki 判断一个概念的名字的谓词
::> 将概念描述与概念名连接的蕴涵
ei 一个事件（对一种情况的描述）
Ei 仅对概念 ki的事件为真的谓词
Xi 属性
LEF 评价函数
DOM(P) 描述符 P的定义域
2009-8-20 史忠植 高级人工智能 9
概念获取概念获取的一类特殊情况，它的观察语句集 F是一个蕴涵的集合,其形式如下：
F,{eik,:> Ki} i? I
其中,eik(Ki的训练事件 )是概念 Ki的第 k个例子的符号描述。概念的谓词 Ki,I是 Ki的下标集合。
eik,:> Ki的含义是,凡符合描述 eik的事件均可被断言为概念 Ki的例子。
2009-8-20 史忠植 高级人工智能 10
概念获取学习程序要寻求的归纳断言 H可以用概念识别规则集来刻画,形式如下：
H:{Di,:> Ki} i? I
其中 Di是概念 Ki的描述，即表达式 Di是事件的逻辑推论，
该事件可被断言为概念 Ki的一个例子。
2009-8-20 史忠植 高级人工智能 11
完整性条件
i? I (Ei? Di)
2009-8-20 史忠植 高级人工智能 12
一致性条件
i,j? I (Di? ~ Ej),
若 i? j
2009-8-20 史忠植 高级人工智能 13
描述符类型
(1) 名称性描述符。这种描述符的定义域由独立的符号或名字组成，即值集中值之间没有结构关系。例如水果、人名等。
(2) 线性描述符。该类描述符值集中的元素是一个全序集。例如，资金、温度、重量、产量等都是线性描述符。表示序数、区间、比率和绝对标度的变量都是线性描述符的特例。将一个集合映射成一个完全有序集的函数也是线性描述符。
2009-8-20 史忠植 高级人工智能 14
描述符类型
(3) 结构描述符。其值集是一个树形的图结构，反映值之间的生成层次。
在这样的结构中，父节点表示比子节点更一般的概念。例如，在,地名,的值集中,,中国,是节点,北京,,,上海,,,江苏,,,广东,等的父节点。
结构描述符的定义域是通过问题背景知识说明的一组推理规则来定义的。结构描述符也能进一步细分为有序和无序的结构描述符。描述符的类型对确定应用描述符的操作是很重要的。
2009-8-20 史忠植 高级人工智能 15
选择型泛化规则
(1) 消除条件规则
CTX & S,:> K |< CTX,:> K
其中 S是任意的谓词或逻辑表达式。
(2) 增加选择项规则
CTX1,:> K |< CTX1? CTX2,:> K
通过增加选择项将概念描述泛化
2009-8-20 史忠植 高级人工智能 16
选择型泛化规则
(3) 扩大引用范围规则
CTX & [L = R1],:> K |< CTX \& [L = R_2],:> K
其中 R1? R2? DOM(L),DOM(L) 为 L的域,L是一个项，
Ri是 L取值的一个集合。
(4) 闭区间规则
CTX & [L = a],:> K
CTX & [L = b],:> K
|< CTX & [L = a..b],:> K
2009-8-20 史忠植 高级人工智能 17
选择型泛化规则
(5) 爬山泛化树规则
CTX & [L = a],:> K
CTX & [L = b],:> K
…
CTX & [L = i],:> K
|< CTX & [L = S],:> K
其中 L是结构描述符，在 L的泛化树域中,S表示后继为
a,b,…,i的最低的父节点。
2009-8-20 史忠植 高级人工智能 18
选择型泛化规则
(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]成立。
2009-8-20 史忠植 高级人工智能 19
选择型泛化规则
(7) 将合取转换为析取规则
F1 & F2,:> K |< F1? F2,:> K
其中 F1,F2为任意描述。
2009-8-20 史忠植 高级人工智能 20
选择型泛化规则
(8) 扩充量词范围规则
x,F[x],:> k |<? x,F[x],:> k
(I1)x,F[x],:> K |<?(I2)x,F[x]::> K
其中 I1,I2是量词的域（整数集合），
且 I1? I2
2009-8-20 史忠植 高级人工智能 21
选择型泛化规则
(9) 泛化分解规则用于概念获取
P & F1,:> K
~ P & F2,:> K
|< F1? F2,:> K
用于描述泛化
P & F1? ~ P & F2 |< F1 & F2
这里 P均为谓词。
2009-8-20 史忠植 高级人工智能 22
选择型泛化规则
(10) 反扩充规则
CTX1 & [L = R1],:> K
CTX2 & [L = R2],:> ~ K
|< [L? R2],:> K
其中 R1,R2是析取式。
2009-8-20 史忠植 高级人工智能 23
构造型泛化规则构造性泛化规则能生成一些归纳断言，这些归纳断言使用的描述符不出现在初始的观察陈述中，也就是说，这些规则对初始表示空间进行了变换。
(1) 通用构造型规则
CTX & F1,:> K
F1? F2
|< CTX & F2,:> K
该规则表示，若一个概念描述含有一部分 F1,已知 F1蕴涵另一概念 F2,则通过用 F2替代 F1可得到一个更一般的描述。
2009-8-20 史忠植 高级人工智能 24
构造型泛化规则
(2) 计算变量规则。
计算量词变量 CQ规则,
V1,V2,…,Vk F[V1,V2,…,Vk]
CQ规则将产生一个新的描述符,#v-COND”,表示满足某条件 COND的 vi的个数。
2009-8-20 史忠植 高级人工智能 25
构造型泛化规则
(3) 产生链属性规则。
概念描述中，若一个概念描述中传递关系不同出现的变量形成一条链,该规则能生成刻画链中某些特定对象的特征的描述符。这种对象可能是：
LST-对象：,最小的对象,,或链的开始对象。
MST-对象,链的结束对象。
MID-对象,链中间的对象。
Nth-对象,链中第 N个位置上的对象。
(4) 检测描述符之间的相互依靠关系规则。
2009-8-20 史忠植 高级人工智能 26
偏置变换偏置在概念学习中具有重要作用。所谓偏置，是指概念学习中除了正、反例子外，影响假设选择的所有因素。
这些因素包括：
①描述假设的语言。
②程序考虑假设的空间。
③按什么顺序假设的过程。
④承认定义的准则，即研究过程带有已知假设可以终止还是应该继续挑选一个更好的假设。采用偏置方法，
学习部分选择不同的假设，会导致不同的归纳跳跃。
2009-8-20 史忠植 高级人工智能 27
偏置变换偏置有两个特点：
(1) 强偏置是把概念学习集中于相对少量的假设；
反之，弱偏置允许概念学习考虑相对大量的假设。
(2) 正确偏置允许概念学习选择目标概念，不正确偏置就不能选择目标概念。
2009-8-20 史忠植 高级人工智能 28
偏置变换程序训练集搜索程序 知识偏置训练例假设
2009-8-20 史忠植 高级人工智能 29
变型空间变型空间 (Version Space)方法以整个规则空间为初始的假设规则集合 H。依据训练例子中的信息，它对集合 H进行泛化或特化处理，逐步缩小集合 H。最后使 H收敛为只含有要求的规则。由于被搜索的空间 H
逐步缩小，故称为变型空间。
2009-8-20 史忠植 高级人工智能 30
变型空间没有描述训练例子
G
S
更特殊更一般变型空间方法的初始 G
集是最上面的一个点
（最一般的概念），初始 S集是最下面的直线上的点（训练正例），
初始 H集是整个规则空间。在搜索过程中,G 集逐步下移
（进行特化）,S 集逐步上移（进行泛化），
H 逐步缩小。最后 H收敛为只含一个要求的概念。
2009-8-20 史忠植 高级人工智能 31
初始变型空间
( x y )
( s m y ) ( lg y ) ( x s q u ) ( x c ir ) ( x tr i)
( s m s q u ) ( lg s q u ) ( s m c ir ) ( lg c ir ) ( s m tr i) ( lg tr i)
2009-8-20 史忠植 高级人工智能 32
第一个训练实例 (sm cir)
( x y )
( s m y ) ( lg y ) ( x s q u ) ( x c ir ) ( x tr i)
( s m s q u ) ( lg s q u ) ( s m c ir ) ( lg c ir ) ( s m tr i) ( lg tr i)
2009-8-20 史忠植 高级人工智能 33
第二个训练实例 (lg,tri)
( x y )
( s m y ) ( lg y ) ( x s q u ) ( x c ir ) ( x tr i)
( s m s q u ) ( lg s q u ) ( s m c ir ) ( lg c ir ) ( s m tr i) ( lg tr i)
2009-8-20 史忠植 高级人工智能 34
第三个训练实例 (lg cir)
( x y )
( s m y ) ( lg y ) ( x s q u ) ( x c ir ) ( x tr i)
( s m s q u ) ( lg s q u ) ( s m c ir ) ( lg c ir ) ( s m tr i) ( lg tr i)
2009-8-20 史忠植 高级人工智能 35
消除候选元素算法
(1) 正规的初始 H集是整个规则空间，这时 S包含所有可能的训练正例（最特殊的概念）。这时 S集规模太大。实际算法的初始 S集只包含第一个训练正例,这种 H就不是全空间了。
(2) 接收一个新的训练例子。如果是正例，则首先由 G中去掉不覆盖新正例的概念，然后修改 S为由新正例和 S原有元素共同归纳出的最特殊的结果（这就是尽量少修改 S，但要求 S覆盖新正例）。如果这是反例，则首先由 S中去掉覆盖该反例的概念，
然后修改 G为由新反例和 G原有元素共同作特殊化的最一般的结果（这就是尽量少修改 G，但要求 G不覆盖新反例）。
2009-8-20 史忠植 高级人工智能 36
消除候选元素算法
(3) 若 G=S且是单元素集，则转 (4)，否则转 (2)。
(4) 输出 H中的概念（即 G和 S）。
2009-8-20 史忠植 高级人工智能 37
改进算法冲突匹配算法 (Hayes-Roth和 McDormott)
它用于学习,参数化结构表示,所表达的概念。在上述的修改 S
过程中，总是对 S作尽量少的泛化，以便覆盖新的正例。如果描述形式为谓词表达式，则这个过程相当于寻找最大的公共子表达式，这只需要去掉最少的合取条件。
最大的合一泛化这个算法用于寻找谓词表达式的最大的合一泛化。它类似于冲突匹配算法，但是它使用的表示语言允许在匹配中多对一的参数联系。
2009-8-20 史忠植 高级人工智能 38
变型空间缺点
(1) 抗干扰能力差
(2) 不能学习析取概念
2009-8-20 史忠植 高级人工智能 39
AQ归纳学习算法
1969年,Michalski提出了 AQ学习算法,这是一种基于实例的学习方法。 AQ算法生成的选择假设的析取,
覆盖全部正例,而不覆盖任何反例。
1978年提出了 AQ11
AQ18
AQ19
2009-8-20 史忠植 高级人工智能 40
简单的 AQ学习算法它是利用覆盖所有正例，排斥所有反例的思想来寻找规则。
比较典型的有 Michalski的 AQ11方法洪家荣改进的 AQ15方法洪家荣的 AE5方法
2009-8-20 史忠植 高级人工智能 41
简单的 AQ学习算法
(1) 集中注意一个实例 (作为种子 );
(2) 生成该实例的一致性泛化式 (称作 star);
(3) 根据偏好标准,从 star选择最优的泛化式 (假设 )。如果需要,特化该假设 ;
(4) 如果该假设覆盖了全部实例,则停止 ; 否则选择一个未被假设覆盖的实例,
转到 (2)。
2009-8-20 史忠植 高级人工智能 42
简单的 AQ学习算法
AE方法
AE系列方法是在扩张矩阵中寻找覆盖正例排斥反例的字段值的规则
2009-8-20 史忠植 高级人工智能 43
AQ学习算法
Michalski等采用 AQ11程序学习 15种黄豆病害的诊断规则。提供给程序 630种患病黄豆植株的描述，每个描述是 35个特征的特征向量。同时送入每个描述的专家诊断结论。选择例子程序从中选出 290种样本植株作为训练例子。选择准则是使例子间相差较大。其余 340种植株留作测试集合，
用来检验得到的规则 。
第六章 归纳学习史忠植中科院计算所
2009-8-20 史忠植 高级人工智能 2
内容提要
6.1 归纳学习的逻辑基础
6.2 偏置变换
6.3 变型空间方法
6.4 AQ归纳学习算法
6.5 产生与测试方法
6.6 决策树学习
6.7 归纳学习的计算理论
6.8 支持下向量机
2009-8-20 史忠植 高级人工智能 3
概述给定关于某个概念的一系列已知的正例和反例，其任务是从中归纳出一个一般的概念描述。归纳学习能够获得新的概念，创立新的规则，发现新的理论。
泛化 (generalization)用来扩展一假设的语义信息，
以使其能够包含更多的正例，应用于更多的情况。
特化 (specialization)是泛化的相反的操作，用于限制概念描述的应用范围。
2009-8-20 史忠植 高级人工智能 4
归纳学习的一般模式给定,
① 观察语句集 (事实 )F：这是有关某类对象中个别具体对象的知识或某一对象的部分特征的知识。
② 假定的初始归纳断言 (可空 )：是关于目标的泛化项或泛化描述。
③ 背景知识：背景知识定义了在观察语句和所产生的候选归纳断言上的假定和限制，以及任何有关问题领域知识。有关问题领域知识包括特化所找归纳断言的期望性质的择优标准。
寻找,
归纳断言 H(hypothesis),H 重言或弱蕴涵观察语句并满足背景知识。
2009-8-20 史忠植 高级人工智能 5
概述
2009-8-20 史忠植 高级人工智能 6
概述变型空间
AQ11算法决策树方法 ID3
2009-8-20 史忠植 高级人工智能 7
基本符号表
~ 非
&合取（逻辑乘）
析取（逻辑加）
蕴涵
逻辑等价
项重写
异或
F事实集
H 假设
|> 特化
|< 泛化
2009-8-20 史忠植 高级人工智能 8
基本符号表
|= 重新形式化
vi存在量词约束变项 vi
Ivi 数值存在量词约束变项 vi
vi 全称量词约束变项 vi
Di 概念描述
Ki 判断一个概念的名字的谓词
::> 将概念描述与概念名连接的蕴涵
ei 一个事件（对一种情况的描述）
Ei 仅对概念 ki的事件为真的谓词
Xi 属性
LEF 评价函数
DOM(P) 描述符 P的定义域
2009-8-20 史忠植 高级人工智能 9
概念获取概念获取的一类特殊情况，它的观察语句集 F是一个蕴涵的集合,其形式如下：
F,{eik,:> Ki} i? I
其中,eik(Ki的训练事件 )是概念 Ki的第 k个例子的符号描述。概念的谓词 Ki,I是 Ki的下标集合。
eik,:> Ki的含义是,凡符合描述 eik的事件均可被断言为概念 Ki的例子。
2009-8-20 史忠植 高级人工智能 10
概念获取学习程序要寻求的归纳断言 H可以用概念识别规则集来刻画,形式如下：
H:{Di,:> Ki} i? I
其中 Di是概念 Ki的描述，即表达式 Di是事件的逻辑推论，
该事件可被断言为概念 Ki的一个例子。
2009-8-20 史忠植 高级人工智能 11
完整性条件
i? I (Ei? Di)
2009-8-20 史忠植 高级人工智能 12
一致性条件
i,j? I (Di? ~ Ej),
若 i? j
2009-8-20 史忠植 高级人工智能 13
描述符类型
(1) 名称性描述符。这种描述符的定义域由独立的符号或名字组成，即值集中值之间没有结构关系。例如水果、人名等。
(2) 线性描述符。该类描述符值集中的元素是一个全序集。例如，资金、温度、重量、产量等都是线性描述符。表示序数、区间、比率和绝对标度的变量都是线性描述符的特例。将一个集合映射成一个完全有序集的函数也是线性描述符。
2009-8-20 史忠植 高级人工智能 14
描述符类型
(3) 结构描述符。其值集是一个树形的图结构，反映值之间的生成层次。
在这样的结构中，父节点表示比子节点更一般的概念。例如，在,地名,的值集中,,中国,是节点,北京,,,上海,,,江苏,,,广东,等的父节点。
结构描述符的定义域是通过问题背景知识说明的一组推理规则来定义的。结构描述符也能进一步细分为有序和无序的结构描述符。描述符的类型对确定应用描述符的操作是很重要的。
2009-8-20 史忠植 高级人工智能 15
选择型泛化规则
(1) 消除条件规则
CTX & S,:> K |< CTX,:> K
其中 S是任意的谓词或逻辑表达式。
(2) 增加选择项规则
CTX1,:> K |< CTX1? CTX2,:> K
通过增加选择项将概念描述泛化
2009-8-20 史忠植 高级人工智能 16
选择型泛化规则
(3) 扩大引用范围规则
CTX & [L = R1],:> K |< CTX \& [L = R_2],:> K
其中 R1? R2? DOM(L),DOM(L) 为 L的域,L是一个项，
Ri是 L取值的一个集合。
(4) 闭区间规则
CTX & [L = a],:> K
CTX & [L = b],:> K
|< CTX & [L = a..b],:> K
2009-8-20 史忠植 高级人工智能 17
选择型泛化规则
(5) 爬山泛化树规则
CTX & [L = a],:> K
CTX & [L = b],:> K
…
CTX & [L = i],:> K
|< CTX & [L = S],:> K
其中 L是结构描述符，在 L的泛化树域中,S表示后继为
a,b,…,i的最低的父节点。
2009-8-20 史忠植 高级人工智能 18
选择型泛化规则
(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]成立。
2009-8-20 史忠植 高级人工智能 19
选择型泛化规则
(7) 将合取转换为析取规则
F1 & F2,:> K |< F1? F2,:> K
其中 F1,F2为任意描述。
2009-8-20 史忠植 高级人工智能 20
选择型泛化规则
(8) 扩充量词范围规则
x,F[x],:> k |<? x,F[x],:> k
(I1)x,F[x],:> K |<?(I2)x,F[x]::> K
其中 I1,I2是量词的域（整数集合），
且 I1? I2
2009-8-20 史忠植 高级人工智能 21
选择型泛化规则
(9) 泛化分解规则用于概念获取
P & F1,:> K
~ P & F2,:> K
|< F1? F2,:> K
用于描述泛化
P & F1? ~ P & F2 |< F1 & F2
这里 P均为谓词。
2009-8-20 史忠植 高级人工智能 22
选择型泛化规则
(10) 反扩充规则
CTX1 & [L = R1],:> K
CTX2 & [L = R2],:> ~ K
|< [L? R2],:> K
其中 R1,R2是析取式。
2009-8-20 史忠植 高级人工智能 23
构造型泛化规则构造性泛化规则能生成一些归纳断言，这些归纳断言使用的描述符不出现在初始的观察陈述中，也就是说，这些规则对初始表示空间进行了变换。
(1) 通用构造型规则
CTX & F1,:> K
F1? F2
|< CTX & F2,:> K
该规则表示，若一个概念描述含有一部分 F1,已知 F1蕴涵另一概念 F2,则通过用 F2替代 F1可得到一个更一般的描述。
2009-8-20 史忠植 高级人工智能 24
构造型泛化规则
(2) 计算变量规则。
计算量词变量 CQ规则,
V1,V2,…,Vk F[V1,V2,…,Vk]
CQ规则将产生一个新的描述符,#v-COND”,表示满足某条件 COND的 vi的个数。
2009-8-20 史忠植 高级人工智能 25
构造型泛化规则
(3) 产生链属性规则。
概念描述中，若一个概念描述中传递关系不同出现的变量形成一条链,该规则能生成刻画链中某些特定对象的特征的描述符。这种对象可能是：
LST-对象：,最小的对象,,或链的开始对象。
MST-对象,链的结束对象。
MID-对象,链中间的对象。
Nth-对象,链中第 N个位置上的对象。
(4) 检测描述符之间的相互依靠关系规则。
2009-8-20 史忠植 高级人工智能 26
偏置变换偏置在概念学习中具有重要作用。所谓偏置，是指概念学习中除了正、反例子外，影响假设选择的所有因素。
这些因素包括：
①描述假设的语言。
②程序考虑假设的空间。
③按什么顺序假设的过程。
④承认定义的准则，即研究过程带有已知假设可以终止还是应该继续挑选一个更好的假设。采用偏置方法，
学习部分选择不同的假设，会导致不同的归纳跳跃。
2009-8-20 史忠植 高级人工智能 27
偏置变换偏置有两个特点：
(1) 强偏置是把概念学习集中于相对少量的假设；
反之，弱偏置允许概念学习考虑相对大量的假设。
(2) 正确偏置允许概念学习选择目标概念，不正确偏置就不能选择目标概念。
2009-8-20 史忠植 高级人工智能 28
偏置变换程序训练集搜索程序 知识偏置训练例假设
2009-8-20 史忠植 高级人工智能 29
变型空间变型空间 (Version Space)方法以整个规则空间为初始的假设规则集合 H。依据训练例子中的信息，它对集合 H进行泛化或特化处理，逐步缩小集合 H。最后使 H收敛为只含有要求的规则。由于被搜索的空间 H
逐步缩小，故称为变型空间。
2009-8-20 史忠植 高级人工智能 30
变型空间没有描述训练例子
G
S
更特殊更一般变型空间方法的初始 G
集是最上面的一个点
（最一般的概念），初始 S集是最下面的直线上的点（训练正例），
初始 H集是整个规则空间。在搜索过程中,G 集逐步下移
（进行特化）,S 集逐步上移（进行泛化），
H 逐步缩小。最后 H收敛为只含一个要求的概念。
2009-8-20 史忠植 高级人工智能 31
初始变型空间
( x y )
( s m y ) ( lg y ) ( x s q u ) ( x c ir ) ( x tr i)
( s m s q u ) ( lg s q u ) ( s m c ir ) ( lg c ir ) ( s m tr i) ( lg tr i)
2009-8-20 史忠植 高级人工智能 32
第一个训练实例 (sm cir)
( x y )
( s m y ) ( lg y ) ( x s q u ) ( x c ir ) ( x tr i)
( s m s q u ) ( lg s q u ) ( s m c ir ) ( lg c ir ) ( s m tr i) ( lg tr i)
2009-8-20 史忠植 高级人工智能 33
第二个训练实例 (lg,tri)
( x y )
( s m y ) ( lg y ) ( x s q u ) ( x c ir ) ( x tr i)
( s m s q u ) ( lg s q u ) ( s m c ir ) ( lg c ir ) ( s m tr i) ( lg tr i)
2009-8-20 史忠植 高级人工智能 34
第三个训练实例 (lg cir)
( x y )
( s m y ) ( lg y ) ( x s q u ) ( x c ir ) ( x tr i)
( s m s q u ) ( lg s q u ) ( s m c ir ) ( lg c ir ) ( s m tr i) ( lg tr i)
2009-8-20 史忠植 高级人工智能 35
消除候选元素算法
(1) 正规的初始 H集是整个规则空间，这时 S包含所有可能的训练正例（最特殊的概念）。这时 S集规模太大。实际算法的初始 S集只包含第一个训练正例,这种 H就不是全空间了。
(2) 接收一个新的训练例子。如果是正例，则首先由 G中去掉不覆盖新正例的概念，然后修改 S为由新正例和 S原有元素共同归纳出的最特殊的结果（这就是尽量少修改 S，但要求 S覆盖新正例）。如果这是反例，则首先由 S中去掉覆盖该反例的概念，
然后修改 G为由新反例和 G原有元素共同作特殊化的最一般的结果（这就是尽量少修改 G，但要求 G不覆盖新反例）。
2009-8-20 史忠植 高级人工智能 36
消除候选元素算法
(3) 若 G=S且是单元素集，则转 (4)，否则转 (2)。
(4) 输出 H中的概念（即 G和 S）。
2009-8-20 史忠植 高级人工智能 37
改进算法冲突匹配算法 (Hayes-Roth和 McDormott)
它用于学习,参数化结构表示,所表达的概念。在上述的修改 S
过程中，总是对 S作尽量少的泛化，以便覆盖新的正例。如果描述形式为谓词表达式，则这个过程相当于寻找最大的公共子表达式，这只需要去掉最少的合取条件。
最大的合一泛化这个算法用于寻找谓词表达式的最大的合一泛化。它类似于冲突匹配算法，但是它使用的表示语言允许在匹配中多对一的参数联系。
2009-8-20 史忠植 高级人工智能 38
变型空间缺点
(1) 抗干扰能力差
(2) 不能学习析取概念
2009-8-20 史忠植 高级人工智能 39
AQ归纳学习算法
1969年,Michalski提出了 AQ学习算法,这是一种基于实例的学习方法。 AQ算法生成的选择假设的析取,
覆盖全部正例,而不覆盖任何反例。
1978年提出了 AQ11
AQ18
AQ19
2009-8-20 史忠植 高级人工智能 40
简单的 AQ学习算法它是利用覆盖所有正例，排斥所有反例的思想来寻找规则。
比较典型的有 Michalski的 AQ11方法洪家荣改进的 AQ15方法洪家荣的 AE5方法
2009-8-20 史忠植 高级人工智能 41
简单的 AQ学习算法
(1) 集中注意一个实例 (作为种子 );
(2) 生成该实例的一致性泛化式 (称作 star);
(3) 根据偏好标准,从 star选择最优的泛化式 (假设 )。如果需要,特化该假设 ;
(4) 如果该假设覆盖了全部实例,则停止 ; 否则选择一个未被假设覆盖的实例,
转到 (2)。
2009-8-20 史忠植 高级人工智能 42
简单的 AQ学习算法
AE方法
AE系列方法是在扩张矩阵中寻找覆盖正例排斥反例的字段值的规则
2009-8-20 史忠植 高级人工智能 43
AQ学习算法
Michalski等采用 AQ11程序学习 15种黄豆病害的诊断规则。提供给程序 630种患病黄豆植株的描述，每个描述是 35个特征的特征向量。同时送入每个描述的专家诊断结论。选择例子程序从中选出 290种样本植株作为训练例子。选择准则是使例子间相差较大。其余 340种植株留作测试集合，
用来检验得到的规则 。
