———— 殷勤昨夜三更雨，又得浮生一日凉。

该部分先讲述一些机器学习的基本概念，然后再引出过拟合等知识点。

机器学习的主要目标是我们的算法必须能够在先前未观测的新输入上表现良好，而不只是在训练集上表现良好。在先前未观测到的输入上表现良好的能力被称为泛化 (generalization)。

当我们训练机器学习模型时，我们可以使用某个训练集，在训练集上计算误差函数被称为训练误差 (training error)，我们的训练目标是降低训练误差，这是一个优化问题。而机器学习和优化不同的地方在于，我们也希望泛化误差 (generalization error)（也被称为测试误差 (test error)）很低，泛化误差被定义为新输入的误差期望。我们通过度量模型在测试集样本上的性能，来评估机器学习模型的泛化误差。

根据统计学习理论，训练集和测试集数据可以看做是同一个概率生成模型的独立同分布 (independent identically distribution) 采样，这个假设使我们能够在单个样本的概率分布描述整个数据的生成过程。然后相同的分布可以用来生成每一个训练样本和每一个测试样本。我们将这个共享的潜在分布称为数据生成分布 (data generating distribution)。

学习理论表明机器学习算法能够在有限个训练集样本中很好地泛化。而使用归纳推理，从一组有限的样本中推断一般的规则，在逻辑上不是很有效。为了逻辑地推断一个规则去描述集合中的元素，我们必须具有集合中每个元素的信息。但在一定程度上，机器学习通过概率论就可以避免这个问题，无需使用纯逻辑推理整个确定性法则。机器学习的目的就是保证找到一个在所关注的大多数样本上可能正确的规则。

但即使这样，还是会有一些纰漏，机器学习的没有免费的午餐定理 (no free lunch theorem) 表明，在所有可能的数据上平均之后，每一个分类算法在未知的点上都有相同的错误率，没有一个机器学习算法总是比其他的要好。我们能够设想的最先进的算法和简单地将所有点归为同一类的简单算法有着相同的平均性能（在所有可能的任务上）。但在真实世界应用中我们并不会考虑所有可能的数据生成分布的任务，所以我们可以仅在遇到的数据分布上设计效果良好的学习算法，这也正是我们最关注的算法。

上述的概率框架和独立同分布假设允许我们从数学上研究训练误差和测试误差之间的关系。当我们使用机器学习算法时，我们先采样得到训练集，然后挑选参数去降低训练集误差，再采样得到测试集。在这个过程中，测试误差期望会大于或等于训练误差期望。一个好的机器学习算法，既能够降低训练误差，也应该缩小训练误差和测试误差的差距。如果不能在训练集上获得足够低的误差，说明模型没有适当捕捉到训练数据的结构特征，一般对应于参数较少的简单模型，我们这种现象称作欠拟合 (underfitting)；而如果训练误差和测试误差之间的差距太大，说明模型只适合训练使用的数据集而不具备泛化能力，一般对应于参数量较大的复杂模型，我们称作过拟合 (overfitting)。一般只要选择正确的算法，我们都可以获得期望误差，这是就更关注过拟合问题了。

1. 过拟合 (Overfitting)

重新考察第一篇文章 1.1 节的多项式曲线拟合问题，采样一组由  产生的数据点，输入  是在区间  上均值分布的采样，然后对每个点的标签  加上高斯噪声，就得到了数据集。使用多项式函数

进行曲线拟合，我们分别选择多详述阶数  。正常情况判断是否过拟合需要计算训练集和测试集的误差函数，此处为了方便起见，由于我们知道数据是从  采样的，所以我们只需要观察拟合的曲线在区间  上与  偏差即可。如下图是四个不同的阶数的曲线拟合结果

