01 引言
Contents
01 引言¶
1.1 机器学习是什么？¶
我们正在进入大数据时代。举例来说，在网络上有近 40 万亿张网页；每分钟有近 100 小时时长的视频上传至 Youtube； 10 世纪人的基因组，每一个都有长度达 \(3.8×10^9\) 的基本基因对，其测序工作已经被不同的实验室完成；沃尔玛每小时完成 1M 的交易，并且拥有包含超过 \(2.5×10^{15}\) 字节信息的数据库。
数据泛滥提出了对数据进行自动分析的要求，这便是机器学习解决的问题。本书定义 机器学习 (Machine Learning ) 为一系列可以自动挖掘数据中潜在模式的方法，并且利用发现的模式去预测未来的数据，或者在不确定的情况下执行其他决策。
本书基于如下观点：“解决此类问题的最好方法是使用概率论中的工具”。
概率论可应用在任何涉及 不确定度 的问题上。在机器学习中，不确定度以很多形式出现，例如：在给定历史数据前提下，未来最有可能出现什么数据？ 能够解释某些数据的最好模型是什么？在机器学习中所使用的概率论相关方法与统计学领域有密切关联，但两者的侧重点和一些术语存在些许不同。
本书将介绍多种概率模型，它们分别适用于不同类型的数据和任务。本书也会描述各种机器学习算法并且使用这些算法解决一些问题。本书的目的并不是简单地提供一本关于机器学习的工具书，反之，本书希望透过概率模型和概率推断视角来展示关于此领域的统一观点。尽管我们会关注算法的计算效率，但是将这些算法更好地应用在真正大规模数据集上的细节部分最好还是参考其他的书籍。
需要注意的是，即使某人拥有表面上十分庞大的某个数据集，但对于特定感兴趣的问题，其有效数据量可能是相当小的。事实上，在很多领域中，数据都呈现出一种 长尾 ( long tail ) 效应，这意味着只有一小部分事件频繁发生，而大部分事件很少发生。例如，常用的单词往往是词汇表中很小一部分 ( 比如「the」和「and」 ) ，大多数单词 ( 比如「pareidolia」 ) 是很少使用的。类似的，有些电影和书非常有名，但大部分并非如此。本书 第 2.4.7 节 将进一步讨论长尾效应。长尾效应导致一个结果：只需要较少数据就可以预测或者理解大部分行为，而本书则主要讨论处理此类数据集的技术。
1.1.1 机器学习的分类¶
机器学习一般分为两大类：监督学习和非监督学习。
（1）监督学习
在 预测性 ( predictive ) 或者 监督 ( supervised ) 学习方法中，模型的目的是：在给定的已标记数据集 ( 指对每一个样本 \(\mathbf {x}\)，都赋予一个标签值 \(y\) ) \(\mathcal {D}=\{( \mathbf {x}_i,y_i ) \}_{i=1}^N\) 的情况下，通过学习得到一个从输入 \(\mathbf {x}\) 到输出 \(y\) 的映射。其中 \(\mathcal {D}\) 被称为 训练集 ( training set ) ，\(N\) 为训练集中样本的数量。
从最简单的情况出发，假设训练集中的输入 \(\mathbf {x}_i\) 是一个 2 维向量，向量的一个分量代表身高，另一分量代表体重，则这两个分量被称为两个 特征 ( features ) 、属性 ( attributes ) 或者 协变量 ( covariates ) 。但通常情况下，输入 \(\mathbf {x}_i\) 会是比较复杂的结构化对象（比如一张图片，一个句子，一条邮件，一个时间序列，一个分子形状，一个图表等），会涉及非常多分量。例如：一幅 4000 像素 x 4000 像素的灰度照片，会涉及 \(4000^2\) 个特征（或属性、协变量）。
类似的，模型的输出（或响应） 变量的形式理论上也可以是多样的，但在大部分方法中，都假设 \(y_i\) 仅代表一个变量（即不是向量）。此时又分两种情况：
\(y_i\) 是一个
类别 ( categorical )或者名义 ( nominal )变量，变量取值于一个有限的集合 \(y_i\in\{1,...,C\}\) ( 如：男性或女性类别 ) ，此时对应的问题被称为分类 ( classification )或者模式识别 ( pattern recognition )问题；\(y_i\) 是一个属于实数域的标量 ( 如：个人收入 )，此时对应问题被称为
回归 ( regression )问题 。回归的一个变种是定序回归 ( ordinal regression )，该情况出现在需要输出的标签之间具备一些自然的顺序时（如：分数等级 \(A-F\)）。
Note
注： 统计学中常见的几种数据类型：定类数据（ 或名义数据）、定序数据和定量数据。
（2）非监督学习
机器学习中的另一类方法被称为 描述性 ( descriptive ) 或者 非监督 ( unsupervised ) 学习方法。在这种情况下，模型给定的输入为 \(\mathcal {D}=\{\mathbf {x}\}_{i=1}^N\)，模型的目标是在数据中找到「感兴趣的模式」。有时此方法也称 知识发现 ( knowledge discovery ) 。非监督学习是一个不够明确的问题，因为我们并没有被告知应当发掘什么类型的模式，所以没有明确的评价标准可使用 ( 与之相对，监督学习可以将模型的预测值与观测的真实值作对比进而给出评价 ) 。
（3） 强化学习
机器学习中还有一类被称为 强化学习 ( reinforcement learning )的方法。该方法在某种程度上很少被使用。该方法有助于学习当偶尔出现奖励或惩罚信号时，模型应该如何行动或表现 ( 例如：考虑一个儿童如何学习走路 )。 不过强化学习的内容已超出本书范畴，我们会在 第 5.7 节 讨论决策论的内容，那是强化学习的基础。
1.2 监督学习 ( Supervised learning )¶
我们先从监督学习开始对机器学习展开探索，因为它在实践中被广泛使用。
1.2.1 分类任务¶
分类的目的是得到一个从输入 \(\mathbf {x}\) 到输出 \(y\) 的映射，其中 \(y\in\{1,...,C\}\)，\(C\) 为类别的数量。如果 \(C=2\)，则被称为 二分类 ( binary classification ) ( 在这种情况下，通常假设 \(y\in\{0,1\}\) ) ； 如果 \(C>2\)，则被称为 多分类 ( multiclass classification ) 。如果类别标签之间彼此互不排斥 ( 如：是否“高”和是否“强壮” ) , 则称之为 多标签分类 ( multi-label classification ), 当然更好的方式是将其理解为预测多个相关的二元分类问题 ( 即 多变量输出模型 ) 。当使用术语「分类」时，通常是指输出单个变量的多分类问题，除非做出特别说明。
一种关于上述问题的形式化表达是 函数近似 ( function approximation ) 。假设存在一个未知函数 \(f\)，使得 \(y=f ( \mathbf {x} )\)，那么我们的目的就是在给定的含标签训练集上估计函数 \(f\) 的形式，然后使用得到的函数 \(f\) 进行预测 \(\hat {y}=\hat {f} ( \mathbf {x} )\)。 ( 注：使用符号 \(^\) 表示估计量 ) 。模型的最终目的是对新输入（即还未观测到的输入）预测其输出 (即 泛化 generalization )。
1.2.1.1 例子¶
举一个分类问题的小例子，考虑如 图 1.1 ( a ) 所示的问题。有两类对象，分别对应标签 0 ( no ) 和 1 ( yes ) 。输入为彩色的形状，每个输入通过 \(D\) 个属性或特征进行描述，所有输入的属性可以被存储在一个大小为 \(N\times D\) 的矩阵 \(\mathbf {X}\) 中，如 图 1.1 ( b ) 所示。输入特征 \(\mathbf {x}\) 的取值可以是离散的、连续的或者两者的组合。在训练集中，除了输入外还包含一个标签向量 \(\mathbf {y}\)。
图 1.1 中的测试用例为一个蓝色新月、一个黄色圆环和一个蓝色箭头。这些用例在训练集中都没有出现过，因此我们希望模型具备一定的泛化能力，使得在新数据上也能表现良好。例如：一个合理猜测是蓝色新月应该属于类 1，因为在训练集中所有蓝色形状都被标记为了 1。黄色圆环很难被分类，因为训练集中有些黄色被标记为 1，有些黄色被标记为 0，有些圆被标记为 1，有些圆被标记为 0，因此很难说黄色圆环应该属于哪一类。类似情况在蓝色箭头上一样适用。
图 1.1 左图：一些有彩色形状标记的训练样本，以及 3 个未标记的测试用例。右图：将训练数据表示为 \(N × D\) 设计矩阵。第一行代表特征向量 \(\mathbf{x}_i\) ，最后一列是标签 \(y_i \in \{ 0，1\}\)。
1.2.1.2 概率性预测的必要性¶
为处理如上文所提及的预测结果比较模糊的情况 ( 比如黄色圆环属于哪一类 ) ，可以利用概率论的相关知识。
在给定训练集 \(\mathcal {D}\) 的情况下，输入向量 \(\mathbf {x}\) 所属的类别 \(y\) 服从的分布由 \(p ( y|\mathbf {x},\mathcal {D} )\) 表示。通常情况下，此概率分布的取值有 \(C\) 种 ( 即 \(y\) 的取值有 \(C\) 种），但是在二分类问题中，\(y\) 的取值只有两种，此时只需要关心 \(p ( y=1|\mathbf {x},\mathcal {D} )\) 的取值即可，因为存在约束条件 \(p ( y=1|\mathbf {x},\mathcal {D} ) +p ( y=0|\mathbf {x},\mathcal {D} ) =1\) 。
在我们的符号表达中：
明确了概率分布以测试输入 ( 即新输入 ) \(\mathbf {x}\) 和训练集 \(\mathcal {D}\) 为条件，形式上表现为 \(\mathbf {x}\),\(\mathcal {D}\) 被放置在符号「|」的后面。注意：该表达形式隐藏了概率分布所基于的模型，因为如果模型在上下文语境中已经明确时，在公式中一般不明确书写。当预测基于多种模型时，比较完整的写法会显式地表达出概率分布对模型的条件依赖 \(p ( y|\mathbf {x},\mathcal {D},M )\)，其中 \(M\) 表示模型类型。
如果已知上文中所提及的概率分布 \(p ( y|\mathbf {x},\mathcal {D} )\)，那么总可以使用下式作出最好的预测，并将其作为真实的标签输出：
式中的估计量 \(\hat {y}\) 是输入 \(\mathbf {x}\) 最有可能的类别标签，对应分布 \(p ( y|\mathbf {x},\mathcal {D} )\) 的 众数 ( mode ) ( 众数指一个概率分布中发生频率最高的情况 ) ； 上式又被称为 最大后验估计 ( MAP estimate ) 。 使用最有可能的输出作为最终选择从直觉上是正确的，我们将在 第 5.7 节 给出更加正式的证明。
现在回到之前的例子中，假设对黄色圆环的标签存在估计值 \(\hat {y}\)，但其概率值 \(p ( \hat {y}|\mathbf {x},\mathcal {D} )\) 远小于 1， 也就是说，我们对这个选择并不是很确定。 那么此时相较于给出这个不信任的答案，直接指出「我不知道」可能会更好，这在医疗或者金融等需要规避风险的领域尤其重要。
关于上文中「我不知道」的回答，有一个十分有趣的应用。有一款电视节目秀 Jeopardy，在该节目中，参赛者需要解决各种单词拼图以及回答一些简单问题，如果回答错误，他们会失去奖励。2011 年，IBM 开发了一款名为 Watson 的计算机系统，该系统打败了该节目的人类冠军。在 Watson 使用的一系列有趣技术中，与当前讨论最相关的技术就是：该系统包含一个模块，用于估计系统对答案的置信程度。只有当置信度足够高时，系统才会选择给出答案。
另一个需要估计不确定度的重要应用就是在线广告。Google 有一个系统 SmartASS ( add selection system ) ，它根据你的检索历史以及其他用户及广告特征来估计你点击某个广告的可能性。此概率被称为 点击率 ( click-through rate, CTR ) ，它可以用来最大化预期收益。最近的畅销书 《The Signal and the Noise》 给出了许多案例，说明在进行预测时，使用概率性的方法多么重要，无论是政治博弈还是天气预报。
1.2.1.3 实际应用¶
分类是在机器学习中最广泛的应用形式，已被用来解决很多有趣但很难解决的问题。接下来，将给出更多的例子：
（1） 文本分类和垃圾邮箱过滤
在 文本分类 ( document classification ) 问题中，目标是将一个文本分类成 \(C\) 类中的某一种，此处文本可以是一个网页或者一个邮件，从概率角度分析，即需要计算 \(p ( y=c|\mathbf {x},\mathcal {D} )\) ) ，其中 \(\mathbf {x}\) 为文本的向量化表示。在文本分类问题中，有一类问题被称为 垃圾邮件过滤 ( email spam filtering ) ，在其中 \(y\) 的取值可以是 1 ( 垃圾邮件 ) 或者 0 ( 非垃圾邮件 ) 。
大部分分类器都假设输入向量 \(\mathbf {x}\) 的大小是固定的。一种将变长文本转化为固定长度特征向量的方法是 词袋法 ( bag of words ) 。我们将在 第 3.4.4.1 节解释更多细节，其基本思想是：
如果单词 \(j\) 在文本 \(i\) 中出现，则 \(x_{ij}=1\)。如果使用这种表达方式，我们将得到一个大小为「文本数量 × 单词数量」的二值矩阵 ( 指矩阵中的每一个元素只能取 0 或者 1 ) ，图 1.2 为图示。本质上，文本分类问题退化成一个在“位”中寻找细微模式变化的问题。举例来说，垃圾信息文本中包含单词 “buy”,”cheap”,”viagra” 等的可能性很大。在练习 8.1 和 8.2 中，你将有机会使用各种分类技术解决垃圾过滤问题。
图 1.2 20个新闻组数据中大小为 \(16242 x 100\) 的子集。为清楚起见，只显示 \(1000\) 行。每行是一个文档（表示为一个词袋位向量），每列是一个单词。红线分隔了4个类，分别是（按降序）comp、rec、sci、talk( USENET 的组标题)。可以看到，有一些词的子集，它们的存在与否影响了类别。数据可从http://cs.nyu.edu/~roweis/data.html 获得。
（2） 花朵分类
图 1.3 给出了分类问题的另一个例子，其目的是区分三种不同的鸢尾花，分别为 setosa, versicolor 和 virginica。 幸运的是，我们不需要直接对图像进行分类，一个植物学家已经提取了对分类有用的 4 种特征：萼片（sepal）的长度和宽度，花瓣（petal）的长度和宽度。这种选择合适特征的工作被称为 特征提取 ( feature extraction ) ，是特别重要而且困难的任务。大部分机器学习方法使用人工选择的特征，后面将讨论一些可以从数据中自动获取好特征的方法。如果如图 1.4 那样绘制鸢尾花数据的散点图，不难发现，仅仅通过花瓣的长度或者宽度就可以将 setosas 与其他两种区分开。然而，要想将 versiclor 与 virginica 区分开却有一点难度，在两者之间做出任何决定都至少要基于两个特征。
Note
注： 在应用机器学习方法之间，对数据进行探索性分析十分有用，比如绘制数据图。
图 1.3 三种鸢尾花：setosa 、versicolor 和 virginica 。资料来源: http://www.statlab.uni-heidelberg.de/data/iris/。
图1.4 鸢尾花数据的可视化散点图。对角线绘制了 4 个特征的边缘直方图，偏离对角线的为其他特征对的散点图。红色圆圈= setosa，绿色菱形= versicolor，蓝色星形= virginica。
（3） 图像分类和手写识别
下面的问题更困难些，直接对图片进行分类。我们可能需要对一张图片进行整体上的分类，比如：它是室内还是室外？它是水平还是垂直的？它是否包含一条狗？ 此类对图像整体进行分类的任务被称为 图像分类 ( image classification ) 。
Note
注： 请注意图像分类任务和语义分割任务的区别。此外，遥感图像处理领域常用的图像分类任务，通常指语义分割任务。
图像分类任务中有一种情况比较特殊，即图片中仅包含单独的手写数字和字母，此时可就具象为 手写识别 ( handwriting recognition )任务。在该领域中的标准数据集是 MNIST， 该数据集包含 60000 张训练图片和 10000 张测试图片，每张图片上为不同人书写的数字 0-9。图片尺寸为 28×28，灰度值范围为 0:255。图 1.5 ( a ) 展示了一些样例图。
许多一般性的分类方法会忽略输入特征中的结构信息（比如空间布局），因此也可以处理类似于 图 1.5 ( b ) 中的数据。该图中的数据与 1.5 ( a ) 中的数据一致，只是随机打乱了特征的排列。这种灵活性既有优势 ( 因为方法通用 ) 又有弊端 ( 因为忽略了较为明显的信息源 ) 。
图 1.5 (a) 前9个测试 MNIST 灰度图像。 (b) 与 (a) 相同，但特征随机排列。两个版本的数据分类性能相同（假设训练数据以相同的方式排列）。
（4） 人脸检测和识别
一个更加困难的任务是在一张图片中发现目标，这被称为 目标检测 ( object detection ) 或者 目标定位 ( object localization ) 。典型案例就是 人脸检测 ( face detection ) 。
一种解决这类问题的方法是在不同的位置，以不同尺度和方向，将图片分割成许多互相重叠的小区域，然后通过分析这些小区域中是否存在类人脸的纹理特征来进行分类。这被称为 滑动窗口检测器 ( sliding window detector )。系统将返回那些拥有人脸概率足够高的位置。
图 1.6 给出了一个例子。这种人脸检测系统内置于大部分的现代数字相机；被检测到的人脸位置被用来决定自动聚焦点。另一个应用是在谷歌街景系统中为保护隐私自动模糊人脸。
在找到人脸位置后，可以进行 人脸识别 ( face recognition ) ，也就是估计一个人的身份 ( 见 图 1.10 ( a )) 。此时，类别的数量非常大，同时使用的特征与人脸检测也不一样：对于人脸识别问题，脸与脸之间细微差别（如：发型区别），可能对确定身份起着决定性作用，但对于人脸检测问题而言，系统反而会尽量忽略细节信息（不仅要忽略，还要具备旋转、缩放、平移不变性） ，而只关注脸与非脸之间的区别。
图 1.6 人脸检测示例。(a) 输入图像(墨菲一家，照片拍摄于2010年8月5日)。 (b) 分类器的输出，其检测出不同姿态的 5 张脸。分类器在 1000 张人工标记的人脸和非人脸图像上进行训练，然后应用于测试图像中一组密集的重叠图像块，其中只有包含人脸概率足够高的图像块被返回。
1.2.2 回归任务¶
回归与分类很像，不同之处在于，回归所输出的变量是连续的。
图 1.7 展示了一个简单例子：我们拥有一个实值输入 \(x_i \in \mathbb {R}\)，和一个相应的输出 \(y_i\in\mathbb {R}\)。考虑使用两种模式去匹配这些数据：一条直线和一条二次函数曲线。基于这个基本问题，还可以扩展出很多新问题，例如：高维输入、异常值、非光滑响应等。
以下是现实世界中的一些回归问题：
基于当前市场情况和一些其他辅助信息预测明天的股票价格；
预测 YouTube 上一个观看特定视频的观众年龄；
给定机器人各电机的控制信号，预测机器人手臂末端执行器在三维空间中的位置；
根据多种不同临床测量数据预测前列腺特异性抗原在体内的数量；
使用天气数据、时间等信息预测某建筑内任意位置的温度。
图1.7 (a) 一维数据的线性回归。 （b）相同数据的 2 次多项式回归。
1.3 非监督学习¶
非监督学习的目标是发现数据中「有趣的结构」，这通常被称为 知识发现 ( knowledge discovery )。与监督学习方法不同，我们并没有被告知每个输入应该对应什么预期的输出。相反，我们将非监督学习任务作为 密度估计 ( density estimation ) 中的一种，即希望建立一个模型 \(p ( \mathbf {x}_i|\mathbf {\theta )}\)。
这个形式与监督学习中的概率表达存在两个方面的不同：
首先，非监督学习用 \(p (\mathbf {x}_i|\mathbf {\theta} )\) 代替了监督学习中的 \(p ( y_i|\mathbf {x}_i,\mathbf {\theta} )\)。即监督学习是条件概率密度估计，然而非监督学习是无条件概率密度估计。
其次，\(\mathbf {x}_i\) 通常是高维特征向量，因此非监督学习需要建立多变量的概率模型。而在大部分监督学习中，\(y_i\) 通常只是一个单独的变量，使用单变量的概率模型，大大简化了问题本身。 ( 我们将在第 19 章讨论多输出分类问题，其中将会看到多变量概率模型 )
非监督学习可以说是人类和动物学习的典型方法。相较于监督学习，非监督学习使用更加广泛，因为它不需要人为标记的数据。带标签数据不仅很难获得，而且具备的信息也相对较少，以至于难以用于估计复杂模型的参数。Geoff Hinton 是在 ML ( 机器学习 ) 领域著名的教授，他曾经说：
「 当我们学习观测事物时，没有人告诉我们正确的答案是什么 —— 我们只是在观测。通常情况下，你的母亲会说「那是一条狗」，但其所具备的信息是很少的。如果你获得一些信息，哪怕一秒钟只有一比特，那也是很幸运的。人类大脑的视觉系统拥有 1014 个神经连接。一个人的寿命为 109 秒。所以每秒钟学习一个比特的信息并没有用，你需要额外的 105 位信息。拥有如此多的信息的地方只有一个，那就是输入本身。——Geoffrey Hinton,1996。」
接下来，将描述一些在非监督学习中经典的例子。
1.3.1 发现聚类¶
作为非监督学习中的典型案例，考虑将数据聚类为 簇 ( clusters ) 。举例来说，图 1.8 ( a ) 绘制了一些 2 维数据，代表 210 个人的身高和体重。从图中可以发现，数据中好像存在不同的簇或者子群，尽管并不知道这些簇到底有多少个。假设 \(K\) 为簇的数目。我们首先需要估计簇数目的分布 \(p ( K|\mathcal {D} )\)。为简单起见，通常利用 \(p ( K|\mathcal {D} )\) 的众数作为估计量，即 \(K^*=\arg\max_Kp ( K|\mathcal {D} )\)。在监督学习中，我们会被告知预测值有多少个类别，但在非监督学习中，我们可以自由选择簇 ( 类 ) 的数量。
我们的第二个目标是预测某个数据点属于哪一个簇。令 \(z_i\in\{1,...,K\}\) 代表数据点 \(i\) 所归属的簇。 在概率模型中，\(z_i\) 又被称为隐变量或者潜变量，因为在训练集中从未见过 。我们可以通过计算 \(z_i^*=\arg\max_kp ( z_i=k|\mathbf {x_i|\mathcal {D}} )\) 来推测每个数据点所归属的簇。如如 图 1.8 ( b ) 所示，使用不同的颜色代表不同簇，其中假设 \(K=2\)。
本书主要关注 基于模型的聚类 ( model based clustering )方法 ，意味着我们会利用概率模型对数据进行拟合，而不是采用其他一些算法。模型方法的优势在于：可以客观的比较不同模型，并且在一些大规模系统中，可以将不同模型组合起来。
以下是在现实世界中一些聚类的应用：
在天文学中，Autoclass 系统通过对天体物理测量数据聚类，发现了一种新型恒星。
电子商务中经常会根据购买行为或搜索行为将客户聚类到不同簇中，然后向不同簇发送定制的广告。
在生物学中，流式细胞术数据通常聚类成组，以发现不同的细胞亚群。
图 1.8 (a)一些人的身高和体重。(b) 使用 \(K = 2\) 个类的可能聚类。
1.3.2 发现潜在因子¶
在处理维度特别高的数据时，通常需要将数据投影到低维空间中实现数据降维（ dimensionality reduction ），以获得数据的「本质」。一个简单例子如 图 1.9 所示，其中将三维数据投影到一个二维平面。这个二维的近似效果很好，因为大部分点都靠近该子空间。而将数据点映射到直线上则可以将数据降到一维空间，如 图 1.9 ( a ) 中红线所示，但这种近似的效果并不好。
图1.9 (a) 一组嵌入到三维空间的二维线性子空间点。红色实线是第一主组分方向。黑色虚线是第二个主组分方向。(b) 数据的二维表示。
降维背后的动力在于尽管数据是高维的，但可能只有少量主导因素，这些潜在主导因素被称为 潜在因子 ( latent factors ) 。举例来说，当对人脸图像进行建模时，可能只有少数潜在因子主导着不同图像的变化，例如：光线、位置、身份等，但是一张图像的维度却很高。图 1.10 给出了示例说明。
图 1.10 (a) 从 Olivetti 人脸数据库中随机选择的 25 幅 64 × 64 像素图像。(b) 平均值和前三个主成分基向量(特征面)。
将低维的特征表示作为统计模型的输入，往往会取得更好的预测精度。因为输入仅仅关注了数据的「本质」，排除了那些不必要特征。同时，低维表示可以加快最近邻目标的搜索，并且数据在二维空间的投影可以使数据更加可视化。
最常用的降维方法是 主元分析 ( principal components analysis, PCA ) 。在 PCA 中，观测到的是高维数据 \(\mathbf {y}\)，而不是低维的「起因」\(\mathbf {z}\)，模型具备形式 \(\mathbf {z}\rightarrow\mathbf {y}\) ，PCA 要做的是「反转这个箭头」，从观测到的高维数据 \(\mathbf {y}\) 推断出潜在的低维数据 \(\mathbf {z}\)。
降维（特别是 PCA），已经在很多领域得到应用：
生物学常用 PCA 来分析基因微阵列数据，以解释这样一个事实，即每次测量通常是许多基因的结果，这些基因由于属于不同的生物途径而在行为上相关联。
自然语言处理中常用一种
潜在语义分析的 PCA 变体进行文档检索 ( 见第 27.2.2 节) 。信号处理中常用
独立成分分析ICA( PCA 的一种变体 ) 将信号分离成不同的源 ( 见第 12.6 节) 。计算机图形学中常将运动捕捉数据投影到低维空间中，并用它来创建动画。有关处理此类问题的一种方法，请参见
第 15.5 节。
1.3.3 发现图结构¶
有时测量一组相关变量，是想要发现哪些变量之间最相关。这可以用图 \(G\) 表示，其中节点表示变量，边表示变量之间的直接依赖关系 ( 将在 第 10 章 讨论图模型时进行详细说明 ) 。然后我们可以从数据中学习这个图形结构，即计算 \(\hat {G}=\arg\max p ( G|\mathcal {D} )\) ) 。
与一般的非监督学习一样，学习稀疏图主要有两种目的：发现新知识 和 获得更好的联合概率密度估计。
现在我们分别给出一些例子：
学习稀疏图模型的大部分动机来自于系统生物学社区。例如，假设测量细胞中某些蛋白质的磷酸化状态 ( Sachs 等，2005 ) 。图 1.11 给出了一个从数据中学习到的图结构 ( 使用
第 26.7.2 节中讨论的方法 ) 。另一个例子，( Smith 等， 2006 ) 表明可以从时序脑电图数据中恢复某种鸟的神经“接线图”，恢复的结构与已知鸟类大脑该部分的功能连接紧密吻合。在某些情况下，我们对解释图结构不感兴趣，只是想用它来建模相关性并做出预测。例如：在金融投资组合管理中，对大量股票之间的协方差准确建模很重要。Carvalho and West 的研究表明，通过学习稀疏图，然后将其作为交易策略的基础，有可能跑赢大盘，比不利用稀疏图的方法赚更多钱。另一个例子是预测高速公路上的交通堵塞。Horvitz 等人描述了一个名为 JamBayes 的已部署系统，用于预测西雅图地区的交通流量，其预测是基于从数据中学习的图模型做出的。
图 1.11 使用图形套索 ( 第26.7.2节) 学习的稀疏无向高斯图模型，应用于一些流式细胞术数据 (from (Sachs et al. 2005))，该模型测量了 11 种蛋白质的磷酸化状态。
1.3.4 矩阵补全¶
有时我们会丢失数据，也就是说，某些变量的值因为某些原因缺失了。例如，进行了一项调查，有些人可能没有回答某些问题。或者有各种各样的传感器，其中一些失灵了。此时相应的设计矩阵中就会出现“孔”。这些缺失的条目通常由 NaN 表示，代表「Not A Number」。插补 ( imputation ) 的目的是推断出缺失项的合理值，这有时被称为 矩阵补全 ( matrix completion ) 。
下面给出一些示例应用程序：
（1） 图像修复
补全任务的一个有趣的例子是 图像修复 ( image inpainting ) 。目标是在一个具有真实纹理的图像中「填补」由于划痕或遮挡形成的洞。如 图 1.12 所示，对图像进行去噪，并修复黑色矩形遮挡区域后面隐藏的像素。这可以通过建立像素的联合概率模型来解决，给定一组干净图像，然后在已知变量下推断未知变量（此处指像素）的值。这有点像购物篮分析，只是数据为实值并具有空间结构，所以使用的概率模型有所不同。其他可能的选择，请参阅 第 19.6.2.7节 和 第 13.8.4 节。
图 1.12 (a) 带有遮挡区域的噪声图像。(b) 基于成对 MRF 模型的潜在像素强度估计。资料来源：图 8 (Felzenszwalb和Huttenlocher，2006年)。
（2） 协同过滤
补全任务的另一个有趣例子是 协同过滤 ( collaborative filtering )，在推荐系统中非常常见。它根据不同用户对其看过电影的评价数据，来预测他们想观看哪些电影。关键点是：基于协同过滤的预测不基于电影或用户的特征 ( 这涉及另外的推荐算法 ) ，而仅仅基于评分矩阵。更准确地说，有一个矩阵 \(\mathbf {X}\)，其中 \(X ( m,u )\) 是用户 \(u\) 对电影 \(m\) 的评价 ( 假设一个介于 1 和 5 之间的整数，其中 1 表示不喜欢，5 表示喜欢 ) 。注意，\(\mathbf {X}\) 中大多数条目会是未知的，因为很多用户不会对电影进行评级。因此，我们观测到的是 \(\mathbf {X}\) 矩阵的一个很小的子集，而想要预测的是另外一个子集。特别是，对于任何给定用户 \(u\)，想要预测他 / 她最喜欢看哪些未被排名的电影。
为鼓励该领域的研究，DVD 租赁公司 Netflix 于 2006 年发起了一项竞赛，奖金 100 万美元 ( 见 < http://netflixprize.com/> ) 。特别是，他们为约 50 万个用户创作的约 18k 部电影提供了一个 1 到 5 级的大型评分矩阵。完整的矩阵有大约 \(9 × 10^9\) 个元素，但实际仅观测到大约 1% 的条目，因此矩阵极其稀疏。其中一部分用于训练，其余用于测试，如图 1.13 所示。这次竞赛的目标是比 Netflix 现有的系统预测得更准确。2009 年 9 月 21 日，该奖项被授予了一个名为「BellKor’s Pragmatic Chaos」的研究团队。第 27.6.2 节讨论了它们的一些方法。有关这些团队及其方法的详细信息，请访问 http://www.netflixprize.com/community/viewtopic.php?id=1537。
图 1.13 电影分级数据示例。训练数据是红色的，测试数据用？表示，空单元格未知。
（3） 购物篮分析
在商业数据挖掘中，人们对 购物篮分析 ( market basket analysis ) 的任务非常感兴趣。数据由一个二进制矩阵 ( 通常非常大但稀疏 ) 组成，其中每一列代表一个项目或产品，每一行代表一次交易。如果项目 \(j\) 是在第 \(i\) 个交易上购买的，则 \(x_{ij}=1\)。许多商品是一起购买的 ( 例如，面包和黄油 ) ，所以各个部分之间会有关联。给定一个新的部分观测到的位向量，表示消费者购买的商品子集，目标是预测这个位向量其他哪些位会被激活，即哪些产品可能会被购买 ( 注意：与协同过滤不同，我们通常假设训练数据中没有缺失的数据，因为可以准确知道每个客户过去的购物行为 )。
除对购买模式建模之外，该任务还出现在更多领域。例如：可以使用类似技术对复杂软件系统中文件之间的依赖关系建模。在这种情况下，任务是给定一个已更改的文件子集，预测哪些其他文件需要更新以确保一致性。
解决这类任务的一般方法是 频繁项集挖掘 ( frequent itemset mining ) , 该方法创建关联规则。另外，也可以采用概率方法，针对位向量拟合联合概率密度模型 \(p ( x_1,...,x_D )\) 。这样的模型通常比关联规则具有更好的预测精度，但是可能不太容易解释。这是数据挖掘和机器学习的典型区别：在数据挖掘中，更强调可解释的模型，而在机器学习中，更强调准确的模型。
1.4 机器学习中的一些基本概念¶
本节将介绍机器学习中一些核心概念。尽管将在后面的内容中扩展这些概念，但在此处会进行简单介绍。
1.4.1 参数模型和非参数模型¶
本书将关注概率模型 \(p ( y|\mathbf {x} )\) 或 \(p ( \mathbf {x} )\)，采用哪种模型取决于研究的问题是监督学习还是非监督学习。有很多方法来确定概率模型，不同方法中最重要的区别在于：模型是否具备固定的参数数量，或者说参数数量是否随训练样本的增加而增加？
前者被称为 参数模型 ( parametric model ) ，后者被称为 非参数模型 ( non-parametric model ) 。
参数模型：优势在于使用起来更加快捷，其缺点在于需要对数据分布作强假设。
非参数模型：更加灵活，但是对于大数据集而言，其计算难度通常很大。
我们在后面给出两种模型的例子。为了方便，主要针对监督学习进行讨论，尽管很多讨论同样适用于非监督学习。
1.4.2 一个简单的非参数分类器：K 近邻¶
非参数分类器的简单例子是 \(K\) 近邻 ( K-nearest neighbors，KNN ) 分类器。在该模型中，针对测试输入 \(\mathbf {x}\) 的分类仅仅参考训练集中距离该点最近的 \(K\) 个样本构成的集合，统计该集合中每个类的数量，返回在这个集合中每个类的占比作为估计量，图 1.14 给出了说明，形式上表达为：
图 1.14 (a) \(K = 3\) 的二维 \(K\) 近邻分类器示意图。测试点 \(x_1\) 的3个最近邻居有标签 1、1 和 0，所以预测 \(p(y = 1|x_1，D，K = 3 ) = 2/3\) 。测试点 \(x_2\) 的3个最近邻分别有标签 0、0 和 0，所以预测 \(p(y = 1|x_2，D，K = 3 ) = 0/3\) 。(b) 1 近邻推导出的 Voronoi 图。
其中 \(N_K ( \mathbf {x},\mathcal {D} )\) 为在数据集 \(\mathcal {D}\) 中距离 \(\mathbf {x}\) 最近的 \(K\) 个数据点，\(\mathbb {I}\) 为指示函数，定义为：
\begin {align*} \mathbb {I} ( e ) = \begin {cases} 1, & \mbox {if } e\mbox { is true} \ 0, & \mbox {if } e\mbox { is false} \end {cases} \tag {1.3} \end {align*}
这个方法被称为 基于存储的学习 ( memory-based learning ) 或者 基于样例的学习 ( instance-based learning ) 。在该方法中，最常用的距离测度为欧氏距离 ( 该距离将这个技术限制在了实数领域 ) ，尽管其他的测度也可以使用。
图 1.15 给出了这个方法在实际使用过程中的一个例子，其中输入为二维向量，所有数据共有 3 类，此时选择 \(K=10\) ( 会在后面的内容中讨论 \(K\) 的影响 ) 。图 ( a ) 绘制了训练数据，图 ( b ) 绘制了 \(p ( y=1|\mathbf {x},\mathcal {D} )\)，图 ( c ) 绘制了 \(p ( y=2|\mathbf {x},\mathcal {D} )\)，我们不需要绘制 \(p ( y=3|\mathbf {x},\mathcal {D} )\)，因为每个点属于哪个类的概率满足和为 1 的定理。图 ( d ) 绘制了最大后验概率分布 \(\hat {y} ( \mathbf {x} ) =\arg \max_c p ( y=c|\mathbf {x},\mathcal {D} )\)。
当 K=1 时，\(KNN\) 分类器将得到关于所有点的 泰森多边形图 ( Voronoi tessellation ) ( 见 图 1.14 ( b )) 。这是一种空间划分方式，在该方式中，每一个区域 \(V ( \mathbf {x}_i )\) 与每一个点 \(\mathbf {x}_i\) 相关联，其中 \(V ( \mathbf {x}_i )\) 中的每一个点距离 \(\mathbf {x}_i\) 相较其他点更近。在每一个区域中，预测的标签就是该区域关联的训练样本 \(\mathbf {x}_i\) 的标签。
图 1.15 (a) 二维中一些合成的 3-类别 训练数据。(b) 10-KNN 时类别 1 的概率。(c) 类别 2 的概率。(d) 类别标签的最大后验估计。
1.4.3 维度灾难¶
\(KNN\) 分类器十分简单且效果很好，其前提是需要一个好的距离测度以及足够多的标记数据。事实上如果 \(N \to \infty\) (Cover和Hart 1967)，\(KNN\) 分类器可以达到最佳性能的 2 倍以内。然而，\(KNN\) 的劣势在于不适用于高维输入。造成该问题的原因是 维度灾难 ( curse of dimensionality )。
为解释维度灾难问题，我们给出一个案例。考虑一个在 \(D\) 维的单位空间中非均匀分布的数据集，基于该数据集进行 \(KNN\) 分类。假设为了估计测试点 \(\mathbf {x}\) 的类标签密度，在 \(\mathbf {x}\) 附近做不断生长的超立方体，直至超立方体内的邻居数量达到总数的一定比例 \(f\) 。此时，超立方体边长的期望为 \(e_D ( f ) =f^{1/D}\) （即超立方体体积 \(f\) 的 \(1/D\) 次开方）。若 \(D=10\) ( 即输入特征维度为 10 ) ，其希望基于整个数据集 10% 的数据做密度估计，则 \(e_{10} ( 0.1 ) =0.8\)，也就是说需要在每个维度上扩展 80% 的边长。哪怕只需要 1% 的数据量，也有 \(e_{10} ( 0.01 ) =0.63\)，可以结合图 1.16 加深理解。由于数据在每个维度的总范围为 1，所以上述数据表明当维度过大时， \(KNN\) 方法几乎不再具备局域性。换句话说，\(KNN\) 需要考察最近的邻居，但当数据维度特别高时，最近的邻居实际上也很远，因而它对测试点 \(\mathbf {x}\) 做估计的参考价值就很低。
图 1.16 维度灾难图解。(a) 在一个较大的单位立方体中嵌入一个边为 \(s\) 的小立方体。(b) 将覆盖单位立方体的给定体积所需的立方体的边长绘制为维数的函数。基于图2.6(Hastie等人，2009年)。
1.4.4 归纳偏置（或归纳偏好）¶
为解决维度灾难问题，一种常见方式是对数据的分布 （ 监督学习中的 \(p ( y|\mathbf {x} )\) 或者非监督学习中的 \(p ( \mathbf {x} )\) ）作出一些假设，而这些假设被称为 归纳偏好 ( inductive bias ) 。归纳偏好通常以参数模型的形式展示出来 ( 例如：假设数据分布服从高斯分布，那么相应模型就由高斯分布的参数期望 \(\mu\) 和方差 \(\sigma^2\) 定义 ) 。接下来，简要描述两种广泛使用的参数模型，后面章节会重新做详细阐述。
1.4.5 线性回归的归纳偏好¶
在回归模型中最广泛使用的是 线性回归 ( linear regression ) ，该模型的输出是输入的线性函数。
其中 \(\mathbf {w}^T\mathbf {x}\) 表示输入向量 \(\mathbf {x}\) 与模型权重向量 \(\mathbf {w}\) 之间的内积，\(\epsilon\) 表示预测结果与真实值之间的 残差 ( residual error ) 。
通常情况下，假设 \(\epsilon\) 服从高斯或者正态分布，符号上表示为 \(\epsilon \sim \mathcal {N} ( \mu,\sigma^2 )\)，其中 \(\mu\) 表示期望，\(\sigma^2\) 表示方差。高斯分布的图形如图 1.17 ( a ) 所示。
为更加明确线性回归与高斯分布之间的联系，重写上述模型的形式：
根据上式可以发现该模型是一个条件概率密度模型。在最简单的情况下，假设 \(\mu\) 是一个关于 \(\mathbf {x}\) 的线性函数，即 \(\mu=\mathbf {w}^T\mathbf {x}\)，且噪声部分与输入无关，即 \(\sigma^2 ( \mathbf {x} ) =\sigma^2\)。在这种情况下，\(\mathbf {\theta}= ( \mathbf {w},\sigma^2 )\) 为模型的参数。
如果输入是一维变量，则预期输出可以表示为：
其中 \(w_0\) 为截距或者偏差 ( bias ) 项，\(w_1\) 为斜率。上式定义了向量 \(\mathbf {x}= ( 1,x )\)。 ( 注：通过使用常数项 1，将偏差项和其他项组合在一起形成向量，这是一个常用的符号上的技巧 ) 。如果 \(w_1\) 大于 0，意味着我们希望输出随着输入的增加而增加。图 1.17 ( b ) 给出了说明。图 1.7 ( a ) 给出了一个更加方便的展示方式，其中绘制了输出的预期值与 \(x\) 的关系。
图1.17 (a) 均值为 0 、方差为 1 的高斯概率密度函数。(b) 条件密度模型 \(p(y|x,θ) = \mathcal{N}(y|w_0+ w_1x, σ^2)\) 的可视化。当远离回归线时，密度会以指数形式快速下降。
如果对输入做预处理，将 \(\mathbf {x}\) 替换为关于输入的线性函数 \(\phi ( \mathbf {x} )\)，则利用线性回归模型同样可以对非线性关系建模。也就是说，使用：
上式被称为 基函数拓展 ( basis function expansion )。举例来说，图 1.18 中的 \(\phi ( \mathbf {x} ) =[1,x,x^2,...,x^d]\) 即为基函数，其中 \(d=14\) 和 \(d=20\)，而基于这组基函数得到的模型被称为 多项式回归 ( polynomial regression )模型。本书后面内容会介绍到其他的基函数拓展形式。事实上，许多著名的机器学习方法（如：支持向量机、神经网络、分类和回归树等），都可以看做是从数据中学习基函数的不同方法，我们会在 第 14 章 和第 16 章 中继续讨论。
图 1.18 基于 21 个数据点通过最小二乘法拟合的 14 和 20 次多项式。
1.4.6 逻辑回归的归纳偏好¶
我们可以将线性回归模型推广到 ( 二元 ) 分类问题中，为实现这一点，只需要做出两点变化。
首先，将关于 \(y\) 的分布由高斯分布替换为 伯努利分布 ( Bernoulli ) ，该分布对于目标为二值变量的情况更加适合，即 \(y\in\{0,1\}\)。也就是说，令：
其中 \(\mu ( \mathbf {x} ) =\mathbb {E}[y|\mathbf {x}]=p ( y=1|\mathbf {x} )\)。
第二个改变在于，先计算关于输入的线性组合（与线性回归模型一样），并将结果输入到一个非线性函数中，从而确保 \(0\le\mu ( \mathbf {x} ) \le 1\)，即：
上式中 \({\rm {sigm}} ( \eta )\) 为 sigmoid 函数，又被称为 logistic 或者 logit 函数。定义为：
术语 sigmoid 表示 S 型：如图 1.19 ( a ) 所示。它又被称为压缩函数，因为它将整个实轴映射到了区间 \([0,1]\)，这对于那些需要输出具有概率性解释的模型而言很有必要。
图 1.19 (a) sigmoid 函数或 logistic 函数。有\(sigm(-\infty)= 0\)，\(sigm(0) = 0.5\)，\(sigm(+\infty) = 1\)。 (b) SAT成绩的 logistic 回归。实心黑点是数据，红色圆圈是预测的概率。绿色十字表示两个学生具有相同的 525 分 (因此具有相同的输入表示 \(x\) )，但具有不同的训练标签 ( 一个学生通过，\(y = 1\)，另一个学生失败，\(y = 0\))。因此，仅使用 SAT 特征无法完全分离这些数据。
将上述两个改变统一，可以得到逻辑回归的概率模型：
上式被称为 逻辑回归，但需要主要它是分类模型而并非回归模型，名字中的“回归”两个字也只是因为其形式上与线性回归十分相似而已。
图 1.19 ( b ) 给出了一个逻辑回归的例子，其中绘制了：
\(x_i\) 为学生 \(i\) 的 SAT 成绩，\(y_i\) 表示该学生是否通过考试。黑色实心点表示训练数据，红色圆点即 \(p ( y=1|\mathbf {x}_i,\hat {\mathbf {w}} )\)，其中 \(\hat {\mathbf {w}}\) 表示从训练集中估计的参数 ( 将在第 8.3.4 节中讨论如何估计这些参数 ) .
如果将 0.5 作为输出概率的阈值，可以得到一个具备如下形式的 决策规则：
根据图 1.19 ( b ) 可以发现，\({\rm {sigm}} ( w_0+w_1x ) =0.5\) 时，对应的输入 \(x\approx 545 =x^*\)。我们可以绘制一条垂线 \(x=x^*\)，这被称为决策边界。所有分布在边界左边的点被分类为 0，右边的被分类为 1.
我们发现该决策规则在训练集上的错误率并非为 0，这是因为数据并非线性可分。也就是说，没有办法通过一条直线将 \(0\) 和 \(1\) 分开。当然，我们可以通过基函数拓展的方式获得一个非线性的决策边界，就像在非线性回归中那样。本书后面章节会看到更多相关案例。
1.4.7 过拟合¶
当我们训练非常灵活的模型时，需要关注模型是否过分适应了数据 ( 过拟合 ) ，也就是说我们应该避免对输入中的任何微小变化进行建模，因为那些微小变化很有可能来自噪音而非真实信号。这个在图 1.18 ( b ) 中可以体现，该图表明，当使用一个阶数特别高的多项式拟合数据时，曲线会非常「扭曲」，而真实的函数基本上不会是这样的变化趋势，因此使用这样的模型很难保证未来预测的精度。
另一个例子，考虑 \(KNN\) 分类器。
\(K\) 值对模型性能有重要影响。当 \(K=1\) 时，模型在训练集上没有任何误差 ( 因为直接返回原始训练数据的标签 ) ，但最终预测的决策边界非常「扭曲」，如图 1.20 ( a ) 所示，所以该方法在预测未来数据时未必有效。在图 1.20 ( b ) 中，当 \(K=5\) 时，最终决策边界将会更加平滑，因为我们在一个更大的邻域内进行预测。当 \(K\) 不断增加时，决策边界将会越来越平滑，当 \(K=N\) 时，会将所有测试输入的类别都判定为训练集中占主要部分的类别。
图 1.20 根据图 1.15(a) 中的数据对 \(KNN\) 的预测曲面。(a) K=1 ；(b) K=5。
1.4.8 模型选择¶
当我们拥有一系列不同复杂度的模型时 ( 参数模型如：包含不同阶数的线性或逻辑回归模型，非参数模型如：具有不同 \(K\) 值的 KNN 模型 ) ，该如何选择最合适的那一个呢？一个自然的方法是计算每种方法在训练集上的 误分类率 ( misclassification rate )。定义为：
其中 \(f ( \mathbf {x} )\) 为分类器。在图 1.21 ( a ) 中，我们绘制了在 \(KNN\) 分类器中误分类率与 \(K\) 的关系 ( 点蓝线 ) 。我们发现当 \(K\) 的数量增加时，训练集上的错误率将会增加。正如前文所述，如果选择 \(K=1\)，模型在训练集上的错误率为 0，因为模型只是存储了训练集而已。
图 1.21 (a) \(K\) 近邻分类器中误分类率与 \(K\) 的关系。左边的 \(K\) 很小，模型很复杂，因此过拟合。右边的 \(K\) 较大，模型相对简单，因此欠拟合。蓝色虚线：训练集 ( 大小为 200 ) 。红色实线：测试集 ( 大小为 500 ) 。(b) 五折交叉验证示意图。
然而，我们真正关心的是 泛化误差 ( generalization rate ) , 即模型在新数据集上的平均误分类率 ( 见 6.3 节 ) 。这个泛化误差可以近似为模型在一个独立 测试集 ( test set ) 上的错误率，这个测试集在模型训练过程中不被使用。在图 1.21 ( a ) 中绘制了测试集错误率与 \(K\) 的关系。现在会发现一条 U-型曲线：对于复杂模型 ( \(K\) 比较小 ) ，模型过拟合，对于简单模型 ( \(K\) 值很大 ) ，模型 欠拟合 ( underfits ) 。所以最明显的方法是挑选在测试集上错误率最小的 \(K\) 值 ( 例如图中 10 到 100 之间的取值应该都很好 ) 。
不幸的是，当训练模型时，我们接触不到测试集，所以不能使用测试集来辅助选择正确的模型复杂度。然而，可以通过将训练集分成两部分的方法创建一个测试集：一部分用于训练模型，另一部分称为 验证集 ( validation set )，用于选择模型的复杂度。
我们基于训练集优化所有的模型，然后评估他们在验证集上的性能，并且选择性能最好的模型。一旦选择了最好的模型作为最终模型，可以基于全部数据重新优化模型。如果我们还有一个独立的测试集，则可以基于这个测试集进行性能评估，用来估计模型精度 (们将在第 6.5.3 节介绍更多细节 ) 。
通常会使用 80% 的数据作为训练集，20% 作为验证集。但如果可获取的训练集样本数量有限，这种二分法会面临挑战，因为模型将没有足够数据用于训练，也不会有足够数据用于对性能进行合理估计。
此时的解决方法是使用 交叉验证 ( cross validation ) 。其思想很简单：将训练集分成 \(K\) 个 折 ( folds ) ；然后对于每个折 \(k\in\{1,...,K\}\)，基于除了 \(k\) 以外的所有折进行模型训练，然后在折 \(k\) 上进行测试。这个过程循环进行 \(K\) 次后，如图 1.21 ( b ) 所示，计算模型在所有折上错误率的平均值，用作对测试误差的代理 (注意：每个数据点只会被用来预测一次，但可以被用来训练 \(K-1\) 次 ) 。通常情况下会使用 \(K=5\)，这被称为 5 折交叉验证（ 5-folds CV ）。如果设置 \(K = N\)，相应方法被称为 留一法交叉验证 ( leave-one out cross validation, LOOCV ) , 即在折 \(i\) 中，利用除了 \(i\) 以外的所有数据进行训练，用数据 \(i\) 进行测试。
选择 \(KNN\) 分类器中的 \(K\) 值是 模型选择 ( model selection ) 的一个特例，在模型选择问题中，我们需要在具有不同复杂度的模型中作出选择。交叉验证被广泛用于解决这类问题，尽管我们会在书中介绍其他方法。
1.4.9 没有免费的午餐理论 ( No free lunch theorem )¶
All models are wrong, but some models are useful.—George Box
很多机器学习方法都涉及到不同模型，以及不同的算法去训练这些模型。我们可以针对特定问题使用诸如交叉验证的方法去选择最好的模型。然而，没有放之四海而皆好的模型，因为很多假设在某个领域可能会十分奏效，在另一个领域则不尽然。这被称为 没有免费的午餐理论 ( no free lunch theorem )。
因为没有免费的午餐理论，我们需要开发不同类型的模型，去涵盖现实世界中不同领域的数据。对于每个模型，可能有很多不同算法去训练它们，且不同算法都会在 速度 — 精度 — 复杂度 之间做权衡。