因果图探索的适应性复杂度

Jun, 2023

Adaptivity Complexity for Causal Graph Discovery

Davin Choo, Kirankumar Shiragur

TL;DR研究了在尽可能减少干预数量的同时，利用总共 r 个序列回合恢复因果图的问题，提出了一种可达到较好的近似水平的 r 自适应算法，并将其定义在非自适应（r=1）和完全自适应（r=n）设置之间。

Abstract

causal discovery from interventional data is an important problem, where the task is to design an interventional strategy that learns the hidden ground truth causal graph $G(V,E)$ on $|V| = n$ nodes while minimiz

causal discovery interventional strategy r-adaptivity approximation verification number

发现论文，激发创造

加权因果有向无环图的新度量和搜索算法

通过研究自适应干预下的因果图发现，提出了一种新的基准，捕捉任何搜索算法的最坏干预成本，并提出了在各种设置下实现对数逼近的自适应搜索算法。

May, 2023

适应性在线实验设计用于因果推断

在线学习中基于干预样本历史的分离图系统相匹配的追踪停止因果发现算法优于现有方法，通过较少的样本实现更高准确性的因果图学习。

May, 2024

非目标干预下的因果发现

该研究论文提出了一种基于随机干预的因果发现模型，通过最小化干预次数来解决因果发现问题，提供了多对数竞争比的近似算法，并给出了一些初步实验结果。

Feb, 2024

基于排列的带干预因果推断算法

本文提出了两种利用观测和介入数据学习基因调控网络的算法，并证明了这两种算法在符合无偏性假设的情况下均具有一致性保证。同时，这些算法具有非参数性质，适用于分析非高斯数据。本文还对这两种算法在模拟数据，蛋白质信号数据和单细胞基因表达数据上的性能进行了分析。

May, 2017

混合有向无环图中的干预因果发现

通过干预来学习混合因果模型中变量之间的因果关系是一项具有挑战性的任务，本文提出了匹配性的必要和充分条件以及一种自适应算法，用于学习混合因果模型中的所有真实边，具有最佳干预效果并在混合模型不包含循环关系时尺寸最小。

Jun, 2024

从干预数据中主动学习因果模型的两种最优策略

本文提出了两种基于最优实验设计策略的主动学习方法，用于求解因果 DAG 的最优干预目标，以改进因果 DAG 的边缘识别。其中第二种策略在多项式时间内得到任意大小的最小目标集，保证因果 DAG 的全识别。在模拟研究中，两种主动学习方法与随机干预进行比较，并分析估计误差对主动学习性能的影响。

May, 2012

因果结构学习的预算实验设计

本文研究了在实验者最多进行 $k$ 个大小为 $1$ 的非自适应实验的情况下因果结构学习的问题。我们将寻找最佳干预目标集的问题制定为优化问题，旨在最大化解决方向的边的平均数量。我们证明了相应的目标函数是子模的，并且贪心算法足以实现最优值的 $(1-rac {1}{e})$- 逼近。我们进一步提出了一种加速的贪心算法变体，可以实现数量级的性能加速。我们在合成和真实图上验证了我们提出的方法。结果表明，与纯观测设置相比，我们的算法通过较少的干预将大部分边定向。

Sep, 2017

通过小操作学习因果图

该论文探讨了在 Pearl 的结构方程模型下使用有限干预学习因果网络的问题，并使用信息论方法研究了干预次数的下界，并提出了一种新的分离系统构造方法来学习弦图和任意骨架的因果方向。

Oct, 2015

使用干预学习和测试因果模型

本文研究了因果贝叶斯网络上的测试和学习问题，并提出了有效的算法来测试两个未知因果贝叶斯网络的相似性和学习因果贝叶斯网络。

May, 2018

隐变量因果发现的高效干预设计

本文研究了如何在潜变量的影响下，通过最小化干预代价来恢复因果图，并提出了两种干预代价模型，并在此基础上，给出了在线性代价模型下识别祖先关系的算法，以及使用特殊类型的 colliders 来限制干预次数的方法。

May, 2020