链事件图（CEGS）是最近的概率图形模型 - 贝叶斯网络的概括 - 在图形拓扑中提供了结构零，结构缺失值和上下文的条件独立性的显式表示。通过从事件树的顶点的着色开始以识别一步转变对称的变换，从事件树构成CEG。这个彩色的事件树，也称为阶段树是用于这个家庭的学习算法的输出。令人惊讶的是，尚未设计一般算法，它会自动将任何分阶段的树转换为CEG表示。在本文中，我们为该转换提供了一种简单的迭代反向算法。此外，我们表明，没有任何信息从将阶段的树转换成CEG。最后，我们证明，通过最佳停止标准，我们的算法比Silander和Leong（2013）中出现的特殊情况的概率更有效。我们还提供使用此算法的Python代码从任何暂存树中获取CEG以及使用采样零添加边缘的功能。

Chain event graphs are a family of probabilistic graphical models that generalise Bayesian networks and have been successfully applied to a wide range of domains. Unlike Bayesian networks, these models can encode context-specific conditional independencies as well as asymmetric developments within the evolution of a process. More recently, new model classes belonging to the chain event graph family have been developed for modelling time-to-event data to study the temporal dynamics of a process. However, existing model selection algorithms for chain event graphs and its variants rely on all parameters having conjugate priors. This is unrealistic for many real-world applications. In this paper, we propose a mixture modelling approach to model selection in chain event graphs that does not rely on conjugacy. Moreover, we also show that this methodology is more amenable to being robustly scaled than the existing model selection algorithms used for this family. We demonstrate our techniques on simulated datasets.

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

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

分类的生成模型使用类变量的联合概率分布和功能来构建决策规则。在生成模型中，贝叶斯网络和天真的贝叶斯分类器是最常用的，并提供了所有变量之间关系的明确图形表示。但是，这些具有高度限制可能存在的关系类型的缺点，而不允许特定于上下文的独立性。在这里，我们介绍了一种新的生成分类器类别，称为“分阶性树分类器”，该分类器正式解释了特定于上下文的独立性。它们是通过对事件树的顶点的分区进行构建的，可以正式读取条件独立性。还定义了天真的阶段树分类器，它扩展了经典的天真贝叶斯分类器，同时保持相同的复杂性。一项广泛的仿真研究表明，分级树分类器的分类精度与最先进的分类器的分类精度具有竞争力，并且一个示例展示了它们在实践中的使用。

已经定义了几种分期树模型的结构学习算法，这是贝叶斯网络的不对称扩展。但是，随着变量考虑的增加数量，它们不会有效地扩展。在这里，我们介绍了第一个针对分阶段树的可扩展结构学习算法，该算法在仅少量依赖项的模型中进行搜索。一项仿真研究以及现实世界的应用程序说明了我们的日常工作以及此类学习的分阶段的实际使用。

We consider the problem of learning the structure underlying a Gaussian graphical model when the variables (or subsets thereof) are corrupted by independent noise. A recent line of work establishes that even for tree-structured graphical models, only partial structure recovery is possible and goes on to devise algorithms to identify the structure up to an (unavoidable) equivalence class of trees. We extend these results beyond trees and consider the model selection problem under noise for non tree-structured graphs, as tree graphs cannot model several real-world scenarios. Although unidentifiable, we show that, like the tree-structured graphs, the ambiguity is limited to an equivalence class. This limited ambiguity can help provide meaningful clustering information (even with noise), which is helpful in computer and social networks, protein-protein interaction networks, and power networks. Furthermore, we devise an algorithm based on a novel ancestral testing method for recovering the equivalence class. We complement these results with finite sample guarantees for the algorithm in the high-dimensional regime.

