差异与波动平衡 Bias/Variance Tradeoff
我们在之前的课程中已讲到，选择不合适的模型进行拟合会导致欠拟合（Underfitting）和过拟合问题（Overfitting），在这一讲中，我们将针对这一问题，给出更深度的讨论。直观而言，欠拟合来自于“简单”的模型，而过拟合来自于“复杂”的模型，如下图所示
正如我们之前讨论的那样，如右图那样对训练集精确拟合的高阶函数，在对测试集进行处理时依然存在较大的误差，这一误差称为泛化误差Generalization Error，对应的，与训练集产生的误差称为Training Error。上图中左右两幅图都有巨大的泛化误差，但很明显它们具有不同的产生原因。
如左图所示，我们称差异BIas为尽管拟合了更大规模训练集也会产生的泛化误差的期望，这是欠拟合的表现。泛化误差的另一部分来自于波动Variance，如右图所示，即由于过于追求细节而没有反映出更广泛的模式。
一般而言，这两种误差都是不可避免的，如果我们选择了过少的参数来表达模型，我们的模型会比较“简单”，这样会产生差异Bias；如果我们选择了过多的参数，我们的模型会比较“复杂”，这样会产生波动Variance。在上图中，二次函数较好的表现了训练集的模式，我们可以认为其达到了一个较好的平衡，当应注意，其依然存在差异和波动。
联合界定理 The Union Bound
联合界定理可表述如下，在概率论中一般被认为是一个公理，可简单称为事件和的概率小于等于事件概率的和。
霍弗丁不等式 Hoeffding Inequality
霍弗丁不等式来自于大数定理，但它的适用条件比大数定律要宽松，其定义如下，也称为切尔诺夫不等式
经验风险最小化 Empirical Risk Minimize ERM
假定我们给定训练集 S={(xi,yi);i=1,...m}，各训练元素服从独立同分布D。我们定义训练误差（也称为经验风险或经验误差）为
同样我们定义泛化误差为
我们定义假设函数
，我们的目标是选择最小化经验风险的θ，如下
在此θ条件下我们得到的假设函数为
。ERM算法是一种很基础的算法，我们之前介绍过的算法如Logistic算法都可认为是ERM算法的近似。
我们定义假设集
是分类问题所有假设的集合，此时ERM算法可认为是从假设集中选出最合适的假设
有限假设集问题 The Case of Finite H
我们假设一个假设集H={h1,...hk}有k个假设函数，每一个假设函数都可将输入数据映射到{0,1}。我们希望证明通过ERM算法求得的假设h的泛化误差存在上界。我们的证明将分两步进行：1）我们将证明ε_hat(h)是对所有h的ε(h)的可信估计；2）我们将这将给出h_hat泛化误差的上界。
我们任取一个hi固定，假设一个伯努利变量Z定义如下：在分布D中采样(x,y)，令Z=1{hi(x)=y}。同样我们可以定义Zj=1{h(xj) != yj}，此时训练误差可写为
此时ε_hat是m个随机变量Zj的均值，然后我们应用Hoeffding不等式
，令事件Ai表示
，使用联合界定理可得
对两边取反，有
因此我们有不低于1-2k*exp(2*γ^2*m)的概率认为ε(h)在ε_hat(h)的γ界内，这一结果称为一致收敛Uniform Convergence，这一结果对所有h都成立。在这一问题中，我们有三个变量γ、m和错误的概率1-δ，当确定两项即可求得第三项，因此我们有
，这一对规模的限制成为采样复杂度 Sample Complexity。
同样我们有
，定义
为假设集中的最优解，因此我们有
综上所述，我们可以得出如下定理
上试中的第一项表示差异，随着更大的假设集而减小，而第二项表示波动，随k的增加而增加。我们可以得到下列采样复杂边界Sample Complexity Bound
//这里是分割线~
//顺便给自己的公众号打个广告，希望大家多多关注~
//关注我的公众号可以看到更多有意思的东西哦~
