Efficient Enumeration of Markov Equivalent DAGs
- URL: http://arxiv.org/abs/2301.12212v2
- Date: Mon, 18 Dec 2023 11:13:45 GMT
- Title: Efficient Enumeration of Markov Equivalent DAGs
- Authors: Marcel Wien\"obst and Malte Luttermann and Max Bannach and Maciej
Li\'skiewicz
- Abstract summary: In this paper, we present the first linear-time delay algorithm.
On the theoretical side, we show that our algorithm can be generalized to enumerate DAGs represented by models that incorporate background knowledge.
We also provide intriguing insights into Markov equivalence itself.
- Score: 6.288056740658763
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Enumerating the directed acyclic graphs (DAGs) of a Markov equivalence class
(MEC) is an important primitive in causal analysis. The central resource from
the perspective of computational complexity is the delay, that is, the time an
algorithm that lists all members of the class requires between two consecutive
outputs. Commonly used algorithms for this task utilize the rules proposed by
Meek (1995) or the transformational characterization by Chickering (1995), both
resulting in superlinear delay. In this paper, we present the first linear-time
delay algorithm. On the theoretical side, we show that our algorithm can be
generalized to enumerate DAGs represented by models that incorporate background
knowledge, such as MPDAGs; on the practical side, we provide an efficient
implementation and evaluate it in a series of experiments. Complementary to the
linear-time delay algorithm, we also provide intriguing insights into Markov
equivalence itself: All members of an MEC can be enumerated such that two
successive DAGs have structural Hamming distance at most three.
Related papers
- An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks.
The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions.
We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
arXiv Detail & Related papers (2023-09-30T15:57:14Z) - Quick Adaptive Ternary Segmentation: An Efficient Decoding Procedure For
Hidden Markov Models [70.26374282390401]
Decoding the original signal (i.e., hidden chain) from the noisy observations is one of the main goals in nearly all HMM based data analyses.
We present Quick Adaptive Ternary (QATS), a divide-and-conquer procedure which decodes the hidden sequence in polylogarithmic computational complexity.
arXiv Detail & Related papers (2023-05-29T19:37:48Z) - Towards Better Out-of-Distribution Generalization of Neural Algorithmic
Reasoning Tasks [51.8723187709964]
We study the OOD generalization of neural algorithmic reasoning tasks.
The goal is to learn an algorithm from input-output pairs using deep neural networks.
arXiv Detail & Related papers (2022-11-01T18:33:20Z) - Exploring the Algorithm-Dependent Generalization of AUPRC Optimization
with List Stability [107.65337427333064]
optimization of the Area Under the Precision-Recall Curve (AUPRC) is a crucial problem for machine learning.
In this work, we present the first trial in the single-dependent generalization of AUPRC optimization.
Experiments on three image retrieval datasets on speak to the effectiveness and soundness of our framework.
arXiv Detail & Related papers (2022-09-27T09:06:37Z) - Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for
Scalar Data -- An Algorithm and A Benchmark [8.648433479399857]
This paper introduces an efficient algorithm for persistence diagram computation, given an input piecewise linear scalar field f defined on a d-dimensional simplicial complex K.
We express this algorithm within the setting of discrete Morse theory, which considerably reduces the number of input simplices to consider.
We also introduce a stratification approach to the problem, that we call "sandwiching"
arXiv Detail & Related papers (2022-06-27T10:54:24Z) - Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent
DAGs with Applications [6.03124479597323]
Counting and sampling directed acyclic graphs from a Markov equivalence class are fundamental tasks in causal analysis.
We show that these tasks can be performed in graphical time, solving a long-standing open problem in this area.
Our algorithms are effective and easily implementable.
arXiv Detail & Related papers (2022-05-05T13:56:13Z) - DAGs with No Curl: An Efficient DAG Structure Learning Approach [62.885572432958504]
Recently directed acyclic graph (DAG) structure learning is formulated as a constrained continuous optimization problem with continuous acyclicity constraints.
We propose a novel learning framework to model and learn the weighted adjacency matrices in the DAG space directly.
We show that our method provides comparable accuracy but better efficiency than baseline DAG structure learning methods on both linear and generalized structural equation models.
arXiv Detail & Related papers (2021-06-14T07:11:36Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
Bilevel optimization has been widely applied in many important machine learning applications.
We propose two new algorithms for bilevel optimization.
We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
arXiv Detail & Related papers (2021-06-08T21:05:30Z) - Temporal Parallelization of Inference in Hidden Markov Models [0.0]
This paper presents algorithms for parallelization of inference in hidden Markov models (HMMs)
We propose parallel backward-forward type of filtering and smoothing algorithm as well as parallel Viterbi-type maximum-a-posteriori (MAP)
We empirically compare the performance of the proposed methods to classical methods on a highly parallel processing unit (GPU)
arXiv Detail & Related papers (2021-02-10T21:26:09Z) - Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent
DAGs [6.252236971703546]
Counting and uniform sampling of directed acyclic graphs (DAGs) are fundamental in causal analysis.
In this paper, we show that these tasks can be performed from graphical time, solving a long-standing open problem in this area.
Our algorithms are effective and easily implementable.
arXiv Detail & Related papers (2020-12-17T15:47:15Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.