是独立随机变量X
1
,X
2
,...,X
n
之和,X
i
∊[a
i
,b
i
],则对任意t>0,以下不等式成立:
对任意函数f∊
,
(f)是N个独立的随机变量L(Y,f(X))的样本均值,R(f)是随机变量L(Y,f(X))的期望值.如果损失函数取值于区间[0,1],即对所有i,[a
i
,b
i
]=[0,1],那么由Hoeffding不等式(1.28)不难得知,对
>0,以下不等式成立:
由于
={f
1
,f
2
,...,f
d
}是一个有限集合,故
或者等价的,对任意f∊
,有
即至少以概率1-
有R(f)<
(f)+
,其中
由式(1.29)得到,即为式(1.26).
从泛化误差上界可知,
其中,
(