统计机器学习导论 (一)

写在前面：

大家好，我是强哥，一个热爱分享的技术狂。目前已有 12 年大数据与 AI 相关项目经验， 10 年推荐系统研究及实践经验。平时喜欢读书、暴走和写作。

业余时间专注于输出大数据、AI 等相关文章，目前已经输出了 40 万字的推荐系统系列精品文章，强哥的畅销书「构建企业级推荐系统：算法、工程实现与案例分析」已经出版，需要提升可以私信我呀。如果这些文章能够帮助你快速入门，实现职场升职加薪，我将不胜欢喜。

想要获得更多免费学习资料或内推信息，一定要看到文章最后喔。

内推信息

如果你正在看相关的招聘信息，请加我微信：liuq4360，我这里有很多内推资源等着你，欢迎投递简历。

免费学习资料

如果你想获得更多免费的学习资料，请关注同名公众号【数据与智能】，输入“资料”即可！

学习交流群

如果你想找到组织，和大家一起学习成长，交流经验，也可以加入我们的学习成长群。群里有老司机带你飞，另有小哥哥、小姐姐等你来勾搭！加小姐姐微信：epsila，她会带你入群。

第一章统计机器学习导论

这一章我们先简要介绍一下什么是统计机器学习。熟悉机器学习的同学们可以直接跳到第二章，在那里我们将介绍半监督学习。

例 1.1. 在一次星际探索中，你到达了一颗太阳系外的行星，并受到了居住在那里的外星小绿人的欢迎。你观察了周围 100 个绿色小人的体重和身高，并且你根据观察的测量值绘制了一张图表，如下图 1.1 所示。你能从这组数据中得到什么结论？

图 1.1：来自太阳系外行星的 100 个小绿人的体重和身高。每个绿点都是一个实例，分别由两个特征表示: 体重和身高。

这是一个经典的机器学习场景的案例（当然除了小绿人部分）。利用这些数据，我们可以完成许多任务: 根据这些小绿人的身高和体重将他们分组，或者识别出他们中身高或体重属于极端值的个人（可能数据是错误的），还能根据其中一个测量值去预测另一个测量值，等等。在我们探讨这类机器学习任务之前，先来了解一些定义。

1.1 数据

定义 1.2. 实例。实例 x 表示一个特定的对象。实例通常用一个 D 维特征向量 

来表示，其中每个维度被称为特征。特征向量的长度 D 被称为特征向量的维数。

特征表示是对物体的一个抽象的表达，它本质上忽略了不被该特征所表示的其他所有信息。例如，两个有着相同体重和身高，但名字不同的小绿人，由于只使用了体重、身高特征，这两个名字不同的小绿人是无法区分的。这里需要注意，我们用粗体的 x 表示整个实例，

 表示 x 的第

 个特征。在小绿人这个例子中，一个实例指一个特定的绿色小人; 特征向量由

 个特征组成:其中

 为体重，

 为身高。特征也可以是离散值。当有多个实例时，我们将使用

 来表示第

 个实例的第 

 个特性。

定义 1.3. 训练样本。训练样本是实例

 的集合，也是机器学习的输入。假设这些实例是潜在分布 

 的独立样本，其中

 是未知的。我们用

 来表示，其中 i.i.d. 代表独立同分布。

在我们的例子中，训练样本由

 个实例组成，它们是

。训练样本是我们给予学习算法的某种“经验”，算法可以利用它进行学习。然而，所学到的“知识”可能存在变化或偏差。这一章，我们介绍了两种基本的学习范式:无监督学习和监督学习。

 无监督学习

定义 1.4. 无监督学习。无监督学习适用于有 n 个实例的训练样本

。没有“老师”来监督应该如何处理单个实例——这是无监督学习的定义。常见的无监督学习任务包括:

 聚类，聚类的目标是将 n 个实例分成不同的小组;

 异常点检测，它的目标是识别出个别与大多数非常不同的实例;

 降维，即在保持训练样本的关键特征的同时，用一个较低的维数特征向量来表示每个实例。

在无监督学习任务中，聚类是与本书最相关的内容，我们将对此进行更详细的讨论。

定义 1.5. 聚类。聚类将

分成 k 个类或者说 k 个小组。其中，相同类中的实例是相似的，不同类中的实例是不同的。类的数量 k 可以由用户指定，也可以从训练样本本身推断出来。

