问答集编程的复杂性和通用性

导读

论文原题《The complexity and generality of learning answer set programs》，于2018年6月正式发表于Artificial Intelligence杂志。由良宵听雨摘选翻译。

摘要

传统上认为，归纳逻辑程序设计（ILP）领域的大部分工作解决了逻辑编程的问题。另一方面，问答集编程（ASP）正在崛起，成为知识表示和推理领域的良好实践，越来越被业内认可。因而，随着若干个有关新学习框架提议的诞生，ILP的研究活动已经扩展到了ASP领域。

在本文中，我们研究了这些现有框架在问答集语义下的特点。

具体来说，我们详细分析了每个框架的计算复杂性，并考虑了两个问题：1. 判断某个假设是否必要；2. 学习任务是否有解。我们引入了“通用性”这个新概念，用来定义那些更通用的框架，从而可以在一组错误的ASP程序中区分出一个ASP假设解。

我们在文中特地展示了我们新提出的“有序问答集的上下文学习框架（Context-dependent Learning from Ordered Answer Sets）”。

在勇敢归纳（brave induction）、稳定模型归纳（induction of stable models）、谨慎归纳（cautious induction）这3类框架中，谨慎归纳的复杂性最高。我们新提出的框架有着和谨慎归纳相同的计算复杂性，比上述三类框架更通用。

关键词

非单调逻辑学习；问答集编程；非单调学习的复杂性