示例 2.8 ( k-项析取范式)

析取范式（DNF）是一种公式，写成多个项的析取形式，每个项是一个布尔文字的合取。一个 $k$ -项 DNF 是由 $k$ 项的析取定义的 DNF 公式，每个项至多是一个布尔文字的合取。因此，对于 $k=2$ 和 $n=3$ ，一个 $k$ -项 DNF 的例子是 $\left(x_1\wedge {\bar{x}}_2\wedge x_3\right)\vee \left({\bar{x}}_1\wedge x_3\right)$ 。

$\mathcal{C}$ 类的 $k$ -项 DNF 公式是否可PAC学习？因为这个类的势是 $3^{nk}$ ，因为每个项至多是一个变量的合取，并且像之前看到的那样有 $3^n$ 这样的合取。假设集 $\mathcal{H}$ 必须包含 $\mathcal{C}$ 以保证一致性是可能的，因此 $\left|\mathcal{H}\right|\ge 3^{nk}$ 。定理 2.5 给出了以下样本复杂性界限：

$$m\ge \frac{1}{ϵ}\left(\left(\log 3\right)nk+\log \frac{1}{\delta }\right)$$

$\left(2.12\right)$

这是多项式的。然而，可以通过从图 3-着色问题归约来证明，即使对于 $k=3$ ，学习 $k$ -项 DNF 的问题也是不可有效 PAC 学习的，除非 RP，即那些接受随机多项式时间决策解的问题的复杂性类，与 $\mathrm{NP}\left(\mathrm{RP}=\mathrm{NP}\right)$ 相同，这通常被认为是不可能的。因此，尽管学习 $k$ -项 DNF 公式所需的样本大小只是多项式的，但如果 $\mathrm{RP}\ne \mathrm{NP}$ ，则不可能有效地 PAC 学习这个类。