我们注意到  时多项式对于数据的拟合效果相当差。三阶多项式似乎给出了对  的最好拟合。当我们达到更⾼阶的多项式 (  )，我们得到了对于训练数据的⼀个完美的拟合。 事实上， 多项式函数精确地通过了每⼀个数据点，误差函数降到了 0。 然⽽，拟合的曲线剧烈震荡，与  相去甚远，发生了过拟合，如果在测试集上做预测，可想而知效果是很差的。我们可以观察训练集和测试集的均方和误差，或者更一般的使用根均方误差  ，这样可以确保与目标变量  使⽤相同规模的单位进⾏度量，下图展示了  取  上所有整数时训练集与测试集根均方的情况。

对于  的情形，训练集的误差为 0，因为此时的多项式函数有 10 个⾃由度，对应于10个系数  ，调节后使得模型与训练集中的 10 个数据点精确匹配。但是它在测试集上却突然变差，这可能看起来很⽭盾， 因为给定阶数的多项式包含了所有低阶的多项式函数作为特殊情况。  的多项式因此能够产⽣⾄少与  ⼀样的结果。同时由于生成数据的函数  的幂级数展开包含所有阶数的项，所以我们直观地认为结果会随着  的增⼤⽽单调地变好，然而这时候却发生了激烈的震荡，尤其是在区间两端，考虑到附加的噪声，我们可以直观的解释，随着  值的增大，多项式可以被更灵活地调参，但是过度调参后反而连⽬标值的随机噪声都拟合了。所以在实际应用中，越复杂的模型未必能够得出更好的结果，但是从以上分析可以看出，可调节的参数数量小于用于训练的数据点个数，结果还都不错，所以，增加训练数据点个数，也可以避免发生这种过拟合的情况。

可知，如果如果模型过于复杂或参数过于固定，就会把数据的噪声也考虑进去导致过拟合，所以我们解决思路有两种，一种是针对参数，一种是针对模型，过拟合是一个很常见的问题，深度学习中常用 dropout 方法丢弃某些神经单元，其目的是为了使用不同的神经网络，这样可以有效抑制过拟合；此外，高斯过程和贝叶斯神经网络分别通过增加模型的不确定性以及参数的不确定性增强泛化能力；下面将一种很常见的控制过拟合的方法。

2. 正则化 (Regularization)

没有免费午餐定理暗示我们必须在特定任务上设计性能良好的机器学习算法。当我们设计的算法特性与希望解决的学习问题相吻合，也就是恰好能适应当前的数据生成分布时，算法性能会更好。上一节多项式回归过拟合问题表明，我们可以通过增加或减少学习算法的可选函数来增加或减少模型，比如增加或减少多项式的次数。算法的效果受影响于选择的的函数数量以及函数的具体形式，即模型结构。在可选空间中，相比于某一个学习算法，我们可能更偏好另一个学习算法。这意味着两个函数都是符合条件的，但是我们更偏好其中一个。

比如我们把加入权重衰减 (weight decay) 作为一种控制过拟合的常见方法，就是给误差函数添加一个惩罚项或正则项 (regularization)，令函数偏好于其偏好于可以使正则项较小的权重。此时误差函数为

其中  是正则化系数，控制数据误差函数和正则化项的相对重要性和偏好性。对于正则化项的选择⽅法也称为权值衰减 (weight decay)，在梯度下降算法中，它倾向于让权值向零的⽅向衰减。在统计学中，  的情形被称为套索 (lasso)。它的性质为：如果  充分⼤，那么某些系数  会变为零，从⽽产⽣了⼀个稀疏 (sparse) 模型，这个模型中对应的基函数或数据点不起作⽤。根据拉格朗日乘数法 (Lagrange Multipliers)，最小化公式 (2) 等价于在满⾜以下限制条件时最⼩化平⽅和误差函数。

参数  要选择⼀个合适的值。稀疏性的来源可以从下图中看出来，在限制条件 (3) 下误差函数的最⼩值。书中对这部分解释实在太少，我大致猜想，蓝色表示未正则化的误差函数的范围，由于是二次型所以误差函数轮廓是个圆，其中圆心位置又目标和训练数据的均值决定。 的套索轮廓与误差函数轮廓相切的位置通常在坐标轴上，而  的圆形轮廓与误差函数的切点在其他位置，因此  时有更多最优参数会为 0，随着  的增⼤，越来越多的参数会变为零。也许这也是一种解释，但类似第一篇 1.3 节所提及最大后验估计结果也带有一个正则化项来看，正则化项也是我们加入对参数的先验估计的一种隐性表达，无论  取何值，总是希望  向 0 的方向移动。

