1.6 泛化能力
1.6.1 泛化误差
泛化能力是指模型对未知数据的预测能力。
现实中采用最多的办法是通过测试误差来评估泛化能力，但测试数据集是有限的，由此得到的评价是不可靠的。
现从理论上对泛化能力进行分析，首先给出泛化误差的定义。
如果学习到的模型是
，那么该模型对未知数据的泛化误差为，即期望风险：
1.6.2 泛化误差上界
泛化误差上界通常用来比较两种学习方法的优劣，且具有以下性质：
- 它是样本容量的函数，当样本容量增加时，泛化误差上界趋于0；
- 它是假设空间容量的函数，当假设空间容量越大，泛化误差上界就越大，模型就越难学；
已知训练集
，
是样本容量，
是从联合概率分布
独立同分布产生的，
，
。假设空间是函数的有限集合
，
是函数个数。设
是从
中选的选取的0-1损失函数。关于
的期望风险和经验风险分别是：
下面讨论从有限集合
中任意选出的函数
的泛化误差上界。
定理（二分类泛化误差上界） 对二分类问题，当假设空间是有限个函数的集合
时，对于任意一个函数
，至少以概率
，以下不等式成立：
其中，
对于一般的假设空间要到泛化误差上界不作介绍
证明
对任意函数
，
是
个独立的随机变量
的样本均值，
是
个独立的随机变量
的期望值
对所有
，那么由 Hoffding’s Inequality 不难得知，对
，以下不等式成立：
由于
是一个有限集合，故：
上式表明假设空间至少存在一个函数满足条件的概率，等价于：
令：
，解得：
，代入上式得到：
回顾泛化误差上界的性质，
- 它是样本容量的函数，当样本容量增加时，泛化误差上界趋于0；
- 它是假设空间容量的函数，当假设空间容量越大，泛化误差上界就越大，模型就越难学；
补充：Markov’s Inequality
是非负随机变量，则对任意
，有：
证明
补充：Hoffding’s Lemma
是一个随机变量，取值于
区间，且
%3D0#card=math&code=E%28X%29%3D0&id=LwzPV)，那么对于任意
，有：
%20%5Cle%20e%5E%5Cfrac%7B%5Clambda%20%5E%202%20(b-a)%5E2%7D%7B8%7D%0A#card=math&code=E%28e%5E%7B%5Clambda%20x%7D%29%20%5Cle%20e%5E%5Cfrac%7B%5Clambda%20%5E%202%20%28b-a%29%5E2%7D%7B8%7D%0A&id=Ss1RI)
证明
设
#card=math&code=f%28x%29&id=wIG4p)在
上是凸函数，根据图函数的性质，则有如下不等式：
%20%5Cle%20f(a)%2B%5Cfrac%7Bf(b)-f(a)%7D%7Bb-a%7D(x-a)%EF%BC%8Cx%20%5Cin%20%5Ba%2Cb%5D%0A#card=math&code=f%28x%29%20%5Cle%20f%28a%29%2B%5Cfrac%7Bf%28b%29-f%28a%29%7D%7Bb-a%7D%28x-a%29%EF%BC%8Cx%20%5Cin%20%5Ba%2Cb%5D%0A&id=kPvlU)
显然%3De%5E%7B%5Clambda%20x%7D#card=math&code=f%28x%29%3De%5E%7B%5Clambda%20x%7D&id=wU2Ox)亦是凸函数，代入后：
将
看作
上的随机变量
，对上述不等式同时取期望，我们有：
%20%5Cle%20%5Cfrac%20%7Bb-E(x)%7D%7Bb-a%7De%5E%7B%5Clambda%20a%7D%20%2B%20%5Cfrac%7BE(x)-a%7D%7Bb-a%7De%5E%7B%5Clambda%20b%7D%0A#card=math&code=E%28e%5E%7B%5Clambda%20x%7D%29%20%5Cle%20%5Cfrac%20%7Bb-E%28x%29%7D%7Bb-a%7De%5E%7B%5Clambda%20a%7D%20%2B%20%5Cfrac%7BE%28x%29-a%7D%7Bb-a%7De%5E%7B%5Clambda%20b%7D%0A&id=IrIYs)
由题设条件
%3D0#card=math&code=E%28x%29%3D0&id=VK34H)，化简后得到：
%20%5Cle%20%5Cfrac%20%7Bb%7D%7Bb-a%7De%5E%7B%5Clambda%20a%7D%20-%20%5Cfrac%7Ba%7D%7Bb-a%7De%5E%7B%5Clambda%20b%7D%20%20%3D%20e%5E%7B%5Clambda%20a%7D%5B1%2B%5Cfrac%7Ba%7D%7Bb-a%7D-%5Cfrac%7Ba%7D%7Bb-a%7De%5E%7B%5Clambda(b-a)%7D%5D%0A#card=math&code=E%28e%5E%7B%5Clambda%20x%7D%29%20%5Cle%20%5Cfrac%20%7Bb%7D%7Bb-a%7De%5E%7B%5Clambda%20a%7D%20-%20%5Cfrac%7Ba%7D%7Bb-a%7De%5E%7B%5Clambda%20b%7D%20%20%3D%20e%5E%7B%5Clambda%20a%7D%5B1%2B%5Cfrac%7Ba%7D%7Bb-a%7D-%5Cfrac%7Ba%7D%7Bb-a%7De%5E%7B%5Clambda%28b-a%29%7D%5D%0A&id=Esv1J)
进行变量代换，令
，
%3E0#card=math&code=h%3D%5Clambda%28b-a%29%3E0&id=VWGaS)，代入后得到：
%20%5Cle%20(1-p%2Bpe%5Eh)e%5E%7B-hp%7D%20%3D%20e%5E%7B-hp%2Bln(1-p%2Bpe%5Eh)%7D%3De%5E%7BL(h)%7D%0A#card=math&code=E%28e%5E%7B%5Clambda%20x%7D%29%20%5Cle%20%281-p%2Bpe%5Eh%29e%5E%7B-hp%7D%20%3D%20e%5E%7B-hp%2Bln%281-p%2Bpe%5Eh%29%7D%3De%5E%7BL%28h%29%7D%0A&id=uasbw)
若能证明
%7D%20%5Cle%20e%5E%5Cfrac%7B%5Clambda%20%5E2%20(b-a)%5E2%7D%7B8%7D%20%3D%20e%5E%7B%5Cfrac%7Bh%5E2%7D%7B8%7D%7D#card=math&code=e%5E%7BL%28h%29%7D%20%5Cle%20e%5E%5Cfrac%7B%5Clambda%20%5E2%20%28b-a%29%5E2%7D%7B8%7D%20%3D%20e%5E%7B%5Cfrac%7Bh%5E2%7D%7B8%7D%7D&id=N6EuT)，就可以证明Hoffding’s lemma，即证
%20%5Cle%20%5Cfrac%7Bh%5E2%7D%7B8%7D#card=math&code=L%28h%29%20%5Cle%20%5Cfrac%7Bh%5E2%7D%7B8%7D&id=Hq2sK)，构造：
%3DL(h)-%5Cfrac%7Bh%5E2%7D%7B8%7D%20%3D%20-hp%2Bln(1-p%2Bpe%5Eh)-%5Cfrac%7Bh%5E2%7D%7B8%7D%2C%20p%3E0%2C%20h%20%3E%200%0A#card=math&code=g%28h%29%3DL%28h%29-%5Cfrac%7Bh%5E2%7D%7B8%7D%20%3D%20-hp%2Bln%281-p%2Bpe%5Eh%29-%5Cfrac%7Bh%5E2%7D%7B8%7D%2C%20p%3E0%2C%20h%20%3E%200%0A&id=NMiMz)
显然有：
%3D0%5C%5Cg’(h)%3D-p%2B%20%5Cfrac%7Bpe%5Eh%7D%7B1-p%2Bpe%5Eh%7D-%5Cfrac%7Bh%7D%7B4%7D%5C%5Cg’’(h)%3D%5Cfrac%7Bpe%5Eh(1-p%2Bpe%5Eh)-pe%5E%7B2h%7D%7D%7B(1-p%2Bpe%5Eh)%5E2%7D-%5Cfrac%7B1%7D%7B4%7D%3D%5Cfrac%7B(1-p)pe%5Eh%7D%7B(1-p%2Bpe%5Eh)%5E2%7D-%5Cfrac%7B1%7D%7B4%7D%0A#card=math&code=g%280%29%3D0%5C%5Cg%27%28h%29%3D-p%2B%20%5Cfrac%7Bpe%5Eh%7D%7B1-p%2Bpe%5Eh%7D-%5Cfrac%7Bh%7D%7B4%7D%5C%5Cg%27%27%28h%29%3D%5Cfrac%7Bpe%5Eh%281-p%2Bpe%5Eh%29-pe%5E%7B2h%7D%7D%7B%281-p%2Bpe%5Eh%29%5E2%7D-%5Cfrac%7B1%7D%7B4%7D%3D%5Cfrac%7B%281-p%29pe%5Eh%7D%7B%281-p%2Bpe%5Eh%29%5E2%7D-%5Cfrac%7B1%7D%7B4%7D%0A&id=RHSJZ)
设
，
，根据基本不等式：
%3D%5Cfrac%7Bmn%7D%7B(m%2Bn)%5E2%7D-%5Cfrac%7B1%7D%7B4%7D%3D%5Cfrac%7B1%7D%7B%5Cfrac%7Bm%7D%7Bn%7D%2B%5Cfrac%7Bn%7D%7Bm%7D%2B2%7D%20%5Cle%200%0A#card=math&code=g%27%27%28h%29%3D%5Cfrac%7Bmn%7D%7B%28m%2Bn%29%5E2%7D-%5Cfrac%7B1%7D%7B4%7D%3D%5Cfrac%7B1%7D%7B%5Cfrac%7Bm%7D%7Bn%7D%2B%5Cfrac%7Bn%7D%7Bm%7D%2B2%7D%20%5Cle%200%0A&id=E1qU6)
所以，
%20%5Cdownarrow#card=math&code=g%27%28h%29%20%5Cdownarrow&id=xyRNI)，%3Cg’(0)%3D0#card=math&code=g%27%28h%29%3Cg%27%280%29%3D0&id=MxBKF)，进而%20%5Cdownarrow#card=math&code=g%28h%29%20%5Cdownarrow&id=Iu4m8)，%3Cg(0)%3D0#card=math&code=g%28h%29%3Cg%280%29%3D0&id=FdcXG)
最后 Hoffding’s lemma 成立
补充：Hoffding’s Inequality
是随机独立变量，且
, 
，对任意
，以下不等式成立：
证明
设
，由Markov’s Inequality，可得：
对上式中得期望部分进行化简：
其中，
且 
再对上式中的期望部分使用Hoffding’s Lemma，可得：
将其不断回代，继续化简得：
考虑关于
的二次函数最小值，得到如下不等式：
令
，代入上式，可得：
