Complexity analysis of Bayesian learning of high-dimensional DAG models and their equivalence classes
高维有向无环图模型及其等价类的贝叶斯学习复杂度AI 解读 ↓
← 返回论文列表与筛选
阅读说明
本页整理公开书目信息，不生成学术质量评分。AI 解读根据题名及所注明的摘要或原文片段生成，未完成全文核验，可能有误；具体假设、证明与结论请核对原文。摘要保留来源文本，未经模型改写。
DOI 首次登记不等于接收或发表日期。部分更正、评论等条目没有独立摘要；缺少可靠材料时保留待补状态。
引用量采用 OpenAlex 单条关联记录，不合计多个记录；关联记录可能包含正式发表版本，不等于此版本单独引用。缺失不视为零，引用指标不代表论文质量。
关注作者按书目中的完整姓名匹配，同名和姓名变体需人工辨别。相关论文先按共享细分方向和具体方法排列，再参考通用方法与发表日期。
分类依据与纠错
AI 根据所提供的论文材料归类：摘要研究统计图模型的结构学习，未明确经济网络、干扰效应或因果识别，故不强行分类。
反馈分类问题
正在核对关联版本…
代码、数据与补充材料
正在核对对应版本的资源…
关注这篇论文的作者
高维有向无环图模型及其等价类的贝叶斯学习复杂度
- 研究问题
- 面对巨大的图结构搜索空间和 Markov 等价图，如何刻画贝叶斯结构学习的 MCMC 混合速度及高维计算复杂度？
- 方法与思路
- 作者分析随机游走 Metropolis–Hastings 算法，建立有限状态空间混合时间界，并在度数受限的等价类空间构造高概率搜索路径。
- 材料陈述的贡献
- 摘要称，在一定高维条件下算法快速混合，复杂度随样本量和维数多项式增长，并获得经验贝叶斯结构选择的强一致性。
- 阅读关注点
- 核对稀疏性、节点度数和其他高维条件，等价类上的提议机制，以及快速混合、一致性和复杂度结论的适用范围。
- 阅读边界
- 来源为稿件版本未注明的 OpenAlex 索引摘要；条件、混合界和复杂度次数未说明，图结构学习也不能自动解释为因果识别。
原文摘要
Structure learning via MCMC sampling is known to be very challenging because of the enormous search space and the existence of Markov equivalent DAGs. Theoretical results on the mixing behavior are lacking. In this work, we prove the rapid mixing of a random walk Metropolis–Hastings algorithm, which reveals that the complexity of Bayesian learning of sparse equivalence classes grows only polynomially in n and p, under some high-dimensional assumptions. A series of high-dimensional consistency results is obtained, including the strong selection consistency of an empirical Bayes model for structure learning. Our proof is based on two new results. First, we derive a general mixing time bound on finite-state spaces, which can be applied to local MCMC schemes for other model selection problems. Second, we construct high-probability search paths on the space of equivalence classes with node degree constraints by proving a combinatorial property of DAG comparisons. Simulation studies on the proposed MCMC sampler are conducted to illustrate the main theoretical findings.