推论 3.19 VC 维度泛化界

推论 3.19 VC 维度泛化界

设 $\mathcal{H}$ 是取值于 $\{-1,+1\}$ 的函数族，VC 维度为 $d$。 那么，对于任意 $\delta >0$，以至少 $1-\delta$ 的概率，以下结果对所有 $h\in \mathcal{H}$ 成立： R\left( h\right) \leq {\widehat{R}}_{S}\left( h\right) + \sqrt{\frac{{2d}\log \frac{em}{d}}{m}} + \sqrt{\frac{\log \frac{1}{\delta }}{2m}}. \tag{3.29}

因此，这个泛化界的形式是

R\left( h\right) \leq {\widehat{R}}_{S}\left( h\right) + O\left( \sqrt{\frac{\log \left( {m/d}\right) }{\left( m/d\right) }}\right) , \tag{3.30}

• 这强调了 $m/d$ 比例在泛化中的重要性。
• 该定理提供了另一个 奥卡姆剃刀原则 (Occam’s Razor principle) 的例子，其中简洁性通过较小的 VC 维度来衡量。

Remark

VC 维度界可以直接推导，而无需使用中间的 Rademacher 复杂度界，如 (3.23) 所示： 将 Sauer 引理与 (3.23) 结合，得到以下高概率界 $R\left(h\right)\le {\hat{R}}_S\left(h\right)+\sqrt{\frac{8d\log \frac{2em}{d}+8\log \frac{4}{\delta }}{m}},$ 其形式与 (3.30) 的一般形式一致。 对这些界限来说，对数因子仅起次要作用。 实际上，可以通过更细致的分析来消除该因子。