Pre-processing for Triangulation of Probabilistic Networks
Hans Bodlaender, Arie Koster, Frank van den Eijkhof, Linda van der Gaag
The currently most efficient algorithm for inference with a probabilistic network builds upon a triangulation of a network's graph. In this paper, we show that pre-processing can help in finding good triangulations forprobabilistic networks, that is, triangulations with a minimal maximum clique size. We provide a set of rules for stepwise reducing a graph, without losing optimality. This reduction allows us to solve the triangulation problem on a smaller graph. From the smaller graph's triangulation, a triangulation of the original graph is obtained by reversing the reduction steps. Our experimental results show that the graphs of some well-known real-life probabilistic networks can be triangulated optimally just by preprocessing; for other networks, huge reductions in their graph's size are obtained.
PDF Link: /papers/01/p32-bodlaender.pdf
AUTHOR = "Hans Bodlaender
and Arie Koster and Frank van den Eijkhof and Linda van der Gaag",
TITLE = "Pre-processing for Triangulation of Probabilistic Networks",
BOOKTITLE = "Proceedings of the Seventeenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-01)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "2001",
PAGES = "32--39"