A Depth-First Search Algorithm for Optimal Triangulation of Bayesian Network
Chao Li, Maomi Ueno · 2012
Finding the triangulation of a Bayesian network with minimum total table size reduces the computational cost for probabilistic reasoning in the Bayesian network. This task can be done by conducting a search in the space of all possible elimination orders of the Bayesian network. However, such a search is known to be NP-hard. To relax this problem, Ottosen and Vomlel (2010b) proposed a depth-first branch and bound algorithm, which reduces the computational complexity from Θ(β ·| V|!) to O(β ·| V|!), where β describes the overhead computation per node in the search space, and where |V|! is the search space size. Nevertheless, this algorithm entails a heavy computational cost. To mitigate this problem, this paper presents a proposal of an extended algorithm with the following features: (1) Reduction of the search space to O ((|V|-1)!) using Dirac’s theorem, and (2) reduction of the computational cost β per node. Some simulation experiments show that the proposed method is consistently faster than Ottosen and Vomlel’s method.