By RaySaint 2011/06/17
概念学习和归纳偏置
感觉概念学习现在提得很少，可能是因为在机器学习的实际应用中很少用到，但是从概念学习中很容易引出归纳偏置的概念，而归纳偏置是个很重要的概念，因此这次会简单讲讲概念学习，着重于归纳偏置。可以看到归纳偏置对于机器学习的重要性。
概念学习
给定一样例集合以及每个样例是否属于某一概念的标注，怎样自动推断出该概念的一般定义。这一问题被称为概念学习。
一个更准确的定义：
概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。注意，在前面一篇文章《机器学习的基本概念和学习系统的设计》中提到，机器学习中要学习的知识的确切类型通常是一个函数，在概念学习里面，这个函数被限定为是一个布尔函数，也就是它的输出只有{0,1}（0代表false，1（代表true）），也就是说目标函数的形式如下：
f: X->{0,1}
根据上面的定义，很明显概念学习属于监督学习的分类问题。
举一个《机器学习》By mitchell书上的例子来更好的理解概念学习。
目标概念：Aldo（人名）会去海边游泳的日子，注意，这里这样描述不太好，很容易理解成我们要得到的表示目标感念 的函数输出的是一串日期，不符合前面所说的概念学习的目标是推断一个布尔函数，实际上，这里是给出一个日子，基于这一天的各种属性，推断Aldo是否会在 这天去游泳。下面的表1描述了一系列日子的样例，每个样例表示为属性的集合。属性EnjoySport表示这一天Aldo是否乐于进行水上运动，也是需要 预测的属性；Sky、AirTemp、Humidity、Wind、Water、Forcast是已知的属性，就是要基于这些属性来推断Aldo是否会在 这天去海边游泳。
表1 目标概念EnjoySport的正例和反例
| Example | Sky | AirTemp | Humidity | Wind | Water | Forecast | EnjoySport |
| 1 | Sunny | Warm | Normal | Strong | Warm | Same | Yes |
| 2 | Sunny | Warm | High | Strong | Warm | Same | Yes |
| 3 | Rainy | Cold | High | Strong | Warm | Change | No |
| 4 | Sunny | Warm | High | Strong | Cool | Change | Yes |
接下来要确定假设（目标函数）的形式，可以先考虑一个较为简单的形式，即实例的各个属性的合取式。可令每个假设为6个约束的向量，这些约束指定了Sky、AirTemp、Humidity、Wind、Water、Forcast的值。每个属性可取值为：
- 由“？”表示任意本属性可接受的值。
- 明确指定的属性值（如warm）。
- 由“∅”表示不接受任何值。
如果某些实例x满足假设h的所有约束，那么h将x分类为正例(h(x)=1)。比如，为判定Aldo只在寒冷的和潮湿的日子里进行随上运动（并与其他属性无关），这样的假设可以表示为下面的表达式：
<?, Cold, High, ?, ?, ?>
也就是要表达：
if AirTemp = Cold ∧ Humidity = High then EnjoySport = Yes
那么最一般的假设是每一天都是正例，可表示为：
<?, ?, ?, ?, ?, ?>
而最特殊的假设即每一天都是反例，表示为：
<∅, ∅, ∅, ∅, ∅, ∅>
这里有几点要注意：
1. <∅, ∅, ∅, ∅, ∅, ∅>和<∅, ?, ?, ?, ?, ?>、<∅, ∅, ?, ?, ?, ?>等等其实是一样的假设，也就是只要假设中有一个属性为“∅”，那么这个假设就表示每天都是反例。
2. 你很可能会怀疑，这里假设的形式为什么一定是属性的合取，若属性Humidity有3种取值：High、Normal和Low，那么就无法表达Aldo会在湿度Normal或High的时候去海边游泳，因为这是一个析取式:
if Humidity = Normal ∨ Humidity = High then EnjoySport = Yes
后面会讲，断言假设的形式为属性的合取是一种归纳偏置，它使得我们的学习器是有偏的，如果学习器是无偏的，那么它根本上无法对未见实例进行分类，这一点很重要，后面会慢慢解释。
现在做一些术语定义，方便后面的表述：
- (1)待学习的概念或函数称为目标概念，记作c。
- (2)概念定义在一个实例集合上，这个集合表示为X。学习目标概念时，必须提供一套训练样例（训练集，记 为D），训练集中的人每个样例为X中的一个实例x和它的目标概念值c(x)（如上面的表1中的example）。c(x)=1，x称为正例 (positive)；c(x)=0，x称为反例(negative)。可以用序偶<x, c(x)>来描述训练样例。
- (3)给定目标概念c的训练样例集，学习器面临的问题就是假设或估计c。使用符号H来表示所有可能假设的 集合，也称为假设空间，对于我们的问题来说假设空间就是所有各个属性的合取式。H中的每个假设h表示X上定义的布尔函数,即h:X->{0,1}。 机器学习的目标就是寻找一个假设h，使对于X中的所有x，h(x)=c(x)。
归纳学习假设
机器学习的任务是在实例集合X上寻找一个与目标概念c相同的假设h，然而我们对于c仅有的信息只是它在训练结合上的 值。因此，归纳学习算法最多只能保证输出的假设能与训练样例相拟合。如果没有更多的信息，我们只能假定，对于未见实例最好的假设就是与训练样例数据最佳拟 合的假设。这是一个归纳学习的基本假定。下面给出一个准确的定义：
归纳学习假设 任一假设如果在足够大的训练样例集合中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数。
那么现在该讲讲如何逼近目标函数，也就是先前在《机器学习的基本概念和学习系统的设计》中提到的搜索策略，即如何搜索假设空间H获得与目标概念c一致的假设h。
假设的一般到特殊序、变型空间和候选消除算法
假设的一般到特殊序
许多概念学习算法（如这里要讲的候选消除算法），搜索假设空间的方法依赖于一种针对任意概念学习都很有效的结构：假设的一般到特殊序关系。
考虑下面两个假设：
h1=<Sunny, ?, ?, Strong, ?, ?>
h2=<Sunny,?, ?, ?, ?, ?>
很明显，被h1划分为正例的实例都会被h2划分为正例，因此，可以说h2比h1更一般，h1比h2更特殊。现在要定义“比……更一般”这种关系
定义：令hj和hk为在X上定义的布尔函数。称hj more_general_than_or_equal_to hk （记作hj≥ghk），当且仅当
如果hj≥ghk ∧ (hk ≠g hj)，那么就说 hj 严格的 more_general_than hk（写作hj>ghk），可以得出≥g的一些简单性质：
(1) 自反性，hj≥ghj
(2) 反对称，若hj≥ghk，那么hk 非≥g hj
(3) 传递性，若hi≥ghj且hj≥ghk，那么hi≥ghk
很明显，≥g是假设空间H上的一个偏序关系。
≥g很重要，因为它在假设空间H上对任意概念学习问题提供了一种有效的结构，可以更加有效地搜索假设空间。
变型空间
为了更好的说明变型空间，先给出一个定义：
一个假设h与训练样例集合D一致，当且仅当对D中每一个样例<x,c(x)>都有h(x) = c(x)。
记为
马上要提到的候选现出算法能够表示与训练样例一致的所有假设。在假设空间中的这一子集被称为关于假设空间H和训练样例D的变型空间，因为它包含了目标概念的所有合理的变型。
定义：关于假设空间H和训练样例集D的变型空间，标记为VSH,D，是H中与训练样例D一致的所有假设构成的子集。
使用上面介绍到的一般到特殊序的结构，可以用更简洁的形式表示变型空间。变型空间可以表示为它的极大一般的和极大特殊的成员。
看下面一个假设（怎么得到的先不管），
h = <Sunny, Warm, ?, Strong, ?, ?>
这个h和表1中的4个训练样例一致，实际上，这只是与训练样例一致的所有6个假设之一。下面的图1给出了这个6假设：
图1
图1中的6个假设构成一个变型空间（6个假设都与训练样例集一致），箭头表示实例间的 more_general_than关系。其中S就是极大特殊假设的集合，而G就是极大一般假设的集合，图上很容易看出，如果给定G和S那么很容易通过一 般到特殊偏序结构来生成S和G之间的所有假设，因此只需要给定极大特殊假设的集合和极大一般假设的集合，就能够完整地表示一个变型空间。
下面给出准确的定义：
一般边界：关于假设空间H和训练数据D的一般边界（general boundary）G，是在H中与D相一致的极大一般成员的集合。
特殊边界：关于假设空间H和训练数据D的特殊边界（specific boundary）S，是在H中与D相一致的极大特殊成员的集合。
变型空间表示定理：令X为一任意的实例集合，H为X上定义的布尔假设的结合。令c:X->{0,1}为X上定义的任意目标概念，并令D为任一训练样例的集合{<x,c(x)>}。对所有的X, H, c, D 以及良好定义的S和G：
候选消除算法
有了上面的一些预备知识，现在可以来说明候选消除算法。算法的思路如下：获得变型空间VSH,D ，首先将G边界和S边界分别初始化为H中最一般的假设和最特殊的假设。即:
G0 <- {<?, ?, ?, ?, ?, ?>}
S0 <- {<∅, ∅, ∅, ∅, ∅, ∅>}
然后处理每个训练样例，使得S被一般化，G被特殊化，从而逐步缩小变型空间，消去变型空间中与样例不一致的假设。
伪代码描述如下：
候选消除算法，输入训练样例D，输出由G和S表示的变型空间
G <- {<?, ?, ?, ?, ?, ?>}
S <- {<∅, ∅, ∅, ∅, ∅, ∅>}
foreach d in D
{
if (d == positive)
{
foreach g in G
{
if (g与d不一致)
{
从G中移去g;
}
}
foreach s in S
{
if(s与d不一致)
{
从S从移去s;
foreach s的极小一般化式h
{
if(h与d一致 && G的某个成员比h更一般)
{
将h加入到S中;
}
}
从S中移去所有这样的假设：它比S中另一假设更一般;
}
}
}
else
{
foreach s in S
{
if(s与d不一致)
{
从S中移去s;
}
}
foreach g in G
{
if(g与d不一致)
{
从G中移去g;
foreach g的极小特殊化式h
{
if(h与d一致 && S的某个成员比h更特殊)
{
将h加入到G中;
}
}
从G中移去所有这样的假设：它比G中另一假设更特殊;
}
}
}
}
简单总结一下上面的算法。正例使得变型空间的S边界逐渐一般化，而反例扮演的角色恰好使得G边界逐渐特殊化。每输入一个训练样例，S和G边界将继续单调移动并相互靠近，划分出越来越小的变型空间。
对表1执行候选消除算法，便可以得到图1的结果。
使用不完全学习概念进行分类
假设只提供了表1中的4个训练样例，没有更多的训练样例，现在要对未见过的实例进行分类。图1表示的变型空间仍包含多个假设，即目标概念还未完全学习到，但是仍然有可能对新样例进行一定可信度的分类。为示范这一过程，给出表2列出待分类的新实例：
表2 待分类的新实例
| Instance | Sky | AirTemp | Humidity | Wind | Water | Forecast | EnjoySport |
| A | Sunny | Warm | Normal | Strong | Cool | Change | ? |
| B | Rainy | Cold | Normal | Light | Warm | Same | ? |
| C | Sunny | Warm | Normal | Light | Warm | Same | ? |
| D | Sunny | Cold | Normal | Strong | Warm | Same | ? |