Capacity, underfitting, and overfitting

Training error, and test error(generalization error)

机器学习算法的主要挑战是：我们所使用的算法模型必须能够在先前未观测到的新输入上表现良好，而不只是在训练集上表现良好。这种“在先前未观测到的输入上表现良好”的能力被称为泛化(generalization)。

在通常情况下，训练机器学习模型时，我们可以使用某个训练集，在训练集上计算一些被称作训练误差(training error)的度量误差(即损失函数，目标函数)，训练的目标就是降低训练误差。对于优化问题而言，我们只需要降低训练误差即可，而机器学学习算法和优化算法不同的地方在于，我们在降低训练误差的同时，也希望泛化误差(generalization error, 有时也被称为测试误差(test error))很低。泛化误差被定义为新输入的误差期望。

通常，我们度量模型在训练集中分出来的测试集(test set，按照作者在此处所述，称其为验证集(validation set)更为确切)样本上的性能，来评估机器学习模型的泛化误差。例如，在对于简单的线性回归示例中，我们通过最小化training error来训练模型：

但实际上，我们真正关注的是generalization error：

但是，严谨地讲，test set的“未知性”意味着我们无法直接观测到测试集。那么，当我们只能观测到训练集时，如何才能提高测试集的性能呢？

统计学习理论(statistical learning theory)提供了一些答案。如果training test和test set的数据是任意收集的，那么我们能做的的确很有限；但是，如果对training test和test set的收集方式做出一些假设，那么我们就能够对算法做出一些改进。

我们可以将training set和test set看作通过数据集上被称作数据生成过程(data generating process)的概率分布生成。通常，我们会做一系列被统称为独立同分布假设(i.i.d. assumption)。该假设的含义是，每个数据集中的样本都是彼此相互独立的(independent)，并且training set和test set是同分布的(identically distributed)，采样自相同的分布。我们称这个共享的潜在分布为数据生成分布(data generating distribution)，记作$p_{data}$。这个概率框架和独立同分布假设允许我们从数学上研究训练误差和测试误差之间的关系。

我们能观察到的training error和无法观察到的test error之间的直接关系是：training error的期望和test error的期望是一致的。假设我们有概率分布$p(x,y)$，从中重复采样生成training set和test set，对于某个固定的参数，training error和test error的期望是一样，这是因为这两个期望的计算都使用了相同的数据生成过程。training set和test set之间唯一的区别就是数据集的名字不同。

但是在实际中，$p(x,y)$的参数并不是固定的，在这种情况下， test error的误差期望就会大于或等于training error的期望。因此，我们主要从以下两个方面来构建“效果良好”的机器学习算法：

• 尽可能地降低training error；
• 尽可能缩小training error和test error之间的差距；

Underfitting, overfitting, and capacity

我们在这两个方面的努力对应着在训练机器学习算法时所面临的两个主要挑战：欠拟合(underfitting)和过拟合(overfitting)。欠拟合是指模型不能够在训练集上获得足够低的误差，而过拟合则是指训练误差和测试误差之间的差距过大。

我们可以通过调整模型的容量(capacity)来控制模型是否偏向于过拟合或者欠拟合。通俗地讲，模型的容量是指其拟合各种函数的能力。容量低的模型可能很难拟合训练集，因而training error就较大；而容量高的模型可能会过拟合，因为记住了不适用于测试集的训练集性质(噪声)，导致training error和test error之间的差距较大。

一种控制算法容量的方法是选择假设空间(hypothesis space)，即学习算法可以选择为解决方案的函数集。例如，线性回归算法将关于其输入的所有线性函数作为假设空间；广义线性回归的假设空间包括多项式函数，而非仅有线性函数，后者就增加了模型的容量。

比如，一次多项式提供了线性回归模型：

通过引入$x^2$作为线性回归模型的另一个特征，我们能够学习关于特征$x$的二次函数模型：

我们可以继续添加$x$的更高次幂作为额外的特征，比如使用下面的9次多项式：

从上面的讨论我们可以知道，当算法的容量过高或过低都不合适，当机器学习算法的容量适用于(1)所执行任务的复杂度和(2)所提供训练数据的数量时，算法效果通常会最佳。容量不足的模型不能解决复杂任务，而容量高的模型虽然能够解决复杂的任务，但是当其容量高于任务所需时，有可能会过拟合。下图就展示了这个原理的使用情况。

