Jan, 2014

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

PDF
TL;DR本文提出了使用两种 SAT 编码的噪声 OR 和两种编码的噪声 MAX 的技术，以提高 Bayesian 网络的精确推理。经过实验评估，我们的技术在具有噪声 OR/MAX 关系的网络中获得了最佳效果。
bayesian networksat formulaweighted model countingnoisy-ornoisy-max
发现论文，激发创造
  • SAT 问题的分布感知抽样和加权模型计数

    本文介绍了一种新的方法，使用黑箱预言机，通过 NP-Oracle 实际求解带权重赋值的模型计数问题和分布感知的满足分配的抽样问题，从而在中等规模的问题上获得了强大的理论保证。

    Apr, 2014

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

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

    Nov, 2015

  • 基于公式的概率推断

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

    Mar, 2012

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

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

    Dec, 2023

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

    该研究论文探讨了如何通过增加短的随机奇偶约束来计算公式满足的真实赋值（模型），实现 NP 问题的计数，尤其是当需要添加多个约束时，随机奇偶约束的集合解的几何结构类似于纠错编码，得到了严格的数学保证。

    Jul, 2017

  • 基于树宽限制的贝叶斯网络结构学习的 Turbocharging

    我们介绍了一种新的方法来学习结构属于树宽有限的贝叶斯网络 (Bayesian Network)。该方法的关键是局部应用基于 MaxSAT 的精确方法，以提高启发式计算 BN 的得分。我们的实验证明，我们的方法可以显著提高由最先进的启发式方法提供的 BN 的得分。

    Jun, 2020

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

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

    Apr, 2020

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

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

    Jun, 2013

  • 学习推理：利用神经网络实现近似 DNF 计数

    本文提出了一种基于神经网络模型的加权 #DNF 模型计数方法，结合了近似模型计数和深度学习，可以在线性时间内准确估算模型数目，并在大规模 #DNF 实例中表现良好。

    Apr, 2019

  • 结构感知的 SMT 加权模型集成增强

    本文介绍一种基于 SMT 枚举的新算法，通过对问题结构的有效编码避免生成冗余模型，从而实现与不同整合技术的无缝配合，可以显著扩展可以通过 WMI 技术处理的问题集，而且相比现有的解决方案具有巨大的计算优势，已在合成和真实世界数据集上进行了广泛的实验评估，并在旨在验证概率程序公平性的原型任务中展示了该技术的应用潜力。

    Feb, 2023