拉格朗日乘数法 (Lagrange Multipliers)

简单解释下拉格朗日乘数法，这是一个被⽤于寻找多元变量在⼀个或者多个限制条件下的驻点的方法。考虑一个  维空间变量  ，限制方程  表示空间中一个曲面，那么在限制曲⾯上的任何点处，限制函数的梯度  都正交于限制曲⾯，通过考虑⼀个位于限制曲⾯上的点  以及这个点附近同样位于曲⾯上的点  ，对后者进行一阶泰勒展开  ，由于在限制曲面上恒有  且  平行于曲面，就能发现  正交于曲面。而对于  ，我们寻找限制曲⾯上的⼀个点  使得  最⼤，那么这个点也一定满足  正交于曲面，因为如果不满足的话，那我们一定可以沿着曲面短距离移动  使  增加，这与已知条件相悖，因此  与  都正交于曲面且平行，因此存在一个常数  使得

通过积分可得对应的拉格朗日函数为

所以说最小化限制条件  下的  等价于最小化上述拉格朗日函数。

最后回到正题，正则化⽅法通过限制模型的复杂度，使得复杂的模型能够在有限⼤⼩的数据集上进⾏训练，⽽不会产⽣严重的过拟合。需要注意的是，正则化通过修改学习算法，旨在降低泛化误差而非训练误差。

局部加权线性回归 (Locally Weighted Regression)

下面再介绍一种针对线性回归问题解决过拟合的方法，一种非参数学习方法，叫做局部加权回归 (locally weighted regression)。普通的线性回归属于参数学习算法 (parametric learning algorithm)；而局部加权线性回归属于非参数学习算法 (non-parametric learning algorithm)。参数学习方法在训练完成所有数据后得到一系列训练参数，在预测时用固定参数来测试。而非参数学习在预测新样本值时候每次都会重新训练数据得到新的参数值，每次得到的参数值也是不确定的。

之前的线性回归误差函数形式为  ，而在局部加权回归中，误差函数为  ，其中  是权重，取自高斯采样

其中  是新预测的样本，参数  控制权值变化速率，可知如果  ，那么  ；如果  ，那么  ；所以，离预测样本数据  较近的点权值大，离预测样本较远的点权值小。这种做法本质上是为了让线性回归模型不再依赖于整体数据的特征选择，让与预测点更加接近的局部训练数据在重新训练时的损失函数中占据主导地位，实际上这种方法同时有效解决了过拟合和欠拟合的问题，而我们前面提到的样条函数其实也是为了让相近的局部函数在映射到新的特征空间后能够更接近，都是用局部数据预测局部数据，因为它们原始特征更接近，同样的，这种做法必然付出代价。样条函数是我们需要选择大量不同的函数分区拟合，而局部加权线性回归则因为在预测每一个新的数据点时都需要重新训练，因此需要付出巨大的计算量。

3. 模型选择 (Model Selection)

在我们使⽤最⼩平⽅拟合多项式曲线的例⼦中可以看到，存在⼀个最优的多项式阶数给出最好的结果。多项式的阶数控制了模型的⾃由度，以及模型的复杂度。添加正则项后，正则化系数也控制了我们的模型复杂度。在实际应⽤中，我们需要确定这些参数的值，以期在新数据上能做出最好的预测。此外，我们可能还希望找到适当的可选模型算法，以便找到对于特定应⽤的最好模型。

