Jul, 2017

使用简短的异或实现概率模型计数

PDF
TL;DR该研究论文探讨了如何通过增加短的随机奇偶约束来计算公式满足的真实赋值（模型），实现 NP 问题的计数，尤其是当需要添加多个约束时，随机奇偶约束的集合解的几何结构类似于纠错编码，得到了严格的数学保证。
发现论文，激发创造
  • 缩小模型计数中短 XOR 和长 XOR 之间的差距

    提供了一种计算近似模型计数的算法，要求对奇偶约束的渐近长度进行匹配的必要和充分条件，并提供了一系列新的下限和上限来计算任意短的 XOR 约束的模型计数，在统计中有很好的应用。

    Dec, 2015

  • 稀疏哈希用于可扩展近似模型计数的理论与实践

    本文介绍了一种使用浓缩哈希算法来加速模型计数问题的近似计数算法，实验结果表明使用浓缩哈希算法可以显著提高算法的速度。

    Apr, 2020

  • 通过字级计数进行概率近似推断

    该研究提出了一种基于单词级哈希函数的模型计数方法，可以直接利用复杂的 SMT 求解器，为概率推理中的计数问题提供了新思路。

    Nov, 2015

  • 构建精确的伪布尔模型计数器

    我们提出了第一个准确的伪布尔模型计数器 PBCount，它通过代数决策图的知识编译方法来实现。我们的实证评估表明，PBCount 可以计算 1513 个实例的计数，而当前最先进的方法只能处理 1013 个实例。我们的工作为进一步研究伪布尔公式的模型计数提供了几个方向，如预处理技术的开发和除知识编译之外的其他方法的探索。

    Dec, 2023

  • 正式验证的近似模型计数

    我们提出了第一个近似模型计数的认证框架，并且证明了其输出近似值的质量保证。

    Jun, 2024

  • 稳定模型计数及其在概率逻辑编程中的应用

    本文研究了使用稳定模型语义进行推理的问题，提出了两种基于未建立的集合检测的实现技术，扩展了命题模型计数器到稳定模型计数器，可以在时间和空间使用方面显著优于现有的解决方案。

    Nov, 2014

  • 投影模型计数

    本文介绍了优先变量，非优先变量，以及计算仅涉及优先变量的模型计数问题，探讨了三种不同的计数方法，并在多组实验结果上进行了比较。

    Jul, 2015

  • SMT 中的近似计数和概率程序的值估计

    本篇论文介绍了一种从 SMT 到 #SMT 近似版本的约简方法，并提出了关于整数算术和线性实数算术的模型计数算法，通过对现代 SMT 求解器的高级启发式算法进行利用，运行时间为多项式级别并提供正式边界。我们使用这些算法来解决带有非确定性的无循环概率程序模型的值问题。

    Nov, 2014

  • 可扩展的近似模型计数器

    介绍了一种基于 SAT 求解器的算法和实现工具，用于处理大规模的 CNF 公式的近似计数问题。通过多项式调用的方式，能够高精度地估算满足条件的解数，同时针对过大的问题仍能提供高置信度的估算边界。

    Jun, 2013

  • 解决符号与统计人工智能集成的可证明保证下的可满足性模数计数

    通过使用 XOR-SMC，我们提出了一种多项式算法，用于解决高度棘手的 SMC 问题，该算法具有恒定近似保证，并通过将 SMC 中的模型计数替换为受随机 XOR 约束的 SAT 公式，将高度棘手的 SMC 转化为可满足性问题。我们在 AI 有益于社会的重要 SMC 问题的求解实验中展示了 XOR-SMC，它找到了接近真实最优解的解决方案，胜过了几个难以找到可靠逼近 SMC 中棘手模型计数的基线方法。

    Sep, 2023