Depicting variable elimination with Bayesian networks

Abstract

This thesis presents a novel graphical representation of variable elimination in discrete Bayesian networks (BNs) utilizing the BN’s directed acyclic graph (DAG) component. This includes methods representing both multiplication and marginalization operations. This graphical representation is achieved by introducing what are known as compound BN nodes, whose presence denotes a compound BN. The key to fitting them into the pre-existing BN DAG is to re-evaluate what a single node in the DAG represents; not a single variable, but the left-hand side of a single conditional probability table (CPT) of the BN. Using compound BNs allows for more descriptive nodes that can better represent the dependency relationship between variables as they are merged and marginalized out according to the variable elimination algorithm (VE), which is used for efficient probabilistic inference using BNs. This thesis also presents an application which implements the graphical representation of VE. This implementation follows the introduced d-separation algorithm to add edges to preserve the dependencies for the elimination target’s parents, children, and spouse nodes. Node multiplication, as it is conceptually understood, is redundant in this implementation as it does not need to generate and modify compound nodes; just delete classic BN nodes and their edges after adding compensatory edges according to d-separation. The work presented in this thesis precisely depicts the recursive elimination of arbitrary variables as classical BNs. This new graphical representation is an improvement over previous literature, which is currently limited to graphically representing the probability information as a sub-DAG prior to variable elimination starting or special cases of variable elimination. Other previous attempts in the literature would take a non-Bayesian approach to representing arbitrary variable elimination, whereas this graphical representation is done entirely by utilizing a BN DAG.