此前由于过拟合，模型在训练集上的表现并不能应用于对未知数据的预测。如果数据量很⼤，那么模型选择很简单。我们使⽤⼀部分可得到的数据，可以训练出⼀系列模型的参数值。之后在独⽴数据上⽐较它们，选择预测表现最好的模型即可。因此除了训练集和测试集外，我们又引入验证集 (validation set)。训练过程的超参数总是倾向于过拟合的方向，而测试集通常用来估计训练收敛后最终的泛化误差，在实际中并不能参与到模型选择中，因此从训练数据中构建验证集，将训练数据分成两个不相交的子集，一个用于学习参数，另一个作为验证集，估计训练中的泛化误差，更新超参数。

将训练数据集分成固定的训练集和验证集后，若验证集的误差很小，可能是有问题的。因为一个小规模的数据集意味着平均测试误差估计的统计不确定性，使得很难判断算法在其他给定的任务上是否做得更好。通常数据集都是有限的。为了建⽴更好的模型，我们想使⽤尽可能多的可得到的数据进⾏训练，使用所有的样本估计平均测试误差。⼀种解决⽅法是使⽤交叉验证 (cross validation)，这种⽅法能够让可得到数据总量  的  ⽤于训练，同时使⽤所有的数据来评估表现。

交叉验证法可以描述为：随机将数据集  平均划分为  个不相交的子集  ，对于可选择的  个模型  ，将每个模型依次在  个子集上训练，在剩余的一个子集  上验证得到误差  ，共进行  次，使每个子集都能都作为一次验证集，将  个误差作均值得到  ，然后选择具有最小估计误差的模型  ，然后在整个训练集上重新训练，得出的结果即为最终模型。当数据相当稀疏的时候，考虑  的情况很合适，其中  是数据点的总数，这种技术叫做 “留⼀法” (leave-one-out)。

如下图所示的交叉验证⽅法，其中  ，然后，  组数据被⽤于训练⼀组模型，然后在剩余的⼀组上进⾏评估，图中用红色标出，之后，对  轮运⾏结果的误差求均值。

4. 特征选择 (Feature Selection)

一个好的机器学习算法，不仅需要选择适当的模型，所选模型也要能提取合适的特征。第一篇文章基函数的选择就包含了特征选择的考虑成分。更一般地，假设我们有一个机器学习算法，输入向量可提取特征数量非常大，但只有一小部分特征对目标值相关性较大。因此即使用最简单的线性模型，参数数量也会巨大，尤其对于上述多项式曲线回归问题，很容易出现过拟合。

所以我们需要一个特征选择算法来减少特征的数量。假设输入向量包含  维特征，我们对于每个特征都有可选或不选两种情况，就有  种可选的特征组合，我们也可以将其看作是一个包含  种模型的模型选择问题。如果  较大，那么遍历所有的模型代价过高，我们一般采用一些启发式流程来搜索，其中有包装器特征选择 (wrapper feature selection) 和过滤器特征选择 (filter feature selection)。

4.1 包装器特征选择 (Wrapper Feature Selection)

包装器可以分为前向和后向两种。前向搜索是每次从未选择的特征集合  中选出一个加入特征集  中，待达到备选特征阈值或选择了全部特征时，从所有的中选出误差最小的。具体步骤为

1. 初始化  为空
2. 遍历  ，如果第  个特征不在  中，令  ，利用交叉验证得到  中所有特征子集的误差。
3. 选择误差最小的特征子集，并将下一次搜索的  设置为该特征子集，再次进行步骤 2。
4. 选择整个搜索过程中表现最佳的特征子集输出

包装器特征选择通过遍历所有特征，每次循环选择出对结果影响最大的一个特征，特征是按照对结果影响从高到低给出的。当然，这种算法需要假设前提是所有特征相互独立。

包装器后向搜索正好反其道而行，初始特征集包含所有特征，然后依次减去对结果影响最小的  个特征。包装器特征选择算法通常效果较好，但是相对来说计算代价较高。完整的前向搜索过程会进行约  次学习算法的调用。

4.2 过滤器特征选择 (Filter Feature Selection)

