学习理论之偏差与方差

1. 偏差和方差平衡

在线性回归中，对于同一个数据集，可以拟合出简单的线性模型或者较为复杂一些的多项式例如：

图中的训练样本是一致的，但是可以拟合出不同的模型。最右边图中拟合出的5阶多项式，并不见得就是一个好模型，虽然该模型能够准确预测出样本点的y值,因为这种模型过分拟合了训练样本（过拟合），当对非训练样本预测时，往往效果很糟糕，即由训练集拟合出的这个模型泛化能力很差。某个假设的泛化误差就是该假设用于预测新样本时的期望误差与其用于预测训练集样本的误差不一致。

而最左边的模型由于拟合程度不够，导致对训练集的预测都很糟糕（欠拟合），泛化误差也很大。由图中所画样本点很容易看出，y与x是非线性关系，即使我们用大量的数据拟合出来一个线性模型，这个模型仍然不能准确的拟合出数据结构特征。我们定义偏差（bias）对预期的泛化误差进行建模，那么最左边图中的线性模型存在较大偏差。

除了偏差，还可以用方差（variance）来衡量模型的泛化误差。特别是上面最右边的5阶模型，很有可能就是该模型就仅仅是对图中所示的几个样本（有限样本集）有效，而没有真正拟合出x和y之间的关系模式，对新的测试样本效果很差，因此得到的模型泛化误差同样很大。这时，我们就说模型的方差较大（可以形象理解为模型波动较大）。

所以，需要在偏置和方差之间加以平衡。当模型过于简单，参数较少，则偏差较大（但是方差较小），当模型过于复杂，参数很多，则方差较大（但是偏差较小）。因此，对于上面的例子，拟合出一个二次函数要比左右两端的模型都要好。

2. 预备知识

定理（联合边界）如果 A₁, A₂, ..., A_k是 k 个不同的事件（不一定互相独立），那么：

这是概率论中的一个公理，直观上很容易理解：k个不同事件并的发生概率小于k个事件各自发生的概率之和。

定理（Hoeffding不等式）如果Z1, ... Zm 是 m 个独立同分布的随机变量，且服从伯努利分布，即，，用表示这些随机变量的均值，给定任意正数，那么：

由概率论可知，就是伯努利分布的期望，而是通过m个样本得出的对的估计，所以这个定理的意思是，随着样本数量m的增加，样本估计的均值与期望的差别会越来越小。

下面会用这两个定理来证明一些很重要的学习理论。为了简化起见，这里讨论二分类问题，标签是，所有讨论都可以泛化到其他问题，如回归和多分类问题。

给定训练集：，所有样本独立同分布，均服从分布. 定义训练误差（又叫经验风险或者经验误差）如下：

注意这里的符号“1{}”，表示如果{}里面的表达式为真，则1{} = 1，否则为0，如1{3=2} = 0,1{3=3}=1.

所以这个定义就是计算被错分类的样本占所有样本的比例。

如果将于训练集 S 联系起来，即训练集的训练误差，就可以写为. 再定义泛化误差：

这个定义的意思是，现在随机采样一个服从分布的新样本（不是从训练集中随机选，而是重新采样），那么这个样本被错分的概率就是泛化误差。

考虑线性分类，令，通过什么样的方式拟合参数才合理呢？一种方法是最小化训练误差：

我们称这个过程为经验风险最小化（empirical risk minimization，ERM）,拟合出的模型就是. ERM是一种最基本的算法（逻辑回归算可以近似看做一种经验风险最小化）。

在我们的讨论学习理论时，将参数和假设从具体的问题中抽象出来会很有用。定义一个假设类，它表示某一类问题对应的分类器的集合。对于线性分类，就表示所有输入为，决策边界为线性的分类器。更加广泛地说，如果我们学习一个神经网络，那么可以令表示某种神经网络结构。

经验风险最小化现在可以被认为是在的基础上进行，即学习算法在中选出训练误差最小的假设：

3. 有限假设集（The case of finite ）

这一部分讨论有限假设集学习问题，在这个问题中，假设集包含 k 个假设。因此是一个包含 k 个函数的集合，这 k 个函数将映射到{0, 1}.

对于任意一个给定的假设，考虑伯努利随机变量. 采样，然后，令.也即是说我们随机采取样本，用来表示假设是否错分了该样本。类似地，可以定义.由于训练集是由分布中采样出的独立同分布样本组成，所以和服从同一分布。

可以看出对随机样本错分的概率就是（和）的期望值（注意不是训练集的元素，是训练集的元素）。训练误差可以写为：

