机器学习概述

简单的二元分类器

Posted by Xiaosheng on February 19, 2017

本文为 Peter Flach 所著《机器学习》的读书笔记,内容基本摘自原书,部分内容有修改。

1 线性分类器

我们也许尚未意识到,自己很可能已经是一名机器学习技术的普通用户了。例如,目前绝大多数电子邮件客户端都采用了识别和过滤垃圾邮件的算法。SpamAssasin 是一款非常流行的开源垃圾邮件过滤器,其工作机制是对每封到来的邮件进行多项“测试”来对其进行评分,如果邮件的综合得分不低于 5 分,SpamAssassin 就把它判定为垃圾邮件。那么 SpamAssassin 是如何确定每项测试分值的“权值”的呢?

假设现有一个规模较大的电子邮件“训练集”(training set),该集合中的所有邮件都带有人工标注的类别标签(“垃圾邮件”或“普通邮件”),且每封邮件的各项测试的分值均已给出。现在我们的目标是为每项测试找一个恰当的权值,以使所有垃圾邮件的得分均超过 5 分,而所有普通邮件的得分均低于 5 分。

下面通过一个简单的示例来说明解决这个问题的主要思想:

例1(线性分类)

假设我们只考虑两项测试。给定的邮件训练集有 4 封邮件,3 封普通邮件 1 封垃圾邮件,如下表所示。可以看出,对于垃圾邮件(行1),两项测试都成功;对一封普通邮件(行2),两项测试均失败;对其余两封普通邮件(行3、4),两项测试均只有一项成功。

显然,若将这两项测试的权值全部设为 4,就可以对上述 4 封邮件正确分类。可以将上述分类器表示为 $4x_1+4x_2>5$ 或 $(4,4)\cdot(x_1,x_2) > 5$。实际上,只要满足每个权值均小于 5 且总和超过 5,就能确保上述 4 封邮件被正确分类。

电子邮件 $x_1$ $x_2$ 垃圾邮件 $4x_1+4x_2$
1 1 1 1 8
2 0 0 0 0
3 1 0 0 4
4 0 1 0 4

背景知识1 用数学语言描述 SpamAssassin 的工作原理

若将对给定邮件的第 $i$ 项测试结果记为 $x_i$(如果测试成功,则 $x_i=1$,否则 $x_i=0$),并记第 $i$ 项测试的权值为 $w_i$,则邮件的总分为 $\sum_{i=1}^nw_ix_i$。注意,仅当 $x_i=1$ (即对该封邮件的测试成功)时,$w_i$ 才计入总分。若用 $t$ 表示阈值(即如果邮件总分超过 $t$,则将其判为垃圾邮件),则“决策规则”可表示为 $\sum_{i=1}^nw_ix_i>t$。可以看到,不等式左边部分对变量 $x_i$ 是线性的,如果 $x_i$ 的增量为 $\delta$,则总和的增量为一个不依赖于 $x_i$ 的数——$w_i\delta$。

借助线性代数知识,可对该决策规则符号做进一步简化。设 $\boldsymbol{w} =(w_1,\cdots,w_n)$,$\boldsymbol{x}=(x_1,\cdots,x_n)$,则上述不等式可简化为内积形式:$\boldsymbol{w}\cdot\boldsymbol{x}>t$。将该不等式修改为等式,就得到了用于判断邮件是否为垃圾邮件的“决策边界”(或“决策面”)方程:$\boldsymbol{w}\cdot\boldsymbol{x}=t$。不难看出,由于方程左边为线性项,所以由变量 $x_i$ 所张成的空间中,决策边界为一平面。向量 $\boldsymbol{w}$ 与该平面垂直,并指向垃圾邮件样本的方向。下图给出了数据点和决策面在 2D 空间中的可视化结果。

1

上图为 2D 空间中的线性分类示例,图中将正例(+)和反例(-)分离的直线(决策边界)方程为 $\boldsymbol{w}\cdot\boldsymbol{x}_i=t$,该式中 $\boldsymbol{w}$ 为一个与决策边界垂直的向量,其方向指向正例,$t$ 为决策阈值,而 $\boldsymbol{x}_i$ 对应于决策边界上的某一个点。特别地,$\boldsymbol{x}_0$ 的方向与 $\boldsymbol{w}$ 一致,故有 $\boldsymbol{w}\cdot\boldsymbol{x}_0= ||\boldsymbol{w}||\cdot||\boldsymbol{x}_0||=t$ ($||\boldsymbol{x}||$ 表示向量 $\boldsymbol{x}$ 的长度),因此决策边界可表示为 $\boldsymbol{w}\cdot(\boldsymbol{x}-\boldsymbol{x}_0)=0$。该形式在一些场合中使用时尤为方便,特别是这种符号能够更清晰地表达如下重要事实——决定决策边界位置的是 $\boldsymbol{w}$ 的方向,而非其长度。

