Pre-processing for triangulation of probabilistic networks

H.L. Bodlaender, A.M.C.A. Koster, F. van den Eijkhof, L.C. van der Gaag

Research output: Contribution to journalArticleAcademic

18 Downloads (Pure)

Abstract

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.
Original languageEnglish
Article number1301.2256v1
Pages (from-to)1-8
Number of pages8
JournalarXiv
Issue number1301.2256v1
Publication statusPublished - 10 Jan 2013

Bibliographical note

Appears in Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence (UAI2001)

Keywords

  • cs.AI
  • cs.DS

Fingerprint Dive into the research topics of 'Pre-processing for triangulation of probabilistic networks'. Together they form a unique fingerprint.

Cite this