Optimal Decomposition of Belief Networks

2013/03/27 by Wilson X. Wen, Wen, Wilson X.
Computer Science · #Bayesian Modeling and Causal Inference #Machine Learning and Algorithms #Neural Networks and Applications

paper · pdf · doi:10.48550/arxiv.1304.1111

Abstract

In this paper, optimum decomposition of belief networks is discussed. Some methods of decomposition are examined and a new method - the method of Minimum Total Number of States (MTNS) - is proposed. The problem of optimum belief network decomposition under our framework, as under all the other frameworks, is shown to be NP-hard. According to the computational complexity analysis, an algorithm of belief network decomposition is proposed in (Wee, 1990a) based on simulated annealing.

Cited by

• Efficient Approximation for Triangulation of Minimum Treewidth
• From Relational Databases to Belief Networks
• Non-Minimal Triangulations for Mixed Stochastic/Deterministic Graphical Models
• A computational scheme for Reasoning in Dynamic Probabilistic Networks

Related

• Using Tree-Decomposable Structures to Approximate Belief Networks
• An efficient approach for finding the MPE in belief networks
• Minimum Error Tree Decomposition
• On Heuristics for Finding Loop Cutsets in Multiply-Connected Belief Networks
• Ideal Reformulation of Belief Networks