课题基金 / 基金详情

Complexity Aspects of Knowledge Representation and Learning

Complexity Aspects of Knowledge Representation and Learning
知识表示和学习的复杂性
批准号:
0431059
负责人:
Robert Sloan
金额:
$0.0万
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
2004
资助国家:
美国
项目状态:
已结题
起止时间:
2004-09-15 至 2008-08-31

项目摘要

项目成果

Robert Sloan的其他基金

相似基金

相关文献

中文摘要
翻译
拟议的研究涉及理论计算机科学和人工智能(AI)。特别是,理论计算机科学的技术将应用于人工智能的两个重要问题领域:知识表示和机器学习。某些形式的知识表示对于人工智能应用非常重要。有些词,比如霍恩从句的连词,从人工智能的早期就被研究过;其他的,如可分解否定范式(DNNF),则相对较新。该项目将研究这些和其他形式的知识表示的计算复杂性方面,以及它们的正式可学习性结果。知识表示很有趣,因为表示的选择决定了智能代理必须执行的各种任务的难易程度,比如推理或计划。本研究感兴趣的表示包括各种形式的命题逻辑,从析取范式到DNNF,以及各种更强大的逻辑,如模态逻辑,某些形式的谓词逻辑和概率描述逻辑。该提案包括各种各样的问题和方法,由组合学和逻辑学中反复出现的主题统一起来。提出的工作的一个主要目标是促进对重要的知识表示形式的几个方面的理解。这包括回答基本形式(如析取范式和决策树)和最近的形式(如dnnf)的表达性问题。它还包括确定不同形式的异常处理的复杂性,这既是一个实际问题,也与表示的有效可学习性问题密切相关。建议的工作将包括对霍恩近似的重要推理技术的概率分析,以确定该方法可以预期有效工作的情况,尽管示例展示了其最坏情况的行为,并分析将知识库编译成更有效形式的可能性,并具有其结果的短分辨率证明。该项目的另一个目标是将不同知识表示形式的可学习性更好地整合到新兴的知识表示比较理论中。这条研究路线包括在老的、已经确立的问题上取得新进展,例如学习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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
III: Medium: Collaborative Research: Extracting and Linking AI Artifacts
  • 批准号:
    2107518
  • 项目类别:
    Continuing Grant
  • 资助金额:
    $53.0万
  • 财政年份:
    2021
  • 负责人:
    Robert Sloan
  • 依托单位:
Collaborative Research: HCC: Medium: Fine-grained Emotion Analysis in Crises
  • 批准号:
    2107487
  • 项目类别:
    Standard Grant
  • 资助金额:
    $34.76万
  • 财政年份:
    2021
  • 负责人:
    Robert Sloan
  • 依托单位:
BIGDATA: IA: Collaborative Research: Domain Adaptation Approaches for Classifying Crisis Related Data on Social Media
  • 批准号:
    1912887
  • 项目类别:
    Standard Grant
  • 资助金额:
    $39.55万
  • 财政年份:
    2018
  • 负责人:
    Robert Sloan
  • 依托单位:
CAREER: From Data to Knowledge: Extracting and Utilizing Concept Graphs in Online Environments
  • 批准号:
    1914575
  • 项目类别:
    Continuing Grant
  • 资助金额:
    $49.99万
  • 财政年份:
    2018
  • 负责人:
    Robert Sloan
  • 依托单位:
国内基金
海外基金
基于构件软件的面向可靠安全Aspects建模和一体化开发方法研究