Andrew Cropper等作者陈萍编辑

走过近30年,这个用逻辑程序表示数据的ML算法值得深入了解

归纳逻辑程序设计已「走过」近 30 年的历程。回顾这 30 年来的发展轨迹,似乎很少有人提起这种算法,我们用到更多是深度学习、神经网络等热门算法。其实作为一门相对冷门的算法,归纳逻辑程序设计却在某些方面优于 ML。在这种算法即将迎来 30 周年之际,来自牛津大学与鲁汶大学的研究者用一篇超长论文详细解读了归纳逻辑程序设计的相关内容。

选自arXiv

作者:Andrew Cropper等

归纳逻辑程序设计(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

理论牛津大学归纳逻辑程序设计
相关数据
深度学习技术

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法,至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

逻辑推理技术

逻辑推理中有三种方式:演绎推理、归纳推理和溯因推理。它包括给定前提、结论和规则

神经网络技术

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

逻辑技术

人工智能领域用逻辑来理解智能推理问题;它可以提供用于分析编程语言的技术,也可用作分析、表征知识或编程的工具。目前人们常用的逻辑分支有命题逻辑(Propositional Logic )以及一阶逻辑(FOL)等谓词逻辑。

支持向量机技术

在机器学习中,支持向量机是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。给定一组训练实例,每个训练实例被标记为属于两个类别中的一个或另一个,SVM训练算法创建一个将新的实例分配给两个类别之一的模型,使其成为非概率二元线性分类器。SVM模型是将实例表示为空间中的点,这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后,将新的实例映射到同一空间,并基于它们落在间隔的哪一侧来预测所属类别。

迁移学习技术

迁移学习是一种机器学习方法,就是把为任务 A 开发的模型作为初始点,重新使用在为任务 B 开发模型的过程中。迁移学习是通过从已学习的相关任务中转移知识来改进学习的新任务,虽然大多数机器学习算法都是为了解决单个任务而设计的,但是促进迁移学习的算法的开发是机器学习社区持续关注的话题。 迁移学习对人类来说很常见,例如,我们可能会发现学习识别苹果可能有助于识别梨,或者学习弹奏电子琴可能有助于学习钢琴。

关系数据库技术

关系数据库,是创建在关系模型基础上的数据库,借助于集合代数等数学概念和方法来处理数据库中的数据。现实世界中的各种实体以及实体之间的各种联系均用关系模型来表示。关系模型是由埃德加·科德于1970年首先提出的,并配合“科德十二定律”。现如今虽然对此模型有一些批评意见,但它还是数据存储的传统标准。

一阶逻辑技术

一阶逻辑是使用于数学、哲学、语言学及计算机科学中的一种形式系统。 过去一百多年,一阶逻辑出现过许多种名称,包括:一阶断言演算、低阶断言演算、量化理论或断言逻辑。一阶逻辑和命题逻辑的不同之处在于,一阶逻辑有使用量化变数。

推荐文章
暂无评论
暂无评论~