AAAIApr, 2014

SAT 问题的分布感知抽样和加权模型计数

PDF
TL;DR本文介绍了一种新的方法，使用黑箱预言机，通过 NP-Oracle 实际求解带权重赋值的模型计数问题和分布感知的满足分配的抽样问题，从而在中等规模的问题上获得了强大的理论保证。
weighted model countingdistribution-aware samplingapproximate algorithmsblack-box oracletheoretical guarantees
发现论文，激发创造
  • 约束采样与计数：通用哈希遇见 SAT 求解

    本文探讨了一种利用通用哈希和 SAT 求解器的方法，可以在不牺牲正确性保证的同时，处理具有数十万个变量的公式，解决了人工智能中受限采样和计数的两个基本问题，这对于概率推理及规划，约束随机验证等方面有着广泛应用，并探讨一些需要解决的挑战。

    Dec, 2015

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

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

    Aug, 2023

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

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

    Apr, 2020

  • 利用加权模型计数中的结构进行概率推断

    本文提出了使用两种 SAT 编码的噪声 OR 和两种编码的噪声 MAX 的技术，以提高 Bayesian 网络的精确推理。经过实验评估，我们的技术在具有噪声 OR/MAX 关系的网络中获得了最佳效果。

    Jan, 2014

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

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

    Jun, 2013

  • 布尔可满足性问题的抽样技术

    提出使用有限独立哈希的新方法来解决 boolean satisfiability 问题，并基于此方法设计了两个实用算法：一个近似均匀生成器和一个可扩展的近似模型计数器，该方法具有强大的理论保证和可扩展性，可适用于不同的应用领域。

    Apr, 2014

  • 基于公式的概率推断

    本文提出了精确算法和近似算法，以及相应的公式分解和条件概率以及基于模型计数的概率推断方法，并展示了其在实验中的实际有效性，特别是相比于最先进方案，本文提出的算法可以利用公式结构信息大大提高效率。

    Mar, 2012

  • PBCounter: 伪布尔公式上的加权模型计数

    基于动态规划算法框架 ADD，我们提出了一种加权伪布尔计数工具 PBCounter 来对伪布尔公式进行加权模型计数，并且通过与基于 CNF 公式的模型计数工具进行实验比较，结果显示 PBCounter 在 CNF 公式上具有更好的性能。

    Dec, 2023

  • 基于代数决策图的加权模型计数

    使用动态规划算法和代数决策图作为主要数据结构来计算布尔公式的精确文字加权模型计数，并将该方法实现在 ADDMC 中，通过在 1914 个标准模型计数基准测试中的比较，展示 ADDMC 在加权模型计数上显著优于现有最佳的求解器。

    Jul, 2019

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

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

    Nov, 2015