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