当今现实生活系统中图的普遍性很明显，该系统要么明确地以图形为单位，要么可以很容易地将其建模为一个。因此，这种图形结构是商店丰富的信息。这具有各种含义，具体取决于我们对节点还是整个图表感兴趣。在本文中，我们主要关注的是稍后的，即图表的结构会影响其代表的现实生活系统的属性。这种结构影响的模型将有助于通过其结构特性来推断复杂和大型系统（例如VLSI电路）的有用特性。但是，在我们可以将基于机器学习（ML）技术应用于建模这种关系之前，必须有效地表示图。在本文中，我们提出了一个图表表示，该图表是无损的，在顶点数量方面是线性大小的，并给出图形的1-D表示。我们的表示是基于对树木编码的Prufer编码。此外，我们的方法基于一种新颖的技术，称为$ \ Mathcal {gt} $ - 增强功能，我们首先转换图形，使其可以由单数树表示。编码还提供了包括附加图形属性并改善代码的解释性的范围。

对表示形式的研究对于任何形式的交流都是至关重要的，我们有效利用它们的能力至关重要。本文介绍了一种新颖的理论 - 代表性系统理论 - 旨在从三个核心角度从三个核心角度进行抽象地编码各种表示：语法，综合及其属性。通过介绍建筑空间的概念，我们能够在一个统一的范式下编码这些核心组件中的每个核心组件。使用我们的代表性系统理论，有可能在结构上将一个系统中的表示形式转换为另一个系统的表示形式。我们结构转化技术的固有方面是根据表示的属性（例如它们的相对认知有效性或结构复杂性）的代表选择。提供一般结构转化技术的主要理论障碍是缺乏终止算法。代表系统理论允许在没有终止算法的情况下衍生部分变换。由于代表性系统理论提供了一种通用编码代表系统的通用方法，因此消除了进一步的关键障碍：需要设计特定于系统的结构转换算法，这是当不同系统采用不同的形式化方法时所必需的。因此，代表性系统理论是第一个提供统一方法来编码表示形式，通过结构转换支持表示形式的第一个通用框架，并具有广泛的实用应用。

Bayesian networks are widely used to learn and reason about the dependence structure of discrete variables. However, they are only capable of formally encoding symmetric conditional independence, which in practice is often too strict to hold. Asymmetry-labeled DAGs have been recently proposed to both extend the class of Bayesian networks by relaxing the symmetric assumption of independence and denote the type of dependence existing between the variables of interest. Here, we introduce novel structural learning algorithms for this class of models which, whilst being efficient, allow for a straightforward interpretation of the underlying dependence structure. A comprehensive computational study highlights the efficiency of the algorithms. A real-world data application using data from the Fear of COVID-19 Scale collected in Italy showcases their use in practice.

This paper presents a new approach for analyzing and identifying potentially useful generalized plans. It presents a new conceptual framework along with an algorithmic process for assessing termination and reachability related properties of generalized plans. The presented framework builds upon classic results on the analysis of graphs to decompose generalized plans into smaller components in a novel algorithm for conducting a hierarchical analysis for termination of arbitrary generalized plans. Theoretical analysis of the new framework establishes soundness of the presented algorithms and shows how it goes beyond existing approaches; empirical analysis illustrates the scope of this approach. Our analysis shows that this new approach can effectively identify termination for a significantly larger class of generalized plans than was possible using existing methods.

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

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

The stochastic block model (SBM) is a random graph model with planted clusters. It is widely employed as a canonical model to study clustering and community detection, and provides generally a fertile ground to study the statistical and computational tradeoffs that arise in network and data sciences.This note surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to information-theoretic and computational thresholds, and for various recovery requirements such as exact, partial and weak recovery (a.k.a., detection). The main results discussed are the phase transitions for exact recovery at the Chernoff-Hellinger threshold, the phase transition for weak recovery at the Kesten-Stigum threshold, the optimal distortion-SNR tradeoff for partial recovery, the learning of the SBM parameters and the gap between information-theoretic and computational thresholds.The note also covers some of the algorithms developed in the quest of achieving the limits, in particular two-round algorithms via graph-splitting, semi-definite programming, linearized belief propagation, classical and nonbacktracking spectral methods. A few open problems are also discussed.

