Inference in belief networks: A procedural guide

This document provides a self-contained, procedural guide to understanding and implementing probability propagation in trees of clusters (PPTC), and synthesizes various optimizations to PPTC that are scattered throughout the literature.

Abstract

Belief networks are popular tools for encoding uncertainty in expert systems. These networks rely on inference algorithms to compute beliefs in the context of observed evidence. One established method for exact inference on belief networks is the probability propagation in trees of clusters (PPTC) algorithm, as developed by Lauritzen and Spiegelhalter and refined by Jensen et al. PPTC converts the belief network into a secondary structure, then computes probabilities by manipulating the secondary structure. In this document, we provide a self-contained, procedural guide to understanding and implementing PPTC. We synthesize various optimizations to PPTC that are scattered throughout the literature. We articulate undocumented "open secrets" that are vital to producing a robust and efficient implementation of PPTC. We hope that this document makes probabilistic inference more accessible and affordable to those without extensive prior exposure.