2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 1
机器学习第 2章 概念学习和一般到特殊序
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
提纲
概念学习
– 给定某一类别的若干正例和反例，从中获得该类别的一般定义。
搜索的观点
– 在预定义的假设空间中搜索假设，使其与训练样例有最佳的拟合。
– 利用假设空间的偏序结构
算法收敛到正确假设的条件
归纳学习的本质，从训练数据中泛化的理由
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
简介
许多机器学习涉及到从特殊训练样例中得到一般概念。
概念，可被看作一个对象或事件集合，它是从更大的集合中选取的子集，或在这个较大集合中定义的布尔函数。
概念学习问题的定义
– 给定一个样例集合以及每个样例是否属于某个概念的标注，怎样推断出该概念的一般定义。又称从样例中逼近布尔函数。
– 概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
概念学习任务
一个例子
– 目标概念,Aldo进行水上运动的日子，表示为布尔函数 EnjoySport
– 任务目的，基于某天的各属性，预测
EnjoySport的值
– 一个样例集，每个样例表示为属性的集合
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
概念学习任务（ 2）
YesChangeCoolStrongHighWarmSunny4
YesChangeWarmStrongHighColdRainy3
YesSameWarmStrongHighWarmSunny2
YesSameWarmStrongNormalWarmSunny1
EnjoySportForecastWaterWindHumidityAirTempSkyExample
表 2-1 目标概念 EnjoySport的训练样例
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
概念学习任务（ 3）
表示假设的形式
– 一个简单的形式，实例的各属性约束的合取式
– 令每个假设为 6个约束（或变量）的向量，每个约束对应一个属性可取值范围，为
？任意本属性可接受的值
明确指定的属性值
不接受任何值
– 假设的例子
<?,Cold,High,?,?,?>
<?,?,?,?,?,?> // 所有的样例都是正例
<?,?,?,?,?,?> // 所有的样例都是反例
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 7
概念学习任务（ 4）
EnjoySport概念学习任务
已知
– 实例集 X
每个实例 x由 6个属性描述，每个属性的取值范围已确定
– 假设集 H
每个假设 h描述为 6个属性的取值约束的合取
– 目标概念 c
一个布尔函数，变量为实例
– 训练样例集 D
目标函数（或目标概念）的正例和反例
求解
– H中的一假设 h，使对于 X中任意 x,h(x)=c(x)
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
术语定义
实例 x
实例集 X
概念
目标概念 c
训练样例 x
训练样例集 D
正例，目标概念成员
反例，非目标概念成员
假设 h
假设集 H
机器学习的目标就是寻找一个假设 h，使得对所有的 h，都有 h(x)=c(x)
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
归纳学习假设
什么是归纳学习？
– 从特殊的样例得到普遍的规律
归纳
– 只能保证输出的假设能与训练样例相拟合
归纳假设的一个基本假定
– 对于未见实例最好的假设就是与训练数据最佳拟合的假设
归纳学习假设
– 任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数。
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
作为搜索的概念学习
概念学习可以看作一个搜索的过程
– 搜索范围：假设的表示所隐含定义的整个空间
– 搜索目标：能够最好地拟合训练样例的假设
当假设的表示形式选定后，那么就隐含地为学习算法确定了所有假设的空间
例子 EnjoySport的假设空间
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
假设的一般到特殊序
假设的一般到特殊序关系
– 考虑下面两个假设
h1=<sunny,?,?,Strong,?,?>
h2=<Sunny,?,?,?,?,?>
– 任何被 h1划分为正例的实例都会被 h2划分为正例，因此 h2比 h1更一般。
利用这个关系，无需列举所有假设，就能在无限的假设空间中进行彻底的搜索
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
假设的一般到特殊序（ 2）
关系“更一般”的精确定义
– 任给实例 x和假设 h，说 x满足 h，当且仅当
h(x)=1
– 令 hj和 hk是在 X上定义的布尔函数，称 hj比 hk
更一般，当且仅当
(?x?X)[(hk(x)=1)?(hj(x)=1)]
– 记为 hj more_general_than_or_equal_to hk，或
hj?g hk
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
假设的一般到特殊序（ 3）
,更一般”的严格情形
– hj >g hk，当且仅当,(hj?g hk) (hk?g hj)
,更特殊”关系的定义
– hj?g hk，当且仅当,hk?g hj
以 EnjoySport为例说明上面的定义
偏序的特点（区别于全序），全序上的搜索可以是二分法，偏序的搜索比无序简单，比全序复杂。
这个偏序关系的定义与目标概念无关
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
Find-S：寻找极大特殊假设
使用 more_general_than偏序的搜索算法
– 从 H中最特殊假设开始，然后在假设覆盖正例失败时将其一般化表 2-3 Find-S算法
1,将 h初始化为 H中最特殊假设
2,对每个正例 x
– 对 h的每个属性约束 ai
如果 x满足 ai
那么不做任何处理否则将 h中 ai替换为 x满足的另一个更一般约束
3,输出假设 h
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
Find-S：寻找极大特殊假设（ 2）
Find-S算法在例子 EnjoySport上的应用
– h?<?,?,?,?,?,?>
– h?<Sunny,Warm,Normal,Strong,Warm,
Same>
– h?<Sunny,Warm,?,Strong,Warm,Same>
– 遇到反例,h不变（因为 h已经能够正确地识别反例）
– h?<Sunny,Warm,?,Strong,?,?>
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
Find-S：寻找极大特殊假设（ 3）
Find-S算法演示了一种利用 more_general_than偏序来搜索假设空间的方法，沿着偏序链，从较特殊的假设逐渐转移到较一般的假设。因此，每一步得到的假设都是在那一点上与训练样例一致的最特殊的假设。
Find-S的重要特点：对以属性约束的合取式描述的假设空间 H，保证输出为 H中与正例一致的最特殊的假设。
存在的问题
– 是否收敛到了正确的目标概念？
– 为什么要用最特殊的假设？
– 训练样例是否相互一致？
– 如果有多个极大特殊假设怎么办？
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
变型空间和候选消除算法
候选消除算法概说
– 概念学习的另一种方法，候选消除算法（ candidate-elimination）
– Find-S算法的不足，输出的假设只是 H中能够拟合训练样例的多个假设中的一个
– 候选消除算法输出与训练样例一致的所有假设的集合
– 候选消除算法在描述这一集合时不需要明确列举所有成员
– 利用 more_general_than偏序结构，可以维护一个一致假设集合的简洁表示
– 候选消除算法的应用，化学质谱分析、启发式搜索的控制规则
– 候选消除算法的缺点，容错性能差
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
变型空间和候选消除算法（ 2）
,一致”的定义
– 一个假设 h与训练样例集合 D一致，当且仅当对 D中每一个样例 <x,c(x)>都有 h(x)=c(x)，即
Consistent(h,D)?(?<x,c(x)>?D)h(x)=c(x)
–,一致”与“满足”的关系
变型空间（ version space）
– 与训练样例一致的所有假设组成的集合
– 表示了目标概念的所有合理的变型
关于 H和 D的变型空间，记为 VSH,D，是 H中与训练样例
D一致的所有假设构成的子集
VSH,D={h?H|Consistent(h,D)}
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
变型空间和候选消除算法（ 3）
列表后消除算法表示变型空间的一种方法是列出其所有成员
– 变型空间?包含 H中所有假设的列表
– 对每个训练样例 <x,c(x)>，从变型空间中移除所有 h(x)?c(x)的假设
– 输出 Version Space中的假设列表
优点
– 保证得到所有与训练数据一致的假设
缺点
– 非常繁琐地列出 H中的所有假设，大多数实际的假设空间无法做到
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
变型空间和候选消除算法（ 4）
变型空间的更简洁表示
– 变型空间被表示为它的极大一般和极大特殊的成员
– 这些成员形成了一般和特殊边界的集合，这些边界在整个偏序结构中划分出变型空间
– 以 EnjoySport为例
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
变型空间和候选消除算法（ 5）
形式化定义
– 极大一般
– 极大特殊
– 关于假设空间 H和训练数据 D的 一般边界 G，
是在 H中与 D相一致的极大一般成员的集合
– 关于假设空间 H和训练数据 D的 特殊边界 S，
是在 H中与 D相一致的极大特殊成员的集合
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
变型空间和候选消除算法（ 6）
变型空间表示定理，令 X为一任意的实例集合,H为 X上定义的布尔假设的集合。令 c,X?{0,1}为 X上定义的任一目标概念，并令 D为任一训练样例集合
{<x,c(x)>}。对所有的 X,H,c,D以及良好定义的 S和 G：
VSH,D={h?H|(?s?S)(?g?G)(g?gh?gs)}
证明：只需证明,1）每一个满足上式右边的 h都在 VSH,D中,2） VSH,D的每个成员都满足都满足等式右边。 …
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
变型空间和候选消除算法（ 7）
候选消除算法
– 初始化 G和 S
– 如果 d是一个正例
从 G中移去所有与 d不一致的假设
对 S中每个与 d不一致的假设 s
– 从 S中移去 s
– 把 s的所有的极小泛化式 h加入到 S中，其中 h满足
h与 d一致，而且 G的某个成员比 h更一般
– 如果 d是一个反例
从 S中移去所有与 d不一致的假设
对 G中每个与 d不一致的假设 g
– 从 G中移去 g
– 把 g的所有的极小特殊化式 h加入到 G中，其中 h满足
h与 d一致，而且 S的某个成员比 h更特殊
– 从 G中移去所有这样的假设：它比 G中另一个假设更特殊
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
变型空间和候选消除算法（ 8）
算法举例
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
变型空间和候选消除的说明
候选消除算法收敛到正确的假设
– 训练样例中没有错误
– H中确实包含描述目标概念的正确假设
如果样例中存在错误
– 如果给定足够的训练数据，我们会发现 S和 G边界收敛得到一个空的变型空间
如果目标概念不能由假设表示方式所描述
– 相似情况出现
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
变型空间和候选消除（ 2）
下一步需要什么样的训练样例
– 一般来说，概念学习的最优查询策略，是产生实例以满足当前变型空间中大约半数的假设。这样，变型空间的大小可以在遇到每个新样例时减半，正确的目标概念就可在只用
log2|VS|次实验后得到。
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 27
变型空间和候选消除（ 3）
怎样使用不完全学习概念
– 虽然图 2-3的变型空间中仍包含多个假设，
即目标概念还未学习到，但是仍然有可能对新样例进行一定可信度的分类。
– 表 2-6的例子
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 28
归纳偏置
有关候选消除算法的几个问题
– 如果目标概念不在假设空间中怎么办？
– 是否可设计一个包含所有假设的空间来解决这一困难？
– 假设空间的大小对于算法推广到未见实例的能力有什么影响？
– 假设空间的大小对所需训练样例的数量有什么影响？
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 29
归纳偏置（ 2）
一个有偏的假设空间
– 在 EnjoySport这个例子中，假设空间限制为只包含属性值的合取。（有偏）
– 这一限制，导致假设空间不能够表示最简单的析取形式的目标概念。
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 30
归纳偏置（ 3）
无偏的学习器
– 为了保证目标概念在假设空间中，需要提供一个假设空间，它能表达所有的可教授概念。
换言之，它能表达实例集 X的所有子集。
问题：为什么 2.3节中合取假设空间只能表示 973个假设？
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 31
归纳偏置（ 4）
EnjoySport的无偏形式
– 带来的问题：概念学习算法无法从训练样例中泛化。
– 要想获得单个目标概念，就必须提供 X中所有实例作为训练样例
– 使用 2.6.3节讨论的部分学习的无效
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 32
归纳偏置（ 5）
无偏学习的无用性
– 归纳学习的一个基本属性：学习器如果不对目标概念的形式做预先的假定，它从根本上无法对未见实例进行分类
– 归纳学习需要的预先假定，称为归纳偏置
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 33
归纳偏置（ 6）
归纳偏置的精确定义
– (Dc?xi)?L(xi,Dc)
– 需要在 Dc?xi上附加怎样的前提，以使 L(xi,Dc) 能够演绎派生。
– L的归纳偏置定义为前提集合 B，使所有的新实例满足：
(B?Dc?xi)?L(xi,Dc)
– 考虑对于实例集合 X的概念学习算法 L。令 c为 X上定义的任一概念，并令 Dc为 c的任意训练样例集合,L(xi,Dc) 表示经过 Dc
训练后 L赋予实例 xi的分类。 L的归纳偏置是最小断言集合 B，
它使任意目标概念 c和相应的训练样例 Dc满足：
xi?X[(B?Dc?xi)?L(xi,Dc)]
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 34
归纳偏置（ 6）
候选消除算法的归纳偏置
– {c?H}
3个有偏程度不同的归纳学习算法
– 机械式
– 候选消除算法
– Find-S
一种算法的有偏性越强，它的归纳能力越强，
可以分类更多的未见实例。
某些归纳偏置隐含在学习器中，有些表示为断言集合，可由学习器操作。
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 35
小结
主要内容
– 概念学习可看作搜索预定义潜在假设空间的过程
– 假设的一般到特殊偏序结构可以定义在任何概念学习问题中，
这种结构便于假设空间的搜索
– Find-S算法使用一般到特殊序，在偏序结构的一个分支上执行一般到特殊搜索，寻找一个与样例一致的最特殊假设
– 候选消除算法利用一般到特殊序，通过渐进地计算极大特殊假设集合和极大一般假设集合发现变型空间
– 候选消除算法缺少健壮性，第 10章描述了几种基于一般到特殊序关系的概念学习算法，它们能够处理有噪声的数据和目标概念无法在假设空间中表示的情况
– 归纳学习算法隐含了归纳偏置，候选消除算法的偏置是：目标概念可以在假设空间中找到。输出的假设和对新实例的分类可由归纳偏置和训练样例演绎推出
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 36
补充读物
Bruner et al.1957和 Hunt & Hovland1963研究了概念学习以及一般到特殊的偏序
Winston1970的博士论文将概念学习看作是包含泛化和特殊化操作的搜索过程
Simon & Lea1973将学习的过程看作是在假设空间中搜索的过程
Mitchell1977,1982提出变型空间和候选消除算法
Haussler1988证明，一般边界的大小随训练样例的数目成指数增长
Mitchell1979扩展了候选消除算法，以处理可预见的有限数量的误分类样例
Sebag1994,1996展示了一种被称为析取变型空间的方法来从有噪声数据中学习析取概念
,..
机器学习第 2章 概念学习和一般到特殊序
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
提纲
概念学习
– 给定某一类别的若干正例和反例，从中获得该类别的一般定义。
搜索的观点
– 在预定义的假设空间中搜索假设，使其与训练样例有最佳的拟合。
– 利用假设空间的偏序结构
算法收敛到正确假设的条件
归纳学习的本质，从训练数据中泛化的理由
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
简介
许多机器学习涉及到从特殊训练样例中得到一般概念。
概念，可被看作一个对象或事件集合，它是从更大的集合中选取的子集，或在这个较大集合中定义的布尔函数。
概念学习问题的定义
– 给定一个样例集合以及每个样例是否属于某个概念的标注，怎样推断出该概念的一般定义。又称从样例中逼近布尔函数。
– 概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
概念学习任务
一个例子
– 目标概念,Aldo进行水上运动的日子，表示为布尔函数 EnjoySport
– 任务目的，基于某天的各属性，预测
EnjoySport的值
– 一个样例集，每个样例表示为属性的集合
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
概念学习任务（ 2）
YesChangeCoolStrongHighWarmSunny4
YesChangeWarmStrongHighColdRainy3
YesSameWarmStrongHighWarmSunny2
YesSameWarmStrongNormalWarmSunny1
EnjoySportForecastWaterWindHumidityAirTempSkyExample
表 2-1 目标概念 EnjoySport的训练样例
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
概念学习任务（ 3）
表示假设的形式
– 一个简单的形式，实例的各属性约束的合取式
– 令每个假设为 6个约束（或变量）的向量，每个约束对应一个属性可取值范围，为
？任意本属性可接受的值
明确指定的属性值
不接受任何值
– 假设的例子
<?,Cold,High,?,?,?>
<?,?,?,?,?,?> // 所有的样例都是正例
<?,?,?,?,?,?> // 所有的样例都是反例
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 7
概念学习任务（ 4）
EnjoySport概念学习任务
已知
– 实例集 X
每个实例 x由 6个属性描述，每个属性的取值范围已确定
– 假设集 H
每个假设 h描述为 6个属性的取值约束的合取
– 目标概念 c
一个布尔函数，变量为实例
– 训练样例集 D
目标函数（或目标概念）的正例和反例
求解
– H中的一假设 h，使对于 X中任意 x,h(x)=c(x)
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
术语定义
实例 x
实例集 X
概念
目标概念 c
训练样例 x
训练样例集 D
正例，目标概念成员
反例，非目标概念成员
假设 h
假设集 H
机器学习的目标就是寻找一个假设 h，使得对所有的 h，都有 h(x)=c(x)
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
归纳学习假设
什么是归纳学习？
– 从特殊的样例得到普遍的规律
归纳
– 只能保证输出的假设能与训练样例相拟合
归纳假设的一个基本假定
– 对于未见实例最好的假设就是与训练数据最佳拟合的假设
归纳学习假设
– 任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数。
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
作为搜索的概念学习
概念学习可以看作一个搜索的过程
– 搜索范围：假设的表示所隐含定义的整个空间
– 搜索目标：能够最好地拟合训练样例的假设
当假设的表示形式选定后，那么就隐含地为学习算法确定了所有假设的空间
例子 EnjoySport的假设空间
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
假设的一般到特殊序
假设的一般到特殊序关系
– 考虑下面两个假设
h1=<sunny,?,?,Strong,?,?>
h2=<Sunny,?,?,?,?,?>
– 任何被 h1划分为正例的实例都会被 h2划分为正例，因此 h2比 h1更一般。
利用这个关系，无需列举所有假设，就能在无限的假设空间中进行彻底的搜索
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
假设的一般到特殊序（ 2）
关系“更一般”的精确定义
– 任给实例 x和假设 h，说 x满足 h，当且仅当
h(x)=1
– 令 hj和 hk是在 X上定义的布尔函数，称 hj比 hk
更一般，当且仅当
(?x?X)[(hk(x)=1)?(hj(x)=1)]
– 记为 hj more_general_than_or_equal_to hk，或
hj?g hk
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
假设的一般到特殊序（ 3）
,更一般”的严格情形
– hj >g hk，当且仅当,(hj?g hk) (hk?g hj)
,更特殊”关系的定义
– hj?g hk，当且仅当,hk?g hj
以 EnjoySport为例说明上面的定义
偏序的特点（区别于全序），全序上的搜索可以是二分法，偏序的搜索比无序简单，比全序复杂。
这个偏序关系的定义与目标概念无关
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
Find-S：寻找极大特殊假设
使用 more_general_than偏序的搜索算法
– 从 H中最特殊假设开始，然后在假设覆盖正例失败时将其一般化表 2-3 Find-S算法
1,将 h初始化为 H中最特殊假设
2,对每个正例 x
– 对 h的每个属性约束 ai
如果 x满足 ai
那么不做任何处理否则将 h中 ai替换为 x满足的另一个更一般约束
3,输出假设 h
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
Find-S：寻找极大特殊假设（ 2）
Find-S算法在例子 EnjoySport上的应用
– h?<?,?,?,?,?,?>
– h?<Sunny,Warm,Normal,Strong,Warm,
Same>
– h?<Sunny,Warm,?,Strong,Warm,Same>
– 遇到反例,h不变（因为 h已经能够正确地识别反例）
– h?<Sunny,Warm,?,Strong,?,?>
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
Find-S：寻找极大特殊假设（ 3）
Find-S算法演示了一种利用 more_general_than偏序来搜索假设空间的方法，沿着偏序链，从较特殊的假设逐渐转移到较一般的假设。因此，每一步得到的假设都是在那一点上与训练样例一致的最特殊的假设。
Find-S的重要特点：对以属性约束的合取式描述的假设空间 H，保证输出为 H中与正例一致的最特殊的假设。
存在的问题
– 是否收敛到了正确的目标概念？
– 为什么要用最特殊的假设？
– 训练样例是否相互一致？
– 如果有多个极大特殊假设怎么办？
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
变型空间和候选消除算法
候选消除算法概说
– 概念学习的另一种方法，候选消除算法（ candidate-elimination）
– Find-S算法的不足，输出的假设只是 H中能够拟合训练样例的多个假设中的一个
– 候选消除算法输出与训练样例一致的所有假设的集合
– 候选消除算法在描述这一集合时不需要明确列举所有成员
– 利用 more_general_than偏序结构，可以维护一个一致假设集合的简洁表示
– 候选消除算法的应用，化学质谱分析、启发式搜索的控制规则
– 候选消除算法的缺点，容错性能差
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
变型空间和候选消除算法（ 2）
,一致”的定义
– 一个假设 h与训练样例集合 D一致，当且仅当对 D中每一个样例 <x,c(x)>都有 h(x)=c(x)，即
Consistent(h,D)?(?<x,c(x)>?D)h(x)=c(x)
–,一致”与“满足”的关系
变型空间（ version space）
– 与训练样例一致的所有假设组成的集合
– 表示了目标概念的所有合理的变型
关于 H和 D的变型空间，记为 VSH,D，是 H中与训练样例
D一致的所有假设构成的子集
VSH,D={h?H|Consistent(h,D)}
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
变型空间和候选消除算法（ 3）
列表后消除算法表示变型空间的一种方法是列出其所有成员
– 变型空间?包含 H中所有假设的列表
– 对每个训练样例 <x,c(x)>，从变型空间中移除所有 h(x)?c(x)的假设
– 输出 Version Space中的假设列表
优点
– 保证得到所有与训练数据一致的假设
缺点
– 非常繁琐地列出 H中的所有假设，大多数实际的假设空间无法做到
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
变型空间和候选消除算法（ 4）
变型空间的更简洁表示
– 变型空间被表示为它的极大一般和极大特殊的成员
– 这些成员形成了一般和特殊边界的集合，这些边界在整个偏序结构中划分出变型空间
– 以 EnjoySport为例
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
变型空间和候选消除算法（ 5）
形式化定义
– 极大一般
– 极大特殊
– 关于假设空间 H和训练数据 D的 一般边界 G，
是在 H中与 D相一致的极大一般成员的集合
– 关于假设空间 H和训练数据 D的 特殊边界 S，
是在 H中与 D相一致的极大特殊成员的集合
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
变型空间和候选消除算法（ 6）
变型空间表示定理，令 X为一任意的实例集合,H为 X上定义的布尔假设的集合。令 c,X?{0,1}为 X上定义的任一目标概念，并令 D为任一训练样例集合
{<x,c(x)>}。对所有的 X,H,c,D以及良好定义的 S和 G：
VSH,D={h?H|(?s?S)(?g?G)(g?gh?gs)}
证明：只需证明,1）每一个满足上式右边的 h都在 VSH,D中,2） VSH,D的每个成员都满足都满足等式右边。 …
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
变型空间和候选消除算法（ 7）
候选消除算法
– 初始化 G和 S
– 如果 d是一个正例
从 G中移去所有与 d不一致的假设
对 S中每个与 d不一致的假设 s
– 从 S中移去 s
– 把 s的所有的极小泛化式 h加入到 S中，其中 h满足
h与 d一致，而且 G的某个成员比 h更一般
– 如果 d是一个反例
从 S中移去所有与 d不一致的假设
对 G中每个与 d不一致的假设 g
– 从 G中移去 g
– 把 g的所有的极小特殊化式 h加入到 G中，其中 h满足
h与 d一致，而且 S的某个成员比 h更特殊
– 从 G中移去所有这样的假设：它比 G中另一个假设更特殊
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
变型空间和候选消除算法（ 8）
算法举例
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
变型空间和候选消除的说明
候选消除算法收敛到正确的假设
– 训练样例中没有错误
– H中确实包含描述目标概念的正确假设
如果样例中存在错误
– 如果给定足够的训练数据，我们会发现 S和 G边界收敛得到一个空的变型空间
如果目标概念不能由假设表示方式所描述
– 相似情况出现
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
变型空间和候选消除（ 2）
下一步需要什么样的训练样例
– 一般来说，概念学习的最优查询策略，是产生实例以满足当前变型空间中大约半数的假设。这样，变型空间的大小可以在遇到每个新样例时减半，正确的目标概念就可在只用
log2|VS|次实验后得到。
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 27
变型空间和候选消除（ 3）
怎样使用不完全学习概念
– 虽然图 2-3的变型空间中仍包含多个假设，
即目标概念还未学习到，但是仍然有可能对新样例进行一定可信度的分类。
– 表 2-6的例子
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 28
归纳偏置
有关候选消除算法的几个问题
– 如果目标概念不在假设空间中怎么办？
– 是否可设计一个包含所有假设的空间来解决这一困难？
– 假设空间的大小对于算法推广到未见实例的能力有什么影响？
– 假设空间的大小对所需训练样例的数量有什么影响？
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 29
归纳偏置（ 2）
一个有偏的假设空间
– 在 EnjoySport这个例子中，假设空间限制为只包含属性值的合取。（有偏）
– 这一限制，导致假设空间不能够表示最简单的析取形式的目标概念。
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 30
归纳偏置（ 3）
无偏的学习器
– 为了保证目标概念在假设空间中，需要提供一个假设空间，它能表达所有的可教授概念。
换言之，它能表达实例集 X的所有子集。
问题：为什么 2.3节中合取假设空间只能表示 973个假设？
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 31
归纳偏置（ 4）
EnjoySport的无偏形式
– 带来的问题：概念学习算法无法从训练样例中泛化。
– 要想获得单个目标概念，就必须提供 X中所有实例作为训练样例
– 使用 2.6.3节讨论的部分学习的无效
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 32
归纳偏置（ 5）
无偏学习的无用性
– 归纳学习的一个基本属性：学习器如果不对目标概念的形式做预先的假定，它从根本上无法对未见实例进行分类
– 归纳学习需要的预先假定，称为归纳偏置
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 33
归纳偏置（ 6）
归纳偏置的精确定义
– (Dc?xi)?L(xi,Dc)
– 需要在 Dc?xi上附加怎样的前提，以使 L(xi,Dc) 能够演绎派生。
– L的归纳偏置定义为前提集合 B，使所有的新实例满足：
(B?Dc?xi)?L(xi,Dc)
– 考虑对于实例集合 X的概念学习算法 L。令 c为 X上定义的任一概念，并令 Dc为 c的任意训练样例集合,L(xi,Dc) 表示经过 Dc
训练后 L赋予实例 xi的分类。 L的归纳偏置是最小断言集合 B，
它使任意目标概念 c和相应的训练样例 Dc满足：
xi?X[(B?Dc?xi)?L(xi,Dc)]
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 34
归纳偏置（ 6）
候选消除算法的归纳偏置
– {c?H}
3个有偏程度不同的归纳学习算法
– 机械式
– 候选消除算法
– Find-S
一种算法的有偏性越强，它的归纳能力越强，
可以分类更多的未见实例。
某些归纳偏置隐含在学习器中，有些表示为断言集合，可由学习器操作。
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 35
小结
主要内容
– 概念学习可看作搜索预定义潜在假设空间的过程
– 假设的一般到特殊偏序结构可以定义在任何概念学习问题中，
这种结构便于假设空间的搜索
– Find-S算法使用一般到特殊序，在偏序结构的一个分支上执行一般到特殊搜索，寻找一个与样例一致的最特殊假设
– 候选消除算法利用一般到特殊序，通过渐进地计算极大特殊假设集合和极大一般假设集合发现变型空间
– 候选消除算法缺少健壮性，第 10章描述了几种基于一般到特殊序关系的概念学习算法，它们能够处理有噪声的数据和目标概念无法在假设空间中表示的情况
– 归纳学习算法隐含了归纳偏置，候选消除算法的偏置是：目标概念可以在假设空间中找到。输出的假设和对新实例的分类可由归纳偏置和训练样例演绎推出
2003.12.18 机器学习 -概念学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 36
补充读物
Bruner et al.1957和 Hunt & Hovland1963研究了概念学习以及一般到特殊的偏序
Winston1970的博士论文将概念学习看作是包含泛化和特殊化操作的搜索过程
Simon & Lea1973将学习的过程看作是在假设空间中搜索的过程
Mitchell1977,1982提出变型空间和候选消除算法
Haussler1988证明，一般边界的大小随训练样例的数目成指数增长
Mitchell1979扩展了候选消除算法，以处理可预见的有限数量的误分类样例
Sebag1994,1996展示了一种被称为析取变型空间的方法来从有噪声数据中学习析取概念
,..
