调整识别距离：因果结构学习的一个𝚐𝚊𝚍𝚓𝚒𝚍

这是 𝚐𝚊𝚍𝚓𝚒𝚍 🐥 的早期版本，非常欢迎反馈！只需在github上 提交一个issue。

如果您使用 𝚐𝚊𝚍𝚓𝚒𝚍 进行研究，请引用 我们的文章

@article{henckel2024adjustment,
    title = {{Adjustment Identification Distance: A gadjid for Causal Structure Learning}},
    author = {Leonard Henckel and Theo Würtzen and Sebastian Weichwald},
    journal = {{arXiv preprint arXiv:2402.08616}},
    year = {2024},
    doi = {10.48550/arXiv.2402.08616},
}

快速入门 🚀 – 入门示例

只需 pip install gadjid 安装 𝚐𝚊𝚍𝚓𝚒𝚍 的最新版本
并运行 python -c "import gadjid; help(gadjid)" 开始使用（或查看 安装替代方案）。

import gadjid
from gadjid import example, ancestor_aid, oset_aid, parent_aid, shd
import numpy as np

help(gadjid)

example.run_parent_aid()

Gtrue = np.array([
    [0, 1, 1, 1, 1],
    [0, 0, 1, 1, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
], dtype=np.int8)
Gguess = np.array([
    [0, 0, 1, 1, 1],
    [1, 0, 1, 1, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
], dtype=np.int8)

print(ancestor_aid(Gtrue, Gguess, edge_direction="from row to column"))
print(shd(Gtrue, Gguess))

𝚐𝚊𝚍𝚓𝚒𝚍 使用 Rust 实现，可以通过我们的 Python 包装器（使用 maturin 和 PyO3 实现）方便地从 Python 调用。

评估因果发现算法学习到的图是困难的：两个图之间不同的边的数量并不能反映它们在识别公式方面如何不同，这些公式用于表示因果效应。我们提出了一种框架，用于开发图之间的因果距离，其中包括有向无环图的结构干预距离作为一个特例。我们使用这个框架开发改进的调整距离，以及扩展到完成的半有向无环图和因果顺序。我们开发了新的可达性算法，以有效地计算距离，并证明它们的低多项式时间复杂度。在我们的包gadjid中，我们提供了我们距离的实现；它们的速度比结构干预距离快几个数量级，并且已经证明具有较低的时间复杂度，因此为因果发现提供了一种成功指标，可以扩展到以前无法承受的图大小。

并行化 – 设置线程数

𝚐𝚊𝚍𝚓𝚒𝚍使用rayon进行并行化，默认情况下使用与物理CPU核心数相同的线程数。可以通过环境变量RAYON_NUM_THREADS设置要使用的线程数。我们建议这样做，并手动设置线程数，这不仅是为了明确，而且可以避免确定物理CPU核心数的小运行时开销。

实现距离

• ancestor_aid(Gtrue, Gguess, edge_direction)
• oset_aid(Gtrue, Gguess, edge_direction)
• parent_aid(Gtrue, Gguess, edge_direction)
• 为了方便，还实现了以下距离
  • shd(Gtrue, Gguess)
  • sid(Gtrue, Gguess, edge_direction) – 仅适用于DAGs！

其中Gtrue和Gguess是DAG或CPDAG的邻接矩阵，edge_direction确定邻接矩阵中第r行第c列的1表示边r → c（edge_direction="from row to column"）还是c → r（edge_direction="from column to row"）。这些函数在其输入上不是对称的：为了计算距离，在图Gguess中推断因果效应的识别公式，并对其进行验证以与图Gtrue进行比较。距离返回一个元组(normalised_distance, mistake_count)，表示在Gguess中推断的因果效应中相对于Gtrue错误的分数，normalised_distance，以及错误推断的因果效应的数量，mistake_count。在具有p个节点的图中，有$p(p-1)$对因果效应需要推断，我们定义归一化如下：normalised_distance = mistake_count / p(p-1)。

您也可以通过parent_aid(DAGtrue, DAGguess, edge_direction)计算DAG之间的SID，但我们推荐使用ancestor_aid和oset_aid，并且对于CPDAG输入，parent_aid与SID不匹配（参见我们的相关文章）。

如果edge_direction="from row to column"，则行r和列c中的1表示有向边r → c；如果edge_direction="from column to row"，则行r和列c中的1表示有向边c → r；对于任一edge_direction设置，行r和列c中的2表示无向边r – c（行c和列r中的附加2被忽略；这两个条目中的任何一个都足以表示无向边）。

DAG的邻接矩阵只能包含0和1。CPDAG的邻接矩阵只能包含0、1和2。对DAG和CPDAG输入进行无环性验证。然而，对于CPDAG输入，用户需要确保邻接矩阵确实编码了一个有效的CPDAG（而不是只是一个PDAG）。

实证运行时间分析

在配备了8GB RAM和4核i5-8365U处理器的笔记本电脑上运行实验。在这里，对于一个有$p$个节点的图，稀疏图期望有$10p$条边，密集图期望有$0.3p(p-1)/2$条边，而x-稀疏图期望有$0.75p$条边。

在1分钟内可行的最大图大小

使用Python接口和CRAN的SID R包v1.1通过𝚐𝚊𝚍𝚓𝚒𝚍 v0.1.0获得的结果。

平均运行时间

使用Python接口和CRAN的SID R包v1.1通过𝚐𝚊𝚍𝚓𝚒𝚍 v0.1.0获得的结果。

许可证

𝚐𝚊𝚍𝚓𝚒𝚍的源代码形式可在https://github.com/CausalDisco/gadjid找到。

此源代码形式受Mozilla公共许可证，第2.0版条款约束。如果此文件未附带MPL副本，您可以从中获取一个：https://mozilla.org/MPL/2.0/。

另请参阅MPL-2.0 FAQ。