归纳(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 西瓜问题的版本空
