通过字级计数进行概率近似推断
本文探讨了一种利用通用哈希和 SAT 求解器的方法,可以在不牺牲正确性保证的同时,处理具有数十万个变量的公式,解决了人工智能中受限采样和计数的两个基本问题,这对于概率推理及规划,约束随机验证等方面有着广泛应用,并探讨一些需要解决的挑战。
Dec, 2015
本文研究了命题模型计数问题,针对约束条件表达式分别为 DNF 公式和 CNF 公式分别介绍了 Monte Carlo 和基于哈希的计数技术,并提出了两种新算法技术:Symbolic Hashing 和 Stochastic Cell Counting,通过设计基于哈希的 FPRAS for DNF counting 提高了效率和应用价值。
Oct, 2017
该研究论文探讨了如何通过增加短的随机奇偶约束来计算公式满足的真实赋值(模型),实现 NP 问题的计数,尤其是当需要添加多个约束时,随机奇偶约束的集合解的几何结构类似于纠错编码,得到了严格的数学保证。
Jul, 2017
本篇论文介绍了一种从 SMT 到 #SMT 近似版本的约简方法,并提出了关于整数算术和线性实数算术的模型计数算法,通过对现代 SMT 求解器的高级启发式算法进行利用,运行时间为多项式级别并提供正式边界。我们使用这些算法来解决带有非确定性的无循环概率程序模型的值问题。
Nov, 2014
我们提出了第一个准确的伪布尔模型计数器 PBCount,它通过代数决策图的知识编译方法来实现。我们的实证评估表明,PBCount 可以计算 1513 个实例的计数,而当前最先进的方法只能处理 1013 个实例。我们的工作为进一步研究伪布尔公式的模型计数提供了几个方向,如预处理技术的开发和除知识编译之外的其他方法的探索。
Dec, 2023
本文提出了精确算法和近似算法,以及相应的公式分解和条件概率以及基于模型计数的概率推断方法,并展示了其在实验中的实际有效性,特别是相比于最先进方案,本文提出的算法可以利用公式结构信息大大提高效率。
Mar, 2012
介绍了一种基于 SAT 求解器的算法和实现工具,用于处理大规模的 CNF 公式的近似计数问题。通过多项式调用的方式,能够高精度地估算满足条件的解数,同时针对过大的问题仍能提供高置信度的估算边界。
Jun, 2013
本文研究了使用稳定模型语义进行推理的问题,提出了两种基于未建立的集合检测的实现技术,扩展了命题模型计数器到稳定模型计数器,可以在时间和空间使用方面显著优于现有的解决方案。
Nov, 2014
提供了一种计算近似模型计数的算法,要求对奇偶约束的渐近长度进行匹配的必要和充分条件,并提供了一系列新的下限和上限来计算任意短的 XOR 约束的模型计数,在统计中有很好的应用。
Dec, 2015