Belief Network Support via Decision Diagrams

This paper proposes improving the efficiency of belief (Bayesian) networks (BNs) by embedding decision diagrams (DDs) in place of the conditional probability tables (distributed local memories of BNs). The resulting hybrid graphical data structure is a high-efficiency BN which can be used for the modelling of large-scale multi-state systems. For example if the number of values attainable by all nodes is r, and the number of parent nodes of the current node is n, then the complexity of the representation of a conditional probability table (CPT) is reduced in some cases from O(rn+1) to O(rn) when the conditional probability tables are replaced with DDs. The approach is demonstrated via illustrative examples for binary and ternary systems.