Complexity Aspects of Knowledge Representation and Learning

知识表示和学习的复杂性

• 批准号: 0431059
• 负责人: Robert Sloan
• 金额: --
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-15 至 2008-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0431059&HistoricalAwards=false
• 关键词: Complexity; Aspects; Knowledge; Representation; Learning

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.

该研究涉及理论计算机科学和人工智能（AI）。特别是，理论计算机科学的技术将应用于AI中的两个重要问题领域：知识表示和机器学习。某些形式的知识表示对于人工智能应用是极其重要的。一些，如Hornclauses的连词，从AI的早期就已经被研究过了;其他的，如可分解否定范式（DNNF），相对较新。这个项目将研究这些和其他形式的知识表示的计算复杂性方面，以及它们的形式化可学习性结果。知识表示是有趣的，因为表示的选择决定了智能代理必须执行的各种任务的难易程度，例如推理或规划。本研究感兴趣的表示包括各种形式的命题逻辑，从析取范式到DNNF，以及各种更强大的逻辑，如模态逻辑，某些形式的谓词逻辑和概率描述逻辑。这个建议包括一个varietyof问题和方法，统一从组合学和logic.One建议的工作的主要目标是推进重要的知识表示形式主义的几个方面的主题。这包括回答有关基本形式主义（如析取范式和决策树）以及最近形式主义（如DNNFs）的表达性问题。它还包括确定处理不同形式主义的异常的复杂性，这既是一个实际问题，也与表示的有效可学习性的一些问题密切相关。拟议的工作将包括一个重要的霍恩近似推理技术的概率分析，以确定情况时，该方法可以预期有效地工作，尽管例子演示其最坏情况下的行为，并分析了将知识库编译成更有效的形式的可能性，该形式具有对其结果的简短解析证明。该项目的另一个目标是获得更好的将不同知识表示形式主义的可学习性方面整合到新兴的知识表示比较理论中。这条研究路线包括在老的、建立良好的问题上取得新的进展，如学习Horn句子，对最近引入的问题的进一步研究，如revisingHorn句子，以及从可学习性的角度探索尚未研究的表征，如模态逻辑。工作也提出了排斥维度，一个有前途的最近的概念，在命题和谓词logic.Intellectual优点：该建议解决了几个关键问题，在知识representationand学习：表达能力，有效的操作，有效的推理，有效的学习和revision，在命题，谓词和模态逻辑。该提案建立在提案者先前的研究成果之上，其中包括开发逻辑学习和理论修订的新方法，以及他们在计算学习理论，计算复杂性理论，组合学和逻辑方面的技术专长，从而全面，深入研究人工智能的核心问题领域，强调不同方面之间的相互作用。建议者在几个建议的研究方向上取得了初步成果。更广泛的影响：数据量和固有复杂性的快速增长大大增加了表达性知识表示形式的重要性，这些形式适合于有效的操作，推理，自动获取和修订。基于命题逻辑、谓词逻辑、模态逻辑等的符号知识表示形式是大量应用中不可缺少的组成部分。了解这些应用程序的复杂性和障碍，并确定绕过它们的可能途径，是进一步开发的关键组成部分。