过滤器特征选择按照发散性或相关性对各个特征进行评分，设定待选择阈值的个数，从而选择满足条件的特征。过滤器特征选择算法的计算代价很小，算法思想是计算每个特征  对其目标值  所能体现的信息量  ，然后选择得分最高的  个特征作为特征集。一般将  定义为  与  之间的相关程度（基于训练集计算）。

实际应用中通过  和  的互信息 (mutual information) 来计算  ：

此处假设输入向量特征维度为 2 的二分类问题，上式的概率都基于训练集估计。

5. 偏差和方差 (Bias and Variance)

统计领域为我们提供了很多工具来实现机器学习目标，不仅可以解决训练任务，还可以有效提高模型泛化能力。使用偏差和方差等概念，对于正式地描述泛化、欠拟合和过拟合都非常有帮助。

重新考察我们前面所讲的多项式曲线拟合问题，对于一些随机生成的数据点，我们分别使用线性函数，二阶多项式和五阶多项式进行拟合，生成上面三种效果。上文已经说过，左图和右图分别对应欠拟合和过拟合的情况，如果我们再从偏差和方差的角度考虑，可以认为，欠拟合由于很多的数据点未被拟合，我们用来拟合的模型对新的数据做出的预测可能与实际差异很大，也就是模型本身就不能完全提取数据的特征，这种情况属于高偏差；而右图过拟合虽然让每个数据点都经过该曲线，但是对于新的数据可能会加上一些它们并不拥有高次特征，同样会产生很大差异，这种情况对应于高方差。因此选择一个模型使得它在偏差与方差之间取得一个平衡，就是我们要解决的问题。

先引入几个理论，再来进行下面的推导。

1. 联合界引理 (The Union Bound)

集合  包含  个相互独立或不相互独立事件，对此有

对任意两个事件  ，我们有  ，因此可推导出联合界引理，即  集合中至少一件事情发生的概率不大于  个事件发生单独发生的概率和。

2. 霍夫丁不等式 (Hoeffding Inequality)

令  为  个服从伯努利分布的独立同分布事件，有  ，  ，使用  个  的平均值来得到一个  的估计值  ：

对于任意的固定值  ，存在

这条定理也成切尔诺夫界 (Chernoff bound)，可以看出，当  固定时，  的值越大，即用于估计的随机事件数量越多，估计值  与真实的  越接近。

3. 经验风险最小化 (Empirical Risk Minimization)

为方便讨论，在此考虑一个二分类问题。给定训练集  ，训练数据  独立同分布服从概率分布  ，假设一个函数  ，我们定义训练误差 (training error)（也称作经验风险 (empirical risk) 或经验误差 (empirical error)）为

这表示  误分类的数据占所有数据样本的比例，训练集  上的训练误差记作  。我们也可以定义泛化误差 (generalization error)

其中  服从分布  。这部分是 CS229 中的描述，与本章开头选自 Deep Learning 关于误差的表述如出一辙。  就是所谓的数据生成分布，泛化误差表示该模型本身对于描述该数据分布的误差。利用线性分类器进行二分类，定义  ，所有假设模型集合为  。由公式 (11) 所定义的误差公式，有经验风险最小化 (empirical risk minimization) （CS229 中的高级定义，即误差最小化）

分别表示假设参数和函数经验风险最小化。

5.1 一致收敛 (Uniform Convergence)

此处的一致收敛有两个前提，一是由函数的经验风险最小化推导，二是假设函数的数量是有限的。一致收敛的意义是，训练误差与一般误差的差值大于某阈值的概率存在着界限，根据公式 (10) 这个上界会因样本数量的上升而下降。由一致收敛 (uniform convergence) 我们可以推导出偏差/方差权衡的方式。

假设集  共含  个假设模型。其次，用  表示错误分类的模型。 训练误差可以写成

然后令泛化误差为  ，根据霍夫丁不等式，有

接下来证明所有属于集合  的模型都满足上面这个结论。令  表示  ，则有  ，结合联合界引理，我们有

再用 1 减去公式 (17) 两侧，可以得到