回到我们之前的列子，在图 1.1 中的小绿人数据中，你能找到多少个类? 可能 k = 2，k = 4，或者更多。如果没有进一步的假设，这两种都是可以接受的。不同于监督学习(下一节将介绍)，这里没有老师告诉我们每个类中应该有哪些实例。

有很多聚类算法。这里为了使无监督学习具体化，我们引入了一种特别简单的方法——凝聚层次聚类（hierarchical agglomerative clustering）。

算法 1.6.  凝聚层次聚类

输入：一组训练样本

；一个距离函数 d( )。

1. 首先，将每个实例放在它自己的类中(称为单例类：singleton cluster)。

2. 当（类的数量> 1 ）时，进行如下运算：

3.     找出最接近的一对类 A, B，即它们将距离 d(A, B)最小化。

4.     合并 A, B 形成一个新的类。

输出：一个二叉树，它包含整个训练样本，并且显示了类从单例到根类逐渐合并的过程。

这个聚类算法很简单。唯一未指定的是距离函数 d()。如果 xi,xj 是两个单例类，那么定义 d(xi,xj)的一种方法是取两者之间的欧氏距离：

我们同样需要定义两个非单例的类 A，B 之间的距离。这有多种可能:它可以被定义为 A 和 B 之间最近的一对点之间的距离、最远的一对点之间的距离或者某个平均距离。为简单起见，我们将使用第一个方法，也称为单链接（single linkage）:

我们不需要将树完全生长直到只剩下一个类: 当 d()超过某个阈值时，或者类的数量达到预定的 k 时，聚类算法可以在任何点停止。

图 1.2 分别展示了 k = 2,3,4 时的分层凝聚聚类结果。这些类看起来确实不错。但是由于没有关于如何对每个实例进行聚类的信息，因此很难客观地评估聚类算法的结果。

图 1.2：100 个小绿人数据中，k = 2,3,4 时的分层凝聚聚类结果。

监督学习

假设你现在发现你的外星客人们有性别的区分：男或女（所以后续他们将不会统一被称为小绿人）。你现在可能会比较感兴趣如何从身高体重去预测他们性别。相似的，你也可能希望通过身高体重去预测它们是青少年，还是成年人。我们需要一些定义来解释如何完成这些任务。

定义 1.7.标记（label）。标记 y 是对实例 x 的期望预测。

标记可能来自一组有限的值，例如，{‘女’，‘男’}。这些不同的值称为类（classes）。常用整数编码类，例如，‘女’ = −1, ‘男’ = 1，因此 y∈{−1,1}。这种编码通常用于二元(两个类)标记，这两个类通常分别被称为负类和正类。对于两个以上类的问题，传统的编码方法是 y∈{1，…， C}，其中 C 是类的数量。通常来说，这种编码方式不能表示类中的结构。也就是说，用 y = 1 和 y = 2 编码的两个类并不一定比用 y = 1 和 y = 3 编码的类更接近。标记也可以采用自然数连续值。例如，人们可以尝试根据小绿外星人的身高和体重预测他们的血压。

在监督学习中，训练样本由一对一对的样本组成，每一对包含一个实例 x 和一个标记 y:

。我们可以把 y 看作是一位老师在 x 上做的标记，因此才有了监督学习这个名字。这样的(实例，标记)对被称为有标记的数据，而没有标记的实例(如在无监督学习中)被称为无标记的数据。现在我们开始定义监督学习了。

定义 1.8.监督学习。设实例的定义域为

，标签的定义域为

，设

为实例和标签

上的(未知)联合概率分布。给定一组训练样本

,监督学习在某个函数族

中训练函数

，目标是用

预测未来数据 x 上的真实标签 y。其中

。

根据标签 y 的定义域，监督学习问题将进一步被分为“分类”和“回归”:

定义 1.9.分类。分类是值域

 为离散集的监督学习问题。函数

 被称为分类器。

定义 1.10.回归。回归是值域

 为连续集的监督学习问题。函数

 被称为回归函数。

到底什么是好的

 呢？根据最优化问题的定义，要满足如下公式：

argmin’的意思是“找到使上式中右边公式的值最小的那个 f”。

是从分布 P 随机抽取的测试数据的期望。不熟悉这一符号的读者可以参阅附录 A。

是一个损失函数，它确定了损失或影响，即当作出与真实值 y 不

同的预测值 f(x)时的损失或影响。稍后我们将讨论一些典型的损失函数。注意，我们将注意力限制在了一些函数族

