Apr, 2023

贝叶斯网络近似最优度数测试

PDF
TL;DR本文研究了在给定概率分布 P（{0,1}^n 上），并具有样本访问的情况下，测试潜在贝叶斯网络的最大入度的问题。研究表明，该问题的样本复杂度为 Θ(2^(n/2)/ε^2) 。我们的算法依赖于先前用于获得样本最优测试器的测试通过学习框架；为了应用该框架，我们开发了新的算法来进行 “近似适当” 的贝叶斯网络学习，并在 χ^2 差异下高概率学习，这具有独立兴趣。
bayes netprobability distributionsample complexitytesting-by-learningin-degree
发现论文，激发创造
  • 使用干预学习和测试因果模型

    本文研究了因果贝叶斯网络上的测试和学习问题，并提出了有效的算法来测试两个未知因果贝叶斯网络的相似性和学习因果贝叶斯网络。

    May, 2018

  • 测试贝叶斯网络

    本文研究了 Bayesian 网络的身份测试和相似性测试的性质，提出了第一个非平凡的高效测试算法，并给出了相应的信息理论下界，其测试样本复杂度在维度上是亚线性的，适用于各种参数设置，是样本的最优解，直到常数因子。

    Dec, 2016

  • 贝叶斯网络中稀疏假设的测试

    本文介绍了一种用于判断线性贝叶斯网络最大入度是否大于 1 的假设检验方法，并提出了一种基于该方法的结构发现工作流程。通过对模拟数据和人体银屑病研究数据的实验验证，证明该方法的有效性和可行性。

    Jul, 2023

  • 贝叶斯线性贝叶斯网络

    该研究提出了第一个用于学习高维线性贝叶斯网络的贝叶斯方法，该方法通过反向逐步估计拓扑排序的每个元素及其父节点，使用了偏差协方差矩阵的逆。当应用于具有不等收缩的逆协方差矩阵的贝叶斯正则化时，该方法成功恢复了底层结构。具体来说，该方法表明样本数 n = Ω(d_M^2logp) 和 n = Ω(d_M^2p^{2/m}) 足以让该算法学习具有亚高斯和 4m 阶有界矩的线性贝叶斯网络，其中 p 是节点数，d_M 是道德化图的最大度数。理论发现得到了包括真实数据分析在内的大量模拟研究的支持。此外，该方法在合成数据中表现出优于 BHLSM、LISTEN 和 TD 等频频方法的性能。

    Nov, 2023

  • 学习贝叶斯网络的样本复杂度

    研究使用最小描述长度（MDL）原则基于样本复杂性学习贝叶斯网络，并提出了使用样本复杂性结果加速学习过程的方法，同时表明了以熵距离为误差阈值的 epsilon-close 近似所需样本数量是 O ((1/epsilon)^(4/3) log (1/epsilon) log (1/delta) loglog (1/delta))。

    Feb, 2013

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

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

    Oct, 2012

  • 贝叶斯网络中精确贝叶斯结构发现的进展

    本文介绍了一种贝叶斯方法用于从完整数据中学习贝叶斯网络结构，并使用前向 - 后向技术和快速莫比乌斯变换算法实现了对所有潜在边缘后验概率的计算，从而加速了学习中等大小网络的统计能力的实验研究。

    Jun, 2012

  • 高概率离散分布的最佳测试

    研究总变差距离下的离散分布测试问题，提出可用于样本较高概率区域的属性测试的算法，包括相应参数的样本复杂度与正确性保障。

    Sep, 2020

  • 测试图的聚类结构

    在有界度模型的性质测试框架中研究了识别图的集群结构问题，提出了一个亚线性算法，可识别由参数 k, phi, epsilon 制定的 (d) 有界度图，并且是渐近最优的，关键是集群内外的 conductance。

    Apr, 2015

  • 带有增长度数的随机块模型的最优假设检验

    研究在平均度数与图像增长的渐近情况下，将 Erdos-Renyi 随机图模型与随机块模型进行比较的方案和方法，提出了一种线性谱统计的新方法，并构建了一系列准确的测试统计量和一类自适应测试来解决假设检验问题。

    May, 2017