公式 (18) 即一致收敛定理，对于所有属于集合  的模型  ，至少存在  的概率，使得训练误差与一般误差的差值最大为  ，也表明当  很大的时候，训练误差会收敛到泛化误差。一致收敛中有三个重要参数，分别是样本数量  ，误差阈值  ，以及误差概率。我们可以根据任意两个量推导出另外一个量。我们试着推导一遍。

给定误差阈值  与一个误差概率  ，要保证至少有  的概率使训练误差与泛化误差的差值小于  ，需要的样本数量为

其中  ，样本数量  是概率误差  的减函数，当  增加，  减少，  增大。当满足公式 (19) 时，取等号即为取得最小的样本复杂度，当取大于号，即增加一致收敛成立时满足的最小概率。  代表了当一个模型想要到达一个确定性能的时候，它所需要的样本数目，也被称为样本复杂度 (sample complexity)。

再看给定样本数量  与  ，误差阈值  的范围，反推公式 (19) 可得

这被称为误差界 (error bound)。

接下来考虑偏差和方差的权衡，我们定义使训练误差最小的函数为  ，泛化误差最小的函数为  。对训练误差应用一致收敛性，可得  。函数  才能使训练误差  取最小值，所以有  。对于泛化误差而言，又有  ，将这几个式子串起来，可得

 表示，经过经验风险最小化处理得到的最优假设函数  ，在实际应用  中的分类错误率。也就是我们在训练集上训练出的模型在测试集上的错误率。这也表明，在一致收敛成立的前提下，训练最优的模型与理论上能达到的最优模型之间，错误率最多相差  。

将  代入公式 (21) 和 (14)，可以得到

其中，  称为偏差衡量，  称为方差衡量，这就是偏差、方差权衡的公式。  表示实际分类错误率，越小越好。 选择一个复杂模型时，模型会有更多的参数组合所以  值会变大，在偏差衡量中可选模型变多了，在更多的选择中，会使  更小，对应低错误率；但是，由于  正比于方差衡量，  值增大也会伴随方差增大，对应着泛化误差增加。

这样我们就定量的将过拟合，欠拟合与方差和误差的关系描述了，理想的模型应该使偏差、方差之和最小。

5.2 VC 维 (Vapnik-Chervonenkis Dimension)

如果我们将假设模型的数量扩充为无限数量，将会得到一个更一般的形式，在经验中，模型复杂度常与样本复杂度成正比。即假设线性模型含有  个参数，那么样本复杂度与  常为线性关系。讨论这个我们先引入一个 VC 维的概念。

给定一个集合  ，按照任意方式对  中的点进行标记后，模型集合  中总存在着某个模型  可以将其线性分开，则称  可以分散  。对一个模型集合来说，它的 VC 维，记为  ，是其能够分散  的最大集合的大小。假设  中有 3 个点，对应 8 种标记方式，模型集合  都能将其分开，如下图所示

虽然在三点共线或重合时，没有直线能够将其线性分开的，但是只要存在着以任何方式标记的三个点集合，能被直线集合线性分开，就满足定义。我们称线性模型集合  可以打散三个点的集合  ，并且  的 VC 维是 3，即  。更一般地，对于  维线性分类模型来说，它的 VC 维为  。

对于一个模型集合来说，不管它是有限的还是无限的，都可以根据 VC 维来获得其一致收敛定理。VC 维推导过程较为复杂，这里直接给出结论：对于模型集合  ，令  ，那么至少有  的概率，对于模型集合中所有的  来说，有

为使  对模型集合  中的所有  ，都有至少  概率成立，那么样本数量必须满足  ，即要使模型经验风险最小化，训练样本的数量  就要与  呈线性相关。

为了将 CS229 和 PRML 相关联的内容整合，本章篇幅较长，需要注意 CS229 中对于很多基础概念的定义不是很常见，最后一节讨论的方差与偏差其实就是探讨训练集与测试集的误差关系，只不过与我们常见的叫法不同而已。