二、假设空间与归纳偏好

假设空间

归纳（induction）与演绎（deduction）是科学推理的两大基本手段。前者是从特殊到一般的泛化（generalization）过程，即从具体的事实归结出一般性规律；后者则是从一般到特殊的特化（specialization）过程，即从基础原理推演出具体状况。

例如，在数学公理系统中，基于一组公理和推理规则推导出与之相洽的定理，这里演绎；而从样例中学习显然是一个归纳的过程，因此亦称归纳学习（inductive learning）。

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

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

编号	色泽	根蒂	敲声	好瓜
1	青绿	蜷缩	浊响	是
2	乌黑	蜷缩	浊响	是
3	青绿	硬挺	清脆	否
4	乌黑	稍卷	沉闷	否

这里要学习的目标是“好瓜”，暂且假设“好瓜”可由“色泽”“根蒂”“敲声”这三个因素完全确定，换言之，只要某个瓜的这三个属性取值明确了，我们就能判断出它是不是好瓜。

于是，我们学得的将是“好瓜是某种色泽、某种根蒂、某种敲声的瓜”这样的概念，用布尔表达式写出来则是“好瓜↔（色泽=？）^（根蒂=？）^（敲声=？）”，这里”？“表示尚未确定的取值，而我们的任务就是通过对表的训练集进行学习，把”？“确定下来。

对于表中第一行，（色泽=青绿）^（根蒂=蜷缩）^（敲声=浊响）就是好瓜，但这是一个已见过的瓜，我们学习的目的是泛化，即通过对训练集中瓜的学习以获得对没见过的瓜进行判断的能力。如果仅仅把训练集中的瓜记住，今后再见到一模一样的瓜当然可以判断。”记住“训练样本，就是所谓的”机械学习“。

但是，对没见过的瓜，例如（色泽=浅白）^（根蒂=蜷缩）^（敲声=浊响）怎么办？我们可以把学习过程看作一个在所有假设（hypothesis）组成的空间中进行搜索的过程，搜索目标是找到与训练集”匹配“（fit）的假设，即能够将训练集中的瓜判断正确的假设。假设的表示一旦确定，假设空间及其规模大小就确定了。

这里我们的假设空间由形如”（色泽=？）^（根蒂=？）^（敲声=？）“的可能取值所形成的假设组成。例如色泽有”青绿“”乌黑“”浅白“这三种可能取值；还需考虑到，也许”色泽“无论取什么值都适合，我们用通配符”*“来表示，例如“好瓜↔（色泽=*）^（根蒂=蜷缩）^（敲声=浊响）”。(此外，还需考虑极端情况：有可能”好瓜“这个概念根本就不成立，世界上没有”好瓜“这种东西，我们用Ø表示这个假设。)这里我们假定训练样本不含噪声，并且不考虑”非青绿“这样的操作。由于训练集包含正例，因此Ø假设自然不会出现。

若”色泽“”根蒂”“敲声“分别有3、2、2种可能取值，则我们面临的假设空间规模大小为433+1 = 37（含*）。如下图所示：

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

需注意的是，现实问题中我们常面临很大的假设空间，但学习过程是基于有限样本训练集进行的，因此，可能有多个假设与训练集一致，即存在着一个与训练集一致的假设集合，我们称之为版本空间（version space）。

归纳偏好

通过学习得到的模型对应了假设空间中的一个假设。于是上图的西瓜问题版本空间给我们带来一个麻烦：现在有三个与训练集一致的假设，但与它们对应的模型在面临新样本的时候，却会产生不同的输出。

若仅有上表中的训练样本，则无法断定上述三个假设中哪一个更好。然而，对于一个具体的学习算法而言，它必须要产生一个模型。这时，学习算法本身的“偏好”就会起到关键的作用。例如，若我们的算法喜欢“尽可能特殊”的模型，则它会选择“好瓜↔（色泽=*）^（根蒂=蜷缩）^（敲声=浊响）”；但若我们的算法喜欢“尽可能一般”的模型，并且由于某种原因它更“相信”根蒂，则它会选择“好瓜↔（色泽=*）^（根蒂=蜷缩）^（敲声=*）”。尽可能特殊即“使用情形尽可能少”；尽可能一般即“适用情形尽可能多”。机器学习算法在学习过程中对某种类型假设的偏好，称为“归纳偏好”（inductive bias），或简称为“偏好”。

