令
Z
i
=
l
(
f
(
x
i
)
,
y
i
)
Z_i = l(f(x_i),y_i)
Zi=l(f(xi),yi)，其中
(
x
i
,
y
i
)
∈
S
t
e
s
t
(x_i,y_i) \in S_{test}
(xi,yi)∈Stest，
i
=
1
,
2
,
.
.
.
,
m
,
m
=
∣
S
t
e
s
t
∣
i=1,2,...,m,m=|S_{test}|
i=1,2,...,m,m=∣Stest∣
由于
(
x
i
,
y
i
)
∼
D
(x_i,y_i) \sim \mathcal{D}
(xi,yi)∼D，
Z
i
Z_i
Zi是独立同分布的随机变量，且由假设，
Z
i
∈
[
a
,
b
]
Z_i \in [a,b]
Zi∈[a,b]。于是：
E [ Z i ] = E ( x , y ) ∼ D [ l ( f ( x ) , y ) ] = L D ( f ) \mathbb{E}[Z_i]=\mathbb{E}_{(x,y) \sim \mathcal{D}}[l(f(x),y)]=L_{\mathcal{D}}(f) E[Zi]=E(x,y)∼D[l(f(x),y)]=LD(f)
经验分险为：
L S t e s t ( f ) = 1 m ∑ m i = 1 Z i L_{S_{test}}(f)=\frac{1}{m}\underset{i=1}{\overset{m}{\sum}}Z_i LStest(f)=m1i=1∑mZi
引入霍夫丁不等式，它表面对于 m m m个独立随机变量 Z 1 , . . . , Z m Z_1, ..., Z_m Z1,...,Zm，每个 Z i ∈ [ a , b ] Z_i \in [a,b] Zi∈[a,b]，有：
Pr [ ∣ 1 m ∑ i = 1 m Z i − E [ Z i ] ∣ ≥ ϵ ] ≤ 2 exp ( − 2 m ϵ 2 ( b − a ) 2 ) \Pr\left[ \left| \frac{1}{m} \sum_{i=1}^m Z_i - \mathbb{E}[Z_i] \right| \geq \epsilon \right] \leq 2 \exp\left( -\frac{2m\epsilon^2}{(b - a)^2} \right) Pr[ m1∑i=1mZi−E[Zi] ≥ϵ]≤2exp(−(b−a)22mϵ2)
代入后则有：
Pr [ ∣ L S test ( f ) − L D ( f ) ∣ ≥ ϵ ] ≤ 2 exp ( − 2 m ϵ 2 ( b − a ) 2 ) \Pr\left[ \left| L_{S_{\text{test}}}(f) - L_{\mathcal{D}}(f) \right| \geq \epsilon \right] \leq 2 \exp\left( -\frac{2m\epsilon^2}{(b - a)^2} \right) Pr[∣LStest(f)−LD(f)∣≥ϵ]≤2exp(−(b−a)22mϵ2)
确定一个特定的 ϵ \epsilon ϵ，令：
2 e x p ( − 2 m ϵ 2 ( b − a ) 2 ) = δ 2 2exp(-\frac{2m\epsilon^2}{(b-a)^2})=\frac{\delta}{2} 2exp(−(b−a)22mϵ2)=2δ
ϵ = ( b − a ) 2 l n ( 2 / δ ) 2 m = ( b − a ) 2 l n ( 2 / δ ) 2 ∣ S t e s t ∣ \epsilon=\sqrt{\frac{(b-a)^2ln(2/\delta)}{2m}}=\sqrt{\frac{(b-a)^2ln(2/\delta)}{2|S_{test}|}} ϵ=2m(b−a)2ln(2/δ)=2∣Stest∣(b−a)2ln(2/δ)
最终得到：
Pr [ ∣ L D ( f ) − L S test ( f ) ∣ ≥ ( b − a ) 2 ln ( 2 / δ ) 2 ∣ S test ∣ ] ≤ δ \Pr\left[ \left| L_{\mathcal{D}}(f) - L_{S_{\text{test}}}(f) \right| \geq \sqrt{\frac{(b - a)^2 \ln(2/\delta)}{2 |S_{\text{test}}|}} \right] \leq \delta Pr[∣LD(f)−LStest(f)∣≥2∣Stest∣(b−a)2ln(2/δ)]≤δ