4.2 经验风险最小化(ERM)

一个可以界定估计误差的标准算法是 经验风险最小化(ERM)。 ERM旨在最小化训练样本上的误差:

h_{S}^{ERM} = h \in H argmin R_{S} (h) (4.2)

命题 4.1

对于任何样本 $S$ ，ERM 返回的假设以下不等式成立:
$\leq P [R (h_{S}^{ERM}) - h \in H in f R (h) > ϵ] P [h \in H sup R (h) - R_{S} (h) > \frac{ϵ}{2}] (4.3)$

\begin{proof} 根据 $h \in H in f R (h)$ 的定义，对于任何 $ϵ > 0$ ，存在 $h_{ϵ}$ 使得 $R (h_{ϵ}) \leq h \in H in f R (h) + ϵ$ 因此，使用 $R_{S} (h_{S}^{ERM}) \leq R_{S} (h_{ϵ})$ (因为 $h_{S}^{ERM}$ 的定义)

根据算法的定义，我们可以写出

R (h_{S}^{ERM}) - h \in H in f R (h) = R (h_{S}^{ERM}) - R (h_{ϵ}) + R (h_{ϵ}) - h \in H in f R (h) \leq R (h_{S}^{ERM}) - R (h_{ϵ}) + ϵ = R (h_{S}^{ERM}) - R_{S} (h_{S}^{ERM}) + R_{S} (h_{S}^{ERM}) - R (h_{ϵ}) + ϵ \leq R (h_{S}^{ERM}) - R_{S} (h_{S}^{ERM}) + R_{S} (h_{ϵ}) - R (h_{ϵ}) + ϵ \leq 2 h \in H sup R (h) - R_{S} (h) + ϵ .

由于不等式对所有 $ϵ > 0$ 都成立，因此它暗示了以下内容:

R (h_{S}^{ERM}) - h \in H in f R (h) \leq 2 h \in H sup R (h) - R_{S} (h)

这就完成了证明。 \end{proof}

ERM 的右侧界定
- 可以通过上一章中介绍的一般化边界来用 Rademacher 复杂度、增长函数或 $H$ 的 VC 维来界定。
- 特别是，可以被 $2 e^{- 2 m [ϵ - ℜ_{m} (H)]^{2}}$ 所界定。
ERM 的局限性
- 当 $H$ 具有有利的 Rademacher 复杂度时 (例如有限的 VC 维)，对于足够大的样本，以高概率保证估计误差较小。
- 然而，ERM 的性能通常非常差。
  - 因为算法忽视了假设集 $H$ 的复杂性：在实践中，
    - 要么 $H$ 不够复杂，这种情况下近似误差可能非常大，
    - 要么 $H$ 非常丰富，这种情况下对估计误差的界定变得非常宽松。
- 还有，确定 ERM 解在计算上是不可行的：
  - 例如，寻找在训练样本上误差最小的线性假设，作为空间维度的函数，是 NP 难的。

Youliang Zhong

4.2 经验风险最小化(ERM)

Graph View

Backlinks