计算和抽样马尔科夫等效有向无环图的多项式时间算法
本文提出了一种能够在多项式时间内计数和抽样来自马尔可夫等价类的有向无环图的算法,解决了该领域长期存在的一个问题。通过实验实现,该算法应用价值高,使因果结构和因果效应识别的主动学习策略变得实用。
May, 2022
本文提出了一种用于计算标记等价类中 DAG 数量的技术,并显示在有限制图案下,所提出的算法是多项式时间的。此技术可用于均匀采样来枚举等价类中的 DAG,并可用于因果实验设计和估计联合干预的因果效应。
Feb, 2018
本文研究的问题是,在部分边缘方向已知的情况下,如何计算马尔科夫等价类中有向无环图的数量。我们发现,这个问题在一个有趣的实例类中是可固定参数可解的,因为我们建立了一个计数算法,它所需要的时间是该图大小的多项式,其次数不依赖于作为输入提供的附加边的数量。
Jun, 2022
提出了一种线性时间延迟算法,用于枚举由 Meek 和 Chickering 规则产生的马尔可夫等价类中的有向无环图,并在实验中评估其有效性,同时向马尔可夫等价本身提供了新的见解。
Jan, 2023
本文介绍了使用 Pearl 和 Verma 的等价标准确定的 ADGs 模型的等价类的枚举程序,分析了模型的各种属性,并且发现了等效类数量与 ADGs 数量之间的一个近似 0.267 的渐进比率。
Jan, 2013
给定一个无向图 G 作为输入,本文通过给出一个以树宽和图 G 的最大度数为参数的固定参数可行算法,为解决如何计算具有相同骨架 G 的不同 Markov 等价类的问题取得了进展。
Oct, 2023
在推断贝叶斯网络结构(有向无环图,DAG)的背景下,我们设计了一种非可逆连续时间马尔可夫链,称为 “因果 Zig-Zag 采样器”,该采样器针对一类观测等效(Markov 等价)DAG 的概率分布。这些类别以完成的部分有向无环图(CPDAG)表示。非可逆马尔可夫链依赖于 Chickering 的贪婪等价搜索(GES)中使用的操作符,并以动量变量进行了改进,从实证结果上显示其混合效果显著。可能的目标分布包括基于 DAG 先验和 Markov 等价似然的后验分布。我们提供了一种高效的实现,其中我们开发了新的算法来列出、计数、均匀采样和应用 GES 操作符的可能移动,所有这些都显著改进了现有技术水平。
Oct, 2023
本文将有向无环图(DAGs)上的马尔可夫等价性的概念扩展到多重干预实验的干预性分布,给出两个 DAGs 在干预下等价的图理论标准,并且提出干预性本质图的概念,揭示了在干预性分布情况下因果模型识别过程的关键见解,最后基于这些见解,构建出一种新的算法来从干预性数据中进行结构学习,并进行了模拟研究。
Apr, 2011
使用置换的贪心方法,基于一个置换多面体中的边图,在有限多步内,找到了一个对应于支配生成有向无环图原则的图结构的稀疏最小置换,该方法成功应用于有向无环图的生成。
Feb, 2017
本研究研究了祖先图在有潜在变量和选择变量的有向无环图模型中所表示的条件独立性关系,阐述了两个最大祖先图如何满足马尔可夫等价关系,并通过算法在多项式时间内计算出马尔可夫等价问题。
Aug, 2009