Complexity Aspects of Knowledge Representation and Learning

这项研究涉及理论计算机科学和人工智能，特别是理论计算机科学的技术将应用于人工智能的两个重要问题领域：知识表示和机器学习。某些形式的知识表示对于人工智能应用来说是极其重要的。有些是从人工智能最早的时候就开始研究的，如Horn句的连词；另一些则是相对较新的，如可分解否定范式(DNNF)。这个项目将研究这些和其他形式的知识表示的计算复杂性，以及它们的形式可学习性。知识表示是有趣的，因为表示的选择决定了智能代理必须执行的各种任务的难易程度，例如推理或规划。这项研究的兴趣表示包括各种形式的命题逻辑，从析取范式到DNNF，以及各种更强大的逻辑，如模式逻辑，一些形式的谓词逻辑，和概率描述逻辑。这项建议包括各种问题和方法，由来自组合学和逻辑学的反复出现的主题统一起来。建议工作的一个主要目标是促进对重要知识表示形式的几个方面的理解。这包括回答诸如析取范式和决策树之类的基本形式化以及诸如dNFS之类的近期形式化的表达问题。它还包括确定不同形式的异常处理的复杂性，这既是一个实际问题，也与表示的有效可学习性问题密切相关。建议的工作将包括对Horn近似的重要推理技术的概率分析，以便确定尽管实例证明了该方法的最坏情况，该方法仍然可以有效地工作的情况，以及分析将知识库编译成更有效的形式的可能性，并对其结果进行简短的分解证明。该项目的另一个目标是更好地将不同知识表示形式的可学习性方面集成到新兴的知识表示比较理论中。这一系列研究包括在一些古老而成熟的问题上取得新的进展，如学习Horn句，对最近引入的问题的进一步研究，如修改Horn句，以及从可学习性的角度探索尚未被研究的表征，如模态逻辑。此外，还提出了命题逻辑和谓词逻辑中的一个新概念--排除维度方面的工作。智力优势：该建议解决了知识表示和学习中的几个关键问题：命题逻辑、谓词逻辑和模态逻辑中的表现力、有效操作、有效推理以及有效的学习和复习。该建议建立在提出者之前的研究成果基础上，包括开发新的逻辑学习和理论修改方法，以及他们在计算学习理论、计算复杂性理论、组合学和逻辑方面的技术专长，导致对人工智能核心问题领域的全面、深入研究，强调不同方面之间的相互作用。提出者在几个建议的研究方向上取得了初步成果。广泛的影响：数据量的快速增长和固有的复杂性极大地增加了适用于高效操作、推理、自动获取和修改的可表达的知识表示形式的重要性。基于命题、谓词、情态等逻辑的符号知识表示形式是大量应用中不可缺少的组成部分。了解这些应用中的复杂障碍，并找出规避这些障碍的可能途径，是进一步发展的一个关键组成部分。

The proposed research touches on both theoretical computer science and artifcial intelligence (AI).In particular, the techniques of theoretical computer science will be applied to two significantproblem areas in AI: knowledge representation and machine learning. Certain forms of knowledgerepresentation are extremely important for AI applications. Some, such as conjunctions of Hornclauses, have been studied from AI's earliest days; others, such as decomposable negation normalform (DNNF), are relatively new. This project will study the computational complexity aspects ofthese and other forms of knowledge representation, and formal learnability results for them.Knowledge representation is interesting because the choice of representation determines the easeor difficulty of various tasks that an intelligent agent must perform, such as reasoning or planning.The representations of interest for this research include various forms of propositional logic, rangingfrom disjunctive normal form to DNNF, and various more powerful logics, such as modal logics,some forms of predicate logic, and probabilistic description logic. This proposal includes a varietyof problems and approaches, unified by recurring themes drawn from combinatorics and logic.One main goal of the proposed work is to advance the understanding of several aspects of im-portant knowledge representation formalisms. This includes answering questions on expressivenessfor both basic formalisms such as disjunctive normal forms and decision trees, and also for recentformalisms such as DNNFs. It also includes determining the complexity of handling exceptions indifferent formalisms, which is both a practical problem and is also closely related to some questionson the efficient learnability of the representations. The proposed work will include a probabilisticanalysis of the important reasoning technique of Horn approximations, in order to identify situ-ations when the method can be expected to work efficiently in spite of examples demonstratingits worst-case behavior, and an analysis of the possibilities for compiling a knowledge bases into amore efficient form having short resolution proofs of its consequences.Another goal of the project is to obtain a better integration of the learnability aspect of thedifferent knowledge representation formalisms into the emerging comparative theory of knowledgerepresentation. This line of research includes making new progress on old, well established problems,such as learning Horn sentences, the further study of recently introduced problems, such as revisingHorn sentences, and the exploration of representations that have not been studied yet from the pointof view of learnability, such as modal logics. Work is also proposed on the exclusion dimension, apromising recent notion, in both propositional and predicate logic.Intellectual merit: The proposal addresses several key issues in knowledge representationand learning: expressiveness, efficient manipulation, efficient reasoning, and efficient learning andrevision, in propositional, predicate, and modal logic. The proposal builds on the previous re-search results of the proposers, which includes the development of new approaches to logic learningand theory revision, and their technical expertise in computational learning theory, computationalcomplexity theory, combinatorics and logic, leading up to a comprehensive, in-depth study of coreproblem areas of artificial intelligence, emphasizing the interactions between the different aspects.The proposers have initial results in several of the suggested research directions.Broader impact: The rapid increase in both the amount of, and the inherent complexityof data greatly increases the importance of expressive knowledge representation formalisms thatare suitable for efficient manipulation, reasoning, automated acquisition and revision. Symbolicknowledge representation formalisms based on propositional, predicate, modal and other logicsform an indispensable component in a large number of applications. Understanding the complexityobstacles in these applications, and identifying possible avenues for circumventing them, is a crucialcomponent of further development.