Fast Bayesian Network Structure Learning using Quasi-Determinism Screening

National audienceLearning the structure of Bayesian networks from data is a NP-Hard problem thatinvolves optimization over a super-exponential sized space. In this work, we show that in mostreal life datasets, a number of the arcs contained in the final structure can be pre-screenedat low computational cost with a limited impact on the global graph score. We formalize theidentification of these arcs via the notion of quasi-determinism, and propose an associated algorithm that narrows the structure learning task down to a subset of the original variables.We show, on diverse benchmark datasets, that this algorithm exhibits a significant decrease incomputational time and complexity for only a little decrease in performance score