本研究提出了针对因果有向无环图(DAGs)的干预设计的通用下限,并基于有向团树将 DAG 分解成可独立定向的组件,从而证明在任何 EC 中定向任何 DAG 所需的单节点干预数至少是每个基本图的链组件中最大团大小的一半的总和。另外,我们还提出了一个两阶段干预设计算法,其性能符合以最大团个数的对数乘性为界限的最优干预数,并通过合成实验验证了我们的算法可以比大多数相关工作处理更大的图形并且获得更好的最坏情况性能。
Nov, 2020
本文研究了因果贝叶斯网络上的测试和学习问题,并提出了有效的算法来测试两个未知因果贝叶斯网络的相似性和学习因果贝叶斯网络。
May, 2018
通过干预来学习混合因果模型中变量之间的因果关系是一项具有挑战性的任务,本文提出了匹配性的必要和充分条件以及一种自适应算法,用于学习混合因果模型中的所有真实边,具有最佳干预效果并在混合模型不包含循环关系时尺寸最小。
Jun, 2024
本文研究了在实验者最多进行 $k$ 个大小为 $1$ 的非自适应实验的情况下因果结构学习的问题。 我们将寻找最佳干预目标集的问题制定为优化问题,旨在最大化解决方向的边的平均数量。我们证明了相应的目标函数是子模的,并且贪心算法足以实现最优值的 $(1-rac {1}{e})$- 逼近。我们进一步提出了一种加速的贪心算法变体,可以实现数量级的性能加速。我们在合成和真实图上验证了我们提出的方法。结果表明,与纯观测设置相比,我们的算法通过较少的干预将大部分边定向。
Sep, 2017
考虑有干预的变量集合的因果图学习问题,研究了在给定骨架的情况下设计最小总代价的干预集合,以唯一确定具有该骨架的任何因果图的成本最优因果图学习问题,并证明该问题可以在多项式时间内求解,针对干预数量有限的情况,我们提供了树或团树骨架的情况下的多项式时间算法,对于一般弦图骨架,我们开发了一个高效的贪心算法,当因果图骨架是区间图时,可以改进算法。
Mar, 2017
在线学习中基于干预样本历史的分离图系统相匹配的追踪停止因果发现算法优于现有方法,通过较少的样本实现更高准确性的因果图学习。
May, 2024
本文研究探讨了在给定一个观测 Markov 等价类的因果图时,发现其唯一性所需的最坏情况实验次数可以指定为 Markov 等价类中最大团的函数。我们提供了一种算法来计算我们认为对于上述任务最优的干预集合。该算法建立在 Eberhardt 等人(2005 年)对于当考虑所有可能的 N 个变量的有向无环图时的一系列实验的最坏情况分析中获得的洞见的基础上。仿真结果表明我们的猜想是正确的。我们还展示了我们的猜想推广到其他可能的图假设类别不易进行,以及算法不再最优的意义。
Jun, 2012
研究了在给定因果图的情况下,通过最小成本干预变量来学习任意因果图的问题。证明了该问题是 NP 难问题,提出了一种基于贪心算法的常数级别近似解,并开发了一种计算干预设计的算法,该算法在稀疏因果图和干预条件下几乎是最优的,并讨论了在节点有成本的情况下如何使用它。
Oct, 2018
本文提出了两种基于最优实验设计策略的主动学习方法,用于求解因果 DAG 的最优干预目标,以改进因果 DAG 的边缘识别。其中第二种策略在多项式时间内得到任意大小的最小目标集,保证因果 DAG 的全识别。在模拟研究中,两种主动学习方法与随机干预进行比较,并分析估计误差对主动学习性能的影响。
May, 2012
通过研究自适应干预下的因果图发现,提出了一种新的基准,捕捉任何搜索算法的最坏干预成本,并提出了在各种设置下实现对数逼近的自适应搜索算法。
May, 2023