Mar, 2017

Sum-Product Networks 的最大后验推断的近似复杂度

PDF
TL;DR探讨了在总和 - 乘积网络中近似最大后验推断的计算复杂性，证明了在高度为 2 和 3 的树状网络中，这一问题都是 NP 难问题，并提出了一种比传统算法更优秀的简单算法。
computational complexitymaximum a posteriori inferencesum-product networksapproximationalgorithm
发现论文，激发创造
  • 和积定理：可学习可计算模型的基础

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

    Nov, 2016

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

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

    Jun, 2024

  • 概率电路中边缘 MAP 的神经网络逼近器

    近似推理是通过使用神经网络来近似代表大型概率分布，该方法通过在查询变量上使用连续多线性函数来近似赋值的代价，并通过神经网络输出解决方案。本论文通过在多个基准数据集上的评估表明，该方法在求解概率电路中的最大边后验和边后验最大估计任务时优于竞争的线性时间近似方法。

    Feb, 2024

  • 分布式系统中的健壮概率推断

    本文研究了概率推断问题在分布式系统中的应用，提出了一种新的基于消息传递的算法，相较于传统的 sum-product 算法，该算法对节点故障和通信失效有更好的稳健性，且在网络拓扑复杂时具有更优的计算复杂度，并用传感器网络定标任务进行了实验验证。

    Jul, 2012

  • MAP 复杂性结果和近似方法

    本文研究了贝叶斯网络中最可信赖实例化的计算问题，证明在多种情形下该问题为 NP 完全问题，在多叉树限制下也难以有效近似，采用置信传播的局部搜索方法可提供较准确的估计。

    Dec, 2012

  • 使用和积网络学习深层高斯过程专家混合模型

    本文介绍通过将高斯过程嵌入可计算的和积网络中，实现灵活的先验函数分布，从而实现计算和内存高效、容易实施后验推理的概率回归模型。

    Sep, 2018

  • MAP 解释的复杂性结果和逼近策略

    研究了贝叶斯网络中 MAP 问题的复杂性，发现即使 MPE 和 Pr 可以轻松计算，MAP 仍然很难。为了找到一个接近最优解的算法，提出了一种通用的 MAP 近似框架，并给出了两个具体的实现，用于对那些即使 Pr 和 MPE 都难以计算的网络进行近似。实验结果表明，这些算法比标准技术提供更好的解决方案，并在许多情况下提供准确的 MAP 估计。

    Jun, 2011

  • Sum-Product Networks: 一种新的深层网络结构

    提出了一种新型深层架构 —— 求和积网络（SPN），通过学习和推理，SPNs 能够实现比标准深层网络更快和更准确的图形建模推理，例如在图像完成任务方面表现优异。

    Feb, 2012

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

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

    Jan, 2015

  • 使用增量构建 - 推断 - 近似范式进行 MPE 推断

    本文提出了一种基于增量建立 - 推断 - 近似（IBIA）框架的算法，用于近似求解贝叶斯网络中最大可能解（MPE）的推断问题，该算法无需搜索，运行时间竞争力强，可在 117 个测试基准中的 100 个得到有效结果，精度与分支限界搜索相当。

    Jun, 2022