机器学习构成三要素之模型

模型:机器学习的输出

Posted by Xiaosheng on February 26, 2017

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

模型是为解决某个既定问题而从数据中学习到的,因而它是机器学习中最核心的概念。因为机器学习的适用范围非常广泛:分类、回归、聚类、关联规则的分析等等,所以针对一个问题,通常有大量的机器学习模型可供选择。数学家、计算机科学家等各行业的人士都发现了解决这些问题的途径,他们纷纷运用自己特定领域的知识来解决问题,因而使得这些模型背后的原理也不尽相同。

虽然机器学习的模型多种多样,但在它们的背后,我们依然可以观察到一些公共的主题。在下文中,我们将对以下三种模型展开讨论:

  • 几何模型(geometric model)
  • 概率模型(probabilistic model)
  • 逻辑模型(logical model)

注:上面这种划分并非严格“互斥”,有时某种模型可以从几何和概率两个角度来解释。

1 几何模型

1.1 决策面

实例空间(instance space)是由所有可能的实例(即样本)所构成的集合,无论它们是否存在于已有的数据集中。通常该集合具有一定的几何结构,例如,若所有特征都是数值型的,则可将每个实例视为笛卡尔坐标系中的一个点。几何模型是借助于一些几何概念(如线、平面及距离)直接在实例空间中构建的,例如,线性分类器即为一个几何分类器。笛卡尔实例空间的维数与特征的维数相同,可能是十维、百维、千维甚至更高,这样的高维空间超过了我们的想象力,在机器学习中却极为常见。那些可以运用于高维空间的几何概念通常都带有前缀“超”(hyper-),例如,在一个未指定维数的空间中,决策面通常被称为超平面(hyperplane)

如果存在某个线性决策面能够将两类样本分离,则称所给的数据集是线性可分的(linearly seperable)。通过线性分类器我们知道,线性决策面可用方程 $\boldsymbol{w}\cdot\boldsymbol{x}=t$ 来表示,其中 $\boldsymbol{w}$ 是一个与决策面垂直的向量,$\boldsymbol{x}$ 为决策面上任意一点,$t$ 代表决策阈值。其中,向量 $\boldsymbol{w}$ 可看成是由反例“质心” $\boldsymbol{n}$ 指向正例“质心” $\boldsymbol{p}$ 的向量 $\boldsymbol{p}-\boldsymbol{n}$,假设 $P$ 为一个由 $n$ 个正例构成的集合,则可将其质心定义为 $\boldsymbol{p}=\frac{1}{n}\sum_{x\in P}x$,同理可求得 $\boldsymbol{n}$。只要设定恰当的决策阈值 $t$,便可用一个从向量 $\boldsymbol{p}-\boldsymbol{n}$ 中间穿过的决策面将正例和反例分离。这种分类器称为基本线性分类器(basic linear classifier),它的优点在于简单,因为 $\boldsymbol{w}$ 可表示为样本的线性组合。

注:由于数据中通常都含有噪声,实际中线性可分往往无法实现,除非数据本身非常稀疏。

但是,由于能够分离线性可分数据的决策面并不唯一,因而决策面也有无数种的选择。一种的很自然的选择是优先考虑能够产生“大间隔”(large margin)(决策面与距其最近实例之间的距离)的分类器,例如支持向量机(support vector machine)便是一种强大的线性分类器,它寻找的是一个能够产生尽可能大的分类间隔的决策面。

1.2 距离

机器学习中另一个极为有用的几何概念是距离(distance)。如果两个实例之间的距离很小,意味着二者的特征值相似,这样邻近的实例就可能被分到同一类或属于同一个簇(cluster)。在笛卡尔坐标系中,距离可用欧氏距离(Euclidean distance)来度量,它定义为两数据点 $\boldsymbol{x}$ 和 $\boldsymbol{y}$ 沿各坐标轴距离平方之和的平方根:$\sqrt{\sum_{i=1}^d(x_i-y_i)^2}$。