上图中比较了线性、二次和九次函数拟合真实二次函数函数的效果。可以看到，线性函数无法刻画真实函数的曲率，所以是欠拟合的；九次函数能够表示正确的函数，但是由于训练的参数比训练样本还多，它能够表示无限多个刚好穿过训练样本点的很多函数，我们不太可能从很多不同的解中选出一个泛化良好的解。在这个问题中，二次模型就非常符合任务的真实结构，因此它可以很好地泛化到新数据上。

Representational capacity(of the model family), and effective capacity(of the learning algorithms)

上述改变模型容量的方式，是通过改变输入特征的数目和加入这些特征对应的参数实现的。实际上，这只是其中一种方式，还有很多方法可以改变模型的容量。容量不仅仅取决于模型的选择。当选定了一个模型后，我们需要使用某种特定的学习算法来拟合模型的参数。模型的选择规定了学习算法可以从哪些函数族中选取函数，这称为模型的表示容量(representational capacity)。但是在很多情况下，从这些函数中学习出最优的函数是非常困难的优化问题。实际中，学习算法不会真的找到最优函数，而仅仅是找到了一个可以大大降低训练误差的函数。其他的额外的限制因素，比如说优化算法的不完美，可能意味着学习算法的有效容量(learning algorithm’s **effective capacity**)可能小于函数族的表示容量(the representational capacity of the model family)。

Occam’s razor

提高机器学习模型的现代思想可以追溯到托勒密使其的哲学家的思想。许多早期的学者提出一个简约的原则，现在被广泛地称为奥卡姆提到(Occam’s razor)。该原则指出，在同样能够解释一致观测现象的假设中，我们应该挑选出“最简单”的那一个。

Quantifying the capacity of the model(VC dimension)

统计机器学习理论提供了量化模型容量的不同方法。在这些方法中，最有名的是Vapnik-Chervonenkis维度(Vapnik-Chervonenkis dimension, VC)，简称VC维。VC维度量二元分类器的容量。VC维定义为该分类器能够分类的训练样本的最大数目。假设存在$m$个不同的$x$点的训练集，分类器可以任意地标记该$m$个不同的$x$点，VC维被定义为$m$的最大可能值。

量化模型的容量使得统计学习理论可以进行量化预测。统计学习理论中最重要的结论阐述了：训练误差和泛化误差之间的误差的上界随着模型容量增长而增长，但随着样本增多而下降。这些边界为机器学习算法可以有效解决问题提供了理论验证，但是它们很少应用于实际中的深度学习算法，其原因主要在于两个方面：

• 一部分原因是边界太松；
• 另一部分原因是我们很难确定深度学习算法的容量；

正如前面所阐述的，模型的有效容量受限于优化算法的能力，确定深度学习模型容量的问题就变得特别困难。并且对于深度学习中的一般凸优化问题，我们只有很少的理论分析。

我们必须要记住的是：虽然更简单的函数更可能泛化(即训练误差和测试误差的差距小)，但是我们仍然需要选择一个充分复杂的假设以达到低的训练误差。通常，当模型容量上升时，训练误差会下降，知道其渐进最小可能误差(假设误差度量有最小值)。如下图所示，泛化误差通常是一个关于模型容量的U形曲线。

The No Free Lunch Theorem

学习理论表明机器学习算法能够在有限个训练集样本中很好地泛化。这似乎违背一些基本的逻辑原则。从逻辑上讲，归纳推理(Inductive reasoning)，或者说从一个有限的样本中推断一般的规则，是无效的(not logically valid)。因为，为了从逻辑上推断出一个规则去描述，我们必须具有集合中每个元素的信息，如果只是在训练集上推断，那么得出的结论并不一定有效。

在一定程度上，机器学习仅仅是通过概率法则(probabilistic rules)来避免这个问题，而不是使用纯逻辑推理(purely logical reasoning)推理整个的确定性法则(entirely certain rules)。机器学习算法只是保证找到一个在所关注的大多数样本上可能正确的规则。

遗憾的是，即使这样也不能解决整个我们所关注的问题。机器学习的没有免费午餐定理(no free lunch theory)表明，在所有可能的data-generating distributions平均之后，每一个分类算法在previously unobserved points上都有相同的错误率。也就是说，在某种意义上，没有一个机器学习算法总是比其他的算法好。我们能够设想的最先进的算法和简单地所有点归为同一类的简单算法有着相同的平均性能(在所有可能的任务上)。

