不完全知识的遗忘理论研究及应用

Knowledge representation and reasoning (KR) is a crucial problem in artificial intelligence, the spring-up of large-scale and incomplete knowledge base demands new challenges for sharing and inconsistency handling of knowledge base. In 1994, Lin and Reiter proposed a forgetting theory for first-order logic, called eliminating intermediate variables. It is proved being an effective approach for knowledge base, and was successfully applied in abductive reasoning, inconsistency handling, multi-agents negotiation, knowledge base merging and extracting and so forth. Logic programming based on answer set semantics, called Answer set programming, provides a declarative knowledge representation and reasoning paradigm. Due to its nonmonotonic nature and the existence of many effective solvers for answer set programs, it turns into an important formalism for incomplete knowledge representation and reasoning. Nowadays, it has found many successful applications in artificial intelligence, such as diagnosis, planning and scheduling, and beyond artificial intelligence like bioinformatics and others. In the project, we will study the forgetting theory in answer set programs, investigate its algorithms, properties, complexities and its applications in handling inconsistency, multi-agents negotiation, belief update, abductive reasoning and diagnosis. We will further consider the forgetting theory in other nonmonotonic logics, such as default logic. Bases on the theoretical foundation, we build up a framework of forgetting theory in incomplete knowledge formalisms, that provides an effective and new mechanism to deal with large-scale and incomplete knowledge base, and in particular for its sharing and handling inconsistency.

知识表示与推理一直是人工智能研究的核心问题之一，大规模以及不完全知识库的快速涌现为知识库共享和不一致性处理提出了新的挑战。Lin和Reiter在1994年为一阶逻辑提出的遗忘理论(即删除中间变量)被证明是知识库处理的重要手段,可用于溯因推理、不一致性处理、多智能体协商以及知识抽取与合并等各个方面。基于回答集语义的逻辑程序(回答集程序)是描述性知识表示与推理的重要形式系统之一，由于其非单调的本质特征和各种有效的回答集求解系统的出现而成为不完全知识表示与推理的有力工具，在诊断、规划、调度以及生物信息学等方面具有广阔的应用情景。我们将从研究回答集程序的遗忘理论出发，探讨其算法、性质、复杂性以及在不一致性处理、多智能体协商、信念更新以及溯因推理与诊断等方面的应用；进而推广遗忘理论到其它非单调形式系统，例如缺省逻辑,从而建立不完全知识的遗忘理论框架，为大规模及不完全知识库提供新的有效处理手段。

知识表示与推理一直是人工智能研究的核心问题之一，大规模以及不完全知识库的快速涌现为知识库共享和不一致性处理提出了新的挑战。基于回答集语义的逻辑程序设计（Answer set programming，简称ASP）作为不完全知识表示与推理的主要框架在人工智能等领域具有广泛的应用前景。..我们主要以回答集程序为载体，研究知识表示与推理中的遗忘理论，通过遗忘掉一些与具体任务不相关的符号，来实现知识库的抽取、重用以及知识的推理（例如最弱充分性和最强必要性条件）。主要完成了（1）在各种强等价意义下的命题回答集程序的遗忘公设、算法、复杂性及其与经典命题逻辑下遗忘的关系，证明了回答集程序遗忘的表示定理，即一个公式可以作为遗忘结果的充分必要条件，证明了判定是否是遗忘结果是coNP完全的，遗忘结果的等价性问题是与2QBF的有效性问题的复杂性是一致的（即处在复杂性分层的第二层）；（2）提出了限制理论（circumscription）的遗忘算子，发现该遗忘理论不具有的一些经典命题逻辑下遗忘的性质，以及保持这些性质的充要条件；（3）发现了回答集程序遗忘理论各种公设之间的不一致关系，证明了保持这些公设的充要条件（即回答集程序子类），并提出了一个计算其遗忘结果的句法方法；（4）发现了基于回答集程序环及其切分概念的回答集计算加速机制；（5）提出基于解释变换的Horn和析取逻辑程序归纳学习理论，为发现生物信息领域中的基因调控网络结构提出了一种新方法。..上述关于知识表示与推理中遗忘理论的研究，从逻辑角度为大规模的知识共享、重用与推理提供了新的理论方法，而归纳学习作为遗忘的对立面（发现符号及符号之间的关系）为深化遗忘（去掉符号及符号之间的关系）理论提供了有益的补充，从而对从不完全、大规模的数据中发现知识提供新的思路。