机器学习——绪论　机器学习概述

你也许尚未意识到，自己很可能已经是一名机器学习技术的普通用户了。例如，目前绝大多数电子邮件客户端都采用了识别和滤除垃圾邮件（spam① e-mail）的算法。早期的垃圾邮件过滤器（spam filter）采用的是基于人工规则（如正则表达式）的模式匹配方法。但人们很快发现，这样的系统不仅难以维护，而且也缺乏灵活性。这很容易理解，因为绝对意义上的“垃圾”邮件是不存在的。有些邮件对某些人来说是“垃圾”，但对其他人来说则可能极有价值。如今，机器学习技术在邮件分类领域已得到了广泛应用，其所带来的自适应性和灵活性远非早期方法可以企及。 SpamAssassin 是一款非常流行的开源垃圾邮件过滤器，其工作机制是依据一组内置规则或“测试”（Spam①ssassin 的专用术语）为每封到来的邮件进行评分。如果某封邮件的得分不低于5分，则SpamAssassin 会自动为其添加一个“junk”（即垃圾邮件）标签，并在该邮件标头（emailheader）中添加一段简要说明。下面展示了我收到的某封邮件的简要说明。 图 在该图中，从左到右依次为某项测试的评分、测试标识符以及包含对邮件相关部分引用的简短描述。可以看到，不同测试给出的评分可能为负（表明该邮件为普通邮件而非垃圾邮件）也可能为正。由于该邮件的综合得分为5.3 分，表明该邮件有可能是一封垃圾邮件。这封邮件实际上传达的是来自中介服务器的一条通知，即另外一封邮件( 其得分高达14.6 分) 被认定为垃圾邮件而被拒收。由于该条“退信”消息中包含了原始邮件，故继承了后者的某些特征，如低文本- 图像比（text-to-image ratio），所以它的得分超过了给定的阈值 — 5 分。 —————————— ① spam 这个词原本是香料火腿（spice ham）的缩写，该肉制品之所以“声名狼藉”，完全要归咎于电视剧《蒙提•派森的飞行马戏团》 （Monty Python’s Flying Circus）在1970年某一集中的讽刺。 —————————— 下面再举一例。这次所涉及的是一封我本人期盼已久的重要邮件。但不幸的是，我后来在“垃圾箱”中找到了它。 图 这封邮件事关我与研究小组的一名同事提交到欧洲机器学习会议（ECML）和欧洲数据库中的知识发现原理与实践会议（PKDD）的一篇文章（自2001 年起，这两个会议一直是联合举办）。虽然这两个会议在2008 年所使用的域名ecmlpkdd2008.org 对每位机器学习研究者来说几乎是耳熟能详，但却因连续出现了11 个“非元音字符”而引起了SpamAssassin 的怀疑！这个例子表明对于不同的用户，某项SpamAssassin 测试的重要性可能不同。机器学习是一种可为用户量身打造程序的绝佳方法。 至此，你一定十分希望了解SpamAssassin 确定每项测试分值或“权值”的依据到底是什么。我要告诉你的是，这正是机器学习的用武之地。假设现有一个规模较大的电子邮件“训练集”（trainingset），该集合中的所有邮件都带有人工标注的类别标签，即“垃圾邮件”或“普通邮件”，且每封邮件的全部测试结果均已给出。我们的目标是为每项测试找到一个恰当的权值，以使所有垃圾邮件的得分均超过5 分，而所有普通邮件的得分均低于5 分。在本书后面的章节中，你将接触到大量适于解决该问题的机器学习技术。下面我们先通过一个简单的示例来阐述这些方法的主要思想。 例1( 线性分类)　假设我们只考虑两项测试。给定的邮件训练集中共有4 封邮件，其中含3 封普通邮件和1 封垃圾邮件，如表1 所示。可以看出，对于垃圾邮件（对应表中第1 行），两项测试都是成功的；对其中一封普通邮件（表中第2 行），两项测试均失败；而对其余两封普通邮件（对应表中第3、4 行），两项测试均只有一项成功。显然，将这两项测试的权值全部设为4，便可以对上述4 封邮件正确分类。依据“背景知识1”所引入的数学符号，我们可将上述分类器表示为4x1 + 4x2 > 5 或(4, 4) . (x1, x2) > 5。实际上，采用任意介于2.5 和5 之间的权值都能够确保仅当两项测试均 成功时，邮件的最终得分才高于阈值5。我们甚至可以考虑为两项测试分配不同的权值（只要满足每个权值均小于5，且总和超过5 即可），尽管也许很难从训练数据看出这种做法的合理性。 表1 供SpamAssassin使用的一个规模较小的训练集。x1 和x2 两列分别对应两项测试的结果，第4列表明哪些邮件为垃圾邮件，而最右列则表明如果将5作为判别函数4x1+4x2 的阈值，可轻易地将垃圾邮件分离出来 图 背景知识1　用数学语言描述SpamAssassin 的工作原理 图 图 你可能会感到疑惑，上面这些内容究竟与学习有什么关系? 毕竟，这只是一个数学问题。你这样想似乎有些道理，但我们完全可以换一种说法 —“ SpamAssassin通过正例和反例来学习如何识别垃圾邮件”，这听起来似乎也有道理。况且，如果能够预先获得更多的训练数据，SpamAssassin 的表现会更为优异。依据经验提升性能几乎是各种形式的机器学习方法的核心。下面我们给出机器学习的一般定义：机器学习是对依据经验提升自身性能或丰富自身知识的各种算法和系统的系统性研究。在上述SpamAssassin 的例子中，“经验”对应一组正确标注的训练数据，而“性能”对应识别垃圾邮件的能力。图2 给出了机器学习如何介入垃圾邮件分类这项任务的原理性示意。在不同的机器学习任务中，“经验”往往具有不同的形式，如对错误的纠正、实现某个目标后的奖励等。此外还需注意，与人类的学习类似，在某些任务中，机器学习的目的可能不是针对特定任务取得性能提升，而是在整体上使知识得到提升。 图２ 我们已经看到，一个机器学习问题往往存在多种解决方案，即便对于像例1 这样的简单问题也不例外。这就引发了一个很重要的问题：我们如何从众多候选方法中做出抉择？考虑这个问题的一种方式是意识到，我们其实对算法在训练数据上的性能并不关心，毕竟我们已经知道其中哪些邮件为垃圾邮件。我们真正关心的其实是即将到来的邮件能否被正确分类。这听起来有点像“先有鸡还是先有蛋”的问题 — 要想知道一封邮件是否被正确分类，必须事先获知其类别；如果我们已经知道该邮件的类别，则无须再进行分类决策。但是，我们必须牢记在训练数据上取得优异性能只是手段，而非目的。实际上，如果一味追求系统在训练数据上的性能，很容易造成一种貌似喜人、实则存在巨大隐患的现象 — 过拟合（overfitting）。 例2（过拟合）　假设你正在备战“机器学习101”课程的考试。为了帮助复习，Flach 教授将历年真题及答案共享给了大家。做题时，你一开始还尝试自己求解答案，然后与参考答案进行比对。但不幸的是，做着做着你就走火入魔了，将全部时间都花在了机械地记忆参考答案上。如果即将到来的考试完全采用过去考过的题目，你一定会取得非常优异的成绩。然而，如果考试中出现了考察相同知识点、但具有不同表述形式的新题目，那么跟老老实实复习相比，你势必会因准备不足而得到低得多的分数。这种情形下，我们就可以说，你对历年考试产生了“过拟合”：机械记忆所获取的知识无法推广到新考题上。 推广性（generalization）① 可能是机器学习中最基础的概念。如果SpamAssassin 从训练数据中提炼的知识能够在你的邮件中得到运用，你一定十分满意；否则，你可能会寻找替代SpamAssassin 的垃圾邮件过滤器。但过拟合并不是系统在新数据上表现得不尽人意的唯一可能原因。另一种可能的原因是SpamAssassin 程序的作者设定权值时使用的训练数据不符合你电子邮件的实际情况。幸运的是，这类问题是存在解决方案的 — 你可选用符合你邮件特点的不同样本作为训练数据。如果可能的话，你甚至可以使用自己实际收到的垃圾邮件和普通邮件作为训练集。机器学习是一项能够改变软件行为以自动适应你个人情况的伟大技术，目前已有许多垃圾邮件过滤系统允许用户为其定制训练数据。 —————————— ① 也称为泛化能力。— 译者注 —————————— 可见，当一个问题存在多种解决方案时，你必须谨慎选择以避免产生过拟合。本书后面的章节将向你介绍一些选择方法。现实中，我们有时也会遇到另一种情形，即无法找到一种在训练数据上表现良好的解决方案。这种情况下，我们该如何应对？例如，假设例1 中的第2 封邮件（两次测试均失败）是垃圾邮件，则任意一条直线（决策面）都无法将垃圾邮件和普通邮件分离（你可在由x1 和x2 组成的2D坐标系中画出这四封邮件所对应的点来验证这一说法）。在这种情况下，存在几种可能的解决方案。一种是无视这一点，认为第二封邮件可能是非典型的或存在标注错误（也称噪声）；另一种方案则是尝试描述能力更强的分类器。例如，我们可引入垃圾邮件的第二条决策规则：除已有的4x1 + 4x2 > 5 外，我们再添加规则4x1 + 4x2 < 1。注意，采用这种方法会学习出不同的阈值，甚至不同的权值向量。一般仅在训练数据集容量较大、能够保证可靠地学到这些参数的情况下才会选择这种方法。 SpamAssassin 风格的线性分类很适合入门讲解。但你有必要了解，它并不是机器学习中的唯一方法，否则本书的篇幅就要短得多了。如果学习的任务不仅包括测试的权值，而且包括测试本身，我们该如何应对？如何确定文本- 图像比是不是合适的测试？最重要的是，我们如何首先设计出这样的测试？令人欣慰的是，这些都是机器学习最擅长解决的。 你可能已经注意到，截至目前，SpamAssassin 的测试看似并未对邮件本身的内容给予足够的关注。诚然，像“Viagra”（万艾可/ 伟哥）、“free iPod”（免费iPod）或“arm your accountdetails”（确认你的账户细节）这样的词汇或短语都可作为很好的垃圾邮件指示信号，而其他某些词汇( 如只有朋友才使用的特定昵称) 则指向普通邮件。为此，许多垃圾邮件过滤器都运用了文本分类技术。通常，这些技术都会维护一个可作为垃圾邮件或普通邮件指示信号的词汇/ 短语表。例如，假设我们在4 封垃圾邮件和1 封普通邮件中发现了“Viagra”这个词。当新邮件到来时，如果它包含了“Viagra”这个词，我们会推断它有4 : 1的几率成为垃圾邮件，或者说该邮件为垃圾邮件的概率为0.8，为普通邮件的概率为0.2（可参考“背景知识2”来回顾概率论中的一些基本概念）。 　 背景知识2　概率论基础 图 然而实际情况往往并非如此简单，因为我们还需考虑垃圾邮件的出现频率。假设在我所收到的邮件中，平均每七封邮件中有一封垃圾邮件（真这样就好了！），这就意味着下一封到来的邮件有1 : 6的几率为垃圾邮件。这个几率不算很高，但也不能无视。如果我获知该邮件中包含了“Viagra”，由于该词在垃圾邮件中出现的几率是普通邮件的4 倍，所以在下结论之前需要将这两个几率综合考虑。稍后你将看到，借助贝叶斯公式，只需将这两个几率相乘，即(1 : 6)  (4 : 1) = 4/6，便可得出该邮件是垃圾邮件的概率为0.4。换言之，尽管该封邮件的正文中出现了“Viagra”，最保险的方式仍然是将其判定为普通邮件。这显然不合常理，不是吗？ 要理解上述内容，需要明确我们刚才所做的是对两种彼此独立的证据进行融合，其中一种证据刻画的是垃圾邮件的出现概率，而另一种证据则描述了“Viagra”这个词的出现概率。这两种证据形成两股互相牵制的力量，这意味着对二者相对强弱的评价极其重要。前面给出的数字告诉我们：为了推翻垃圾邮件相对稀少这个假设，需要至少6 : 1 的几率，但“Viagra”的出现几率的估计量仅为4 : 1，不足以决定性地倒向“垃圾邮件”的方向，也就无法确保该邮件为垃圾邮件。它所起的作用是削弱“该邮件为普通邮件”这个结论的力度( 因为该邮件为普通邮件的概率从6/7 = 0.86 降至了6/10 = 0.60)。 贝叶斯分类的好处是进一步的证据可在原有基础上使用。例如，假设包含短语“blue pill”的邮件为垃圾邮件的几率的估计量为3 : 1（即在包含该短语的邮件中，垃圾邮件的数量是普通邮件的3 倍），并假定待分类邮件同时包含了“Viagra”和“blue pill”，则综合考虑二者得到的几率为4 : 1乘以3 : 1，即12 : 1，这足以压倒垃圾邮件1 : 6的低出现几率。这样，该邮件为垃圾邮件的总几率即为2 : 1，从而其为垃圾邮件的概率由原先的0.4 增加至0.67。 无须估计和操作联合概率使得处理大量( 高维) 随机变量成为可能。实际上，一个典型的贝叶斯垃圾邮件过滤器或文本分类器的词汇表可能包含了10 000 来个词汇①。所以，我们并不使用由领域专家手工构造的、被认为具有相关性和可预测性的一小组“特征”，而是在规模较大的数据集上借助分类器来指出哪些特征是重要的，以及何种组合方式是最优的。 —————————— ① 实际上，多个词构成的词组通常会分解为其构成词，这样P(blue pill) 便可用P(blue)P(pill) 来近似。 —————————— 需要注意的是，在将与“Viagra”和“blue pill”关联的几率相乘时，我们隐式地做出了二者彼此独立的假设。这显然值得商榷，因为在获知某封邮件包含短语“blue pill”后，如果又从邮件中发现了词语“Viagra”，我们肯定不会感到意外。该现象可用如下的概率语言来表述： 概率P(Viagra | blue pill) 接近于1； 因此联合概率P(Viagra, blue pill) 接近于P(blue pill)； 因此，与两个短语“Viagra”和“blue pill”关联的垃圾邮件的几率不会和与“blue pill”关联的垃圾邮件的几率存在明显差异。 换言之，将两个几率相乘是将本质上同一的信息统计了两次。乘积几率12 : 1 几乎必然是一种过高的估计，实际的联合几率可能不会超过一个比其明显低的几率值，如5 : 1。 这样看来，我们好像陷入了一种困境。为了避免重复计数，就需要考虑一些短语联合出现的情况；而为了保证这些联合概率的可计算性，在定义该问题时我们又必须假设各变量相互独立。这样，我们所期望的看起来更类似于基于规则的模型，例如： （1）如果邮件中包含了“Viagra”，则将垃圾邮件的几率估计为4 : 1； （2）否则，如果它包含了短语“blue pill”，则将垃圾邮件的几率估计为3 : 1； （3）否则，将垃圾邮件的几率估计为1 : 6。 上述第一条规则涵盖了所有包含“Viagra”的邮件（无论这些邮件是否包含短语“bluepill”)，因此不会出现重复计数的情况；第二条规则利用“otherwise”（否则）子句，仅涵盖了包含短语“blue pill”但不包含单词“Viagra”的邮件；而第三条规则涵盖了其余所有邮件，即那些既不包含“Viagra”也不包含“blue pill”的邮件。 这种基于规则的分类器的本质是“具体情况具体分析”，而非按照统一的方式对全部邮件进行处理。针对不同的情况，它们只采用最相关的一组特征。所涉及的各种情况可通过如下几种嵌套特征来定义。 1. 该邮件中是否包含单词“Viagra”? （a）如果为真，该邮件中是否包含短语“blue pill”？ i.如果为真，将垃圾邮件的几率估计为5 : 1。 ii.如果为假，将垃圾邮件的几率估计为4 : 1。 （b）如果为假，该邮件中是否包含单词“lottery”？ i.如果为真，将垃圾邮件的几率估计为3 : 1。 ii.如果为假，将垃圾邮件的几率估计为1 : 6。 这四种情况均通过逻辑条件来描述，如“邮件包含单词‘Viagra’，但不包含短语‘bluepill’”。在本书后面的章节中，你将了解到目前已有众多有效且高效的算法可专门用于辨识那些预测能力最强的特征组合，以及将它们组织为规则或决策树。 至此，我们已经接触了垃圾邮件识别中三个实用的机器学习案例。通常，机器学习研究者称这样的任务为二元分类或两类分类（binary classification）问题，因为其中涉及将不同对象( 电子邮件) 划分为两个不同的类别 — 垃圾邮件或普通邮件。要完成该任务，需要将每封电子邮件转化为一组变量或特征。在SpamAssassin 这个例子中，所用到的特征是由专门研究垃圾邮件过滤的专家人工设计的，而在贝叶斯文本分类的例子中，特征的设计则借助于一个规模较大的词汇表。问题的关键在于如何运用这些特征将垃圾邮件与普通邮件区分开。我们所要做的是通过分析带有正确标注信息的电子邮件训练集，发现样本特征与其所属类别之间的联系（机器学习研究者通常称这种联系为模型）。 图 可见任务、模型及特征是机器学习的三大“原料”。图3 展示了这三大要素之间的关系。如果与图2 进行比对，我们会发现模型占据着中心地位，其内涵绝不仅限于某个分类器的由特征定义的一组参数。这里的灵活性恰是我们在统一看待机器学习用到的形形色色的模型时所需要的。关于“任务”（task）和“学习问题”（learning problem），我们有必要强调一下二者的区别：任务是通过模型来完成的，而学习问题则通过能够产生模型的学习算法来解决。虽然该区别已被广泛认可，但有时人们使用的术语可能并不完全一致。例如，你可能会发现其他研究者会使用术语“学习任务 ”（learning task）来表示上述的“学习问题”。 图３ 综上，我们可以这样来概括：机器学习所关注的问题是使用正确的特征来构建正确的模型，以完成既定的任务。我有意使用“原料”这个词来强调这三个要素形式的多样性。为了制作出一道“佳肴” — 机器学习研究者通常称之为应用( 即为完成某个实际任务，借助各种机器学习方法和来自相应任务领域的数据所构造的模型)，我们往往需要慎重地进行选择和搭配( 组合)。如果没把手头的原料完全吃透，想成为一名优秀厨师那是白日做梦。这道理在机器学习领域也同样适用。从第2 章开始，我们将深入探讨任务、模型及特征这三个要素。而在下一章中，我会呈上大量案例，先从享受一份小的“特色菜”开始，以期帮助你对这些“原料”有更多品味。