Complexity Aspects of Knowledge Representation and 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.