Projects per year
Abstract
Various algorithms have been proposed for finding a Bayesian network structure that is guaranteed to maximize a given scoring function. Implementations of stateoftheart algorithms, solvers, for this Bayesian network structure learning problem rely on adaptive search strategies, such as branchandbound and integer linear programming techniques. Thus, the time requirements of the solvers are not well characterized by simple functions of the instance size. Furthermore, no single solver dominates the others in speed. Given a problem instance, it is thus a priori unclear which solver will perform best and how fast it will solve the instance. We show that for a given solver the hardness of a problem instance can be efficiently predicted based on a collection of nontrivial features which go beyond the basic parameters of instance size. Specifically, we train and test statistical models on empirical data, based on the largest evaluation of stateoftheart exact solvers to date. We demonstrate that we can predict the runtimes to a reasonable degree of accuracy. These predictions enable effective selection of solvers that perform well in terms of runtimes on a particular instance. Thus, this work contributes a highly efficient portfolio solver that makes use of several individual solvers.
Original language  English 

Journal  Machine Learning 
Volume  107 
Issue number  1 
Pages (fromto)  247283 
Number of pages  37 
ISSN  08856125 
DOIs  
Publication status  Published  Jan 2018 
MoE publication type  A1 Journal articlerefereed 
Fields of Science
 113 Computer and information sciences
 Bayesian networks
 Structure learning
 Algorithm selection
 Hyperparameter optimization
 Empirical hardness
 Algorithm portfolio
 Runtime prediction
 STRUCTURE DISCOVERY
 SEARCH PROBLEMS
 CONSTRAINTS
 SAT
Projects
 3 Finished

Harnessing Constraint Reasoning for Structure Discovery
01/01/2015 → 31/12/2018
Project: University of Helsinki ThreeYear Research Project


Decision Procedures for the Polynomial Hierarchy, Boolean Optimization, and Model Counting
01/09/2014 → 31/08/2019
Project: Research project