Pre-processing for Triangulation of Probabilistic Networks
This work addresses the computational bottleneck of inference in probabilistic networks, offering a practical improvement for researchers and practitioners in AI and machine learning, though it is incremental as it builds on existing triangulation algorithms.
The paper tackles the problem of finding optimal triangulations for probabilistic networks by introducing a pre-processing method that reduces graph size without losing optimality, enabling efficient inference. Experimental results show that some real-life networks can be optimally triangulated solely through pre-processing, while others achieve significant size reductions.
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.