我们研究在有关系统的结构侧信息时学习一组变量的贝叶斯网络（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.

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

我们分析了在没有特定分布假设的常规设置中从观察数据的学习中学循环图形模型的复杂性。我们的方法是信息定理，并使用本地马尔可夫边界搜索程序，以便在基础图形模型中递归地构建祖先集。也许令人惊讶的是，我们表明，对于某些图形集合，一个简单的前向贪婪搜索算法（即没有向后修剪阶段）足以学习每个节点的马尔可夫边界。这显着提高了我们在节点的数量中显示的样本复杂性。然后应用这一点以在从文献中概括存在现有条件的新型标识性条件下学习整个图。作为独立利益的问题，我们建立了有限样本的保障，以解决从数据中恢复马尔可夫边界的问题。此外，我们将我们的结果应用于特殊情况的Polytrees，其中假设简化，并提供了多项识别的明确条件，并且在多项式时间中可以识别和可知。我们进一步说明了算法在仿真研究中易于实现的算法的性能。我们的方法是普遍的，用于无需分布假设的离散或连续分布，并且由于这种棚灯对有效地学习来自数据的定向图形模型结构所需的最小假设。

我们研究了因果结构学习的问题，没有关于功能关系和噪声的假设。我们开发DAG-Foci，这是一种基于\ Cite {Azadkia2019Simple}的焦点变量选择算法的计算快速算法。DAG-Foci不需要调整参数并输出父母和Markov边界的响应变量的响应变量。当底层图形是多料时，我们提供了我们程序的高维保证。此外，我们展示了DAG-Foci在计算生物学\ Cite {Sachs2005Causal}的真实数据上的适用性，并说明了我们对侵犯假设的方法的稳健性。

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

常用图是表示和可视化因果关系的。对于少量变量，这种方法提供了简洁和清晰的方案的视图。随着下属的变量数量增加，图形方法可能变得不切实际，并且表示的清晰度丢失。变量的聚类是减少因果图大小的自然方式，但如果任意实施，可能会错误地改变因果关系的基本属性。我们定义了一种特定类型的群集，称为Transit Cluster，保证在某些条件下保留因果效应的可识别性属性。我们提供了一种用于在给定图中查找所有传输群集的声音和完整的算法，并演示集群如何简化因果效应的识别。我们还研究了逆问题，其中一个人以群集的图形开始，寻找扩展图，其中因果效应的可识别性属性保持不变。我们表明这种结构稳健性与过境集群密切相关。

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

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

贝叶斯网络是一组$ N $随机变量的定向非循环图（DAG）（用顶点标识）;贝叶斯网络分布（BND）是RV的概率分布，即在图中是马尔可夫的。这种模型的有限混合物是在较大的图表上对这些变量的投影，其具有额外的“隐藏”（或“隐藏”（或“潜伏”）随机变量$ U $，范围在$ \ {1，\ ldots，k \ $，以及从$ U $到其他每个其他顶点的指示边。这种类型的模型是对因因果推理的基础，其中$ U $模型是一种混杂效果。一个非常特殊的案例一直是在理论文学中的长期兴趣：空图。这种分布只是$ k $产品分布的混合。考虑到k $产品分布的混合物的联合分布，以识别产物分布及其混合重量，这一直是长期的问题。我们的结果是：（1）我们改善了从$ \ exp（o（k ^ 2））$到$ \ exp（o（k \ log k）的$ k $产品分布的混合物的示例复杂性（和运行时） ）$。鉴于已知的$ \ exp（\ omega（k））$下限，这几乎可以最好。 （2）我们为非空图表提供了第一算法。最大程度为$ \ delta $的图表的复杂性为$ \ exp（o（k（\ delta ^ 2 + \ log k）））$。 （上述复杂性是近似和抑制辅助参数的依赖性。）

最近，已经提出了利用预测模型在不断变化的环境方面的不变性来推断响应变量的因果父母的子集的不变性。如果环境仅影响少数基本机制，则例如不变因果预测（ICP）确定的子集可能很小，甚至是空的。我们介绍了最小不变性的概念，并提出了不变的血统搜索（IAS）。在其人群版本中，IAS输出了一个仅包含响应祖先的集合，并且是ICP输出的超集。当应用于数据时，如果不变性的基础测试具有渐近水平和功率，则相应的保证会渐近。我们开发可扩展算法并在模拟和真实数据上执行实验。

在图形因果发现的背景下，我们适应了线性非高斯无环模型（Lingams）的多功能框架，以提出新算法以有效地学习polytrees的图形。我们的方法结合了Chow- Liu算法，该算法首先学习了无向树结构，并与新的方案定向边缘。方向方案评估数据生成分布的矩之间的代数关系，并且计算便宜。我们为我们的方法建立了高维的一致性结果，并比较了数值实验中的不同算法版本。

转移学习中最关键的问题之一是域适应的任务，其中目标是将在一个或多个源域中培训的算法应用于不同（但相关）的目标域。本文在域内存在协变量转变时，涉及域适应。解决此问题的现有因果推断方法的主要限制之一是可扩展性。为了克服这种困难，我们提出了一种避免穷举搜索的算法，并识别基于Markov毯子发现的源和目标域的不变因果特征。 SCTL不需要先前了解因果结构，干预措施的类型或干预目标。有一个与SCTL相关的内在位置，使其实现实际上可扩展且稳健，因为本地因果发现增加了计算独立性测试的力量，并使域适配的任务进行了计算地进行了易行的。我们通过低维和高维设置中的合成和实际数据集显示SCTL的可扩展性和稳健性。

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.

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.

Variational autoencoders and Helmholtz machines use a recognition network (encoder) to approximate the posterior distribution of a generative model (decoder). In this paper we study the necessary and sufficient properties of a recognition network so that it can model the true posterior distribution exactly. These results are derived in the general context of probabilistic graphical modelling / Bayesian networks, for which the network represents a set of conditional independence statements. We derive both global conditions, in terms of d-separation, and local conditions for the recognition network to have the desired qualities. It turns out that for the local conditions the property perfectness (for every node, all parents are joined) plays an important role.

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

我们研究了在存在潜在变量存在下从数据重建因果图形模型的问题。感兴趣的主要问题是在潜在变量上恢复因果结构，同时允许一般，可能在变量之间的非线性依赖性。在许多实际问题中，原始观测之间的依赖性（例如，图像中的像素）的依赖性比某些高级潜在特征（例如概念或对象）之间的依赖性要小得多，这是感兴趣的设置。我们提供潜在表示和潜在潜在因果模型的条件可通过减少到混合甲骨文来识别。这些结果突出了学习混合模型的顺序的良好研究问题与观察到和解开的基础结构的问题之间的富裕问题之间的有趣连接。证明是建设性的，并导致几种算法用于明确重建全图形模型。我们讨论高效算法并提供说明实践中算法的实验。

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

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