上面向我们展示了 SpamAssassin 如何通过已有的正例和反例来学习识别垃圾邮件,如果能够预先获得更多的训练数据,SpamAssassin 的表现会更为优异。依据经验来提升性能几乎是各种形式的机器学习方法的核心,可以这样定义机器学习:机器学习是对依据经验提升自身性能或丰富自身知识的各种算法和系统的系统性研究。上述的例子中,“经验”对应一组正确标注的训练数据,而“性能”对应识别垃圾邮件的能力。

但一定要注意到,我们其实对算法在训练数据上的性能并不关心,毕竟我们已经知道其中哪些为垃圾邮件,我们真正关心的即将到来的邮件能否被正确分类。我们必须牢记,在训练数据上取得优异性能只是手段,而非目的。实际上,如果一味追求系统在训练数据上的性能,很容易造成一种貌似喜人,实则存在巨大隐患的现象——过拟合(overfitting)。

例2(过拟合)

假设你正在备战“机器学习”课程的考试,为了帮助复习,老师将历年真题及答案共享给了大家。一开始你还尝试自己求解答案再与参考答案进行比对,但做着做着就走火入魔,将全部时间都花在了机械地记忆答案上。如果即将到来的考试完全采用过去的考题,你一定能取得优异的成绩。然而,如果考试中出现了考察相同知识点,但表述完全不同的新题,那么你势必会因准备不足而得到低分。这种情况下,我们就说,你对历年真题产生了“过拟合”:机械记忆所获得的知识无法推广到新考题上。

推广性(generalization)(又称泛化性)可能是机器学习中最基础的概念。设想如果 SpamAssassin 从训练数据中提炼的知识在你的邮件中无法运用,你一定会选择其他的垃圾邮件过滤器。但过拟合并不是系统在新数据上表现不如意的唯一可能,另一种可能是 SpamAssassin 的作者在设定权值时使用的训练数据与你的邮件情况相差甚远。这类问题最容易的解决方案就是,选择与你邮件相似的样本作为训练数据,重新训练。这也正是机器学习最伟大的地方,它可以通过定制训练数据来自动适应不同的情况。

2 贝叶斯分类器

SpamAssassin 的测试看似并未对邮件本身的内容给予足够的关注,例如像“保健品”、“免费iPod”这样的短语都可以作为很好的垃圾邮件指示信号,而其他某些词汇(如只有朋友才使用的特定昵称)则指向普通邮件,许多垃圾邮件过滤器都运用了文本分类技术。通常,这些技术都会维护一个可作为垃圾邮件或普通邮件指示信号的词汇/短语表。

例如,假设我们从已有的邮件训练集上统计出,垃圾邮件中“保健品”出现的概率为 $\frac{4}{5}$,普通邮件中“保健品”出现的概率为 $\frac{1}{5}$。如果我们记 $P(保健品)$ 为邮件中出现“保健品”的概率,那么上面的结果可以记为 $P(保健品\mid 垃圾邮件)=\frac{4}{5}$ 和 $P(保健品\mid 普通邮件)=\frac{1}{5}$(可以参考下方的背景知识2)。很明显,“保健品”可以作为垃圾邮件的一个指示信号。

背景知识2 概率论基础

概率涉及描述“事件”结果的随机变量,这里的“事件”通常是以“假设”的形式出现,因此需要用估计的方法来得出其概率。例如有这样一个假设:英国有 42% 的公民支持现任首相。检验该假设的唯一方法是逐一询问每一位英国公民,但显然这是不可行的,因此我们转而抽取具有代表性的公民样本进行调查,该假设更准确的说法应为“支持英国现任首相的公民比例约为 42%”。注意,这些假设都是基于比例而形成的,对应于概率的相应假设则为“随机抽取一名英国公民,则该人支持现任首相的概率约为 0.42”。

条件概率 $P(A\mid B)$ 刻画的是当事件 $B$ 发生时,事件 $A$ 发生的概率。若记 $P(PM)$ 为随机抽到公民支持现任首相的概率,$P(PM\mid woman)$ 为随机抽到的女性公民支持现任首相的概率,则有 $P(PM\mid woman)=\frac{P(PM,woman)}{P(woman)}$,其中 $P(PM,woman)$ 为随机抽到的公民既支持现任首相同时为女性的“联合事件”的概率,而 $P(woman)$ 则表示随机抽到的公民为女性的概率。

其余有用的公式还包括 $P(A,B)=P(A\mid B)P(B)$ 和 $P(A\mid B)=\frac{P(A)P(B\mid A)}{P(B)}$ ,后者被称为“贝叶斯公式”。上述公式可推广到多随机变量的情形,如“概率链式法则” $P(A,B,C,D)=P(A\mid B,C,D)P(B\mid C,D)P(C\mid D)P(D)$。

