示例 2.6（布尔文字的合取）

考虑

• 学习概念类 ${\mathcal{C}}_n$ ，即最多 $n$ 个布尔文字的合取 $x_1,\dots ,x_n$ 。
• 布尔文字可以是变量 $x_i$, $i\in \left[n\right]$ ，或者是它的否定 ${\bar{x}}_i$ 。
• 对于 $n=4$ ，一个例子是合取： $x_1\wedge {\bar{x}}_2\wedge x_4$，其中 ${\bar{x}}_2$ 表示布尔文字 $x_2$.
  • $\left(1,0,0,1\right)$ : 正
  • $\left(1,0,0,0\right)$ : 负
• 一个正例 $\left(1,0,1,0\right)$ 意味着目标概念
  • 不能包含字面量 ${\bar{x}}_1$ 和 ${\bar{x}}_3$ ，
  • 也不能包含字面量 $x_2$ 和 $x_4$ 。
• 相比之下，负例的信息量不那么大，因为不知道它的 $n$ 位中哪些是错误的。

---

因此，一个寻找一致假设的简单算法基于正例，并包括以下步骤： 对于每个正例 $\left(b_1,\dots ,b_n\right)$ 和 $i\in \left[n\right]$ ，

• 如果 $b_i=1$ ，那么 ${\bar{x}}_i$ 被排除在概念类中的可能字面量之外，
• 如果 $b_i=0$ ，那么 $x_i$ 被排除。 因此，所有未被排除的字面量的合取就是一个与目标一致假设。

^fig-2-4 展示了一个训练样本的示例以及对于情况 $n=6$ 的一致假设。

---

图2.4

0	1	?	?	1	1
0	1	1	0	1	1	+
0	1	1	1	1	1	+
0	0	1	1	0	1	-
0	1	1	1	1	1	+
1	0	0	1	1	0	-
0	1	0	0	1	1	+

• 第一行在 $i\in \left[6\right]$ 列中包含 0（分别对应 1），如果所有正示例中的 $i$ 项为 0（分别对应 1）。
• 如果某些正示例的 $i$ 项中同时出现 0 和 1，则它包含 “?”。
• 其他六行代表六个训练示例及其标签，+ 或 -，在最后一列中指示。

因此，对于这个训练样本，文中描述的一致性算法返回的假设是 ${\bar{x}}_1\wedge x_2\wedge x_5\wedge x_6$。

---

• 我们有 $\left|\mathcal{H}\right|=\left|{\mathcal{C}}_n\right|=3^n$，
  • 因为每个字面量可以以肯定、否定或不包含的方式被包括。
• 将这个结果代入 一致假设的样本复杂度界限 (2.8)， 得到对于任何 $ϵ>0$ 和 $\delta >0$ 的以下样本复杂度界限：

m \geq \frac{1}{\epsilon }\left( {n \left( {\log 3}\right) + \log \frac{1}{\delta }}\right) \tag{2.10}$$ --- - 因此，至多 $n$ 个布尔字面量的合取类是PAC可学习的。 - 注意计算复杂度也是多项式的，因为每个示例的训练成本在 $O\left( n\right)$ 内。 - 对于 $\delta = {0.02}$, $\epsilon = {0.1}$ 和 $n = {10}$ ，界限变为 $m \geq {149}$。 - 因此，对于一个至少包含 149 个示例的标记样本, 该界限保证 ${90}\%$ 的准确度，置信度至少为 ${98}\%$。