Jan, 2014

使用回溯搜索解决 #SAT 和贝叶斯推断

PDF
TL;DR使用简单的记忆化方案可以将标准回溯搜索与最先进的精确算法相混合，以更好的时间复杂度解决任何 sum-of-products 问题，并且具有最佳的时间空间权衡，并且这种方法可以实现其他标准算法的指数加速，适用于各种类型的 sum-of-product 问题，已有多项研究验证了其性能优势。
bayes netspropositional formulasum-of-productsbacktracking searchtime-space tradeoff
发现论文，激发创造
  • 应用贝叶斯方法解决困难的计算问题

    本文提出了一个利用贝叶斯模型为决策性控制搜索和推理算法提供通用框架的方法，并通过结构化约束满足问题的一种难类任务，演示了该方法的应用。本文进一步探讨了如何通过学习贝叶斯模型来创建动态截止策略，以及在哪些情况下动态重启策略能够超越理论上最优的固定策略。

    Jan, 2013

  • 和积定理：可学习可计算模型的基础

    文章介绍了将 sum-product networks 扩展到更广泛的学习问题并确保可解，同时应用于结构化预测问题上取得了很好的效果，实验表明模型学习的可行性和广泛性。

    Nov, 2016

  • 关于在 SAT 中使用后门的加密攻击

    本文提出一种新的 SAT 后门集类别，用于密码攻击中的猜测和确定攻击，通过使用 SAT 求解器识别最佳的后门变量集以及统计预估硬度，实验结果显示该方法较现有技术在反推攻击的硬度方面具有优势。

    Mar, 2018

  • Sum-Product Networks 与贝叶斯网络之间的关系

    本文研究和探讨了和 Sum-Product Networks 有关的 Bayesian Networks 的理论联系，并给出了使用 Algebraic Decision Diagrams 来表示和转换 SPN 为 BN 的一个线性时间和空间复杂度的算法。同时，用 Variable Elimination 算法来恢复原始的 SPN，并且介绍了 SPN 的深度和对应的 BN 树宽的下界之间的联系。

    Jan, 2015

  • 自顶向下的贝叶斯后验抽样在和积网络中的应用

    通过导出一种新的 Gibbs 采样的全部条件概率，通过边际化多个随机变量来快速获得后验分布，我们提出了一种可用于大规模 sum-product networks 的贝叶斯学习方法，同时还提出了一种超参数调优方法，通过在大规模 sum-product networks 中平衡先验分布的多样性和优化效率，改进了学习时间复杂度，并在超过 20 个数据集的数值实验中展示出了十倍到一百倍以上的计算速度和优秀的预测性能。

    Jun, 2024

  • 非连续逻辑程序的回归正常

    研究了如何利用命题可满足性 (SAT) 解决比 NP 或 co-NP 更困难的问题，特别是对命题析取答案集编程中的基本推理问题进行探讨，介绍了利用新的 Parameterized Complexity 技术从 Brave 和 Skeptical Reasoning 转换到 SAT 的方法。

    Jan, 2013

  • 用概率方法扩展机器学习以解决组合优化问题的隐蔽博弈

    应用深度学习解决困难的组合问题具有巨大的潜力。该研究侧重于布尔可满足性（SAT）问题，并通过基本的概率方法消除了由于训练集仅限于小于实际问题规模几个数量级的随机公式导致的难题。使用我们的生成器，我们对现有的最先进模型进行训练，以预测具有 10,000 个变量的公式的可满足性，提出了新的分类器，可以对大多数困难水平的相同数据集进行显着改进，从而打破了过去基于公式的句法特征学习的方法，并使用求解器计算的简短前缀进行学习。

    Nov, 2022

  • Survey propagation: 一种可满足性问题的算法

    本研究介绍了一种新的消息传递算法，可有效找到困难区域内变量的满足性分配，并应用于随机生成的具有一定数量的变量、布尔运算和公式的问题中，问题的困难程度与解决思路中 “聚类” 现象相关

    Dec, 2002

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

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

    Jan, 2014

  • 使用系统搜索精确解决 MAP 问题

    该论文介绍了一种新的、简单的 MAP 解的概率上限，并使用该上限提出了一种分支定界搜索算法，能够准确高效地解决一些网络的 MAP 问题，这些网络的约束树宽度超过了 40。

    Oct, 2012