证明二类分类问题的泛化误差上界

泛化误差上界：

对二分类问题，当假设空间是有限个函数的集合F={f1,f2,f3,...,fn}时，对任意一个函数 $f\epsilon F$ ，至少以概率 $1-\delta$ ，以下不等式成立：

$R(f)\leq \hat{R}(f)+\varepsilon (d,N,\delta)$

其中， $\varepsilon (d,N,\delta )=\sqrt{1/2N(logd+log(1/\delta ))}$

不等式右端第一项为训练误差，训练误差越小，泛化误差就越小

第二项为N的单调递减函数，当N趋于无穷时其趋于0，且假设空间包含的函数越多，其值越大

以下为证明过程：

首先，因为证明过程要用到Hoeffding不等式，叙述如下：

设 $S_{n}=\sum_{i=1}^{n}X_{i}$ 是独立随机变量X1,X2,...,Xn之和， $X_{i}\epsilon [ai,bi]$ ，则对任意t>0，以下不等式成立：

$P(S_{n}-ES_{n}\geq t)\leq exp(\frac{-2t^{2}}{\sum_{i=1}^{n}(bi-ai)^{2} })$

$P(ES_{n}-S_{n}\geq t)\leq exp(\frac{-2t^{2}}{\sum_{i=1}^{n}(bi-ai)^{2} })$

现有，对任意 $f\epsilon F$ ， $\hat{R}(f)$ 是N个独立随机变量L(Y,f(X))的样本均值， $R(f)$ 是随机变量L(Y,f(X))的期望值，损失函数取值于区间[0,1],即对所有i，[ai,bi]=[0,1]则有：

$S_{n}=\sum_{i=1}^{N}L(Y_{i},f(X_{i}))=NR(f)$

$E(S_{n})=E(\sum_{i=1}^{N}L(Y_{i},f(X_{i})))=\sum_{i=1}^{N}(E(L(Y_{i},f(X_{i})))=\sum_{i=1}^{N}\hat{R}(f)=N\hat{R}(f)$

因为 $P(NR(f)-N\hat{R}(f)\geq N\varepsilon )=P(R(f)-\hat{R}(f)\geq \varepsilon )$

因此，由Hoeffding不等式得：

$P(R(f)-\hat{R}(f)\geq \varepsilon ) \leq exp(-2(N\varepsilon )^{2}/N)=exp(-2N\varepsilon ^{2})$

因为，假设空间是一个有限集合，则有：

$P(R(f)-\hat{R}(f)\geq \varepsilon )\leq dexp(-2N \varepsilon ^{2})$

等价于：

$P(R(f)-\hat{R}(f)\leq \varepsilon )\geq 1-dexp(-2N \varepsilon ^{2})$

令 $dexp(-2N \varepsilon ^{2})= \delta$ ，则至少以概率 $1-\delta$ 有 $R(f)< \hat{R}(f)+ \varepsilon$ 成立

因此，训练误差小的模型，泛化误差也会小