上，这主要是出于计算方面的原因。如果我们去掉这个限制并考虑所有可能的函数，那么得到的

 就是贝叶斯最优预测器，即平均来说是最优的。对于分布 P，在进行预测时,该函数可能产生的损失最小。

被称为贝叶斯误差。然而，贝叶斯最优预测器在一般情况下可能不在

中。我们的目标是找出

让它尽可能接近贝叶斯最优预测器

值得注意的是，潜在分布 P(x,y)对我们来说是未知的。因此，我们不可能直接找到

，甚至我们不可能测量任何预测器 

 的效果。这就是统计机器学习的根本困难所在:从有限的训练样本推广到所有看不见的测试数据，这就是归纳。

一个看似合理的近似法是使用训练样本的误差来评估 f 的效果。即用训练样本的平均值代替未知期望:

定义 1.11.训练样本误差。给定训练样本

，训练样本误差为

对于分类问题，一个常用的损失函数是 0-1 损失

如果

（即

 预测了一个不同于

 的类），则

的值为 1，反之为 0。

对于回归问题，我们常用的损失函数是平方损失：

其他的损失函数将在本书后面遇到时加以讨论。

通过选取

最大限度地减少训练样本误差可能是非常好的策略。然而，这个策略也有缺陷:这样选择的

会过度拟合训练样本，也就是说，它会学习到样本的噪音。也即学习过程超越了

 和

 之间的真实关系。这样一个过度拟合的预测器会在测试集上有比较小的误差，在测试未知数据上，它可能表现得不太好。机器学习的一个子领域：计算学习理论，它研究过拟合的问题。它在训练样本误差和真实误差之间建立了严格的联系，这些联系包括“Vapnik-Chervonenkis 维”或“Rademacher 复杂性”等形式化的描述复杂度的概念。 我们将在 8.1 节中进行简明的讨论。根据计算学习理论，一个合理的学习策略意在寻找“近似”最小化训练样本误差的

，同时对

 进行正则化，使其在某种程度上不太复杂。感兴趣的读者可以在书目注释中找到参考文献。

要估计 f 的预测能力，可以使用标记实例的一个单独的样本，称为测试样本:

。在训练期间，测试样本没有被使用，因此它提供了对预测能力的忠实(无偏差)估计。

定义 1.12.测试样本误差。使用损失的分类问题对应的测试样本误差为：

损失的分类问题对应的测试样本误差为：

使用平方损失的回归问题对应的测试样本误差为：

在本书的其余部分，我们将重点放在分类上，因为它在半监督学习研究中很普遍。本书讨论的大多数思路也适用于回归问题。

作为监督学习方法的一个具体例子，我们现在介绍一个简单的分类算法:k 最邻近算法 （ k-nearest-neighbor，kNN）.

算法 1.13.  kNN 分类器。

输入：训练数据

；距离函数 d()

; k 个近邻；测试实例

。

在距离 d()

下，找到 k 个训练实例

，最接近

。

1. 在距离 d()

下，找到 k 个训练实例

，最接近

。

2. 将

的大多数类作为

输出。

作为一个 D 维特征向量，测试实例

可以被视为 D 维特征空间中的一个点。分类器给特征空间中的每个点分配一个标签。这将特征空间划分为不同的决策区域，每个区域中的点具有相同的标签。分隔这些区域的边界称为分类构建的决策边界。

例 1.14. 让我们来看看两个涉及绿色小外星人的分类任务。图 1.3(a)是第一个任务：根据体重和身高进行性别分类。图中这些符号是训练数据。每个训练实例都有一个标签:女性(红色十字)或男性(蓝色圆圈)。1NN 分类器的决策区域显示为白色和灰色。图 1.3(b)是第二个任务：在相同的训练实例样本上进行年龄分类。训练实例现在有不同的标签:青少年(红色的十字)或成人(蓝色的圆圈)。决策区域如图所示。请注意，对根据不同的分类目标进行分类的相同训练实例来说，决策边界可能有很大不同。当然，这是监督学习独有的特性，因为无监督学习根本不使用任何特定的标签集。

图 1.3:从 100 个绿色小外星人的训练样本中，根据性别或年龄进行分类，其中显示了 1 个最近邻的决策区域。

在这一章中，我们介绍了统计机器学习，他是本书其余部分的基础。我们介绍了无监督和监督学习的一些基础知识，以及具体的例子。在下一章中，我们将概述介于这两者之间的半监督学习。后续章节将分别介绍不同类型的半监督学习算法。