The idea of ILP learning decomposable models: chordal graph polytope

The integer linear programming approach to structural learning graphical models is based on the idea to represent them by means of special vectors, whose components are integers. In the context of learning decomposable models, we propose to represent them by special zero-one vectors, named characteristic imsets (of the corresponding Bayesian network model) [1]. This idea leads to the study of a special polytope, defined as the convex hull of all characteristic imsets for chordal graphs we name the chordal graph polytope [2]. The talk will be devoted to the attempts to characterize theoretically all facet-defining inequalities for this polytope in order to utilize that in ILP-based procedures for learning decomposable models.

The talk is based on joint research with James Cussens from York University, UK.