Apr, 2020

稀疏约束下的贝叶斯网络学习：参数化复杂度分析

PDF
TL;DR本文研究在给定的约束条件下，学习最优贝叶斯网络的结构，其中最大程度为 1 的边界至少有距离 k，最大程度为 2 的边界以及具有大小至多为 c（c≥3）的连通分量的网络或其模糊化图的学习被证明是 NP 困难的，而在模糊化图中最多具有 k 个弧可以在两个范围内得到解决：O (k)*|I | 或 2^O (k)*|I|。
bayesian networkgraph theorypolynomial timenp-hardarc
发现论文，激发创造
  • 基于结构的约束学习马尔可夫网络

    用约束条件的结构学习方法学习马尔可夫网络的理论限制与性能逐渐变好，并且对条件独立性测试的集合大小和测试数量进行了研究。

    Mar, 2024

  • 稀疏性和拉普拉斯约束下的网络拓扑推断

    通过利用 Laplacian 约束的高斯图模型解决网络拓扑推断问题，我们将任务重塑为估计一个图拉普拉斯形式的精度矩阵。通过在此模型中检验广泛使用的 l₁范数的局限性，我们发现正则化参数的增大会导致解中非零条目的数量增加，理论上，大的正则化参数会导致完全连接（最密）的图。为了克服这些挑战，我们提出了一种图拉普拉斯估计方法，结合了 l₀范数约束。我们开发了一个高效的梯度投影算法来解决由稀疏性和拉普拉斯约束所特征化的优化问题。通过对合成和金融时间序列数据集进行数值实验证明了所提方法在网络拓扑推断中的有效性。

    Sep, 2023

  • 基于最稀疏排列的有向无环图学习

    该研究提出了一种新的基于分数的算法（SP 算法）来学习贝叶斯网络或有向无环图（DAG）模型，该算法在弱于忠实性假设的条件下具有一致性保证，并且在一些小 DAG 的模拟中表现出与其他算法相比的优越性。

    Jul, 2013

  • 贝叶斯网络的大样本学习是 NP 难的

    本文研究从数据中学习离散变量贝叶斯网络的算法的复杂度结果，结果表明即使具有独立性、推理或信息神谕，识别高得分的结构也很困难，负面结果也适用于每个节点最多有 K 个父母的离散变量贝叶斯网络，其中 k > 3。

    Oct, 2012

  • 凹惩罚估计稀疏高斯贝叶斯网络

    本文提出了一种基于得分的结构学习快速算法的罚似然估计框架，该快速算法不受限制地处理高维数据集，并使用凹规则化以解决估计问题的固有不可识别性。其中，高斯贝叶斯网络是重点研究领域之一。

    Jan, 2014

  • 深度网络剪枝的几何视角：有多稀疏可以剪枝？

    本文研究了深度神经网络的过度参数化问题，提出了一种全局一次性网络剪枝算法，并通过计算高维几何中的正交宽度来确定剪枝比率的相变点，该值等于基于 $l_1$ 正则化损失函数的某个凸体的平方高斯宽度除以参数的原始维度。

    Jun, 2023

  • 关于稀疏性和 DAG 约束在学习线性 DAG 中的作用

    通过研究稀疏性和 DAG 约束的渐近作用，提出了一种基于类似似然函数的求解 DAG 约束的无约束优化方法，该方法能够在处理成千上万个节点时仍然保持高精度。实验证明，该方法比使用最小二乘法和硬 DAG 约束的方法更加有效。

    Jun, 2020

  • SparsityBoost: 一种新的评分函数用于学习贝叶斯网络结构

    本文提出了一种新的一致性结构学习评分函数，与传统方法相比，该评分函数具有数据相关性且随着数据量的增加而变得更易于最大化，使用线性规划松弛方法时效果特别好，可学习与生成分布接近且没有错误边的结构。

    Sep, 2013

  • 联合边模型稀疏学习对于图神经网络的可证明效率

    本文从样本复杂度和收敛速率的角度，首次提供了从联合边缘 - 模型稀疏学习的理论特性，证明了重要节点抽样和低幅度神经元剪枝可以减少样本复杂度，提高收敛速度，而不影响测试精度。

    Feb, 2023

  • 使用贪心搜索从大数据中学习贝叶斯网络：计算复杂度和高效实现

    本研究探讨了大数据环境下的贝叶斯网络结构学习问题，提出了使用预测性好坏拟合评分来加速贝叶斯网络学习的方法，并在环境和流行病学数据以及公共数据集上验证了其准确性。

    Apr, 2018