2 PAC学习框架 （page 20 21）

示例 2.4 k项DNF公式

析取范式（DNF）公式是几个项的析取的公式，每个项都是布尔文字的合取。$k$项DNF是由$k$项的析取定义的DNF公式，每个项最多由$n$个布尔文字组成。因此，对于$k＝2$和$n＝3$，k项DNF的示例为$(x_1∧ \overline x_2∧ x_3)∨ (\overline x_1∧ x_3)$。
$k$项DNF公式的$C$类是PAC可学习的吗？类的基数是$3^{nk}$的基数，因为每个项是至多$n$个变量的合取，并且有$3^n$个这样的合取，如前面所见。假设集$H$必须包含$C$才能实现一致性，因此$| H |≥ 3^{nk}$。定理2.1给出了以下样本复杂性界：