1.3 概念学习与假设空间

归纳（Induction）与演绎（Deduction）是科学推理的两大基本手段。归纳是从特殊到一般的泛化过程，即从具体的事实归结出一般性规律；演绎则是从一般到特殊的特化（Specialization）过程，即从基础原理推演出具体情况。从特殊的训练样例中归纳出一般函数是机器学习的中心问题，该归纳过程称为归纳学习（Inductive Learning）。

归纳学习有广义与狭义之分，前者通常指的是从样例中学习的归纳过程，而后者指的是从训练数据中学得概念（Concept），因此狭义的归纳学习也称为概念学习（Concept Learning）。对概念学习有所了解，有助于理解机器学习的一些基础思想。

概念学习考虑的问题是，给定一样例集合及每个样例是否属于某一概念的标记，怎样自动推断出该概念的一般定义。概念定义在一个实例（Instance）集合之上，这个集合表示为X。在学习目标概念时，必须提供一套训练样例（Training Examples），每个样例为X中的一个实例x及它的目标概念值c(x)。通常用序偶来描述训练样例，表示包含了实例x和目标概念值c(x)。符号D用来表示训练样例的集合。

一旦给定目标概念c的训练样例集，学习器面临的问题就是假设或估计c。可以把学习过程看作一个在所有可能假设（All Possible Hypotheses）的集合上进行搜索的过程，搜索的目标是找到与训练集匹配（Match）或拟合（Fit）的假设。这些所有可能的假设（Hypothesis）组成的空间称为假设空间（Hypothesis Space）。假设空间中的假设集合才是确定目标概念所考虑的范围，通常使用符号来表示。机器学习的目标就是寻找一个假设h，使对于X中的所有x有h(x)=c(x)。换言之，机器学习的任务是在整个实例集合X上确定与目标概念c相同的假设h。

事实上，目标概念c仅仅是训练样例上的信息，没有包含测试样例。因此，归纳学习算法最多只能保证输出的假设能与训练样例相拟合。如果没有更多的信息，我们只能假定，对于未见实例，最好的假设就是与训练数据最佳拟合的假设。由此引出归纳学习的一个基本假设，即归纳学习假设：任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数。

概念学习可以看为一个搜索过程，范围是假设的表示所隐含定义的整个空间。搜索的目标是寻找能最好地拟合训练样例的假设。自然的，对学习算法的研究需要考查假设空间搜索的不同策略。特别引起我们兴趣的算法应能有效地搜索非常大的或无限大的假设空间，以找到最佳拟合训练数据的假设。有很多策略可以对这个假设空间进行搜索，如自顶向下、从一般到特殊，或是自底向上、从特殊到一般。搜索过程中可以不断删除与正例不一致的假设和（或）与反例一致的假设，最终获得与训练集一致的假设，即对所有训练样本能够进行正确判断的假设，这就是我们学得的结果。