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…
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 equivalence”
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…
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.
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.
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…
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.
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 …
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.
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.
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.
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".
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.
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…
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.
Marginal AMP Chain Graphsstat.ML
We present a new family of models that is based on graphs that may have undirected, directed and bidirected edges. We name these new models marginal AMP (MAMP) chain graphs because each of them is Markov equivalent to some AMP chain graph under marginalization of some of its nodes. However, MAMP chain graphs do not onl…
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.
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…
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.
This paper optimizes MDP policies for efficient state aggregation.
problem Optimizing policies in aggregated Markov chains while preserving optimal performance.
method Homomorphic mappings to establish optimal policy equivalence and derive performance bounds.
result Developed HPG and EBHPG methods for efficient aggregation and policy optimization.
Hidden Markov Chains and Linear-chain CRFs are equivalent.
problem Comparing Hidden Markov Chains and Conditional Random Fields.
method Constructing an HMC with the same posterior distribution as a CRF.
result HMCs and linear-chain CRFs are equivalent models.
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 Semi-Hidden Markov Model (SHMM) for bursty error channels is defined by a state transition probability matrix , a prior probability vector , and the state dependent output symbol error probability matrix . Several processes are utilized for estimating , and from a given empirically obtained or sim…
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.
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)).
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.
A Markov theorem for plat closure of surface braids in Dunwoody and periodic Takahashi manifoldsmath.GT
The article finds equivalence moves for links in specific manifolds using plat closure of braids.
problem Finding equivalence moves for links in Dunwoody and periodic Takahashi manifolds.
method Representing manifolds with Heegaard splitting and braids, determining equivalence moves algorithmically and computing them explicitly.
result Explicit computation of equivalence moves for some cases.
The paper defines conditions for learning causal graphs from data with unobserved variables.
problem Learning causal graphs from data with unobserved variables.
method Formalizes constraint-based structure learning algorithms under conditions and assumptions.
result Natural family of algorithms output Markov equivalent graphs to the causal graph under faithfulness assumption.
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.
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.
In 1997 M.~Khovanov proved that any doodle can be presented as closure of twin, this result is analogue of classical Alexander's theorem for braids and links. We give a description of twins that have equivalent closures, this theorem is analogue of classical Markov theorem.
We prove a Markov theorem for tame links in a connected closed orientable 3-manifold with respect to a plat-like representation. More precisely, given a genus Heegaard surface for we represent each link in as the plat closure of a braid in the surface braid group and an…
Chow and Liu (1968) studied the problem of learning a maximumlikelihood Markov tree. We generalize their work to more complexMarkov networks by considering the problem of learning a maximumlikelihood Markov network of bounded complexity. We discuss howtree-width is in many ways the appropriate measure of complexity and…
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…
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.
Q-learning for average cost MDPs gets a concentration bound.
problem Finding bounds for Q-learning in average cost MDPs.
method Derives a concentration bound using shortest path problem equivalence.
result Numerical comparison with relative value iteration shows the bound's effectiveness.
This paper applies AMP theory to improve learning tasks.
problem Improving learning efficiency by optimizing task-specific models.
method Uses aggregated Markov processes to reduce model complexity and enhance learning.
result Demonstrates how AMP theory can be effectively applied to stochastic learning.
We introduce interacting particle Markov chain Monte Carlo (iPMCMC), a PMCMC method based on an interacting pool of standard and conditional sequential Monte Carlo samplers. Like related methods, iPMCMC is a Markov chain Monte Carlo sampler on an extended space. We present empirical results that show significant improv…
Identification and Adaptive Control of Markov Jump Systems: Sample Complexity and Regret Boundscs.LG
This paper tackles adaptive control of unknown Markov jump systems with sample complexity and regret bounds.
problem Adaptive control of unknown Markov jump systems with changing dynamics.
method Identification-based adaptive control using a system identification algorithm and certainty equivalent control.
result The proposed adaptive control scheme achieves regret, improving to with partial knowledge.
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.
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…
A family of Markov blankets in a faithful Bayesian network satisfies the symmetry and consistency properties. In this paper, we draw a bijection between families of consistent Markov blankets and moral graphs. We define the new concepts of weak recursive simpliciality and perfect elimination kits. We prove that they ar…
Knot theory in handlebodiesmath.GT
We consider oriented knots and links in a handlebody of genus through appropriate braid representatives in , which are elements of the braid groups . We prove a geometric version of the Markov theorem for braid equivalence in the handlebody, which is based on the -moves. Using this we then prove tw…
Error AMP Chain Graphsstat.ML
Any regular Gaussian probability distribution that can be represented by an AMP chain graph (CG) can be expressed as a system of linear equations with correlated errors whose structure depends on the CG. However, the CG represents the errors implicitly, as no nodes in the CG correspond to the errors. We propose in this…
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…
New methods solve complex financial equations.
problem Solving backward stochastic differential equations driven by continuous-time Markov chains.
method Multi-stage Euler-Maruyama methods and multilevel spatial discretization.
result Efficiently solved stiff Markov BSDEs.
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.