机器学习基础：容量、过拟合和欠拟合
机器学习的主要挑战是我们的算法必须能够在先前未观测到的新输入上表现良好，而不只是在训练集上表现良好。在先前未观测到的输入上表现良好的能力被称为泛化 （generaliza-tion）。
通常情况下，训练机器学习模型时，我们可以使用某个训练集，在训练集上计算一些被称为训练误差 （training error）的度量误差，目标是降低训练误差。到目前为止，我们讨论的是一个简单的优化问题。机器学习和优化不同的地方在于，我们也希望泛化误差 （generalization error）（也被称为测试误差 （test error））很低。泛化误差被定义为新输入的误差期望。这里，期望的计算基于不同的可能输入，这些输入采自系统在现实中遇到的分布。
通常，我们度量模型在训练集中分出来的测试集 （test set）样本上的性能，来评估机器学习模型的泛化误差。
在我们的线性回归示例中，通过最小化训练误差来训练模型，
但是我们真正关注的是测试误差
。
当我们只能观测到训练集时，如何才能影响测试集的性能呢？统计学习理论 （statistical learning theory）提供了一些答案。如果训练集和测试集的数据是任意收集的，那么我们能够做的确实很有限。如果可以对训练集和测试集数据的收集方式有些假设，那么我们能够对算法做些改进。
训练集和测试集数据通过数据集上被称为数据生成过程 （data generating process）的概率分布生成。通常，我们会做一系列被统称为独立同分布假设 （i.i.d．assumption）的假设。该假设是说，每个数据集中的样本都是彼此相互独立的 （independent），并且训练集和测试集是同分布的 （identically distributed），采样自相同的分布。这个假设使我们能够在单个样本的概率分布描述数据生成过程。然后相同的分布可以用来生成每一个训练样本和每一个测试样本。我们将这个共享的潜在分布称为数据生成分布 （data generating distribution），记作p data 。这个概率框架和独立同分布假设允许我们从数学上研究训练误差和测试误差之间的关系。
我们能观察到训练误差和测试误差之间的直接联系是，随机模型训练误差的期望和该模型测试误差的期望是一样的。假设我们有概率分布p（ x ，y），从中重复采样生成训练集和测试集。对于某个固定的 w ，训练集误差的期望恰好和测试集误差的期望一样，这是因为这两个期望的计算都使用了相同的数据集生成过程。这两种情况的唯一区别是数据集的名字不同。
当然，在使用机器学习算法时，我们不会提前固定参数，然后采样得到两个数据集。我们采样得到训练集，然后挑选参数去降低训练集误差，然后采样得到测试集。在这个过程中，测试误差期望会大于或等于训练误差期望。以下是决定机器学习算法效果是否好的因素：
（1）降低训练误差。
（2）缩小训练误差和测试误差的差距。
这两个因素对应机器学习的两个主要挑战：欠拟合 （underfitting）和过拟合 （overfitting）。欠拟合是指模型不能在训练集上获得足够低的误差，而过拟合是指训练误差和测试误差之间的差距太大。
通过调整模型的容量 （capacity），我们可以控制模型是否偏向于过拟合或者欠拟合。通俗来讲，模型的容量是指其拟合各种函数的能力。容量低的模型可能很难拟合训练集。容量高的模型可能会过拟合，因为记住了不适用于测试集的训练集性质。
一种控制训练算法容量的方法是选择假设空间 （hypothesis space），即学习算法可以选择为解决方案的函数集。例如，线性回归函数将关于其输入的所有线性函数作为假设空间。广义线性回归的假设空间包括多项式函数，而非仅有线性函数。这样做就增加了模型的容量。
一次多项式提供了我们已经熟悉的线性回归模型，其预测如下
通过引入x 2 作为线性回归模型的另一个特征，我们能够学习关于x的二次函数模型：
尽管该模型是输入的二次函数，但输出仍是参数的线性函数，因此我们仍然可以用正规方程得到模型的闭解。我们可以继续添加x的更高幂作为额外特征，例如下面的9次多项式：
当机器学习算法的容量适合于所执行任务的复杂度和所提供训练数据的数量时，算法效果通常会最佳。容量不足的模型不能解决复杂任务。容量高的模型能够解决复杂的任务，但是当其容量高于任务所需时，有可能会过拟合。
图1展示了这个原理的使用情况。我们比较了线性、二次和9次预测器拟合真实二次函数的效果。线性函数无法刻画真实函数的曲率，所以欠拟合。9次函数能够表示正确的函数，但是因为训练参数比训练样本还多，所以它也能够表示无限多个刚好穿越训练样本点的很多其他函数。我们不太可能从这很多不同的解中选出一个泛化良好的。在这个问题中，二次模型非常符合任务的真实结构，因此它可以很好地泛化到新数据上。
图1 我们用3个模型拟合了这个训练集的样本。训练数据是通过随机抽取x然后用二次函数确定性地生成y来合成的。（左）用一个线性函数拟合数据会导致欠拟合——它无法捕捉数据中的曲率信息。（中）用二次函数拟合数据在未观察到的点上泛化得很好，这并不会导致明显的欠拟合或者过拟合。（右）一个9阶的多项式拟合数据会导致过拟合。在这里我们使用Moore-Penrose伪逆来解这个欠定的正规方程。得出的解能够精确地穿过所有的训练点，但可惜我们无法提取有效的结构信息。在两个数据点之间它有一个真实的函数所不包含的深谷。在数据的左侧，它也会急剧增长，而在这一区域真实的函数却是下降的
到目前为止，我们探讨了通过改变输入特征的数目和加入这些特征对应的参数，改变模型的容量。事实上，还有很多方法可以改变模型的容量。容量不仅取决于模型的选择。模型规定了调整参数降低训练目标时，学习算法可以从哪些函数族中选择函数。这被称为模型的表示容量 （representational capacity）。在很多情况下，从这些函数中挑选出最优函数是非常困难的优化问题。实际中，学习算法不会真的找到最优函数，而仅是找到一个可以大大降低训练误差的函数。额外的限制因素，比如优化算法的不完美，意味着学习算法的有效容量 （effective capacity）可能小于模型族的表示容量。
提高机器学习模型泛化的现代思想可以追溯到早在托勒密时期的哲学家的思想。许多早期的学者提出一个简约原则，现在广泛被称为奥卡姆剃刀 （Occam's razor）（c．1287-1387）。该原则指出，在同样能够解释已知观测现象的假设中，我们应该挑选“最简单”的那一个。这个想法是在20世纪，由统计学习理论创始人形式化并精确化的（Vapnik and Chervonenkis，1971；Vapnik，1982；Blumer et al. ，1989；Vapnik，1995）。
统计学习理论提供了量化模型容量的不同方法。在这些方法中，最有名的是Vapnik-Chervonenkis维度 （Vapnik-Chervonenkis dimension，VC），简称VC维。VC维度量二元分类器的容量。VC维定义为该分类器能够分类的训练样本的最大数目。假设存在m个不同 x 点的训练集，分类器可以任意地标记该m个不同的 x 点，VC维被定义为m的最大可能值。
量化模型的容量使得统计学习理论可以进行量化预测。统计学习理论中最重要的结论阐述了训练误差和泛化误差之间差异的上界随着模型容量增长而增长，但随着训练样本增多而下降（Vapnik and Chervonenkis，1971；Vapnik，1982；Blumeret al. ，1989；Vapnik，1995）。这些边界为机器学习算法可以有效解决问题提供了理论验证，但是它们很少应用于实际中的深度学习算法。一部分原因是边界太松，另一部分原因是很难确定深度学习算法的容量。由于有效容量受限于优化算法的能力，确定深度学习模型容量的问题特别困难。而且对于深度学习中的一般非凸优化问题，我们只有很少的理论分析。
我们必须记住虽然更简单的函数更可能泛化（训练误差和测试误差的差距小），但我们仍然需要选择一个充分复杂的假设以达到低的训练误差。通常，当模型容量上升时，训练误差会下降，直到其渐近最小可能误差（假设误差度量有最小值）。通常，泛化误差是一个关于模型容量的U形曲线函数，如图2所示。
图2 容量和误差之间的典型关系。训练误差和测试误差表现得非常不同。在图的左端，训练误差和泛化误差都非常高，这是 欠拟合机制 （underfitting regime）。当我们增加容量时，训练误差减小，但是训练误差和泛化误差之间的间距却不断扩大。最终，这个间距的大小超过了训练误差的下降，我们进入到了 过拟合机制 （overfitting regime），其中容量过大，超过了 最优容量 （optimal capacity）
为考虑容量任意高的极端情况，我们介绍非参数 （non-parametric）模型的概念。至此，我们只探讨过参数模型，例如线性回归。参数模型学习的函数在观测到新数据前，参数向量的分量个数是有限且固定的。非参数模型没有这些限制。
有时，非参数模型仅是一些不能实际实现的理论抽象（比如搜索所有可能概率分布的算法）。然而，我们也可以设计一些实用的非参数模型，使它们的复杂度和训练集大小有关。这种算法的一个示例是最近邻回归 （nearest neighbor regression）。不像线性回归有固定长度的向量作为权重，最近邻回归模型存储了训练集中所有的 X 和 y 。当需要为测试点 x 分类时，模型会查询训练集中离该点最近的点，并返回相关的回归目标。换言之，
=y i 其中
。该算法也可以扩展成L 2 范数以外的距离度量，例如学成距离度量（Goldberger et al. ，2005）。在最近向量不唯一的情况下，如果允许算法对所有离 x 最近的 X i，： 关联的y i 求平均，那么该算法会在任意回归数据集上达到最小可能的训练误差（如果存在两个相同的输入对应不同的输出，那么训练误差可能会大于零）。
最后，我们也可以将参数学习算法嵌入另一个增加参数数目的算法来创建非参数学习算法。例如，我们可以想象这样一个算法，外层循环调整多项式的次数，内层循环通过线性回归学习模型。
理想模型假设我们能够预先知道生成数据的真实概率分布。然而这样的模型仍然会在很多问题上发生一些错误，因为分布中仍然会有一些噪声。在监督学习中，从 x 到y的映射可能内在是随机的，或者y可能是其他变量（包括 x 在内）的确定性函数。从预先知道的真实分布p（ x ，y）预测而出现的误差被称为贝叶斯误差 （Bayes error）。
训练误差和泛化误差会随训练集的大小发生变化。泛化误差的期望从不会因训练样本数目的增加而增加。对于非参数模型而言，更多的数据会得到更好的泛化能力，直到达到最佳可能的泛化误差。任何模型容量小于最优容量的固定参数模型会渐近到大于贝叶斯误差的误差值，如图3所示。值得注意的是，具有最优容量的模型仍然有可能在训练误差和泛化误差之间存在很大的差距。在这种情况下，我们可以通过收集更多的训练样本来缩小差距。
图3 训练集大小对训练误差、测试误差以及最优容量的影响。通过给一个5阶多项式添加适当大小的噪声，我们构造了一个合成的回归问题，生成单个测试集，然后生成一些不同尺寸的训练集。为了描述95％置信区间的误差条，对于每一个尺寸，我们生成了40个不同的训练集。（上）两个不同的模型上训练集和测试集的MSE，一个二次模型，另一个模型的阶数通过最小化测试误差来选择。两个模型都是用闭式解来拟合。对于二次模型来说，当训练集增加时，训练误差也随之增大。这是由于越大的数据集越难以拟合。同时，测试误差随之减小，因为关于训练数据的不正确的假设越来越少。二次模型的容量并不足以解决这个问题，所以它的测试误差趋近于一个较高的值。最优容量点处的测试误差趋近于贝叶斯误差。训练误差可以低于贝叶斯误差，因为训练算法有能力记住训练集中特定的样本。当训练集趋向于无穷大时，任何固定容量的模型（在这里指的是二次模型）的训练误差都至少增至贝叶斯误差。（下）当训练集大小增大时，最优容量（在这里是用最优多项式回归器的阶数衡量的）也会随之增大。最优容量在达到足够捕捉模型复杂度之后就不再增长了
一、没有免费午餐定理
学习理论表明机器学习算法能够在有限个训练集样本中很好地泛化。这似乎违背一些基本的逻辑原则。归纳推理，或是从一组有限的样本中推断一般的规则，在逻辑上不是很有效。为了逻辑地推断一个规则去描述集合中的元素，我们必须具有集合中每个元素的信息。
在一定程度上，机器学习仅通过概率法则就可以避免这个问题，而无须使用纯逻辑推理整个确定性法则。机器学习保证找到一个在所关注的大多数样本上可能正确的规则。
可惜，即使这样也不能解决整个问题。机器学习的没有免费午餐定理 （no free lunch theorem）表明（Wolpert，1996），在所有可能的数据生成分布上平均之后，每一个分类算法在未事先观测的点上都有相同的错误率。换言之，在某种意义上，没有一个机器学习算法总是比其他的要好。我们能够设想的最先进的算法和简单地将所有点归为同一类的简单算法有着相同的平均性能（在所有可能的任务上）。
幸运的是，这些结论仅在我们考虑所有可能的数据生成分布时才成立。在真实世界应用中，如果我们对遇到的概率分布进行假设，那么可以设计在这些分布上效果良好的学习算法。
这意味着机器学习研究的目标不是找一个通用学习算法或是绝对最好的学习算法，而是理解什么样的分布与人工智能获取经验的“真实世界”相关，以及什么样的学习算法在我们关注的数据生成分布上效果最好。
二、正则化
没有免费午餐定理暗示我们必须在特定任务上设计性能良好的机器学习算法。我们建立一组学习算法的偏好来达到这个要求。当这些偏好和我们希望算法解决的学习问题相吻合时，性能会更好。
至此，我们具体讨论修改学习算法的方法，只有通过增加或减少学习算法可选假设空间的函数来增加或减少模型的容量。所列举的一个具体示例是线性回归增加或减少多项式的次数。到目前为止讨论的观点都是过度简化的。
算法的效果不仅很大程度上受影响于假设空间的函数数量，也取决于这些函数的具体形式。我们已经讨论的学习算法（线性回归）具有包含其输入的线性函数集的假设空间。对于输入和输出确实接近线性相关的问题，这些线性函数是很有用的。对于完全非线性的问题它们不太有效。例如，我们用线性回归，从x预测sin(x)，效果不会好。因此我们可以通过两种方式控制算法的性能，一是允许使用的函数种类，二是这些函数的数量。
在假设空间中，相比于某一个学习算法，我们可能更偏好另一个学习算法。这意味着两个函数都是符合条件的，但是我们更偏好其中一个。只有非偏好函数比偏好函数在训练数据集上效果明显好很多时，我们才会考虑非偏好函数。
例如，可以加入权重衰减 （weight decay）来修改线性回归的训练标准。带权重衰减的线性回归最小化训练集上的均方误差和正则项的和J（ w ），其偏好于平方L 2 范数较小的权重。具体如下
其中λ是提前挑选的值，控制我们偏好小范数权重的程度。当λ=0时，我们没有任何偏好。越大的λ偏好范数越小的权重。最小化J（ w ）可以看作拟合训练数据和偏好小权重范数之间的权衡。这会使得解决方案的斜率较小，或是将权重放在较少的特征上。我们可以训练具有不同λ值的高次多项式回归模型，来举例说明如何通过权重衰减控制模型欠拟合或过拟合的趋势，如图4所示。
图4 我们使用高阶多项式回归模型来拟合图1中的训练样本。真实函数是二次的，但是在这里只使用9阶多项式。我们通过改变权重衰减的量来避免高阶模型的过拟合问题。（左）当λ非常大时，我们可以强迫模型学习到一个没有斜率的函数。由于它只能表示一个常数函数，所以会导致欠拟合。（中）取一个适当的λ时，学习算法能够用一个正常的形状来恢复曲率。即使模型能够用更复杂的形状来表示函数，权重衰减也鼓励用一个带有更小参数的更简单的模型来描述它。（右）当权重衰减趋近于0（即使用Moore-Penrose伪逆来解这个带有最小正则化的欠定问题）时，这个9阶多项式会导致严重的过拟合，这和我们在图1中看到的一样
更一般地，正则化一个学习函数 f（x；θ） 的模型，我们可以给代价函数添加被称为正则化项 （regularizer）的惩罚。在权重衰减的例子中，正则化是
。
表示对函数的偏好是比增减假设空间的成员函数更一般地控制模型容量的方法。我们可以将去掉假设空间中的某个函数看作对不赞成这个函数的无限偏好。
在权重衰减的示例中，通过在最小化的目标中额外增加一项，我们明确地表示了偏好权重较小的线性函数。有很多其他方法隐式或显式地表示对不同解的偏好。总而言之，这些不同的方法都被称为正则化 （regularization）。正则化是指修改学习算法，使其降低泛化误差而非训练误差。正则化是机器学习领域的中心问题之一，只有优化能够与其重要性相提并论。
没有免费午餐定理已经清楚地阐述了没有最优的学习算法，特别是没有最优的正则化形式。反之，我们必须挑选一个非常适合于我们所要解决的任务的正则形式。深度学习中普遍的理念是大量任务（例如所有人能做的智能任务）也许都可以使用非常通用的正则化形式来有效解决。