The Complexity of Morality: Checking Markov Blanket Consistency with DAGs via Morality
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 are equivalent to graph morality. In addition, we prove that morality can be decided in polynomial time for graphs with maximum degree less than $5$, but the problem is NP-complete for graphs with higher maximum degrees.
Code (1)
Similar Papers 제목 키워드 기반
Blankets Joint Posterior score for learning Markov network structures
Markov networks are extensively used to model complex sequential, spatial, and relational interactions in a wide range of fields. By learning the structure of independences of a domain, more accurate joint probability di…
Knitting a Markov blanket is hard when you are out-of-equilibrium: two examples in canonical nonequilibrium models
Bayesian theories of biological and brain function speculate that Markov blankets (a conditional independence separating a system from external states) play a key role for facilitating inference-like behaviour in living …
Learning LWF Chain Graphs: A Markov Blanket Discovery Approach
This paper provides a graphical characterization of Markov blankets in chain graphs (CGs) under the Lauritzen-Wermuth-Frydenberg (LWF) interpretation. The characterization is different from the well-known one for Bayesia…
Probably approximately correct high-dimensional causal effect estimation given a valid adjustment set
Accurate estimates of causal effects play a key role in decision-making across applications such as healthcare, economics, and operations. In the absence of randomized experiments, a common approach to estimating causal …
PAC learningvalidBayesian Markov Blanket Estimation
This paper considers a Bayesian view for estimating a sub-network in a Markov random field. The sub-network corresponds to the Markov blanket of a set of query variables, where the set of potential neighbours here is big…