在之前的博客中,我们讲到了一台机器通过机器学习所能完成的壮举,以及深入学习机器学习之前必备的数学知识。那么,在理解了机器学习的先决条件之后,就让我们迈着小而高效的步子,开始机器学习的成功之旅吧。
许多人常常思考,机器是如何从数据中学习,是如何预测未来的。诚然,我们正生活在一个很多人快速高效地工作于全球大数据技术的时代,但需要我们关注的并不仅限于拥有大量数据,我们还需要关注这些数据的高效运用,直到能找到其中的模式,并使用它们来预测未来和找出对策。
要想知道一台机器是如何从经历中学习并根据经历预测未来,我们首先需要了解的,是人脑的工作方式。一旦我们洞察了人脑解决问题的模式,就可以让机器以几乎相同的方式进行学习。并且,机器相对人脑更加不受限制,有更多可探索的地方。但是,机器学习是一个十分宽广的领域,并且存在很多可能性,所以,我们今天就从最简单的机器学习算法开始: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 上的值。我们的算法可以确保它与训练数据相匹配。换句话说:
“如果发现任何假设在预估目标函数时远远超过了一个足够大的训练实例集合,那么它也将同时远远超过其他未观测的实例”。
例如,一个人去看电影是基于四个具有两个值(真或假)的二进制特征:
通过这些训练数据,我们可以将两个数据对象作为正实例,一个作为负实例:
每个数据对象都代表一个概念和假设。我们认为这样的一个假设 <true,true,false,false> 是更具体的,因为它只覆盖了一个实例。一般来说,我们可以在这个假设中加入一些符号。我们有以下符号:
假设 ⵁ 会拒绝所有的数据实例。假设 < ? , ? , ? , ? > 会接受所有的数据实例。? 符号表示此特定特征的值不会影响结果。
所有可能的假设的总数是 (3 * 3 * 3 * 3) + 1 — 3,因为一个特征可能有 真,假或 ?以及一个拒绝所有的假设(ⵁ)。
许多机器学习算法依托于一个概念,即将假设从一般到具体地排序。
任何由 h1 分类的实例也将被 h2 分类。我们可以说 h2 比 h1 更一般化。通过这个概念,我们便可以找到一个可以在整个数据集 X 上定义的一般化假设。
为了找到在 X 上定义的单个假设,我们可以使用比部分排序更一般化的概念。其中一种方法是从 H 的最具体的假设开始,并在每次它不能将正训练数据对象分类和观察为 “正” 时,都去一般化这个假设。
用于概念学习的 Find-S 算法是机器学习最基本的算法之一,但它也具有如下的不足和缺点:
许多局限性都可以通过一个被称之为概念学习的最重要的算法来消除,它便是:候选删除算法 (candidate elimination algorithm)。
在我们的下一篇博客中,我们将用一个基础例子来解释 Find-S 算法。想要探索 Find-S 的实现,请查看这个博客的下一部分(即将推出)。