Feb, 2023

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

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

    本研究将 van den Broeck 等人最近的对第二阶逻辑 FO2 下的对称加权一阶模型计数问题 (WFOMC) 多项式时间可解性证明，扩展到了两个独立方向：格式为 “phi 和∀∃^=1 psi” 的 FO2 句子以及在 FO 的一维均匀片段中构造的语句。同时，我们也鉴定了一阶前缀类的完整分类，以表明 WFOMC 在多项式时间或 Sharp-P_1 完备性之间的区别。

    Apr, 2018

  • 带计数量词的二元分片的加权一阶模型计数

    该研究将 Van den Broeck 等人关于加权第一阶模型计数在一阶逻辑中的多项式解法扩展到同时带有计数量词的两变量片段，探究其时间复杂度。

    Jul, 2020

  • 线性序公理的提升推理

    本文研究了在统计关系学中用于概率推断的加权一阶模型计数（WFOMC）任务，并证明了添加线性序公理后，WFOMC 仍可以在多项式时间内计算。作者提出了一种基于动态规划的新算法，可以在多项式时间内计算带有线性序的 WFOMC。

    Nov, 2022

  • 超越一阶逻辑的提升推理

    据我们展开的 C² 的领域扩展，任何 C² 句子在其关系受限于表示有向无环图、连通图、树（或有向树）、森林（或有向森林）时仍保持领域可提升，这提供了一个计算组合结构的通用框架。

    Aug, 2023

  • 概率逻辑编程的升级变量消除

    本文提出 LP$^2$ 算法来解决概率逻辑编程中的查询问题。LP$^2$ 是通过将 Generalized Counting First Order Variable Elimination (GC-FOVE) 转换为 Prolog Factor Language (PFL) 实现的，并增加了两个新的操作符来处理异构因子。结果表明该方法有潜力超过 PITA 和 ProbLog2。

    May, 2014

  • 对称加权一阶模型采样的提升算法

    证明了一种高效的采样算法，解决了带有计数量词的一阶逻辑的两个变量片段的权重模型采样在多项式时间内可行的问题。

    Aug, 2023

  • 概率定理证明

    该论文提出了一种将概率论和第一阶逻辑相结合的方法，在有限域内具有 Herbrand 解释的情况下，定义了概率证明定理及其推广问题，然后提出了能够同时拥有图模型推理和一阶定理证明的完整能力的方法，并开发了一种高效算法。实验表明，当逻辑结构存在时，该算法远优于目前已有的方法。

    Feb, 2012

  • 术语模态逻辑的双变量片段

    本篇论文研究了 Term Modal Logics 中的两个变量，并证明了该领域中的一个有趣分支的可决定性，与两个变量的一阶模态逻辑不同，后者是不可判定的。

    Apr, 2019

  • 带计数量词的双变量片段的数据复杂度

    对于带计数的两变量片段的可满足性和有限可满足性问题的数据复杂度为 NP - 完全；对于带计数的两变量受限片段的查询回答和有限查询回答问题的数据复杂度为 co-NP - 完全。

    Jun, 2008

  • 带基数约束和计数量词的 FO2 加权模型计数：一个封闭式公式

    本文介绍了一种新的 lifted interpretations 工具，用于重构 Beame et al. 提出的多项式时间 FOMC 的闭合式公式，并将其扩展以涵盖基数约束、存在量词和计数量词（C2），同时仍然保持 domain-liftability。最后，我们展示了所获得的闭合形式促进了一种权重函数家族的自然定义，严格大于对称权重函数。

    Oct, 2021