示例 2.7（通用概念类）

考虑由所有具有 $n$ 个分量的布尔向量组成的集合 $X=\{0,1{\}}^n$，并让 ${\mathcal{U}}_n$ 成为由 $x$ 的所有子集形成的概念类。这个概念类是 PAC 可学习的吗？为了确保一个一致的假设，假设类必须包含概念类，因此 $\left|\mathcal{H}\right|\ge \left|{\mathcal{U}}_n\right|=2^{\left(2^n\right)}$。定理 2.5 给出了以下样本复杂性界限：

$$m\ge \frac{1}{ϵ}\left(\left(\log 2\right)2^n+\log \frac{1}{\delta }\right)\text{\hspace{1em}(2.11)}$$

在这里，所需的训练样本数量在 $n$ 上是指数级的，这是在 $x$ 中表示一个点的成本。因此，定理并不保证 PAC 学习。实际上，不难证明这个通用概念类不是 PAC 可学习的。