概念学习：“Find-S 算法”，机器学习的敲门砖
在之前的博客中，我们讲到了一台机器通过机器学习所能完成的壮举，以及深入学习机器学习之前必备的数学知识。那么，在理解了机器学习的先决条件之后，就让我们迈着小而高效的步子，开始机器学习的成功之旅吧。
许多人常常思考，机器是如何从数据中学习，是如何预测未来的。诚然，我们正生活在一个很多人快速高效地工作于全球大数据技术的时代，但需要我们关注的并不仅限于拥有大量数据，我们还需要关注这些数据的高效运用，直到能找到其中的模式，并使用它们来预测未来和找出对策。
要想知道一台机器是如何从经历中学习并根据经历预测未来，我们首先需要了解的，是人脑的工作方式。一旦我们洞察了人脑解决问题的模式，就可以让机器以几乎相同的方式进行学习。并且，机器相对人脑更加不受限制，有更多可探索的地方。但是，机器学习是一个十分宽广的领域，并且存在很多可能性，所以，我们今天就从最简单的机器学习算法开始：Find-S 算法。
什么是学习？
“学习”有好几个定义，其中一个最简单的是：
“通过学习，实践，听讲，或体验某事，获得知识或技能的活动或过程”。
正如学习有不同的定义一样，学习方法也有很多种。
作为一个人，我们一生都在学习很多东西。其中一些是基于我们的经历，另外一些则是基于记忆。在此基础上，我们可以将学习方法分为五个部分：
- 死记硬背（记忆）：记住事物，但不知道背后的概念/逻辑。
- 被动学习（指导）：从老师/专家那里学习。
- 类比（经历）：从过去的经历中学习新事物。
- 归纳学习（经历）：根据过去的经历，构建一个概括性的概念。
- 演绎学习： 从过去的事实中推导新的事实。
归纳学习旨在通过观察一个概念的例子来构建一个概括性的概念。例如，如果一个孩子被要求写出 2 * 8 = x 的答案 ，那么他即可以用死记硬背的方法来记忆答案，或者，他也可以用归纳学习（即思考为什么 2 * 1 = 2, 2 * 2 = 4 ...）来构建解题的方案，然后得出答案。通过这种方式，这个孩子将能够使用这一方案来解决许多类似的问题。
同样，我们可以让我们的机器从过去的数据中学习，并让它们能够判断一个对象是否属于我们感兴趣的那一类。
什么是概念学习？
在机器学习中，“概念学习” 可以被定义为：
“一个搜索过程，它在预定义的假设空间中按着某种搜索策略进行搜索，使学到的概念与训练实例有最佳的拟合度。” - Tom Michell
大部分的人类学习都包含了从过去的经历中获得一般性的概念。例如，人类可以通过在大量特征集合中定义出的特定特征集合，来辨别出每一种交通工具的不同。这个特征集合可以从 “交通工具” 的集合中区分出名为 “汽车” 的子集。而这种区分出汽车的特征集合便被称之为 “概念”。
类似地，机器也可以从概念中学习，通过处理 旧数据/训练数据，找出对象是否属于特定类别，最终找出与训练实例拟合度最高的假设。
定义一个概念的项目/对象集称为实例集，用 X 表示。要学习的概念或函数称为目标概念，用 c 表示。它可以看作是一个在 X 上定义的布尔值函数，表示为 c: X -> {0, 1}。
如果我们有一套具有特定目标概念 c 的特征的训练实例，那么学习者面临的问题则是去估计可在训练数据上定义的 c。
关于目标概念的特征，H 被用来表示学习者可能考虑的的所有可能假设的集合。此时学习者的目标是找到一个能够辨别 X 中所有对象的假设 H，使得对所有的 X 中的 x，有 h(x) = c(x)。
一个支持概念学习的算法需要：
- 训练数据（通过过去的经验来训练我们的模型）
- 目标概念（通过假设来辨别数据对象）
- 实际数据对象（用于测试模型）
归纳性的学习假设
正如我们前面所讨论的，概念学习的最终目标是确定一个与目标概念 C 在实例集 X 上相同的假设 H，并且唯一可用的信息是 C 在 X 上的值。我们的算法可以确保它与训练数据相匹配。换句话说：
“如果发现任何假设在预估目标函数时远远超过了一个足够大的训练实例集合，那么它也将同时远远超过其他未观测的实例”。
例如，一个人去看电影是基于四个具有两个值（真或假）的二进制特征：
- 有钱
- 有空闲时间
- 在假期
- 有待处理的工作 (pending work)
通过这些训练数据，我们可以将两个数据对象作为正实例，一个作为负实例：
- x1: <true, true, false, false> : +ve
- x2: <true, false, false, true> : +ve
- x3: <true, false, false, true> : -ve
假设符号
每个数据对象都代表一个概念和假设。我们认为这样的一个假设 <true，true，false，false> 是更具体的，因为它只覆盖了一个实例。一般来说，我们可以在这个假设中加入一些符号。我们有以下符号：
- ⵁ （一个拒绝所有实例的假设）
- < ? , ? , ? , ? > （全部接受）
- <true, false, ? , ? >（部分接受）
假设 ⵁ 会拒绝所有的数据实例。假设 < ? , ? , ? , ? > 会接受所有的数据实例。? 符号表示此特定特征的值不会影响结果。
所有可能的假设的总数是 (3 * 3 * 3 * 3) + 1 — 3，因为一个特征可能有 真，假或 ？以及一个拒绝所有的假设（ⵁ）。
从一般到具体
许多机器学习算法依托于一个概念，即将假设从一般到具体地排序。
- h1 = <true，true，？，？>
- h2 = <true，？，？，？>
任何由 h1 分类的实例也将被 h2 分类。我们可以说 h2 比 h1 更一般化。通过这个概念，我们便可以找到一个可以在整个数据集 X 上定义的一般化假设。
为了找到在 X 上定义的单个假设，我们可以使用比部分排序更一般化的概念。其中一种方法是从 H 的最具体的假设开始，并在每次它不能将正训练数据对象分类和观察为 “正” 时，都去一般化这个假设。
- Find-S 算法的第一步是从最具体的假设开始，这个假设可以表示为 h <- <ⵁ, ⵁ, ⵁ, ⵁ>。
- 选择下一个训练实例，并在这个实例上应用第 3 步。
- 观察数据实例。如果实例是 “否”，假设保持不变，选择下一个训练实例，再次运行步骤 2。反之，我们进行第 4 步。
- 如果实例是 “正”，并且我们发现我们的初始假设太过于特殊（如果它不包括当前的训练实例），则我们需要更新我们当前的假设。这个操作可以通过当前假设和训练实例的成对连接（逻辑和操作）来完成。 如果下一个训练实例是 <true, true, false, false>，并且当前假设是<ⵁ, ⵁ, ⵁ, ⵁ>，那么我们可以直接用新假设代替我们现有的假设。 如果下一个 “正” 训练实例是 <true, true, false, true>，并且当前假设是 <true, true, false, false>， 那么我们可以执行成对连接。通过当前假设和下一个训练实例，并将 ? 放在结合的结果是 “否”的地方，我们可以发现一个新的假设： <true, true, false, true> ⴷ <true, true, false, false> = <true, true, false, ?> 现在，我们便可以用新的假设取代我们现有的假设： h <-<true, true, false, ?>
- 重复第 2 步，直到有更多的训练实例出现。
- 一旦没有更多的训练实例，则当前的假设便是我们想要找的那个。如此，便可以用最后的那个假设来判断真实的对象。
Find-S 算法的局限性
用于概念学习的 Find-S 算法是机器学习最基本的算法之一，但它也具有如下的不足和缺点：
- 没有办法确定最终假设（Find-S 找出的）是否是唯一一个与数据一致 (consistent) 的假设。
- 不一致 (inconsistent) 的训练实例会误导 Find-S 算法，因为它忽略了 “负” 数据实例。一个能检测训练数据不一致的算法是更好的选择。
- 一个好的概念学习算法应该能够回溯对找到的假设的选择，以便能够逐步改进所得到的假设。但不幸的是，Find-S 不能提供这样的方法。
许多局限性都可以通过一个被称之为概念学习的最重要的算法来消除，它便是：候选删除算法 (candidate elimination algorithm)。
在我们的下一篇博客中，我们将用一个基础例子来解释 Find-S 算法。想要探索 Find-S 的实现，请查看这个博客的下一部分（即将推出）。