All Roads Lead To Rome: New Search Methods for Optimal
Thorsten J. Ottosen, Jiří Vomlel · VBN Forskningsportal (Aalborg Universitet) · 2010
To perform ecient inference in Bayesian networks, the network graph needs to be triangu- lated. The quality of this triangulation largely determines the efficiency of the subsequent inference, but the triangulation problem is unfortunately NP-hard. It is common for ex- isting methods to use the treewidth criterion for optimality of a triangulation. However, this criterion may lead to a somewhat harder inference problem than the total table size criterion. We therefore investigate new methods for depth-first search and best-first search for finding optimal total table size triangulations. The search methods are made faster by eficient dynamic maintenance of the cliques of a graph. The algorithms are mainly sup- posed to be off-line methods, but they may form the basis for ecient any-time heuristics. Furthermore, the methods make it possible to evaluate the quality of heuristics precisely.