Skip to main content

James Cussens: Branch-price-and-cut for Bayesian network structure learning

Time: Tue 2021-05-25 11.15

Location: Zoom, meeting ID: 625 8662 8413

Participating: James Cussens (University of Bristol)

Export to calendar

Abstract

A Bayesian network structure is an acyclic directed graph (DAG) which encodes conditional independence relations between random variables in a joint distribution. One option for learning such a DAG from data is to encode the graph learning problem as an integer linear program (ILP) and send the problem to an ILP solver to solve. Unfortunately, the number of ILP variables required to represent the problem grows exponentially with the number of random variables. In this talk I will report on ongoing work to get round this problem. The key idea is to add only those ILP variables which are 'necessary' into the ILP during the course of solving the ILP, a well-known ILP technique called 'pricing'. The talk will not assume prior knowledge of Bayesian network structure learning or integer linear programming.