推论 3.9 生长函数的泛化界

将 定理 3.5 的泛化界限 (3.17) 与 推论 3.8 结合，即可立即得到以下以生长函数为基础的泛化界。

推论 3.9（生长函数泛化界）

• 设 $\mathcal{H}$ 是一个取值在 $\{-1,+1\}$ 的函数族。
• 则，对于任意 $\delta >0$，以至少 $1-\delta$ 的概率，
  • 对于任何 $h\in \mathcal{H}$， R\left( h\right) \leq {\widehat{R}}_{S}\left( h\right) + \sqrt{\frac{2\log {\Pi }_{\mathcal{H}}\left( m\right) }{m}} + \sqrt{\frac{\log \frac{1}{\delta }}{2m}}. \tag{3.22}

Remark

• 生长函数界限也可以直接推导出来
  • 不需要先使用 Rademacher 复杂度界限
• 最终得到的界限是： \mathbb{P}\left\lbrack {\left| {R\left( h\right) - {\widehat{R}}_{S}\left( h\right) }\right| > \epsilon }\right\rbrack \leq 4{\Pi }_{\mathcal{H}}\left( {2m}\right) \exp \left( {-\frac{m{\epsilon }^{2}}{8}}\right) , \tag{3.23}
  • 这与 (3.22) 仅在常数上有所不同。