欧式距离用向量符号可表示为 $||\boldsymbol{x}-\boldsymbol{y}||=\sqrt{(\boldsymbol{x}-\boldsymbol{y})\cdot(\boldsymbol{x}-\boldsymbol{y})}=\sqrt{\boldsymbol{x}\cdot\boldsymbol{x}-2\boldsymbol{x}\cdot\boldsymbol{y}+\boldsymbol{y}\cdot\boldsymbol{y}}=\sqrt{||\boldsymbol{x}||^2-2||\boldsymbol{x}||\cdot||\boldsymbol{y}||\cos\theta+||\boldsymbol{y}||}$,其中 $\theta$ 表示 $\boldsymbol{x}$ 与 $\boldsymbol{y}$ 之间的夹角。

下面介绍一种非常简单的基于距离的分类器——最近邻分类器(nearest-neighbour classifier)。为确定一个新实例所属的类别,可首先从内存中获取与该实例最相似的训练实例(即与待分类实例欧氏距离最小的训练实例),并将训练实例的类别赋予该实例。后来人们对这种简单又强大的分类器提出了许多改进方案,例如,可以找出与待分类实例最相似的 $k$ 个训练实例,并由这 $k$ 个近邻依据其所属类别进行投票,从而确定新实例的类别;或依据到待分类实例距离的倒数来对每个近邻实例的投票进行加权;等等。这些方法的共同点是预测具有区部性,因为决策都依据近邻的少量实例,而非通过由整个数据集构建的全局模型到处。

欧氏距离与点集的均值存在天然的联系:给定点集的均值实际上是一个满足到该集合中所有点的欧氏距离平方和最小的点。因此,可用一组近邻数据点的均值作为它们的范例(exemplar)。假定我们希望通过聚类将数据划分到 $K$ 个簇中,并同时对聚类中心给出了初始估计。那么我们只需将每个点分配到与其距离最近的聚类中心所在的簇中,并重新计算每个簇的均值作为该簇新的聚类中心,重复这个过程直到每个簇都不再发生变化。这种聚类算法称为$K$ 均值聚类(K-means)。最常见的初始化策略是随机初始化,即通过随机猜测给出 $K$ 个聚类中心的位置。即使初始状态与实际情况存在偏差也无大碍,当算法历经若干次迭代后,这种偏差会迅速得到修正。

注:欧氏距离可能会对离群点(outlier)较敏感,我们还可以采用其他距离,如曼哈顿距离(Manhattan distance,又称街区距离),这种距离为两点沿坐标轴方向的距离之和:$\sum_{i=1}^d|x_i-y_i|$。

2 概率模型

之前在《机器学习概述》中介绍的贝叶斯分类器便属于概率模型的范畴。这类模型基于下列观点:令 $X$ 为已知变量(如实例的特征),$Y$ 为目标变量(target variable,如实例所属的类别),机器学习则负责对 $X$ 和 $Y$ 之间的依赖关系建模。

2.1 后验概率

对于特定的实例,由于 $X$ 已知,而 $Y$ 可能未知,因此我们对条件概率 $P(Y\mid X)$ 的取值特别感兴趣。例如,$Y$ 指示邮件是否为垃圾邮件,而 $X$ 表示邮件中是否包含“保健品”和“抗衰老”,则我们感兴趣的条件概率可表示为 $P(Y\mid 保健品,抗衰老)$。“保健品”和“抗衰老”为两个布尔变量,共同构成特征向量 $X$。由于对该形式条件概率的使用发生在观测到特征 $X$ 之后,因此它被称为后验概率(posterior probability)。例如,对一封包含短语“保健品”和“抗衰老”的邮件进行分类,我们只需查找相应的概率值 $P(Y=垃圾邮件\mid 保健品=1,抗衰老=1)$,如果该值大于 0.5 ,则将其判为垃圾邮件。这种依据 $X$ 和后验概率 $P(Y\mid X)$ 来预测 $Y$ 的方法称为决策规则(decision rule)

下面是一个后验概率的示例:

保健品 抗衰老 $P(Y=垃圾邮件\mid保健品,抗衰老)$ $P(Y=普通邮件\mid保健品,抗衰老)$
0 0 0.31 0.69
0 1 0.65 0.35
1 0 0.8 0.2
1 1 0.4 0.6

“保健品”和“抗衰老”均为布尔型,代表邮件中是否包含该词;$Y$ 为类变量,其值域为 {垃圾邮件,普通邮件}。

2.2 似然函数