任何一个有效的机器学习算法必有其归纳偏好，否则它将被假设空间中看似在训练集上“等效”的假设所迷惑，而无法产生确定的学习结果。可以想象，如果没有偏好，我们的西瓜学习算法产生的模型每次在进行预测时随机抽选训练集上的等效假设，那么对这个新瓜“色泽=青绿）^（根蒂=蜷缩）^（敲声=沉闷）”，学得模型时而告诉我们它是好的、时而告诉我们它是不好的，这样的学习结果显然没有意义。

归纳偏好的作用在下图这个回归学习图示中可能更直观。这里的每个训练样本是图中的一个点（x，y），要学得一个与训练集一致的模型，相当于找到一条穿过所有训练样本点的曲线。显然，对有限个样本点组成的训练集，存在着很多条曲线与其一致。我们的学习算法必须有某种偏好，才能产出它认为“正确”的模型。例如，若认为相似的样本应有相似的输出（例如，在各种属性上都很相像的西瓜，成熟程度应该比较接近），则对应的学习算法可能偏好图中比较“平滑”的曲线A而不是比较“崎岖”的曲线B。

归纳偏好可看作学习算法自身在一个可能很庞大的假设空间中对假设进行选择的启发式或“价值观”。那么，有没有一般性的原则来引导算法确立“正确的”偏好呢？“奥卡姆剃刀（Occam’s razor）”是一种常用的、自然科学研究中最基本的原则，即“若有多个假设与观察一致，则选择最简单的那个”。如果采用这个原则，并且假设我们认为“更平滑”意味着“更简单”（例如曲线A更易于描述，其方程式是y=-x^2+6x+1,而曲线B则要复杂的多），则在上图中我们会自然的偏好“平滑”的曲线A。

然而，奥卡姆剃刀并非唯一可行的原则。要注意到，奥卡姆剃刀本身存在不同的诠释，例如对西瓜问题来说，假设1：“好瓜↔（色泽=*）^（根蒂=蜷缩）^（敲声=浊响）”和假设2：“好瓜↔（色泽=*）^（根蒂=蜷缩）^（敲声=*）”这两个假设，哪一个更“简单”呢？这个问题并不简单，需借助其他机制才能解决。

事实上，归纳偏好对应了学习算法本身所做出的关与“什么样的模型更好”的假设。在具体的现实问题中，这个假设是否成立，即算法的归纳偏好是否与问题本身匹配，大多数时候直接决定了算法能否取得好的性能。

让我们再回头看看曲线图。假设学习算法fa基于某种归纳偏好产生了对应于曲线A的模型，学习算法fb基于另一种归纳偏好产生了对应于曲线B的模型。基于前面讨论的平滑曲线的某种“描述简单性”，我们满怀信心的期待算法fa比fb更好。确实，下图（a）显示出，与B相比，A与训练集外的样本更一致；换言之，A的泛化能力比B强。但是，若出现了图（b）的情况，B与训练集外的样本更一致。

这种情况完全可能出现。换言之，对于一个学习算法fa，若它在某些问题上比学习算法fb好，则必然存在在另一些问题上，fb比fa好。这个结论对任何算法均成立。“没有免费的午餐”定理（No Free Lunch Theorem，简称NFL定理）证实，无论学习算法fa多聪明、学习算法fb多笨拙，它们的期望性能竟然相同（训练集外误差）。

但是，同时我们需注意到，NFL定理有一个重要前提：所有“问题”出现的机会相同、或所有问题同等重要。但实际情形并不是这样的。很多时候，我们只关注自己正在试图解决的问题（例如某个具体应用任务），希望为它找到一个解决方案，至于这个解决方案在别的问题、甚至在相似的问题上是否为好方案，我们并不关心。

NFL定理最重要的寓意，是让我们清楚的认识到，脱离具体问题，空泛的谈论“什么学习算法更好”毫无意义，因为若考虑所有潜在的问题，则所有学习算法都一样好。要谈论算法的相对优劣，必须要针对具体的学习问题；在某些问题上表现好的学习算法，在另一些问题上却可能不尽如人意，学习算法自身的归纳偏好与问题是否相配，往往会起到决定性的作用。