示例 2.9 ( k-CNF 公式)

合取范式 (CNF) 公式是若干个析取式的合取。一个 $k$ -CNF 公式是如下形式的表达式 $T_{1} \land \dots \land T_{j}$ ，长度任意 $j \in N$ ，且每个项 $T_{i}$ 是至多 $k$ 个布尔属性的析取。

学习 $k$ -CNF 公式的问题可以归结为学习布尔文字合取的问题，如前所述，这是一个 PAC 可学习概念类。这可以通过引入 $(2 n)^{k}$ 个新变量 $Y_{u_{1}, \dots, u_{k}}$ 来实现，使用以下双射：

(u_{1}, \dots, u_{k}) \to Y_{u_{1}, \dots, u_{k}} (2.13)

其中 $u_{1}, \dots, u_{k}$ 是原始变量 $x_{1}, \dots, x_{n}$ 上的布尔文字。 $Y_{u_{1}, \dots, u_{k}}$ 的值由 $Y_{u_{1}, \dots, u_{k}} = u_{1} \lor \dots \lor u_{k}$ 确定。使用这个映射，原始训练样本可以转换为以新变量定义的样本，且任何关于原始变量的 $k$ -CNF 公式都可以写为关于变量 $Y_{u_{1}, \dots, u_{k}}$ 的合取。这种归结到布尔文字合取的 PAC 学习可能会影响原始样本的分布，但在 PAC 框架下，并没有对分布做出假设。因此，使用这种转换，布尔文字合取的 PAC 可学习性意味着 $k$ -CNF 公式的 PAC 可学习性。

然而，这是一个令人惊讶的结果，因为任何 $k$ -项 DNF 公式都可以写为 $k$ -CNF 公式。实际上，使用结合性，一个 $k$ -项 DNF $T_{1} \lor \dots \lor T_{k}$ 以 $T_{i} = u_{i, 1} \land \dots \land u_{i, n_{i}}$ 为 $i \in [k]$ 可以重写为 $k$ -CNF 公式通过

i = 1 ⋁ k u_{i, 1} \land \dots \land u_{i, n_{i}} = j_{1} \in [n_{1}], \dots, j_{k} \in [n_{k}] ⋀ u_{1, j_{1}} \lor \dots \lor u_{k, j_{k}}

为了具体说明这种重写，观察例如

(u_{1} \land u_{2} \land u_{3}) \lor (v_{1} \land v_{2} \land v_{3}) = i, j = 1 ⋀ 3 (u_{i} \lor v_{j}) .

但是，正如我们之前所见， $k$ -项的DNF公式在 $RP \neq = NP$ 的情况下并不是有效可PAC学习的！这种明显的矛盾可以如何解释呢？问题在于，将我们学习到的 $k$ -CNF公式（其等价于 $k$ -项的DNF）转换为 $k$ -项的DNF公式在一般情况下是不可解的，如果 $RP \neq = NP$ 。

这个例子揭示了PAC学习的几个关键方面，包括概念的表征成本和假设集的选择。对于一个固定的概念类，学习可能是不可解的，也可能不是，这取决于表征的选择。

Youliang Zhong

Backlinks

Graph View

示例 2.9 ( k-CNF 公式)