20、规则模型与线性模型解析

规则模型与线性模型解析

规则模型概述

规则模型在机器学习中有着重要的地位，它可用于学习假设和目标谓词，但也面临着诸如非终止性等计算挑战。不过，这并不意味着学习无法进行，相关技术可用于同时学习多个相互关联的谓词，还能创造出完全未被观察到的新背景谓词。

在决策树中，从根到叶的分支可被解释为一个合取分类规则。规则模型将其进行了推广，在将多个规则组合成模型的方式上更加灵活。典型的规则学习算法是覆盖算法，它迭代地学习一条规则，然后移除被该规则覆盖的示例。这种方法由Michalski在1975年通过其AQ系统开创，并在随后的三十年里得到了高度发展。

规则可能会重叠，因此需要一种策略来解决规则之间的潜在冲突。常见的策略有以下两种：
1. 有序规则列表 ：将规则组合成有序规则列表。知名的规则列表学习器包括CN2和Ripper，后者通过增量式减少误差剪枝特别有效地避免了过拟合。Opus系统也值得注意，它会对所有可能规则的空间进行完全搜索。
2. 无序规则集 ：无序规则集是有序规则列表的一种替代方案。覆盖算法经过调整，每次为单个类学习规则，并仅移除当前考虑类中被覆盖的示例。CN2可以在无序模式下运行以学习规则集。

规则模型还可用于描述性任务，例如子组发现。加权覆盖算法是CN2的一种改进，可用于子组发现。此外，关联规则学习算法可从著名的Apriori算法改编而来，关联规则也可用于构建有效的分类器。

一阶规则学习已经研究了40年，有着丰富的历史。有多种系统可用于一阶规则学习，如FOIL系统实现了一种自上而下的学习算法，而Golem系统开创了自下而上的技术，并在Progo