《机器学习》笔记-规则学习（15）

作者： 刘才权

编辑：龚 赛

前 言

如今机器学习和深度学习如此火热，相信很多像我一样的普通程序猿或者还在大学校园中的同学，一定也想参与其中。不管是出于好奇，还是自身充电，跟上潮流，我觉得都值得试一试。对于自己，经历了一段时间的系统学习（参考《机器学习/深度学习入门资料汇总》），现在计划重新阅读《机器学习》[周志华]和《深度学习》[Goodfellow et al]这两本书，并在阅读的过程中进行记录和总结。这两本是机器学习和深度学习的入门经典。笔记中除了会对书中核心及重点内容进行记录，同时，也会增加自己的理解，包括过程中的疑问，并尽量的和实际的工程应用和现实场景进行结合，使得知识不只是停留在理论层面，而是能够更好的指导实践。记录笔记，一方面，是对自己先前学习过程的总结和补充。 另一方面，相信这个系列学习过程的记录，也能为像我一样入门机器学习和深度学习同学作为学习参考。

01

基本概念

规则学习是“符号主义学习”（symbolism learning）的主要代表，是最早开始研究的机器学习技术之一。

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

与神经网络、支持向量机这样的“黑箱模型”相比，规则学习具有更好的可解释性，能使用户更直观地对判别过程有所了解。另一方面，数理逻辑具有极强的表达能力，绝大多数人类知识都能通过数理逻辑进行简洁的刻画和表达。因此，规则学习能更自然的在学习过程中引入领域知识。此外，逻辑规则的抽象描述能力在处理一些高复杂度的AI任务时具有显著的优势，例如在问答系统中有时可能遇到非常多、甚至无穷种可能的答案，此时若能基于逻辑规则进行抽象表述或者推理，则将带来极大的便利。

从形式语言表达能力而言，规则可分为两类：

* ”命题规则“（propositional rule）

由”原子命题“（propositional atom）和逻辑连接词“与”、“或”、“非”和“蕴含”构成的简单陈述句；

* “一阶规则”（first-order rule）

基本成分是能描述事物的属性或关系的“原子公式”（automic formula）；

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

02

序贯覆盖

规则学习的目标是产生一个能覆盖尽可能多的样例规则集。最直接的做法是“序贯覆盖”（sequential covering），即逐条归纳：在训练集上每学到一条规则，就将该规则覆盖的训练样例去除，然后以剩下的训练样例组成训练集重复上述过程。由于每次只处理一部分数据，因此也被称为“分治”（separate-and-conquer）策略。

由于序贯覆盖法简单有效，几乎所有规则学习算法都以它为基本框架。它能方便地推广到多分类问题上，只需将每类分别处理即可。

03

剪枝优化

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

04

一阶规则学习

受限于命题规则表达能力，命题规则学习难以处理对象之间的“关系”（relation），而关系信息在很多任务中非常重要。需用一阶逻辑表示，并且要使用一阶规则学习。

05

归纳逻辑程序设计

归纳逻辑程序设计（Inductive Logic Programming，简称ILP）在一阶规则学习中引入了函数和逻辑表达式嵌套。一方面，这使得机器学习系统具备了更为强大的表达能力；另一方面，ILP可看作用机器学习技术来解决基于背景知识的逻辑程序（logic program）归纳，其学得的“规则”可被PROLOG等逻辑程序设计语言直接使用。

往期回顾之作者刘才权

【1】《机器学习》笔记-概率图模型（14)

【2】《机器学习》笔记-半监督学习（13）

【3】《机器学习》笔记-计算学习理论（12）

【4】《机器学习》笔记-特征选择与稀疏学习（11）

【5】《机器学习》笔记-降维与度量学习（10）

【6】《机器学习》笔记-聚类（9）

【7】《机器学习》笔记-集成学习（8）