论文标题
用于计数和采样马尔可夫等效的多项式时间算法与应用
Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications
论文作者
论文摘要
来自马尔可夫等效类的计数和采样定向的无环图是图形因果分析中的基本任务。在本文中，我们表明可以在多项式时间内执行这些任务，从而解决该领域的长期开放问题。我们的算法是有效的，易于实现。正如我们在实验中所显示的那样，这些突破使人们对因果关系结构的积极学习和因果关系识别而言是马尔可夫等效类别实际上适用的因果效应识别。
Counting and sampling directed acyclic graphs from a Markov equivalence class are fundamental tasks in graphical causal analysis. In this paper we show that these tasks can be performed in polynomial time, solving a long-standing open problem in this area. Our algorithms are effective and easily implementable. As we show in experiments, these breakthroughs make thought-to-be-infeasible strategies in active learning of causal structures and causal effect identification with regard to a Markov equivalence class practically applicable.
