Identifying independence in bayesian networks

TLDR

Bayesian networks encode domain independencies, enabling efficient inference. The study aims to characterize all independence assertions implied by a network’s topology and to devise a linear‑time algorithm to identify them. The algorithm uses d‑separation (and its extension D‑separation for functional dependencies) to correctly and optimally identify independencies in linear time. The algorithm successfully identifies a broad class of nonprobabilistic independencies.

Abstract

Abstract An important feature of Bayesian networks is that they facilitate explicit encoding of information about independencies in the domain, information that is indispensable for efficient inferencing. This article characterizes all independence assertions that logically follow from the topology of a network and develops a linear time algorithm that identifies these assertions. The algorithm's correctness is based on the soundness of a graphical criterion, called d ‐separation, and its optimality stems from the completeness of d ‐separation. An enhanced version of d ‐separation, called D ‐separation, is defined, extending the algorithm to networks that encode functional dependencies. Finally, the algorithm is shown to work for a broad class of nonprobabilistic independencies.