我们建议在没有观察到的变量的情况下，提出基于订购的方法，用于学习结构方程模型（SEM）的最大祖先图（MAG），直到其Markov等效类（MEC）。文献中的现有基于订购的方法通过学习因果顺序（C-order）恢复图。我们提倡一个名为“可移动顺序”（R-rorder）的新颖订单，因为它们比结构学习的C端口有利。这是因为R-orders是适当定义的优化问题的最小化器，该问题可以准确解决（使用强化学习方法）或大约（使用爬山搜索）。此外，R-orders（与C-orders不同）在MEC中的所有图表中都是不变的，并将C-orders包括为子集。鉴于一组R-orders通常明显大于C-orders集，因此优化问题更容易找到R级而不是C级。我们评估了在现实世界和随机生成的网络上提出的方法的性能和可伸缩性。

我们研究在有关系统的结构侧信息时学习一组变量的贝叶斯网络（BN）的问题。众所周知，学习一般BN的结构在计算上和统计上具有挑战性。然而，通常在许多应用中，关于底层结构的侧面信息可能会降低学习复杂性。在本文中，我们开发了一种基于递归约束的算法，其有效地将这些知识（即侧信息）纳入学习过程。特别地，我们研究了关于底层BN的两种类型的结构侧信息：（i）其集团数的上限是已知的，或者（ii）它是无菱形的。我们为学习算法提供理论保证，包括每个场景所需的最坏情况的测试数量。由于我们的工作，我们表明可以通过多项式复杂性学习有界树木宽度BNS。此外，我们评估了综合性和现实世界结构的算法的性能和可扩展性，并表明它们优于最先进的结构学习算法。

We study experiment design for unique identification of the causal graph of a system where the graph may contain cycles. The presence of cycles in the structure introduces major challenges for experiment design as, unlike acyclic graphs, learning the skeleton of causal graphs with cycles may not be possible from merely the observational distribution. Furthermore, intervening on a variable in such graphs does not necessarily lead to orienting all the edges incident to it. In this paper, we propose an experiment design approach that can learn both cyclic and acyclic graphs and hence, unifies the task of experiment design for both types of graphs. We provide a lower bound on the number of experiments required to guarantee the unique identification of the causal graph in the worst case, showing that the proposed approach is order-optimal in terms of the number of experiments up to an additive logarithmic term. Moreover, we extend our result to the setting where the size of each experiment is bounded by a constant. For this case, we show that our approach is optimal in terms of the size of the largest experiment required for uniquely identifying the causal graph in the worst case.

Pearl's Do Colculus是一种完整的公理方法，可以从观察数据中学习可识别的因果效应。如果无法识别这种效果，则有必要在系统中执行经常昂贵的干预措施以学习因果效应。在这项工作中，我们考虑了设计干预措施以最低成本来确定所需效果的问题。首先，我们证明了这个问题是NP-HARD，随后提出了一种可以找到最佳解或对数因子近似值的算法。这是通过在我们的问题和最小击球设置问题之间建立联系来完成的。此外，我们提出了几种多项式启发式算法来解决问题的计算复杂性。尽管这些算法可能会偶然发现亚最佳解决方案，但我们的模拟表明它们在随机图上产生了小的遗憾。

人们对利用置换推理来搜索定向的无环因果模型的方法越来越兴趣，包括Teysier和Kohler和Solus，Wang和Uhler的GSP的“订购搜索”。我们通过基于置换的操作Tuck扩展了后者的方法，并开发了一类算法，即掌握，这些算法在越来越弱的假设下比忠诚度更有效且方向保持一致。最放松的掌握形式优于模拟中许多最新的因果搜索算法，即使对于具有超过100个变量的密集图和图形，也可以有效，准确地搜索。

Wien \ \'inst，Bannach和li \'Skiewicz（AAAI 2021）最近给出了一种用于计算马尔可夫等效类中定向无环形数量数量的多项式精确算法。在本文中，我们考虑了更一般的问题当某些边缘的方向也固定时，计算马尔可夫等效类中有向无环的数量的数量（例如，在部分可用的介入数据时会出现此设置）。从理论上讲，复杂性。相比之下，我们证明了问题在有趣的一类实例中仍然可以解决，它是通过确定``固定参数tractable''。特别是，我们的计数算法在时间范围内运行。多项式在图的大小中，其中多项式的程度\ emph {not}取决于提供的附加边数作为输入的数量。

