Optimal Decomposition of Belief Networks
This addresses a computational efficiency issue for researchers and practitioners in probabilistic graphical models, but it appears incremental as it builds on existing decomposition frameworks.
The paper tackles the problem of optimally decomposing belief networks, proposing the Minimum Total Number of States (MTNS) method and showing the problem is NP-hard, with an algorithm based on simulated annealing introduced in related work.
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.