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

已知训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\} T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}，它是联合概率分布 P ( X , Y ) P(X,Y) P(X,Y)独立同分布产生的， X ∈ R n , Y ∈ { − 1 , + 1 } X\in R^n, Y\in \{-1,+1\} X∈Rn,Y∈{−1,+1}. 假设空间是函数的有限集合 F = { f 1 , f 2 , . . . , f d } F=\{f_1,f_2,...,f_d\} F={f1​,f2​,...,fd​}，d是函数个数。设f是从F中选取的函数。损失函数是0-1损失，关于f的期望风险和经验风险分别是： R ( f ) = E [ L ( Y , f ( X ) ) ] R ^ ( f ) = 1 N ∑ i = 1 N L ( y i , f ( x i ) ) R(f)=E[L(Y,f(X))] \\ \hat R(f) = \frac{1}{N}\sum_{i=1}^N L(y_i,f(x_i)) R(f)=E[L(Y,f(X))]R^(f)=N1​i=1∑N​L(yi​,f(xi​)) 经验风险最小化函数是： f N = a r g   m i n f ∈ F R ^ ( f ) f_N = arg \space min_{f\in F}\hat R(f) fN​=arg minf∈F​R^(f) f N f_N fN​的泛化能力： R ( f N ) = E [ L , f N ( X ) ] R(f_N)=E[L,f_N(X)] R(fN​)=E[L,fN​(X)] **定理(泛化误差上界)：**对二类分类问题，当假设空间是有限个函数的集合 F = { f 1 , f 2 , . . . f d } F=\{f_1,f_2,...f_d\} F={f1​,f2​,...fd​}时，对任意一个函数 f ∈ F f\in F f∈F，至少以概率 1 − δ 1-\delta 1−δ，以下不等式成立： R ( f ) ≤ R ^ ( f ) + ϵ ( d , N , δ ) (1) R(f) \leq \hat R(f) + \epsilon(d,N,\delta) \tag{1} R(f)≤R^(f)+ϵ(d,N,δ)(1) 其中 ϵ ( d , N , δ ) = 1 2 N ( l o g   d + l o g 1 δ ) \epsilon(d,N,\delta)=\sqrt{\frac{1}{2N}(log\space d+log\frac{1}{\delta})} ϵ(d,N,δ)=2N1​(log d+logδ1​) ​ 不等式（1）左端 R ( f ) R(f) R(f)是泛化误差，右端即为泛化误差上界。在泛化误差上界中，第1项是训练误差，训练误差越小，泛化误差越小。第2项 ϵ ( d , N , δ ) \epsilon(d,N,\delta) ϵ(d,N,δ)是N的单调递减函数，当 N N N趋于无穷时，它趋于0；同时它也是 l o g   d \sqrt{log\space d} log d ​阶的函数，假设空间 F F F包含的函数越多，其值越大。

**证明：**在证明中要用到 H o e f f d i n g Hoeffding Hoeffding不等式，先叙述如下

设 S n = ∑ i = 1 n X i S_n=\sum_{i=1}^nX_i Sn​=∑i=1n​Xi​是独立随机变量 X 1 , X 2 , . . . , X n X_1,X_2,...,X_n X1​,X2​,...,Xn​之和， X i ∈ [ a i , b i ] X_i\in [a_i,b_i] Xi​∈[ai​,bi​]，则对任意 t > 0 t>0 t>0，以下不等式成立： P ( S n − E S n ≥ t ) ≤ e x p ( − 2 t 2 ∑ i = 1 n ( b i − a i ) 2 ) (2) P(S_n-ES_n\geq t) \leq exp(\frac{-2t^2}{\sum_{i=1}^n(b_i-a_i)^2}) \tag{2} P(Sn​−ESn​≥t)≤exp(∑i=1n​(bi​−ai​)2−2t2​)(2)

P ( E S n − S n ≥ t ) ≤ e x p ( − 2 t 2 ∑ i = 1 n ( b i − a i ) 2 ) (3) P(ES_n -S_n \geq t)\leq exp(\frac{-2t^2}{\sum_{i=1}^n(b_i-a_i)^2}) \tag{3} P(ESn​−Sn​≥t)≤exp(∑i=1n​(bi​−ai​)2−2t2​)(3)

对任意函数 f ∈ F f\in F f∈F， R ^ ( f ) \hat R(f) R^(f)是N个独立的随机变量 L ( Y , f ( X ) ) L(Y,f(X)) L(Y,f(X))的样本均值， R ( f ) R(f) R(f)是随机变量 L ( Y , f ( X ) ) L(Y,f(X)) L(Y,f(X))的期望值。如果损失函数取值于区间 [ 0 , 1 ] [0,1] [0,1]，即对所有i， [ a i , b i ] = [ 0 , 1 ] [a_i,b_i]=[0,1] [ai​,bi​]=[0,1]，那么由 H o e f f d i n g Hoeffding Hoeffding不等式(3)不难得知，对 ϵ > 0 \epsilon>0 ϵ>0，以下不等式成立： P ( R ( f ) − R ^ ( f ) ≥ ϵ ) ≤ e x p ( − 2 N ϵ 2 ) P(R(f)-\hat R(f)\geq \epsilon) \leq exp(-2 N\epsilon^2) P(R(f)−R^(f)≥ϵ)≤exp(−2Nϵ2) 由于 F = { f 1 , f 2 , . . . , f d } F=\{f_1,f_2,...,f_d\} F={f1​,f2​,...,fd​}是一个有限集合，故 P ( ∃ f ∈ F : R ( f ) − R ^ ( f ) ≥ ϵ ) = P ( ⋃ f ∈ F { R ( f ) − R ^ ( f ) ≥ ϵ } ) ≤ ∑ f ∈ F P ( R ( f ) − R ^ ( f ) ≥ ϵ ) ≤ d   e x p ( − 2 N ϵ 2 ) P(\exists f\in F:R(f)-\hat R(f)\geq \epsilon)=P(\bigcup_{f\in F}\{R(f)-\hat R(f) \geq \epsilon\}) \\ \leq \sum_{f\in F}P(R(f)-\hat R(f)\geq \epsilon) \\ \leq d \space exp(-2N\epsilon^2) P(∃f∈F:R(f)−R^(f)≥ϵ)=P(f∈F⋃​{R(f)−R^(f)≥ϵ})≤f∈F∑​P(R(f)−R^(f)≥ϵ)≤d exp(−2Nϵ2) 或者等价的，对任意的 f ∈ F f\in F f∈F，有 P ( R ( f ) − R ^ ( f ) < ϵ ) ≥ 1 − d   e x p ( − 2 N ϵ 2 ) P(R(f)-\hat R(f)< \epsilon) \geq 1-d \space exp(-2N\epsilon ^2) P(R(f)−R^(f)