机器之心|走过近30年，这个用逻辑程序表示数据的ML算法值得深入了解
选自arXiv
作者：Andrew Cropper等
机器之心编译
编辑：陈萍
归纳逻辑程序设计已「走过」近 30 年的历程 。 回顾这 30 年来的发展轨迹 ， 似乎很少有人提起这种算法 ， 我们用到更多是深度学习、神经网络等热门算法 。 其实作为一门相对冷门的算法 ， 归纳逻辑程序设计却在某些方面优于 ML 。 在这种算法即将迎来 30 周年之际 ， 来自牛津大学与鲁汶大学的研究者用一篇超长论文详细解读了归纳逻辑程序设计的相关内容 。
归纳逻辑程序设计（Inductive Logic Programming, ILP）是机器学习的一种形式 。 与基于统计的机器学习类似 ， ILP 也是需要给定一些例子作为训练样本 。 所不同的是 ， 基于统计的机器学习输出的是一个统计学的分类模型 ， 而 ILP 输出的是一个逻辑程序 。
近日 ， 来自牛津大学与鲁汶大学的研究者发表了一篇论文 ， 该论文介绍了必要的逻辑符号和主要的 ILP 学习设置 。 此外还介绍了 ILP 系统的主要组成部分 。 他们在几种维度上比较了几个 ILP 系统 ， 并详细介绍了 Aleph、TILDE、ASPAL 和 Metagol 等四个系统 。 最后 ， 研究者还将 ILP 与其他形式的机器学习进行对比 ， 并总结了 ILP 当前的局限性以及未来研究的新方向 。
论文地址：https://arxiv.org/pdf/2008.07912.pdf
因为该论文较长且还在完善的过程中 ， 本文就先摘取了其中的核心内容进行介绍 。
我们首先来了解下论文的核心结构 ， 该论文主要由以下 9 个部分组成：
ILP 发展史（第 1 节）；
描述 ILP 必要的逻辑程序设计符号（第 2 节）；
定义了标准的 ILP 学习设置（从蕴含中学习、从解释中学习和从满足性中学习）（第 3 节）；
描述构建 ILP 系统所需的基本假设（第 4 节）；
比较了多个 ILP 系统并描述了它们所支持的特征（第 5 节）；
描述了四个 ILP 系统（Aleph、TILDE、ASPAL、和 Metagol）（第 6 节）；
描述了 ILP 应用层面（第 7 节）；
将 ILP 与其他形式的 ML 进行比较（第 8 节）；
概述未来的研究方向（第 9 节） 。
以下内容将重点介绍 ILP 的基础知识、选择 ILP 的理由以及 ILP 的工作方式 。
ILP 简介
人类智慧的一项非凡成就是拥有学习新知识的能力 。 归纳法就是一种主要的学习类型：从特定观察（示例）形成通用规则（假设）的过程 。 例如 ， 假设你从一个袋子中抽出 10 个红色的球 ， 那么你可能会得出一个假设（一个规则） ， 即袋子中的所有球都是红色的 。 得出此假设后 ， 你就可以预测出袋子中下一个球的颜色 。
机器学习（ML）的目标是自动化归纳过程 。 换句话说 ， 机器学习的目标是产生一个能够泛化训练示例（观察）的假设（也称为模型） 。 例如 ， 给定带有标签的猫和狗的图像 ， 目标则是得出一个预测未标记图像是猫还是狗的假设 。
ILP 是 ML 的一种形式 。 与其他形式的 ML 一样 ， ILP 的目标是得出一个可以泛化训练示例的假设 。 虽然大多数形式的 ML 使用表格来表示数据（示例和假设） ， 但 ILP 使用逻辑程序（逻辑规则集）来表示数据 。
下表 1 说明使用 ML 与 ILP 的区别所在：
本文插图
大多数形式的 ML 采用标准表格表示来描述 ML 任务 。
本文插图
ILP 使用逻辑程序来表示数据 ， 由三个集合组成 (B ， E+ ，E-) ， 其中 B 集合表示背景知识 (BK) ， 其与特征类似 ， 但可以包含与示例间接关联的关系和信息；E + 和 E - 分别表示正面例子与负面例子 。
为什么选择 ILP
ILP 与大多数 ML 方法的根本不同在于 ， 大多数机器学习方法 ， 如支持向量机和神经网络 ， 都依赖于统计推理 。 相比之下 ， ILP 依赖逻辑推理 。 下表 2 展示了 ILP 和统计 ML 方法之间的不同之处：
本文插图
由上表可以得出 ， ML 与 ILP 的主要区别表现在用例、数据、假设、泛化、可解释性和知识迁移 6 个方面：
用例方面：众所周知 ， 许多形式的 ML 都非常需要数据 。 相比之下 ， ILP 系统可以基于少量示例进行归纳 ， 通常是从单个示例就能归纳；
数据方面：与大多数 ML 形式相反 ， ILP 使用表示为逻辑程序的 BK 进行学习 。 使用逻辑程序表示数据可以使 ILP 学习复杂的关系信息 ， 并可以轻松集成专家知识；
假设：使用逻辑程序表示假设有很多好处 。 因为它们与关系数据库密切相关 ， 所以逻辑程序自然支持关系数据 ， 例如图表；
泛化能力：ILP 得出的归纳假设超出了训练数据的范围 。 相比之下 ， 许多其他形式的 ML 因无法从少量训练示例中进行归纳而名声不佳（尤其是深度学习）；
可解释性：由于逻辑与自然语言的相似性 ， 因此人类可以轻松阅读逻辑程序 ， 这对于可解释的 AI 和超强的 ML 至关重要；
知识迁移：大多数机器学习算法都是单任务学习 ， 无法重用学到的知识 。 相比之下 ， 由于 ILP 具有符号表示 ， 它自然支持终身学习和迁移学习 ， 对于 AI 来说至关重要 。
ILP 工作方式
ILP 问题通常由三个集合构成：B（背景知识）、E+（正面例子）和 E-（负面例子） 。 ILP 问题是诱导一个假设 H ， 其中用 B 来解释 E + 和 E- 。
ILP 主要有三种学习设置：从蕴含中学习（learning from entailment, LFE）、从解释行中学习（learning from interpretation, LFI）和从可满足性中学习（learning from satisfiability, LFS） 。 LFE 和 LFI 是目前最流行的学习设置 ， 所以这里着重讨论这两种 。
从蕴含中学习（LFE）
定义 1：对于给定一个元组 (B ，E + , E ? )：
本文插图
LFE 的目标是返回一个假设 H ， 使得：
本文插图
可以从以下示例中获得直观感受 ， 考虑从蕴含元组学习：
本文插图
同时假定存在假设空间：
本文插图
那么可以考虑 ILP 系统应该返回哪些假设：
本文插图
根据定义 1 ， 一个假设必须包含每一个正面示例（完整的）而不需要负面示例（一致的） 。 然而 ， 训练示例往往是混杂的 ， 所以很难找到一个既完整又一致的假设 。 因此 ， 大多数方法都放宽了这一定义 ， 并试图找到一个包含尽可能多的正面示例和尽可能少的负面示例的假设 。
从解释中学习（LFI）
第二受欢迎的学习设置是 LFI 。
定义 2（从解释中学习）：给定元组（B ， E+ ， E?） ， 其中：
本文插图
LFI 的目标是返回一个假设 H ， 使得：
本文插图
示例 2 ， 为了说明 LFI ， 该论文重用 Law（2018）的示例 。 考虑以下输入元组：
本文插图
同时假定存在有假设空间：
本文插图
要找到一个解决 LFI 问题（定义 2）的假设 H ， 必须首先对每个示例计算 B 的最小模型 ， 即：
本文插图
问题是要找到一个假设 H ， 使 M_1 和 M_1 都是 H 的模型 ， 而 M_3 不是 。 假设 h_1 不是解 ， 因为 M_1 不是 B∪h_1 的模型；假设 h_1 不是解 ， 因为 M_1 不是 B∪h_2 的模型；假设 h_3 是一个解 ， 因为 M_1 和 M_2 都是 B∪h_3 的模型而 M_# 不是 B∪h_3 的模型 。
总体而言 ， ILP 相关设计架构如下：正面示例 + 负面示例 + 背景知识假设 。 ILP 所学模型基于一阶逻辑符号规则 ， 而非难以理解的黑箱模型 。 学习得到的模型可基于个体间的关系建模 ， 而非只对个体的标记进行预测 。 如果你想了解更多细节内容 ， 请参考该论文 。
参考链接：https://hyper.ai/wiki/4863
如何根据任务需求搭配恰当类型的数据库？
【机器之心|走过近30年，这个用逻辑程序表示数据的ML算法值得深入了解】在AWS推出的白皮书《进入专用数据库时代》中 ， 介绍了8种数据库类型：关系、键值、文档、内存中、关系图、时间序列、分类账、领域宽列 ， 并逐一分析了每种类型的优势、挑战与主要使用案例 。
推荐阅读
- 酿酒|用真全粮酿酒机器做酒，为什么发酵时间越长口感越好？
- 海沟|海洋新霸主诞生？软体机器鱼游入世界最深海沟
- 地球仪|机器压成的地球仪，纸张怎么完美贴合成曲面？
- 血管|陆清声教授：血管腔内介入手术机器人的特点和未来发展方向
- 狮子鱼|软体机器鱼“打卡”万米深海
- 太空探索技术公司|SpaceX的赛博朋克场景：机器狗检查星际飞船火箭残骸
- 马斯克|马斯克雇机器狗勘察火箭爆炸现场，网友：《黑镜》现实版
- 软体机器人|在海洋深深深处游泳的软体机器人
- 马里亚纳海沟|“打卡”马里亚纳海沟，这条软体机器鱼表现生猛
- 机器人|马斯克的星舰SN10爆炸，波动公司机器人成亮点，有何玄机？