[Mitchell 机器学习读书笔记]——概念学习 偏序结构

从特殊的训练样例中归纳出一般函数式机器学习的中心问题。为了获得一个合适的假设，需要在假设空间上搜索以便得到结果，而假设空间本身形成一种自然的结构——即一般到特殊的特殊偏序结构。

1、简介

许多机器学习问题涉及到从特殊训练样例中得到一般概念。比如日常生活中学习到的一些概念和类别包括：鸟类、汽车、勤奋的学习等。如果给定一样例集合以及每个样例是否属于某一概念的标注，怎样自动推断出该概念的一般定义，这一问题称为概念学习（concept learning）。

概念学习的定义：概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。

2、概念学习任务

考虑一个例子，本例的目标概念是：”A进行水上运动的日子“。表1描述了一系列日子的样例，每个样例表示为属性的集合，属性EnjoySport表示这一天A是否乐于进行水上运动。这个任务的目的是基于某天的各属性推测出该天EnjoySport的值。 先考虑一个较为简单的形式，即实例的各属性约束的合取式。令每个假设是一个具有6种约束的向量，这些约束指定了属性Sky,AirTemp,……,Forecast的值。每个属性可取值为： 由”？“表示本属性任意可接受的值；明确指定的属性值（如Warm）；由”∅“表示不接受任何值。如果某些实例x满足假设h的所有约束，那么h将x分类为正例(h(x) = 1)。假设A只在寒冷和潮湿的日子进行水上运动（并且与其他属性无关），这样的假设可以表示为：

<?,cold,high,?,?,?>

总之，EnjoySport这个概念学习任务需要学习的是使EnjoySport = yes的日子，并将其表示为属性约束的合取式。任何概念学习任务能被描述为：实例的集合、实例集合上的目标函数、候选假设的集合以及训练样例的集合。术语解释：X：实例集合c：待学习的概念或目标概念，实例集X上的任意布尔函数，即c:X->{0,1} 一旦给定目标概念c 训练样例集，学习器面临的问题就是假设或估计c。使用H来表示所有可能假设的集合，H中每个假设h表示X上定义的布尔函数，即h:X->{0,1}。机器学习的目标是寻找一个假设h，使对于X中的所有x,h(x)=c(x)。

归纳学习假设：任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好的逼近目标函数。归纳学习假设是一个基本假定，以后还会有分析……

3、基于搜索的概念学习

如果把学习看做是一个搜索问题，那么很自然，对于学习算法的研究需要考察假设空间搜索的不同策略。特别是引起我们兴趣的算法能有效地搜索非常大的或无限大的假设空间，以便找到最佳拟合训练数据的假设。 概念学习都有一种很有效的结构：假设的一般到特殊序关系，利用这种自然结构，就不需要明确列出所有的假设，就可以在无限的假设空间中进行彻底的搜索。 比如假设h1,h2，如果任何能够被h1分为正例的实例都会被h2划分为正例，因此，我们说h2比h1更一般。 定义：令h_j和h_k为在X上定义的布尔函数，称 h_j more_general_than_or_equal_to h_k（记作h_j >=gh_k）当且仅当(∀x∈X)[(h_k (x)=1)→(h_j (x)=1)]>=g是自反、反对称和传递的，即对于3个假设，可能有h2>=gh1，h2>=gh3，但是在h1和h3之间，可能就没有>=g关系了，如下图：>=g给任意概念学习提供了一种有效的结构。

4、FIND-S：寻找极大特殊假设

FIND-S算法的重要特点是：对以属性约束的合取式描述的假设空间，FIND-S保证输出为H中与正例一致的最特殊的假设，不过FIND-S算法有很多的不足，比如选择的假设是一个最特殊的，没有广泛性，简单说来就是正例的合取式，如果碰到错误的训练实例，假设就会出错。

5、变形空间和候选消除算法

候选消除算法寻找与训练样例一致的所有假设。 定义1：一个假设h与训练样例集合D一致，当且仅当对D中每一个样例<x,c(x)>都有h(x) = c(x)。Consistent(h,D) <=>(∀<x,c(x)>∈D)h(x)= c(x)定义2：关于假设空间H和训练样例集D的变型空间，标记为， 5.1 列表后消除算法

5.2 简洁表示变型空间

变型空间中一些极大特殊和极大一般成员形成了一般和特殊边界的集合，这些边界在整个偏序结构中划分出变型空间。

定义：关于假设空间H和训练数据D的一般边界G，是在H中与D相一致的极大一般成员的集合。

定义：关于假设空间H和训练数据D的特殊边界G，是在H中与D相一致的极大特殊成员的集合。

只要集合G和S被良好地定义好了，它们就完全规定了变型空间，其组成是：G中包含的假设，S中包含的假设以及G和S之间偏序结构所规定的假设。

5.3 候选消除学习算法

6、归纳偏置

在给定正确的训练样例并且保证初始假设空间包含目标概念时，候选消除算法可以收敛到目标概念，如果目标概念不在假设空间怎么办？

学习器如果不对目标概念的形式做预先的假定，它从根本上就无法对未见实例进行分类。归纳学习需要某种形式的预先假定，这种假定被称作归纳偏置。

定义：考虑对于实例集合X的概念学习算法L。令c为X上定义的任一概念，并令D_c = {<x,c(x)>}为c的任一训练样例集合。令L(x_i,D_c)表示经过数据D_c的训练后L赋予实例x_i的分类。L的归纳偏置是最小断言集合B，它使任意目标概念c和相应的训练样例D_c满足：

候选消除算法的归纳偏置：目标概念c包含在给定的假设空间H中。 总之，归纳偏置就是一个假定，在这个假定之上，我们的学习算法能够很好地得到目标函数。

7、小结

概念学习可看作是搜索预定义潜在假设空间的过程；假设的一般到特殊偏序结构可以定义在任何概念学习问题中，它提供了一种有用的结构以便于假设空间的搜索；归纳学习算法能够对未见数据进行分类，是因为它们在选择一致的假设过程中隐含的归纳偏置。 （本文参考Mitchell的《机器学习》第二章，是为读书笔记）