In this review, we discuss approaches for learning causal structure from data, also called causal discovery. In particular, we focus on approaches for learning directed acyclic graphs (DAGs) and various generalizations which allow for some variables to be unobserved in the available data. We devote special attention to two fundamental combinatorial aspects of causal structure learning. First, we discuss the structure of the search space over causal graphs. Second, we discuss the structure of equivalence classes over causal graphs, i.e., sets of graphs which represent what can be learned from observational data alone, and how these equivalence classes can be refined by adding interventional data.

本文考虑了从观察和介入数据估算因果导向的非循环图中未知干预目标的问题。重点是线性结构方程模型（SEM）中的软干预。目前对因果结构的方法学习使用已知的干预目标或使用假设测试来发现即使是线性SEM也可以发现未知的干预目标。这严重限制了它们的可扩展性和样本复杂性。本文提出了一种可扩展和高效的算法，始终识别所有干预目标。关键思想是从与观察和介入数据集相关联的精度矩阵之间的差异来估计干预站点。它涉及反复估计不同亚空间子集中的这些站点。该算法的算法还可用于将给定的观察马尔可夫等效类更新为介入马尔可夫等价类。在分析地建立一致性，马尔可夫等效和采样复杂性。最后，实际和合成数据的仿真结果展示了所提出的可扩展因果结构恢复方法的增益。算法的实现和重现仿真结果的代码可用于\ url {https://github.com/bvarici/intervention- istimation}。

We present a new algorithm for Bayesian network structure learning, called Max-Min Hill-Climbing (MMHC). The algorithm combines ideas from local learning, constraint-based, and search-and-score techniques in a principled and effective way. It first reconstructs the skeleton of a Bayesian network and then performs a Bayesian-scoring greedy hill-climbing search to orient the edges. In our extensive empirical evaluation MMHC outperforms on average and in terms of various metrics several prototypical and state-of-the-art algorithms, namely the PC, Sparse Candidate, Three Phase Dependency Analysis, Optimal Reinsertion, Greedy Equivalence Search, and Greedy Search. These are the first empirical results simultaneously comparing most of the major Bayesian network algorithms against each other. MMHC offers certain theoretical advantages, specifically over the Sparse Candidate algorithm, corroborated by our experiments. MMHC and detailed results of our study are publicly available at http://www.dsl-lab.org/supplements/mmhc paper/mmhc index.html.

在非参数环境中，因果结构通常仅在马尔可夫等效性上可识别，并且出于因果推断的目的，学习马尔可夫等效类（MEC）的图形表示很有用。在本文中，我们重新审视了贪婪的等效搜索（GES）算法，该算法被广泛引用为一种基于分数的算法，用于学习基本因果结构的MEC。我们观察到，为了使GES算法在非参数设置中保持一致，不必设计评估图的评分度量。取而代之的是，足以插入有条件依赖度量的一致估计器来指导搜索。因此，我们提出了GES算法的重塑，该算法比基于标准分数的版本更灵活，并且很容易将自己带到非参数设置，并具有条件依赖性的一般度量。此外，我们提出了一种神经条件依赖性（NCD）度量，该措施利用深神经网络的表达能力以非参数方式表征条件独立性。我们根据标准假设建立了重新构架GES算法的最佳性，并使用我们的NCD估计器来决定条件独立性的一致性。这些结果共同证明了拟议的方法。实验结果证明了我们方法在因果发现中的有效性，以及使用我们的NCD度量而不是基于内核的措施的优势。

在学习从观察数据中学习贝叶斯网络的图形结构是描述和帮助了解复杂应用程序中的数据生成过程的关键，而任务由于其计算复杂性而构成了相当大的挑战。代表贝叶斯网络模型的定向非循环图（DAG）通常不会从观察数据识别，并且存在各种方法来估计其等价类。在某些假设下，流行的PC算法可以通过测试条件独立（CI）一致地始终恢复正确的等价类，从边际独立关系开始，逐步扩展调节集。这里，我们提出了一种通过利用协方差与精密矩阵之间的反向关系来执行PC算法内的CI测试的新颖方案。值得注意的是，精密矩阵的元素与高斯数据的部分相关性。然后，我们的算法利用对协方差和精密矩阵的块矩阵逆转，同时对互补（或双）调节集的部分相关性进行测试。因此，双PC算法的多个CI测试首先考虑边缘和全阶CI关系并逐步地移动到中心顺序。仿真研究表明，双PC算法在运行时和恢复底层网络结构方面都优于经典PC算法。

因果鉴定是因果推理文献的核心，在该文献中提出了完整的算法来识别感兴趣的因果问题。这些算法的有效性取决于访问正确指定的因果结构的限制性假设。在这项工作中，我们研究了可获得因果结构概率模型的环境。具体而言，因果图中的边缘是分配的概率，例如，可能代表来自领域专家的信念程度。另外，关于边缘的不确定的可能反映了特定统计检验的置信度。在这种情况下自然出现的问题是：给定这样的概率图和感兴趣的特定因果效应，哪些具有最高合理性的子图是什么？我们表明回答这个问题减少了解决NP-HARD组合优化问题，我们称之为边缘ID问题。我们提出有效的算法来近似此问题，并评估我们针对现实世界网络和随机生成图的算法。

在观察性研究中，经常遇到有关存在或缺乏因果边缘和路径的因果背景知识。由于背景知识而导致的马尔可夫等效dag的子类共享的指向边缘和链接可以由因果关系最大部分定向的无循环图（MPDAG）表示。在本文中，我们首先提供了因果MPDAG的声音和完整的图形表征，并提供了因果MPDAG的最小表示。然后，我们介绍了一种名为Direct Causal子句（DCC）的新颖表示，以统一形式表示所有类型的因果背景知识。使用DCC，我们研究因果背景知识的一致性和等效性，并表明任何因果背景知识集都可以等效地分解为因果MPDAG，以及最小的残留DCC。还提供了多项式时间算法，以检查一致性，等效性并找到分解的MPDAG和残留DCC。最后，有了因果背景知识，我们证明了一个足够且必要的条件来识别因果关系，并且出人意料地发现因果效应的可识别性仅取决于分解的MPDAG。我们还开发了局部IDA型算法，以估计无法识别效应的可能值。模拟表明因果背景知识可以显着提高因果影响的识别性。

我们考虑代表代理模型的问题，该模型使用我们称之为CSTREES的阶段树模型的适当子类对离散数据编码离散数据的原因模型。我们表明，可以通过集合表达CSTREE编码的上下文专用信息。由于并非所有阶段树模型都承认此属性，CSTREES是一个子类，可提供特定于上下文的因果信息的透明，直观和紧凑的表示。我们证明了CSTREEES承认全球性马尔可夫属性，它产生了模型等价的图形标准，概括了Verma和珍珠的DAG模型。这些结果延伸到一般介入模型设置，使CSTREES第一族的上下文专用模型允许介入模型等价的特征。我们还为CSTREE的最大似然估计器提供了一种封闭式公式，并使用它来表示贝叶斯信息标准是该模型类的本地一致的分数函数。在模拟和实际数据上分析了CSTHEELE的性能，在那里我们看到与CSTREELE而不是一般上演树的建模不会导致预测精度的显着损失，同时提供了特定于上下文的因果信息的DAG表示。

Linear structural causal models (SCMs)-- in which each observed variable is generated by a subset of the other observed variables as well as a subset of the exogenous sources-- are pervasive in causal inference and casual discovery. However, for the task of causal discovery, existing work almost exclusively focus on the submodel where each observed variable is associated with a distinct source with non-zero variance. This results in the restriction that no observed variable can deterministically depend on other observed variables or latent confounders. In this paper, we extend the results on structure learning by focusing on a subclass of linear SCMs which do not have this property, i.e., models in which observed variables can be causally affected by any subset of the sources, and are allowed to be a deterministic function of other observed variables or latent confounders. This allows for a more realistic modeling of influence or information propagation in systems. We focus on the task of causal discovery form observational data generated from a member of this subclass. We derive a set of necessary and sufficient conditions for unique identifiability of the causal structure. To the best of our knowledge, this is the first work that gives identifiability results for causal discovery under both latent confounding and deterministic relationships. Further, we propose an algorithm for recovering the underlying causal structure when the aforementioned conditions are satisfied. We validate our theoretical results both on synthetic and real datasets.

In this paper we prove the so-called "Meek Conjecture". In particular, we show that if a DAG H is an independence map of another DAG G, then there exists a finite sequence of edge additions and covered edge reversals in G such that (1) after each edge modification H remains an independence map of G and ( 2) after all modifications G = H. As shown by Meek (1997), this result has an important consequence for Bayesian approaches to learning Bayesian networks from data: in the limit of large sample size, there exists a twophase greedy search algorithm that-when applied to a particular sparsely-connected search space-provably identifies a perfect map of the generative distribution if that perfect map is a DAG. We provide a new implementation of the search space, using equivalence classes as states, for which all operators used in the greedy search can be scored efficiently using local functions of the nodes in the domain. Finally, using both synthetic and real-world datasets, we demonstrate that the two-phase greedy approach leads to good solutions when learning with finite sample sizes.

本地到全球学习方法在贝叶斯网络（BN）结构学习中起着重要作用。现有的本地到全局学习算法首先通过在数据集中学习每个变量的MB（马尔可夫毯子）或PC（家长和儿童）来构建DAG（Markov毯子）或PC（父母和儿童），然后在骨架中定向边缘。然而，现有的MB或PC学习方法通​​常是昂贵的昂贵昂贵，特别是具有大型BN，导致局部到全局学习算法效率低下。为了解决问题，在本文中，我们使用特征选择开发了一个有效的本地到全局学习方法。具体地，我们首先分析众所周知的最小冗余和最大相关性（MRMR）特征选择方法的基本原理，用于学习变量的PC集。基于分析，我们提出了一种高效的F2SL（基于特征选择的结构学习）方法，以局部 - 全局BN结构学习。 F2SL方法首先采用MRMR方法来学习DAG骨架，然后在骨架中的边缘。采用独立测试或进行定向边缘的分数函数，我们将F2SL方法实例化为两个新算法，F2SL-C（使用独立测试）和F2SL-S（使用得分函数）。与最先进的本地到全局BN学习算法相比，实验验证了本文中所提出的算法比比较算法更有效，提供竞争性结构学习质量。

我们介绍了一种声音和完整的算法，称为迭代因果发现（ICD），用于在存在潜在混杂器和选择偏压的情况下恢复因果图。 ICD依赖于因果性马尔可夫和忠诚的假设，并恢复潜在因果图的等价类别。它以完整的图形开始，由单个迭代阶段组成，通过识别连接节点之间的条件独立性（CI）逐渐改进该图。任何迭代后都需要的独立性和因果关系是正确的，随时渲染ICD。基本上，我们将CI调节的大小与测试节点绑定到图表上的距离，并在连续迭代中提高此值。因此，每次迭代都改进了通过具有较小调节集的先前迭代恢复的图 - 一种更高的统计功率 - 这有助于稳定性。我们凭经验证明ICD需要较少的CI测试，并与FCI，FCI +和RFCI算法相比，学习更准确的因果图。

本文提出了一种新的因果发现方法，即结构不可知的建模（SAM）。SAM利用条件独立性和分布不对称性，旨在从观察数据中找到潜在的因果结构。该方法基于不同玩家之间的游戏，该游戏将每个变量分布有条件地作为神经网估算，而对手则旨在区分生成的数据与原始数据。结合分布估计，稀疏性和无环限制的学习标准用于通过随机梯度下降来实施图形结构和参数的优化。SAM在合成和真实数据上进行了实验验证。

因果结构学习是许多领域的关键问题。通过对感兴趣系统进行实验来学习因果结构。我们解决了设计一批实验的主要原因，每个实验中同时干预多个变量。虽然可能比常用的单变干预措施更具信息丰富，但选择这种干预措施是更具挑战性的，这是由于复合干预措施的双指数组合搜索空间。在本文中，我们开发有效的算法，以优化量化预算限制批次实验的信息性的不同目标函数。通过建立这些目标的新型子模具性质，我们为我们的算法提供近似保证。我们的算法经验上优于随机干预和算法，只能选择单变化干预。