语义明确、能描述数据分布所隐含的客观规律或领域概念

可写成”若。。。，则。。。“形式的逻辑规则

形式表示：\(\bigoplus \leftarrow f_1 \wedge f_2 \wedge \cdot\cdot\cdot \wedge f_L\)

\(\leftarrow\)：逻辑蕴含符号

\(f_1 \wedge f_2 \wedge \cdot\cdot\cdot \wedge f_L\)：规则体（body），表示该规则的前提（右边部分）。由逻辑文字组成的合取式，\(\wedge\)：表示并且。

\(\bigoplus\)：规则头（head），表示该条规则的结果。一般是逻辑文字，规则所判定的目标类别或概念。

\(L\)：规则中逻辑文字的个数，是规则的长度

这样的逻辑规则也称为”if-then规则“

规则学习：

rule learning

从训练数据中学习出一组能用于对未见示例进行判别的规则

具有更好的可解释性

数理逻辑具有很强的表达能力

覆盖：cover，符合某规则的样本称为被该规则覆盖

规则1：\(好瓜 \leftarrow （根蒂=蜷缩） \wedge（脐部=凹陷）\)

规则2：\(\neg好瓜 \leftarrow （纹理=模糊）\)

被规则1覆盖的是好瓜，但未被规则1覆盖的未必不是好瓜

被规则2覆盖的是好瓜，但未被规则2覆盖的不是好瓜。因为此时的规则头带有\(\neg\)标签

conflict

规则集合中的每一条规则可看做一个模型

当同一个示例被判别结果不同的多条规则覆盖时，发生冲突

冲突消解：

conflict resolution

投票法：判别规则数多的一类结果

排序法：在规则集合上定义顺序，冲突时使用排序最前的规则。带序规则或者优先级规则

元规则法：根据领域知识事先设定一些元规则，即关于规则的规则，比如”发生冲突时使用长度最短的规则“

命题规则：原子命题和逻辑连接词构成的简单陈述句。

一阶规则：所有自然数加1都是自然数，这种就是一阶规则，可以写成表达式：\(\forall X(自然数(\sigma(X)) \leftarrow 自然数(X), sigma(X)=X+1)\)

能表达复杂的关系，也称为关系型规则(relational rule)

命题规则是一阶规则的一个特例，一阶规则的学习复杂得多

例子：西瓜训练集2.0

根据第一个样本加入规则：\(\neg好瓜 \leftarrow （色泽=亲绿）\)

此规则覆盖样本1，6，10，17，其中2个正样本，2个负样本，不符合规则的条件

尝试基于”色泽“的其他原子命题：”色泽=乌黑“，亦不能满足

基于”色泽“不能产生一条规则，所以返回”色泽=青绿“，尝试增加一个基于其他属性的原子命题，比如”根蒂=蜷缩“，\(好瓜 \leftarrow （色泽=青绿） \wedge（根蒂=蜷缩）\)

此规则覆盖了负样本17，不行

更换基于”根蒂“的其他原子命题：\(好瓜 \leftarrow （色泽=青绿） \wedge（根蒂=稍蜷）\)

此规则不覆盖任何负样本，符合规则的条件

保留此规则，去掉其覆盖的正样本6，将剩下的样本作为训练集。重复进行规则生成。

最后可得到一个序贯覆盖学习的结果：

缺点：基于穷尽搜索，在属性和候选值较多事出现组合爆炸

现实策略：

自顶向下：top-down，从比较一般的规则开始，逐渐添加新文字以缩小规则覆盖范围，直到满足预定条件为止。规则逐渐特化的过程，也称为生成-测试法。

自底向上：bottom-up，从比较特殊的规则开始，逐渐删除文字以扩大规则覆盖范围，直到满足条件为止。规则逐渐泛化的过程，也称为数据驱动法。

自顶向下：容易获得泛化性能较好的规则，对噪声的鲁棒性更强。命题规则学习通常使用。

