chapter15.md 3.9 KB
第15章 规则学习
规则学习是"符号主义学习"的代表性方法，用来从训练数据中学到一组能对未见示例进行判别的规则，形如"如果A或B，并且C的条件下，D满足"这样的形式。因为这种学习方法更加贴合人类从数据中学到经验的描述，具有非常良好的可解释性，是最早开始研究机器学习的技术之一。
15.1 剪枝优化
15.1.1 式(15.2)和式(15.3)的解释
似然率统计量LRS定义为：
$$\mathrm{LRS}=2 \cdot\left(\hat{m}_{+} \log {2} \frac{\left(\frac{\hat{m}{+}}{\hat{m}{+}+\hat{m}{-}}\right)}{\left(\frac{m{+}}{m{+}+m{-}}\right)}+\hat{m}{-} \log {2} \frac{\left(\frac{\hat{m}{-}}{\hat{m}{+}+\hat{m}{-}}\right)}{\left(\frac{m{-}}{m{+}+m_{-}}\right)}\right)$$
同时，根据对数函数的定义，我们可以对式(15.3)进行化简：
$$\begin{aligned} \mathrm{F}{-} \text {Gain }&=\hat{m}{+} \times\left(\log {2} \frac{\hat{m}{+}}{\hat{m}{+}+\hat{m}{-}}-\log {2} \frac{m{+}}{m{+}+m{-}}\right)\ &=\hat{m}{+}\left(\log{2}\frac{\frac{\hat{m}{+}}{\hat{m}{+}+\hat{m}{-}}}{\frac{m{+}}{m{+}+m{-}}}\right) \end{aligned}$$
可以观察到F_Gain即为式(15.2)中LRS求和项中的第一项。这里"西瓜书"中做了详细的解释，FOIL仅考虑正例的信息量，由于关系数据中正例数旺旺远少于反例数，因此通常对正例应该赋予更多的关注。
15.2 归纳逻辑程序设计
15.2.1 式(15.6)的解释
定义析合范式的删除操作符为"$-$"，表示在$A$和$B$的析合式中删除成分$B$，得到成分$A$。
15.2.2 式(15.7)的推导
$C=A\vee B$，把$A=C_1 - {L}$和$L=C_2-{\neg L}$带入即得。
15.2.3 式(15.9)的推导
根据式(15.7) $C=\left(C_1-{L}\right) \vee\left(C_2-{\neg L}\right)$ 和析合范式的删除操作，等式两边同时删除析合项$C_2-{\neg L}$有：
$$C - (C_1 - {L}) = C_2-{\neg L}$$
再次运用析合范式删除操作符的逆定义，等式两边同时加上析合项${\neg L}$有：
$$C_2=\left(C-\left(C_1-{L}\right)\right) \vee{\neg L}$$
15.2.4 式(15.10)的解释
该式是吸收(absorption)操作的定义。注意作者在文章中所用的符号定义，用 $\frac{X}{Y}$ 表示 $X$ 蕴含 $Y$，${X}$的子句或是${Y}$的归结项，或是$Y$中某个子句的等价项。所谓吸收，是指替换部分逻辑子句（大写字母），生成一个新的逻辑文字（小写字母）用于定义这些被替换的逻辑子句。在式(15.10)中，逻辑子句$A$被逻辑文字$q$替换。
15.2.5 式(15.11)的解释
该式是辨识(identification)操作的定义。辨识操作依据已知的逻辑文字，构造新的逻辑子句和文字的关系。在式(15.11)中，已知$p \leftarrow A \wedge B$和$p \leftarrow A \wedge q$，构造的新逻辑文字为$q \leftarrow B$。
15.2.6 式(15.12)的解释
该式是内构(intra-construction)操作的定义。内构操作找到关于同一逻辑文字中的共同逻辑子句部分，并且提取其中不同的部分作为新的逻辑文字。在式(15.12)中，逻辑文字$p \leftarrow A \wedge B$和$p \leftarrow A \wedge C$的共同部分为$p \leftarrow A \wedge q$，其中新逻辑文字$q \leftarrow B \quad q \leftarrow C$。
15.2.7 式(15.13)的解释
该式是互构(inter-construction)操作的定义。互构操作找到不同逻辑文字中的共同逻辑子句部分，并定义新的逻辑文字已描述这个共同的逻辑子句。在式(15.13)中，逻辑文字$p \leftarrow A \wedge B$ 和 $q \leftarrow A \wedge C$的共同逻辑子句$A$提取出来，并用逻辑文字定义为$r \leftarrow A$。逻辑文字$p$和$q$的定义也用$r$做相应的替换得到$p \leftarrow r \wedge B$与$q \leftarrow r \wedge C$。
15.2.8 式(15.16)的推导
$\theta_1$为作者笔误，由15.9
$$\begin{aligned} C{2}&=\left(C-\left(C{1}-{L_1}\right)\right) \vee{L_2}\ \end{aligned}$$
因为 $L_2=(\neg L_1\theta_1)\theta_2^{-1}$，替换得证。