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 很大的时候，对于特定的假设，训练误差和泛化误差非常接近（很高的概率），

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

（待续。。。）

学习理论