容易看出，就是 m 个随机变量的均值，所以是由一个伯努利分布采样出来的一系列独立同分布变量，这个伯努利的分布的均值是（因为上面讨论过和服从同一分布，的所服从分布的均值是，所以所服从分布的均值也是），那么应用上面提到的Hoeffding不等式：

这表明，当 m 很大的时候，对于特定的假设，训练误差和泛化误差非常接近（很高的概率），

但是，我们不只是想只保证某一个特定假设的训练误差和泛化误差非常接近，而是针对所有均同时有该结论成立，下面将证明之。

令表示事件，已知对任意一个特定的，有成立，我们要证明的是对于所有的（i = 1, ... , m）,有 m 个不等式可以同时成立。利用联合边界：

用1 同时减去等式两边：

这个不等式的意思是，至少有的概率，“和的差值小于”这个事件对所有同时成立。这叫做一致收敛的结果，因为

这个界限是对所有同时成立，而不是只对某一个假设成立。

继续，给定和某个，上面讨论的过程中都是说当 m 足够大的时候，就可以保证训练误差和泛化误差的差值小于（任意小的正数）的概率至少为（注意由上面讨论容易看出，m足够大的时候是趋向0的，例如就是一个的特例）。到底m多大才和合适？

令，可以发现如果：

那么就可以保证对于所有，同时成立的概率至少是. 这个界限给出了到底需要多少个训练样本，才能使的训练误差和泛化误差的差别很小。某个方法或者算法为了到达某种指标所采取的训练集的大小，也就是训练样本的个数被称为采样复杂度。

对于，固定m和，可以解出，又，所以：

现在假设一致收敛成立，即对于所有，有成立。定义是中可能最好的假设，为什么说是可能最好的假设呢？因为你是在集合的基础上选择假设，但是真正最佳假设可能不在这个集合里面，但是对于这个集合中的假设而言，就是最佳的。现在我们通过学习算法选出的假设为：，有必要比较下学习算法选出的集合中的某一个假设与：

第一行用到了不等式（利用了前面说的一致收敛成立的假设），第二，是通过最小化选择出来的，因此，又本身就是一个的特例，所以，第三行再次用到一致收敛假设。所以，可以看出，如果一致收敛成立，的泛化误差最多与中最好的假设的泛化误差相差

以定理的形式写出上面的结论：

定理：令，固定m和，那么不等式：

成立的概率至少是.

这个定理也量化出关于前面提到的偏差/方差平衡重的模型选择。特别地，假如我们有一个假设集，现在扩大假设集，对于，那么第一项只能减小（因为我们是在一个更大的函数集合中选出最小值），所以通过对一个更大的假设集学习之后，偏差（bias）只会减小。但是第二项而言，假设集变大就意味着 k变大，该项显然会变大，这一项的变大就对应着增大假设集时，方差（variance）会变大。

通过固定和，解出m,可以得到采样复杂度的界限：

推论令，固定和，不等式成立的最小概率是，那么将满足如下不等式：

4. 无限假设集（The case of infinite ）

上面对于有限假设集证明除了一些很有用的定理，但是对于很多假设集，我们可以提出无限多的假设函数，那么该假设集就是一个无限假设集。对于无限假设集是否与有限假设集存在类似的结论呢？

假设有d个实数参数，在计算机中双精度（double-precision）浮点数是64位，假定我们参数都采用双精度表示，那么我们的假设集可包含多达个不同的假设，从上一部分的最后一个推论，为了保证成立的最小概率是，必须满足：

可以说，固定和了之后，需要的训练样本的数量与模型参数数量几乎是线性关系。

由上面的例子可以大致得出一个结论：如果我们想最小化训练误差（经验风险），为了在含有d个参数的假设集中学习出较好的模型，通常需要的训练样本数需与d成一个线性关系。

从这一点出发，需要注意，这些所有我们已经证明的理论是对采用经验风险最小化（ERM）的算法成立，注意经验风险就是训练误差，二者是同一个概念，所以对大多数采用ERM或者类似于ERM的判别式学习算法（discriminative learning algorithms），采用复杂度（即需要的训练样本数）与参数个数之间的线性依赖关系是成立的，但是对于并不是对所有判别式学习算法成立，关于非-ERM学习算法的理论仍在研究阶段。

上面的推理仍然难以令人满意，因为它依赖于假设集的参数。下面进一步讨论,将会给出更多定义。

给定集合（和训练集无关），，如果对于任意一个标签集合，总存在某个假设使得（）成立，那么就说可分（shatters）.