Turbocharging Treewidth-Bounded Bayesian Network Structure Learning
This addresses the scalability problem for Bayesian Network structure learning in domains like bioinformatics or AI, though it is incremental as it builds on existing methods.
They tackled learning treewidth-bounded Bayesian Network structures by combining exact and heuristic methods, scaling to thousands of variables and improving scores over state-of-the-art heuristics, often significantly.
We present a new approach for learning the structure of a treewidth-bounded Bayesian Network (BN). The key to our approach is applying an exact method (based on MaxSAT) locally, to improve the score of a heuristically computed BN. This approach allows us to scale the power of exact methods -- so far only applicable to BNs with several dozens of random variables -- to large BNs with several thousands of random variables. Our experiments show that our method improves the score of BNs provided by state-of-the-art heuristic methods, often significantly.