Premium
PREPROCESSING RULES FOR TRIANGULATION OF PROBABILISTIC NETWORKS *
Author(s) -
Bodlaender Hans L.,
Koster Arie M.C.A.,
Eijkhof Frank van den
Publication year - 2005
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/j.1467-8640.2005.00274.x
Subject(s) - preprocessor , probabilistic logic , graph , computer science , triangulation , algorithm , mathematics , theoretical computer science , artificial intelligence , geometry
Currently, the 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 for probabilistic networks, that is, triangulations with a maximum clique size as small as possible. 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.