【机器学习-周志华】学习笔记-第十五章

记录第一遍没看懂的
记录觉得有用的
其他章节：
        第一章
        第三章
        第五章
        第六章
        第七章
        第八章
        第九章
        第十章
        十一章
        十二章
        十三章
        十四章
        十五章
        十六章

        从形式语言表达能力而言，规则可分为两类：“命题规则”和" 一阶规则"。 前者是由"原子命题" 和逻辑连接词“与” ($\wedge$)、“或” ($\vee$) 、“非” ($\neg$)和“蕴含”($\leftarrow$))构成的简单陈述句；后者的基本成分是能描述事物的属性或关系的"原子公式"。他的优点是能使用户更直观地对判别过程有所了解。
        规则学习的目标是产生一个能覆盖尽可能多的样例的规则集。最直接的做法是“序贯覆盖”，即逐条归纳：在训练集上每学到一条规则，就将该规则覆盖的训练样例去除，然后以剩下的训练样例组成训练集重复上述过程。由于每次只处理一部分数据，因此也被称为"分治"策略。
        但基于穷尽搜索的做法在属性和候选值较多时会由于组合爆炸而不可行。现实任务中一般有两种策略来产生规则：第一种是“自顶向下”（特化过程），即从比较一般的规则开始，逐渐添加新文字以缩小规则覆盖范围，直到满足预定条件为止；第二种策略是“自底向上”（泛化过程），即从比较特殊的规则开始，逐渐删除文字以扩大规则覆盖范围，直到满足条件为止。前者更容易产生泛化性能较好的规则，对噪声的鲁棒性好；后者则更适合于训练样本较少的情形。
        规则生成本质上是一个贪心搜索过程，需有一定的机制来缓解过拟合的风险，最常见的做法是剪枝。剪枝可发生在规则生长过程中，即“预剪枝”；也可发生在规则产生后，即“后剪枝”。通常是基于某种性能度量指标来评估增/删逻辑文字前后的规则性能，或增/删规则前后的规则集性能，从而判断是否要进行剪枝。
        命题规则学习难以处理对象之间的关系 ，而关系信息在很多任务中非常重要，因此需要一阶规则学习。FOIL (Fírst-Order Inductive Learner) 是著名的一阶规则学习算法，它遵循序贯覆盖框架且采用自顶向下的规则归纳策略。它可大致看作命题规则学习与归纳逻辑程序设计之间的过渡，其自顶向下的规则生成过程不能支持函数和逻辑表达式嵌套，因此规则表达能力仍有不足；但它是把命题规则学习过程通过变量替换等操作直接转化为一阶规则学习，因此比一般归纳逻辑程序设计技术更高效。
        归纳逻辑程序设计 (ILP) 在一阶规则学习中引入了函数和逻辑表达式嵌套。一方面，这使得机器学习系统具备了更为强大的表达能力；另一方面，ILP可看作用机器学习技术来解决基于背景知识的逻辑程序归纳，其学得的"规则"可被 PROLOG 等逻辑程序设计语言直接使用。
        归纳逻辑程序设计采用自底向上的规则生成策略，直接将一个或多个正例所对应的具体事实作为初始规则，再对规则逐步进行泛化以增加其对样例的覆盖率。泛化操作可以是将规则中的常量替换为逻辑变量，也可以是删除规则体中的某个文字。最基础的技术是“最小一般泛化” 。
        归结原理可以参考百度百科的例子：

        归结是已知$C_1$和$C_2$，得$C$；而逆归结研究的是在己知$C$和某个$C_i$的情况下如何得$C_j(i\ne j)$。逆归结的一些范式：

        一阶逻辑的归结、逆归结通常需进行合一置换操作。置换是用某些项来替换逻辑表达式中的变量；合一是用一种变量置换令两个或多个逻辑表达式相等。

规则运算这一章感觉跟前面的都不一样，做的是逻辑上的与或非运算。