规则学习：对样本的标记规律进行归纳总结、并进行演绎推理，得出（逻辑）规则。
以命题形式的规则表达，由“条件”得到“结论”。
从集合论的角度来看，具有蕴涵（包含）关系。
“条件”可能分解为若干“子条件”，需要它们同时成立。
通过真值表可以定义语义。

命题规则

首先，我们看以命题形式的规则表达
$$\begin{array}{r}\text{if (条件) then (结论)}\end{array}\text{\hspace{1em}(15.1)}$$

式(15.1)中由“条件”得到“结论”，从集合论的角度来看，该“条件”除了能得到该“结论”外，可能还会得到其他什么结论，故具有蕴涵（包含）关系
$$\begin{array}{r}\text{结论⊆条件}\end{array}\text{\hspace{1em}(15.2)}$$
用逻辑学中的符号，则为
$$\begin{array}{r}\text{“结论”←“条件”}\end{array}\text{\hspace{1em}(15.3)}$$

对于二分类问题，“结论”通常取“正例”（或“正例集”），用$⨁$表示，而“条件”可能分解为若干“子条件”，需要它们同时成立，这时，上述两式分别为
$$\begin{array}{r}\oplus \subseteq {\mathbf{f}}_1\cap {\mathbf{f}}_2\cap \cdots \cap {\mathbf{f}}_L\end{array}\text{\hspace{1em}(15.4)}$$
$$\begin{array}{r}\oplus \leftarrow {\mathbf{f}}_1\wedge {\mathbf{f}}_2\wedge \cdots \wedge {\mathbf{f}}_L\end{array}\text{\hspace{1em}(15.5)}$$
其中，${\mathbf{f}}_1$可以是布尔表达式，例如，关于西瓜属性的表达对应是这样的：(色泽=乌黑)、$\neg$(根蒂=硬挺)。

有五个连接符号：$\neg$（否定），$\wedge$（合取），$\vee$（析取），$\leftarrow$（蕴涵），$\leftrightarrow$（等价）。 而“逻辑连词”与布尔代数及集合论中的符号具有对应关系（如，上述式(15.5)与式(15.4)对应）。

式(15.5)中${\mathbf{f}}_1\wedge {\mathbf{f}}_2\wedge \cdots \wedge {\mathbf{f}}_L$表示条件同时满足，称为合取式（合取（$\bigwedge$）是指同时满足，类似于集合的“交”；析取（$\bigvee$）是指至少满足其一，类似于集合的“并”），而${\mathbf{f}}_1\vee {\mathbf{f}}_2\vee \cdots \vee {\mathbf{f}}_L$表示至少满足一个条件，称为析取式。

通过真值表可以定义其语义，如，表15.1 中，每行的第2、3、4列为$\alpha ,\beta ,\gamma$的一个真值指派（因变量赋值），第5列对应于$\alpha \wedge \beta$的语义（变量的定义），整个表则是完整的因变量真值指派及表达式值定义。

式(15.5)是单一合取式，若使用“析合范式”将有更强的表达能力，我们以【西瓜书表1.1】数据为例，讨论“析合范式”表达的假设空间。

设数据集有3个属性（不妨抽象成$a$,$b$,$c$）每个属性3个值（分别以下标1，2，3表示，并有通配符“$\ast$”），【西瓜书图1.2】已得到了“版本空间”，根据这里的记号，则“版本空间”为
$$\begin{array}{c}\{(a_{\ast }\wedge b_1\wedge c_{\ast }),(a_{\ast }\wedge b_{\ast }\wedge c_1),(a_{\ast }\wedge b_1\wedge c_1)\}\end{array}\text{\hspace{1em}(15.6)}$$
“版本空间”中的任一“版本”都是任务的一个解，即都是训练出的预测器，可用于进行预测。

1）在某种偏好下，保留符合训练样本的节点，如：删除与正例不一致的节点（当然，这是默认的偏好，也可以用“满足负例”作为偏好，当以既“满足正例”又“满足负例”作为偏好时，必须加上二者冲突时的偏好选择）；

2）再去掉两种极端情况（删除对预测不起实质作用的假设），即删除未泛化的叶（如，$(a_1,b_1,c_1)$）和删除泛化过度的根（如，$(a_{\ast },b_{\ast },c_{\ast })$）。

式(15.6)中每一个就只含一个合取式（的析合范式）。

二个合取式的析合范式为从式(15.6)中任取两个合取式再进行析取，再考虑到吸收律（如$(a_{\ast }\wedge b_{\ast }\wedge c_1)\vee (a_{\ast }\wedge b_1\wedge c_1)=(a_{\ast }\wedge b_{\ast }\wedge c_1)$，其中$b_{\ast }$吸收了$b_1$），故只有
$$\begin{array}{c}(a_{\ast }\wedge b_1\wedge c_{\ast })\vee (a_{\ast }\wedge b_{\ast }\wedge c_1)\end{array}\text{\hspace{1em}(15.7)}$$

又将式(15.6)中三个合取式进行析取，由吸收律仍得到式(15.7)，故没有含三个（及以上）合取式的析合范式假设。

本文为原创，您可以：

• 点赞（支持博主）
• 收藏（待以后看）
• 转发（他考研或学习，正需要）
• 评论（或讨论）
• 引用（支持原创）
• 不侵权

上一篇：14.12 趣谈话题模型（话题“打词机”，盘式记法）
下一篇：15.2 形式推理（哥德尔怎么说？）