Graphical models are popular statistical tools which are used to represent dependent or causal complex systems. Statistically equivalent causal or directed graphical models are said to belong to a Markov equivalent class. It is of great interest to describe and understand the space of such classes. However, with curren…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “Markov Equivalent Classes”
The paper shows that relaxing assumptions about causal graphs can lead to exponentially large equivalence classes.
problem The size of Markov equivalence classes under relaxed assumptions.
method Analytical proofs for three settings: sparse random directed acyclic graphs, uniformly random acyclic directed mixed graphs, and uniformly random directed cyclic graphs.
result Exponentially large lower bounds for the expected size of Markov equivalence classes.
The sizes of Markov equivalence classes of directed acyclic graphs play important roles in measuring the uncertainty and complexity in causal learning. A Markov equivalence class can be represented by an essential graph and its undirected subgraphs determine the size of the class. In this paper, we develop a method to …
A Characterization of Markov Equivalence Classes for Directed Acyclic Graphs with Latent Variablesstat.ME
Different directed acyclic graphs (DAGs) may be Markov equivalent in the sense that they entail the same conditional independence relations among the observed variables. Meek (1995) characterizes Markov equivalence classes for DAGs (with no latent variables) by presenting a set of orientation rules that can correctly i…
In this paper we discuss four problems regarding Markov equivalences for subclasses of loopless mixed graphs. We classify these four problems as finding conditions for internal Markov equivalence, which is Markov equivalence within a subclass, for external Markov equivalence, which is Markov equivalence between subclas…
Polynomial-time methods count and sample DAGs from Markov classes.
problem Counting and sampling Markov equivalent DAGs.
method Polynomial-time algorithms for DAGs from Markov classes.
result Long-standing open problem solved, making practical infeasible strategies feasible.
A new sampler improves the inference of causal structures from observational data.
problem Inferring causal relationships from observational data when DAGs are Markov equivalent.
method Developed a non-reversible Markov chain, Causal Zig-Zag sampler, targeting Markov Equivalence Classes of DAGs.
result The sampler improves mixing and offers efficient algorithms for DAG inference.
Polynomial-time methods count and sample DAGs from equivalence classes.
problem Counting and sampling DAGs from Markov equivalence classes.
method Polynomial-time algorithms for DAGs.
result Counting and sampling can be done in polynomial time.
Supplement to "Reversible MCMC on Markov equivalence classes of sparse directed acyclic graphs"stat.ML
This supplementary material includes three parts: some preliminary results, four examples, an experiment, three new algorithms, and all proofs of the results in the paper "Reversible MCMC on Markov equivalence classes of sparse directed acyclic graphs".
Study restricts causal graphs with expert knowledge.
problem Restricting causal graphs to include expert orientation knowledge.
method Prove properties, present new orientation rules, develop algorithms.
result Shows how to uniquely represent restricted essential ancestral graphs.
A directed acyclic graph (DAG) is the most common graphical model for representing causal relationships among a set of variables. When restricted to using only observational data, the structure of the ground truth DAG is identifiable only up to Markov equivalence, based on conditional independence relations among the v…
New algorithm estimates causal effects for non-Gaussian data.
problem Estimating causal effects in non-Gaussian distributions.
method Generalized k-Triangle Faithfulness Assumption and Edge Estimation Algorithm.
result Uniformly consistent estimates of causal effects.
Characterizes Bayesian networks up to unconditional equivalence.
problem Characterizing Bayesian networks up to unconditional equivalence.
method Transformational characterization via undirected graphs and specified moves.
result Two DAGs are in the same UEC if and only if one can be transformed into the other via a finite sequence of moves.
A new algorithm for robust causal discovery in small sample sizes.
problem Limited data leads to weak conditional independence tests in causal discovery.
method Proposes a -PC algorithm that bounds conditioning set size for robust causal discovery.
result The -PC algorithm enables more robust causal discovery in small sample sizes.
MEC-IP uses IP to efficiently find MECs in BNs from observational data.
problem Discovering Markov Equivalent Classes (MECs) in Bayesian Networks (BNs) efficiently.
method Clique-focusing strategy and EMSG for MEC discovery via Integer Programming.
result Significant reduction in computational time and improved accuracy.
Differentiable structure learning addresses DAGs with multiple global minimizers.
problem Identify the true DAG from global minimizers of acyclicity-constrained optimization problems.
method Carefully regularize the likelihood to identify the sparsest model in the Markov equivalence class.
result Regularization of the likelihood defines a score that identifies the sparsest model in general models and likelihoods.
Epsilon-machines are minimal, unifilar presentations of stationary stochastic processes. They were originally defined in the history machine sense, as hidden Markov models whose states are the equivalence classes of infinite pasts with the same probability distribution over futures. In analyzing synchronization, though…
Paper proposes scalable algorithm to estimate intervention targets in linear models.
problem Estimating intervention targets in linear models from observational and interventional data.
method The paper proposes a scalable algorithm that estimates intervention sites from the difference between precision matrices of observational and interventional datasets.
result The algorithm consistently identifies all intervention targets and updates observational Markov equivalence classes to interventional ones.
A fast algorithm for counting Markov equivalent DAGs and designing experiments.
problem Counting Markov equivalent DAGs and designing experiments efficiently.
method LazyIter algorithm for efficient iteration over MECs, utilizing intervention results.
result Significant reduction in time complexity for sparse graphs (O(n)).
Novel graphical models for time series with latent confounders improve causal inference.
problem Causal relationships and independencies in multivariate time series with unobserved confounders.
method Introduced a novel class of graphical models and characterized their properties.
result Novel graphs provide stronger causal inferences without additional assumptions.
The paper develops methods to bound causal effects using Partial Ancestral Graphs.
problem Bounding causal effects from observational data when true causal diagrams are unknown.
method Proposes a method using Partial Ancestral Graphs to derive bounds on causal effects from observational data.
result Demonstrates the effectiveness of the method with synthetic and real data examples.
Bayesian method for causal discovery from unknown general interventions.
problem Learning causal DAGs from unknown interventions that modify parent sets.
method Bayesian approach with MCMC for approximating posterior DAGs and intervention targets.
result Bayesian method can identify DAGs and intervention targets up to equivalence classes.
New method estimates causal effects without knowing graph structure.
problem Estimating causal effects when graph structure is unknown.
method Testable conditional independence statements for front-door adjustment.
result Effect estimation without Markov equivalence class knowledge.
Bayesian model selection improves causal discovery in complex datasets.
problem Identifying causal direction in Markov equivalence classes with realistic assumptions.
method Incorporating causal assumptions within Bayesian framework for model selection.
result Bayesian model selection outperforms previous methods on various datasets.
Markov models lie at the interface between statistical independence in a probability distribution and graph separation properties. We review model selection and estimation in directed and undirected Markov models with Gaussian parametrization, emphasizing the main similarities and differences. These two model classes a…
In this paper, we unify the Markov theory of a variety of different types of graphs used in graphical Markov models by introducing the class of loopless mixed graphs, and show that all independence models induced by -separation on such graphs are compositional graphoids. We focus in particular on the subclass of rib…
A new method for efficient causal structure learning at scale.
problem Causal structure learning is computationally challenging at scale.
method Relaxed sparsest-permutation formulation with support-level relaxation and masked zero-fill incomplete Cholesky factorization.
result The method enables scalable comparison of candidate orderings and matches the accuracy of slower baselines.
This project attempts to address the problem of asset pricing in a financial market, where the interest rates and volatilities exhibit regime switching. This is an extension of the Black-Scholes model. Studies of Markov-modulated regime switching models have been well-documented. This project extends that notion to a c…
Unifying DAGs and UGsstat.ML
We introduce a new class of graphical models that generalizes Lauritzen-Wermuth-Frydenberg chain graphs by relaxing the semi-directed acyclity constraint so that only directed cycles are forbidden. Moreover, up to two edges are allowed between any pair of nodes. Specifically, we present local, pairwise and global Marko…
We prove that the criterion for Markov equivalence provided by Zhao et al. (2005) may involve a set of features of a graph that is exponential in the number of vertices.
New method resolves inconsistency in learning directed acyclic graphs using penalized likelihood.
problem Inconsistency of -penalized likelihood in learning directed acyclic graphs.
method Developed a hybrid differentiable structure learning method based on -penalized likelihood with hard acyclicity constraint.
result Demonstrated and explained why -penalized likelihood is fundamentally inconsistent in identifying true structure up to Markov equivalence classes.
Directed acyclic graph (DAG) models are popular for capturing causal relationships. From observational and interventional data, a DAG model can only be determined up to its \emph{interventional Markov equivalence class} (I-MEC). We investigate the size of MECs for random DAG models generated by uniformly sampling and o…
Overview of risk-sensitive Markov decision processes with Optimized Certainty Equivalent.
problem Optimizing decision-making under risk in Markov processes.
method Analyzes risk-sensitive criteria using Optimized Certainty Equivalent, including entropic risk and Conditional Value-at-Risk.
result Conditions for the existence of optimal policies and solution procedures are provided.
The search space of Bayesian Network structures is usually defined as Acyclic Directed Graphs (DAGs) and the search is done by local transformations of DAGs. But the space of Bayesian Networks is ordered by DAG Markov model inclusion and it is natural to consider that a good search policy should take this into account.…
New measures assess differences in causal graphs' separations.
problem Evaluating causal discovery algorithms' output.
method Proposes new distance measures capturing causal graphs' separations.
result Proposed distances assess differences in causal graphs' separations.
Paper characterizes and represents pairwise causal background knowledge for improved causal inference.
problem Improving causal inference by handling pairwise causal constraints.
method Graphical characterization, direct causal clause (DCC), unified representation, MPDAG, polynomial-time algorithms.
result Pairwise causal background knowledge uniquely decomposes into MPDAG and DCCs, improving causal effect identification.
Ordinal Causal Discoverystat.ME
New method uniquely identifies causal structure from ordinal data.
problem Challenges in causal discovery for categorical data, especially direction of relationships.
method Exploits ordinal information to uniquely identify causal structure.
result Favorable and robust performance compared to state-of-the-art methods.
Local method identifies causal relations in Markov equivalent DAGs.
problem Identifying causal relations when multiple DAGs are Markov equivalent.
method Graphical condition and local criteria for identifying causal paths.
result Local learning algorithm efficiently identifies causal variables.
Model identifies causal structure from paired observational and interventional data with unknown soft interventions.
problem Identifying causal structure from observational and interventional data with unknown soft interventions.
method Proposes a scalable causal discovery model that aggregates subset-level PDAGs and applies contrastive cross-regime orientation rules.
result The model asymptotically recovers the identifiable PDAG and can orient additional edges compared to non-contrastive subset-restricted methods.
New protocol identifies impossible edge orientations in causal graphs.
problem Causal-discovery algorithms cannot distinguish edge directions without assumptions.
method Discrete impossibility certificates and oracle queries.
result Upper bound of expert interactions for DAG recovery.
Let denote the classical braid group on strands and let the {\em mixed braid group} be the subgroup of comprising braids for which the first strands form the identity braid. Let . We will describe explicit algebraic moves on such that equivale…
New method tests causal relationships from data without needing to learn the entire graph.
problem Testing if a causal graph belongs to a specific Markov equivalence class from observational data.
method Established bounds on the number of independence tests required and provided an algorithm that matches these bounds.
result Testing requires exponentially less independence tests compared to learning, especially in graphs with high in-degrees and small clique sizes.
LGES speeds up causal discovery while maintaining accuracy.
problem Causal discovery from observational data with computational and accuracy limitations.
method LGES modifies GES by avoiding certain edge insertions, using prior knowledge, and leveraging interventional data.
result LGES outperforms GES in speed, accuracy, and robustness to misspecified knowledge.
Learning AMP Chain Graphs and some Marginal Models Thereof under Faithfulness: Extended Versionstat.ML
This paper deals with chain graphs under the Andersson-Madigan-Perlman (AMP) interpretation. In particular, we present a constraint based algorithm for learning an AMP chain graph a given probability distribution is faithful to. Moreover, we show that the extension of Meek's conjecture to AMP chain graphs does not hold…
Causal graphs, such as directed acyclic graphs (DAGs) and partial ancestral graphs (PAGs), represent causal relationships among variables in a model. Methods exist for learning DAGs and PAGs from data and for converting DAGs to PAGs. However, these methods are significantly limited in that they only output a single cau…
Reframed GES uses a neural conditional dependence measure for consistent causal structure learning.
problem Identifying causal structure in nonparametric settings.
method Reframed GES algorithm with a neural conditional dependence measure.
result Optimality and consistency of the reframed GES algorithm under standard assumptions.
Specialized knot theory theorems for strongly involutive links.
problem Classical Alexander and Markov theorems for links.
method Equivariant closure map for strongly involutive links.
result Surjective equivariant closure map up to equivalence of strongly involutive links.
We consider the task of learning a causal graph in the presence of latent confounders given i.i.d.~samples from the model. While current algorithms for causal structure discovery in the presence of latent confounders are constraint-based, we here propose a score-based approach. We prove that under assumptions weaker th…