自底向上：更适合训练样本较少的情形。一阶规则学习这类假设空间很复杂的任务上使用。

自顶向下：

空规则开始

准确率评估规则好坏

第一轮：两个相同准确率（3/4），选择次序靠前的

第二轮：5个相同的准确率(100%)，选择覆盖样本最多、且属性次序最靠前的。

对于这里：先准确率，相同时考虑覆盖样本数，再相同时考虑属性次序。具体可自行设计。

每次仅考虑一个”最优“

贪心：易限于局部最优

做法：集束搜索（beam search），每轮保留最优的b个逻辑文字，在下一轮均用于创建候选集，再把候选集中最优的b个留待下一轮使用

序贯覆盖：

基本框架，可扩展至其他规则学习

多分类问题：当学习第c类的规则时，将所有 属于类别c的为正样本，其他均为负样本

性能指标：评估增加、删除逻辑文字前后的规则性能，判断是否需要剪枝

借助统计性显著性检验：CN2算法

使用似然率统计量（likelihood ratio statistics，LRS）：\(m_+,m_-\)：训练集正负样本，\(\hat m_+,\hat m_-\)：规则覆盖的正负样本

衡量规则覆盖的样本分布与经验分布的差别：值越大，说明差别越大；值越小，说明规则的效果可能是偶然现象。

一般设置LRS很大：比如0.99，才让算法停止生长

减错剪枝，reduced error pruning，REP

将样本集划分为训练集和验证集

从训练集学得规则集合

对规则集合进行多轮剪枝：每一轮穷举可能的剪枝操作，然后用验证集对剪枝产生的所有候选规则集进行评估，保留最好的那个规则集进行下一轮剪枝

重复，直到通过剪枝无法提高验证集的性能为止

复杂度太高

IREP：incremental REP

在生成每条规则前，先将当前样本集划分为训练集和验证集

在训练集山生成一条规则r，立即在验证集上对其进行REP剪枝，得到规则r’

将r’覆盖的样本去掉，在更新后的数据集上重复上述过程

IREP：对单条规则进行剪枝，更加高效

REP：针对规则集进行剪枝

RIPPER：

泛化性能超过很多决策树

学习速度更快

将剪枝和后处理优化相结合

剪枝+后处理：

对于R中的每条规则\(r_i\)，会产生两个变体：

\(r_i'\)：基于\(r_i\)覆盖的样本，用IREP*重新生成一条规则\(r_i'\)，称为替代规则(replacement rule)

\(r_i''\)：对\(r_i\)增加文字进行特化，然后使用IREP*剪枝生成一条规则\(r_i''\)，称为修订规则(revised rule)

把\(r_i'\)和\(r_i''\)分别与R中除了\(r_i\)之外的规则放在一起，组成规则集R’和R‘’，与R进行比较，选择最优的保留下来。

为什么更好？

之前：按序生成规则，每条规则没有考虑对其后产生的规则，属于贪心算法，容易陷入局部最优

现在：后处理优化过程中将R中的所有规则放在一起重新加以优化，是通过全局的考虑来缓解贪心算法的局部性，从而得到更好的效果。

著名的一阶规则学习算法

遵循序罐覆盖框架且采用自顶向下的规则归纳策略

使用“FOIL增益”来选择文字：\(F_{Gain}=\hat m_+ \times (log_2{\frac{\hat m_+}{\hat m_+ + \hat m_-}} - log_2{\frac{m_+}{m_+ + m_-}})\)

vs 决策树增益：仅考虑正样本的信息量，并使用新规则覆盖的正样本数作为权重

对文字的每个位置的常量进行考察

若常量在两个文字中相同则保持不变，记为：\(LGG(t,t)=t\)

若不同则替换为用一个新变量，且变换应用于公式其他位置，记为：\(LGG(s,t)=V\)，V是新变量

LGG是能特化为r1和r2的所有一阶公式中最为特殊的一个:BU 不存在既能特化为r1和r2，也能泛化为他们的LGG的一阶公式r‘。