AAAIJul, 2014

使用 FODD 和 GFODD 进行推理的复杂性

PDF
TL;DR本文研究可决策的关系领域中采用广义一阶决策图（GFODD）的启发式推理算法，在假设预期模型的大小为已知时，证明 GFODD 的计算问题可在多项式函数层次内解决。
generalized first order decision diagramscomputational complexitydecision theoretic planningexistential quantificationuniversal quantification
发现论文，激发创造
  • 关系马尔可夫决策过程的一阶决策图

    研究证明，使用新的紧凑表示 ——FODD，可以解决 RMDPs，通过 FODDs 操作开发价值迭代算法，并证明该算法完全收敛且具有独立于领域大小或实例化的最佳策略。

    Oct, 2011

  • FO (FD)：使用基于规则的不动点定义扩展经典逻辑

    介绍了货值点定义 —— 一种基于规则的货值点重构。定义了 FO（FD）逻辑，它是一种扩展了经典逻辑的逻辑。探讨了 FO（FD）的可满足性问题。将 FO (FD) 简化为区别逻辑，然后使用区别逻辑求解器。在计算代表公平条件的 FO (FD) 理论的模型的过程中，评估了这些缩减，并提供了 FO (FD) 的潜在应用。

    Jul, 2010

  • 句子决策图的相对简洁性

    本文旨在确定哪些布尔函数可以由小型的 SDDs 表示，同时将多项式大小的布尔函数表示集合与来自 Darwiche 和 Marquis 经典知识编译地图的表示类型进行比较。最主要的结果是通过等效的不明确的非确定性 OBDDs 对 SDDs 进行准多项式仿真，回答了 SDDs 和超过 OBDDs 的 FBDDs 相对简洁性之间的一个开放问题。

    Feb, 2018

  • 知识图谱上存在性一阶查询的推理

    这篇论文通过系统检视问题之前的范围并提出一个新的数据集，讨论了同时出现的新挑战，并提出了一种模糊逻辑理论的新搜索算法，以解决新的公式并在现有公式中胜过以前的方法。

    Apr, 2023

  • 基于 EFO_k 的 CQA：超越集合操作的知识图谱复杂查询响应

    为了回答知识图谱上的复杂查询，我们提出了一个综合框架，涵盖了存在性一阶查询的组合空间，并构建了一个 dataset 进行评估。我们的结果揭示了查询难度对结果的影响，并强调了现有数据集构建过程中的系统偏见对查询 - 回答方法的适当发展的重要性。

    Jul, 2023

  • 关于概率和因果推理的困难程度

    研究员从计算复杂性的角度出发，研究了能够完全表达数量化概率推理和因果效应的形式语言。研究集中于可表达许多概率和因果推断任务的可满足性问题，并建立了这些可满足性问题的确切计算复杂性。研究结果表明，一些在概率和因果推断中常用的标准语言的变体的算法限制更强。

    May, 2023

  • 一阶逻辑双变量片段中的精确采样

    本文研究了最近由 Wang 等人提出的一阶逻辑采样问题 —— 如何在有限域上高效地采样给定一阶句子的模型？我们将他们对于双变量逻辑 FO^2 的普遍量化子片段 UFO^2 的结果扩展到整个 FO^2 片段。具体来说，我们证明了 FO^2 在采样下的域可扩展性，即存在一种能在域大小多项式时间下运行的 FO^2 采样算法。然后，我们进一步表明，即使存在像所有 x 存在 = ky: φ（x，y）和存在 = kx 为所有 y 的数量约束，如 φ（x，y）的量化器公式，我们的方法也可以保持运作。我们的提出的方法是具有建设性的，由此产生的采样算法在各个领域都有潜在的应用，包括在组合结构和统计关系模型的均匀生成方面以及如 Markov 逻辑网络和概率逻辑程序的采样方面。

    Feb, 2023

  • 本体概念的计量和聚合

    该论文描述了一种扩展一阶逻辑的方法，使方案更加容易修改，并引入了一个保护机制来保证公式的正确性，同时将该方案应用于四个不同问题领域的知识表示中。

    Feb, 2022

  • 基于理论的规范决策图

    决策图是一种有效表达命题公式的强大工具，本文介绍了一种通用技术将决策图应用于 SMT 级别，并可产生理论规范的 T-DD，从而解决了现有技术的一些限制。

    Apr, 2024

  • FO 和 FO (ID) 的限制性推理

    本文介绍了一种自动计算和添加语义冗余信息的方法，来简化撰写能够有效进行推理的输入理论的任务。首先介绍了该方法用于经典一阶逻辑（FO）理论，然后扩展到带归纳定义的 FO（ID），并且讨论了实现问题并验证了该方法的实际适用性。

    Jan, 2014