实际中,我们更容易接触到的是大量由似然函数 $P(X\mid Y)$ 给定的各种各样的条件概率。例如对于一封包含 $X$ 的邮件,已知 $P(X\mid Y=垃圾邮件)=3.5\times10^{-5}$,$P(X\mid Y=普通邮件)=7.4\times10^{-6}$,这表明在垃圾邮件中观测到 $X$ 的概率大约是普通邮件的 5 倍。由此可导出如下的决策规则:如果似然比(likelihood ratio,即似然的比值)大于 1,则将该邮件判定为垃圾邮件。

注:对于给定的 $X$,$P(X\mid Y)$ 是一个从 $Y$ 到概率值的映射,但这些概率之和并不为 1,因此不构成一个 $Y$ 的概率分布,因而被称为“似然函数”而不是“似然分布”。关于似然函数的进一步说明,可以参见《似然函数》

那么在决策时应该使用后验概率还是似然?实际上,借助贝叶斯公式(Bayes’ Rule)可以实现二者的转换:

其中,$P(Y)$ 为先验概率(prior probability)。在分类问题中,先验概率传达的信息是在观测到数据 $X$ 之前每个类别的数据出现的可能。$P(X)$ 是数据 $X$ 出现的概率,它与 $Y$ 相互独立,且在多数情况下可以忽略。借助贝叶斯公式,可清晰表达出似然函数与后验概率之间的关系:

该规则被称为最大后验概率(Maximum A Posteriori,MAP)决策规则。如果先验分布为均匀分布(即 $P(Y)$ 的值不随 $Y$ 的变化而变化),则上式还可进一步简化为最大似然(Maximum Likelihood,ML)决策规则:

根据经验,如果忽略先验分布或假定它为均匀分布,则使用似然,否则使用后验概率。

似然函数在统计机器学习中扮演着极其重要的角色,可以说,似然函数是产生式模型(generative model) 的基石。所谓产生式模型是一种概率模型,依据它,我们可以对模型中所涉及的任意变量的值进行抽样。在统计机器学习学中,这种抽样估计方法称为最大似然估计

如果假设在同一个类中,各单词的似然相互独立,则可将联合似然分解为一组边缘似然(marginal likelihood)的乘积,例如:

实际上,这种独立性假设意味着某个单词在邮件中出现与否无助于了解其他单词的出现情况。上式右边的概率之所以被称为“边缘似然”,是因为它们是通过将联合分布中的某些变量实施“边缘化”(marginalising)运算的结果,例如 $P(保健品\mid Y)=\sum_{抗衰老}P(保健品,抗衰老\mid Y)$。

假设边缘似然如下表所示:

$Y$ $P(保健品=1\mid Y)$ $P(保健品=0\mid Y)$
垃圾邮件 0.4 0.6
普通邮件 0.12 0.88
$Y$ $P(抗衰老=1\mid Y)$ $P(抗衰老=0\mid Y)$
垃圾邮件 0.21 0.79
普通邮件 0.13 0.87

则似然比可计算如下:

很明显,第一例会被判为普通邮件,后三例都会被判为垃圾邮件。有人可能觉得这种将联合似然分解为边缘似然乘积的条件独立性假设过于简单,实际上,这种简化版的贝叶斯分类器被称为朴素贝叶斯(naive Bayes)分类器。这种“朴素”的思想正阐释了机器学习中一条重要的指导原则——任何事物都应尽可能地简单,而不是更加复杂。在统计学的语境下,该规则可归结为使用最简单的产生式模型来解决我们所面临的问题。

学习概率模型可归结为依据给定数据估计模型参数,而这通常是通过简单的计数来实现的。例如,对于垃圾邮件识别,模型参数就是词汇表中的每一个词 $w_i$ 在垃圾邮件和普通邮件中出现的概率 $\theta_i^\oplus$ 和 $\theta_i^\ominus$,凭借这些参数就可以计算出所有的似然:

为了估计 $\theta_i^\oplus$ 和 $\theta_i^\ominus$ 的值,需要一个已标识好“垃圾邮件”和“普通邮件”的邮件训练集。然后取出所有垃圾邮件,统计其中每个单词 $w_i$ 出现的次数,并用它除以垃圾邮件的总数,从而得到 $\theta_i^\oplus$ 的估值;同法,从普通邮件中获得对 $\theta_i^\ominus$ 的估值。

3 逻辑模型

3.1 特征树

