AMP chain graphs: minimal separators and structure learning algorithms
From MaRDI portal
Publication:5130009
Abstract: We address the problem of finding a minimal separator in an Andersson-Madigan-Perlman chain graph (AMP CG), namely, finding a set Z of nodes that separates a given nonadjacent pair of nodes such that no proper subset of Z separates that pair. We analyze several versions of this problem and offer polynomial-time algorithms for each. These include finding a minimal separator from a restricted set of nodes, finding a minimal separator for two given disjoint sets, and testing whether a given separator is minimal. To address the problem of learning the structure of AMP CGs from data, we show that the PC-like algorithm (Pena, 2012) is order-dependent, in the sense that the output can depend on the order in which the variables are given. We propose several modifications of the PC-like algorithm that remove part or all of this order-dependence. We also extend the decomposition-based approach for learning Bayesian networks (BNs) proposed by (Xie et al., 2006) to learn AMP CGs, which include BNs as a special case, under the faithfulness assumption. We prove the correctness of our extension using the minimal separator results. Using standard benchmarks and synthetically generated models and data in our experiments demonstrate the competitive performance of our decomposition-based method, called LCD-AMP, in comparison with the (modified versions of) PC-like algorithm. The LCD-AMP algorithm usually outperforms the PC-like algorithm, and our modifications of the PC-like algorithm learn structures that are more similar to the underlying ground truth graphs than the original PC-like algorithm, especially in high-dimensional settings. In particular, we empirically show that the results of both algorithms are more accurate and stabler when the sample size is reasonably large and the underlying graph is sparse.
Recommendations
- Learning AMP chain graphs and some marginal models thereof under faithfulness
- Separation and completeness properties for AMP chain graph Markov models.
- Characterizing Markov equivalence classes for AMP chain graph models
- Learning marginal AMP chain graphs under faithfulness
- Learning marginal AMP chain graphs under faithfulness revisited
Cites work
- A hybrid methodology for learning belief networks: BENEDICT
- A Unified Approach to the Characterization of Equivalence Classes of DAGs, Chain Graphs with no Flags and Chain Graphs
- Adaptive probabilistic networks with hidden variables
- Alternative Markov properties for chain graphs
- Ancestral graph Markov models.
- Approximating discrete probability distributions with dependence trees
- Artificial intelligence: with an introduction to machine learning
- Bayesian Networks and Decision Graphs
- Bayesian networks in R. With applications in systems biology
- Bayesian networks. With examples in R
- Causation, prediction, and search
- Chain graph interpretations and their relations revisited
- Characterizing Markov equivalence classes for AMP chain graph models
- Discrete chain graph models
- Efficient enumeration of all minimal separators in a graph
- Efficient Markov Network Structure Discovery Using Independence Tests
- Estimating high-dimensional directed acyclic graphs with the PC-algorithm
- Every LWF and AMP chain graph originates from a set of causal models
- Finding consensus Bayesian network structures
- Graphical models for associations between variables, some of which are qualitative and some quantitative
- Graphical models with R.
- High-dimensional Ising model selection using \(\ell _{1}\)-regularized logistic regression
- High-dimensional structure estimation in Ising models: local separation criterion
- scientific article; zbMATH DE number 5968958 (Why is no real title available?)
- scientific article; zbMATH DE number 992990 (Why is no real title available?)
- scientific article; zbMATH DE number 4174001 (Why is no real title available?)
- scientific article; zbMATH DE number 48812 (Why is no real title available?)
- scientific article; zbMATH DE number 1222287 (Why is no real title available?)
- scientific article; zbMATH DE number 1134987 (Why is no real title available?)
- scientific article; zbMATH DE number 4121482 (Why is no real title available?)
- Indirect causes in dynamic Bayesian networks revisited
- Introduction to algorithms.
- Introduction to Graphical Modelling
- Learning marginal AMP chain graphs under faithfulness revisited
- Linear dependencies represented by chain graphs. With comments and a rejoinder by the authors
- Marginal AMP chain graphs
- Maximum cardinality search for computing minimal triangulations of graphs
- Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data
- On Block Ordering of Variables in Graphical Modelling
- Order-independent constraint-based causal structure learning
- Order-independent structure learning of multivariate regression chain graphs
- Probabilistic graphical models.
- Probabilistic Networks and Expert Systems
- Probabilistic Reasoning in Multiagent Systems
- Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms
- Risk assessment and decision analysis with Bayesian networks.
- Separation and completeness properties for AMP chain graph Markov models.
- Separators and adjustment sets in causal graphs: complete criteria and an algorithmic framework
- The computational complexity of probabilistic inference using Bayesian belief networks
- The max-min hill-climbing Bayesian network structure learning algorithm
- Two operations of merging and splitting components in a chain graph
Cited in
(6)- A decomposition-based algorithm for learning the structure of multivariate regression chain graphs
- scientific article; zbMATH DE number 5968958 (Why is no real title available?)
- Order-independent structure learning of multivariate regression chain graphs
- Factorization, inference and parameter learning in discrete AMP chain graphs
- Identifiability and Consistent Estimation for Gaussian Chain Graph Models
- Chain graph structure learning based on minimal c-separation trees
This page was built for publication: AMP chain graphs: minimal separators and structure learning algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5130009)