但是，幸运的是，这些结论仅仅在我们考虑所有可能的data-generating distribution时才成立。在实际应用时，如果我们对遇到的概率分布进行假设，那么可以设计在这些分布上效果良好的学习算法。

这同样意味着，机器学习算法的目标不是找到一个通用的(universal)学习算法或者绝对最好的(absolute best)学习算法，而是理解什么样的分布与人工智能获取经验“真实世界”相关，以及什么样的学习算法在我们关注的数据生成分布上效果最好。

Regularization and Regularizer

没有免费午餐定理暗示我们必须针对特定任务(specific task)设计性能良好的机器学习算法。我们建立一组具有特定偏好的学习算法来达到这个要求。当这些偏好和我们希望算法解决的学习问题相吻合时，性能会更好。

在前文中，我们通过改变学习算法可选假设空间的函数来改变模型的容量，但实际上，算法的效果不仅受假设空间的函数数量的影响，也取决于这些函数的具体形式。比如，线性回归学习算法具有包含其输入的线性函数集的假设空间。对于输入和输出确实接近线性相关的问题，这些线性函数是有用的。但是，对于完全非线性的问题，它们就不太有效。例如，我们用线性回归，从$x$预测$\sin(x)$，效果不太好。但是，我们可以通过两种方法控制算法的性能，一是允许使用的函数种类，二是这些函数的数量。

在假设空间中，相比与某一种学习算法，我们可能更偏好另一种学习算法，这意味着两个函数都是符合条件的，但是我们更偏好其中一个。只有非偏好函数比偏好函数在训练数据集上效果明显好得多时，我们才会考虑非偏好函数。

例如，我们可以加入线性衰减(weight decay，也就是常说的岭回归)来修改线性回归的训练标准。带权重衰减的线性回归最小化训练集上的均方误差和正则项的和$J(w)$，其偏好于平方$L^2$范数较小的权重。具体如下：

其中，$\lambda$为提前挑选的值，控制我们偏好范数权重的程度。当$\lambda=0$时，我们没有任何偏好。越大的$\lambda$偏好范数越小的权重。最小化$J(w)$可以看作拟合数据和偏好最小权重范数之间的权衡。这会使得解的斜率较小，或是将权重放在较小的特征上。我们可以训练具有不同$\lambda$值得高次多项式回归模型，来说明权重衰减对于模型欠拟合和过拟合的控制，如下图所示。

在上图中，我们使用9阶多项式拟合真实函数是二次函数的训练样本。我们通过改变权重衰减的量来避免高阶模型的过拟合问题。在左图中，当$\lambda$非常大时，则可以强迫模型学习到一个没有斜率的函数。由于它只能表示一个常数函数，所以会导致欠拟合；在中间的图中，去一个适当的$\lambda$值，学习算法能够用一个正常的形状来恢复斜率，并且即使模型能够用更复杂的形状来表示函数，权重衰减项的存在也鼓励用一个具有更小参数的更简单的模型来描述它；在右图中，当权重衰减趋近于0时(即使用Moore-Penrose)伪逆来解决这个带有最小正则化的前定问题)，这个9阶多项式会导致严重的过拟合。

表示对函数的偏好是比增减假设空间的成员函数更一般地控制模型容量地方法。我们可以将去掉假设空间中的某个函数看作对不赞成这个函数的无限偏好。

更一般地，正则化一个学习函数$f(x;\theta)$，我们可以给代价函数添加被称为正则化项(regularizer)的惩罚。在上面权重衰减的例子中，正则化项是$\Omega(w)=w^Tw$，通过在最小化的目标中额外增加一项，我们明确地表示了偏好权重较小的线性函数。除此之外，我们还可以使用其他方法隐式地(比如early stopping技术)或者显式地表示对不同解的偏好。总而言之，这些不同的方法(技术)都被称为正则化(regularization)。应当明确的是，正则化是指修改学习算法，使其降低泛化误差而非训练误差。并且，正则化是机器学习领域的中心问题之一，只有优化能够与其重要性相提并论。

免费午餐定理已经清楚地阐述了没有最优的学习算法，特别是没有最优的正则化形式。反之，我们必须针对所要解决的问题，挑选一个非常适用的正则形式，这就需要我们对所解决的问题有相当程度的了解。

另外，深度学习中普遍的理念是：大量任务(例如所有人类能够做的智能任务)也许都可以使用非常通常的(general-purpose)正则化形式来有效解决。

Reference

[1] Ian Goodfellow and Yoshua Bengio and Aaron Courville. Deep Learning. MIT Press.