规则学习

“规则” 指语意明确,能描述数据分布所隐含的客观规律或领域概念;规则学习指从训练数据中学习出一组能用于未见实例进行判别的规则

  1. 命题规则:由原子命题【与,或,非,蕴含】组成的简单陈述句
  2. 一阶规则、关系型规则:在1的基础上添加条件限定【X是Y,对于任意X成立,存在Y使之成立】,能表达复杂关系式
  • 序贯覆盖

在训练集上每学到一条规则,就将数据集中符合这条规则的训练样例去除(分治策略)

较多时候,穷尽搜索会由于组合爆炸而不可行

- 自顶向下(生成-测试)
从比较一般的规则开始,逐渐添加新文字以缩小覆盖范围,更容易产生泛化性能好的规则

- 自底向上(数据驱动法)
从比较特殊的规则开始,主键删除文字以扩大范围,是规则泛化的过程,适合小数据量
  • 剪枝优化

预剪枝或后剪枝,参考决策树

CN2算法

假设用规则集进行预测必须显著优于直接基于训练样例集后验概率进行预测。

剪错剪枝(REP)O(m^4)

将样例集划分为训练集和验证集,从训练集上学得规则集R后进行多轮剪枝,在每一轮穷举所有可能的剪枝操作,然后用验证集对所有的候选规则集进行验证,选取最好的进行下一轮

IREP O(m log^2m)

每生成一条规则就立即验证,在验证集上进行REP剪枝;将完成后规则覆盖的样例去除,再新的样例上重复上述过程

RIPPER

使用IREP*生成规则集R,删除尾部多个文字,并得到最终规则集后再进行一次IREP

  • 一阶规则学习

数据直接描述样例之间的关系,成为关系数据。更容易引入领域知识。

FOIL

学习过程类似命题规则学习,

  • 归纳逻辑程序设计(ILP)

使用机器学习技术解决基于背景知识的逻辑程序。

最小一般泛化

直接将一个或多个正例对应的具体事实作为初始规则,再逐步泛化。对每个位置的常量进行考察,若常量在两个文字中相同则保持不变,否则替换为新一个变量,并替换公式的所有其他位置。忽略不含共同谓词的文字

逆归结

  1. 吸收 \frac{p \gets A \land B \, q \gets A}{p \gets q\land B \, q \gets A}
  2. 辨识 \frac{p \gets A \land B \, p \gets A \land q}{q \gets B \, p \gets A \land q}
  3. 内构 \frac{p \gets A \land B \, p \gets A \land C }{q \gets B \, p \gets A \land q \, q \gets C}
  4. 互构 \frac{p \gets A \land B \, q \gets A \land C}{p \gets r\land B \, r \\gets A \, q \gets r \land C }

其中 \frac{X}{Y} 表示X蕴含Y。一阶逻辑的归纳通常需要合一置换操作

  1. 置换:用某些项来替换逻辑表达式中的变量
  2. 合一:用一种变量置换令两或多个逻辑表达式相等