AAAIMay, 2022

计算与取样马尔可夫等价有向无环图的多项式时间算法及其应用

PDF
TL;DR本文提出了一种能够在多项式时间内计数和抽样来自马尔可夫等价类的有向无环图的算法，解决了该领域长期存在的一个问题。通过实验实现，该算法应用价值高，使因果结构和因果效应识别的主动学习策略变得实用。
directed acyclic graphsmarkov equivalence classpolynomial timecausal analysisactive learning
发现论文，激发创造
  • 计算和抽样马尔科夫等效有向无环图的多项式时间算法

    本文解决了图形因果分析领域中的一个长期存在的难题，即如何在多项式时间内计数和均匀采样来自马尔可夫等价类的有向无环图（DAGs）。我们提出的算法实现容易且高效，并且实验结果表明这些算法显著优于现有的最先进方法。

    Dec, 2020

  • 利用团树从马尔可夫等效有向无环图中计数和采样

    本文提出了一种用于计算标记等价类中 DAG 数量的技术，并显示在有限制图案下，所提出的算法是多项式时间的。此技术可用于均匀采样来枚举等价类中的 DAG，并可用于因果实验设计和估计联合干预的因果效应。

    Feb, 2018

  • 计算与背景知识相一致的马尔可夫等价有向无环图数量

    本文研究的问题是，在部分边缘方向已知的情况下，如何计算马尔科夫等价类中有向无环图的数量。我们发现，这个问题在一个有趣的实例类中是可固定参数可解的，因为我们建立了一个计数算法，它所需要的时间是该图大小的多项式，其次数不依赖于作为输入提供的附加边的数量。

    Jun, 2022

  • 动量驱动的因果结构学习：在有向无环图的 Markov 等价类上采样分布

    在推断贝叶斯网络结构（有向无环图，DAG）的背景下，我们设计了一种非可逆连续时间马尔可夫链，称为 “因果 Zig-Zag 采样器”，该采样器针对一类观测等效（Markov 等价）DAG 的概率分布。这些类别以完成的部分有向无环图（CPDAG）表示。非可逆马尔可夫链依赖于 Chickering 的贪婪等价搜索（GES）中使用的操作符，并以动量变量进行了改进，从实证结果上显示其混合效果显著。可能的目标分布包括基于 DAG 先验和 Markov 等价似然的后验分布。我们提供了一种高效的实现，其中我们开发了新的算法来列出、计数、均匀采样和应用 GES 操作符的可能移动，所有这些都显著改进了现有技术水平。

    Oct, 2023

  • 马尔可夫等价有向无环图的高效枚举

    提出了一种线性时间延迟算法，用于枚举由 Meek 和 Chickering 规则产生的马尔可夫等价类中的有向无环图，并在实验中评估其有效性，同时向马尔可夫等价本身提供了新的见解。

    Jan, 2023

  • 计算具有相同骨架的马尔可夫等价类的一个易于参数化的算法

    给定一个无向图 G 作为输入，本文通过给出一个以树宽和图 G 的最大度数为参数的固定参数可行算法，为解决如何计算具有相同骨架 G 的不同 Markov 等价类的问题取得了进展。

    Oct, 2023

  • 无向无环图模型的马尔可夫等价类枚举

    本文介绍了使用 Pearl 和 Verma 的等价标准确定的 ADGs 模型的等价类的枚举程序，分析了模型的各种属性，并且发现了等效类数量与 ADGs 数量之间的一个近似 0.267 的渐进比率。

    Jan, 2013

  • 有向无环图干预马尔可夫等价类的特征和贪心学习

    本文将有向无环图（DAGs）上的马尔可夫等价性的概念扩展到多重干预实验的干预性分布，给出两个 DAGs 在干预下等价的图理论标准，并且提出干预性本质图的概念，揭示了在干预性分布情况下因果模型识别过程的关键见解，最后基于这些见解，构建出一种新的算法来从干预性数据中进行结构学习，并进行了模拟研究。

    Apr, 2011

  • 面向可扩展的因果 DAGs 贝叶斯学习

    本文提出了贝叶斯因果推断的方法，其中用到了 MCMC 方法来进行图结构的采样，并得到了线性高斯 DAG 模型的因果效应估计。

    Sep, 2020

  • LazyIter：一种快速计数 Markov Equivalent DAGs 的算法及设计试验

    该研究提出了一种在给定干预结果的情况下高效迭代可能的 Markov 等价类的方法，结合动态规划实现了最优算法，可用于计算 MEC 的大小和实验设计。实验结果表明，该方法在计算 MEC 和实验设计方面优于现有技术。

    Jun, 2020