解析周志华《机器学习》之规则学习

作者: LiBiscuit | 来源:发表于2019-11-15 20:34 被阅读0次

今天给自己加班量产两篇坚持输出yeap!
这是写西瓜书系列的最后一章啦！
————————

规则学习

基本概念：机器学习中的规则通常指语义明确、能描述数据分布所隐含的客观规律或领域概念、可写成“若…，则…”形式的逻辑规则。
规则学习：从训练数据中学习出一组能用于对未见示例进行判别的规则。
规则的基本表达形式如下图：

举个例子：
采用规则学习的优势：
（1）规则学习具有更好的可解释性，能使用户更直观地对判别过程有所了解；
（2）规则学习能更自然地在学习过程中引入领域知识；
（3）逻辑规则的抽象描述能力在处理一些高度复杂的AI任务时具有显著的优势。
冲突与冲突消解：

规则集合中的每条规则都可看作一个子模型，规则集合是这些子模型的一个集成。当同一个示例被判别结果不同的多条规则覆盖时，称“冲突”.
消解的方法如下：

命题规则VS一阶规则
从形式语言系统的角度看，命题规则是一阶规则的特例，一阶规则的学习要比命题规则复杂。

序贯覆盖

基本概念：序贯覆盖”，即逐条归纳，在训练集上每学到一条规则，就将该规则覆盖的训练样例去除，然后以剩下的训练样例组成训练集重复上述过程，由于每次只处理一部分数据，也被称为“分治”策略。
关键：如何从训练集学出单条规则。
对规则学习目标⊕，产生一条规则就是寻找最优的一组逻辑文字来构成规则体，这是一个搜索问题。
简单的做法是从空规则“⊕←”开始，将正例类别作为规则头，再逐个遍历训练集中的每个属性及取值，尝试将其作为逻辑文字增加到规则体中，若能使当前规则体仅覆盖正例,则由此产生一条规则，然后去除已被覆盖的正例并基于剩余样本尝试生成下一条规则。
那么问题来了，这种基于穷尽搜索的做法在属性和候选值较多时会由于组合爆炸而不可行。

因而有了自顶向下和自底向上两种搜索方法。
1.自顶向下，从比较一般的规则开始，逐渐增加新文字以缩小规则覆盖范围，直到满足预定条件，也称生成-测试法，是规则逐渐特化的过程，从一般到特殊

如上图所示，自顶向下，覆盖范围从大往小搜索规则，更容易产生泛化性能较好的规则。
2.自底向上，从比较特殊的规则开始，逐渐删除文字以扩大覆盖范围，直到满足条件；也称数据驱动法，是规则逐渐泛化的过程，从特殊到一般的过程。
如上图所示，自底向上，覆盖范围从小往大搜索规则，适合于训练样本较少的情形。
这两种方法，前者对噪声的鲁棒性比后者要强得多。因此，在命题规则学习中通常使用第一种策略,而第二种策略在一阶规则学习这类假设空间非常复杂的任务上实用得多。
下面以西瓜集为例（采用自顶向下的方式）

从空规则“好瓜”开始，逐一将“属性=取值”作为原子命题加入空规则。n/m 表示加入某命题后新规则在训练集的准确率（m覆盖的样例总数，n为覆盖的正例数）从上图可以看到，第一轮候选集中，色泽=乌黑、脐部=凹陷都是3/4，于是选择属性次序靠前的加入空规则，也就是好瓜←（色泽=乌黑）加入规则。然后对上面这条规则覆盖的样例通过第二轮评估，都能达到100%，我们将覆盖样例最多，且属性次序最靠前的根蒂=蜷缩加入规则，最终得到结果。
注意：（因为自顶向下中，若每次仅考虑一个最优文字，过于贪心，易陷入局部最优，通常采取集束搜索，即每轮保留最优的b个逻辑文字，在下一轮均用于构建候选集，再把候选集中最优的b个留待下一轮使用。）

剪枝优化

规则生成本质上是一个贪心搜索过程，需要一定的机制来缓解过拟合的风险，最常见的做法是剪枝
剪枝可发生在规则生长过程中，即预剪枝；发生在规则产生后，即后剪枝。
通常是基于某种性能度量指标来评估增/删逻辑文字前后的规则性能，或增/删规则前后的规则集性能，从而判断是否要进行剪枝。

预剪枝

预剪枝可以借助统计显著性检验
CN2算法
CN2算法在预剪枝时，假设用规则集进行预测必须显著优于直接基于训练样例集后验概率分布进行预测。CN2使用了似然率统计量(LRS).
信息量指标，衡量了规则(集)覆盖样例的分布与训练集经验分布的差别：
LRS越大，说明采用规则(集)进行预测与直接使用训练集正、反例比率进行猜测的差别越大；
LRS越小，说明规则(集)的效果越可能仅是偶然现象。
在数据量比较大的任务中，通常设置为在LRS很大(例如0.99)时CN2算法才停止规则(集)生长
后剪枝

减错剪枝(简称REP)：
将样例集划分为训练集和验证集，从训练集上学得规则集R后进行多轮剪枝，在每一轮穷举所有可能的剪枝操作，包括删除规则中某个文字、删除规则结尾文字、删除规则尾部多个文字、删除整条规则等，然后用验证集对剪枝产生的所有候选规则集进行评估保留最好的那个规则集进行下一轮剪枝，直到无法通过剪枝提高验证集上的性能为止。
REP：复杂度是O(m^4)
IREP ：复杂度O(mlog2m)
在生成每条规则前，先将当前样例集划分为训练集和验证集，在训练集上生成一条规则r，立即在验证集上对其进行REP剪枝，得到规则r，将r覆盖的样例去除，在更新后的样例集上重复上述过程。
REP针对规则集进行剪枝，而IREP仅对单条规则进行剪枝，后者比前者更高效。
二者结合的RIPPER算法
RIPPER中的后处理机制是为了在剪枝的基础上进一步提升性能，对R中的每条规则ri，RIPPER为它产生两个变体： RIPPER有效在通过将规则集中所有规则放在一起重新优化，通过全局的考虑缓解了贪心算法的局部性。

一阶规则学习

受限于命题逻辑表达能力，命题规则学习难以处理对象之间的关系，而关系信息再很多任务中是很重要的，要用一阶逻辑表示，使用一阶规则学习。
一阶的目的是描述一类物体的性质和相互关系.
同样的以西瓜集为例子，我们在现实生活中，很难去量化色泽、敲声等属性值，所以采用一阶规则学习来判断好瓜。下图表格是通过西瓜集转换得到的。
如上图，更好、更蜷、更凹是规则中关系描述对应的谓词，而个体对象瓜1 瓜2 被逻辑变量X \Y 替换。一阶学习能容易的引入领域知识，是相比命题学习的一大优势。
FOIL算法

1.遵循序贯覆盖
2.采用后剪枝(自顶向下)进行优化。
3.使用FOIL增益来选择文字。

举例：

归纳逻辑程序设计(ILP)

ILP的目标是完备地学习一阶规则。
我们之前所举的例子的规则大都是只对应了特殊的关系数据的样例，难以具有泛化能力。如果我们需要把特殊规则变为更一般就需要最小一般泛化（LGG）。举个例子：

其中，第一步先比较更好（1,10）和更好（1,15），由于文字中常量10不等于15，因此替换为Y，并在r1和r2中将其余位置上成对出现的10 和15 都替换为Y