2 PAC学习框架（page 21 22）

4年前更新

2470

2.3 有限假设集的保证——不一致情形

在最一般的情况下，H 中可能没有与标记训练样本一致的假设。这实际上是实践中的典型案例，其中学习问题可能有些困难，或者概念类比学习算法使用的假设集更复杂。然而，在训练样本上具有少量错误的不一致假设可能是有用的，并且正如我们将看到的，可以从某些假设下的有利保证中受益。本节为这种不一致的情况和有限的假设集提供了学习保证。
为了在这种更一般的环境中获得学习保证，我们将使用 Hoeffding 不等式（定理 D.1）或以下推论，它涉及单个假设的泛化误差和经验误差。

推论2.1

固定 $\epsilon > 0$ 并让 $S$ 表示一个 i.i.d.大小为 $m$ 的样本。然后，对于任何假设 $h：X → \{0,1\}$ ，以下不等式成立：

\begin{aligned} \underset {S D^m}{Pr}[\widehat R(h)-R(h)\ge\epsilon]&\le exp(-2m\epsilon ^2)(2.14)\\ \underset {S D^m}{Pr}[\widehat R(h)-R(h)\le -\epsilon]&\le exp(-2m\epsilon ^2).(2.15)\\ \end{aligned}

© 版权声明

文章版权归作者所有，未经允许请勿转载。

THE END

喜欢就支持一下吧

相关推荐