【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.序贯覆盖
规则学习的目标是产生一个能覆盖尽可能多的样例的规则集。最直接的做法是“序贯覆盖”（sequential covering），即逐条归纳：在训练集上每学到一条规则，就将该规则覆盖的训练样例去除，然后以剩下的训练样例组成训练集重复上述过程。由于每次只处理一部分数据，因此也被称为“分治”（separate-and-conquer）策略。
我们以命题规则学习为例来考察序贯覆盖法。命题规则的规则体是对样例属性值进行评估的布尔函数，如“色泽=青绿”“含糖率$\leqslant 0.2$”等，规则头是样例类别。序贯覆盖法的关键是如何从训练集学出单条规则。显然，对规则学习目标$\oplus$，产生一条规则就是寻找最优的一组逻辑文字来构成规则体，这是一个搜索问题。形式化地说，给定正例集合与反例集合，学习任务是基于候选文字集合$\mathcal{F}=\{ \mathbf{f}_k \}$来生成最优规则$\mathbf{r}$。在命题规则学习中，候选文字是形如“$R(属性_i,属性值_{i,j})$”的布尔表达式，其中$属性_i$表示样例第$i$个属性，$属性值_{i,j}$表示$属性_i$的第$j$个候选值，$R(x,y)$则是判断$x$、$y$是否满足关系$R$的二元布尔函数。
最简单的做法是从空规则“$\oplus \leftarrow$”开始，将正例类别作为规则头，再逐个遍历训练集中的每个属性及取值，尝试将其作为逻辑文字增加到规则体中，若能使当前规则体仅覆盖正例，则由此产生一条规则，然后去除已被覆盖的正例并基于剩余样本尝试生成下一条规则。
以西瓜数据集2.0训练集为例，首先根据第1个样例生成文字“好瓜”和“色泽=青绿”加入规则，得到：
\[好瓜 \leftarrow (色泽=青绿)\]这条规则覆盖样例1，6，10和17，其中有两个正例和两个反例，不符合“当前规则仅覆盖正例”的条件。于是，我们尝试将该命题替换为基于属性“色泽”形成的其他原子命题，例如“色泽=乌黑”；然而在这个数据集上，这样的操作不能产生符合条件的规则。于是我们回到“色泽=青绿”，尝试增加一个基于其他属性的原子命题，例如“根蒂=蜷缩”：
\[好瓜\leftarrow (色泽=青绿) \land (根蒂=蜷缩)\]为简便起见，后续部分不考虑否定形式的逻辑文字，即仅以$\mathbf{f}$为候选文字，不考虑$\neg \mathbf{f}$。
该规则仍覆盖了反例17。于是我们将第二个命题替换为基于该属性形成的其他原子命题，例如“根蒂=稍蜷”：
\[好瓜 \leftarrow (色泽=青绿) \land (根蒂=稍蜷)\]这条规则不覆盖任何反例，虽然它仅覆盖一个正例，但已满足“当前规则仅覆盖正例”的条件。因此我们保留这条规则并去除它覆盖的样例6，然后将剩下的9个样例用作训练集。如此继续，我们将得到：
- 规则1：$好瓜 \leftarrow (色泽=青绿) \land (根蒂=稍蜷)$
- 规则2：$好瓜 \leftarrow (色泽=青绿) \land (敲声=浊响)$
- 规则3：$好瓜 \leftarrow (色泽=乌黑) \land (根蒂=蜷缩)$
- 规则4：$好瓜 \leftarrow (色泽=乌黑) \land (纹理=稍糊)$
这个规则集覆盖了所有正例，未覆盖任何反例，这就是序贯覆盖法学得的结果。
上面这种基于穷尽搜索的做法在属性和候选值较多时会由于组合爆炸而不可行。现实任务中一般有两种策略来产生规则：第一种是“自顶向下”（top-down），即从比较一般的规则开始（例如不含任何属性的空规则，它覆盖所有样例，就是一条比较一般的规则），逐渐添加新文字以缩小规则覆盖范围，直到满足预定条件为止；亦称为“生成-测试”（generate-then-test）法，是规则逐渐“特化”（specialization）的过程。第二种策略是“自底向上”（bottom-up），即从比较特殊的规则开始（例如直接以某样例的属性取值形成规则，该规则仅覆盖此样例，就是一条比较特殊的规则），逐渐删除文字以扩大规则覆盖范围，直到满足条件为止；亦称为“数据驱动”（data-driven）法，是规则逐渐“泛化”（generalization）的过程。第一种策略是覆盖范围从大往小搜索规则，第二种策略则相反；前者通常更容易产生泛化性能较好的规则，而后者则更适合于训练样本较少的情形，此外，前者对噪声的鲁棒性比后者要强得多。因此，在命题规则学习中通常使用第一种策略，而第二种策略在一阶规则学习这类假设空间非常复杂的任务上使用较多。
下面以西瓜数据集2.0训练集为例来展示自顶向下的规则生成方法。首先从空规则“好瓜$\leftarrow$”开始，逐一将“属性=取值”作为原子命题加入空规则进行考察。假定基于训练集准确率来评估规则的优劣，$n/m$表示加入某命题后新规则在训练集上的准确率，其中$m$为覆盖的样例总数，$n$为覆盖的正例数。如图15.1所示，经过第一轮评估，“色泽=乌黑”和“脐部=凹陷”都达到了最高准确率$3/4$。
将属性次序最靠前的逻辑文字“色泽=乌黑”加入空规则，得到：
\[好瓜 \leftarrow (色泽=乌黑)\]然后，对上面这条规则覆盖的样例，通过第二轮评估可发现，将图15.1中的五个逻辑文字加入规则后都能达到100%准确率，我们将覆盖样例最多、且属性次序最靠前的逻辑文字“根蒂=蜷缩”加入规则，于是得到结果：
\[好瓜 \leftarrow (色泽=乌黑) \land (根蒂=蜷缩)\]规则生成过程中涉及一个评估规则优劣的标准，在上面的例子中使用的标准是：先考虑规则准确率，准确率相同时考虑覆盖样例数，再相同时考虑属性次序。现实应用中可根据具体任务情况设计适当的标准。
此外，在上面的例子中每次仅考虑一个“最优”文字，这通常过于贪心，易陷入局部最优。为缓解这个问题，可采用一些相对温和的做法，例如采用“集束搜索”（beam search），即每轮保留最优的$b$个逻辑文字，在下一轮均用于构建候选集，再把候选集中最优的$b$个留待再下一轮使用。图15.1中若采用$b=2$的集束搜索，则第一轮将保留准确率为$3/4$的两个逻辑文字，在第二轮评估后就能获得下面这条规则，其准确率仍为100%，但是覆盖了3个正例：
\[好瓜 \leftarrow (脐部=凹陷) \land (根蒂=蜷缩)\]由于序贯覆盖法简单有效，几乎所有规则学习算法都以它为基本框架。它能方便地推广到多分类问题上，只需将每类分别处理即可：当学习关于第$c$类的规则时，将所有属于类别$c$的样本作为正例，其他类别的样本作为反例。
