本文研究了解析式权重一阶模型计数问题的 Lifted Inference 问题,通过提供一些结论,针对解析式的约束进行了分析讨论,并探讨了在对称概率性数据库中采用 Lifted Inference 的局限性和复杂性。
May, 2014
本文介绍了一种新的 lifted interpretations 工具,用于重构 Beame et al. 提出的多项式时间 FOMC 的闭合式公式,并将其扩展以涵盖基数约束、存在量词和计数量词(C2),同时仍然保持 domain-liftability。最后,我们展示了所获得的闭合形式促进了一种权重函数家族的自然定义,严格大于对称权重函数。
Oct, 2021
该论文研究的是加权一阶模型计数问题 (WFOMC),主要关注于能够在多项式时间内进行 WFOMC 的逻辑片段,其中包括经过拓展的两变量一阶逻辑碎片及其衍生的包含计数量词的逻辑碎片,通过在关系上添加定向无环图 (DAG) 公理,这篇论文对子领域进行了扩展。
Feb, 2023
本文研究了在统计关系学中用于概率推断的加权一阶模型计数(WFOMC)任务,并证明了添加线性序公理后,WFOMC 仍可以在多项式时间内计算。作者提出了一种基于动态规划的新算法,可以在多项式时间内计算带有线性序的 WFOMC。
Nov, 2022
据我们展开的 C² 的领域扩展,任何 C² 句子在其关系受限于表示有向无环图、连通图、树(或有向树)、森林(或有向森林)时仍保持领域可提升,这提供了一个计算组合结构的通用框架。
Aug, 2023
本文介绍了一种新的方法,使用黑箱预言机,通过 NP-Oracle 实际求解带权重赋值的模型计数问题和分布感知的满足分配的抽样问题,从而在中等规模的问题上获得了强大的理论保证。
Apr, 2014
介绍了代数模型计数(AMC),它是对半环结构加权模型计数(WMC)的推广。研究表明,AMC 泛化了众多领域的很多任务如概率推理,软限制和网络和数据库分析。此外,该研究还从知识编译角度研究了 AMC,并表明所有的 AMC 任务都可以使用 sd-DNNF 电路来评估。
Nov, 2012
该研究将 Van den Broeck 等人关于加权第一阶模型计数在一阶逻辑中的多项式解法扩展到同时带有计数量词的两变量片段,探究其时间复杂度。
Jul, 2020
在本文中,我们研究了对称加权有限模型计数问题的复杂性,旨在解决知识库推理中的软约束问题。我们证明了特定情况下该问题的数据复杂度可在多项式时间内计算,但在一般情况下该问题在 #P 中是完全的复杂度。
Dec, 2014
基于动态规划算法框架 ADD,我们提出了一种加权伪布尔计数工具 PBCounter 来对伪布尔公式进行加权模型计数,并且通过与基于 CNF 公式的模型计数工具进行实验比较,结果显示 PBCounter 在 CNF 公式上具有更好的性能。
Dec, 2023