机构名称：
¥ 1.0
观察数据的因果效应估计是经验科学中的基本任务。当没有观察到的混杂因素参与系统时，这变得特别具有挑战性。本文着重于前门调整 - 一种经典技术，使用观察到的调解人即使在存在未观察到的混杂的情况下，也可以识别因果关系。虽然在前门估计的统计特性众所周知，但长期以来其算法方面尚未探索。In 2022, Jeong, Tian, and Bareinboim presented the first polynomial-time algorithm for finding sets satisfying the front-door criterion in a given directed acyclic graph (DAG), with an O ( n 3 ( n + m )) run time, where n denotes the number of variables and m the number of edges of the causal graph.在我们的工作中，我们给出了第一个线性时间，即O（n + M），该任务的算法，因此达到了渐近最佳的时间复杂。此结果意味着所有前门调整集的O（n（n + M））延迟枚举算法，再次将先前的工作提高了n 3。此外，我们提供了第一个线性时算法，用于查找最小的前门调整集。我们在多种编程语言中提供了算法的实现，以促进实际用法并验证其可行性，即使对于大图。
因果图中前门调整的线性时间算法
主要关键词
相关文件推荐
