论文部分内容阅读
知识表示和推理（Knowledge Representation and Reasoning,KRR）是人工智能核心研究内容之一,旨在为实现基于知识的智能系统提供知识编码和问题求解的理论和技术方法。为了能够处理不同类型的知识从而能够实现对更多问题的建模和求解,研究表达能力强的知识表示语言以及配套的通用求解技术是KRR领域的一项长期关键任务。作为KRR的一种主要方法,逻辑程序的表达能力和求解技术在几十年来获得了长足的发展。从早期的Prolog到回答集逻辑程序（Answer Set Programming,ASP）以及各类概率逻辑程序如P-log、Prob Log、马尔可夫逻辑网（Markov Logic Network,MLN）等,逻辑程序的表达能力逐步提升,相应的求解系统也逐渐成熟,能够处理越来越复杂的问题。马尔可夫回答集逻辑程序(Logic Programming under answer set semantics and Markov Logic Networks,LPMLN)是一种新型逻辑程序。语言表达能力方面,LPMLN通过在ASP的基础上引入MLN中的不确定信息处理方式,为常见的不确定、不一致、以及缺省知识的表示提供了一种新途径。在医疗诊断、个性化推荐、地理知识问答等方面的初步应用研究表明LPMLN语言在实际的知识表示中具有应用价值。但是当前LPMLN的求解技术尚未得到充分的研究,缺乏提升求解效率相关的理论和技术。已有的LPMLN求解器通过借用ASP和MLN求解器实现,尚未基于LPMLN自身的理论及性质对求解过程进行优化,求解效率较差。这些问题制约了LPMLN的进一步发展和推广应用,因此,迫切需要优化LPMLN程序的求解系统,提升求解效率。为了支撑LPMLN程序求解的优化,本文有针对性地研究LPMLN程序求解并行化和LPMLN程序简化的理论及技术,构建了程序切分和等价化简的基础理论及用于求解优化的技术方法,具体分为四个部分:（1）为了支撑LPMLN求解的并行化,针对LPMLN的求解空间的可切分问题,提出LPMLN程序的增强子集理论,以及基于该理论的LPMLN程序的纵向切分方法和并行求解算法。基于LPMLN求解的生成-测试过程,定义了将LPMLN的求解空间划分为若干子集的概念,即为增强子集。并且证明了LPMLN程序及其增强子集的求解结果之间具有包含关系,即LPMLN程序的增强子集定理。根据该定理可以认为增强子集是对LPMLN程序的纵向切分。在此基础上,给出了一种基于ASP的增强子集求解方法以及基于增强子集的LPMLN程序的并行求解算法。（2）为了支撑LPMLN求解的简化并提供更丰富的LPMLN求解并行化方法,针对LPMLN的求解步骤的可切分问题,提出了LPMLN程序的分割集理论,以及基于该理论的LPMLN求解的简化方法以及横向切分方法和并行求解算法。基于LPMLN程序中规则的依赖关系,定义了将LPMLN程序的求解划分为若干步骤的概念,即为分割集。并证明了LPMLN程序的求解结果可以通过其关于分割集的子程序的求解结果组合得到,即LPMLN程序的分割集定理。根据该定理可以认为分割集是对LPMLN程序的横向切分。在此基础上,提出了一类特殊的LPMLN程序,即独立可分LPMLN程序,并证明了该类LPMLN程序的推理任务的求解过程可以简化。对于独立可分和一般LPMLN程序,分别提出了基于分割集定理的并行求解算法。（3）为了验证基于增强子集和分割集的LPMLN的并行求解方法的效果,构造了一组LPMLN程序的测试案例,并用给出的案例对上述两种方法进行了实验验证。实验结果表明基于增强子集和分割集的LPMLN并行求解方法能够提升求解的效率。进一步介绍了基于两种求解方法实现的LPMLN求解系统在解决实际问题中的应用,包括国家863项目“开放域知识关联、推理与检索关键技术及系统”以及国家重点研发计划项目“大数据多模态交互协同关键技术”等中的应用。（4）为了在保持语义等价的前提下减少程序中规则及文字数量使得程序简化,从而支撑LPMLN求解优化,针对LPMLN程序的语义等价判定问题,提出了LPMLN程序的强等价的概念及模型论判定方法,为进一步研究LPMLN程序的简化奠定基础。基于不同语义等价关系,定义了LPMLN程序的半强等价、权重强等价、以及概率强等价等三种类型的强等价概念,其中半强等价是其它类型强等价的基础。基于HT-逻辑（Logic of Here-and-There）,提出了判定LPMLN程序的三种强等价的方法,即HT-模型方法,并证明了该判定方法的时间复杂度为co-NP-complete。上述研究成果从理论上表明,基于强等价的LPMLN程序的简化方法通过减少程序中的规则或文字可以缩小求解时模型搜索的空间,提升求解效率,但存在计算复杂度高的问题。（5）为了更高效地判定LPMLN程序的强等价,针对缺乏判定LPMLN半强等价的语法条件（简称半强等价语法条件）的问题,提出了自动构造并验证LPMLN的半强等价语法条件的算法,并给出了一组可以用于LPMLN程序简化的半强等价语法条件。通过深入研究LPMLN强等价判定的HT-模型方法,定义了LPMLN程序的独立集的概念,并针对独立集的不同操作,提出了LPMLN程序的单次替换、单次删除、单次约减、单次添加、以及单次扩张等五种单次变换方法。随后,给出了LPMLN程序在不同的单次变换下保持半强等价和非半强等价关系不变的性质。基于这些性质,提出了LPMLN程序的半强等价语法条件的一般形式,即独立集条件。在此基础上,给出了构造和验证独立集条件的算法以及对该算法的改进方法。通过改进后的算法,给出了一组可以用于LPMLN程序简化的半强等价语法条件。本文的研究成果不仅有利于实现更加高效的LPMLN求解系统从而促进其应用,也有助于加深对于LPMLN程序理论性质的认识从而促进对于逻辑程序基础理论的研究。