若 $P(A\mid B)=P(A)$,即事件 $B$ 发生与否不影响事件 $A$ 的发生,则称事件 $A$ 与 $B$ 独立。上式的一个等价形式为 $P(A,B)=P(A)P(B)$。通常,概率相乘中蕴含着对应事件相互独立的假设。

假设我们收到的邮件中,平均每七封邮件中有一封垃圾邮件,这意味着下一封到来的邮件有 $\frac{1}{7}$ 的概率为垃圾邮件,记为 $P(垃圾邮件)=\frac{1}{7}$。由于我们已经知道垃圾邮件中“保健品”出现的概率为 $\frac{4}{5}$,普通邮件中“保健品”出现的概率为 $\frac{1}{5}$。所以运用贝叶斯公式可以得到:

进一步化简可以得到:

将对应的值代入可得:

又因为一封邮件要么为垃圾邮件,要么为普通邮件,所以 $P(垃圾邮件\mid 保健品)+P(普通邮件\mid 保健品)=1$,结合上式很容计算出 $P(垃圾邮件\mid 保健品)=0.4$、$P(普通邮件\mid 保健品)=0.6$,即如果一封邮件中出现“保健品”,那么该邮件为垃圾邮件的概率为 0.4。换言之,虽然该邮件出现了“保健品”,但是最保险的方式依然将其判定为普通邮件。

贝叶斯分类的好处是进一步的证据可在原有基础上使用。例如,假设通过统计发现,在随机抽取的垃圾邮件中“抗衰老”出现的概率为 0.75,而在普通邮件中出现概率为 0.2。现在假定待分类的邮件同时包含了“保健品”和“抗衰老”,运用贝叶斯公式可得:

进一步化简可以得到:

现在我们假设邮件中出现“保健品”和“抗衰老”的情况彼此独立,那么:

左右约去 $P(垃圾邮件)$ 得:

同理可得 $P(保健品,抗衰老\mid 普通邮件)=P(保健品\mid 普通邮件)P(抗衰老\mid 普通邮件)$。代入原式可得:

最后将对应的值代入:

与之前的计算方法类似,我们很容计算出 $P(垃圾邮件|保健品,抗衰老)=\frac{5}{7}$、$P(普通邮件|保健品,抗衰老)=\frac{2}{7}$,即如果一封邮件中同时出现“保健品”和“抗衰老”,那么该邮件为垃圾邮件的概率为 $\frac{5}{7}$,因而我么将其判定为垃圾邮件。

无需估计和操作联合概率使得处理大量(高维)随机变量成为可能。实际上,一个典型的贝叶斯垃圾邮件过滤器可能包含超过 10000 个词汇。所以我们使用的不是专家手工构造的“特征”,而是在规模较大的数据集上借助分类器来指出哪些特征是重要的,以及何种组合方式是最优的。

结语

至此我们已经接触了垃圾邮件识别中的两个机器学习案例,通常机器学习研究者称这样的任务为二元分类(binary classification)问题,因为其中涉及将不同的对象(电子邮件)划分为两个不同的类别——垃圾邮件或普通邮件。要完成该任务,需要将每封邮件转化为一组变量或特征。在 SpamAssassin 中,特征由专家人工设计,而在贝叶斯文本分类的例子中,特征的设计借助于一个规模较大的词汇表。

问题的关键在于如何运用这些特征将垃圾邮件与普通邮件区分开。我们所要做的是通过分析带有正确标注信息的邮件训练集,发现样本特征与其所属类别之间的联系(机器学习研究者通常称这种联系为模型)。

我们回顾一下上面介绍的两种分类器,可以看到:

  • 在 SpamAssassin 案例中,我们使用的决策规则具有如下形式:$\sum_{i=1}^nw_ix_i>t$,其中 $x_i\in{0,1}$(也称为“布尔”特征)用于指示对当前邮件的第 $i$ 项测试是否成功,$w_i$ 为从训练集中学习到的特征权值,$t$ 为决策阈值,得分高于该阈值的邮件将被判为垃圾邮件
  • 在贝叶斯文本分类的案例中,我们使用了一种形式为 $\prod_{i=1}^no_i>1$ 的决策规则,其中 $o_i=\frac{P(x_i\mid 垃圾邮件)}{P(x_i\mid 普通邮件)}$(1≤ $i$ ≤ $n$)为词汇表中每个单词 $x_i$ 在垃圾邮件和普通邮件中出现的概率之比,而 $o_0=\frac{P(垃圾邮件)}{P(普通邮件)}$ 为垃圾邮件和普通邮件的先验概率之比,这些值均需要从邮件训练集中进行估计。

可见,任务、模型及特征是机器学习的三大“原料”。可以这样概括:机器学习所关注的问题是使用正确的特征来构建正确的模型,以完成既定的任务。