A new constraint-based algorithm to learn Bayesian network structure from data: Control of Spurious Pairwise Information (CSPI)

Abstract

A Bayesian network is a directed acyclic graphical representation of a set of variables. This representation occupies the middle ground between a causal network and a simple list of pairwise correlations by including information about dependencies between variables. There are applications of Bayesian networks in many fields, such as financial risk management, bioinformatics and audio-visual perception, to name just a few. However, learning the network structure from data requires an exponential number of conditional independence tests; several algorithms have been proposed in order to reduce the runtime of this procedure. We present a new constraint-based algorithm for learning Bayesian network structure from data, based on Control of Spurious Pairwise Information (CSPI). We limit the computational cost of learning by trading an increase in complexity of the initial steps for a substantial reduction in the complexity of conditional pairwise independence testing. We employ a logging and rollback strategy to reduce the number of missing edges. We show that the CSPI algorithm outperforms several other algorithms in complexity and/or accuracy on benchmark datasets.