即使机器学习算法已经在数据科学中发挥了重要作用，但许多当前方法对输入数据提出了不现实的假设。由于不兼容的数据格式，或数据集中的异质，分层或完全缺少的数据片段，因此很难应用此类方法。作为解决方案，我们提出了一个用于样本表示，模型定义和培训的多功能，统一的框架，称为“ Hmill”。我们深入审查框架构建和扩展的机器学习的多个范围范式。从理论上讲，为HMILL的关键组件的设计合理，我们将通用近似定理的扩展显示到框架中实现的模型所实现的所有功能的集合。本文还包含有关我们实施中技术和绩效改进的详细讨论，该讨论将在MIT许可下发布供下载。该框架的主要资产是其灵活性，它可以通过相同的工具对不同的现实世界数据源进行建模。除了单独观察到每个对象的一组属性的标准设置外，我们解释了如何在框架中实现表示整个对象系统的图表中的消息推断。为了支持我们的主张，我们使用框架解决了网络安全域的三个不同问题。第一种用例涉及来自原始网络观察结果的IoT设备识别。在第二个问题中，我们研究了如何使用以有向图表示的操作系统的快照可以对恶意二进制文件进行分类。最后提供的示例是通过网络中实体之间建模域黑名单扩展的任务。在所有三个问题中，基于建议的框架的解决方案可实现与专业方法相当的性能。

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

Motivated by alignment of correlated sparse random graphs, we introduce a hypothesis testing problem of deciding whether or not two random trees are correlated. We obtain sufficient conditions under which this testing is impossible or feasible. We propose MPAlign, a message-passing algorithm for graph alignment inspired by the tree correlation detection problem. We prove MPAlign to succeed in polynomial time at partial alignment whenever tree detection is feasible. As a result our analysis of tree detection reveals new ranges of parameters for which partial alignment of sparse random graphs is feasible in polynomial time. We then conjecture that graph alignment is not feasible in polynomial time when the associated tree detection problem is impossible. If true, this conjecture together with our sufficient conditions on tree detection impossibility would imply the existence of a hard phase for graph alignment, i.e. a parameter range where alignment cannot be done in polynomial time even though it is known to be feasible in non-polynomial time.

我们为保留部分顺序的部分有序数据的基于相似性的分层群集提供了一个目标函数。也就是说，如果$ x \ le y $，如果$ [x] $和$ [y] $是$ x $和$ y $的相应群集，那么有一个订单关系$ \ LE' $群集$ [x] \ Le'| Y] $。该理论将本身与现有的理论区分开了用于统称有序数据的理论，因为顺序关系和相似性被组合成双目标优化问题，以获得寻求满足两者的分层聚类。特别地，顺序关系在$ [0,1] $的范围内加权，如果相似性和顺序关系未对齐，则订单保存可能必须屈服于群集。找到最佳解决方案是NP-HARD，因此我们提供多项式时间近似算法，具有$ O \左的相对性能保证（\ log ^ {3/2} \！\！\，n \右）$ ，基于定向稀疏性切割的连续应用。我们在基准数据集中提供了演示，显示我们的方法优于具有重要边距的顺序保留分层聚类的现有方法。该理论是划分分层聚类的Dasgupta成本函数的扩展。

随机块模型（SBM）是一个随机图模型，其连接不同的顶点组不同。它被广泛用作研究聚类和社区检测的规范模型，并提供了肥沃的基础来研究组合统计和更普遍的数据科学中出现的信息理论和计算权衡。该专着调查了最近在SBM中建立社区检测的基本限制的最新发展，无论是在信息理论和计算方案方面，以及各种恢复要求，例如精确，部分和弱恢复。讨论的主要结果是在Chernoff-Hellinger阈值中进行精确恢复的相转换，Kesten-Stigum阈值弱恢复的相变，最佳的SNR - 单位信息折衷的部分恢复以及信息理论和信息理论之间的差距计算阈值。该专着给出了在寻求限制时开发的主要算法的原则推导，特别是通过绘制绘制，半定义编程，（线性化）信念传播，经典/非背带频谱和图形供电。还讨论了其他块模型的扩展，例如几何模型和一些开放问题。

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.