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的值。每个属性可取值为：
如果某些实例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
后面会讲，断言假设的形式为属性的合取是一种归纳偏置，它使得我们的学习器是有偏的，如果学习器是无偏的，那么它根本上无法对未见实例进行分类，这一点很重要，后面会慢慢解释。
现在做一些术语定义，方便后面的表述：
归纳学习假设
机器学习的任务是在实例集合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