逻辑模型更偏向于规则系统,它很容易翻译为人所理解的规则,例如 if 保健品=1 then Class=Y=垃圾邮件。这些规则很容易用树形结构来表示,如下图所示,我们称这种树为特征树(feature tree)。它的主要思想是利用特征以迭代方式不断划分实例空间。叶结点被标记为类别的特征树称为决策树(decision tree)

绘图1

上图的特征树中包含了两个布尔型特征,每个内部结点(或分裂结点)都用一个特征来标记,从每个分裂结点出发的边都用某个特征的值来标识,这样每个叶结点都对应若干特征值的唯一组合。运用多数类(majority class)的简单决策规则,可将上面树种的叶结点从左至右标为“普通邮件”、“垃圾邮件”、“垃圾邮件”。

回顾前面讨论过的朴素贝叶斯分类器,由于它使用了边缘似然,因而将实例空间划分的区域个数等于所有特征值组合的个数,可以将其想象为一个运用了完全特征树(complete feature tree)的模型。完全特征树囊括了所有的特征,且树的每一层都对应一个特征,如下图所示。由于最右端的叶结点仅覆盖了一个实例,所以这棵特征树存在着对数据过拟合的风险,所以上面那棵特征树是一个更优的模型。通常人们在训练决策树时,会运用剪枝(pruning)技术来将诸如此类的分类结点从树中剔除。

绘图2

3.2 特征列表

特征列表(feature list)是一棵二叉特征树,其特点是始终沿一个方向(向左或向右)产生分支。3.1 节第一张图中的树即为一棵左分支的特征列表。这种形式的特征列表可用嵌套结构的 if-then-else 语句来表示。例如,通过多数类来对第一张图中的叶子结点进行标记,可获得如下决策列表:

if 保健品 = 1 then Class = Y = 垃圾邮件
else if 抗衰老 = 1 then Class = Y = 垃圾邮件
else Class = Y = 普通邮件

逻辑模型通常具有形式不同但等价的表示,例如,上述模型也可表示为:

if 保健品 = 1 ∨ 抗衰老 = 1 then Class = Y = 垃圾邮件
else Class = Y = 普通邮件

if 保健品 = 0 ∧ 抗衰老 = 0 then Class = Y = 普通邮件
else Class = Y = 垃圾邮件

第一种等价形式通过析取运算(即逻辑或,记为 ∨)将原始决策列表中的两条规则进行了整合。第二个模型为对立类(即普通邮件类)构造了一个合取条件(即逻辑与,记为 ∧),将不满足该合取条件的邮件全部归类为垃圾邮件。

此外,还可以用如下的非嵌套规则来构造另一种等价模型:

if 保健品 = 1 then Class = Y = 垃圾邮件
if 保健品 = 0 ∧ 抗衰老 = 1 then Class = Y = 垃圾邮件
if 保健品 = 0 ∧ 抗衰老 = 0 then Class = Y = 普通邮件

该模型中,从根结点到每个叶结点的路径都被翻译为一条规则,且每对规则都至少存在一些互斥条件。然而,实际情况并非总是如此:不同规则之间可能会有一定程度的重叠。

(重叠规则)考虑如下规则:

if 抗衰老 = 1 then Class = Y = 垃圾邮件
if 张三 = 1 then Class = Y = 普通邮件

抗衰老 = 1 ∧ 张三 = 1 的区域,这两条规则出现重叠,做出矛盾的预测。此外,在 抗衰老 = 0 ∧ 张三 = 0 时,这两条规则都失效而无法做出预测。

树的学习算法通常采取自顶向下的方法。首要任务是在树的顶端找到一个好的特征来进行分裂,其主要目标是找到一个能够提高下一层结点纯度的分裂。“结点纯度”是指属于该结点的训练样本来自相同类别的程度。一旦学习算法找到这样一个特征,训练集就被划分为若干子集,且每个子集与该分裂产生的一个结点对应。对于每个子集,我们再次寻找一个好的特征进行分裂,如此往复进行下去。我们通常将这种不断把原问题分解为小的子问题的算法称为分治(divide-and-conquer)算法。当属于一个结点的所有训练样本都来自同一个类别时,分裂停止。

相关文章

  1. 《机器学习构成三要素之任务》
  2. 《机器学习构成三要素之模型》
  3. 《机器学习构成三要素之特征》