2 PAC学习框架 （page 17 18）

2.2 有限假设集的保证 —— 一致情况

在我们检查的轴对齐矩形的例子中，算法返回的假设 $h_S$ 总是一致的，即它在训练样本 $S$ 上不承认错误。 在本节中，我们提出了一个通用的样本复杂度界限，或等效地，一个泛化界，对于一致的假设，在基数$|H|$的情况下的假设集是有限的。由于我们考虑一致的假设，我们将假设目标概念 $c$ 在 $H$ 中。

定理2.1学习边界——有限H，一致情况

设 $H$ 是从 $X$ 到 $Y$ 映射的有限函数集。设 $A$ 是一个算法，对于任何目标概念 $c ∈ H$ 和 i.i.d.样本 $S$ 返回一个一致的假设 $h_S ：\widehat R(h_S) = 0$。那么，对于任何 $\epsilon,δ > 0$，不等式 $\underset {S∼D_m}{Pr}[R(h_S) ≤ \epsilon] ≥ 1−δ$ 成立，如果