3 机器学习之假设空间

归纳(induction)与演绎(deduction)是科学推理的两大基本手段。前者是从特殊到一般的“泛化”(generalization)过程，即从具体的事实归结出一般性规律；后者则是从一般到特殊的“特化”(specialization)过程，即从基础原理推演出具体状况。例如，在数学公理系统中，基于一组公理和推理规则推导出与之相洽的定理，这是演绎；而“从样例中学习”显然是一个归纳的过程，因此亦称“归纳学习”(inductivelearning)。

归纳学习有狭义与广义之分，广义的归纳学习大体相当于从样例中学习，而狭义的归纳学习则要求从训练数据中学得概念(concept)，因此亦称为“概念学习”或“概念形成”​。概念学习技术目前研究、应用都比较少，因为要学得泛化性能好且语义明确的概念实在太困难了，现实常用的技术大多是产生“黑箱”模型。然而，对概念学习有所了解，有助于理解机器学习的一些基础思想。

概念学习中最基本的是布尔概念学习，即对“是”​“不是”这样的可表示为0/1布尔值的目标概念的学习。举一个简单的例子，假定我们获得了这样一个训练数据集：

表1.1　西瓜数据集

更一般的情况是考虑形如(A∧B)∨(C∧D)的析合范式。

这里要学习的目标是“好瓜”​。暂且假设“好瓜”可由“色泽”​“根蒂”​“敲声”这三个因素完全确定，换言之，只要某个瓜的这三个属性取值明确了，我们就能判断出它是不是好瓜。于是，我们学得的将是“好瓜是某种色泽、某种根蒂、某种敲声的瓜”这样的概念，用布尔表达式写出来则是“好瓜。​（色泽=？​）∧（根蒂=？​）∧（敲声=？​）​”​，这里“​？​”表示尚未确定的取值，而我们的任务就是通过对表1.1的训练集进行学习，把“​？​”确定下来。

“记住”训练样本，就能力。如果仅仅把训练集中的瓜“记住”​，是所谓的“机械学习”​[Cohen and Feigenbaum,1983]​，或称“死记硬背式学习”​，参见（1.5 发展历程）​。

读者可能马上发现，表1.1第一行：​“​（色泽=青绿）∧（根蒂=蜷缩）∧（敲声=浊响）​”不就是好瓜吗？是的，但这是一个已见过的瓜，别忘了我们学习的目的是“泛化”​，即通过对训练集中瓜的学习以获得对没见过的瓜进行判断的能力。如果仅仅把训练集中的瓜“记住”​，今后再见到一模一样的瓜当然可判断，但是，对没见过的瓜，例如“​（色泽=浅白）∧（根蒂=蜷缩）∧（敲声=浊响）​”怎么办呢？

这里我们假定训练样本不含噪声，并且不考虑“非青绿”这样的操作。由于训练集包含正例，因此假设自然不出现。

我们可以把学习过程看作一个在所有假设(hypothesis)组成的空间中进行搜索的过程，搜索目标是找到与训练集“匹配”(fit)的假设，即能够将训练集中的瓜判断正确的假设。假设的表示一旦确定，假设空间及其规模大小就确定了。这里我们的假设空间由形如“​（色泽=？​）∧（根蒂=？​）∧（敲声=？​）​”的可能取值所形成的假设组成。例如色泽有“青绿”​“乌黑”​“浅白”这三种可能取值；还需考虑到，也许“色泽”无论取什么值都合适，我们用通配符“”来表示，例如“好瓜。​（色泽=）∧（根蒂=蜷缩）∧（敲声=浊响）​”​，即“好瓜是根蒂蜷缩、敲声浊响的瓜，什么色泽都行”​。此外，还需考虑极端情况：有可能“好瓜”这个概念根本就不成立，世界上没有“好瓜”这种东西；我们用表示这个假设。这样，若“色泽”​“根蒂”​“敲声”分别有3、3、3种可能取值，则我们面临的假设空间规模大小为4×4×4+1=65。图1.1直观地显示出了这个西瓜问题假设空间。
图1.1　西瓜问题的假设空间

有许多可能的选择，如在路径上自顶向下与自底向上同时进行，在操作上只删除与正例不一致的假设等。

可以有许多策略对这个假设空间进行搜索，例如自顶向下、从一般到特殊，或是自底向上、从特殊到一般，搜索过程中可以不断删除与正例不一致的假设、和（或）与反例一致的假设。最终将会获得与训练集一致（即对所有训练样本能够进行正确判断）的假设，这就是我们学得的结果。

需注意的是，现实问题中我们常面临很大的假设空间，但学习过程是基于有限样本训练集进行的，因此，可能有多个假设与训练集一致，即存在着一个与训练集一致的“假设集合”​，我们称之为“版本空间”(version space)。例如，在西瓜问题中，与表1.1训练集所对应的版本空间如图1.2所示。
图1.2　西瓜问题的版本空